全国2008年10月高等教育自学考试数据结构试题
课程代码:02331

一、单项选择题(本大题共15小题,每小题2分,共30分)
在每小题列出的四个备选项中只有一个是最符合题目要求的,请将其代码填写在题后的括号内.错选、多选或未选均无分.
1.如果在数据结构中每个数据元素只可能有一个直接前驱,但可以有多个直接后继,则该结构是（　　）
A. 栈
B. 队列
C. 树
D. 图

2.下面程序段的时间复杂度为（　　）
for (i=0; ifor (j=0; jA[i][j]=i*j;
A. O (m2)
B. O (n2)
C. O (m*n)
D. O (m+n)

3.在头指针为head的非空单循环链表中,指针p指向尾结点,下列关系成立的是（　　）
A. p->next==head
B. p->next->next==head
C. p->next==NULL
D. p==head

4.若以S和X分别表示进栈和退栈操作,则对初始状态为空的栈可以进行的栈操作系列是（　　）
A. SXSSXXXX
B. SXXSXSSX
C. SXSXXSSX
D. SSSXXSXX

5.两个字符串相等的条件是（　　）
A. 串的长度相等
B. 含有相同的字符集
C. 都是非空串
D. 串的长度相等且对应的字符相同

6.如果将矩阵An×n的每一列看成一个子表,整个矩阵看成是一个广义表L,即L=((a11,a21,…,an1),( a12,a22,…,an2),…,（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素,则求得a21的运算是（　　）
A. head (tail (head (L)))
B. head (head(head(L)))
C. tail (head (tail (L)))
D. head (head (tail (L)))

7.已知一棵含50个结点的二叉树中只有一个叶子结点,则该树中度为1的结点个数为（　　）
A. 0
B. 1
C. 48
D. 49

8.在一个具有n个顶点的有向图中,所有顶点的出度之和为Dout ,则所有顶点的入度之和为（　　）
A. Dout
B. Dout-1
C. Dout+1
D. n

9.如图所示的有向无环图可以得到的拓扑序列的个数是（　　）

A. 3
B. 4
C. 5
D. 6

10.如图所示的带权无向图的最小生成树的权为（　　）

A. 51
B. 52
C. 54
D. 56

11.对长度为n的关键字序列进行堆排序的空间复杂度为（　　）
A. O（log2n）
B. O（1）
C. O（n）
D. O（n*log2n）

12.已知用某种排序方法对关键字序列（51,35,93,24,13,68,56,42,77）进行排序时,前两趟排序的结果为
（35,51,24,13,68,56,42,77,93）
（35,24,13,51,56,42,68,77,93）
所采用的排序方法是（　　）
A. 插入排序
B. 冒泡排序
C. 快速排序
D. 归并排序

13.已知散列表的存储空间为T[0..18],散列函数H（key）=key,并用二次探测法处理冲突.散列表中已插入下列关键字:T[5]=39,T[6]=57和T[7]=7,则下一个关键字23插入的位置是（　　）
A. T[2]
B. T[4]
C. T[8]
D. T[10]

14.适宜进行批量处理的文件类型是（　　）
A. 顺序文件
B. 索引顺序文件
C. 散列文件
D. 多关键字文件

15.VSAM文件的索引结构为（　　）
A. B+树
B. 二叉排序树
C. B-树
D. 最优二叉树

二、填空题(本大题共10小题,每小题2分,共20分)
请在每小题的空格中填上正确答案.错填、不填均无分.
16.如果某算法对于规模为n的问题的时间耗费为T（n）=3n3,在一台计算机上运行时间为t秒,则在另一台运行速度是其64倍的机器上,用同样的时间能解决的问题规模是原问题规模的                    倍.
17.将两个长度分别为m和n的递增有序单链表,归并成一个按元素递减有序的单链表,可能达到的最好的时间复杂度是                    .
18.已知循环队列的存储空间大小为m,队头指针front指向队头元素,队尾指针rear指向队尾元素的下一个位置,则在队列不满的情况下,队列的长度是                    .
19.字符串"sgabacbadfgbacst" 中存在有个                    与字符串"ba"相同的子串.
20.假设以列优先顺序存储二维数组A[5][8],其中元素A[0][0]的存储地址为LOC（a00）,且每个元素占4个存储单元,则数组元素A[i][j]的存储地址为                    .
21.假设用表示树的边（其中x是y的双亲）,已知一棵树的边集为{,,,,,},该树的度是                    .
22.n个顶点且含有环路的无向连通图中,至少含有                    条边.
23.在一般情况下用直接插入排序、选择排序和冒泡排序的过程中,所需记录交换次数最少的是                    .
24.和二分查找相比,顺序查找的优点是除了不要求表中数据元素有序之外,对                    结构也无特殊要求.
25.顺序文件中记录存放的物理顺序和                    顺序一致.

三、解答题(本大题共4小题,每小题5分,共20分)
26.由森林转换得到的对应二叉树如图所示,写出原森林中第三棵树的前序序列和后序序列. 
 

前序序列:
后序序列:
27.图的邻接表的类型定义如下所示:
#define MaxVertexNum 50
typedef struct node {
　　int adjvex;
　　struct node *next;
　　}EdgeNode;
typedef struct {
　　VertexType vertex;
　　EdgeNode *firstedge;
　　}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];
typedef struct {
　　AdjList adjlist;
　　int n, e;
　　}ALGraph;
为便于删除和插入图的顶点的操作,可将邻接表的表头向量定义为链式结构,两种定义的存储表示实例如下图所示,请写出重新定义的类型说明. 
 

28.某类物品的编号由一个大写英文字母及2位数字（0..9）组成,形如E32.运用基数排序对下列物品编号序列进行按字典序

[1]