资源描述：
《数据结构(c++)第二次作业答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构第二次作业答案一.单项选择题(20分)()1.一棵左子树为空的二叉树在前序线索化后，其空指针域数为Ca、0b、1c、2d、不确定()2.下列排序算法中，___D_____算法可能会出现下面的情况：初始数据有序时，花费的时间反而更长。a、堆排序b、起泡排序c、直接选择排序d、快速排序()3.在图采用邻接表存储时，求最小生成树的prim算法的时间复杂度是__B_____。a.O(n*e)b.O(n+e)c.O(n2)d.O(n3)()4.下面程序段的时间复杂度是__A______。i=1;while
2、(i<=n)i++;a.O(n)b.O(n2)c.O(2n)d.O(log2n)()5.在有n(>0)个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为____B______。a.O(n)b.O(log2n)c.O(nlog2n)d.O(n2)()6.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分为__B_____个结点最佳。a.10b.25c.6d.625()7.排序算法的稳定性是指__A____。a.经过排序之
3、后，能使值相同的数据保持原顺序中的相对位置不变b.经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变c.算法的排序性能与被排序元素的数量关系不大d.算法的排序性能与被排序元素的数量关系密切()8.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是___B____的二叉树。a.空或只有一个结点b.高度等于其结点数（空树高度为0）c.任一结点无左孩子d.任一结点无右孩子()9.已知有向图G=(V,E)其中V={V1V2V3V4V5V6V7},E={,,,<
4、V2,V5>,,,,,}为__A_______。a.V1V3V4V6V2V5V7b.V1V3V2V6V4V5V7c.V1V2V3V4V5V6V7d.V1V2V5V3V4V6V7()10.下列关于AOE网的叙述中不正确的是__D______。a.关键活动不按期完成会影响整个工程的完成时间b.所有的关键活动提前完成，那么整个工程将会提前完成c.某些关键活动若提前完成，那么整个工程将会提前完成d.任一关键活动提前完成，那么整个工程将会提前完
5、成二.填空作图简答题（共64分）：1.将算术表达式((a+b)+c*(d+e)+f)*(g+h)转化为二叉树，并写出其前序序列。二叉树略5前序序列：*+++ab*c+def+gh1.有一组关键码序列{10，20，60，47，50，45，95，33，75}，采用Shell排序方法从小到大进行排序，假设其间隔序列为5，3，1，请写出每趟的结果。请按照下面的图例完成此题：2.对下面的3阶B树依次插入关键码80，26，6，画出插入三个关键码后并删除关键码40后的结果。201040121630502851.用Pr
6、im算法求下图的最小生成树,若从顶点0出发，请将算法中的两个辅助数组的变化过程填入下表。12340567647557685128辅助数组lowcost辅助数组nearvex0123456701234567所选边选出第1条边06∞57∞∞∞-10000000(0,3,5)选出第2条边06∞57∞∞6-100-10003(0,1,6)选出第3条边06354∞∞6-1-11-11003(1,2,3)选出第4条边06354126-1-1-1-11223(2,5,1)选出第5条边06354126-1-1-1-11
7、-123(2,6,2)选出第6条边06354126-1-1-1-11-1-13(1,4,4)选出第7条边06354126-1-1-1-1-1-1-13(3,7,6)2.求出下图中顶点A到其余个顶点的最短路径和最短路径长度。5103ABCDHEFG20789919863127AE=10; AF=17; AB=19; AG=25; AC=26; AD=27; AH=281.已知报文为afecdaceadabdefbedeebcdefdede，试设计其赫夫曼编码并画出相应的赫夫曼树。a：2；b：4；c：3；d
8、：6；e：7；acbdeacbde2.设初始归并段为(10,15,31,∞),(9,20,∞),(22,34,37,∞),(6,15,42,∞),(12,37,∞),(84,95,∞),试利用败者树进行6路归并，画出选出最小的2个关键码的过程。3.已知哈希表地址空间为0~8，哈希函数为H(key)=key%7，采用线性探查法处理冲突。将数据（100，20，21，35，3，78，99，45）依次存入该散列表中，并计算等概率下查找不成功时的平均
