数据结构试题06(有答案).pdfVIP

数据结构试题06(有答案)--第1页

数据结构试题06（有答案）

⼀、

单选题（每题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.14

B.5

C.6

D.8

5.由权值分别为3,8,6,2的叶⼦⽣成⼀棵哈夫曼树，它的带权路径长度为

()。

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

以下6-8题基于图1。

6.该⼆叉树结点的前序遍历的序列为()。

A.E、G、F、A、C、D、B

B.E、A、G、C、F、B、D

C.E、A、C、B、D、G、F

D.E、G、A、C、D、F、B

7.该⼆叉树结点的中序遍历的序列为()。

数据结构试题06(有答案)--第1页

数据结构试题06(有答案)--第2页

A.A、B、C、D、E、G、F

B.E、A、G、C、F、B、D

C.E、A、C、B、D、G、F

E.B、D、C、A、F、G、E

8.该⼆叉树的按层遍历的序列为()。

A．E、G、F、A、C、D、

BB.E、A、

C、B、

D、G、F

C.E、A、G、C、F、B、D

D.E、G、A、C、D、F、B

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

A．⽤邻接表法存储图，占⽤的存储空间⼤⼩只与图中边数有关，⽽与结点个数⽆关EAGC

BD

F图1

B．⽤邻接表法存储图，占⽤的存储空间⼤⼩与图中边数和结点个数都有关

C.⽤邻接矩阵法存储图，占⽤的存储空间⼤⼩与图中结点个数和边数都有关D．⽤邻接矩阵法存储图，占⽤的存储空间⼤⼩

只与图中边数有关，⽽与结点个数⽆关

10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下⾯哪⼀个序列是从上述

序列出发建堆的结果?()

A.a，g，h，m，n，p，q，x，z

B.a，g，m，h，q，n，p，x，z

C.g，m，q，a，n，p，x，h，z

D.h，g，m，p，a，n，q，x，z

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

1.数据的物理结构被分为_________、________、__________和___________四

种。

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

_________，在表尾插⼊元素的时间复杂度为____________。

3.向⼀个由HS指向的链栈中插⼊⼀个结点时p时，需要执⾏的操作是

________________;删除⼀个结点时，需要执⾏的操作是______________________________（假设栈不空⽽且⽆需回收

被删除结点）。

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

孩⼦则左孩⼦结点的编号为________，若它有右孩⼦，则右孩⼦结点的编号为________，若它有双亲，则双亲结点的编号为

________。

5.当向⼀个⼤根堆插⼊⼀个具有最⼤值的元素时，需要逐层_________调整，

直到被调整到____________位置为⽌。

数据结构试题06(有答案)--第2页

数据结构试题06(有答案)--第3页

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

________。

7.表⽰图的三种常⽤的存储结构为_____________、____________和

_______________。

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

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