东软数据结构,树和二叉树复习题

树和二叉树：纸质作业

一、已知二叉树T逻辑结构如下图所示，请分别用顺序存储和二叉链表存储法表示此树。

二、将下面的森林F=﹛T1，T2，T3﹜转换为对应的二叉树，并写出相应二叉树的先根遍历序列。

三、将下列由三棵树组成的森林转换为二叉树，并写出相应二叉树的中根遍历序列

B A C D E F K H L G I J M N O P 四、已知树T的孩子链表存储结构如图所示，试画出此树逻辑结构，以及此树转换成的二叉树逻辑结构，并写出二叉树的后根遍历序列

五、设一棵二叉树的先序序列为：A B D F C E G H 中序遍历序列为： B F D A G E H C （1）画出这棵二叉树。

（2）将这棵二叉树转换成对应的树（或森林）。 六、给定集合{15,3,14,2,6,9,16,17}

（1）构造相应的huffman树（规定：二叉树中两个结点，权值小的结点居左） （2）计算它的带权路径长度

（3）写出它的huffman编码：（规定：左子树编码为0，右子树编码为1,左小右大） 七、假设通信电文使用的字符集为{a,b,c,d,e,f}，各字符在电文中出现的频度分别为：0.34，0.05，0.12，0.23，0.08，0.18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子节点的权值小于右孩子节点的权值，左分支表示字符“0”，右分支表示字符“1”)，然后分别写出每个字符对应的编码。

八、假定教室中有A、B、C、D、E五个设备，需编写一套指令集对五个设备进行自动开关控制，五个设备一天中的使用次数分别是7，5，2，4，9次。为使得指令集长度最短，请对五个设备进行编码，要求画出哈夫曼树，并写出五个设备所对应的哈夫曼编码。

九、假定用于通讯的电文仅有8个字母C1，C2，?，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码树，并写出8个字符的哈夫曼编码

十、A,B,C,D,E的权值为{3, 2, 4, 5, 1}，用此权值构造哈夫曼（Huffman）树，并求此哈夫曼（Huffman）树和各个字符的哈夫曼编码（左分支为0，右分支为1）

纸质作业2：排序

