⾃考数据结构历试题及答案个⼈
⾃考数据结构02331历年试题及答案(2009--2015个⼈整理版)
全国2009年1⽉⾃学考试数据结构试题
⼀、单项选择题(本⼤题共15⼩题，每⼩题2分，共30分)
在每⼩题列出的四个备选项中只有⼀个是符合题⽬要求的，请将其代码填写在题后的括号内。错选、多选或未选均⽆分。1.下列程序段的时间复杂度为( )9
s=0；
for(i=1；i
for(j=1；j
s+=i*j ；
A.O(1)
B.O(n)
C.O(2n)
D.O(n 2)
2.假设某个带头结点的单链表的头指针为head ，则判定该表为空表的条件是( )22
A.head==NULL ；
B.head->next==NULL ；
C.head!=NULL ；
D.head->next==head ；
3.栈是⼀种操作受限的线性结构，其操作的主要特征是( )32
A.先进先出
B.后进先出
C.进优于出
D.出优于进
4.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front 和rear 。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前⼀个位置，则当前存于队列中的元素个数为( )
A.(rear-front-1)％n云南省公务员局入口
B.(rear-front)％n
C.(front-rear+1)％n
D.(rear-front+n)％n
5.判断两个串⼤⼩的基本准则是( )52
A.两个串长度的⼤⼩
B.两个串中⾸字符的⼤⼩
C.两个串中⼤写字母的多少
D.对应的第⼀个不等字符的⼤⼩
6.⼆维数组A[4][5]按⾏优先顺序存储，若每个元素占2个存储单元，且第⼀个元素A[0][0]的存储地址为1000，则数组元素A[3]
[2]的存储地址为( )60
A.1012
B.1017
C.1034
D.1036
7.⾼度为5的完全⼆叉树中含有的结点数⾄少为( )72
A.16
山东省公务员面试名单2022
B.17
C.31
D.32
8.已知在⼀棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶⼦结点数为( )
A.5
B.8
C.11
高级职称考试2022年报名条件D.18
9.下列所⽰各图中是中序线索化⼆叉树的是( A
)81A
山东公务员公示
10.已知含6个顶点(v 0，v 1，v 2，v 3，v 4，v 5)的⽆向图的邻接矩阵如图所⽰，则从顶点v 0出发进⾏深度优先遍历可能得到的顶点访问序列为( )108
A.(v 0，v 1，v 2，v 5，v 4，v 3)
B.(v 0，v 1，v 2，v 3，v 4，v 5)
C.(v 0，v 1，v 5，v 2，v 3，v 4)
D.(v 0，v 1，v 4，v 5，v 2，v 3)
11.如图所⽰有向图的⼀个拓扑序列是( )
A.ABCDEF
B.FCBEAD
C.FEDCBA
D.DAEBCF
12.下列关键字序列中，构成⼤根堆的是( )
A.5，8，1，3，9，6，2，7
B.9，8，1，7，5，6，2，33
C.9，8，6，3，5，l ，2，7
D.9，8，6，7，5，1，2，3
13.对长度为15的有序顺序表进⾏⼆分查，在各记录的查概率均相等的情况下，查成功时所需进⾏的关键字⽐较次数的平均值为( )172 A.1539 B.15
49 C.
1551 D.15
55 14.已知⼀个散列表如图所⽰，其散列函数为H(key)=key ％11，采⽤⼆次探查法处理冲突，则下⼀个插⼊的关键字49的地址为( D )d 197
桂聘人才网招聘网15.数据库⽂件是由⼤量带有结构的( )206
A.记录组成的集合
安徽省会计从业资格考试报名B.字符组成的集合
C.数据项组成的集合
D.数据结构组成的集合
⼆、填空题(本⼤题共10⼩题，每⼩题2分，共20分)
请在每⼩题的空格中填上正确答案。错填、不填均⽆分。
16.估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的____输⼊量_____。 8
17.在双向循环链表中插⼊⼀个新的结点时，应修改_____4____个指针域．．．的值。 28 18.若进栈序列为a ，b ，c ，且进栈和出栈可以穿插进⾏，则可能出现___5______个不同的出栈序列。5
19.链串的结点⼤⼩定义为结点的_____数据域____中存放的字符个数。 54
20.⼴义表(a ，(d ，(c)))的深度为___3 ______。67
21.在含有3个结点a ，b ，c 的⼆叉树中，前序序列为abc 且后序序列为cba 的⼆叉树有____4_____棵。4
22.若⽤邻接矩阵表⽰有向图，则顶点i 的⼊度等于矩阵中_________。第i 列⾮零元素的个数107
23.对关键字序列(15，18，11，13，19，16，12，17，10，8)进⾏增量为5的⼀趟希尔排序的结果为_________。
15，12，11，10，8，16，18，17
24.索引顺序查的索引表由各分块中的最⼤关键字及各分块的_____起始位置____构成。173
25.VSAM ⽂件的实现依赖于操作系统中的_____分页____存取⽅法的功能。 215
三、解答题(本⼤题共4⼩题，每⼩题5分，共20分)
26.假设有⼀个形如
的8×8矩阵，矩阵元素都是整型量(次对⾓线以上的元素都是0)。
若将上述矩阵中次对⾓线及其以下的元素按⾏优先压缩存储在⼀维数组B 中，请回答下列问题：
(1)B 数组的体积⾄少是多少?
(2)若a 18存储在B[0]中，a 56存储在B[k]中，则k 值为多少?
(1) （1+8）*8/2=36 存放次对⾓线以上的零为37
(2) 12
27.对关键字序列(5，8，1，3，9，6，2，7)按从⼩到⼤进⾏快速排序。
(1)写出排序过程中前两趟的划分结果；
(2)快速排序是否是稳定的排序⽅法? (1)
第⼀趟划分结果；(2，3，1)，5，(9，6，8，7)
第⼆趟划分结果；(1，2，3)，5，(9，6，8，7)
第三趟划分结果；(1，2，3)，5，(7，6，8，9)
第四趟划分结果； 1，2，3，5，6，7，8，9
第⼀趟划分过程
(5，8，1，3，9，6，2，7)
1．(2，8，1，3，9，6，5，7)
2．(2，5，1，3，9，6，8，7)
3．(2，3，1，5，9，6，8，7)
4．(2，3，1，5，9，6，8，7)
第⼆趟划分过程
(2，3，1，5，9，6，8，7)
1．(1，2，3，5，7，6，8，9)
(2)⾮稳定
↑i ↑j
第⼆趟： 1，2，3，5 （9，6，8，7）
第三趟：1，2，3，5，（7，6，8），9
第四趟：1，2，3，5，6，7，8，9
28.假设通信电⽂使⽤的字符集为{a，b，c，d，e，f，g，h}，各字符在电⽂中出现的频度分别为：7，26，2，28，13，10，3，11，试为这8个字符设计哈夫曼编码。要求：
(1)画出你所构造的哈夫曼树(要求树中左孩⼦结点的权值不⼤于右孩⼦结点的权值)；
(2)按左分⽀为0和右分⽀为1的规则，分别写出与每个字符对应的编码。
(1)
(2)
⾮根【1，2】P184
根【1，2】
(1)画出将关键字6插⼊之后的B—树；
(2)画出在(1)所得树中插⼊关键字2之后的B—树。
四、算法阅读题(本⼤题共4⼩题，每⼩题5分，共20分)
30.假设以带头结点的单链表表⽰线性表，单链表的类型定义如下：typedef int DataType;
typedef struct node {
DataType data;
struct node * next;
} LinkNode, * LinkList;
阅读下列算法，并回答问题：
(1)已知初始链表如图所⽰，画出执⾏f30(head)之后的链表；
题30图
(2)简述算法f30的功能。
void f30( LinkList head)
{ LinkList p,r, s;
if (head - > next) {
r = head - > next;
p = r->next;
r - > next = NULL;
while (p) {
s =p;
p = p->next;
if ( s - > data% 2 = = 0) {
s - > next = head - > next;
head - > next = s;
} else {
s - > next = r - > next;