1、计算机专业基础综合（数据结构）模拟试卷 6 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 若查找每个记录的概率均等，则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度 ASL 为( )。（A）(n 1)2（B） n2（C） (n+1)2（D）n1 顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为( (1) )，二分法查找只适用于查找顺序存储的有序表，平均比较次数为( (2) )。在此假定N 为线性表中结点数，且每次查找都是成功的。2 (1)（A）N+1（B） 2lo
2、g2N（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，int key，int block ，int BLK，int len)int i；block=block1：if(lenlen)BLK=len；for(i=block*BLK；illink ，flag) ； 中序遍历左子树if(pre=null)pre=t； 中序遍历的第一个结点不必判断e
4、lse if(pre 一datadata)pre=t； 前驱指针指向当前结点else flag=false； 不是二叉排序树JudgeBST(t 一rlink， flag)； 中序遍历右子树本题的另一算法是依照定义，二叉排序树的左右子树都是二叉排序树，根结点的值大于左子树中所有值而小于右子树中所有值，即根结点大于左子树的最大值而小于右子树的最小值。算法如下：int JudgeBST(BTree t)判断二叉树 t 是否是二叉排序树，若是，返回 true，否则，返回 falseif(t=null)return true；if(JudgeBST(t 一llink) 否则将其插入第 i 个集合if(
5、iidk)printf(” 无第d 个集合n”，i)；exit(0)： if(i=1)first=0； first 指向第 i 个集合在数据表的首址 else first=idai1+1； last=idai； last 是第i 个集合在数据表中的末址 for(j=first；jidAi；j-)t 查找失败，将 x 插入数据表 Rj+1=Rj； 元素后移 Rj+1=x ； 将 x 插入到原第 i 个集合最后一个元素之后 for(j=i;jk；j+)idaj+； 修改索引表中各集合最后一个元素的下标 由于各集合元素个数不等，各块长度不等且块间无序，索引表中用数组表示，数组中元素值是各集合最后一个
6、元素在数据表中的下标。按本算法插入(2，112)和(1， 53) ，数据表前后状态如下：插入前，索引表中 a 数组的内容是 3，6，12，插入后修改为 4，8，14。【知识模块】 数据结构27 【正确答案】 (1)非递归建立二叉排序树，在二叉排序树上插入的结点都是叶子结点。typedef struct nodeElemtype data；struct node*LLINK，*RLINK；node*BiTree：void Create_BST(BiTree bst，datatype K，int n)以存储在数组 K 中的 n 个关键字，建立一棵初始为空的二又排序树int i：BiTree P，
7、f：for(i=1；idataRLINK； f 是 P 的双亲else if(p 一dataKi)f=P；P=p 一LLINK ；S=(BiTree)malloc(sizeof(BiNode)；申请结点空间s-data=Ki; s-LLINK=null ; s 一RLINK=null ；if(f=null)bst：S ； 根结点else if(S-datadata)f-LLINK=S； 左子女else f 一RLINK=s： 右子树根结点的值大于等于根结点的值(2)本题要求输出遍历二叉排序树的嵌套括号表示。其算法思想是，若二叉排序树非空，则输出根结点，再输出其左右子树。在输出其左右子树前，要输
8、出左括号，在输出其右子树前要输出逗号，在输出其右子树后要输出右括号，在左右子树均空情况下，则不输出括号。void Print(BiTree t) 以嵌套括号表示结构打印二叉排序树if(t!=null)printf(t 一data) ； 打印根结点值if(t 一LLINK |t 一LLINK)； 左子女和右子女中至少有一个不空printf(”(”)； 输出左括号Print(t 一LLINK)i 输出左子树的嵌套括号表示if(t 一RLINK)printf(” ，”)； 若右子树不空，输出逗号Print(t 一RLINK) ； 输出右子树的嵌套括号表示printf(”)”)； 输出右括号【知识模块
9、】 数据结构28 【正确答案】 void Delete(BSTree t，P) 在二叉排序树 t 中，删除 f 所结点的右孩子(由 P 所指向)if(P 一lchild=null)f 一rchild=P 一rchild；free(P)；p 无左子女else 用 P 左子树中的最大值代替 P 结点的值q=p 一lchild；s=q；while(q 一rchild) s=q；q=q 一rchild； 查 P 左子树中序序列最右结点if(s=p 一lchild) p 左子树的根结点无右子女p 一 data=s 一data ；p 一lchild=s 一lchild ； free(S)；elsep 一d
10、ata=q 一data；s 一rchild=q 一lchild；free(q)；【知识模块】 数据结构29 【正确答案】 本题用被删结点右子树中最小值(中序遍历第一个)结点代替被删结点。w)id Delete(BSTree bst，P ，fp)在二叉排序树 bst 上，删除 fp 所指结点的左子女(由 P 所指向)if(!p 一lchild)fp 一lchild=p 一rchild；free(P)； p 无左子女else if(!p 一rchild)fp 一lchild=p 一lehild ；flee(P)； p 无右子女else P 有左子女和右子女q=P 一rchild；s=q； 用 P
11、右子树中的最小值代替 P 结点的值while(q 一lchild)S=q；q=q 一lchild ； 查 P 右子树中序序列最左结点if(S=p 一rehild) p 右子树的根结点无左子女p 一 data=s 一data ；p 一rchild=s 一rchild ； frees)；elsep 一data=q 一data；s 一lchild=q 一rchild；free(q)；【知识模块】 数据结构30 【正确答案】 在二叉排序树上删除结点，首先要查找该结点。查找成功后，若该结点无左子树，则可直接将其右子树的根结点接到其双亲结点上；若该结点有左子树，则将其左子树中按中序遍历的最后一个结点代替该
12、结点，从而不增加树的高度。void Delete(BSTree bst， keytype X) 在二叉排序树 bst 上，删除其关键字为 X 的结点BSTree f，p=bst ：while(P将被删结点的右子树接到其双亲上else f 一rchild=p 一rehild；elseq=P； s=p 一lehild ； 被删结点有左子树while(S-rehild!=null) 查左子树中最右下的结点(中序最后结点)q=s；s=s 一rehild;P 一key=s 一key； 结点值用其左子树最右下的结点的值代替if(q=P)P 一lchild=s 一lchild ； 被删结点左子树的根结点无右
13、子女else q 一rchild=s 一lchild ； s 是被删结点左子树中序序列最后一个结点free(s)；【知识模块】 数据结构31 【正确答案】 intSeareh(reetype r ，int n，keytype k)在 n 个关键字从小到大排列的顺序表中，查找关键字为 k 的结点rn+1key=MAXINTi 在高端设置监视哨int i=1：while(ri keykind=BRANCH P=T 一left；while(Pp=p 一left； q 记 P 的双亲if(P) p 结点的值小于等于 X q 一left=P 一right； p 一right=null ；DelTree(
14、P)； P=q 一left ； 再查原 P 的右子树中小于等于 X 的结点【知识模块】 数据结构38 【正确答案】 typedef struct nodedatatype data；int count；struct node*llink，*rlink；BiTNode，*BSTree：void Search_InsertX(BSTree t，datatype X)在二叉排序树 t 中查找值为 x 的结点，若查到，则其结点的 count 域值增 1，否则，将其插入到二叉排序树中BSTree p=t；while(P!=null 每个结点内含有 m 个正整数，本例中 m 为 5struet node*
15、next； 指向下一结点的指针LNode，*LinkList；typedef struetint j； 正整数在结点内的序号struet node*s； 结点的指针rcd；rcd*LSearch(LinkList head，int n)在链表中查找正整数 n，若查找成功，返回该结点指针及 n 在结点中的序号，否则返回空指针表示失败。rcd*R：P=head 一next； 假定链表带头结点，P 指向链表第一元素结点int found=0：Int 1；while(P&!found)for(i=0；iAi=n)found=1 查找成功P=P 一next： 下一结点if(P=null)return(n
16、ull)；elseRj=i ；Rs=P； return(R)；【知识模块】 数据结构43 【正确答案】 int Search(rectype R，int n，K)在具有 n 个元素的有序表 R 中，顺序查找值为 K 的结点，查找成功返回其位置，否则返回一 1 表示失败int i=0：while(iK)return(一 1)ii+： whilereturn 一 1；在等概率的情况下，则查找成功的平均查找长度为(n+1)2，查找失败的平均查找长度为(n+2) 2(失败位置除小于第一个，还存在大于最后一个 )。若查找成功和不成功的概率也相等，则查找成功时和关键字比较的个数的期望值约为(n+1)4。【知识模块】 数据结构
