《数据结构(c++)第二次作业参考答案》由会员分享，可在线阅读，更多相关《数据结构(c++)第二次作业参考答案（4页珍藏版）》请在金锄头文库上搜索。
1、1数据结构第二次作业答案学号学号： 姓名姓名： 评分评分： .一. 单项选择题选择题(20(20 分分) )( )1. 一棵左右子树均不为空的二叉树在后序线索化后（不带头结点的线索化） ，其空指针域数 为_。 a、0 b、1 c、2 d、不确定 ( )2. 下列排序算法中时间复杂度不受数据初始状态影响，恒为 O(n2)的是_。 a、堆排序 b、起泡排序 c、直接选择排序 d、快速排序 ( )3. 设图的顶点数=n, 边数=e，若用邻接表表示图，那么求最短路径的 Dijkstra 算法的时间复 杂度为_。 a.O(n*e) b.O(n2) c.O(n+e) d.O(n3) ( )4. 下面程序段
2、的时间复杂度是_。i=1;while(i0)个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量 级为_。 a. O(n) b. O(log2n) c. O(nlog2n) d. O(n2) ( )6. 采用分块查找时，若线性表中共有 625 个元素，查找每个元素的概率相同，假设采用顺序 查找来确定结点所在的块时，每块应分为_个结点最佳。a. 10 b. 25 c. 6 d. 625 ( )7. 已知数据表中的每个元素距其最终位置不远，则采用_排序算法最省时间。 a.堆排序 b.插入排序 c.快速排序 d.直接选择排序 ( )8. 某二叉树的先序序列和后序序列正好相反，则该二叉
3、树一定是_的二叉树。 a. 空或只有一个结点 b. 高度等于其结点数（空树高度为 0） c. 任一结点无左孩子 d. 任一结点无右孩子 ( )9. 一棵左子树为空的二叉树在先序线索化后（不带头结点的线索化） ，其中的空链域的个数 为_。 a. 2 b. 1 c. 0 d. 不确定 ( )10. 假设图的顶点数=n, 边数=e，那么当用邻接表表示图时，拓扑排序算法的时间复杂度为 _。 a. O(n2) b. O(n+e) c. O(n*e) d. O(n3)二二. . 填空作图简答题（共填空作图简答题（共 6464 分）：分）：1.依次插入 30，43，21，9，15，51 并由空树构成一棵平衡
4、二叉树， 画出该平衡二叉树形成过 程及其中序线索二叉树。2.有一组关键码序列40，20，60，15，50，45，95，10，75，采用 Shell 排序方法从小到大进 行排序，假设其间隔序列为 5，3，1，请写出每趟的结果。3.对下面的 3 阶 B 树依次插入关键码 60，14，6，画出插入三个关键码后并删除关键码 20 后的 结果。24.用 Prim 算法求下图的最小生成树, 若从顶点 0 出发，请将算法中的两个辅助数组的变化过程 填入下表。3 1234056764 7557685128辅助数组 lowcost辅助数组 nearvex 0123456701234567所选边选出第 1 条边选
5、出第 2 条边选出第 3 条边选出第 4 条边选出第 5 条边选出第 6 条边选出第 7 条边5.求出下图中顶点 A 到其余个顶点的最短路径和最短路径长度。10 3ABCDHEFG207899198631276.已知报文为 acedabdebdeebcdedebcde，试设计其赫夫曼编码并画出相应的赫夫曼树。20104012 1630502 837.设初始归并段为(10,15,31,),(9,20, ),(22,34,37, ),(6,15,42, ),(12,37, ), (84,95, ),试利用败者树进行 6 路归并，画出选出最小的 2 个关键码的过程。8.已知哈希表地址空间为 08，哈
6、希函数为 H(key)=key % 7，采用线性探查法处理冲突。将数 据（100，20，21，35，3，78，99，45）依次存入该散列表中，并计算等概率下查找不成功 时的平均查找长度。 012345678等概率下查找不成功时的平均查找长度：_ _。三. 程序填空填空(16(16 分分) )1.下面是仅给出了部分操作的二叉搜索树类的定义和实现。试在程序的每一划线部分填入一条 语句或表达式，完成将元素 x 插入到二叉树的操作。 class BinNode public:int data; BinNode* leftchild, * rightchild;BinNode() leftchild =
7、 rightchild = NULL; ; class BinTree private:BinNode* root;void clearhelp(BinNode* rt) if (rt = NULL) return;clearhelp(rt-leftchild); clearhelp(rt-rightchild); delete rt; public:BinTree() root = NULL; BinTree() clearhelp(root);void insert(const int x) ; /元素 x 插入到二叉树 ; void BinTree : insert(const int x) /元素 x 插入到二叉树 BinNode *i, *j, *k; ;i-data = x;if ( ) root = i;else j = root;while ( ) k = j;if ( ) j = j-rightchild; else if(x=j-data) return;4else j = j-leftchild;if ( x k-data ) k-rightchild = i;else k-leftchild = i;
