数据结构试题C

数据结构导论模拟试卷(三)一、单顶选择题(在每小题的4个备选答案中，选出1个正确的答案，并将其号码填在题干的括号内。每小题2分，共22分)1．若某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用()最节省运算时间。A)单链表 B)双链表C)带头结点的双循环链表 D)单循环链表设输入序列为A,B,C,D,借助一个栈得到的输出序列不可能是()。A)A，B，C，DB)A，C，D，B C)D，C，B，A D)D，A，B，C3.串是( )。A)不少于一个字符的序列 B)有限个字符的序列C)不少于一个字母的序列 D)任意个字母的序列链表不具有的特点是( )。A)可随机访问任一元素 B)插入删除不需要移动元素C)不必事先估计存储空间 D)所需空间与线性表长度成正比在有n个叶子的哈夫曼树中.其结点总教为()。A)不确定B)2nC)2n+1D)2n-l任何一个无向连通图的最小生成树( )。A)只有一棵B)有一棵或多棵c)一定有多棵 D)可能不存在将一棵有100个结点的完全二叉树从根这一层开始,每一层上从左到右依次对结点进行编号,根结点的编号为1,则编号为49的结点的右孩子编号为()。A)98 B)99 C)50 D)48下列序列中,( )是执行第一趟快速排序后得到的序列。(排序的关键字类型是字符串)A)[da,ax,eb,cd,bb]ff[ha,gc]B)[ge,ax,eb,cd,bb]ff[da,ha]C)[cd,eb,ax,da]ff[ha,gc,bb]D)[ax,bb,cd.da]ff[eb,gc,ha]9•用n个键值构造一棵二叉排序树，最低高度为()。A)n/2 B)Vn cjnlog^ D).log?n1二分查找法要求查找表中各元素的键值必须足( )排列。A)递增或递减B)递增C)递减 D)无序对于键值序列｛72,73,71,23,94,16,5,68,76,103｝用筛选法建堆.必须从键值为( )的结点开始。A)103 B)72 C)94 D)23二、判断题(判断下列各题是否正确，若正确在括号内打“J”,错误的打“X”，每小题1分，共10分)TOC\o"1-5"\h\z1．如果两个串含有相同的字符，则这两个串相等。( )2．数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。()3．在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每一块中元素个数有关。( )在顺序表中取出第i个元素所花费的时间与i成正比。()5．在栈满情况下不能作进栈运算，否则产生“上溢”。( )二路归并排序的核心操作是将两个有序序列归并为一个有序序列。( )对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点。()二叉排序树或者是一棵空二叉树，或者是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值；若它的右子树非空，则根结点的值小于其右孩子的值。()在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置耗反方向移动，则该算法是不稳定的。()TOC\o"1-5"\h\z一个有向图的邻接表和逆邻接表中表结点的个数一定相等。( )三、填空墨(每空2分，共28分)在带有头结点的单链表L中，第一个元素结点的指针是 。在顺序文件中，存取第i个记录，必须先存 。设s[1..maxsize]为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件 。栈为满的条件是 。4•具有64个结点的完全二叉树的深度为. 。有向图G用邻接矩阵A[l..n，l.n]存储，其第i列的所有元素之和等于顶点i的. 。在双循环链表中，若要在指针P所指结点前插入指针S所指的结点，则需执行下列语句：s一>next=p；s一〉prior=p—〉prior；p一〉prior=s； =s。对于图20所示二叉树，按前序遍历所得的结点序列为 。分别采用堆排序、快速排序、冒泡排序和归并排序算法，对初始状态为递增序列的表按递增顺序排序，最省时的时 算法，最费时间的是 树算法。

图20二叉树9．对图21所示的网，执行prim算法可得到最小生成树，试在下表的空白处填上适当的内容。以说明该算法的执行过程。顶点1顶点134UV(U,V)代价(2，1)OO（2，3）4（2，4）2{2}{1,3,4}（U,V）代价（2，3）4////{2,4}{1,3}（U,V）代价（3，1）1//////{2,4,3}{1}（U,V）代价/////////{2,4,3,1}(a)网 (b)prim算法在图21(a)所示的网上的执行示意图21网及在其上执行prim算法示意图10•设散列函数为H(key)，用拉链(链地址)法解决冲突，H的值域为0„n-1,构造的散列表类型如下：．typedefstructnode{keytypekey；structnode*next；}*pointer；typedefpointeropenhash[n]请在下列算法划线处填上适当内容，以完成在散列表HP中查找键值等于k的结点，找到时返回该结点的指针，找不到时返回空指针。pointervesearch(keytypek，openhashHp)

