《《数据结构》全真模拟试题与解答》由会员分享，可在线阅读，更多相关《《数据结构》全真模拟试题与解答（9页珍藏版）》请在金锄头文库上搜索。
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堆排序在最坏情况下，其时间复杂性为() 0(nlog 2n) 0(n2) O(log 2n2) O(log 2n)6快速排序的记录移动次数()比较次数，其总执行时间为0(nlog2n)。大于大于等于小于等于小于7. 棵二叉树有n个结点，要按某顺序对该二叉树中的结点编号，(号码为1-n ),编号须具有如下性质：二叉树中任一结点V,其编号等于其左子树中结点的最大编号加1。而其右子树中结点的最小编号等于V的编号加1。试冋应
3、按()遍历顺序编号。前根 中根8.3个结点可构成(234后根 层次 )个不同形态的二叉树。59对有n个记录的有序表采用二分查找，其平均查找长度的量级为() O(log 2n) O(nlog 2n) O(n) O(n2)10 对有n个记录的表按记录键值有序的顺序建立二叉树，在这种情况下，其平均查 找长度的量级为() O(n) O(nlog 2n) O(1)(log 2n)11 .栈操作的原则是()先进先出后进先出栈顶插入栈顶删除12 .设矩阵A是一对称矩阵(a ij =aji ,1=i,jnext=U-next ; free（U）;2. 有一个长度为20的有序表采用二分查找方法进行查找，共有个元
4、素 的查找长度为3。3. 采用冒泡排序对有n个记录的表A按键值递增排序，若L的初始状态是按键值递增，则排序过程中记录的比较次数为。若A的初始状态为递减排列，则记录的交换次数为。4. 在无头结点的双链表中，指针P所指结点是第一个结点的条件是。5. G为无向图，如果从 G的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图-图。6如果一个有向图中没有，则该图的全部顶点可能排成一个拓扑序列。7. 深度为8 （根的层次号为1）的满二叉树有个叶子结点。8. 将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X,其双亲PARENT（X） 的编号为。9. 设某闭散列表 HT未满，散列
5、函数 H（ KEY为键值第一字母在字母表中的序号，处 理冲突方法为线性探测法，请在下列算法划线处填上适当内容，以实现按键值第一字母的 顺序输出闭散列表中所有键值的算法。void prin tword（keytype HTm） for（i=1;idata=x; p-next=NULL ;?四、应用题（共26分）1有向图G的邻接表如下图所示，若删去图G中的边V V3, V6和V V4, V5,试画出修改后图的邻接表。（4分）顶点入度2有向图如下图所示，写出以V1为出发点对图进行深度优先搜索所得到的所有可能的访问序列。（4分）3. 对于键值序列（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）,按表中顺 序依次插入
7、初始为空的二叉排序树，要求：画出建立的二叉排序树。（4分）求出在等概率情况下查找成功的平均查找长度。（2分）五、设计题（共14分1. 设有一单链表L,结点结构为data|next ，结点个数至少3个，试画出链表 L的结构图，并编写算法判断该单链表L中的元素是否成等差关系，即：设各元素值次为a1,a 2,a 3, -；a n,判断 ai+1 -ai=ai-a i-1 是否成立，其中 i 满足 2=i=n-1.（8 分）2. 设有一棵二叉树以二叉链表作为存储结构，结点结构为|lchild|data|rchild,其中data域中存放一个字符，设计一个算法按前根遍历顺序仅打印出data域为数字的字符
8、（即0=data= 9） （6 分）全真模拟参考答案一、单项选择题I. 2.3.45.6.78910. 对键值有序的、具有 n个记录的表来讲，当所建立的二叉排序树是一棵 深度为n的单支树时，在它上面的查找操作已经退化为顺序查找，所以其平均查找长 度的量级为0(n).II. 12. 按题意要求，将对称矩阵A的上三角部分按行优先进行存放数组了B中，那么Bk与aij的对应关系为：当 i n ext2. 4。 分析：二分查找的过程可以用一棵有序树来表示，该树第三层上有4个结点，表示经过三次比较查找成功的元素个数为4。3. n-1、n(n-1)/2 。分析：采用冒泡排序时，若初始时已经自然有序，那么经过
9、一趟n-1次比较后，算法就自动终止了。若初始状态为递减排列，希望排序成递增排列，则排序过程中比较一次，交换一次，总的比较、交换次数为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)=l10 . rear - next = p 、rear = p四、应用题1.修改后的有向图 G的邻接表如图所示。2. 1, 2, 5, 4, 3, 61, 3, 6, 4, 5, 21, 3, 5, 4, 6, 23 初始堆如图
10、所示。输出13后重建的堆如图所示。输出27后重建的堆如图所示。4分析：在满k叉树中，除编号为1的根结点外，其余结点依次为每k个结点拥有一个共同的双亲。比如：第二号一第k+1号结点的双亲是第1号结点；第k+2号一第2k+1号结点的双亲是第 2号结点；第2k+1号一第3k+1号结点的双亲是第 3号结点；从中可以看出，若编号为n,那么当（n-1）%k = 0 时，它一定是某个结点的最右边的孩子，即它的右边不会再有兄弟了。反之，当（n-1）%k工0，它的右边一定还有兄弟。答案：编号为n的结点有兄弟的条件是（n-1）%k工0,该点的右兄弟的编号是 n+1。5.哈夫曼树的构造过程如图所示。1080101111111011001101在等概率情况下，查找成功的平均查找长度为(1+2+3+4+5+6+.+12)/12 = 7*12/12 = 7五、设计题1 单链表的结构图如图设计题n9.1.2 所示。ala2anAn算法：int isrise (Iklist L)p = L - next; b = p - data- L - data;while (p - next != NULL)q =p - n ext;if (q - data- p - data !=b) return(O)
