数据结构222301-a试题卷.docx

2022～2023学年第一学期试卷课程名称：数据结构考试形式：闭卷试卷：A卷

第(PAGE3)页共(NUMPAGES3)页

专业班级：计算机学院202

专业班级：计算机学院2021级专业班级：学号：姓名：

装订线

一

二

三

总分

标准分

24

48

28

100

得分

注：答案一律填写在答题纸上，写在试卷上无效。

一、填空题（每小题3分，8小题，共24分）

1、假设对称阵A[10][10]采用下三角行优先压缩存储，每个元素占用2个字节，A[5][8]的地址是1000，则A[0][0]的地址是。

2、下面程序段的时间复杂度为。

for(i=0;in;i++)

for(j=0;jm;j++)

a[i][j]=0;

3、带头结点的单链表L，判定该单链表非空的条件。

4、SubString(S,i,k)是求S中从第i个字符开始的连续k个字符组成的子串操作,则对于S=’BeijingNanjing’，SubString(S,4,5)=。

5、GetHead（GetTail（a,b,c,d,e,f））=。

6、一个循环队列Q的储存空间大小为M，其头尾指针分别为front和rear，则当前循环队列中的元素个数为。

7、完全二叉树的结点总数200个，则这棵树的叶子有个。

8、假设初始查找关键词序列“16、18、10、8、12”，其构造的二叉排序树的后序遍历结果是。

应用题（每小题8分，6小题，共计48分）

1、待排序关键字序列（28，39，10，65，14，61，17，50，21），写出希尔排序d=5，d=3，d=1的排序过程。

2、已知一颗二叉树的顺序存储如下表，#表示空树，完成：

①画出图1二叉树的逻辑结构；

②写出此二叉树的先序遍历和后序遍历。

1

2

3

4

5

6

7

8

9

A

B

C

D

#

E

#

#

F

3、设哈希表的地址范围为0～12，哈希函数为：H（key）=key%11。用线性探测法处理冲突，输入关键字序列：（12，66，18，45，21，85，75，30，54，48，77），构造哈希表，试回答下列问题：

①画出哈希表的示意图；

②若查找关键字30，需要依次与哪些关键字进行比较？

③假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

4、已知一个文件中仅由8个字符{A，B，C，D，E，F，G，H}组成，各字符出现的次数分别为{3,4,5,6,10,15,22,25}。试为8个字母构造一棵哈夫曼树（注意：左小右大，左0右1），设计出哈夫曼编码。

5、已知链式存储结构队列的定义如下：

typedefstruct{

QNode*front;//队头

QNode*rear;//队尾

}LinkQueue;

根据队列的操作特性，请回答下列问题:

①画出队列的初始状态，并给出判断队空的条件。

②给出入队操作和出队操作的基本过程。

6、使用Kruskal算法构造出下图的最小生成树。要求完成：

①写出构造过程；

②计算最小代价值。

编程题（1、2题9分，3题10分，共计28分）

1、已知二叉树的存储结构为：

typedefstructBiTNode{

intdata; //结点数据

structBiTNode*lchild,*rchild;//左右孩子指针

}*BiTree;

设计完成算法CountNodeSum，统计二叉树T中结点数据域值大于20的结点，要求打印满足条件结点的值并对这些结点求和。

intsum=0;

函数形式如为：voidCountNodeSum(BiTreeT)

2、已知顺序表存储结构如下。假设已经完成线性表初始分配空间，然后根据提示录入n个元素，且这n个元素是升序排列。请设计完成：采用折半查找算法对关键字key的查找，如果找到则返元素在表中的位置，否则返回0。

typedefstruct

{

int*elem; //指向数据元素基址，0号不存元素

intlength;

}SSTable; //静态顺序表

函数形式如为：intSearch_Bin(SSTableST,KeyTypekey)

3、已知顺序表的