1、综合模拟试卷 17 及答案与解析一、单项选择题1 假定我们从下图所示的二叉堆中删除了值为 11 的结点，那么值为 50 的结点将出现在图中的哪个指定位置( )。（A）A（B） B（C） C（D）D2 有一个 2000 项的表，采用等分区间顺序查找的分块查找算法，若每块大小为20，平均查找长度为( ) 。（A）75（B） 48（C） 61（D）603 A 和 B 分别是一棵二叉树中的两个结点，下面说法中不正确的是 ( )（A）A 在 B 的左边，中根遍历时 A 先被访问（B） A 在 B 的右边，后根遍历时 A 先被访问（C） A 是 B 的子孙，中根遍历时 A 先被访问（D）A 是 B 的祖先
2、，先根遍历时 A 先被访问4 已知 A1,N是一棵顺序存储的完全二叉树，9 号结点和 11 号结点共同的祖先是( )。（A）4（B） 6（C） 2（D）85 一棵满 3 叉树，按层次遍历的方式存储在一维数组 A1，N 中，那么下标为 4 的结点的第 3 个孩子的下标为( )。（A）10（B） 12（C） 13（D）86 在下面的排序算法中哪种是稳定的排序算法( )。（A）希尔排序（B）快速排序（C）选择排序（D）归并排序7 有 6 个元素按 a，b，c ， d，e，顺序进栈，下列哪个不是合法的出栈序列( )。（A）bcdaef（B） chdefa（C） (1cahef（D）edcfba8 已知
3、存在广义表 A=(x，(a ，b)，(c ，d)，在其上进行 head(head(tail(A)的结果为( )。（A）(a，b)（B） (a)（C） (x)（D）(a，b)9 假设存在一棵哈夫曼树 T，它具有 m 个叶结点，则该树的结点总数为( )。（A）2m（B） m+1（C） 2n1（D）不能唯一确定10 存在一个由 8 个结点组成的图，结点从 07 编号，图中有 13 条有向边，分别是：07、0 一 1、14、16、23、34、42、52、6 一 0、63、65、7 一 1、73，下面选项中哪个是该图的强连通分量( )。（A）0 一 1 一 4（B） 356（C） 0 一 1 一 67（
4、D）143二、简答题11 假定使用 B 一树结构来组织一些位于磁盘上的文件数据。请问为什么 B 一树的阶数选择得过大或过小都会使数据查找的性能受到严重影响?12 如果先使用线性探测再用 Hash 法为 1000 个元素设计 Hash 表，Hash 函数的类型为 Hash(x)=xtnodD。假定要求查找成功时平均查找长度不大于 4，不成功时平均查找长度不大于 185。那么为了满足上述要求，D 的值最少应为多少?13 下图表示的是一个三阶 B 一树，请画出在此树中插入值 47 后的结果。14 假设： 请写出 O(T(n)，并证明你的答案。14 假定在内存中存在着一个由多行组成的文本，每行最多有
5、255 个字符，并且具有一个唯一标识自己的行号。该文本中的各行以行号从小到大依次存放。要求行号必须连续，且可以从两个方向访问文本中的各行。试使用链表编写以下函数：15 向文本中插入新行，插入行的位置由参数给出。16 将文本中相邻的两行物理位置进行交换(注意这里不仅仅是交换两行的内容)。17 修改快速排序算法，使它仅输出一个数列中最大的 n 个数，并且这 n 个数不要求已排好序。18 已知存在一个有向图 G，A 和 B 是 G 中的两个结点，试编写一个非递归算法求G 中从 A 到 B 的所有简单路径。假定该有向图使用邻接矩阵的方式存储。19 已知存在一个数组 PN)i存放着整数型完全二叉树中第
6、i 个结点的父亲的结点号，如果 Pi=0，则该结点的父亲为根结点。假定二叉树中左孩子的值肯定大于右孩子的值。另外，存在一个数组 NodeN存放该二叉树各结点的值，如 Nodei存放着第 i 号结点的值。编制一个算法根据 PN和 NodeN构建该二叉树的链表表示结构。20 基于上题所创建的二叉树，使用非递归算法输出和等于指定数的所有连通数列(连通数列指该数列对应的结点在树上存在一条连接路径)。假设所提供的数值不能小于等于根结点的数值。例如，输入 12，如果在二叉树中存在值为 1、3、8 的结点且这 3 个结点连通，则将其输出。综合模拟试卷 17 答案与解析一、单项选择题1 【正确答案】 B【试题
7、解析】 堆排序的调整。2 【正确答案】 C【试题解析】 (1+100)2+(1+20)2=61。3 【正确答案】 C【试题解析】 4 【正确答案】 C【试题解析】 按照子结点与父结点之间的倍数关系推导即可。5 【正确答案】 C【试题解析】 可以先画出简单的一个三叉树，然后展开推导。6 【正确答案】 D7 【正确答案】 C【试题解析】 栈为先进后出的数据结构，在 a、b、c 同时在栈内的情况下，a 不可能比 b 先出栈。8 【正确答案】 A【试题解析】 明白 head 与 tail 的作用即可作答。M1=tail(A)=(a ，b)，e，d)M2=head(M1)=(a，b)，e ，d)M3=h
8、ead(M2)=(a，b)9 【正确答案】 C【试题解析】 叶结点与总数之间的关系公式为 n+n1+n2=n1+2n2+1=nn 0=n2+1=m且 n1=0，则结点总数为 2m-1。10 【正确答案】 C【试题解析】 先画出图，即可得出答案。二、简答题11 【正确答案】 阶数选择过小，B 一树的层数会过大，由于 B 一树存储在磁盘里，如果层数过多，在磁盘上查找的次数会更多；阶数选择过大，则在每个结点中的比较次数就会变多。12 【正确答案】 1000 一 DXD4D3156D 最少是 32。13 【正确答案】 14 【正确答案】 0(T(n)=n。用非递归算法描述时 X=3；for(i=0；i
9、size=size，则交换最后两行p 为指定的结点，PP 为 P 的前驱结点pnext 为 P 的后续结点，pnn 为 pnext 的后续结点inti；Line*P，*pp，*pnext ，*pnn；if(nun=b 一size 一 1&b 一size1)指定行大于总行数，则交换最后两行位置pnext=b 一rear ；P=pnext 一prior；PP=P 一prior：pnn=pnext 一next：17 【正确答案】 intpartition(inta ，intsize ，intn)size 表示数组 a 中的元素个数，下标从 0size1返回值是 sizen，表示从此下标以后的值是最大
10、的 n 个数inttemp，low，high，mark ，begin，end；begin=0；end=size1：if(n=sizedIInNodei)左20 【正确答案】 pop(s)和 push(S，node)为堆栈的出栈和入栈的操作IsEmpty(S)判断是否堆栈为空，是为 1，否为 0getTop(S)返回堆栈的栈顶指针getTopNum(S)返回堆栈的栈顶的编号printPath(S)会将堆栈里的结点的 value 值按照人栈的顺序打印出来node*SN；暂存的结点intVN；暂存栈内对应结点的访问情况，初始 0，左孩子被访问 1，右孩子被访问 2voidshowPath(node 术 tree，intvalue)value
