数据结构冲刺模拟试卷考前密押试卷参考答案与解析

数据结构冲刺模拟试卷、考前密押试卷参考答案与解析冲刺模拟试卷（一）一、单项选择题1.C（p3）2.D（p3）3.A（p13）4.D（p28）5.B（p32）6.B（p37）7.B（p51）8.B（p60）9.D（p83）10.B（p95）11.A（p113）12.C（p174）13.D（p196）14.A（p137）15.A（p2071.[解析]逻辑上的数据结构称为逻辑结构，逻辑结构有线性结构和非线性结构两大类。2.[解析]循环队列、链表和哈希表都属于存储结构的描述，而栈属于逻辑结构的描述。3.[解析]采用顺序存储方式在已知元素序号的情况下可以直接计算出地址，当指定在线性表的最后进行插入和删除运算时，也不需要进行大量元素的移动。4.[解析]D答案的操作过程①s-prior=p;②s-next=p-next;③p-next-prior=s;④p-next=s;而其他答案先执行④p-next=s;则使得③p-next-prior=s;中的p-next指向了s，没有真正指向p的原后继结点。5.[解析]因为输出序列的第一个元素是n，说明n个元素进栈后才开始出栈，则输出第1个是n，第2个时n-1，第3个时n-2，……，第i个是n-（i-1），即n-i+1。6.[解析]循环队列，一次入队是队尾指针rear循环加1，一次出队（删除）是对头指针front循环加1。本题可以不用考虑循环，因为运算没有超出数组最大值。7.[解析]空串（EmptyString）是长度为零的串，由一个或多个空格组成的串称为空白串（BlankString）。8.[解析]按给定的下标范围A[0..8,1..10]进行计算：A[8,5]按行优先存储是第8*10+5=85个元素，要满足题意，应找到按列优先存储时也是第85个的那个元素：每列式9个元素，9*9=81（小于85的最大值），故此元素应在第10列上，又85-81=4，故此元素应在第3行上（行号从0开始的），所以为A[3,10]满足题意。9.[解析]在后序线索树中查找*p的后序后继结点，仅当*p的右子树为空时，才能直接由*p的右线索p-rchild得到，否则必须知道*p的双亲结点才能找到其后序后继。因此，如果线索二叉树中的结点没有指向其双亲结点的指针，就可能要从根开始进行后序遍历才能找到结点*p的后序后继。由此可看出，线索对查找指定结点的后序后继并无多大帮助，即在后序线索二叉树求后序后继的问题没有得到有效解决。同理，在前序线索二叉树中求前序后继的问题也没有得到有效解决。10.[解析]前缀码是字符集中任一字符编码都不是其他字符的编码的前缀。B答案中“0”是“00”的前缀，“1”是“11”的前缀，所以此编码不是前缀码。11.[解析]n个顶点的连通图至少有n-1条边，再少就不连通了，连通是指任意两个顶点之间都有路径，而不要求都有边相连。有路径是指从一个顶点沿着某些边可以到达另一个顶点。12.[解析]C答案的60成了100的左孩子，而别的答案100的左孩子都是80。本题也可以把4个二叉排序树全部构造出来进行比较。13.[解析]H（26）=9，H（25）=8，H（72）=4，H（38）=4，H（8）=8，H（18）=1，H（59）=8，当最后一个元素59存放时，8号地址已经放了25,9号地址放了26,10号放了8,11号地址开放。14.[解析]对于后三种排序方法两趟排序后，序列的首部和尾部两个应是有序的两个极值，而给定的序列并不满足；而使用快速排序两趟排序后，应至少有两个元素已经排在正确位置，现4,8,20都已在正确位置上。15.[解析]检索就是在文件中查找给定条件的记录；维护主要是指对文件记录的插入、删除及修改等更新操作。二、填空题16.（p9）O（n）17.（p4）指针18.（p32）SxSSxSxx19.（p63）6620.（p72）n21.（p175）二叉排序树22.（p101）n（n-1）23.（p174）1624.（p156）O（n㏒2n）25.（p208）多关键字文件17.[解析]链接存储的结点结构至少有两组分组成：数据域和指针域，指针域用来存放存储相邻结点的地址信息。18.[解析]栈是后进先出的线性表，此题不能呢个只考虑1234全部进栈再出栈，否则只能得到4321的出栈顺序。19.[解析]只存储非零元素需要10*3*2=60字节，另外三元组表中还要一组数据存储矩阵的总行数、总列数和非0元素的总个数需要3*2=6字节。20.[解析]每一层上只有一个结点可使用最大高度达到n。21.[解析]二叉排序树的一个重要性质是按中序遍历该树所得到的中序序列是一个递增有序序列。22.[解析]n个结点的有向完全图含有边的数目n(n-1)，n个结点的无向完全图含有边的数目n(n-1)/2。23.[解析]当采用顺序查找确定块时，应将各块中的结点数选定为n，此时查找效率最高。24.[解析]堆排序的最坏时间复杂度为0（nlog2n）。堆排序的平均性能较接近于最坏性能。25.[解析]文件在外存上的基本组织方式有四种：顺序组织、索引组织、散列组织和链组织，文件组织方式往往是这四种基本方式的结合。通常把不同方式组织的文件给予不同的名称。三、解答题26.（P103、105）邻接矩阵：0011001111011110邻接表：0V01V12V23V3顶点表边表27.（P90）WPL=（30+19+17）×2+11×3+4×4+（2+3）×5=206。123^023^01^01^17863650192011945233028.（P174）ASL=（1×1+2×2+2×3+2×4）／7=19/729.（P158）初始关键字[25][57][48][37][12][92][86]第一趟归并后[2557][3748][1292][86]第二趟归并后[25374857][128692]第三趟归并后[12253748578692]四、算法阅读题30.（1）本算法功能是将双向循环链表结点的数据域按值自小到大排序，成为非递减（可能包括数据域值相等的结点）有序双向循环链表。（2）①r-prior=q-prior;//将q结点摘下，以便插入到适当位置。②p-next-prior=q;③p-next=q;//②③将q结点插入④r=r-next；或r=q-next;//后移指针，再将新结点插入到适当位置。31.（1）chars[]或char*s(2)j++(3)i=j32.（1）（i==k）returna[k](2)i+1(3)i-1(4)i!=k[解析]本算法利用快速排序思想，找到第k个元素的位置（下标k-1因而开初有k--）。内层do循环以t（t=a[low]）为“枢轴”找到其应在i位置。这时若i等于k，则算法结束。（即第一个空格处if（i==k）returna[k]）。否则，若ik，就在i+1至high中间去查；若ik，则在low到i-1间去找，知道找到i=k为止。33.（1）height(p-lchild)（2）hi=rh+1（3）0五、算法设计题34.（P84）intLeaves(Treet){//计算以孩子——兄弟表示法存储的森林的叶子数if(t)if(t-fch==NULL)//若结点无孩子，则该结点必是叶子17191143230return(1+Leaves(t-nsib));//返回叶子结点和其兄弟子树中的叶子结点数elsereturn(Leaves(t-fch)+Leaves(t-nsib));//孩子子树和兄弟子树中叶子数之和}//结束Leaves[解析]当森林（树）以孩子兄弟表示法存储时，若结点没孩子（fch==NULL），则它必是叶子，总的叶子结点个数是孩子子树（fch）上的叶子数和兄弟（nsib）子树上叶结点个数之和。冲刺模拟试卷（二）一、单项选择题1.D（P9）2.C(P21)3.C(P38)4.A(P51)5.D(P67)6.D(P60)7.A(P72)8.C(P79)9.D(P105)10.C(P102)11.A(P127)12.C(P147)13.D(P168)14.C(P193)15.B(P214)1.[解析]一个算法在计算机运行所耗费的时间用时间复杂度来度量。算法的时间复杂度是算法输入规模或问题规模的函数，一般不必算出精确值，更关心的是相应的数量级。算法的时间复杂度与算法中语句的执行次数有直接关系，而语句的执行次数又取决于问题规模n的大小。实际上求解时间复杂度的方法是算出算法中执行频度最大的那条语句的频度，取其数量级放入O（）中。2.[解析]在单链表的开始结点之前附加一个结点，称它为头结点，增加头结点会带来以下两个优点：（1）由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置的操作就和在表的其他位置上的操作一致，无需进行特殊处理。（2）无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针为空），因此空表和飞空表的处理也就统一了。3.[解析]根据循环队列的结构，很快可以排除A和B（因为它们与QueueSize无关），而队列指针中front为队头，rear为队尾，当队尾加1循环到达队头时表示队满。5.[解析]一个广义的深度指表展后所含括号的层数。而（x,y,a,L）=(x,y,a,(x,y,a,(x,y,a,…))),L的前三个元素的原子，而第四个元素是L本身，展开后是一个无限的广义表，它的深度为∞。6.[解析]9*10*6=5407.[解析]编号为49的结点的左孩子编号为：2*49=98。8.[解析]有左孩子表示不是线索，即p-ltag=0。9.[解析]在邻接表中，对图中每个顶点都建立一个单链表，每个单链表设一个表头结点，n个顶点的图有n个单链表，共设n个表头结点，所以表头向量的大小就是图中顶点的个数n。10.[解析]连通图是指任意两个不相同的顶点之间都存在路径的无向图，而简单路径指不带有回路的路径，因此在具有n个顶点的连通图上不带回路的路径，其长度不可能超过n-1。11.[解析]B、C、D三种排序在一趟排序结束后都能选出一个元素，放在其最终位置上，只有插入排序，做一趟排序完成的是把当前待排序列中的第一个元素插入到有序序列的适当位置，但并不能保证这个位置是最终位置。12.[解析]直接插入排序和冒泡排序在初始数据有序时，最省时间效率最高，堆排序的时间不受数据初始情况的影响；而快速排序正好相反，初始数据有序时，算法效率最低，花费时间最多。13.[解析]若整个查找过程都在内存中进行，称为内查找；整个查找过程中需要访问外存，称为外查找；若在查找过程中只能进行检索，不做任何修改，查找表不会发生变化的查找为静态查找；若在查找过程中不但要检索，还要修改查找表的内容，称为动态查找。14.[解析]在用线性探测法进行探测时，容易造成“堆积”现象，即非同义词的两个数据元素企图抢占同一个存储单元的现象，所以在探测位置上的键值不一定是同义词。15.[解析]在ISAM文件中删除记录，只要找到待删除记录，在其存储位置上做删除标记即可。不需移动记录或改变指针，对文件的整理也不是删除后马上进行，而是定期整理。二、填空题16.（P3）线性结构17.（P18）其前趋结点的指针域中18.（P34）0（1）19.（P53）顺序存储、链式存储20.（P68）head(tail(head(tail(LS))))21.(P73)6822.(P105)有向23.（P150）50，70，60，95，8024.（P181）平衡二叉树25.（P215）数据集17.[解析]链表正是通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。由于上述链表的每个结点只有一个链域，故将这种链表称为单链表（SingleLinkedList）.显然，单链表中每个结点的存储地址是存放在其前驱结点的指针域中，而开始结点无前驱，故应设计头指针head指向开始结点，同时，由于终端结点无后继，故终端结点的指针域为空。18.[解析]由于入栈、出栈操作均在栈顶进行，与栈中的元素个数无关，所