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

二叉树的二叉链表类型定义如下：

typedef struct btnode {

       datatype data;

       struct btnode *lchild, *rchild;

} bitreptr;

写出后根遍历根指针为t的二叉树的递归算法( void postorder( bitreptr *t ))。

设线性表A =(a1，a2，…，am)，B=(b1，b2，…，bn)，试写一个按下列规则合并A，B为线性表C的算法，使得

       C=(a1，b1，…，am，bm，bm+1，…，bn) 当m≤n时;

或者 C=(a1，b1，…，an，bn，an+1，…，am) 当m>n时。

线性表A，B和C均以带头结点的单链表作为存储结构，且C表利用A表和B表中的结点空间构成。(注意：单链表的长度值m和n均未显式存储。)

用冒泡排序法对数据序列(55，38，65，97，76，138，27，49)进行排序，写出排序过程中的各趟结果。

写出题31图的邻接矩阵和每个顶点的入度与出度。

题31图

二叉排序树的各结点的值依次为20~28，请在题32图中标出各结点的值。

                             题32图

给定权值{3，9，13，5，7｝，构造相应的哈夫曼(Huffman)树，并计算其带权路径长度。

要将序列{51，18，23，68，94，70，73}建成堆，则只需把18与________相互交换。

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

题29图

二分查找算法的时间复杂度是________。

除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为________。

边稀疏的无向图采用________存储较省空间。

二叉树的二叉链表存储结构中判断指针p所指结点为叶子结点的条件是________。

一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右给所有结点编号。设根结点编号为1，若编号为i的结点有父结点，那么其父结点的编号为________。

在一棵树中，________结点没有双亲。

元素s₁，s₂，s₃，s₄，s₅，s₆依次进入顺序栈S，如果6个元素的退栈顺序为s₂，s₃，s₄，s₆，s₅，s₁，则顺序栈的容量至少为________。

稀疏矩阵一般采用的压缩存储方法是________。

在双链表中，前趋指针和后继指针分别为prior和next。若使指针p往后移动两个结点，则需执行语句________。

带有头结点的单向循环链表L(L为头指针)中，指针p所指结点为尾结点的条件是 ________。

数据的不可分割的最小标识单位是________，它通常不具有完整确定的实际意义，或不被当作一个整体对待。

在待排数据基本有序的前提下，效率最高的排序算法是(　　)

• A.直接插入排序
• B.直接选择排序
• C.快速排序
• D.归并排序

运算分为加工型运算和引用型运算，读取操作是________运算。

外存储器的主要特点是(　　)

• A.容量小和存取速度低
• B.容量大和存取速度低
• C.容量大和存取速度高
• D.容量小和存取速度高

顺序存储的表格中有60000个元素，已按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字值不相同。用顺序查找法查找时，平均比较次数约为(　　)

• A.20000
• B.30000
• C.40000
• D.60000

具有n个顶点的无向图的边数最多为(　　)

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

具有12个结点的二叉树的二叉链表存储结构中，空链域NULL的个数为(　　)

• A.11
• B.13
• C.23
• D.25

三个顶点v1，v2，v3的图的邻接矩阵为，该图中顶点v3的入度为(　　)

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

10阶上三角矩阵压缩存储时需存储的元素个数为(　　)

• A.11
• B.56
• C.100
• D.101

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

• A.2k 个
• B.(2^k-1)个
• C.2^k-1个
• D.(2^k+1)个

栈的输入序列依次为1，2，3，4，则不可能的出栈序列是(　　)

• A.1243
• B.1432
• C.2134
• D.4312

关于串的叙述，正确的是(　　)

• A.串是含有一个或多个字符的有穷序列
• B.空串是只含有空格字符的串
• C.空串是含有零个字符或含有空格字符的串
• D.串是含有零个或多个字符的有穷序列

队列是(　　)

• A.先进先出的线性表
• B.先进后出的线性表
• C.后进先出的线性表
• D.随意进出的线性表

单链表中删除由某个指针变量指向的结点的直接后继，该算法的时间复杂度是(　　)

• A.O(1)
• B.
• C.O(log₂n)
• D.O(n)

线性结构是(　　)

• A.具有n(n≥0)个表元素的有穷序列
• B.具有n(n≥0)个字符的有穷序列
• C.具有n(n≥0)个结点的有穷序列
• D.具有n(n≥0)个数据项的有穷序列

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

• A.集合
• B.线性结构
• C.树形结构
• D.图状结构

下面算法程序段的时间复杂度为(　　)

for ( int i=0; i

      for ( int j=0; j

• a[i][j]=i*j;
• A.
• B.
• C.O(mn)
• D.O(m+n)