1、综合模拟试卷 21 及答案与解析一、填空题1 在数据结构中，与计算机无关的数据称为() ；单链表是一种()存储结构的线性表，适合于()查找。2 二叉树最常用的( ) 是二叉链表。3 一棵二叉树的前序遍历是 FcABED，中序遍历是 ACBFED，则其后序遍历是( )。4 设树的度为 5，其中度为 15 的结点数分别为 6、5、4、3、2 个，则该树共有( )个叶子。5 11 个顶点的无向图，最多能有( )条边。6 某索引顺序表共有元素 275 个，平均分成 5 块。若先对索引表采用顺序查找，再对块中元素进行顺序查找，则在等概率情况下，分块查找成功的平均查找长度是( )。7 交换排序适用于( )
2、 存储结构的表。8 由 AF 六个字母构成的堆序列是( )。二、判断题9 抽象数据类型与计算机内部表示及实现无关。( )（A）正确（B）错误10 线性表的插人、删除总是伴随着大量数据的移动。( )（A）正确（B）错误11 队列在程序调用时必不可少，因此递归离不开队列。( )（A）正确（B）错误12 字符串“aababaaaba”的改进失败函数 nextval 数组值是 0020200320。( )（A）正确（B）错误13 二叉树中有双子女的父结点，在中序遍历中后继一定是其中一个子女结点。( )（A）正确（B）错误14 不用递归就不能实现二叉树的前序遍历。( )（A）正确（B）错误15 若有向图
3、有 n 个顶点，则其强连通分量最多有 n 个。( )（A）正确（B）错误16 平衡二叉树一定是一棵完全二叉树。( )（A）正确（B）错误17 若某内排序算法不稳定，则该算法没有实用价值。( )（A）正确（B）错误18 倒排文件的目的是为了多关键字查找。( )（A）正确（B）错误三、综合题19 已知一组关键字为(112，214，305，46，57，86，72，162，95)，现用散列函数 H(k)=k10 将它们散列到表 HT09中，用线性探测法 H(k)，H(k)+1，H(k)+2， ，H(k)一 1 解决冲突，画出最后的散列表，并计算产生冲突的次数。20 简述 Prim 算法和 Kruska
4、l 算法求最小生成树的算法思想，分析它们的时间复杂度及分别适用于什么样的网。21 阅读下面程序，根据输入写出输出结果。#include“iostreamh”voidswap(int&x，int&y)intz=x：x=y；y=z；voidchange(inta100，inti，intj)if(in：for(inti=0；imi；change(m，0，n 一 1)；for(i=0；ilc，isbbt)；inthr=Post(t 一 re，isbbt)；if(h1hr1)isbbt=0；if(hl(t=NULL)return0；(1)inthl=Post(t 一lc，isbbt)；inthr=Pos
5、t(t 一 rc，isbbt)；if(abs(hl-hr)1)isbbt=0；(2)if(hlreturnb1+1(3)intbbt(bitptrt)intisbbt=1；(4)Post(t，isb)t)；returnisbbt：【试题解析】 (1)中 t 为空才返回。(2)中不能确定左大还是右大，所以要用绝对值。(3)中左小于右的话要加 1。(4)要赋初值。23 【正确答案】 typedefstriletarcnodeintadjvex；arctypeinfo；arcnode*nextare：arcnode；typedefstrcutvertypedata；arcnode*firstarc；vernode，adjlstMAXVERTEX；typedefstructadjlistvertices；intvernum，arcnum；graph；voidConvert(graph&gl，graph&g2)for(inti=0；ig1v【试题解析】 对一个 i 结点，其邻接矩阵的 i 行中为 1 的值的元素就要加邻接表的 i 结点后面的结点。唯一需要注意的是空结点在邻接表中是没有的。
