你的位置：
首页
>
IT圈
>
2022年重庆理工大学考研真题809数据结构(A卷)
2024年3月19日发(作者：盘以丹)
重庆理工大学2022年硕士研究生招生考试试题
学院名称：计算机科学与工程学院、重庆两江人工智能学院
学科、专业名称：计算机科学与技术、人工智能、电子信息（计算机技术）、电
子信息（人工智能）
考试科目（代码）：数据结构809（A卷）（试题共3页）
注意：1.所有试题的答案均写在专用的答题纸上，写在试题纸上一律无效。
2.试题与答卷一并随原信封交回。
注意：编程实现题，可以使用C语言及Java语言，直接调用API不得分。
1.（10分）分析以下算法的时间复杂度。
voidfun(intn){
inti=1;
while(i<=n){
i=i+2;
}
}
2.（15分）已知一个顺序表L，其中的元素递增有序排列，完成函数void
insert(SqList*L,intx)，实现插入一个元素x后保持该顺序表仍为递增有序排
列的功能。假定，插入后不会越界。
顺序表定义如下：
typedefstruct{
intdata[100];
intlength;//顺序表长度
}SqList;
3.（15分）有以下递归函数：
voidfun(intn){
if(n==1)
printf(“A:%dn”,n);
else{
printf(“B:%dn”,n);
第1页
fun(n-1);
printf(“C:%dn”,n);
}
}
分析调用fun(4)的输出结果。
4.（15分）设二叉树的存储结构如表所示。
1
left
data
right
0
j
0
2
0
h
0
3
2
f
0
4
3
d
9
5
7
b
4
6
5
a
0
7
8
c
0
8
0
e
0
9
10
g
0
10
1
i
0
left，right分别为结点的左、右孩子指针域，data为结点的数据域。
（1）（5分）画出该二叉树。
（2）（5分）写出按中序和后序遍历该二叉树所得到的结点序列。
（3）（5分）将该二叉树转换为树或森林。
5.（15分）假定一段文字中字母A，E，I，O，U出现的频率分别为7,16，8,13,14，
画出相应的哈夫曼树（保证频率小的在左），写出各字母相应的哈夫曼编码，计算带
权路径长度WPL。
6.（15分）针对如下有向图，完成
（1）（7分）写出该图的邻接矩阵。
（2）（8分）给出从A点出发的深度优先搜索序列。
第2页
2024年3月19日发(作者：盘以丹)
重庆理工大学2022年硕士研究生招生考试试题
学院名称：计算机科学与工程学院、重庆两江人工智能学院
学科、专业名称：计算机科学与技术、人工智能、电子信息（计算机技术）、电
子信息（人工智能）
考试科目（代码）：数据结构809（A卷）（试题共3页）
注意：1.所有试题的答案均写在专用的答题纸上，写在试题纸上一律无效。
2.试题与答卷一并随原信封交回。
注意：编程实现题，可以使用C语言及Java语言，直接调用API不得分。
1.（10分）分析以下算法的时间复杂度。
voidfun(intn){
inti=1;
while(i<=n){
i=i+2;
}
}
2.（15分）已知一个顺序表L，其中的元素递增有序排列，完成函数void
insert(SqList*L,intx)，实现插入一个元素x后保持该顺序表仍为递增有序排
列的功能。假定，插入后不会越界。
顺序表定义如下：
typedefstruct{
intdata[100];
intlength;//顺序表长度
}SqList;
3.（15分）有以下递归函数：
voidfun(intn){
if(n==1)
printf(“A:%dn”,n);
else{
printf(“B:%dn”,n);
第1页
fun(n-1);
printf(“C:%dn”,n);
}
}
分析调用fun(4)的输出结果。
4.（15分）设二叉树的存储结构如表所示。
1
left
data
right
0
j
0
2
0
h
0
3
2
f
0
4
3
d
9
5
7
b
4
6
5
a
0
7
8
c
0
8
0
e
0
9
10
g
0
10
1
i
0
left，right分别为结点的左、右孩子指针域，data为结点的数据域。
（1）（5分）画出该二叉树。
（2）（5分）写出按中序和后序遍历该二叉树所得到的结点序列。
（3）（5分）将该二叉树转换为树或森林。
5.（15分）假定一段文字中字母A，E，I，O，U出现的频率分别为7,16，8,13,14，
画出相应的哈夫曼树（保证频率小的在左），写出各字母相应的哈夫曼编码，计算带
权路径长度WPL。
6.（15分）针对如下有向图，完成
（1）（7分）写出该图的邻接矩阵。
（2）（8分）给出从A点出发的深度优先搜索序列。
第2页