以至少应该是15.

4.插入一个结点要平均移动n/2结点；删除一个结点要平均移动（n-1）/2结点；具体的移动次数取决于n的大小和插入或删除的位置这两个因素。

5.线性表是指由n（n>=0）个数据元素{a0,a1.a2?.an-2,an-1}组成的有限序列。该序列要么为空或仅有一个元素，要么除了第一个元素没有前趋以及最后一个元素没有后续之外，其他元素都有且仅有一个前趋，也有且仅有一个后续。线性表可以表示为：{ai|I属于[0，n-1]} 单链表是指必须是有一个称为表头的指针向连接，N个结点形成一个链，且每个结点只有一个指针域的线性表。

线性表的存储方式是指线性表的存储方式分为线性存储和链式存储两种，其中顺序存储是指线性表的顺序存储，链式存储是指线性表中的每一个结点其物理位置可连续，也可不连续，但是各结点间通过指针相连。

循环链表是指把单链表的末尾结点种的指针域指向头结点，形成环型的链表。

双向链表是指必须具有一个头指针，每个结点有两个指针域，一个指向该结点的前趋，一个指向该结点的后继的线性表。

6．在单链表中不能删除，而在双链表和单循环莲表中可以删除p结点。双向链表的删除p结点的时间复杂度为O(1)，单循链表删除p结点的时间复杂度为O（1）。 7．在循环链表中可以由尾指针表示。

8．因为在顺序表中插入或删除时，需要移动大量的数据，所以在需要提高查找效率，而较少插入或删除的情况下，可以采用顺序储存；链式存储结构便于插入和删除。但是不便于查找结点。所以对于需要经常修改线性表结点位置的情况下，采用链式存储为宜。

9．栈，队列都是一种线性结构，只是他们的运算规则不同。栈是遵循先进后出的运算规则，堆栈的操只能在栈的一端（栈顶）进行；队列则遵循先进先出的运算规则，队的操作只能在队列的队首删除，队尾插入。 10．（1）1234。

（2）能得到1432，不能得到1423。因为同时压入2，3，在弹出时根据堆栈的运算规则只能弹出3，2。

（3）在1，2，3，4的各种排列中，根据堆栈的运算规则（先进后出），可能出现的次序是1234，1324，1432，2143，2134，3214，4321。

11．例如，在空间限定的情况下火车站的一条铁轨上已经停满了火车以后，火车已无法再进站，这属于上溢；调度在车辆派空以后，到时间没有车派了，这属于下溢。

12．循环队列的储存，可以解决假溢出的问题。空的条件是队首追上队尾，既front；满的条件是队尾追上队首，既rear+1=front。

13．两次对应的储存状态分别为：

14．不含任何字符的串称为空串，其串长度为零；仅含有空格字符的串称作空格，其长度为串中空格符的个数。

空格符在字符串中可用来分隔一般的字符，便于阅读和识别，空格符会占用串长。 空串在处理过程中可用于作为任意字符串的子串。

15．两个字符串相等的充要条件是：两个串的长度相等，且对应位置的字符相等。 16．二叉树与树的区别：

（1）二叉树的结点至多有两个子树，数则不然；

（2）二叉树的一个结点的子树有左，右之分，而树则没有此要求。

度为2 的树有两个分支，没有左，右之分，一颗二叉树边也可有两个分支。但 左右之分。且左右不能交换。

17．先序遍历序列：ABDEFC

中序遍历序列：DEFBAC

后序遍历序列：FEDBCA

18.(1)由中序遍历序列和先序遍历序列，或中序遍历序列和后序遍历序列，可以唯一确定一颗二叉树。

由先序序列知，根结点最先被访问，就可确定根结点为A，而又由中序序列得知一棵树的根结点是其左，右子树的分隔点，从而可确定以A为根的左子树的结点为B,C,D,右子树的结点为E,F,G。重复进行就可得到二叉树。

（2）由先序遍历序列和后序遍历序列不能唯一确定一棵二叉树。因为两种遍历方法只能确定根结点，而分不清左右子树。 19．二叉树如图1.20所示.

20．度为2的有序树是指子树从左向右是有次序的，每个结点最多有两个分支，二叉树的最大度也是2，并且子树有左右之分。从表面上看好像没有什么不同，但是当只有一个子树时，度为2的有序树没有左右之分，而二叉树必须有左右之分，这就是度为2的有序树和二叉树的主要区别。

