杭电数据结构复习卷答案.docx

《杭电数据结构复习卷答案.docx》由会员分享，可在线阅读，更多相关《杭电数据结构复习卷答案.docx（7页珍藏版）》请在优知文库上搜索。

1、一.是非题(正确的打“J”，错误的打“X”。)1 .数据结构可用三元式表示(D,S,P)。其中：D是数据对象，S是D上的关系集，P是对D的根本操作集。X2 .线性表的链式存储结构具有可直接存取表中任一元素的优点。3 .字符串是数据对象特定的线性表。4 .二叉树是一棵结点的度最大为二的树。5 .邻接多重表可以用以表示无向图，也可用以表示有向图。X6 .可从任意有向图中得到关于所有顶点的拓扑次序。7 .一棵无向连通图的生成树是其极大的连通子图。X8 .二叉排序树的查找长度至多为logzn。X9 .对于一棵m阶的B树.树中每个结点至多有m个关键字。除根之外的所有非终端结点至少有rm2-1个关键字。1

2、0 .对于目前所知的排序方法，快速排序具有最好的平均性能。11 .顺序存储方式的优点是存储密度大，且插入、删除运算效率高。12 .二维数组是其数据元素为线性表的线性表。13 .连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。X14 .折半查找不适用于有序链表的查找。15 .完全二叉树必定是平衡二叉树。16 .中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。17 .队列是与线性表完全不同的一种数据结构。18 .平均查找长度与记录的查找概率有关。19 .二叉树中每个结点有两个子结点，而对一般的树，那么无此限制，所以，二叉树是树的特殊情形。X20 .算法的时间复杂性越

3、好，可读性就越差；反之，算法的可读性越好，那么时间复杂性就越差。二.选择题1.假设对编号为L2,3的列车车厢依次通过扳道栈进行调度，不能得到(e)的序列。a:1,2,3b:l,3,2c:2,1,3d:2,3,1e:3,1,2f:3,2,12 .递归程序可借助于(b)转化为非递归程序。a:线性表b:栈c:队列d:数组3 .在以下数据结构中(c)具有先进先出(FIFO)特性，(b)具有先进后出(FlLO)特性。a:线性表b:栈c:队列d:广义表4 .对字符串s:data-structure,执行操作replacesubstring6,8),bas,)的结果是(d)。a:*database*b:*d

