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

设有键值序列如题 33 表所示，现采用快速排序算法以位于最左位置的键值为基准对它进行排序。 请给出 57，72，88 这三个元素在第一趟快速排序后的位置。

题33表

假设单链表的类型定义如下:

typedef struct node

{  DataType data;

   struct node *next;

}Node, *LinkList;

设计算法 InitiateLinkList()实现单链表的初始化。

已知静态查找表顺序存储结构的类型定义如下:

const int Maxsize = 20;

typedef struct

{

   KeyType key;  //关键字

   …                    //其他域

}TableElem;

typedef struct

{

  TableElem elem[Maxsize+1];

   int n;

}SqTable;

设计实现有序表二分查找算法 SearchBin(SqTable T, KeyType key)(假定有序表是按键值从小到大有序)。

题31图所示为一有向图，试给出该图的邻接表表示及对该图进行拓扑排序的各种可能的拓扑序列。

设散列表长度为 11，散列函数 H(key) = key mod 11(mod 为求余运算)，给定的键值序列为:(3，12，13，27，34，22，38，25)。 试画出采用线性探测法解决冲突时所构造的散列表，并求出在等概率的情况下查找成功时的平均查找长度。

将题 29 图所示的二叉树转换为对应的树或森林。

假设某个电文由 5 个字母 a，b，c，d，e 组成，每个字母在电文中出现的次数为 7，9，5，6，12，试为这 5 个字母设计哈夫曼树并写出对应的哈夫曼编码。 (构建新二叉树时，要求新二叉树的左子树根的权值小于等于右子树根的权值。)

设表中元素的初始状态是按键值递增有序的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其按递增顺序进行排序，_________排序方法最

静态查找表是以具有相同特性的数据元素集合为逻辑结构，但不包括插入和_________运算。

数据元素的键值和_________之间建立的对应关系称为散列函数。

图的广度优先搜索遍历类似于树的按_________遍历的过程。

稀疏矩阵可以采用_________法进行压缩存储。

完成拓扑排序的前提条件是 AOV 网中不允许出现_________。

高度为 h(h≥2)的完全二叉树至少有_________个叶子结点。

一棵树中所有结点_________的最大值称为该树的高度。

二叉树的任一结点都有两棵子树，并且这两棵子树之间有_________关系。

假设以 E 和 O 分别表示进栈和出栈操作，则对输入序列 a，b，c，d，e 进行一系列操作EEOEEOEOOO之后，得到的输出序列为_________。

栈初始化运算的目的是_________。

单链表各个结点在内存中的存储位置并_________连续。

线性表中如果结点数不为零，则除起始结点没有直接前驱外，其他每个结点有且仅有_________个直接前驱。

在下述四种排序算法中，所需辅助存储量最多的是(　　)

在散列函数 H( k )= k MOD m 中，一般来讲，m 应取(　　)

在用邻接表表示图时，对图进行深度优先搜索遍历的算法的时间复杂度为(　　)

静态查找表与动态查找表二者的根本差别在于(　　)

关于二叉链表，下列叙述正确的是(　　)

无向图中的极大连通子图是(　　)

假设初始森林中共有 n 棵二叉树，每棵树中都仅有一个孤立的结点。将该森林构造成哈夫曼树，则最终求得的哈夫曼树的结点数为(　　)

二叉树第 i(i≥1)层上的结点数最多为(　　)

设循环队列的元素存放在一维数组 Q[30]中，队列非空时，front 指示队列首结点的前一个位置，rear 指示队列尾结点。 如果队列中元素的个数为 10，front 的值为 25，则 rear 应指向的元素是(　　)

带头结点的双向循环链表 L 为空的条件是(　　)

执行进栈操作，在元素 x 进栈前需要进行的操作是(　　)

关于队列，下列叙述正确的是(　　)

下面程序是矩阵转置算法 MM 的实现过程，其时间复杂度为(　　)

const int n = 3;

void MM(int A[n][n])

{  int i, j, temp;

   for(i = 0; i

     for(j = 0; j

     {  temp =A[i][j];

设顺序表的表长为 n，则删除一个元素在最坏情况下元素移动次数为(　　)

数据的逻辑结构分为四种，其中结构最复杂的是(　　)