1、计算机专业基础综合数据结构（查找）-试卷 1 及答案解析(总分：88.00，做题时间：90 分钟)一、单项选择题(总题数：23，分数：48.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。_2.若查找每个记录的概率均等，则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度 ASL 为( )。（分数：2.00）A.(n 一 1)2B.n2C.(n+1)2D.n顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为( (1) )，二分法查找只适用于查找顺序存储的有序表，平均比较次数为( (2) )。在此假定为线性表中
2、结点数，且每次查找都是成功的。（分数：4.00）(1).(1)（分数：2.00）A.N+1B.2log 2 NC.log 2 ND.N2(2).(2)（分数：2.00）A.N+1B.2log 2 NC.log 2 ND.N23.适用于折半查找的表的存储方式及元素排列要求为( )。（分数：2.00）A.链接方式存储，元素无序B.链接方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序4.具有 12 个关键字的有序表，折半查找的平均查找长度为( )。（分数：2.00）A.31B.4C.25D.55.折半查找的时间复杂性为( )。（分数：2.00）A.O(n 2 )B.O(n)C.
3、O(nlog 2 n)D.O(log 2 n)6.当采用分块查找时，数据的组织方式为( )。（分数：2.00）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D.数据分成若干块，每块(除最后一块外)中数据个数需相同7.下面函数的功能是实现分块查找，空白处应该添加的内容是( )。 int BlkSearch(int*nz，mt key，int block，int BLK，int len) int i； block=block-1； if(len=0
4、) puts(”表为空!”)：return 0： if(BLKdlen)BLK=len； for(i=block*BLK；i(block+1)*BLK if(P 一dataX)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 )解析：37.
5、假设一棵平衡二叉树的每个结点都标明了平衡因子 b，试设计一个算法，求平衡二叉树的高度。（分数：2.00）_正确答案：(正确答案：因为二叉树各结点已标明了平衡因子 b，故从根结点开始记树的层次。根结点的层次为 1，每下一层，层次加 1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子 b 为 0 时，任选左右一分支向下查找，若 b 不为 0，则沿左(当 b=1 时)或右(当 b=一 1 时)向下查找。 int Height(BSTree t) 求平衡二叉树 t 的高度 int level=0： BSTree p=t； while(P) level+： 树的高度增 1 if(p-b
6、f0)P=p-rchild；bf=一 1 沿右分支向下 bf 是平衡因子，是二叉树 t 结点的一个域，因篇幅所限，没有写出其存储定义 else P=P 一lchild： bf=0沿左分支向下 while return(level)： 平衡二叉树的高度 算法结束)解析：38.设从键盘输入一个整数的序列：n，a 1 ，a 2 ，a n ，其中 n 表示连续输入整数的个数。 (1)试编写一程序按整数值建立一个二叉排序树。 (2)在(1)的基础上将此二叉树上的各整数按降序写入一磁盘文件中。（分数：2.00）_正确答案：(正确答案：二叉排序树的建立问题前面第 3 题的(1)中已介绍，此处不再赘述。将二叉
7、排序树上的各整数按降序写入磁盘，要对二叉排序树进行“中序遍历”，这里的“中序遍历”要采取“右根左”。为方便起见，先将整数写入一全局变量数组中，再写入磁盘文件中。 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*fp： if(fo=fopen(”fileldat”，”wb”)=nul
8、l) printf(”file can not open!n”)；exit(0)； fwrite(a，sizeof(int)，n，fp)；将数组 a 中的 n 个整数写入磁盘 fclose(fp)； 关闭文件 )解析：39.设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空、右子树非空的结点的数据域的值。（分数：2.00）_正确答案：(正确答案：(1)递归算法 void DecPrint(BSTree t) 递减序输出二叉排序树 t 中所有左子树为空、右子树非空的结点数据域的值 if(t) DecPrint(t 一rchild)： i
9、f(!t 一lchild&t 一rchild)printf(t 一data：4)； DecPrint(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； 去左分支
10、if while 算法结束)解析：40.在单链表中，每个结点含有 5 个正整型的数据元素(若最后一个结点的数据元素不满 5 个，以值 0 充)，试编写一算法查找值为 n(n0)的数据元素所在的结点指针以及在该结点中的序号，若链表中不存在该数据元素则返回空指针。（分数：2.00）_正确答案：(正确答案：这是一个在单链表中查找结点，在结点内查找给定值的过程，先定义存储结构。 typedef struct node int Am： 每个结点内含有 m 个正整数，本例中 m 为 5 struct node *next； 指向下一结点的指针 LNode，*LinkList： typedef struct
11、 int j； i 整数在结点内的序号 struct node *s； 结点的指针 rcd； rcd * LSearch(LinkList head，int n) 在链表中查找正整数 n，若查找成功，返回该结点指针及 n 在结点中的序号， 否则返回空指针表示失败。 rcd*R； P=head 一next； 假定链表带头结点，P 指向链表第一元素结点 int found=0 mt 1； while(P&!found) for(i=0；im；i+) if(P-Ai=n)found=1 查找成功 P=P-next： 下一结点 if(P=null)return(null)； elseRj=i；RS=P
12、；return(R)； )解析：41.编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，且查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。（分数：2.00）_正确答案：(正确答案：int Search(rectype R，int n，K) 在具有 n 个元素的有序表 R 中，顺序查找值为 K 的结点，查找成功返回其位置， 否则返回一 1 表示失败 int i=0： while(in) if(Ri=K)return(i)； else if(RiK)return(一 1)； i+： while return 一 1； 在等概率的情况下，则查找成功的平均查找长度为(n+1)2，查找失败的平均查找长度为(n+2)2(失败位置除小于第一个，还存在大于最后一个)。若查找成功和不成功的概率也相等，则查找成功时和关键字比较的个数的期望值约为(n+1)4。)解析：
