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

一、1.单项选择题

0. 索引顺序文件的记录，在逻辑上按关键字顺序排列，但物理上不一定按关键字顺序存储，故需要建立一张指示逻辑记录和物理记录之间一一对应关系的(  )

A．索引表
B．链接表
C．符号表
D．交叉访问题

1. 在循环双链表的p所指结点之后插入s所指结点的操作是(  )

A．P—＞next=s；
B．p—＞next=s； s—＞prior=p； p—＞next—＞prior=s； p—＞next—＞prior=s； s—＞prior=p； s—＞next=p—＞next； s—＞next=p—＞next
C．s—＞prior=p；
D．s—＞prior=p； s—＞next=p—＞next； s—＞next=p—＞next； p—＞next=s； p—＞next—＞prior=s； p—＞next—＞prior=s； p—＞next=s；

2. 在下面的程序中，语句S的执行次数为(  )
  for(i=1;i＜=n-1;i++)
    {for(j=n;j＞=i;j--)
    {S;
     }

3. 设矩阵A(aij,1≤i,j≤i0)的元素满足：  aij≠0(i≥j,1≤i,j≤10)  aij=O(i＜j,1≤i,j≤10)  现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占4个单元，则元素[9,5]的首地址为(  )

A．2160
B．2164
C．2336
D．2340

4. 循环队列用数组A[0…m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是(  )

A．(rear-front+m)MODm
B．rear-fomt+1
C．rear-fribt-1
D．rear-front

5. 如果要求一个线性表适应动态变化的要求，又必须能尽快地进行查找，则可以选择采用(  )查找方法。

A．分块
B．二分
C．顺序
D．散列

6. 具有12个记录的序列，采用冒泡排序最少的比较次数是(  )

A．1
B．144
C．11
D．66

7. 若用冒泡排序法对序列18,14,6,27,8,12,16,52,10,26,47,29,41,24从小到大进行排序，共要进行(  )次比较。

A．33
B．45
C．70
D．91

8. 若已知一个栈的输入序列为1,2,3…,n，其输出序列为P₁，P₂，…，P_n。若P₁=n，则P₁为(  )

A．i
B．n=i
C．n-i+l
D．不确定

9. 用数组A[0..N-1]存放循环队列的元素值，若其头尾指针分别为front和rear，则循环队列中当前元素的个数为(  )

A．(rear-front+m)mod m
B．(rear-front+1)mod m
C．(rear-front-1+m)mod m
D．(rear-front)mod m

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

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

11. 设栈S和队列Q的初始状态为空，元素e₁、e₂、e₃、e₄、e₅和e₆依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序是e₂、e₃、e₄、e₅、e₆、e₁，则栈S的容量至少应该是(  )

A．6
B．4
C．3
D．2

12. 在一棵二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序(  )

A．都不相同
B．完全相同
C．先序和中序相同，而与后序不同
D．中序和后序相同，而与先序不同

13. 在一棵具有5层的满二叉树中，结点总数为(  )个。

A．33
B．32
C．31
D．30

14. 索化二叉树中，结点T↑没有左子树的充要条件是(  )

A．↑Lchild=NIL
B．↑Ltag=1
C．↑Ltag=1且T↑Lchils=NIL
D．均不对

二、2.填空题

0. 已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
(1)删除P结点的语句序列是______；
(2)删除尾元结点的语句是______。
  a P—＞next=P—＞next—＞next  b P=P—＞next—＞next
  c while(P—＞next!=Q)P=P—＞next
  d while(P—＞next!—＞next!=Q)P=P—＞next
  e while(P—＞next!—＞next!=NULL)P=P—＞next
  f Q=P   g Q=P—＞next
  h P=L   i L=L—＞next
  j free(Q)

1. 严格地讲，二维数组不是一种线性表，但数组可以看成是线性表在下述含义上的扩展：二维数组的数据元素是______的线性表。

2. 记录的______结构是数据在物理存储器上的存储方式。

3. 有m个叶子结点(又称外结点)的哈夫曼树，其结点总数是______。

4. 在B—树上进行删除操作分为两个步骤，即：______和______。

5. 树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和______。

6. 在图的邻接表表示中，每个顶点邻接表中的顶点数，对于有向图来说是______，对于无向图来说是______。

7. VSAM文件既可以在______中进行顺序存取，又可以从最高层的索引出发，进行按钮______的随机存取。

8. 查找表中主关键字指的是______，次关键字指的是______。

9. 若一棵二叉树中只有叶结点和左、右子树皆非空的结点，设叶结点的个数为1，则左右子树皆非空的结点个数为______。

三、3.解答题

0. 试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同的形态。

1. 已知串S=‘(xyz)*’，t=‘(x+z)*y’，试利用串的基本运算将s串转化为t串，t串转化为s串。

3.多项式A(x)=a_nXⁿ+a_n-1X^n-1+…+a₁X+a₀的线性表表示法有下列两种可能的形式：
  A=(n,a_n,a_n-1，…，a₁，a₀)
  A=(m，1_m-1，b_m-1，1_m-2，b_m-2，…，1₀，b₀)
  其中：m为非零项的个数，1_i，b_i分别为非零项的指数和系数。试分析：

两种表示方法对存储空间的需要情况；

4.
进行多项式相加，采用哪一种表示方法处理较为简单?

5. 假设有一个容量为5的队列，假设其初始状态为front=rear=0，则对此队列进行下列操作之后，请画出此时的头、尾指针的变化情况和相应的队列内元素的存储情况。
  (1)队列为空(即没有任何元素进入)；
  (2)A，B，C入队；
  (3)A出队；
  (4)B，C出队，此时队列为空。

四、4.算法阅读题

0. 以下运算实现在循环队上判队空，请在______处用适当的语句予以填充。
  int EmptyCycQueue(CycqcleueTp sq)
    { if(______)retum(1);
     else return(0);
    }

1. 以下算法在有序表R中用二分查找法查找键值等于K的元素，请分析程序，并在______上填充合适的语句。
  int binsearch(sqtable R,keytype K)
  { low=l;hig=R.n;/*置查找区间初值。low，hig分别标记查找区间的下、上界*/
    while(low＜=hig)
    { mid=(low+hig)/2;
     switch
      { case K==R.item[i].key:return(mid);  /*找到，返回位置mid*/
       case K＜R.item[i].key:______.break;/*缩小区间*/
       case K＞R.item[i].key:______;break/*缩小区间*/
      }
    }
   return(0); /*若区间长度已为0但仍不成功，则返回0，表示查找不成功*/
  }

2. 以下运算实现在链栈上的退栈，请在______处用适当的语句予以填充。
  int Pop(LStackTp*is,DataType*x)
   { LStackTp*P;
    if(1s!=NULL)
      { p=ls;
        *x=______;
        ls=ls—＞next;
        ______;
        return(1);
       } else return(0);
  }

3. 分析下面程序段的时间复杂度______。
  j=1;
   while(j＜=n)
  {j=j*2;
  }

五、5.算法设计题

0. 设计一个用链表表示的直接选择排序算法。