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

36． 3DELLEFT(BT,X).

35． 3CREATE(X,LBT,RBT);

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);

    push(s,‘h’);

    while(!stackEmpty(s))

    {pop(s,y);

         printf(y);

         }

         prinft(x)

  }

以二叉链表为存储结构，分别实现二叉树的下列运算：

PARENT(BT,X);

31． 简述一下算法的功能：

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

30． 请将下面的程序改成递归的过程。

voide ditui(int n)

  {int i;

  i=n;

  while(i＞1)

  prinft(i--);

  }

32． 求下面算法中变量count的值：(假设n为2的乘幂，并且n＞2)

int Time

  {int n

       count=0;x=2;

       while(x＜n/2)

       {x*=2;count++;

       }

       return(count)

  }

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

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

26． 已知一棵具有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(…)))

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

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

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

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

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

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

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

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

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

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

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

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

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

12． 倒排文件的主要优点是( )

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

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

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

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

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

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

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

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

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

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

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