4、ata-base,c:basd:idata-basucture,5 .设有二维数组A.，每一元素用相邻的4个字节存储，存储器按字节编址。A的起始地址为100。那么按行存储时，元素AWi的第一个字节的地址是(d)按列存储时，元素A%的第一个字节的地址是(a)a:220b:200c:140d:1246 .对广义表A=(a,(b),(c,0),d)执行操作gettail(gethead(gettail（八）)的结果是：(b)。a:()b:()c:dd:(d)7 .假设用于通讯的电文仅由6个字符组成，字母在电文中出现的频率分别为7,19,22,6,32,14。假设为这6个字母设计哈夫曼编码（设生成新的

5、二叉树的规那么是按给出的次序从左至右的结合，新生成的二叉树总是插入在最右），那么频率为7的字符编码是（g）,频率为32的字符编码是（c）oa:00b:01c:10d:11e:Oilf:110g:HlOh:llll8 .对二叉排序树（c）可得到有序序列。a:按层遍历b:前序遍历c:中序遍历d:后序遍历9 .某树的先根遍历次序为abcdefg,后根遍历次序为Cdebgfa。假设将该树转换为二叉树,其后序遍历次序为（d）oa:abcdefgb:cdebgfac:cdegbfad:edcgfba10 .对一棵完全二叉树进行层序编号。那么编号为n的结点假设存在右孩子,其位序是（d）。编号为n的结点假设存

6、在双亲,其位置是（a）。a:n/2b:2nc:2n-ld:2n+le:nf:2（n+l）U.关键路径是指在只有一个源点和一个汇点的有向无环网中源点至汇点（C）的路径。a:弧的数目最多b:弧的数目最少c:权值之和最大d:权值之和最小12 .哈希表的查找效率取决于（d）oa:哈希函数b:处理冲突的方法。c:哈希表的装填因子。d:以上都是13 .从逻辑上可以把数据结构分成（c）。a:动态结构和静态结构b:顺序组织和链接组织c:线性结构和非线性结构d:根本类型和组合类型14 .在计算递归函数时，如不用递归过程，应借助于（b）这种数据结构。a:线性表b:枝c:队列d:双向队列15 .假设某二叉树的中序和

7、后序遍历序列分别BCAEFD和CBFEDA,那么该二叉树的先序序列为（a）。a:ABCDEFb:ABDCEFc:ABDCFEd:ACBDFE16 .当待排序序列的关键字次序为倒序时，假设需为之进行正序排序，以下方案中（d）为佳。a:起泡排序b:快速排序c:直接插入排序d:简单项选择择排序17 .假设从二叉树的根结点到其它任一结点的路径上所经过的结点序列按其关键字递增有序，那么该二叉树是（C）Oa:二叉排序树b:赫夫曼树c:堆d:平衡二叉树18 .以下图所有可能的拓扑序列有（b）种。a:2b:3c:4d:5a:堆排序b:20 .右图为一棵3阶B树。在该树上插入元素15后的B.树是（c ） ca:

8、,25二10,吵2dj2110-A152 卜21 .蝮林F%三号： 崎）1叉询结避日a:ml b:ml+m222 .根据插入次序（80, 90,起泡排序c:归并排序d:快速排序）b:耍亘二10,1，2135） O O10,2l21 5第攵 第二和第三棵树的结点个数分别为ml、m2和m3,那么与森林F对 二。的结点个数是（d ）oc:m3d: m2+m3l 100, 110, 85, 70, 75, 60, 72）建立二叉排序树。图（a ）是最终变19 .以下排序算法中，（d）算法可能会出现：初始数据为正序时，花费的时间反而最多。化的结果。假设仍以该插入次序建立平衡二叉树。图是最终变化的结果。b

9、:8070607572 ,9075851001106070908572100110c： /9075100708011060 728580756072d:70851109010023.设输入序列为 20,45, 30, 89, 70, 38, 62, (b )o再删除38,该B-树为(f )。19,依次插入到棵2-3树中（初始状态为空），该B-树为a:(30 62 )(19, 20) ( 38 45 )( 70, 89 )b:(30(19 20)(45)(38 )(70 )(62 )( 89 )2o4?(19) ( 30 )89 )(19 )e:(3070 )(19, 20)( 45 62)(

10、89 )(19 )d:45 20/Z (30,38 )(f:(45 20 )(30 )(70 )62 )( 89 )(70 )(62 )( 89 )24.一组待排序的记录关键字初始排列如下:45,34,87,25,67,43,11,66,27,78 。（g）是快速排序法一趟排序的结果；（a）是希尔排序法（初始步长为4）一趟排序的结果;（b）是初始堆（大堆顶）；25.(d)是基数排序法趟排序的结果。a： 27, 34, 11, 25, 45,43, 87, 66, 67, 78c: 11, 43, 34, 25, 45, 66, 27, 67, 87, 78e: 34, 45, 25, 67,4

11、3,11, 66, 27, 78, 87g: 27, 34,11, 25,43,45,67,66,87, 78假设有序表中关键字序列为：14, 20,25,b: 87, 78, 45, 66, 67, 43, 11, 25, 27, 34d:ll,43, 34, 45, 25, 66, 87, 67, 27, 78f: 87, 45,11, 25, 34, 78, 27, 66, 67, 43h: 34,11,27, 25,43,78,45,67, 66,8732, 34, 45, 57, 69, 77, 83, 92。对其进行折半查找,那么在等概率情况下，查找成功时的平均查找长度是（c）。查

12、找32时需进行（c）次比拟。a: 1b:2c:3d:4a: 2b: 3c: 4d: 526.设棵二叉树BT的存储结构如下:12345678Ichild230060(0dataABCDEFGrchild0540870I)其中!child,rchid分别为结点的左、右孩子指针域，data为结点的数据域。那么该二叉树的高度为（d）；第3层有（a）个结点（根结点为第1层）。27 .一个连通图的最小生成树（b）。a:只有一棵b:有一-棵或多棵c:一定有多棵d:可能不存在28 .假设某二叉树有20个叶子结点，有20个结点仅有一个孩子，那么该二叉树的总结点数是（c）。a:40b:55c:59d:6129 .

13、哈希表地址空间为A0.8,哈希函数为H（k）=kmod7,采用线性探测再散列处理冲突。假设依次那么元素17存储的下标为（f ）；在等概率将数据序列：76,45,88,21,94,77,17存入该散列表中,情况下查找成功的平均查找长度为（c）。a: Ob: 1e: 4 30.c:2f: 5d:3g： 6h: 7J 32131.ecadb.be 及 aedb30I-i l l i 2T-15 I -7I1 14! I I I 5 I4TIT 14P 口a:b:adcf:d:32.假设顺序表中各结点的查找概率不梅，两么可用如下策略提高顺序查找的效率：假设找到指定的结点，将该结点与其后继（假设存在十结

14、点交换位置，使得经常被查找的结点逐渐移至表尾。以下为据此策略编写的算法，请选择适当的内容，完成此功能。顺序表的存储结构为：typedefstructElemType*elem;数据元素存储空间，0号单元作监视哨intlength;表长度JSSTable;intsearchseq（SSTableST,KeyTypekey）在顺序表ST中顺序查找关键字等于key的数据元素。假设找到，那么将该元素与其后继交换位置，并返回其在表中的位置，否那么为0。ST.elem0.key=key;i=ST.length;while(ST.elemi.key!=key)f;if(g)ST.elemi*ST.elemi+l；:returni;a:i0b:i=Oc:iST.lengthd:i=ST.lengthe:i+f:ig:A和C同时满足h:B和D同时满足33.以下函数为堆排序中的堆调整过程(调整H.rs的关键字，使H.