一、初始关键字序列如下：{49，38，65，97，76，13，27，49，55 04}，请写出它们的希尔排序的全过程(其中d=5,3,1）

二、给定的关键字序列21，22，27，78，40，05，47，69，12，99，要按升序排序，请写出采用冒泡排序法前3趟的结果，和用堆排序法选择出最大和次大关键字的结果（图）

三、已知某文件的记录关键字集为{50，10，75，40，45，85，80}，写出快速排序方法进行排序的前2次划分的结果

四、已知某文件的记录关键字集为{50，10，30，40，45，85，80}，要从小到大进行排序，请分别写出直接插入排序的前2趟结果和直接选择排序的前3趟结果。 五、设要将序列（17,8,3,25,16,1,13,19,18,4,6,24）中的关键字按升序重新排列，请给出对该序列进行冒泡排序的第一趟排序结果、及以第一个元素为枢轴的快速排序的第一次划分的结果。

纸质作业3：查找

一、设哈希（Hash）表的地址范围为0～13，哈希函数为：H（K）＝K MOD 13。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：

（23，24，32，4，31，30，46，47）造出Hash表，试回答下列问题： （1） 画出哈希表的示意图；

（2） 若查找关键字30，需要依次与哪些关键字进行比较？ （3） 若查找关键字14，需要依次与哪些关键字比较？ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

二、请用序列（45，24，53，12，37，93）建立一棵二叉排序树，画出该树，并求在等概率情况下，查找成功的平均查找长度。

三、选取哈希函数H(key)＝keyMod 11，用线性探测再散列开放定址法解决冲突。试在0～10的散列地址空间内对关键字序列?19、11、31、23、17、27、41、13、91、61?构造哈希表，并计算在等概率下成功查找的平均查找长度。

四、设有一组关键字{9,1,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的线性探测再散列方法解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

五、设哈希（Hash）表的地址范围为0～17，哈希函数为：H （K）=K MOD 16，K为关键字，用线性探测再散列法处理冲突，输入关键字序列：{10，24，32，17，31，30，46，47，40，63，49}造出哈希表，试回答下列问题：

（1）画出哈希表示意图；

（2）若查找关键字63，需要依次与哪些关键字比较? （3）若查找关键字60，需要依次与哪些关键字比较?

（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 六、对于序列：12，16，23，34，45，57，78，91，95，100，112进行二分法查找：

（1）画出二分查找判定树

（2）求出等概率情况下，该二分查找的ASL？

（3）查找元素95需要经过几次比较？和哪些元素比较？

（4）查找元素20需要经过几次比较确定找不到？和哪些元素比较？

七、已知如下所示长度为12的表(34,25,68,72,21,15,49,29,77,8,19,102)

（1）按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树

（2）并求其在等概率的情况下查找成功的平均查找长度。

`习题一参考答案

2．试述数据结构研究的3个方面的内容。 参考答案:

数据结构研究的3个方面分别是数据的逻辑结构、数据的存储结构和数据的运算（操作）。

3．试述集合、线性结构、树型结构和图型结构四种常用数据结构的特性。 参考答案:

集合结构：集合中数据元素之间除了“同属于一个集合”的特性外，数据元素之间无其它关系，它们之间的关系是松散性的。

线性结构：线性结构中数据元素之间存在“一对一”的关系。即若结构非空，则它有且仅有一个开始结点和终端结点，开始结点没有前趋但有一个后继，终端结点没有后继但有一个前趋，其余结点有且仅有一个前驱和一个后继。

树形结构：树形结构中数据元素之间存在“一对多”的关系。即若结构非空，则它有一个称为根的结点，此结点无前驱结点，其余结点有且仅有一个前驱，所有结点都可以有多个后继。

图形结构：图形结构中数据元素之间存在“多对多”的关系。即若结构非空，则在这种数据结构中任何结点都可能有多个前驱和后继。

4．设有数据的逻辑结构的二元组定义形式为B=(D,R)，其中D={a1,a2,?,an}， R={| i=1,2,?，n-1}，请画出此逻辑结构对应的顺序存储结构和链式存储结构的示意图。 参考答案:

顺序存储结构示意图如下：

a1a2a3?an-1an

0 1 2 ? n-2 n-1 链式存储结构示意图如下：

a1a2a3?an^

5．设一个数据结构的逻辑结构如图1.9所示，请写出它的二元组定义形式。

K2 K4 K6 K5 K3 K1 K8 K9 K7

图1.9第5题的逻辑结构图

参考答案:

它的二元组定义形式为B=（D，R），其中D={k1,k2,k3,k4,k5,k6,k7,k8,k9}，

R=,,,,,,,,, }。

6．设有函数f (n)=3n2-n+4，请证明f (n)=O(n2)。

习题二参考答案

一、选择题

1. 链式存储结构的最大优点是（ ）。

A.便于随机存取 C.无需预分配空间

B.存储密度高

D.便于进行插入和删除操作

2. 假设在顺序表{a0,a1,??,an－1}中，每一个数据元素所占的存储单元的数目为4，且第0

个数据元素的存储地址为100，则第7个数据元素的存储地址是（）。 A. 106 B. 107 C.124 D.128

3. 在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（ ）存储方式。

A.顺序表

C.不带头结点的单链表

B. 带头结点的单链表 D. 循环单链表

4. 在链表中若经常要删除表中第一个结点或在最后一个结点之后插入一个新结点，则宜采

用（ ）存储方式。 A. 顺序表

B. 用头指针标识的循环单链表 D. 双向链表

C. 用尾指针标识的循环单链表

5. 在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为S,则修改链的

java语句序列是（ ）。

A. s.setNext(p); q.setNext(s); B. p.setNext(s.getNext()); s.setNext(p); C. q.setNext(s.getNext()); s.setNext(p); D. p.setNext(s); s.setNext(q); 6. 在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的

时间复杂度是（ ）。

A. O(1) B. O(log2n) C. O(n) D. O(n2)

7. 要将一个顺序表{a0,a1,??,an-1}中第i个数据元素ai(0≤i≤n-1)删除，需要移动（ ）

个数据元素。

A. i B. n-i-1 C. n-i D. n-i+1

8. 在带头结点的双向循环链表中的p结点之后插入一个新结点s，其修改链的java语句序

列是（ ）。

A. p.setNext(s); s.setPrior(p); p.getNext().setPrior(s); s.setNext(p.getPrior());

B. p.setNext(s); p.getNext().setPrior(s); s.setPrior(p); s.setNext(p.getNext());

C. s.setPrior(p); s.setNext(p.getNext()); p.setNext(s); p.getNext().setPrior(s);

D. s.setNext(p.getNext()); s.setPrior(p); p.getNext().setPrior(s);

p.setNext(s);

9. 顺序表的存储密度是（ ），而单链表的存储密度是（ ）。

A．小于1 B. 等于1 C. 大于1 D. 不能确定 10. 对于图2.29所示的单链表，下列表达式值为真的是（ ）。

head A B P1 C D P2 E

图2.29 单链表head的存储结构图

A. head.getNext().getData()=='C' B. head.getData()=='B' C. P1.getData()==’D’ D. P2.getNext()==null 二、填空题

1. 线性表是由n（n≥0）个数据元素所构成的有限序列，其中n为数据元素的个数，称为线性表的长度，n=0的线性表称为空表。

2. 线性表中有且仅有一个开始结点和终端结点，除开始结点和终端结点之外，其它每一个数据元素有且仅有一个前驱，有且仅有一个后继。

3. 线性表通常采用顺序存储和链式存储两种存储结构。若线性表的长度确定或变化不大，则适合采用顺序存储结构进行存储。

4. 在顺序表{a0,a1,??,an-1}中的第i(0≤i≤n-1)个位置之前插入一个新的数据元素，会引起n-i个数据元素的移动操作。

5. 在线性表的单链表存储结构中，每一个结点有两个域，一个是数据域，用于存储数据元素值本身，另一个是指针域，用于存储后继结点的地址。

6. 在线性表的顺序存储结构中可实现快速的随机存取，而在链式存储结构中则只能进行 顺序存取。

7. 顺序表中逻辑上相邻的数据元素，其物理位置一定相邻，而在单链表中逻辑上相邻的数据元素，其物理位置不一定相邻。

8. 在仅设置了尾指针的循环链表中，访问第一个结点的时间复杂度是o（1）。

9. 在含有n个结点的单链表中，若要删除一个指定的结点p，则首先必须找到指针结点的前驱，其时间复杂度为o（n）。

10. 若将单链表中的最后一个结点的指针域值改为单链表中头结点的地址值，则这个链表就

构成了循环单链表。

一、单项选择题

1. 下面描述错误的是（）

A． HTML文件由开头，标记结束。 B．文档头信息包含在与之间。

C．在和之间可以包含