​数据结构导论2011年10月真题（02142）

数据结构导论2011年10月真题及答案解析（02142）

数据结构导论2011年10月真题及答案（02142），该试卷为数据结构导论自考历年真题试卷，包含答案及详细解析。

一、单项选择题(本大题共15小题。每小题2分。共30分)在每小题列出的四个备选项中只有一个是符合题目要求的。请将其代码填写在题后的括号内。错选、多选或未选均无分。

1.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，元素退栈后即进人队列Q，若6个元素的出队序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少为(　　)

A.2
B.3
C.4
D.6

2.设计一个判别表达式中左右括号是否配对出现的算法，采用的最佳数据结构为(　　)

A.线性表的顺序存储结构
B.队列
C.线性表的链式存储结构
D.栈

3.下列程序段的时间复杂度为(　　)i=0; s=0;while(s<n){  i++;   s =s+i;}

A.

B.

D.

4.设A是n×n的对称矩阵，将A的对角线及对角线上方的元素Aij(1≤i，j≤n，i≤j)以列优先顺序存放在一维数组元素B[1]至B[n(n+1)/2]中，则元素Aij(i≤j)在B中的位置为(　　)

A.i(i-1)/2+j
B.j(j-1)/2+i
C.j(j-1)/2+i-1
D.i(i-1)/2+j-1

5.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是(　　)

A.G中有弧

C.G中没有弧

6.下列序列中，由第一趟快速排序可得到的序列(排序的关键字类型是字符串)是(　　)

A.[da，ax，eb，de，bb] ff [ha，gc]
B.[cd，eb，ax，da] ff [ha，gc，bb]
C.[gc，ax，eb，cd，bb] ff [da，ha]
D.[ax，bb，cd，da] ff [eb，gc，ha]

7.不稳定的排序方法是(　　)

A.直接插入排序
B.冒泡排序
C.堆排序
D.二路归并排序

8.设散列表表长m=14，散列函数为h(k)=k%11，表中已有4个记录，如果用二次探测法处理冲突，关键字为49的记录的存储位置是(　　)

A.3
B.5
C.8
D.9

9.若元素1，2，3依次进栈，则退栈不可能出现的次序是(　　)

A.3，2，1
B.2，1，3
C.3，1，2
D.1，3，2

10.直接插入排序的时间复杂度是(　　)

A.

B.

D.

11.稀疏矩阵是指(　　)

A.元素少的矩阵
B.有少量零元素的矩阵
C.有少量非零元素的矩阵
D.行数、列数很少的矩阵

12.深度为k(k≥1)的二叉树，结点数最多有(　　)

A.2k

B.-1

C.

D.-1

13.由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为(　　)

A.23
B.37
C.44
D.46

14.有n个顶点的有向完全图的弧数为(　　)

A.

15.图的深度优先搜索类似于二叉树的(　　)

A.先根遍历
B.中根遍历
C.后根遍历
D.层次遍历

二、填空题(本大题共13小题。每小题2分，共26分)请在每小题的空格中填上正确答案。错填、不填均无分。

11.下列程序段的时间复杂度为________。for( i=1; i<-n; i++ )      for( j=1; j<=n; j++ )             x++;

12.数据结构中结点按逻辑关系依次排列形成一条“锁链”的结构是________。

13.在表长为n的顺序表上做删除运算，平均要移动的结点个数为________。

14.在带有头结点的单循环链表head中，指针P所指结点为尾结点的条件是________。

15.队列又称为________的线性表。

16.顺序栈被定义为结构类型，含有两个域：data和top，则对栈*sq进行初始化的操作是________。

17.对于任何一棵二叉树T，如果其终端结点数为‰，度为2的结点数为，则________。

18.一棵具有n个结点的二叉树，采用二叉链表存储，则二叉链表中指向孩子结点的指针有________个。

19.若连通图G的顶点个数为n，则图G的生成树的边数为________。

110.一个具有n个顶点的无向图的边数最多为________。

111.中根遍历二叉排序树所得到的结点访问序列是键值的________序列。

112.冒泡排序的平均时间复杂度为________。

113.将序列(60，20，23，68，94，70，73)建成堆，则只需把20与________互相交换。

三、应用题(本大题共5小题，每小题6分。共30分)

21.如题29图所示，在栈的输入端元素的输入顺序为A，B，C，D，进栈过程中可以退栈，写出在栈的输出端以A开头和以B开头的所有输出序列。

22.一棵二叉树如题30图所示，写出该二叉树的先根遍历序列、中根遍历序列和后根遍历序列。

23.将题31图所示的一棵二叉树转换成森林。题31图

24.对于有向无环图：(1)叙述求拓扑排序算法的基本步骤;(2)对于题32图，写出它的4个不同的拓扑排序序列。

25.判别以下序列是否为堆。如果不是，则把它调整为堆。(1)(100，86，48，73，35，39，42，57，66，21);(2)(12，70，33，65，24，56，48，92，86，33)。

四、算法设计题(本大题共2小题。每小题7分。共14分)

31.n个结点的完全二叉树按结点编号将值顺序存放在一维数组元素A[1]至A[n]中，试编写算法实现将顺序存储结构转换为二叉链表存储结构，其中根结点由tree指向。

32.试写出冒泡排序算法。