浙江工商大学数据结构期末复习题2(6)

├─┼─┤ ├─┼─┤ ├─┼─┤ ２│Ｂ│ ┼→─┤Ａ│ ┼→─┤Ｄ│＾│ ├─┼─┤ ├─┼─┤ ├─┼─┤ ３│Ｃ│ ┼→─┤Ａ│ ┼→─┤Ｄ│＾│

├─┼─┤ ├─┼─┤ ├─┼─┤ ┌─┬─┐ ┌─┬─┐ ４│Ｄ│ ┼→─┤Ｂ│ ┼→─┤Ｃ│ ┼→┤Ｅ│＾├→─┤Ｆ│＾│ ├─┼─┤ ├─┼─┤ ├─┼─┤ └─┴─┘ └─┴─┘ ５│Ｅ│ ┼→─┤Ｄ│ ┼→─┤Ｇ│＾│ ├─┼─┤ ├─┼─┤ ├─┼─┤ ６│Ｆ│ ┼→─┤Ｄ│ ┼→─┤Ｇ│＾│ ├─┼─┤ ├─┼─┤ ├─┼─┤ ７│Ｇ│ ┼→─┤Ｅ│ ┼→─┤Ｆ│＾│ └─┴─┘ └─┴─┘ └─┴─┘

(3)从顶点A出发按深度优先遍历序列(不是唯一的)为A、B、D、C、E、G、F (4)从顶点A出发按广度优先遍历序列(不是唯一的)为A、B、C、D、E、F、G 39.假定一个待散列存储的线性表为(32、75、63、48、94、25、36、18、70)散列地址空间为[0..10]，若采用除留余数法构造散列函数和线性探查法处理冲突，试给出它们对应的散列表，并求出在等概北情况下的平均查找长度。 39. 解答:

k 32 75 63 48 94 25 36 18 70 k 10 9 8 4 6 3 3 7 4

得到的散列表如下：

0 1 2 3 4 5 6 7 8 9 10 ┏━┯━┯━┯━┯━┯━┯━┯━┯━┯━┯━┓ ┃70│ │ │25│48│36│94│18│63│75│32┃ ┗━┷━┷━┷━┷━┷━┷━┷━┷━┷━┷━┛ 成功到位次数 8 1 1 3 1 1 1 1 1 不成功到位次数 2 1 1 10 9 8 7 6 5 4 3 查找成功的平均查找长度为 : (8+1+1+3+1+1+1+1+1)/9=2

查找不成功的平均查找长度为 : (2+1+1+10+9+8+7+6+5+4+3)/11=56/11 40.什么是内部排序？什么是排序方法的稳定性和不稳定性？

40. 解答:假设给定含有n个记录(R1 ，R2 ，?，Rn ）的文件，其相应的关键字为(K1 ，K2 ，?， Kn )，则排序是确定一个排列P(1)，P(2)，?，P(n)，使得KP(1) ≤KP(2) ，?，KP(n) ，

从而得到有序文件(RP(1) ，RP(2) ，?，RP(n) )。整个排序过程都在内存进行的排序称为 内部排序。

假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排 序法排序后，若这些相同关键字的记录的相对次序仍然保持不变，则这种排序方法是稳定 的，否则称这种排序方法是不稳定的。

26

综合题参考答案 1. 解:

(1)顺序存储是按索引（隐含的）直接存取数据元素，方便灵活，效率高，但插入、删除操作时将引起元素移动，因而降低效率；链接存储内存采用动态分配，利用率高，但需增设指示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作十分简单。

(2)应选用链接表存储结构。其理由是，链式存储结构用一组任意的存储单元依次存储线性表里各元素，这里存储单元可以是连续的，也可以是不连续的。这种存储结构，在对元素作插入或删除运算时，不需要移动元素，仅修改指针即可。所以很容易实现表的容量扩充。 (3)应选用顺序存储结构。其理由是，每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。由此，只要确定了起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。而链表则是一种顺序存取的存储结构。

2. 不合适。因为一个城市的设计和规划涉及非常多的项目，很复杂，经常需要修改、 扩充和删除各种信息，才能适应不断发展的需要。有鉴于此，顺序线性表不能很好适应其需要，故是不合适的。

3. 在单链表中只能由当前结点访问其后的任一结点，因为没有指向其前驱结点的指 针。而在双向链表中，既有指向后继结点的指针又有指向前驱结点的指针，故可由当前结点出发访问链表中任一结点。

4. 由栈的定义可知，这种结构的基本性质综述如下：

(1)集合性。栈是由若干个元素集合而成，当没有元素的空集合称为空栈；

(2)线性结构。除栈底元素和栈顶元素外，栈中任一元素均有唯一的前驱元素和后继元素；

(3)受限制的运算。只允许在栈顶实施压入或弹出操作，且栈顶位置由栈指针所指示； (4)数学性质。当多个编号元素依某种顺序压入，且可任意时刻弹出时，所获得的编号元素排列的数目，恰好满足卡塔南数列的计算，即： Ｃn ＝Ｃn 2n /(n＋1)

其中，n为编号元素的个数，Cn 是可能的排列数目。

5. 在队列的顺序存储结构中，设队头指针为front,队尾指针为rear,队的容量（存储空间的大小）为m。当有元素要加入队列时，若rear＝m（初始时reat＝0），则发生队列的上溢现象，该元素不能加入队列。

这里要特别注意的是：队列的虚溢出现象，队列中还有空余的空间，但元素不能进队 列。造成这种现象的原因是由于队列的操作方式所致。 解决队列的上溢有以下几种方法：

(1)建立一个足够大的存储空间，但这样做往往会造成空间使用的效率低。 (2)当出现虚溢出时，可采用以下几种方法：

①采用平移元素的方法。每当队列中加入一个元素时，队列中已有的元素向队头 移动一个位置（当然要有空余的空间可移）；

②每当删去一个队头元素时，则依次序移队中的元素，始终使front指针指向队列 中的第一个位置；

27

③采用循环队列方式。把队头队尾看成是一个首尾相邻的循环队列，虽然物理上 队尾在队首之前，但逻辑上队首依然在前，作插入和删除运算时仍按“先进先出”的原则。 6. 两个字符串相等的充要条件是：两个串的长度相等，且对应位置的字符相等。 7. 根据广义表的结构可知，该树的根结点为A；而B、C、D为A的子树，B又有两棵子 树等等，该广义表对应的树型结构见下图。 A

B C D

E F G H I

J K L

8. 其特点是只有最下面的二层结点可以小于２，其它结点的度数必须为２。 9. 证明

利用前序遍历的结果序列能够得到各子树的根，即从左到右检查前序遍历序列，当得 到根结点之后，利用根结点在中序遍历序列中的位置可以确定其左右子树，这样便可逐次确定整个二叉树。

假设BT为二叉树的根，P1 ，P2 ，?，Pn 为前序遍历序列，I1 ，I2 ，?，In 为中 序遍历序列。

由前序遍历序列可以得到BT＝P1 。

在中序遍历序列中查找等于P1 的结点，设该结点为Ii ，则有Ii ＝P1 。

根据二叉树中序遍历的原理，则该二叉树可被分成左右两棵子树：对于左子树，在中序遍历序列中有I1 ，I2 ，?，Ii－1 ，依此序列在前序遍历序列中可以得到其左子树为P2 ， P3 ，?，Pi ；

同理，对于右子 …… 此处隐藏：4340字，全部文档内容请下载后查看。喜欢就下载吧 ……