1、计算机专业基础综合数据结构（查找）模拟试卷 1 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 若查找每个记录的概率均等，则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度 ASL 为( )。（A）(n 一 1)2（B） n2（C） (n+1)2（D）n1 顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为( (1) )，二分法查找只适用于查找顺序存储的有序表，平均比较次数为( (2) )。在此假定为线性表中结点数，且每次查找都是成功的。2 (1)（A）N+1（B） 2
2、log2N（C） log2N（D）N23 (2)（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 当采用分块查找时，数据的组织方式为( )。（A）数据分成若干块，每块内数据有序（B）数据分成若干
3、块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块（C）数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块（D）数据分成若干块，每块(除最后一块外)中数据个数需相同8 下面函数的功能是实现分块查找，空白处应该添加的内容是( )。int BlkSearch(int*nz，mt key，int block ，int BLK，int len)int i；block=block-1；if(len=0)puts(”表为空 !”)：return 0：if(BLKd len)BLK=len；for(i=block*BLK；i(block+1)*BLKif(P 一d
4、ataX)P=p 一rlink；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【知识模块】 数据结构39 【正确答案】 因为二叉树各结点已标明了平衡因子 b，故从根结点开始记树的层次。根结点的层次为 1，每下一层，层次加 1，直到层数最大的叶子结点，这就是平衡二叉树的
5、高度。当结点的平衡因子 b 为 0 时，任选左右一分支向下查找，若b 不为 0，则沿左(当 b=1 时) 或右(当 b=一 1 时)向下查找。int Height(BSTree t) 求平衡二叉树 t 的高度int level=0：BSTree p=t；while(P)level+： 树的高度增 1if(p-bf0)P=p-rchild；bf= 一 1 沿右分支向下bf 是平衡因子，是二叉树 t 结点的一个域，因篇幅所限，没有写出其存储定义else P=P 一 lchild： bf=0 沿左分支向下 whilereturn(level)： 平衡二叉树的高度算法结束【知识模块】 数据结构40 【
6、正确答案】 二叉排序树的建立问题前面第 3 题的(1)中已介绍，此处不再赘述。将二叉排序树上的各整数按降序写入磁盘，要对二叉排序树进行“中序遍历” ，这里的“中序遍历 ”要采取“右根左”。为方便起见，先将整数写入一全局变量数组中，再写入磁盘文件中。int i=0，an： 长度为 n 的整型数组void lnOrder(BSTree t)先右后左的中序遍历二叉排序树 t，假定该树 t 已在第 3 题(1)中生成if(t)InOrder(t-rchild)；ai+=t-key ；InOrder(t-lchild)；void SaveToDisk() /将二叉排序树上的各整数按降序写入磁盘FILE*
7、fp：if(fo=fopen(”fileldat”，”wb”)=null)printf(”file can not open!n”) ；exit(0) ；fwrite(a，sizeof(int)，n，fp)； 将数组 a 中的 n 个整数写入磁盘fclose(fp)； 关闭文件【知识模块】 数据结构41 【正确答案】 (1)递归算法void DecPrint(BSTree t)递减序输出二叉排序树 t 中所有左子树为空、右子树非空的结点数据域的值if(t)DecPrint(t 一rchild)：if(!t 一lchild&t 一rchild)printf(t 一data：4)；DecPrint
8、(t 一lchild)：(2)非递归算法void DecPrint(BSTree t)递减序输出二叉排序树 t 中所有左子树为空、右子树非空的结点的值BSTree s； s 是二叉排序树结点指针的栈，容量足够大int top=0：while(t | top0)while(t)s+top=t；t=t-rchild ； 沿右分支向下if(top0)t=stop-；if(!t 一lchild&t 一rchild)printf(t 一data：4)：t=t 一lchild； 去左分支 if while算法结束【知识模块】 数据结构42 【正确答案】 这是一个在单链表中查找结点，在结点内查找给定值的过程
9、，先定义存储结构。typedef struct nodeint Am： 每个结点内含有 m 个正整数，本例中 m 为 5struct node *next； 指向下一结点的指针LNode，*LinkList：typedef structint j； i 整数在结点内的序号struct node *s； 结点的指针rcd；rcd * LSearch(LinkList head，int n)在链表中查找正整数 n，若查找成功，返回该结点指针及 n 在结点中的序号，否则返回空指针表示失败。rcd*R；P=head 一next； 假定链表带头结点，P 指向链表第一元素结点int found=0mt 1；while(P&!found)for(i=0；i m；i+)if(P-Ai=n)found=1 查找成功P=P-next ： 下一结点if(P=null)return(null)；elseRj=i ；RS=P；return(R)；【知识模块】 数据结构43 【正确答案】 int Search(rectype R，int n，K)在具有 n 个元素的有序表 R 中，顺序查找值为 K 的结点，查找成功返回其位置，否则返回一 1 表示失败