21．假设结点为A,B,C,3个结点的树的状态如图1.21所示. 3个结点的二叉树的状态如图1.22所示

.

22．最少应为2h-1+1个结点，最多为2 h -1个结点。 23．顺序存储如图1.23所示. 链式存储如图1.24所示.

24．答：假设8个字母所对应的权值为{5，25，4，7，9，12，30，8}，并且n=8。

根据哈夫曼的构造方法。将8个结点构成哈夫曼树，按照左0右1的原则，可以得到字母的豪夫曼编码为：

A.1001 B.11 C.1000 D.0000 E.101 F.001 G.01 H.0001 25.(1)深度优先遍历：V1,V2,V3,V8,V5,V7,V4,V6 广度优先遍历：V1,V2,V4,V6,V3,V5,V7,V8 (2)最短路径为：（V1,V2,,V5,V7,V8）

26．（1）邻接矩阵为：A 0 0 0 1 0 0 A的入度为2，出度为1 B 1 0 1 0 0 0 B的入度为2，出度为2 C 0 0 0 1 1 1 C的入度为1，出度为3 D 0 0 0 0 0 0 E 1 1 0 1 0 0 F 0 1 0 0 1 0

（2）邻接表为如图1.25所示。 A D

B A C C D E F D E A B D F B

E

逆邻接表按边的方向反之即可。 （3）强连通分量如图1.26所示。 图 1.26

27．（1）的无向图如图1.27（a）所示；（2）的有向图如图1.27（b）所示。

（b） 图 1.27 28．（1）采用邻接矩阵表示时，无向图的总边数为所有数值之和除以2；有向图的总边数为各行数值之和。采用邻接表表示时，无向图的边数为内部顶点个数除以2；有向图的边数为内部顶点个数。

（2）对于无向图是以图中i行和j列的交叉点的值是否为1；对于有向图是以图中i行j列交叉点或i列j行交叉点的值是否为1来判断顶点i和j是否有边相连。

（3）无向图顶点的度为每一行的数值之和；有向图顶点度为该行和该列数值之和。 29．顺序查找：表中元素可以任意存放。

折半查找：表中元素必须以关键字的大小按递增或递减的次序存放。 分块查找：表中元素每块内的元素可以任意存放，但是块与块之间必须以关键字的大小按递增或递减的次序存放。

30．顺序查找：查找成功时的平均查找长度为：ASL=（n+1）/2 折半查找：查找成功时的平均查找长度为：ASL=lg（n+1）-1 分

块查找：查找成功时的平均查找长度的大小与其确定所在块所采用的查找方法有关。若用顺序查找法确定所在块，则平均查找长度为（n/s+s）/2+1；若用折半查找法确定所在的块，平均查找长度为lg（n/s+1）+s/2，其中s为每块含有的元素个数。

31．（1）由于散列表的长度为12，则可选不超过表长的最大素数11作为除留余数法的模，则可得其哈希函数为H（k）=k。

（2）若用线性探测再散列法解决冲突，则可构造出散列表如 13 14

35 17 29 153 0 1 2 3 4 5 6 7 8 9 10

11

此时，其装填因子为6/12=1/2，若用链式法解决冲突，则其散列表如图1．28所示。 32．此种排序算法是不稳定的。

由于选择排序算法的原则是从记录中找到最小（或最大）者并与第一个记录交换，一旦被换到某个位置以后再也不动了，此种方法不能保证具有相同排序码的记录原来所具有的相对次序，即原来排在前面的经排序后有可能排在具有相同排序码记录的后面，所以此种排序算法是不稳定的。

33．

初始关键字序列为：

（19，01，26，92，87，11，43，87，21） 第一遍排序比较8次，交换6次后成为： （01，19，26，87，11，43，87，21，92） 第二遍排序比较7次，交换3次后成为： （01，19，26，11，43，87，21，87，92） 第三遍排序比较6次，交换2次后成为： （01，19，11，26，43，21，87，87，92） 第四遍排序比较5次，交换2次后成为： （01，11，19，26，21，43，87，87，92） 第五遍排序比较4次，交换1次后成为： （01，11，19，21，26，43，87，87，92） 第六遍排序比较3次，交换0次。排序完毕。 图１．28

34．直接插入排序算法是稳定的。

它不会将具有相同关键字的记录插入到其记录的前面，所以直接插入排序算法是稳定的。

35．因为在堆排序时，在调整堆的过程中，有可能改变具有相同关键字的元素的先后次序，