数据结构试卷B

数据结构导论模拟试卷(二)一、单项选择题(在每小题的4个备选答案中.选出1个正确的答案，并将其号码填在题干后的括号内。每小题2分，共30分)一个具有n个顶点的无向完全图的边数为()。n(n+1)n(n一1)A)2B)2C)n(n一1) D)n(n+1)在索引顺序表中查找一个元素，可用的且最快的方法是()人)用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找8)用顺序查找法确定元素所在块，再用二分查找法在相应块中查技c)用二分查找法确定元素所在块，再用顺序查找法在相应块中查我D)用二分查找法确定元素所在块，再用二分查找法在相应块中查找若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用()存储方式最节省运算时间。A)单链表 B)双链表C)带头结点的双循环链表 D)容量足够大的顺序表串是()。A)一些符号构成的序列 B)有限个字母构成的序列C)一个以上的字符构成的序列 D)有限个字符构成的序列堆排序在最坏情况下，其时间复杂性为()。A)O(nlogn) B)O(n2) C)O(logn2) D)O(logn)快速排序的记录移动次数()比较次数.其总执行时间为O(nlog2n)。A)大于 B)大于等于 C)小于等于 D)小于一棵二叉树有n个结点，要按某顺序对该二叉树中的结点编号(号码为l〜n)，编号须具有如下性质：二叉树中任一结点V，其编号等于其左子树中结点的最大编号加l，而其右子树中结点的最小编号等于V的编号加l。试问应按( )遍历顺序编号。A)前根 8)中根 C)后根 D)层次3个结点可构成()个不同形态的二叉树。A)2 B)3 C)4 D)5对有n个记录的有序表采用二分查找其平均查找长度的量级为()。A)O(logn) B)O(nlogn) C)O(n) D)O(n2)对有n个记录的表按记录键值有序的顺序建立二叉排序树，在这种情况下.其平均查找长度的量级为()。A)O(n) B)O(nlogn) C)O(1) D)O(logn)栈操作的原则是（）。A）先进先出 8）后进先出 C）栈顶插入 D）栈顶删除设矩阵A是一对称矩阵（a=a,1<i,j<8），若每个矩阵元素占3个单元，将其上三角部分（包括对角线）按行序为主序存放在数组B中，B的首址为1000,则矩阵元素a67的地址为（）。A）1031 B）1093 C）1096 D）1032链表适用于顺序查找，但在链表中进行（ ）操作的效率比在顺序存储结构中进行同样操作的效率高。A）顺序查找 B）二分法查找 C）快速查找 。插入任何一个无向连通图的最小生成树（）。A）只有一棵B）有一棵或多棵c）一定有多棵 D）可能不存在以下有关数据结构的叙述，（）是正确的。A） 线性表的线性存储结构优于链式存储结构B） 二叉树的第i层上有2巨个结点，深度为K的二叉树上有2k-1个结点c）二维数组是其数据元素为线性表的线性表D）栈的操作方式是先进先出。二、填空题侮空2分，共28分）在带有头结点的单链表L中，若要删除第一个结点，则需执行下列三条语句:；L->next=U->next；free（U）；有一个长度为20的有序表采用二分查找方法进行查找，共有—个元素的查找长度为3。采用冒泡排序对有n个记录的表A按键值递增排序，若L的初始状态是按键值递增，则排序过程中记录的比较次数为。若A初始状态为递减排列，则记录的交换次数为。在无头结点的双链表中，指针P所指结点是第一个结点的条件是。G为无向图，如果从G的某个顶点出发，进行一次广度优先搜索.即可访问图的每个顶点，则该图一定是 图。如果一个有向图中没有，则该图的全部顶点可以排成一个拓扑序列。深度为8（根的层次号为1）的满二叉树有 个叶子结点。将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X，其双亲PARENT（X）的编号为。分别采用堆排序、快速排序、冒泡排序和归并排序算法，对初始状态为递增序列的表按递增顺序排序，最省时的时算法，最费时间的是 树算法设有一个链队，结点结构为"佥I址”*'，front为队头指针.rear为队尾指针，当执行入队操作时需执行下列语句：malloc（p）；p->data=x；p->next=NUlLL;11.有向图G用邻接矩阵A[l..n，l..n]存储，其第i列的所有元素之和等于顶点i的。

