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

一、1.单项选择题

0. 循环链表的主要优点是(  )

A．不再需要头指针了
B．已知某个结点的位置后，能够容易找到它的直接前趋
C．在进行插入、删除运算时，能更好地保证链表不断开
D．从表中任一结点出发都能扫描到整个链表

1. 磁带适合存储的文件类型是(  )

A．索引文件
B．顺序文件
C．散列文件
D．多关键字文件

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

A．顺序查找
B．二分查找
C．二叉排序树
D．B-树上的查找

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

A．归并排序
B．插入排序
C．快速排序
D．选择排序

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

A．N(N-1)/2
B．N(N-1)
C．N(N+1)
D．N(N+1)/2

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

A．s—＞next=p—＞next;p—＞next=s;
B．q—＞next=s;s—＞next=p;
C．p—＞next=s—＞next;s—＞next=p;
D．p—＞next=s;s—＞next=q;

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

A．5,4,3,2,1
B．4,5,1,2,3
C．1,2,3,4,5
D．不确定

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

A．它们的逻辑结构不一样
B．施加在其上的操作不同
C．所包含的数据元素的类型不一样
D．存储实现不一样

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

A．每个结点所代表的数据元素都一样
B．每个结点所代表的数据元素包含的数据项的个数要相等
C．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
D．结点所代表的数据元素有同一特点

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

A．p—＞next=NULL
B．p=NULL
C．p—＞next=head
D．p=head

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

A．直接插入排序和快速排序
B．快速排序和归并排序
C．直接选择排序和归并排序
D．直接插入排序和归并排序

11. 下面关于线性表的叙述错误的是(  )

A．线性表采用顺序存储，必须占用一片连续的存储单元
B．线性表采用顺序存储，便于进行插入和删除操作
C．线性表采用链接存储，不必占用一片连续的存储单元
D．线性袁采用链接存储，不便于插入和删除操作

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

A．4
B．5
C．6
D．18

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

A．n²
B．n·lonaⁿ
C．log2ⁿ
D．n-1

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

A．顺序结构和散列结构
B．散列结构和链式结构
C．线性结构和非线性结构
D．顺序存储结构和链式结构

二、2.填空题

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

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

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

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

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

5. 数组的长度是______，线性表的长度是______。

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

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

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

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

三、3.解答题

1.设有多项式
  A(x)=7+3x+9x⁸+5x¹⁷
  B(x)=8x+22x⁷一9x⁸

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

2.
用单链表给出B(x)的存储表示。

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

4. 假设一个循环队列的容量为50，对其进行人队和出队操作，则经过一段时间之后，有：
  (1)front=35，rear=12；
  (2)front=12，rear=35。
  其中front和rear分别是队头和队尾指针。
  求：循环队列中元素的个数?

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

6. 请画出二叉树的五种基本形态。

四、4.算法阅读题

0. 以下运算实现在循环队上取队头，请在______处用适当的语句予以填充。
  int GetHead(CycqueueTp sq,DataType*x)
    { if(sq.rear==______return(0);
      else{*x=sq.data[______];
        return(1);
        }
    }

1. 以下是图的广度优先搜索算法，请在______处填充适当的语句。
  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);
   }
   ______;
   }
  }
  }

2. 以下为单链表的定位运算，分析算法，请在______处填上正确的语句。
  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);
   }

3. 下列算法用于判断带头结点的循环双链表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);
  }

五、5.算法设计题

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