数据结构与考研开场白.doc

数据结构操作存储结构逻辑结构链 式存 储结 构顺 序存 储结 构集合图状结构树型结构线性结构抽象存储结构指针数组2002200120001999线性结构栈的进出序列的总数next值（5）线性表的归并（12）两个栈模拟队列（12）树型结构树和二叉树的定义按层次后序的树的遍历哈夫曼编码和求解二叉树性质：最少层数，叶子总数二叉排序树的平均查找长度二叉排序树的第I个结点和结点的插入建树：层号前序遍历序列二叉树=森林树的基本概念在二叉树上求结点的祖先三次树前后序确定树（5）中序线索树上求后序后继（20）判断二叉树相似（8）按层次顺序遍历二叉树（12）先序+中序建立二叉树（12）图状结构关键路径（逆）邻接表的生成图的深度优先，广度优先，最小生成树（12）集合：查找排序外排快速排序的时间复杂性及推导顺序查找的平均查找长度二分查找法的最坏情况下的查找长度最小化堆的最大元建堆：n1个元素已是堆，建立n个元素的堆(时间：O(log log n)最佳归并树的虚段平衡二叉树二叉排序树 ASL分析Hash表平均查找长度公式（5）B-树的深度定义（5）各类排序复杂度（8）排序时间复杂度证明（8)有序表查找长度证明（8）置换-选择排序（8）删除二叉树结点（12）Hash表的删除（12）二叉排序树，平衡二叉树（7）内部排序第一趟结果（9）堆定义、堆排序与其它排序的比较（8）置换-选择排序（4）算法设计与分析递归方程求解递归方程求解程序题所占比例4/10 352/10 353/12 405/10 602003线性结构Nextval的求法树型结构树和二叉树的定义存储表示线索二叉树二叉树的遍历二叉排序树和线索二叉树的创建图状结构图的存储方式优劣图的顶点和边的查找、删除等操作。AOE网络求最迟发生时间集合：查找排序外排求最大和次最大值外部排序比较次数K 值的选取和内存的关系。算法设计与分析程序题所占比例4/12 70/150总结所考知识点分布：l 线性结构：KMP算法中next数组的值线性表的归并两个栈模拟队列栈的输出序列栈、队列基本操作的时间复杂度l 树：二叉树和树的定义二叉树的前序、中序、后序、层次遍历哪些遍历序列可唯一决定二叉树二叉树的结点查找二叉树的相似判断求二叉树结点的祖先结点中序线索二叉树及中序遍历线索二叉树在中序线索二叉树上求其他序的前驱、后继Huffman树的构造森林（树）与二叉树的转换l 图：图的深度优先、广度优先遍历生成树最小生成树的Kruskal算法（逆）邻接表的生成拓扑排序关键路径最短路径Dijkstra算法、Floyd算法l 查找：有序表ASL证明索引排序表的查找二叉排序树的插入、删除、ASL分析平衡二叉树的插入、删除、B-树的定义、深度、插入Hash表的构造、查找、删除及ASL分析l 排序：各类排序的时间空间复杂度分析稳定性分析基于比较的排序在最坏情况下能达到的最好的时间复杂度证明各类排序的第一趟排序结果堆的定义置换选择排序的初始归并段构造初始归并段平均长度的证明最佳归并树的虚段l 算法设计与分析：递归方程求解例题分析例：假设有两个按元素值非递减有序排列的线性表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-datapb-data) p=pb;pb=pb-next;free(p); elsepc-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);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 = 100class DualStack private:int top1 , top2 ;DataType stackStorageMaxDualStackSize; 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!);elseif(n=1) StackStoragetop1=elt; top1+;if(n=2) StackStoragetop2=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);前序+中序决定二叉树main()Datatype preordern,inordern;Struct link *BT;If (n0)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=preorderprestart;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的左子树);/要用非递归的遍历具体实现 elsef=p; p=p-lchild; 哈希表的删除hashtable del_hashtable (hashtable &hash, keytype K)t=h(k); if ( hasht= = null) return (