41 参考答案
第一章、绪论
一、选择题 1 B；2 A； 3 B； 4 C ；5 C； 6 B；7 C；8 C； 9 D； 10 B。
二、填空题1、存储 ；2、无 ，1，无，1； 3、前驱，1，后继，任意多个；4、一对一，一对多，多对多；5、时间复杂度，空间复杂度；6、集合，线性结构，树形结构，图形结构；7、顺序结构，链式结构，索引结构，散列结构；8、顺序。
三、问答题与算法题
1、3 ；
2、T1 ( n ) = 5n 2 -O ( n ) ; T2 ( n ) = 3 n 2 + O ( n ) ; T3 ( n ) = 8 n 2 + O(log n) ;
T4 ( n ) = 1.5 n 2 + O ( n ) 。T4 ( n ) 较优，T3 ( n )较劣。
3、见课本。
第二章 线性表
一、选择题 1C；2A；3D；4B；5D；6B；7C；8B；9A；10C；11D；12D；13C；14C.
二、填空题 1、O ( 1 ), O ( n )；2、单链表，双链表；3、地址，指针；4、4，2；5、便于访问尾结点和头结点；6、前驱；7、L->next== L且L->prior== L；8、顺序。
三、问答题与算法题
1、头指针：结点或头结点的指针变量。其作用是存放第一个结点或头结点的地址，从头指针出发可以找到链表中所有结点的信息。
头结点：是附加在链表的第一个结点之前的一个特殊结点，其数据域一般不存放信息。其作用是为了简化运算，将空表与非空表统一起来，将第一个结点与其他结点的处理统一起来。
首结点：是链表的第一个结点。
2、(1)基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。
(2)基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之， 若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。
第一章：数据结构包含：逻辑结构，数据的存储结构，对数据进行的操作。数据元素：相对独立的基本单位，即可简单也可复杂，简单的数据元素只有一个数据项，数据项是数据的不可分割的最小单位。数据对象：性质相同的数据元素的集合。数据结构：相互存在一种或者多种特定关系的数据元素的集合（集合，线性结构，树结构，图结构）。顺序存储结构：数据元素按照逻辑顺序依次存放在存储器的一段连续存储单元中。链式存储结构：存储在存储空间的任意位置上，包含一个数据域和至少一个指针域，要访问，必须从第一个元素开始查找。数据类型：一组值加一组操作。
第二章：线性表：有限多个性质相同的数据元素构成的一个序列，数据元素的个数就是长度。线性表的顺序存储结构：用一组地址连续的存储单元能随机存取的结构。链式存储结构：具有链式存储结构的线性表称为链表，是用一组地址任意的存储单元来存线性表中的数据元素。每个数据元素存储结构包括数据元素信息域和地址域，存放一个数据元素的存储结构称为结点，每个结点只定义一个指针域，存放的是当前结点的直接后记结点的地址（直接后继结点），线性表的最后一个结点指针域存放空（0，NULL）标志结束。不支持随机存取，访问必须从第一个结点开始，一次访问。双向链表：每个结点设置两个方向的指针（直接前驱和直接后继）。
第三章：栈：堆栈的简称，限定在表尾进行插入和删除的线性表。特点是后进先出。当栈定指针指向栈底时，为空栈。队列：限定只能在一端进行插入和在另一端进行删除的线性表，进行插入的是队尾，删除的是队头。特点是先进先出。队列的链式结构：用一个链表依次存放从队头到队尾的所有的数据元素。存放队头地址（队头指针）队尾地址（队尾指针），空链队列： 有头结点，空队列条件是头结点存放0，无头结点为队头指针指向空。队列的顺序存储结构：用一组地址连续的存储空间依次存放从队头到队尾的所有数据元素，再用队头指针和队尾指针记录队头和队尾的位置。队头指针指向队头元素前一个数组元素的位置，队尾始终指向队尾，当队尾和队头指向同一位置，空队列。入队和出队，队尾指针都会向数组元素下标的增加方向移动，当队尾指针超出数组上界面无法进行操作（假溢出），解决方法是使用具有顺存储存结构的循环队列：将存放队列元素的数组首尾连接，形成一个环形结构。
数据结构作业系统_第九章答案
9.26②试将折半查找算法改写成递归算法。
实现下列函数：
int BinSearch(SSTable s, int low, int high, KeyType k);
/* Index the element which key is k */
/* in StaticSearchTable s. */
/* Return 0 if x is not found. */
静态查找表的类型SSTable定义如下：
typedef struct {
KeyType key;
... ... // 其他数据域
} ElemType;
typedef struct {
ElemType *elem;
int length;
} SSTable;
int BinSearch(SSTable s, int low, int high, KeyType k)
/* Index the element which key is k */
/* in StaticSearchTable s. */
/* Return 0 if x is not found. */
{
int mid=(low+high)/2;
if(low>high)return 0;
if(s.elem[mid].key==k)return mid;
else if(s.elem[mid].key>k)return BinSearch(s,low,mid-1,k);
else return BinSearch(s,mid+1,high,k);
}
9.31④试写一个判别给定二叉树是否为二叉排序树
的算法，设此二叉树以二叉链表作存储结构。且树中 结点的关键字均不同。
实现下列函数：
Status IsBSTree(BiTree t);
/* 判别给定二叉树t是否为二叉排序树。*/
/* 若是，则返回TRUE，否则FALSE */
解题思路
多代入法
二叉树
度
叶子结点就是没有孩子的结点，其度为0，度为二的结点是指有两个子数的结点。
注意树的度 和 图的度 区别
叶子结点
二叉排序树
完全二叉树
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树； 最优二叉树（就是哈弗曼树）
平衡二叉树
平衡二叉树，又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1.。
满二叉树
满二叉树——除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层的二叉树,。
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点（最后一层上的无子结点的结点为叶子结点）。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上.
本题主要考查一些特殊二叉树的性质。
若二叉树中最多只有最下面两层的结点度数可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树，因此在完全二叉树中，任意一个结点的左、右子树的高度之差的绝对值不超过1。
二叉排序树的递归定义如下：二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：
(1)若左子树不空，则左子树上所有结点的值均小于根结点的值；
(2)若右子树不空，则右子树上所有结点的值均大于根结点的值；
(3)左右子树也都是二叉排序树。
在n个结点的二叉树链式存储中存在n+1个空指针，造成了巨大的空间浪费，为了充分利用存储资源，可以将这些空链域存放指向结点在遍历过程中的直接前驱或直接后继的指针，这种空链域就称为线索，含有线索的二叉树就是线索二叉树。
最优二叉树即哈夫曼树。
