上海交大2004数据结构考研辅导班讲稿下载

总结所考知识点分布：

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->data<=pb->data)

{ 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=A&Ccedil;B，要求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->data<pb->data){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);}

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

&reg; &not;

栈1增长 栈2增长

（1） 实现双栈DualStack，其声明如下：

const int MaxDualStackSize = 100

class DualStack

{

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\");

}

前序+中序决定二*树

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 (prestart<preend)

{for (i=instart;inorder==preorder[start];i++);

if(i>instart)

p->lchild=creatBT(prestart+1,prestart-instart+i,instart,i-1);

if (i<inend)

p->rchild=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);

}

}


在二*排序树中删除所有结点值<=x的结点

void DeleteBST (BiTree &T, Keytype x)

{

f->lchild=T; p=T;

while(!p)

if (p->data<=x)

{f->lchild=p->rchild;

q=p;

p=p->rchild;

delete(q 及 q的左子树);//要用非递归的遍历具体实现

}

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);

}

数据结构与C语言程序设计


一.    是非题（2’&acute;10）


（ ）1、   队列逻辑上是一个表头和表尾既能插入又能删除的线性表。


（ ）2、   任何一个递归过程都可以转换成非递归过程。


（ ）3、 与n个键值的集合{k1,k2,…,kn}相对应的堆是唯一的。


（ ）4、   在索引顺序表上实现分块查找，在等概率查找情况下，其查找长度只与表中元素个数有关，而与每块中元素个数无关。


（ ）5、   所谓加权无向图G的最小生成树T就是将G中各结点间的最短路径作为边所构造出来的G的子图。


（ ）6、   在10万个随机排列的数据中，要选出5个最小的数，采用快速排序比采用Shell排序、堆排序及各种直接排序法都快。


（ ）7、   B树查找算法的时间复杂性为O（n）。


（ ）8、   哈希表查找无需进行关键字的比较。


（ ）9、   在执行某个排序过程中，出现排序码朝着最终位置相反方向移动，则该算法是不稳定的。


（ ）10、任何有向图的顶点都可以按拓扑序排序。




二. 填空题（2’&acute;6）


1． 假设用于通信的电文由8个字母组成，其频率分别为0.07，0.19,0.02,0.06, 0.32,0.03,0.21,0.10, 为这8个字母设计哈夫曼编码，其中编码长度最大的字母的编码是     位。


2．已知二*树按中序遍历所得到的结点序列为DCBGEAHFIJK，按后序遍历所得到的结点序列为DCEGBFHKJIA， 按先序遍历所得到的结点序列为      。


3. 设哈希表长度为11， 散列函数 H(k)=k MOD 11, 若输入顺序为（18,10,21,9,6,3,16,25,7）,处理冲突方法为线性探测再散列，请构造哈希表              。


4．给出一组关键字 T=(20，4，34，5，16，33，18，29，2，40，7)，要求从小到大进行排序，试给出快速排序(选第一个记录为枢轴)第一趟排序结果      。


5．已知模式匹配的KMP算法中模式串t=’adabbadada’，其next函数的值为              。


6．在置换-选择排序中，假设工作区的容量为w，若不计输入、输出的时间，则对n个记录的文件而言，生成所有初始归并段所需时间为             。




三. 简答题（6’&acute;5）


1． 有n个不同的英文单词，它们的长度相等，均为m，若n>>50，m<5，试问采用什么排序方法时间复杂度最佳？为什么？


2． 对于一个栈，给出输入序列A，B，C，试给出全部可能的输出序列。若输入序列的长度为n，则可能的输出序列有多少？


3． 求2-3树的结点数和叶子数的范围并证明之。


4． 求解下列递归方程：


                 1               n=1


