数据结构 逻辑结构 存储结构 操作 线树图集 顺序 链式 性|型|状 存储 存储 结结结 结构 结构 构|构构合 虚拟存储结构 数组 指针 2001 2000 1999 线性 next值(5) 线性表的归并(12) 构 两个栈模拟队列(12) 遍历序列 三次树前后序确定树(5) 按层次顺序遍历二叉 树型 二叉树(=)森林中序线索树上求后序后继(20)树(12) 结构 树的基本概念 判断二叉树相似(8) 先序+中序建立二叉 在二叉树上求结点的 树(12) 祖先 图状 关键路径 图的深度优先,广度 结构 (逆)邻接表的生成 优先,最小生成树 最佳归并树的虚段|Hash表平均查找长度公式(5)Hash表的删除(12) 集合 平衡二叉树 B-树的深度定义(5) 二叉排序树,平衡二 二叉排序树A8L分析各类排序复杂度() 叉树(7) 查找 排序时间复杂度证明(8) 内部排序第一趟结果 排序 有序表查找长度证明(8) 外排 置换-选择排序(8) 堆定义、堆排序与其 删除二叉树结点(12) 它排序的比较(8) 置换-选择排序(4) 算法设计递归方程求解 递归方程求解 与分析 程序题2/1035 3/1240 5/1060 所占比例
2001 2000 1999 线性 结构 next 值（5） 线性表的归并（12） 两个栈模拟队列（12） 树型 结构 遍历序列 二叉树〈=〉森林 树的基本概念 在二叉树上求结点的 祖先 三次树前后序确定树（5） 中序线索树上求后序后继（20） 判断二叉树相似（8） 按层次顺序遍历二叉 树（12） 先序+中序建立二叉 树（12） 图状 结构 关键路径 （逆）邻接表的生成 图的深度优先，广度 优先，最小生 成树 （12） 集合： 查找 排序 外排 最佳归并树的虚段 平衡二叉树 二叉排序树 ASL 分析 Hash 表平均查找长度公式（5） B-树的深度定义（5） 各类排序复杂度（8） 排序时间复杂度证明（8) 有序表查找长度证明（8） 置换-选择排序（8） 删除二叉树结点（12） Hash 表的删除（12） 二叉排序树，平衡二 叉树（7） 内部排序第一趟结果 （9） 堆定义、堆排序与其 它排序的比较（8） 置换-选择排序（4） 算法设计 与分析 递归方程求解 递归方程求解 程序题 所占比例 2/10 35’ 3/12 40’ 5/10 60’ 数据结构 逻辑结构 存储结构 操作 线 性 结 构 树 型 结 构 图 状 结 构 集 合 顺 序 存 储 结 构 链 式 存 储 结 构 虚拟存储结构 数组 指针
总结所考知识点分布: 线性结构 KMP算法中next数组的值 线性表的归并 两个栈模拟队列 栈的输出序列 栈、队列基本操作的时间复杂度 二叉树和树的定义 二叉树的前序、中序、后序、层次遍历 哪些遍历序列可唯一决定二叉树 叉树的结点查找 二叉树的相似判断 求二叉树结点的祖先结点 中序线索二叉树及中序遍历线索二叉树 在中序线索二叉树上求其他序的前驱、后继 Huffman树的构造 森林(树)与二叉树的转换 ●图 图的深度优先、广度优先遍历 生成树 最小生成树的 Kruskal算法 (逆)邻接表的生成 拓扑排序 关键路径 最短路径 Di jkstra算法、 Floyd算法 查找 有序表ASL证明 索引排序表的查找 二叉排序树的插入、删除、ASL分析 平衡二叉树的插入、删除、 B-树的定义、深度、插入 Hash表的构造、查找、删除及ASL分析 排序 各类排序的时间空间复杂度分析 稳定性分析 基于比较的排序在最坏情况下能达到的最好的时间复杂度证明
总结所考知识点分布： ⚫ 线性结构： KMP 算法中 next 数组的值 线性表的归并 两个栈模拟队列 栈的输出序列 栈、队列基本操作的时间复杂度 ⚫ 树： 二叉树和树的定义 二叉树的前序、中序、后序、层次遍历 哪些遍历序列可唯一决定二叉树 二叉树的结点查找 二叉树的相似判断 求二叉树结点的祖先结点 中序线索二叉树及中序遍历线索二叉树 在中序线索二叉树上求其他序的前驱、后继 Huffman 树的构造 森林（树）与二叉树的转换 ⚫ 图： 图的深度优先、广度优先遍历 生成树 最小生成树的 Kruskal 算法 （逆）邻接表的生成 拓扑排序 关键路径 最短路径 Dijkstra 算法、Floyd 算法 ⚫ 查找： 有序表 ASL 证明 索引排序表的查找 二叉排序树的插入、删除、ASL 分析 平衡二叉树的插入、删除、 B-树的定义、深度、插入 Hash 表的构造、查找、删除及 ASL 分析 ⚫ 排序： 各类排序的时间空间复杂度分析 稳定性分析 基于比较的排序在最坏情况下能达到的最好的时间复杂度证明
各类排序的第一趟排序结果 堆的定义 置换选择排序的初始归并段构造 初始归并段平均长度的证明 最佳归并树的虚段 ●算法设计与分析 递归方程求解 例题分析 例:假设有两个按元素值非递减有序排列的线性表A和B,均以单链表 作存储结构,请编写算法将表A和表B归并成一个按元素非递减有 序(允许值相同)排列的线性表C,并要求利用原表(即表A和表B) 的结点空间存放表C void Mergelist L(LinkList &la, LinkList &Lb, LinkList &lc) /已知单链线性表La和Lb的元素按值非递减排列。 /归日并Ia和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列。 pa=La->next pb=Lb->next 用La的头结点作为Lc的头结点 while( pa&&pb) pa->datadata) i pc->next=pa; pc=pa pa=pa->next; i else ( pc->next=pb pc=pb pb=pb->next pc->next-pa? pa ∥插入剩余段 free(Lb) ∥释放Lb的头结点 i//Mergelist L 例:已知两个单链表A和B分别表示两个集合,其元素递增排列,请 编写算法求C=A⌒B,要求C按元素递增排列,并利用原表(即表A 和表B)的结点空间存放表C。 void Join( linklist &la, linklist& lb, linklist Ic) fif( pa-datadata) p=pa, pa=pa->next; free(p); else if( pa->data>pb->data)(p=pb pb=pb->next; free(p); j else pc->next=pa, pc=pa pa=pa->next p=pb pb=pb->next free(p)
各类排序的第一趟排序结果 堆的定义 置换选择排序的初始归并段构造 初始归并段平均长度的证明 最佳归并树的虚段 ⚫ 算法设计与分析： 递归方程求解 例题分析 例：假设有两个按元素值非递减有序排列的线性表 A 和 B，均以单链表 作存储结构，请编写算法将表 A 和表 B 归并成一个按元素非递减有 序（允许值相同）排列的线性表 C，并要求利用原表（即表 A 和表 B） 的结点空间存放表 C。 void MergeList_L(LinkList &La, LinkList &Lb,LinkList &Lc) //已知单链线性表 La 和 Lb 的元素按值非递减排列。 //归并 La 和 Lb 得到新的单链线性表 Lc，Lc 的元素也按值非递减排列。 { pa=La->next;pb=Lb->next; Lc=pc=La; //用 La 的头结点作为 Lc 的头结点 while(pa&&pb) { if(pa->datadata) { pc->next=pa; pc=pa;pa=pa->next;} else {pc->next=pb;pc=pb;pb=pb->next;} } pc->next=pa?pa:pb; //插入剩余段 free(Lb); //释放 Lb 的头结点 }//MergeList_L 例：已知两个单链表 A 和 B 分别表示两个集合，其元素递增排列，请 编写算法求 C=AB，要求 C 按元素递增排列，并利用原表（即表 A 和表 B）的结点空间存放表 C。 void Join(Linklist &la, linklist & lb, linklist & lc) { pa=la->next;pb=lb->next;lc=la;pc=la; while(pa&&pb) {if(pa->datadata){p=pa;pa=pa->next;free(p);} else if(pa->data>pb->data) {p=pb;pb=pb->next;free(p);} else{pc->next=pa;pc=pa;pa=pa->next; p=pb;pb=pb->next;free(p);
pc->next=nil while( pa)p=pa pa=pa->next; free(p); j hile(pb)ip=pb pb=pb->next; free(p);; free(lb) 例:带头结点的单链表的逆置 用类似栈的方式实现 struct link *inverse (head) struct link *head istruct link *pl, *p2,*p; pI=head->next; if (pll=nil) pl->next=nil;∥处理链尾 while(p21=nil) {p=p2->next;∥保存下一个结点 head->next=p2;插入链头 p2=p,∥循链向下 用队列和递归实现 if not empty (head i dequeue( head, x) reverse(head 例:用一个数组存放两个栈,一个从左端开始增长,一个从右端 开始增长。 StackI Stack2 bottom 栈1增长 栈2增长 (1)实现双栈 DualStack,其声明如下 const int max DualStack Size =100
} } pc->next=nil; while(pa){p=pa;pa=pa->next;free(p);} while(pb){p=pb;pb=pb->next;free(p);} free(lb); } 例：带头结点的单链表的逆置 用类似栈的方式实现 struct link *inverse（head） struct link *head； {struct link *p1， *p2， *p； p1=head->next; if (p1!=nil) { p2=p1->next; p1->next=nil; //处理链尾 while (p2!=nil) {p=p2->next; //保存下一个结点 p2->next=head->next; head->next=p2; //插入链头 p2=p; //循链向下 } } } 用队列和递归实现 if not empty(head) { dlqueue(head,x); reverse(head); enqueue(head,x); } 例：用一个数组存放两个栈，一个从左端开始增长，一个从右端 开始增长。 Stack1 Stack2 … … … bottom1 top1 top2 bottom2 → 栈 1 增长 栈 2 增长 （1） 实现双栈 DualStack，其声明如下： const int MaxDualStackSize = 100 class DualStack {
Data Type stack Storage[ MaxDualStackSizeI Publ Dual Stack( void); void Push( Data Type elt,intn),∥/往栈n中压入et Data Type Pop(intn),∥从栈n中弹出 DataType Peak(intn);∥取栈n的栈顶元素 nt Stack Empty(int n)∥栈n为空否? Int Stack Full(int n),∥栈n已满否? void Clear Stack(intn),/清空栈n oid dualStack: push( Data Type elt, int n) if(Stack Full(n)) return("stack overflow!"); else(if(n=l) Stack Storage[ topl]=elt; top1++ i if(n==2)( StackStorage[ top2]=elt; top2--;) int DualStack: Stack Full(int n f return(top2l=top1); i (2)利用双栈 DualStack模拟一个队列,写出入队和出队 的算法。 Void enqueue( Dual Stack Q, Data Type a) all(1))Q push(a, 1); else return("overflow") Data Type dEqueue(DualStack Q) Data lype a fif(!(Q Stack Empty (1)&&Q Stack Empty(2))) fif(!Q StackEmpty (2))a=Q- pop(2) (1))Q- push(Q- pop(1), 2), return(a) else return("Infeasible");
private: int top1 , top2 ; DataType stackStorage[MaxDualStackSize]; Public: DualStack(void); void Push(DataType elt,int n); //往栈 n 中压入 elt DataType Pop(int n); //从栈 n 中弹出 DataType Peak(int n); //取栈 n 的栈顶元素 Int StackEmpty(int n); //栈 n 为空否？ Int StackFull(int n); //栈 n 已满否？ void ClearStack(int n); //清空栈 n }; void DualStack::push(DataType elt, int n) { if(StackFull(n)) return("stack overflow!"); else{if(n==1){ StackStorage[top1]=elt; top1++;} if(n==2){ StackStorage[top2]=elt; top2--;} } } int DualStack::StackFull(int n) {return (top2+1==top1);} （2）利用双栈 DualStack 模拟一个队列，写出入队和出队 的算法。 Void enqueue(Dual Stack Q, DataType a ) { if(!Q.StackFull(1)) Q.push(a,1); else return("overflow"); } DataType dlqueue(DualStack Q) DataType a; {if(!(Q.StackEmpty(1)& &Q.StackEmpty(2))) {if(!Q.StackEmpty(2)) a=Q.pop(2); else {while(!Q.StackEmpty(1)) Q.push(Q.pop(1),2); a=Q.pop(2); } return(a); } else return("Infeasible"); }
前序+中序决定二叉树 Datatype preorder[n], inorder[n] Struct link *BI BI=crea(0,n-1,0,n-1) Return(Bt struct link*creatBT(int prestart, int preend, int instart, int inend) ip=(struct link ")malloc(sizeof(struct link)); p->lchild=null; p->rchild=null p->data=preorderIprestart if (pr f for(iinstart; inorder[]==E ) preorder start: 1++ if(instant) p->lchild=creatBT(prestart+ l, prestart-instart+i, instart, i-1); p->rchild=creatBT(prestart-instart+i+l, preen, i+l, inend); return(p); 按层次遍历二叉树 oid Traverse level( Bitree bt) Enqueue( Q, bt) while(! Queue Empty(Q) if(!v->lchild)Enqueue(Q, v->lchild) if(!v->rchild )Enqueue(Q, v->rchild) 在二叉排序树中删除所有结点值lchild=T; P=T; ff->lchild=p->rchild; qp p=p->rchild delete(q及q的左子树)要用非递归的遍历具体实现
前序+中序决定二叉树 main() {Datatype preorder[n],inorder[n]; Struct link *BT; If (n>0) BT=creat(0,n-1,0,n-1); Return(BT); } struct link * creatBT(int prestart, int preend, int instart, int inend) {p=(struct link *)malloc(sizeof(struct link)); p->lchild=null;p->rchild=null; p->data=preorder[prestart]; if (prestartinstart) p->lchild=creatBT(prestart+1,prestart-instart+i,instart,i-1); if (irchild=creatBT(prestart-instart+i+1,preend,i+1,inend); } return(p); } 按层次遍历二叉树 void Traverse_level(Bitree bt) {Initqueue(Q); Enqueue(Q,bt); while (!QueueEmpty(Q)) {v=Dlqueue(Q); visit(Q); if(!v->lchild)Enqueue(Q,v->lchild); if(!v->rchild)Enqueue(Q,v->rchild); } } 在二叉排序树中删除所有结点值lchild=T; p=T; while(!p) if (p->datalchild=p->rchild; q=p; p=p->rchild; delete(q 及 q 的左子树);//要用非递归的遍历具体实现
else(f=p p-p->lchild 哈希表的删除 hashtable del hashtable(hashtable &hash, keytype K) it=h(k) if( hash[t]==null)return("infeasible") else if (hash[t]==K) hash(t]=hash(t]->next q=hash(t p=hash[t]->next while((I found)&&(p> null)) if( p->key==k) i found=I else(q=p; p=p->next; j if(! found) return(“ infeasible”);
} else{f=p; p=p->lchild; } 哈希表的删除 hashtable del_hashtable (hashtable &hash, keytype K) {t=h(k); if ( hash[t]= = null) return (“infeasible”); else if (hash[t]= =K) hash[t]=hash[t]->next; else { found=0; q=hash[t]; p=hash[t]->next; while ((!found)&&(p<> null)) if ( p->key= =K) {found=1; q->next=p->next; } else{q=p; p=p->next;} if(!found) return (“infeasible”); } return(hash); }