数据结构大纲1、考试范围
1．绪论
1.1引言
1.2数据、逻辑结构和运算
1.3存储实现与运算实现
2．线性表
2.1数组
2.2数组的应用
2.3二维数组－矩阵；
2.4矩阵的应用
2.5转置矩阵
3．栈与队列
3.1栈与队列
3.2表达式求值
3.3栈的应用
3.4链表
3.5链表的运算
3.6链表的几种形式
3.7链表的应用
3.8函数及递归函数
3.9递归函数的概念
3.10递归函数的应用
3.11递归函数举例
4．树
4.1树形结构
4.2遍历二叉树
4.3有关二叉树的算法
4.4二叉树的应用
4.5赫夫曼树
4.6广义表
5．图
5.1图的概念
5.2图的遍历
5.3最小生成树
5.4拓扑排序
5.5关键路径
5.6最短路径
6．查找
6.1顺序查找
6.2折半查找（有序表）
6.3索引顺序查找（分块查找）
6.4二叉排序树查找
6.5哈希法
6.6键树
7．排序
7.1选择排序
7.2插入排序
7.3归并排序
7.4快速排序
7.5堆排序
7.6基数排序
8．文件
8.1文件的概念
8.2在Ｃ程序中使用文件的原因
2、复习题
一、试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？
答：①顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。
优点：存储密度大，存储空间利用率高。缺点：插入或删除元素时不方便。
②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。
顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。
若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。二、快速排序的执行时间，在什么情况下时间最长，这时的总比较次数为多少，在什么情况下时间最短，这时最短的总比较次数又为多少？
答：在待排序记录已经排序的情况下，时间最长，总比较次数为n(n-1)/2。每趟递归调用一次，给一个记录的位置正好是文件的蹭，从而把原文件分成两个大小相等的子文件，在这种情况下，时间最短，总的比较资料为O(nlog2n).
三、已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
答：
四、已知一树的双亲表示法如下，其中各兄弟结点是依次出现的，画出该树对
应的二叉树。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
parent
答：
五、用标准C语言实现Hanoi塔问题。
答：
Void Hanoi (int n ,char x , char y, char z)
If(n==1)
Move(x,1,z);
Else{
Hanoi(n-1,x,z,y);
Move(x,n,z);
Hanoi(n-1,y,x,z);
}
}
六、已知某哈希表的装载因子小于1，哈希函数H(key)为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。
答：
此题装载因子a〈1, 则哈希表未填满。由此可写出下列形式简明的算法：
void PrintWord(Hash Table ht)
{//按第一个字母的顺序输出哈希表ht中的标识符。哈希函数为表示符的第一个字母在字母表中的序号，处理冲突的方法是线性探测开放定址法。
for(i=1; i<=26; i++){
j=i;
While(ht.elem[j].key){
if(Hash(ht.elem[j].key==i)printf(ht.elem[j].key);
j=(j+1)%m;
}
}//PrintWord
七、在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?
答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i越接近n则所需移动的结点数越少。
八、对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？
答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。
二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。
九、已知一棵二叉树的先序序列是ABCDEFGHIJK，中序序列是CDBGFEAHJIK，请构造出该二叉树。
