《数据结构》全真模拟试题与解答(共7页).doc

《《数据结构》全真模拟试题与解答(共7页).doc》由会员分享，可在线阅读，更多相关《《数据结构》全真模拟试题与解答(共7页).doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上全真模拟试题一、单项选择题（在每个小题的4个备选答案中，选出正确的答案，并将其号码填在题后的括号内。每小题2分，共24分）1一个具有n个顶点的无向完全图的边数为（ ）n(n+1)/2 n(n-1)/2 n(n-1) n(n+1)2在索引顺序表中查找一个元素，可用的且最快的方法是（ ）用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找用顺序查找法确定元素所在块，再用二分查找法在相应块中查找用二分查找法确定元素所在块，再用顺序查找法在相应块中查找用二分查找法确定元素所在块，再用二分查找法在相应块中查找3若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最

2、后一个元素，则采用（ ）存储方式最节省运算时间。 单链表 双链表带头结点的双循环链表容量足够大的顺序表4串是（ ）一些符号构成的序列 有限个字母构成的序列一个以上的字符构成的序列有限个字符构成的序列5堆排序在最坏情况下，其时间复杂性为（ ） O(nlog2n) O(n2)O(log2n2) O(log2n)6快速排序的记录移动次数（ ）比较次数，其总执行时间为O(nlog2n)。 大于 大于等于 小于等于 小于7一棵二叉树有n个结点，要按某顺序对该二叉树中的结点编号，（号码为1-n），编号须具有如下性质：二叉树中任一结点V，其编号等于其左子树中结点的最大编号加1。而其右子树中结点的最小编号等于

3、V的编号加1。试问应按（）遍历顺序编号。 前根 中根 后根 层次8.3个结点可构成（ ）个不同形态的二叉树。 2 3 4 59对有n个记录的有序表采用二分查找，其平均查找长度的量级为（） O(log2n)O(nlog2n)O(n)O(n2) 10对有n个记录的表按记录键值有序的顺序建立二叉树，在这种情况下，其平均查找长度的量级为（） O(n)O(nlog2n)O(1)(log2n) 11栈操作的原则是（） 先进先出后进先出栈顶插入栈顶删除 12设矩阵A是一对称矩阵(aij=aji,1=i,jnext=U-next；free(U)；2有一个长度为20的有序表采用二分查找方法进行查找，共有个元素的

4、查找长度为3。3采用冒泡排序对有n个记录的表A按键值递增排序，若L的初始状态是按键值递增，则排序过程中记录的比较次数为。若A的初始状态为递减排列，则记录的交换次数为。4在无头结点的双链表中，指针P所指结点是第一个结点的条件是。5G为无向图，如果从G的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是图。6如果一个有向图中没有，则该图的全部顶点可能排成一个拓扑序列。7深度为8（根的层次号为1）的满二叉树有个叶子结点。8将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X，其双亲PARENT（X）的编号为。9设某闭散列表HT未满，散列函数H（KEY）为键值第一字母在字

5、母表中的序号，处理冲突方法为线性探测法，请在下列算法划线处填上适当内容，以实现按键值第一字母的顺序输出闭散列表中所有键值的算法。void printword(keytype HTm) for(i=1;idata=x; p-next=NULL；四、应用题（共26分）1有向图G的邻接表如下图所示，若删去图G中的边V3，V6和V4，V5，试画出修改后图的邻接表。（4分）2有向图如下图所示，写出以V1为出发点对图进行深度优先搜索所得到的所有可能的访问序列。（4分）3125463对于键值序列（49,38,65,97,76,13,27,50），使用堆排序算法完成排序过程。要求：画出初始堆（用二叉树表示）。

6、画出分别输出13,27后重建的两个堆。（5分）4.一个深度为d（根的层次号为1）的满K叉树有如下性质：第d层上的结点都是叶子结点，其余各层上的每个结点都有K棵非空子树。如果从根这一层开始从左到右顺序逐层对全部结点编号，且根结点的编号为1，问编号为n的结点有右兄弟的条件是什么？其右兄弟的编号是多少？（3分）5给定权值5,10,12,15,30,40，构造相应的哈夫曼树，要求写构造歩骤。（4分）6已知一表为（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec）,按表中顺序依次插入初始为空的二叉排序树，要求：画出建立的二叉排序树。（4分）求出在等概率情况下

7、查找成功的平均查找长度。（2分）五、设计题（共14分）1设有一单链表L，结点结构为data|next，结点个数至少3个，试画出链表L的结构图，并编写算法判断该单链表L中的元素是否成等差关系，即：设各元素值次为a1,a2,a3,an，判断ai+1-ai=ai-ai-1是否成立，其中i满足2=i=n-1.(8分)2设有一棵二叉树以二叉链表作为存储结构，结点结构为lchild|data|rchild,其中data域中存放一个字符，设计一个算法按前根遍历顺序仅打印出data域为数字的字符（即0=data=9）（6分）全真模拟参考答案一、单项选择题1.2.3.4. 5. 6. . 7. 8. 9. 10

8、. 对键值有序的、具有n个记录的表来讲，当所建立的二叉排序树是一棵深度为n的单支树时，在它上面的查找操作已经退化为顺序查找，所以其平均查找长度的量级为O（n）.1112按题意要求，将对称矩阵A的上三角部分按行优先进行存放数组了B中，那么Bk与aij的对应关系为：当i next2 4。分析：二分查找的过程可以用一棵有序树来表示，该树第三层上有4个结点，表示经过三次比较查找成功的元素个数为4。3 n-1、n(n-1)/2。分析：采用冒泡排序时，若初始时已经自然有序，那么经过一趟n-1次比较后，算法就自动终止了。若初始状态为递减排列，希望排序成递增排列，则排序过程中比较一次，交换一次，总的比较、交换

9、次数为n(n-1)/2，其中n-1为趟数，n/2为平均每趟的比较交换次数。4 p - prior = NULL。5 连通6 回路或环7 28-1 = 27 = 1288 249 HTj!=NULL或HTj不为空、H(HTj)=I10 rear - next = p、rear = p四、应用题1 修改后的有向图G的邻接表如图所示。2 1，2，5，4，3，61，3，6，4，5，21，3，5，4，6，23初始堆如图所示。 输出13后重建的堆如图所示。 输出27后重建的堆如图所示。4分析：在满k叉树中，除编号为1的根结点外，其余结点依次为每k个结点拥有一个共同的双亲。比如：第二号第k+1号结点的双亲是

10、第1号结点；第k+2号第2k+1号结点的双亲是第2号结点；第2k+1号第3k+1号结点的双亲是第3号结点；从中可以看出，若编号为n，那么当(n-1)%k = 0时，它一定是某个结点的最右边的孩子，即它的右边不会再有兄弟了。反之，当(n-1)%k0，它的右边一定还有兄弟。答案：编号为n的结点有兄弟的条件是(n-1)%k0，该点的右兄弟的编号是n+1。5哈夫曼树的构造过程如图所示。 6建立的二叉排序树如图所示。 在等概率情况下，查找成功的平均查找长度为（1+2+3+4+5+6+.+12)/12 = 7*12/12 = 7。五、设计题1单链表的结构图如图设计题 9.1.2所示。a1a2an算法：int isrise (lklist L) p = L - next; b = p - data L - data; while (p - next != NULL) q =p - next; if (q - data p - data !=b) return(0) else p = q; return(1); 2 Void Nchar (bitreptr t) if (t != Null) if (t - data = 0 ) & (t - data data ); Nchar (t - lchild); Nchar (t - rchild);专心-专注-专业