数据结构练习题1及答案.pdfVIP

数据结构练习题1

2012-3

一、单选题（每题2分，共20分）

1.以下数据结构中,()是线性结构。

A.有向图B.队列C.线索二叉树D.B树

2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向

的结点，则执行()语句序列。

A.p=q；p-next=q；B.p-next=q；q-next=p；

C.p-next=q-next；p=q；D.q-next=p-next；p-next=q；

3.()不是队列的基本运算。

A.在队列第i个元素之后插入一个元素B.从队头删除一个元素

C.判断一个队列是否为空D.读取队头元素的值

4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可

以组成()个不同的字符串。

A.14B.5C.6D.8

5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为()。

A．11B.35C.19D.53

6.下列二叉树的前序遍历序列为()。

A.E,G,F,A,C,D,BB.E,A,G,C,F,B,D

C.E,A,C,B,D,G,FD.E,G,A,C,D,F,B

二叉树

7.第6题二叉树的中序遍历序列为()。

A.A,B,C,D,E,G,FB.E,A,G,C,F,B,D

C.E,A,C,B,D,G,FD.B,D,C,A,F,G,E

8.第6题二叉树的层次遍历序列为()。

A.E,G,F,A,C,D,BB.E,A,C,B,D,G,F

C.E,A,G,C,F,B,DD.E,G,A,C,D,F,B

9.下面关于图的存储的叙述中正确的是()。

A.用邻接表法存储图,占用的存储空间大小只与图中边数有关，而与结点个数

无关。

B.用邻接表法存储图,占用的存储空间大小与图中边数和结点个数都有关。

C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。

D.用邻接矩阵法存储图,占用的存储空间大小只与图中边数有关，而与结点个

数无关。

10.设有关键码序列(q,g,m,z,a,n,p,x,h)，下面()序列是从该序列出发建成的

堆。

A.a,g,h,m,n,p,q,x,zB.a,g,m,h,q,n,p,x,z

C.g,m,q,a,n,p,x,h,zD.h,g,m,p,a,n,q,x,z

二、填空题（每空1分，共26分）

1.数据的物理结构被分为______、______、______和_____四种。

2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为

______，在表尾插入元素的时间复杂度为_____。

3.向一个由HS指向的链栈中插入一个结点p时，需要执行的操作是____；删除

一个结点时，需要执行的操作是____（假设栈不空而且无需回收被删除结点）。

4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左

孩子则左孩子结点的编号为___，若它有右孩子，则右孩子结点的编号为___，

若它有双亲，则双亲结点的编号为___。

5.当向一个大根堆插入一个具有最大值的元素时，需要逐层___调整，直到被调

整到____位置为止。

6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为

____。

7.表示图的三种常用的存储结构为_____、_____和____。

8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）

=K%7作为散列函数，则散列地址为0的元素有_____个，散列地址为6的有

____个。

9.在归并排序中，进行每趟归并的时间复杂