T（n）={   aT(n/b)+c         n>1


其中 a>1, b>1, a&Icirc;N, b&Icirc;N


为简单起见，设n为b的整数幂。


5．快速排序的时间复杂度是多少？试推导之。

四. 程序设计题（ 38’）


1．假设有两个集合A和B，均以元素值递增有序排列的带头结点的单链表作为存储结构。请编写算法求C=A&Ccedil;B，要求C按元素值递增有序排列，并要求利用原表（即表A和表B）的结点空间存放表C。(12’)


2．  从键盘上输入一串正整数，以—1为输入结束的标志，试设计一个算法，生成一棵二*排序树（即依次把该序列中的结点插入二*排序树）。(12’)


3．  试设计一个算法，在中序线索二*树中求指定结点P在后序遍历序列中的前驱结点。要求算法为非递归的，空间复杂度为O（1）。(14’)

数据结构与C语言程序设计答案

一. 是非题（2’&acute;10）


（&acute;）1、 队列逻辑上是一个表头和表尾既能插入又能删除的线性表。


（√）2、任何一个递归过程都可以转换成非递归过程。


（&acute;）3、 与n个键值的集合{k1,k2,…,kn}相对应的堆是唯一的。


（&acute;）4、 在索引顺序表上实现分块查找，在等概率查找情况下，其查找长度只与表中元素个数有关，而与每块中元素个数无关。


（&acute;）5、 所谓加权无向图G的最小生成树T就是将G中各结点间的最短路径作为边所构造出来的G的子图。


（&acute;）6、 在10万个随机排列的数据中，要选出5个最小的数，采用快速排序比采用Shell排序、堆排序及各种直接排序法都快。


（&acute;）7、 B树查找算法的时间复杂性为O（n）。


（&acute;）8、 哈希表查找无需进行关键字的比较。


（&acute;）9、 在执行某个排序过程中，出现排序码朝着最终位置相反方向移动，则该算法是不稳定的。


（&acute;）10、任何有向图的顶点都可以按拓扑序排序。

二. 填空题（2’&acute;6）


1． 假设用于通信的电文由8个字母组成，其频率分别为0.07，0.19,0.02,0.06, 0.32,0.03,0.21,0.10, 为这8个字母设计哈夫曼编码，其中编码长度最大的字母的编码是 5 位。


2．已知二*树按中序遍历所得到的结点序列为DCBGEAHFIJK，按后序遍历所得到的结点序列为DCEGBFHKJIA， 按先序遍历所得到的结点序列为 ABCDGEIHFJK 。


3. 设哈希表长度为11， 哈希函数 H(k)=k MOD 11, 若输入顺序为（18,10,21,9,6,3,16,25,7）,处理冲突方法为线性探测再散列，请构造哈希表 。


0 1 2 3 4 5 6 7 8 9 10


21 3 25 16 6 18 7 9 10


4．给出一组关键字 T=(20，4，34，5，16，33，18，29，2，40，7)，要求从小到大进行排序，试给出快速排序(选第一个记录为枢轴)第一趟排序结果 7,4,2,5,16,18,20,29,33,40,34 。


5．已知模式匹配的KMP算法中模式串t=’adabbadada’，其next函数的值为 0112112343 。


6．在置换-选择排序中，假设工作区的容量为w，若不计输入、输出的时间，则对n个记录的文件而言，生成所有初始归并段所需时间为 O(n log w) 。


三. 简答题（6’&acute;5）


1． 有n个不同的英文单词，它们的长度相等，均为m，若n>>50，m<5，试问采用什么排序方法时间复杂度最佳？为什么？

采用基数排序方法最佳。


因单词长度相等，而只有26个字母组成，符合基数排序的条件。


因m<<n，故时间复杂性由O(m(n+rm))变成O(n)。




2． 对于一个栈，给出输入序列A，B，C，试给出全部可能的输出序列。若输入序列的长度为n，则可能的输出序列有多少？

ABC，ACB，BAC，BCA，CBA

C2nn/（n+1）

3． 求2-3树的结点数和叶子数的范围并证明之。

2h+1-1 ~ （3h+1-1）/2


2h ~ 3h


h为树的高度


用数学归纳法证明。

4． 求解下列递归方程：

1 n=1


T（n）={ aT(n/b)+c n>1


其中 a>1, b>1, a&Icirc;N, b&Icirc;N


为简单起见，设n为b的整数幂。




T(n)=O(n Log b a )




5． 快速排序的时间复杂度是多少？试推导之。




O(n log n)




四. 程序设计题（ 38’）


1．假设有两个集合A和B，均以元素值递增有序排列的带头结点的单链表作为存储结构。请编写算法求C=A&Ccedil;B，要求C按元素值递增有序排列，并要求利用原表（即表A和表B）的结点空间存放表C。(12’)




void Join(LinkList &la , LinkList &lb , LinkList &lc)


{ pa=la->next; pb=lb->next; lc=la; pc=la;


while (pa&&pb)


if (pa->data<pb->data)


{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);


}


while(pa){p=pa; pa=pa->next; free(p);}


while(pb){p=pb; pb=pb->next; free(p);}


pc->next=NULL;


free(lb);


}








2． 从键盘上输入一串正整数，以—1为输入结束的标志，试设计一个算法，生成一棵二*排序树（即依次把该序列中的结点插入二*排序树）。(12’)




void creat(BiTree *b)


{int x;


BiTree *s;


b=NULL;


do


{scanf(“%d”,&x);


s=(BiTNode *) malloc (sizeof(BiTNode));


s->data=x;


s->lchild=NULL;


s->rchild=NULL;


insert(b,s);


} while(x!=-1);


}




void insert(b,s)


BiTree *b, *s;


{ if (b= =NULL) b=s;


else if (s->data= =b->data) return();


else if(s->data<b->data) insert(b->lchild,s);


else insert(b->rchild,s);


}




3． 试设计一个算法，在中序线索二*树中求指定结点P在后序遍历序列中的前驱结点。要求算法为非递归的，空间复杂度为O（1）。(14’)




BiThrNode * Postorder_Pre( BiThrTree Thrt, BiThrNode *p)




{ if (p->rtag= = 0) q=p->rchild;


else {q=p;


while (q->ltag= =1 && q->lchild!=Thrt)


q=q->lchild;


if (q->ltag= =0) q=q->lchild;


else q=NULL;


}


return(q);


}