{i=H(k)；succ=false；while((p!=NULL)&&(!succ))if(p->key!=k) elsesuce=true；return(p)；}四、应用题(共23分)1．（4分）已知二叉树的后根序列和中根序列如下，构造出该二叉树。后根序列：ABCDEYG中根序列：ACBGEDF2．（5分）有一组关键码序列（38，19，65，13，97，49，41，95，1，73），采用冒泡排序方法由小到大进行排序，请写出每趟的结果。3．（3分）设图G=（V，E），V={1，2，3，4，5，6}，E={<1，2>，<1，3>，<2，5>，<3，6><6,5>,<5,4>,<6,4>}，请写出图G中顶点的所有拓扑序列。（3分）设散列函数为H（K）=K%7,闭散列表的地址空间为0„6,开始时散列表为空，用线性探测法解决冲突,请画出依次插入键值23,14,9,6,30,12,18后的散列表。（4分）对图21所示两棵二叉树,分别画出它们的顺序存储结构。图21两棵二叉树（4分）已知图G的邻接表如图22所示，画出图G的所有连通分量。五、设计题（共17分）1•（6分）设BT为二叉排序树，t指向根结点，每个结点的结构为：1lehild【keyjrchild1,试用类C语言写出算法，用来输出二叉排序树中最小的键值。（6分）设一棵二叉树以二叉链表为存储结构，结点结构为：11ehi1d}data1rchild1,设计一个算法求此二叉树上度为2的结点个数。（8分）设一个环上有若干个整数，若采用单循环链表L存储该环，L的存储结构为：fdatafnextft，试画出链表L的结构图，并编写算法判断环上任意两个相邻的键值之差的绝对值是否不超过2。答案□一、选择题1，C.2，D.3，B.4，A.5，D.6，B.7，B.8，A.9，D.10，A.11，C.二、判断题（每小题1分共10分）1•答案：X。2．分析：准确地说，数组是线性结构的顺序存储方式，逻辑相邻的元素其存储单元也相邻。数组可以看作是线性结构的特例，但是其数据元素的个数是相对固定的，因此不能对数组施加插入、删除运算。答案：X。3.分析：索引顺序表的等概率下的分块平均查找长度为ASL=O.5*（n/s+s）+1,其中n是顺序表中元素的数目，s是每块中元素的个数。因此题中叙述是正确的。答案：厶4．分析：顺序表中存取任一元素，所花费的时间是一样的，因为顺序表具有随机存取的特性，与存取哪一个元素无关系。答案:X。5•答案:J。6•答案:J。分析：只有连通图才能从任意结点出发，通过遍历访问图中每个结点。答案：X。分析:由二叉排序树的定义可知，左子树的所有键值<该结点键值<右子树所有结点键值，而不是左孩子，右孩子。例如，图23所示的二叉树不是二叉排序树，但按题中定义就成了二叉排序树，这显然是错误的。另外，二叉排序树按中序遍历，其结果应是键值按递增顺序排列，这是二叉排序树的重要特点。图23非二叉排序树答案：X。9•答案：X。10.分析：除表头结点外，对于有向图，邻接表的结点个数=逆邻接表结点个数=图中边的个数。答案：厶三、填空题分析：第一个结点的指针（即地址）存放于头结点的指针域中，也就是L->next。答案：L->next。分析：这里耍注意顺序文件同线性结构的顺序存储的区别。内存中的数组是随机存储，存取第i个记录（或结点）同其它结点不发生关系。而外存中必须先顺序存取前i-1个记录。当然说成第i-1个记录也是可以的。答案：前i-1个记录（或第i-1个记录）。3.答案：top=0,top=maxsize。4•分析：求完全二叉树深度的计算公式为LloganJ+Jog?n_|+hlog?64+1=7答案：7。分析：第i列(行)的所有非0元素的个数之和为结点i的入(出)度；当图用矩阵存储时,若有边则矩阵元素用1表示,若无边,用0表示。那么非0元素的个数就等于矩阵中元素值之和。答案：入度。答案：s->prior->next。答案：ABDEHCF。分析：由于冒泡排序的平均时问复杂性为O(加)，而快速、归并和堆排序的平均时间复杂性为O(nlogn)。所以考生容易答成最省时间的是快速排序，最费时间的是冒泡排?序。但是有些排序方法与初始数据状态有关，这点请务必注意。在初始状态递增时，对冒泡排序来讲。只用n〜1次交换就排序完毕；而快速排序选第一个记录为标准，反向扫描时，若初始数据递增则：第一趟扫描比较n-1次；第二趟扫描比较n-2次；第n-1趟扫描比较1次；那么总共比较(n-l)+(n-2)+„+l=n(n-l)/2堆排序和归并排序介于n-l和n(n-1)/2之间。因此，当初始状态递增时冒泡排序的速度最快，而快速排序速度最慢。实际应用时，为了避免快速排序出现这种恶劣的效果，初始关键字的选择一般不选第一个记录，而是取n个记录的居中者，扫描方向也可以交替进行。要想答好此题，必须熟练掌握冒泡排序、快速排序的思想与方法，甚至算法的准确流程和步骤。答案：冒泡排序、快速排序。答案：(4，1)，0(或填“空集”)。5答案：P=HP[i],P=P->next。四、应用题分析：由后根序列知G是根结点，由中根序列知ACB是G的左子树上的结点，EDF是G的右子树上的结点；对ACB，由后根序列知C是子树的根，由中根序列知，A是C的左孩子，B是C的右孩子；对EDF,由后根序列知F是子树的根，由中根序列知，ED是F的左子树上的结点；对ED，由后根序列知E是子树的根，由中根序列知，D是E的右孩子。答案：构造出的二叉树如图24所示。图24根据题中条件构造的二叉树2．冒泡排序步骤：38，19，65，13，97，49，41，95，1，73[19381365494195173]97[191338494165173]9597[1319384149165]73959765739597[131938411]4965739597[1319381]414965739597[13191]38414965739597[131]1938414965739597[1]1319384149657395973．拓扑序列如下：1，2，3，6，5，41，3，2，6，5，41，3，6，2，5，44．散列表如下：01234561418239301265．(1)的顺序存储结构12345678910ABCDEFGHIJ(2)的顺序存储结构1 斗5 6FS9 10 11ABCDEAFAAIJ图28图22(2)的顺序存储结构6．答案：连通分量有3个，如图29所示：五、设计题分析：由于BT是一棵二叉排序树，所以其根结点的最左下的左孩子是键值最小的结点。故本算法比较简单，从报结点出发，只要有左孩子，就顺左孩子指针往下查找，最后输出最左下的左孩子的键值。答案：viodoutput(bitreptrt){p=t；while(p->lchild!=NULL)p=p->lchild；p