第一部分：概念、线性表、栈和队列、串、树组与广义表 ．算法的五个重要特性?
．算法的时间复杂度、空间复杂度? ．线性表的元素关系存储时如何体现？
．头结点的作用？首结点、头结点、头指针区别？
. 单链表、双链表、循环链表的插入和删除操作,以及判断链表为空的条件？
．循环队列Q[0，n-1]，头、尾位置为f、r，队满、队空的条件？队列元素个数计算？ ．双端队列、单端受限队列的入队与出队序列关系？
. 元素进栈与退栈的过程？对已知入栈序列，可能输出结果及不可能输出结果？ . 空串与空字符串的区别？
．给出串匹配算法中已知串的失败函数next或nextval的值?
．数组A[m][n]的每一个元素占k个字节，数组总大小？某元素位置？某地址下标？ . 压缩矩阵的下标与存储地址关系？
．广义表的运算Gethead()、Gettail()，如从广义表L中取出某个部分的运算表达式? . 广义表的存储结构？如已知一个广义表，给出它的存储结构？ 第二部分：树
．树的表示形式？二叉树的5条性质？二叉树的存储结构？二叉树的三种遍历？ . 给二叉树加上线索（三种线索）？
. 具有n个结点的二叉树的最小深度？最大深度？
．n个结点的完全二叉树顺序存储，叶结点和非叶结点的个数、范围？ ．遍历方式不同叶结点的相对顺序如何？，内结点的相对顺序又如何？
. 已知二叉树的两种遍历结果（一般必须包含一个中序或层序），请构造这棵二叉树？ . 树的存储结构有哪些？树和森林与二叉树的相互转换？（即对一棵树或森林给出二叉链表存储？根据二叉链表存储画出该树或森林？）
. 已知电文，求哈夫曼编码需要位数和具体编码数？对已知序列进行哈夫曼编码？ . 设二叉树采用二叉链表存储，请编写算法实现求二叉树高度(结点个数，判定是否为平衡二叉树，是否为二叉排序树等)？ 第三部分：图
．无向图和有向图的存储方法（4种）？十字链表(弧结点，头结点)的指针域? ．图的遍历（深度优先和广度优先）？图的遍历结果与存储结构有关！
. 图的生成树？带权图的最小生成树？
. 有向图可以进行拓扑排序的条件？对一个图进行拓扑排序？
. 对已知带权有向图，求关键路径？计算某源点都其余顶点的最短路径？ .比如，已知一个无向图的邻接表
（1）请画出该无向图；（2）根据邻接表，分别写出用DFS和BFS算法从顶点v0开始的遍历该图后所得到的遍历序列，并画出DFS生成树和BFS生成树。 第四部分：查找
．顺序查找方法适宜于存储结构？
．线性表顺序查找不成功时关键字的比较次数? . 有序表的折半查找过程？查找过程的判定树？ ．分块查找(索引表查找)的T(n)的组成及意义？
. 二叉排序树的形成与查找？如：对同一组数据而言二叉排序树是否唯一的? 对二叉排序树先删去x再插入x，新旧二叉排序树相同？构建二叉排序树，请画出第i步? . 平衡二叉树的平衡调整（4种）？如：对已知序列构造平衡二叉树，如有旋转请画出旋转前、后的树形结构并标注旋转类型?
．B树的元素插入与删除？如：对已知序列，画出一个m阶Ｂ-树？ . 高为3的5阶B-树（连叶层在内）最少的关键字总数目?
. 哈希表（散列表）中散列函数构造与冲突解决方法？如：已知序列，设散列函数H(k)= k mod 7，用线性探测法解决冲突。请建散列表存储及查找次数？ 第五部分：排序
．排序算法的稳定性？对各种排序法中“排序趟”的概念？
. 五类排序中主要排序方法有哪些？对已知序列，可按给定排序方法给出第i趟结果？ . 不稳定的排序算法有那些？ . 冒泡排序算法的主要工作量是什么？
．用筛法建堆则必须从什么位置开始？堆是一个数据结构吗？ . 判断已知序列是否为堆？如不是，请用筛选建堆？ ．初始数据如果已有序，耗费的时间反而最多的算法？ ．对已知序列找出前5个最小的元素用什么算法？ . 做快速排序，请给出第i趟的结果及元素交换次数? . 做Shell排序，步长已知，请给出第i趟结果?
第一章 一
(3) int i=1,j=1;
while(i i=i+1; j=j+i; } j = 1 + 2 + 3 + 4 + 5 + 6 + … + k <= n , 利用等差数列求和公式即可 (4) int i=0; do { for(int j=1;j<=n;j++) i=1+j; }while(i<100+n) 这个题需要细心，i = 1 + j 在这个程序中 i 的最大值只能为 1+n ，永远小于 100+n,即无线循环。 第四章 一．KMP算法求next和nextval值 j 1 2 3 4 5 6 7 模式 a b c a b a a Next Nextval 有关KMP除了按照标准的KMP算法来计算next和nextval值，在手算时可以采用简便算法，即某个字符的next值为该字符前最长公共字串长度加1。 例如，对于第6个字符a的next值，最长公共字串为 ab(12) = ab(45) 公共字串长度为2，则next值为3。(这两个字符串必须一个以1开始，另一个以j-1(前一个字符)结尾) 而nextval值为，如果某个字符的next值指向的字符和当前字符一样，即以指向字符的next值更新nextval值。 第六章 四． 对于利用先序和中序还原树的问题难度不大，利用先序中字符出现的顺序在中序序列进行左右划分，递归此过程即可。 但应该注意对此类题扩展，哪种序列组合可以求，例如先序和后序序列能还原否？ 第七章 一． 对于本题，大多数同学的错误是根据邻接表画出图以后，仅仅利用画出的图的信息进行DFS和BFS，造成答案不唯一。 在DFS算法和BFS算法的实现中，必须利用邻接表中存储的信息，即在某节点具有多个邻接节点时，首先访问的是该节点的邻接链表中存储的最靠近链首的节点。因此本题的DFS序列唯一结果为： 0 -> 2 -> 3 -> 1 -> 4 -> 6 -> 5 而BFS的程序实现一般是采用队列，即对当前访问的节点，将邻接节点进行先进 先出，进的序列也应该为该节点的邻接链表的序列。 BFS序列的唯一结果为: 0 -> 2 -> 5 -> 6 -> 1-> 3 -> 4 三．拓扑排序。 本题同学的错误也均为不细致，题目中描述各顶点的邻接表均从小至大排列，因此当访问某节点时，入队和入栈的顺序均为从小到大。 对于以栈实现的，拓扑流程如下： 当前访问节点 0 0 7 0 7 8 0 7 8 1 0 7 8 1 4 0 7 8 1 4 9 0 7 8 1 4 9 5 0 7 8 1 4 9 5 6 0 7 8 1 4 9 5 6 2 0 7 8 1 4 9 5 6 2 3 对于以队列实现，拓扑流程如下: 当前访问节点 0 0 1 0 1 7 0 1 7 2 0 1 7 2 4 0 1 7 2 4 8 0 1 7 2 4 8 5 0 1 7 2 4 8 5 9 0 1 7 2 4 8 5 9 3 0 1 7 2 4 8 5 9 3 6 栈(栈底 -> 栈顶) 1 7 1 8 1 2 4 2 5 9 2 5 2 6 2 3 (队首 -> 队尾) 1 7 7 2 2 4 8 4 8 8 5 5 9 9 3 6 3 6 6 队列 （一） 1．（1）n^3 (2) (n(n+1)(n+2))/6 (3) ?3?1?8n?1?1?8n?m?，其中m为整数 22[?1?1?8n] [x]表示不超过x的最大整数 2?2(100?n)]步，1?n?14?n[n(n?1) （4）? ?n步，n?15?2．2n?1?o(2n)成立，22n?o(2n)不成立 23．（1）o(nlogn) （2）o(N) (二) 1．删除： Status ListDelete_L(LinkList&L, int i, ElemType &e) { //在不带头结点的单链线性表L中，删除第i个元素，并由e返回其值 P=L; j=1; while (P&&j //寻找第i个结点，并令p指向其前驱 P=P->next; ++j; } if(!P||j>i) return ERROR;//删除位置不合理 q=P->next; e=q->data; P->next=q->data; free(q); return OK; }//ListDelete_L 插入： Status ListInsert_L(LinkList&L, int i, ElemType &e) { //在不带头结点的单链表L中第i个位置前插入元素e P=L; j=1; while(P&&j