全国自考（数据结构）模拟试卷8

自考责任编辑：彭雅倩 2019-08-13

自考公众号点击领取自考备考资料

一、1.单项选择题

0. 在桶排序中，其平均时间复杂度是( )

A．O(1)
B．O(n)
C．O(n²)
D．O(1gn)

1. C语言数组Data[m+1]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为( )

A．front=front+1
B．front=(front+1)%m
C．rear=(rear+1)%m
D．front=(front+1)%(m+1)

2. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是bgbaechf，则其后序遍历的结点访问顺序是( )

A．bdgcefha
B．gdbecfha
C．bdgechfa
D．gdbehfca

3. 如果以链表作为栈的存储结构，则退栈操作时( )

A．必须判别栈是否满
B．判别栈元素的类型
C．必须判别栈是否空
D．对栈不作任何判别

4. 在一个具有n个单元的顺序栈中，假设栈底是存储地址的高端，现在我们以top作为栈顶指针，则作退栈操作时，top的变化是( )

A．top=top-1
B．top=top+1
C．top不变
D．top不确定

5. 对采用二分查找法进行查找运算的查找表，要求按( )方式进行存储。

A．顺序存储
B．链式存储
C．顺序存储且结点按关键字有序
D．链式存储且结点按关键字有序

6. 在一棵完全二叉树的顺序存储方式中，若编号为t的结点有右孩子，则此结点右孩子的编号为( )

A．2t
B．2t-1
C．2t+1
D．t/2

7. 对于一个具有N个结点和E条边的无向图，若采用邻接表示，则表头向量的大小是( )

A．N
B．N+1
C．N-E
D．N-1

8. 任何一个带权的无向连通图的最小生成树( )

A．只有一棵
B．有一棵或多棵
C．一定有多棵
D．可能不存在

9. 在一个链队中，假设f和r分别为队首和队尾指针，则删除一个结点的运算是( )

A．r=f—＞next
B．r=r—＞next
C．f=f—＞next
D．f=r—＞next

10. 森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n₁，n₂，n₃，n₄，那么当把森林T转换成一棵二叉树后，其根结点的左孩子上有( )个结点。

A．n₁-1
B．n₁
C．n₁+n₂+n₃
D．n₂+n₃+n₄

11. 倒排文件的主要优点是( )

A．便于进行插入和删除运算
B．便于进行文件的合并
C．能大大提高基于非关键码数据项的查找速度
D．能大大节省存储空间

12. 一个队列的输入序列是1,2,3,4，则队列的输出序列是( )

A．4,3,2,1
B．1,2,3,4
C．1,4,3,2
D．3,2,4,1

13. 在有向图中，所有顶点的入度之和是所有顶点出度之和的( )倍。

A．0.5
B．1
C．2
D．4

14. 从一个长度为n的顺序表中删除第i个元素(1≤i≤n)8寸，需要向前移动( )

A． n-i
B．n-i+1
C．n-i-1
D．i

二、2.填空题

0. 设线性表(a₁，a₂，…，a₅₀₀)元素的值由小到大排列。对一个给定的k值，用二分法检索查找表中与k相等的元素，在检索不成功的情况下，至多需比较______次。

1. ______与数据元素本身的内容和形式无关。

2. 已知无向图G的结点数为n，边数为e，其邻接表表示中的表结点数与表头结点数之和为______。

3. 对带有头结点的链队列lq，判定队列中具有一个数据元素的条件是______。

4. 判断一个没有头结点的单链表head为空的条件是______。

5. 就文件而言，按用户的观点所确定的基本存储单元称为______。按外设的观点所确定的基本存储单元称为______。

6. 对于一个具有n条边和e个顶点的图来说，如果采用邻接表表示，则其空间复杂度为______，若采用邻接矩阵表示，则其空间复杂度为______。

7. 设有一元多项式A(x)=7+3x+10x³⁰-4X¹⁰⁰+13x¹⁰¹，用单链表给出A(x)的存储表示为______。

8. 在顺序表中，插入或者删除一个元素，需要平均移动______个元素，具体移动的元素个数与______有关。

9. 一棵树中非叶子结点的个数为n，与树对应的二叉树中右子树为空的结点的个数为m，则m=______。

三、3.解答题

0. 已知一棵具有2个结点的二叉树的前序遍历序列和后序遍历序列是AB和BA，请问：这棵二叉树是惟一的吗?如果树是不惟一的，请画出满足此条件的不同的二叉树，并简单分析一下。

1. 对于下面的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(…)))

2. 已知有如下一个关键字序列{96,47,104,32,73,136,15,38,90,180}，按照上述插入顺序构造一棵二叉排序树，则请给出二叉排序树的构造过程，说明其深度，并在等概率的条件下求出平均查找长度。

3. 已知有一组长度为9的关键字序列为{22,63,72,54,97,17,37,80,92}，现在假设散列表的地址空间为T[0..10]，请用除余法构造散列函数，如果存在冲突问题，请用线性探查法解决冲突，并给出相应的散列表。

四、4.算法阅读题

0. 请将下面的程序改成递归的过程。
voide ditui(int n)
{int i;
i=n;
while(i＞1)
prinft(i--);
}

1. 简述一下算法的功能：
status A (1inkedlist  L)
   {//L是无表头结点的单链表
    if (L&&L—＞next)
      {Q=L;L=L—＞next;P=L;
      while(P—＞next)P=P—＞next;
      P—＞next=Q;Q—＞next=NULL;
      }
return ok;
)//A

2. 求下面算法中变量count的值：(假设n为2的乘幂，并且n＞2)
int Time
{int n
    count=0;x=2;
    while(x＜n/2)
    {x*=2;count++;
    }
    return(count)
}

3. 写出下列程序段的输出结果。(假设此栈中元素的类型是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);
   push(s,‘h’);
   while(!stackEmpty(s))
   {pop(s,y);
     printf(y);
     }
     prinft(x)
}