Free考研资料

标题: 上海交大2004数据结构考研辅导班讲稿下载 [打印本页]

作者: yueshen22 时间: 07-4-13 10:16
标题: 上海交大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Ç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);

}

作者: yueshen22 时间: 07-4-13 10:17
例：用一个数组存放两个栈，一个从左端开始增长，一个从右端

开始增长。

Stack1 Stack2
…
…
…

bottom1 top1 top2 bottom2

® ¬

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

}

作者: yueshen22 时间: 07-4-13 10:17
数据结构与C语言程序设计

一. 是非题（2’´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’´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’´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ÎN, bÎN

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

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

四. 程序设计题（ 38’）

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

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

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

作者: yueshen22 时间: 07-4-13 10:18
数据结构与C语言程序设计答案

一. 是非题（2’´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’´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’´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为树的高度

用数学归纳法证明。

作者: yueshen22 时间: 07-4-13 10:18
4．求解下列递归方程：

1 n=1

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

其中 a>1, b>1, aÎN, bÎN

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

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

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

O(n log n)

四. 程序设计题（ 38’）

1．假设有两个集合A和B，均以元素值递增有序排列的带头结点的单链表作为存储结构。请编写算法求C=AÇ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);

}

欢迎光临 Free考研资料 (http://bbs.freekaoyan.com/)