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

如果您发现本试卷没有包含本套题的全部小题，请尝试在页面顶部本站内搜索框搜索相关题目，一般都能找到。

35．设计一个用链表表示的直接选择排序算法。
点击查看答案
33．以下运算实现在链栈上的退栈，请在______处用适当的语句予以填充。
int Pop(LStackTp*is,DataType*x)
    { LStackTp*P;
      if(1s!=NULL)
           { p=ls;
              *x=______;
              ls=ls—＞next;
              ______;
              return(1);
            } else return(0);
  }
点击查看答案
34．分析下面程序段的时间复杂度______。
j=1;
while(j＜=n)
{j=j*2;
}
点击查看答案
30．假设有一个容量为5的队列，假设其初始状态为front=rear=0，则对此队列进行下列操作之后，请画出此时的头、尾指针的变化情况和相应的队列内元素的存储情况。 (1)队列为空(即没有任何元素进入)； (2)A，B，C入队； (3)A出队； (4)B，C出队，此时队列为空。
点击查看答案
31．以下运算实现在循环队上判队空，请在______处用适当的语句予以填充。
int EmptyCycQueue(CycqcleueTp sq)
       { if(______)retum(1);
         else return(0);
       }
点击查看答案
32．以下算法在有序表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，表示查找不成功*/
  }
点击查看答案
29．进行多项式相加，采用哪一种表示方法处理较为简单?
点击查看答案
多项式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分别为非零项的指数和系数。试分析：
两种表示方法对存储空间的需要情况；
点击查看答案
27．已知串S=‘(xyz)*’，t=‘(x+z)*y’，试利用串的基本运算将s串转化为t串，t串转化为s串。
点击查看答案
26．试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同的形态。
点击查看答案
24．查找表中主关键字指的是______，次关键字指的是______。
点击查看答案
23． VSAM文件既可以在______中进行顺序存取，又可以从最高层的索引出发，进行按钮______的随机存取。
点击查看答案
25．若一棵二叉树中只有叶结点和左、右子树皆非空的结点，设叶结点的个数为1，则左右子树皆非空的结点个数为______。
点击查看答案
21．树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和______。
点击查看答案
22．在图的邻接表表示中，每个顶点邻接表中的顶点数，对于有向图来说是______，对于无向图来说是______。
点击查看答案
18．记录的______结构是数据在物理存储器上的存储方式。
点击查看答案
19．有m个叶子结点(又称外结点)的哈夫曼树，其结点总数是______。
点击查看答案
20．在B—树上进行删除操作分为两个步骤，即：______和______。
点击查看答案
17．严格地讲，二维数组不是一种线性表，但数组可以看成是线性表在下述含义上的扩展：二维数组的数据元素是______的线性表。
点击查看答案
16．已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
(1)删除P结点的语句序列是______；
(2)删除尾元结点的语句是______。
  aP—＞next=P—＞next—＞next   b P=P—＞next—＞next
  cwhile(P—＞next!=Q)P=P—＞next
  dwhile(P—＞next!—＞next!=Q)P=P—＞next
  ewhile(P—＞next!—＞next!=NULL)P=P—＞next
  fQ=P     g Q=P—＞next
  hP=L     i L=L—＞next
  jfree(Q)
点击查看答案
14．在一棵具有5层的满二叉树中，结点总数为( )个。
- A．33
- B．32
- C．31
- D．30
点击查看答案
15．在线索化二叉树中，结点T↑没有左子树的充要条件是( )
- A．↑Lchild=NIL
- B．↑Ltag=1
- C．↑Ltag=1且T↑Lchils=NIL
- D．均不对
点击查看答案
13．在一棵二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序( )
- A．都不相同
- B．完全相同
- C．先序和中序相同，而与后序不同
- D．中序和后序相同，而与先序不同
点击查看答案
12．设栈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
点击查看答案
11．任何一个带权的无向连通图的最小生成树( )
- A．只有一棵
- B．有一棵或多棵
- C．一定有多棵
- D．可能不存在
点击查看答案
9．若已知一个栈的输入序列为1,2,3…,n，其输出序列为P₁，P₂，…，P_n。若P₁=n，则P₁为( )
- A．i
- B．n=i
- C．n-i+l
- D．不确定
点击查看答案
10．用数组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
点击查看答案
7．具有12个记录的序列，采用冒泡排序最少的比较次数是( )
- A．1
- B．144
- C．11
- D．66
点击查看答案
8．若用冒泡排序法对序列18,14,6,27,8,12,16,52,10,26,47,29,41,24从小到大进行排序，共要进行( )次比较。
- A．33
- B．45
- C．70
- D．91
点击查看答案
4．设矩阵A(a_ij,1≤i,j≤i0)的元素满足：
- a_ij≠0(i≥j,1≤i,j≤10)
- a_ij=O(i＜j,1≤i,j≤10) 现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占4个单元，则元素[9,5]的首地址为( )
- A.2160
- B.2164
- C.2336
- D.2340
点击查看答案
6．如果要求一个线性表适应动态变化的要求，又必须能尽快地进行查找，则可以选择采用( )查找方法。
- A．分块
- B．二分
- C．顺序
- D．散列
点击查看答案
5．循环队列用数组A[0…m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是( )
- A．(rear-front+m)MODm
- B．rear-fomt+1
- C．rear-fribt-1
- D．rear-front
点击查看答案
2．在循环双链表的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；
点击查看答案
3．在下面的程序中，语句S的执行次数为( )
for(i=1;i＜=n-1;i++)
{for(j=n;j＞=i;j--)
{S;
}
- A.A
- B.B
- C.C
- D.D
点击查看答案
1．索引顺序文件的记录，在逻辑上按关键字顺序排列，但物理上不一定按关键字顺序存储，故需要建立一张指示逻辑记录和物理记录之间一一对应关系的( )
- A．索引表
- B．链接表
- C．符号表
- D．交叉访问题
点击查看答案

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

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

33．以下运算实现在链栈上的退栈，请在处用适当的语句予以填充。
int Pop(LStackTpis,DataTypex)
    { LStackTpP;
      if(1s!=NULL)
           { p=ls;
              x=;
              ls=ls—＞next;
              __;
              return(1);
            } else return(0);
  }

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

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

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

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

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

24．查找表中主关键字指的是，次关键字指的是。

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

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

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

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

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

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

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

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

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

15．在线索化二叉树中，结点T↑没有左子树的充要条件是( )

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

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

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

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

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

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

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

4．设矩阵A(a_ij,1≤i,j≤i0)的元素满足：

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

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

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

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

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