数据结构222301-a卷

二三总分—•123456789标准分244828100A BC D#E##F得分

3、设哈希表的地址范围为0〜12,哈希函数为H key=key%llo用线性探测法处理冲突，输入关键字序列12,66,18,45,21,85,75,30,54,48,77,构造哈希表，试回答注答案一律填写在答题纸上，写在试卷上无效下列问题

一、填空题每小题分，小题，共分3824

①画出哈希表的示意图；点较

1、假设对称阵A

[10]

[10]采用下三角行优先压缩存储，每个元素占用2个字节，

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

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

[8]的地址是1000,则A⑼⑼的地址是o

4、已知一个文件中仅由8个字符｛A,B,C,D,E,F,G,H｝组成，各字符出现的次数分

2、下面程序段的时间复杂度为o别为｛3,4,5,6,10,15,22,25｝试为8个字母构造一棵哈夫曼树注意左小右大，左for i=0;in;i++右1,设计出哈夫曼编码for j=0;jm;j++

5、已知链式存储结构队列的定义如下a[i][j]=0;typedef struct｛

3、带头结点的单链表L,判定该单链表非空的条件oQNode*front;〃队头

4、SubSlringS,i,k是求S中从第i个字符开始的连续k个字符组成的子串操作,则对QNode*rear;//队尾于S=,BeijingNanjing,,SubString S,4,5=[LinkQueue;

5、GetHcad GctTaila,b,c,d,e,f=根据队列的操作特性，请回答下列问题

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

①画出队列的初始状态，并给出判断队空的条件队列中的元素个数为

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

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

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

①写出构造过程；

8、假设初始查找关键词序列“

16、

18、

10、

8、12”，其构造的二叉排序树的后序遍历

②计算最小代价值结果是

二、应用题每小题分，小题，共计分

86481、待排序关键字序列28,39,10,65,14,61,17,50,21,写出希尔排序d=5,d=3,d=l的排序过程

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

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

②写出此二叉树的先序遍历和后序遍历int length;JSSTable;〃静态顺序表函数形式如为int Search_BinSSTable ST,KcyTypc key

3、已知顺序表的存储结构如下假设只存储整数，最多只存储10个元素请设计完成线性表初始分配空间，然后根据提示录入n个元素，再对有n个元素的顺序表完成翻转操作，例如存储的是“

2、

8、3”，翻转后为“

3、

8、2”typedef struct{int*elem;//存储空间基址int length;〃当前使用量int listsize;〃存储容量

三、编程题、题分，题分，共计分12931028jSqList;

1、已知二叉树的存储结构为函数形式为void ReverseListSqListLtypedef struct BiTNode{intdata;〃结点数据structBiTNode*lchild,*rchild;〃左右孩子指针产BiTree;设计完成算法CountNodeSum,统计二叉树T中结点数据域值大于20的结点，要求打印满足条件结点的值并对这些结点求和int sum=;函数形式如为void CountNodeSumBiTreeT

2、已知顺序表存储结构如下假设己经完成线性表初始分配空间，然后根据提示录入n个元素，且这n个元素是升序排列请设计完成采用折半查找算法对关键字key的查找，如果找到则返元素在表中的位置，否则返回0typedef structint*elem;〃指向数据元素基址，号不存元素二三总分—•标准分244828100第4题:得分答题纸

1、

2、

3、

4、

5、

6、第5题:7

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

二、应用题（每小题8分，6小题，共48分）第1题:第6题:第2题:

三、编程题（

1、2题9分，3题10分，共计28分，答案写在答题纸背面）第3题:。