数据结构导论2018年4月真题（02142）
数据结构导论2018年4月真题及答案解析（02142）
数据结构导论2018年4月真题及答案解析（02142），该试卷为数据结构导论自考历年真题试卷，包含答案及详细解析。
一、单项选择题(本大题共 15 小题，每小题 2 分，共 30 分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸冶的相应代码涂黑。 错涂、多涂或未涂均无分。
1.数据的逻辑结构分为四种，其中结构最复杂的是( )
A.集合
B.线性结构
C.树形结构
D.图结构
2.下面程序是矩阵转置算法 MM 的实现过程，其时间复杂度为( )const int n = 3;void MM(int A[n][n]){ int i, j, temp; for(i = 0; i <n; i++) for(j = 0; j <i; j++) { temp =A[i][j]; A[i][j] =A[j][i]; A[j][i] = temp; }}
A.O(1)
B.O(log2n)
C.O(n2)
D.O(2n)
3.设顺序表的表长为 n，则删除一个元素在最坏情况下元素移动次数为( )
A.n-2
B.n-1
C.n
D.n+1
4.带头结点的双向循环链表 L 为空的条件是( )
A.L->next = = L->prior
B.L->prior = =NULL
C.(L->next = = L)&&(L->prior = = L)
D.(L->next = = L)&&(L->prior =NULL)
5.执行进栈操作，在元素 x 进栈前需要进行的操作是( )
A.判断栈是否满，若栈未满，top 值加 1
B.判断栈是否空，若栈未空，top 值加 1
C.判断栈是否满，若栈未满，top 值减 1
D.判断栈是否空，若栈未空，top 值减 1
6.关于队列，下列叙述正确的是( )
A.队列的元素个数可以无穷大
B.队列中元素的类型可以不同
C.队列是一个非线性的序列
D.队列的特点是先进先出
7.设循环队列的元素存放在一维数组 Q[30]中，队列非空时，front 指示队列首结点的前一个位置，rear 指示队列尾结点。 如果队列中元素的个数为 10，front 的值为 25，则 rear 应指向的元素是( )
A.Q[4]
B.Q[5]
C.Q[14]
D.Q[15]
8.二叉树第 i(i≥1)层上的结点数最多为( )
A.2i-1
B.i-1
C.2*i
D.2*(i-1)
9.关于二叉链表，下列叙述正确的是( )
A.二叉链表是二叉树唯一的链式存储结构
B.对二叉链表的访问可以从任意结点开始
C.每个二叉链表不需要有一个指向根节点的指针
D.二叉链表的结点结构包含一个数据域和两个指针域
10.假设初始森林中共有 n 棵二叉树，每棵树中都仅有一个孤立的结点。将该森林构造成哈夫曼树，则最终求得的哈夫曼树的结点数为( )
A.n-1
B.n
C.2n-1
D.2n
11.无向图中的极大连通子图是( )
A.连通分量
B.生成树
C.强连通分量
D.强连通图
12.在用邻接表表示图时，对图进行深度优先搜索遍历的算法的时间复杂度为( )
A.O(n)
B.O(n+e)
C.O(n2)
D.O(n3)
13.静态查找表与动态查找表二者的根本差别在于( )
A.它们的逻辑结构不同
B.施加在其上的操作不同
C.所包含的数据元素类型不同
D.存储实现不同
14.在散列函数 H( k )= k MOD m 中，一般来讲，m 应取( )
A.奇数
B.偶数
C.素数
D.充分大的数
15.在下述四种排序算法中，所需辅助存储量最多的是( )
A.堆排序
B.快速排序
C.直接选择排序
D.归并排序
二、填空题(本大题共 13 小题，每空 2 分，共 26 分)
11.线性表中如果结点数不为零，则除起始结点没有直接前驱外，其他每个结点有且仅有_________个直接前驱。
12.单链表各个结点在内存中的存储位置并_________连续。
13.栈初始化运算的目的是_________。
14.假设以 E 和 O 分别表示进栈和出栈操作，则对输入序列 a，b，c，d，e 进行一系列操作EEOEEOEOOO之后，得到的输出序列为_________。
15.二叉树的任一结点都有两棵子树，并且这两棵子树之间有_________关系。
16.一棵树中所有结点_________的最大值称为该树的高度。
17.高度为 h(h≥2)的完全二叉树至少有_________个叶子结点。
18.图的广度优先搜索遍历类似于树的按_________遍历的过程。
19.稀疏矩阵可以采用_________法进行压缩存储。
110.完成拓扑排序的前提条件是 AOV 网中不允许出现_________。
111.数据元素的键值和_________之间建立的对应关系称为散列函数。
112.静态查找表是以具有相同特性的数据元素集合为逻辑结构，但不包括插入和_________运算。
113.设表中元素的初始状态是按键值递增有序的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其按递增顺序进行排序，_________排序方法最
三、应用题(本大题共 5 小题，每小题 6 分，共 30 分)
21.将题 29 图所示的二叉树转换为对应的树或森林。
22.假设某个电文由 5 个字母 a，b，c，d，e 组成，每个字母在电文中出现的次数为 7，9，5，6，12，试为这 5 个字母设计哈夫曼树并写出对应的哈夫曼编码。 (构建新二叉树时，要求新二叉树的左子树根的权值小于等于右子树根的权值。)
23.题31图所示为一有向图，试给出该图的邻接表表示及对该图进行拓扑排序的各种可能的拓扑序列。
24.设散列表长度为 11，散列函数 H(key) = key mod 11(mod 为求余运算)，给定的键值序列为:(3，12，13，27，34，22，38，25)。 试画出采用线性探测法解决冲突时所构造的散列表，并求出在等概率的情况下查找成功时的平均查找长度。
25.设有键值序列如题 33 表所示，现采用快速排序算法以位于最左位置的键值为基准对它进行排序。 请给出 57，72，88 这三个元素在第一趟快速排序后的位置。题33表
四、算法设计题(本大题共 2 小题，每小题 7 分，共 14 分)
31.假设单链表的类型定义如下:typedef struct node{ DataType data; struct node *next;}Node, *LinkList;设计算法 InitiateLinkList()实现单链表的初始化。
32.已知静态查找表顺序存储结构的类型定义如下:const int Maxsize = 20;typedef struct{ KeyType key; //关键字 … //其他域}TableElem;typedef struct{ TableElem elem[Maxsize+1]; int n;}SqTable;设计实现有序表二分查找算法 SearchBin(SqTable T, KeyType key)(假定有序表是按键值 从小到大有序)。
