1、全国自考（数据结构）模拟试卷 8 及答案与解析一、单项选择题1 在桶排序中，其平均时间复杂度是( )（A）O(1)（B） O(n)（C） O(n2)（D）O(1gn)2 C 语言数组 Datam+1作为循环队列 SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作的语句为( )（A）front=front+1（B） front=(front+1)%m（C） rear=(rear+1)%m（D）front=(front+1)%(m+1)3 某二叉树的前序遍历结点访问顺序是 abdgcefh，中序遍历的结点访问顺序是bgbaechf，则其后序遍历的结点访问顺序是( )（A
2、）bdgcefha（B） gdbecfha（C） bdgechfa（D）gdbehfca4 如果以链表作为栈的存储结构，则退栈操作时( )（A）必须判别栈是否满（B）判别栈元素的类型（C）必须判别栈是否空（D）对栈不作任何判别5 在一个具有 n 个单元的顺序栈中，假设栈底是存储地址的高端，现在我们以 top作为栈顶指针，则作退栈操作时，top 的变化是( )（A）top=top-1（B） top=top+1（C） top 不变（D）top 不确定6 对采用二分查找法进行查找运算的查找表，要求按( )方式进行存储。（A）顺序存储（B）链式存储（C）顺序存储且结点按关键字有序（D）链式存储且结点按
3、关键字有序7 在一棵完全二叉树的顺序存储方式中，若编号为 t 的结点有右孩子，则此结点右孩子的编号为( )（A）2t（B） 2t-1（C） 2t+1（D）t/28 对于一个具有 N 个结点和 E 条边的无向图，若采用邻接表示，则表头向量的大小是( )（A）N（B） N+1（C） N-E（D）N-19 任何一个带权的无向连通图的最小生成树( )（A）只有一棵（B）有一棵或多棵（C）一定有多棵（D）可能不存在10 在一个链队中，假设 f 和 r 分别为队首和队尾指针，则删除一个结点的运算是( )（A）r=f next（B） r=rnext（C） f=fnext（D）f=r next11 森林 T
4、中有 4 棵树，第一、二、三、四棵树的结点个数分别是 n1，n 2，n 3，n 4，那么当把森林 T 转换成一棵二叉树后，其根结点的左孩子上有 ( )个结点。（A）n 1-1（B） n1（C） n1+n2+n3（D）n 2+n3+n412 倒排文件的主要优点是( )（A）便于进行插入和删除运算（B）便于进行文件的合并（C）能大大提高基于非关键码数据项的查找速度（D）能大大节省存储空间13 一个队列的输入序列是 1,2,3,4，则队列的输出序列是( )（A）4,3,2,1（B） 1,2,3,4（C） 1,4,3,2（D）3,2,4,114 在有向图中，所有顶点的入度之和是所有顶点出度之和的( )
5、倍。（A）0.5（B） 1（C） 2（D）415 从一个长度为 n 的顺序表中删除第 i 个元素(1in)8 寸，需要向前移动( )（A） n-i（B） n-i+1（C） n-i-1（D）i二、填空题16 设线性表(a 1，a 2， a500)元素的值由小到大排列。对一个给定的 k 值，用二分法检索查找表中与 k 相等的元素，在检索不成功的情况下，至多需比较_次。17 _与数据元素本身的内容和形式无关。18 已知无向图 G 的结点数为 n，边数为 e，其邻接表表示中的表结点数与表头结点数之和为_。19 对带有头结点的链队列 lq，判定队列中具有一个数据元素的条件是 _。20 判断一个没有头结点
6、的单链表 head 为空的条件是 _。21 就文件而言，按用户的观点所确定的基本存储单元称为_。按外设的观点所确定的基本存储单元称为_。22 对于一个具有 n 条边和 e 个顶点的图来说，如果采用邻接表表示，则其空间复杂度为_，若采用邻接矩阵表示，则其空间复杂度为_。23 设有一元多项式 A(x)=7+3x+10x30-4X100+13x101，用单链表给出 A(x)的存储表示为_。24 在顺序表中，插入或者删除一个元素，需要平均移动_个元素，具体移动的元素个数与_有关。25 一棵树中非叶子结点的个数为 n，与树对应的二叉树中右子树为空的结点的个数为 m，则 m=_。三、解答题26 已知一棵具
7、有 2 个结点的二叉树的前序遍历序列和后序遍历序列是 AB 和BA，请问：这棵二叉树是惟一的吗?如果树是不惟一的，请画出满足此条件的不同的二叉树，并简单分析一下。27 对于下面的 3 个广义表，请画出其图形表示式，并说明它们各属于什么类型的广义表。 (1)B(A(x,l(a,b),y) (2)C(A(x,l(a,b),B(A(x,l(a,b),y) (3)D(a,D(a,D()28 已知有如下一个关键字序列96,47,104,32,73,136,15,38,90,180 ，按照上述插入顺序构造一棵二叉排序树，则请给出二叉排序树的构造过程，说明其深度，并在等概率的条件下求出平均查找长度。29 已
8、知有一组长度为 9 的关键字序列为22,63,72,54,97,17,37,80,92 ，现在假设散列表的地址空间为 T010，请用除余法构造散列函数，如果存在冲突问题，请用线性探查法解决冲突，并给出相应的散列表。四、算法阅读题30 请将下面的程序改成递归的过程。 voide ditui(int n) int i; i=n; while(i1) prinft(i-); 31 简述一下算法的功能： status A (1inkedlist L) /L 是无表头结点的单链表 if (LLnext) Q=L;L=Lnext;P=L; while(Pnext)P=Pnext; Pnext=Q;Q ne
9、xt=NULL; return ok; )/A32 求下面算法中变量 count 的值：(假设 n 为 2 的乘幂，并且 n2) int Time int n count=0;x=2; while(xn/2) x*=2;count+; return(count) 33 写出下列程序段的输出结果。(假设此栈中元素的类型是 char) voide main( ) stack s; char x,y; InitStack(s) x=1,y=0 push(s,x); push(s,x); push(s,y); push(s,x)； push(s,e); push(s,x); pop(s,x); pus
10、h(s,h); while(!stackEmpty(s) pop(s,y); printf(y); prinft(x) 五、算法设计题33 以二叉链表为存储结构，分别实现二叉树的下列运算：34 PARENT(BT,X);35 3CREATE(X,LBT,RBT);36 3DELLEFT(BT,X).全国自考（数据结构）模拟试卷 8 答案与解析一、单项选择题1 【正确答案】 B2 【正确答案】 D3 【正确答案】 D4 【正确答案】 C5 【正确答案】 B6 【正确答案】 C7 【正确答案】 C8 【正确答案】 A9 【正确答案】 B10 【正确答案】 C11 【正确答案】 A12 【正确答案】
11、 C13 【正确答案】 B14 【正确答案】 B15 【正确答案】 A二、填空题16 【正确答案】 917 【正确答案】 数据的逻辑结构18 【正确答案】 n+2e19 【正确答案】 lgfrontnext=lqrear20 【正确答案】 hcad=NULL21 【正确答案】 逻辑记录 物理记录22 【正确答案】 O(n+c) O(n 2)23 【正确答案】 24 【正确答案】 约表长的一半 该元素在线性表中的位置25 【正确答案】 n+1三、解答题26 【正确答案】 满足这个条件是二叉树并不是惟一的，因为仅知道前序遍历序列和后序遍历序列并不能惟一地确定一棵二叉树，满足此题条件的有两棵不同的二
12、叉树，分别如下图所示： 这两棵二叉树的前序遍历序列都是 AB，后序遍历序列是 BA，但它们是两棵完全不同的二叉树。27 【正确答案】 广义表对应的图形如下图所示，其中图 1 为树形结构，所以是纯表，图 2 中结点 A 为共享结点，则它属于再入表，图 3 中因为存在递归，则它属于递归表。 28 【正确答案】 根据二叉排序树的生成过程，我们可以得到如下二叉排序树的构造结果： 此二叉排序树的深度(即高度)为 4，在二叉树上，要找到第 i 层上的结点恰好需要比较 i 次，而在此二叉排序树上，第 1,2,3,4 层上分别有 1,2,3,4 个结点，则在等概率的条件下，查找成功的平均查找长度为： 29 【
13、正确答案】 因为散列函数为：h(key)=key%11，则根据此函数得到上述关键字序列的散列地址为：(0,8,6,10,9,6,1,3,4)，前 5 个关键字在插入时，其相应的地址是开放地址，可以直接插入到 T0，T8 ，T6，T10，T9中，在插入到 6 个关键字时，其散列地址 6 已被关键字 72 占用，所以探查 h1=(6+1)%11=7。此地址开放，所以将关键字 17 插入到 T7中，然后再依次将关键字 34，80，92 插入到相应的散列地址中即可。则相应的散列袁为： 四、算法阅读题30 【正确答案】 此递推过程可以改写成如下递归过程： voide dkui(int j) if(i1)
14、 prind(j); digui(j-1); 31 【正确答案】 本程序实现的功能就是：如果 L 的长度不小于 2，则将首元结点删去并插入到表尾。32 【正确答案】 count=log 2n33 【正确答案】 此题的输出结果是 hello。五、算法设计题34 【正确答案】 bitreptr parent(bitreptr BT,p; datatype x) /*调用前 P 为空指针*/ if(BT!=NULL) if(BTdata=X)return(p) /*找到，返回其父结点 */ elsep=BT; parent(BTlchild,p-,x); /*查找其左子树*/ parent(BTrc
15、hild,p,x)； /*查找其右子树 */ 35 【正确答案】 Void create(datatype x; bhreptr LBT,LBR) BT=mallloc(size) BTdata=x; BTlchild=LBT; /*赋左子树*/ BTrchild=LBR; /*赋右子树*/ 36 【正确答案】 Void delleft(bitreptr BT; datatype x) if(BT!=NULL) if(BTdata=x) BTlchild=NULL; /*删除其左子树*/ return; /*结束*/ else delleft(BTlchild,x)； /*转左子树*/ delleft(BTrchild,x); /*转右子树*/
