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

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

试写出冒泡排序算法。

判别以下序列是否为堆。如果不是，则把它调整为堆。

(1)(100，86，48，73，35，39，42，57，66，21);

(2)(12，70，33，65，24，56，48，92，86，33)。

对于有向无环图：

(1)叙述求拓扑排序算法的基本步骤;

(2)对于题32图，写出它的4个不同的拓扑排序序列。

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

题31图

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

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

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

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

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

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

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

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

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

队列又称为________的线性表。

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

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

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

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

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

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

下列程序段的时间复杂度为________。

for( i=1; i<-n; i++ )

     for( j=1; j<=n; j++ )

            x++;

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

• A.
• B.2n
• C.n(n-1)
• D.2n(n+1)

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

• A.2k
• B.-1
• C.
• D.-1

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

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

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

• A.
• B.
• C.O(n)
• D.

稀疏矩阵是指(　　)

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

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

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

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

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

不稳定的排序方法是(　　)

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

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

• A.G中有弧
• B.G中有一条从Vi到Vj的路径
• C.G中没有弧
• D.G中有一条从Vj到Vi的路径

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

• 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]

设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

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

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

下列程序段的时间复杂度为(　　)

i=0; s=0;

while(s

{ i++;

  s =s+i;

}

• A.
• B.
• C.O(n)
• D.

设栈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