全国2011年10月自考数据结构导论试题（课程代码02142）

一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，元素退栈后即进入队列Q，若6个元素的出队序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少为(      )
A.2                                    B.3
C.4                                    D.6
2.设计一个判别表达式中左右括号是否配对出现的算法，采用的最佳数据结构为(      )
A.线性表的顺序存储结构                 B.队列
C.线性表的链式存储结构                 D.栈
3.下列程序段的时间复杂度为(      )
    i=0；s=0；
    while（s<n）
      {i++；
       s=s+i；
      }
A.O（）                             B.O(log₂n)
C.O(n)                                 D.O(n²)
4.设A是n×n的对称矩阵，将A的对角线及对角线上方的元素A_ij(1≤i,j≤n,i≤j)以列优先顺序存放在一维数组元素B［1］至B［n(n+1)/2］中，则元素A_ij(i≤j)在B中的位置为(      )
A.i(i-l)/2+j                           B.j(j-l)/2+i
C.j(j-l)/2+i-1                         D.i(i-l)/2+j-1
5.在有向图G的拓扑序列中，若顶点V_i在顶点V_j之前，则下列情形不可能出现的是(      )
A.G中有弧<V_i，V_j>                       B.G中有一条从V_i到V_j的路径
C.G中没有弧<V_i，V_j>                     D.G中有一条从V_j到V_i的路径
6.下列序列中，由第一趟快速排序可得到的序列（排序的关键字类型是字符串）是(      )
A.［da，ax，eb，de，bb］ff［ha，gc］   B.［cd，eb，ax，da］ff［ha，gc，bb］
C.［gc，ax，eb，cd，bb］ff［da，ha］   D.［ax，bb，cd，da］ff［eb，gc，ha］
7.不稳定的排序方法是(      )
A.直接插入排序                         B.冒泡排序
C.堆排序                               D.二路归并排序
8.设散列表表长m=14，散列函数为h（k）=k%11，表中已有4个记录，如果用二次探测法处理冲突，关键字为49的记录的存储位置是(      )
       0    1    2    3    4   5    6    7    8    9   10   11   12   13

15

38

61

84

A.3                                    B.5
C.8                                    D.9
9.若元素1，2，3依次进栈，则退栈不可能出现的次序是(      )
A.3，2，1                              B.2，1，3
C.3，1，2                              D.1，3，2
10.直接插入排序的时间复杂度是(      )
A.O（n²）                               B.O（nlog₂n）
C.O（n）                               D.O（log₂n）
11.稀疏矩阵是指(      )
A.元素少的矩阵                         B.有少量零元素的矩阵
C.有少量非零元素的矩阵                 D.行数、列数很少的矩阵
12.深度为k（k≥1）的二叉树，结点数最多有(      )
A.2^k                                    B.2^k-1
C.2^k-1                                  D.2^k-1-1
13.由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为(      )
A.23                                   B.37
C.44                                   D.46
14.有n个顶点的有向完全图的弧数为(      )
A.n²                                    B.2n
C.n（n-1）                             D.2n（n+1）
15.图的深度优先搜索类似于二叉树的(      )
A.先根遍历                             B.中根遍历
C.后根遍历                             D.层次遍历
二、填空题(本大题共13小题，每小题2分，共26分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16.下列程序段的时间复杂度为_________。
for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
        x++;
17.数据结构中结点按逻辑关系依次排列形成一条“锁链”的结构是_________。
18.在表长为n的顺序表上做删除运算，平均要移动的结点个数为_________。
19.在带有头结点的单循环链表head中，指针p所指结点为尾结点的条件是_________。
20.队列又称为_________的线性表。
21.顺序栈被定义为结构类型，含有两个域：data和top，则对栈*sq进行初始化的操作是_________。
22.对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n₂，则n₂=_________。
23.一棵具有n个结点的二叉树，采用二叉链表存储，则二叉链表中指向孩子结点的指针有_________个。
24.若连通图G的顶点个数为n，则图G的生成树的边数为_________。
25.一个具有n个顶点的无向图的边数最多为_________。
26.中根遍历二叉排序树所得到的结点访问序列是键值的_________序列。
27.冒泡排序的平均时间复杂度为_________。
28.将序列{60，20，23，68，94，70，73}建成堆，则只需把20与_________互相交换。
三、应用题(本大题共5小题，每小题6分，共30分)
29.如题29图所示，在栈的输入端元素的输入顺序为A，B，C，D，进栈过程中可以退栈，写出在栈的输出端以A开头和以B开头的所有输出序列。

                                                    题29图
30.一棵二叉树如题30图所示，写出该二叉树的先根遍历序列、中根遍历序列和后根遍历序列。

                                           题30图
31.将题31图所示的一棵二叉树转换成森林。

                                         题31图
32.对于有向无环图：
（1）叙述求拓扑排序算法的基本步骤；
（2）对于题32图，写出它的4个不同的拓扑排序序列。

                                         题32图
33.判别以下序列是否为堆。如果不是，则把它调整为堆。
（1）（100，86，48，73，35，39，42，57，66，21）；
（2）（12，70，33，65，24，56，48，92，86，33）。
四、算法设计题(本大题共2小题，每小题7分，共14分)
34.n个结点的完全二叉树按结点编号将值顺序存放在一维数组元素A［1］至A［n］中，试编写算法实现将顺序存储结构转换为二叉链表存储结构，其中根结点由tree指向。
35.试写出冒泡排序算法。
下载试题WORD文档：

全国2011年10月自考数据结构导论试题（课程代码02142）