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

35． 下列算法用于判断带头结点的循环双链表A是否对称相等，请在算法中的一填上正确的语句。

int dlink_symmetry(dlklist s)

  {j=true;

    p=s—＞next;

    q=s—＞prior;

    while(p!=q)&(______)

      if(p—＞data=q—＞data)

         { (______);

        (______);

         }

      else

           j=false;

       return(j);

  }

34． 以下为单链表的定位运算，分析算法，请在______处填上正确的语句。

int locate_iklist(1klist head,datatype x)

  /*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/

    { p=head;j=O;

      while(______){p=p—＞next;j++;}

      if(p—＞data==x)return(j);

      else{return(0);

    }

36． 若输入12000个不同的整数，其值介于0和19999之间，采用散列表存储这些数，散列函数为h(k)=k/2，请设计实现的算法。

33． 以下是图的广度优先搜索算法，请在______处填充适当的语句。

Bfs(GraphTp g,int v)

    { QueptrTp Q;

    ArcNodeTp*P;

    InitQueue(&Q);

    printf("%"”,v);

    visited[v]=1;

    ______

    while(!EmptyQueue(Q))

    {______;

    p=g.adjlist[v].firstarc;

    while(p! =NULL)

    { if(! visited[p—＞adjvex])

    { printf("%"”,p—＞adjvex);

      visited[p—＞adjvex]=1);

      EnQueue(&Q，p—＞adjvex);

    }

    ______;

    }

   }

  }

32． 以下运算实现在循环队上取队头，请在______处用适当的语句予以填充。

int GetHead(CycqueueTp sq,DataType*x)

       { if(sq.rear==______return(0);

          else{*x=sq.data[______];

               return(1);

              }

       }

31． 请画出二叉树的五种基本形态。

30． 已知散列函数为H(K)=K mod 12，键值序列为25,37,52,43,84,99,120,15,26,11,70,82，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。

28． 以上述两个单链表为基础，通过插入和删除等运算得出A(x)+B(x)的存储表示，使其存储空间覆盖A(x)和B(x)的存储空间。

29． 假设一个循环队列的容量为50，对其进行人队和出队操作，则经过一段时间之后，有：

(1)front=35，rear=12；

(2)front=12，rear=35。

其中front和rear分别是队头和队尾指针。

求：循环队列中元素的个数?

27． 用单链表给出B(x)的存储表示。

25． 在线性表的顺序存储中，元素之间的逻辑关系是通过______决定的；在线性表的链接存储中，元素之间的逻辑关系是通过______决定的。

设有多项式

A(x)=7+3x+9x⁸+5x¹⁷

B(x)=8x+22x⁷一9x⁸

用单链表给出A(x)的存储表示。

24． 顺序串是用一组地址连续的存储单元来存储串中的字符序列，所以可以用字符数组来实现，按照存储分配方式的不同可以将顺序串分为两类：即______和______。

23． 设二维数组A[10··20,5··10]按行优先存储·，每个元素占4个存储单元，A[10,5]的存储地址是1000，则A[15,10]的存储地址是______。

22． 如果一个图中有n条边，则此图的生成树含有______条边，所以生成树是图的边数______的连通图。

21． 数组的长度是______，线性表的长度是______。

18． 任何连通图的连通分量只有一个，即______。

20． 在非空队列中，头指针始终指向______，而尾指针始终指向______。

19． 设有一个已按各元素的值排好序的线性表，长度为125，对给定的k值，用二分法查找与k相等的元素，若查找成功，则至少需要比较______次，至多需比较______次。

17． 朴素的串匹配算法的特点是简单，但是其效率较低，其时间匹配算法的最坏时间是______(假设模式串的长度是m，目标串的长度是n)。

16． ______的有向图，其全部顶点有可能排成一个拓扑序列。

14． 当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为 ( )

15． 栈一般情况下常采用以下两种存储方式( )

13． 假定一棵二叉树的结点为18个，则此二叉树的最大高度为( )，最小高度为( )

12． 下面关于线性表的叙述错误的是( )

11． 考虑下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是( )

9． 线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着( )

10． 非空的循环单链表head的尾结点(由指针p所指)满足( )

7． 如果一个队列的入队顺序是1,2,3,4,5，则此队列的出队顺序是( )

8． 静态查找表与动态查找表二者的根本差别在于( )

5． 在一个具有N个顶点的无向完全图中，包含的边的总数是( )

6． 在一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p，q之间插入s结点，则执行( )操作。

4． ( )方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。

3． 下面的查找方式中，可以对无序表进行查找的是( )

2． 磁带适合存储的文件类型是( )

1． 循环链表的主要优点是( )