三、应用题（共28分）1.有向图G的邻接表如图11所示，若删去图G中的边＜V3,V6＞和（V4,V5）,试画出修改后图的邻接表。（4分）顶点入度V021A1V21—3AV34—6AV40 h3 h5AV13A5V1A图11图G的邻接表对下列有向图12,写出以顶点1为出发点对图进行深度优先搜索所得到的所有可能的访问序列。（4分）对于键值序列（49,38,65,97,76,13,27,50），使用堆排序算法完成排序过程。要求：1） 画出初始堆（用二叉树表示）。（2分）2） 画出分别输出13,27后重建的两个堆。（4分）一个深度为d（根的层次号为1）的满K叉树有如下性质：第d层上的结点都是叶子结点，其余各层上的每个结点都有K棵非空子树。如果从根这一层开始按从左到右顺序逐层对全部结点编号，且根结点的编号为1,问编号为n的结点有右兄弟的条件是什么?其右兄弟的编号是多少?（4分）给定权值｛5,10,12,15,30,40｝，构造相应的赫夫曼树，要求写出构造步骤。（4分）已知一表为（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec）。按表中顺序依次插入初始为空的二叉排序树，要求：1） 画出建立的二叉排序树。（4分）2） 求出在等概率情况下查找成功的平均查找长度。（2分）四、设计题供14分）设有一单链表L,结点结构为"血|，结点个数至少3个，试画出链表l的结构图，并编写算法判断该单链表L中的元素是否成等差关系，即：设各元素值依次为ai，a，a，…，a，判断a-a.=a.-a是否成立，其中i满足2WiWn-l。（8分）2 3 n i+1iii-1设一棵二叉树以二叉链表作为存储结构，结点结构为出皿 ”壶些」，其中data域中存放一个字符，设计一个算法按先序遍历顺序仅打印出dam域为数字的字符（即'0'WdataW'9'）。（6分）数据结构导论模拟试卷(二)分析与解答一、单项选择题B.2,C.3,D.4,D.5,A.6,C.7,B.8,D.9,A.10,A.B.12,B.13,D.14,B.15,C.二、填空题分析：在带有头结点的单链表L上删除第一个结点，需依次执行以下三条语句：U=L->next；L->next=U->next；free(U)答案：U=L->next。分析：二分查找的过程可以用一棵有序树来表示，该树第三层上有4个结点，表示经过三次比较查找成功的元素个数为4。答案：4。分析：采用冒泡排序时，若初始时已经自然有序，那么经过一趟n-1次比比较后，算法就自动终止了。若初始状态为递减排列，希望排序成递增排列，则排序过程中比较一次、交换一次，总的比较、交换次数为n(n-1)/2,其中n-1为趟数，n/2为平均每趟的比较交换次数。答案：n(n-1)/2。答案：p->prior=NULL。分析：对无向图来讲，不管是对它进行一次探度优先搜索还是广度优先搜索，如果都能访问到图的每个顶点，则该图一定是个连通图。答案：连通。分析：一个有向图存在拓扑序列的条件之一是有向图中不存在回路或环。答案：回路或环。答案：28-1=27=128。分析：完全二叉树按层编号后，编号为m的结点，其双亲结点的编号为-。故当m=49时，其双亲编号为49=24。2答案：24。答案：冒泡排序、快速排序。答案：rear一〉next=p,rear=p。答案：入度三、应用题分析：在图11所示的有向图的邻接表上删除一条边时.不仅要在对应的出边表中删除一个结点，而且还要修改对应顶点的入度值。答案：修改后的有向图G的邻接表如图13所示。顶点入度图13修改后的有向图G的邻接表答案：共有3个访问序列：1,2,5,4.3,61,3,6,4,5,21.3,5,4,6,2分析：建堆过程参见前述（8.1节的有关说明）。在排序过程中，每输出一次根结点的键值，都要对二叉树调整一次，使其成为一个新的堆。答案：1）初始堆如图14所示。""图14初始堆2）输出13后重建的堆如图15所示。13图15输出13后重建的堆3）输出27后重建的堆如图16所示。13975076654927139750766549274.分析：在满k叉树中，个共同的双亲。比如：图164.分析：在满k叉树中，个共同的双亲。比如：除编号为1的根结点外，其余结点依次为每k个结点拥有一第2号〜第k+l号结点的双亲是第l号结点;第k+2号〜第2k+l号结点的双亲是第2号结点;第2k+1号〜第3k+1号结点的双亲是第3号结点;从中可以看出，若编号为n,那么当(n-1)%k=0时，它一定是某个结点的最右边的孩子，即它的右边不会再有兄弟了。反之，当(n-1)%k70时，它的右边一定还有兄弟。答案：编号为n的结点有右兄弟的条件是(n—1)%k尹0，该结点的右兄弟的编号是n+l。分析：哈夫曼树的构造过程参见4.1节中的有关说明。答案：哈夫曼树的构造过程如图17所示1510(a)初始时森林中有6颗树将去掉的两颗权值最小的树合并为一颗权值为151510(a)初始时森林中有6颗树将去掉的两颗权值最小的树合并为一颗权值为15的树将去掉的两颗权值最小的树合并为一颗权值为27的树将去掉的两颗权值最小的树合并为一颗权值为42的树将去掉的两颗权值最小的树合并为一颗权值为70的树最终得到的哈夫曼树图17哈夫曼树的构造过程分析：二叉排序树的建立过程就是在二叉排序树上不断插入新结点的过程。每插入一个结点，都是拿结点的值与根结点的值比较.若小于根结点的值，则往左子树上插；若大于根结点的值，则往右子树上插；若等于根结点的值.表示该结点已存在。在左、右子树中，再重复上述步骤，直到找到合适的插入位置。答案：1)建立的二叉排序树如图18所示。2)在等概率情况下，查找成功的平均查找长度为(1*l+2*2+3*3+4*3+5*2+6*1)=竺=7=3.5。12 2Nov图18建立的二叉排序树四、设计题1.分析：先求出前两个结点值的差b,然后再设置两个指针，从表的第2个结点开始，依次比较相邻两结点值的差是否等于b。如果都等于b,则返回真值True，否则返回假值False。答案：单链表的结构图如图19所示。图19单链表结构图算法：intisrise(lktlstL)(p=L->next；b=p->data-L->data；while(p->next!=NULL){q=p->next；if(q->data-p->data!=b)return(