全国自学考试数据结构真题
课程代码: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;
为便于删除和插入图的顶点的操作,可将邻接表的表头向量定义为链式结构,两种定义的存储表示实例如下图所示,请写出重新定义的类型说明.
