信息工程大学820数据结构2015-2016年考研专业课真题试卷.pdfVIP

信息工程大学2016年考研专业课真题试卷（原版）

820数据结构

（共十一题，满分150分）

一、填空题（20分，每空2分）

1.数据的存储结构可用四种基本的存储方法表示，它们分别

是、、和。

2.算法是指。

3.在n个结点的单链表中要删除已知结点*p，需找到它

的，其时间复杂度为。

4.设串s1=‘ABCDEFG’，s2=‘PQRST’，

则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串

是。

5.设数组a[1…100]的基地址为128，每个元素占2个存储单元，采用顺

序存储方式存储，则元素a[52]的存储地址为。

6.一个广义表为L=((a,b),(c,d),(e,f))，则GetHead(GetTail

(GetTail(L)))为。

二、选择题（20分，每题2分）

1.设某棵二叉树的先序遍历序列为ABCDE，中序遍历序列为BADCE，则后

序遍历该二叉树得到序列为（）。

(A)BCDEA(B)BDECA(C)ACDEB(D)BADEC

2.设一组初始记录关键字序列(54，29，62，30，86)，以第一个记录关

键字54为基准进行一趟快速排序的结果为（）。

(A)29，30，54，86，62(B)30，29，54，86，62

(C)29，30，62，54，86(D)30，29，54，62，86

3．最坏情况下，在二叉排序树中插入一个结点的时间复杂度为（）。

2

(A)O(1)(B)O(n)(C)O(logn)(D)O(n)

2

4．下列四种排序中，（）的空间复杂度最大。

(A)快速排序(B)冒泡排序(C)归并排序(D)希尔排序

5.设一采用顺序存储的一组元素，其关键字序列为

(2,8,21,37,51,78,89,92,99)，则用二分查找方法查找关键字为68的元素时

关键字比较次数为（）。

第1页共5页

(A)2次(B)3次(C)4次(D)找不到，0次

6.设某散列表的长度为50，散列函数H(k)=k%P，则P通常情况下最好

选择（）。

(A)49(B)39(C)50(D)27

7．设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，

则在结点A的后面插入结点X的操作序列为（）。

(A)p-right=s；s-left=p；p-right-left=s；s-right=p-right；

(B)s-left=p；s-right=p-right；p-right=s；p-right-left=s；

(C)s-left=p；s-right=p-right；p-right-left=s；p-right=s；

(D)p-right=s；p-right-left=s；s-left=p；s-right=p-