1、计算机专业基础综合（查找）模拟试卷 1 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 若查找每个记录的概率均等，则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度 ASL 为( )。（A）(n 1)2（B） n2（C） (n+1)2（D）n2 顺序查找法适用于查找顺序存储或链式存储的线性表二分法查找只适用于查找顺序存储的有序表，平均比较次数为( )。在此假定 N 为线性表中结点数，且每次查拔都是成功的。（A）N+1（B） 2log2N（C） log2N（D）N23 顺序查找法适用
2、于查找顺序存储或链式存储的线性表，平均比较次数为( )在此假定 N 为线性表中结点数，且每次查拔都是成功的。（A）N+1（B） 2log2N（C） log2N（D）N24 适用于折半查找的表的存储方式及元素排列要求为( )。（A）链接方式存储，元素无序（B）链接方式存储，元素有序（C）顺序方式存储，元素无序（D）顺序方式存储，元素有序5 具有 12 个关键字的有序表，折半查找的平均查找长度为( )。（A）31（B） 4（C） 25（D）56 折半查找的时间复杂性为( )。（A）O(n 2)（B） O(n)（C） O(nlog2n)（D）O(log 2n)7 当采用分块查找时，数据的组织方式为(
3、 )。（A）数据分成若干块，每块内数据有序（B）数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块（C）数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块（D）数据分成若干块，每块(除最后一块外)中数据个数需相同8 下面函数的功能是实现分块查找，空白处应该添加的内容是( )。int BlkSearch(int*nz，int key，int block ，int BLK，int len)int i；block=block-1；if(1enlen)BLK=len；for(i=block*BLK；i0)的数据元素所在的结点指针以及在该结点中的序
4、号，若链表中不存在该数据元素则返回空指针。46 编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，且查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。计算机专业基础综合（查找）模拟试卷 1 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 此题考查的知识点是顺序查找长度 ASL 的计算。假设表长度为 n，那么查找第 i 个数据元素需进行 n 一 i+1 次比较，即 Ci=n 一 i+l。又假设查找
5、每个数据元素的概率相等，即 Pi=1n，则顺序查找算法的平均查找长度为： 所以应选 C。【知识模块】 查找2 【正确答案】 C【试题解析】 此题考查的知识点是各类查找算法的比较次数计算。顺序查找法用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败，其ASL=(n+1) 2，即查找成功时的平均比较次数约为表长的一半。应选 C。【知识模块】 查找3 【正确答案】 D【试题解析】 二分法查找过程可用一个称为判定树的二叉树描述，由于判定树的叶子结点所在层次之差最多为 1，故 n 个结点的判定树的深度与 n 个结点的完全二叉树的深度相等，均为log 2n+1。这样，折半查找成功时，关键字比较次
6、数最多不超过log 2n+1。所以，应选择 D。【知识模块】 查找4 【正确答案】 D【试题解析】 此题考查的知识点是折半查找的特点。折半查找要求顺序存储且元素有序，所以应选 D。【知识模块】 查找5 【正确答案】 A【试题解析】 此题考查的知识点是折半查找的思想。把关键字按完全二叉树的形式画出查找树，按结点高度计算比较次数。12 个结点可以画出高度为 4 的完全二又树，1 层 1 个结点比较 1 次，2 层 2 个结点比较 2 次，3 层 4 个结点比较 3 次，4层 5 个结点比较 4 次，371231，应选 A。【知识模块】 查找6 【正确答案】 D【试题解析】 此题考查的知识点是折半查
7、找的效率。其查找效率与比较次数有关，折半查找成功时，关键字比较次数最多不超过log 2n+1，所以其效率为 O(log2n)，应选 D。【知识模块】 查找7 【正确答案】 B【试题解析】 分块查找是将数据分成若干块，块间有序，块内不必有序。【知识模块】 查找8 【正确答案】 A【试题解析】 如果当前的值与所查找关键字相等，则完成查找。【知识模块】 查找9 【正确答案】 C【试题解析】 二叉查找树的查找效率与树形有关，当结点呈单枝树排列时效率最低。【知识模块】 查找10 【正确答案】 C【知识模块】 查找11 【正确答案】 D【试题解析】 由平衡二叉树的特性可知，一棵高度为 h 的理想平衡二叉树
8、中，含有结点数最少的情形是：前 h 一 1 层为满二叉树，第 h 层只有一个结点，因而结点总数为(2 h-1 一 1)+1=2h-1。 含有结点数最多的情形是：该树是一棵高度为的满二叉树，因而结点总数为 2h-1。【知识模块】 查找12 【正确答案】 C【试题解析】 分别根据给出的序列构建平衡二叉树，得出 C 与其他不同。【知识模块】 查找13 【正确答案】 C【试题解析】 B-树定义如下： 一棵 m 阶 B-树，或者是空树，或者是满足以下性质的 m 叉树： (1)根结点或者是叶子，或者至少有两棵子树，至多有 m 棵子树。 (2)除根结点外，所有非终端结点至少有m 2棵子树，至多有 m 棵子树
9、。 (3) 所有叶子结点都在树的同一层上。 (4)每个结点应包含如下信 息：(n，A 2，K 1，A 1，K 2，A 2，K n，A n)。 其中： Ki(1in)是关键字，且KK i+1(1in一 1)； A i(i=0，1，n) 为指向孩子结点的指针，且 Ai-1 所指向的子树中所有结点的关键字都小于 Ki，A i 所指向的子树中所有结点的关键字都大于Ki。 n 是结点中关键字的个数，且m2 一 1nm一 1，n+1 为子树的棵数。【知识模块】 查找14 【正确答案】 C【试题解析】 设 Ni 表示深度为 h 的平衡二叉树中含有的最少结点数，有： N0=0， N1=1， N2=2； 计算的
10、公式为： N h=Nh-1+Nh-2+1； N 3=N2+N1+1=4； N4=N3+N2+1=7； N 5=N4+N3+1=12； N 6=N5+N4+1=2015。 也就是说，高度为 6的平衡二叉树最少有 20 个结点，因此 15 个结点的平衡二叉树的高度为 5，而最小叶子结点的层数为 3，所以选项 D 错误。 选项A 在查找 30 后，指针应该指向左孩子，而不是右孩子；选项 B 与选项 A 存在同样的问题，因而选项 A、B 错误。而选项 C 的查找路径如下图所示：【知识模块】 查找15 【正确答案】 D【试题解析】 根据 B 树定义可知只有正确。【知识模块】 查找16 【正确答案】 C【
11、试题解析】 此题考查的知识点是 B-树和 B+树的定义。 B-树定义见第 11 题，B+树是应文件系统所需而发展出的一种 B-树的变形树。一棵 m 阶的 B+树和 m 阶的 B-树的差异在于：(1)有 n 棵子树的结点中含有 n 个关键字。(2)所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。(3)所有的非终端结点可以看成是索引部分，结点中仅含其子树(根结点)中的最大(或最小) 关键字。通常在 B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。所以 B+树能有效地支持随机检索和顺序检索。显然应选 C。【知识模
12、块】 查找17 【正确答案】 B【试题解析】 此题考查的知识点是 m 阶 B-树的定义。B-树是一种平衡的多路排序树，m 阶即 m 叉。应选 B。【知识模块】 查找18 【正确答案】 D【试题解析】 二分查找判定树如下图所示，查找 A3的比较序列的下标为9，4，2，3，本题选 D。【知识模块】 查找19 【正确答案】 C【试题解析】 n=13，R11=82，第 1 次与 R(1+13)2=7=45 比较，第 2 次与R(8+13)2=10=77 比较，第 3 次与 R(11+13)2=12=95 比较，第 4 次与R(10+12)2=11=85 比较时成功，总共比较 4 次。【知识模块】 查找
13、20 【正确答案】 B【试题解析】 分块查找时最佳块数为 =25。【知识模块】 查找21 【正确答案】 B【试题解析】 有 n 个结点且为完全二叉树的二叉排序树的高度为 log2n。【知识模块】 查找22 【正确答案】 D【试题解析】 对散列表进行检索，平均检索长度仅与装填因子 有关，而与关键字个数 n 无关。【知识模块】 查找23 【正确答案】 C【试题解析】 由同义词的定义可知本题答案为 C。【知识模块】 查找24 【正确答案】 D【试题解析】 addr(49)=49 mod 11=5，冲突；h1=(5+1*1)mod 11=6，仍冲突；h2=(5+2*2)mod11=9，所以本题答案为
14、D。【知识模块】 查找二、综合应用题41-47 小题，共 70 分。25 【正确答案】 根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量 pre(初值为 null)和全局变量 flag，初值为 true。若非二叉排序树，则置 flag 为 false。#define true 1#define：false 0typedef struct nodedatatype data；stmct node * llink，*rlink ；* BTree；void JudgeBST(BTree t，int flag)判断二叉树是否是二叉
15、排序树，本算法结束后，在调用程序中由 flag 得出结论if(t!=nullif(p-lchild=null) 被删结点无左子树if(f 一lchild=p)f 一lchild：p-rchild；将被删结点的右子树接到其双亲上else f 一rchild=p-rehild；elseq=P； S=P-lchild； 被删结点有左子树while(S-rchild!=null) 查左子树中最右下的结点(中序最后结点)q=s；s=s 一rchild；P-key=s-key； 结点值用其左子树最右下的结点的值代替if(q=P)P 一lchild=s-lchild； 被删结点左子树的根结点无右子女else
16、 q-rchild=s-lchild； s 是被删结点左子树中序序列最后一个结点free(s)；【知识模块】 查找33 【正确答案】 intSearch(rectype r ，int n，keytype k)在 n 个关键字从小到大排列的顺序表中，查找关键字为 k 的结点rn+1key=MAXINT ； 在高端设置监视哨int i=1；while(ri keykind=BRANCHibhptrord(KEYchi) ，+i)； ord 求字符在字母表中的序号if(P 此处 null 代表散列表初始化时的空值switch(Hsi=k)case true;del(HS，i，j，K)；breakic
17、ase false;di=l；j=(i+di)m； m 为表长while(Hsj!=nullif(P 一datarlink ：else P=p-llink；if(!P) 无值为 x 的结点，插入之P：(BiTNode*) malloc(sizeof(BiTNode)；p-data=X；p-llink=null；p-rlink=null ；if(f-dataX) f-llink=P；else f-rlink=p；else P 一count+； 查询成功，值域为 X 的结点的 count 增 1【知识模块】 查找41 【正确答案】 因为二叉树各结点已标明了平衡因子 b，故从根结点开始记树的层次。根
18、结点的层次为 1，每下一层，层次加 1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子 b 为 0 时，任选左右一分支向下查找，若b 不为 0，则沿左(当 b=1 时) 或右(当 b=-1 时)向下查找。int Height(BSTree t) 求平衡二叉树 t 的高度int level=0；BSTree P=t：while(P)level+； 树的高度增 1if(p 一bfrehild；bf=-1 沿右分支向下bf 是平衡因子，是二叉树 t 结点的一个域，因篇幅所限，没有写出其存储定义else P=p 一lchild； bf=0 沿左分支向下 whilereturn(1ev
19、el)； 平衡二叉树的高度算法结束【知识模块】 查找【知识模块】 查找42 【正确答案】 将二叉排序树上的各整数按降序写入磁盘，要对二叉排序树进行“中序遍历”，这里的“中序遍历”要采取“右根左” 。为方便起见，先将整数写入一全局变量数组中，再写入磁盘文件中。int i=0，an； 长度为 n 的整型数组void InOrder(BSTree t)先右后左的中序遍历二叉排序树 t，假定该树 t 已在第 3 题(1)中生成if(t)InOrder(t-rchild)；ai+=t-key；InOrder(t 一 lchild)；【知识模块】 查找43 【正确答案】 void SaveToDisk()
20、 将二叉排序树上的各整数按降序写入磁盘FILE*fp；if(fp=fopen(”fileldat”，”wb”)=null)pfintf(”file caB not open!n”) ；exit(0) ；fwfite(a，sizeof(int)，n，fp)； 将数组 a 中的 n 个整数写入磁盘fclose(fp)； 关闭文件【知识模块】 查找44 【正确答案】 (1)递归算法void DecPfint(BSTree t)递减序输出二叉排序树 t 中所有左子树为空、右子树非空的结点数据域的值if(t)DecPfint(t 一rchild) ；if(!t 一lchild&t-rchild)pfinff(t-data：4) ；DecPfint(t 一lchild)：(2)非递归算法void DecPfint(BSTree t)递减序输出二叉排序树 t 中所有左子树为空、右子树非空的结点的值BSTree s； s 是二叉排序树结点指针的栈，容量足够大int top=0；while(t top0)while(t)s+top=t；t=t 一rchild；沿右分支向下if(top0)t=stop-；
