数据结构期终复习

普里姆算法从顶点1出发得到最小生成树为： (1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20 六、（每小题2分，共8分）

（1）取散列函数为H(key)=key % 13。

（2）顺次将各个数据散列到表中，并同时列出各元素的比较次数如下表所示。

表10-1 各元素的比较次数

地址 关键字 比较 0 1 40 1 2 66 2 3 94 1 4 5 5 1 6 58 1 7 33 1 8 47 1 9 72 3 10 87 2 11 22 3 12 25 1 13 12 2 14 （4）计算查找成功的平均查找次数=（1×7+2×3+3×2）/12=19/12。 七、（第1小题2分，第2、3小题每小题3分，本题8分） （1）图G有2个连通分量。

（2）按深度优先搜索所得的树如下图所示：

（3）按深度优先搜索所得的顶点序列：ABHFGCDE 八、（本题8分）

（1）树，如下图所示：

（2）C是根结点。

（3）F，K，L，H，D，M，N是叶子结点。 （3）深度是5。 九、（本题9分）

（1）（12,2,10,20,6,18,4,16,30,8,28） （2）（6,2,10,4,8,12,28,30,20,16,18） 十、（本题15分）

将算法实现函数声明为二叉树类的友元函数，可采用层次遍历的方式进行复制，将已

复制的结点进入一个队列中即可。

具体算法实现如下：

// 文件路径名:exam5\\alg.h template

void CopyBitree(BinaryTree *fromBtPtr, BinaryTree *&toBtPtr) // 操作结果: 复制二叉树fromBt到toBt的非递归算法 { if (toBtPtr != NULL) delete toBtPtr; // 释放toBtPtr if (fromBtPtr->Empty()) { // 空二叉树 toBtPtr = NULL; // 空二叉树 } else { // 非空二叉树 LinkQueue *> fromQ, toQ; // 队列 BinTreeNode *fromPtr, *toPtr, *fromRoot, *toRoot; fromRoot = fromBtPtr->GetRoot(); // 取出fromBtPtr的根 toRoot = new BinTreeNode(fromRoot->data); // 复制根结点 fromQ.InQueue(fromRoot); toQ.InQueue(toRoot); // 入队 while (!fromQ.Empty()) { // fromQ非空 fromQ.OutQueue(fromPtr); // 出队 toQ.OutQueue(toPtr); // 出队 if (fromPtr->leftChild != NULL) { // 左子树非空 toPtr->leftChild = new BinTreeNode(fromPtr->leftChild->data); // 复制fromPtr左孩子 fromQ.InQueue(fromPtr->leftChild); toQ.InQueue(toPtr->leftChild); // 入队 } if (fromPtr->rightChild != NULL) { // 右子树非空 toPtr->rightChild = new BinTreeNode(fromPtr->rightChild->data); // 复制fromPtr左孩子 fromQ.InQueue(fromPtr->rightChild); toQ.InQueue(toPtr->rightChild); // 入队 } } toBtPtr = new BinaryTree(toRoot); // 生成toBtPtr } }

模拟试题（六）

一、单项选择题（每小题 2 分，共20分）

（1）设二叉树中有n2个度为2的结点，n1个度为1的结点，n0个叶子结点，则此二叉树采用二叉链表存储时空指针域个数为（ ）。

A）n0+n1+n2 B）n2+n1+2n0 C）2n2+n1 D）2n0+n1

（2）若需在O(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择（ ）。

A）快速排序 B）堆排序 C）归并排序 D）直接插入排序 （3）对于有n个顶点的有向图，由弗洛伊德（Floyd）算法求每一对顶之间的最短路径的时间复杂度是（ ）。

A）O(1) B）O(n) C）O(n) D）O(n3)

（4）对n个元素的序列进行并归排序，所需要的辅助存储空间为（ ）。

A）O（1） B）O（log2n） C）O（n） D）O（n2） （5）哈夫曼树中一定不存在（ ）。

A）度为0的结点 B）度为1的结点 C）度为2的结点 D）带权的结点 （6）设D={A,B,C,D}，R={,,,,}，则数据结构(D,{R})是（ ）。

A）树 B）图 B）线性表 D）前面都正确 （7）（ ）关键字序列不符合堆的定义。

A）'A'、'C'、'D'、'G'、'H'、'M'、'P'、'Q'、'R'、'X' B）'A'、'C'、'M'、'D'、'H'、'P'、'X'、'G'、'Q'、'R' C）'A'、'D'、'P'、'R'、'C'、'Q'、'X'、'M'、'H'、'G' D）'A'、'D'、'C'、'M'、'P'、'G'、'H'、'X'、'R'、'Q'

（8）一组记录的排序码为(48,24,18,53,16,26,40)，采用冒泡排序法进行排序，则第一趟排序需要进行记录交换的次数是（ ）。

A）3 B）4 C）5 D）6 （9）下面（ ）可以判断出一个有向图中是否有环（回路）？

A）求关键路径 B）拓扑排序 C）求最短路径 D）前面都不正确

（10）对线性表进行二分法查找，其前提条件是（ ）。

A）线性表以顺序方式存储，并且按关键字值排好序

B）线性表以顺序方式存储，并且按关键字值的检索频率排好序 C）线性表以链接方式存储，并且按关键字值排好序

D）线性表以链接方式存储，并且按关键字值的检索频率排好序 二、（本题8分）

在如下表所示的数组A中链接存储了一个线性表，表头指针存放在A[0].next，试写出该线性表。

表10-2 线性表

A data next 0 4 1 60 0 2 50 5 3 78 2 4 90 7 5 34 1 6 7 40 3 三、（本题8分）

已知一棵二叉树的前序遍历的结果是ABKCDFGHIJ，中序遍历的结果是KBCDAFHIGJ，试画出这棵二叉树。

四、（本题8分）

已知一个图的顶点集V为： V={1,2,3,4,5,6,7}，弧如下表所示。

表10-3 图的弧集

起点 终点 权 1 6 1 2 4 1 2 5 2 5 4 2 5 7 2 2 6 3 2 7 3 6 7 4 1 7 5 3 5 7 试用克鲁斯卡尔算法依次求出该图的最小生成树中所得到的各条边及权值。 五、（本题8分）

向最小根堆中依次插入数据4, 2, 5, 8, 3, 6, 10, 1时，画出每插入一个数据后堆的变化。

六、（本题8分）

有二叉树中序序列为：ABCEFGHD；后序序列为：ABFHGEDC；请画出此二叉树。 七、（每小题4分，共8分）

对给定的有7个顶点的有向图的邻接矩阵如下： （l）画出该有向图；

（2）若将图看成是AOE-网，画出关键路径。

??????????????????2?522?1?????8???35???

5????39????5????????????????????八、（本题8分）

给出一组关键字29、18、25、47、58、12、51、10，分别写出按下列各种排序方法进行排序时的变化过程：

（1）归并排序，每归并一次书写一个次序。

（2）快速排序，每划分一次书写一个次序以及最后排好序后的序列。