资源描述
第十章内部排序
一、 基本知识题答案
1. 排序: 将一组杂乱无序的数据按一定的规律顺次排列起来叫做排序。
内部排序: 数据存储在内存中, 并在内存中加以处理的排序方法叫内部排序。
堆: 堆是一个完全二叉树, 它的每个结点对应于原始数据的一个元素, 且规定如果一个结点有儿子结点, 此结点数据必须大于或等于其儿子结点数据。
稳定排序: 一种排序方法, 若排序后具有相同关键字的记录仍维持原来的相对次序, 则称之为稳定的, 否则称为不稳定的。
2. 回答下面问题
(1) 5000个无序的数据, 希望用最快速度挑选出其中前10个最大的元素, 在快速排序、 堆排序、 归并排序和基数排序中采用哪种方法最好? 为什么?
(2) 大多数排序算法都有哪两个基本操作? 答: (1)采用堆排序最好。
因为以上几种算法中, 快速排序、 归并排序和基数排序都是在排序结束后才能确定数据元素的全部顺序, 而无法知道排序过程中部分元素的有序性。堆排序则每次输出一个最大( 或最小) 的元素, 然后对堆进行调整, 保证堆顶的元素总是余下元素中最大( 或最小) 的。根据题意, 只要选取前10个最大的元素, 故采用堆排序方法是合适的。
(2)两个基本操作: 比较两个关键字的大小、 改变指向记录的指针或移动记录本身。
3. 3. 已知序列{17, 25, 55, 43, 3, 32, 78, 67, 91}, 请给出采用冒泡排序法对该序列作递增排序时每一趟的结果。
答: 采用冒泡排序法排序时的各趟结果如下:
初始: 17, 25, 55, 43, 3, 32, 78, 67, 91
第1趟: 17, 25, 43, 3, 32, 55, 67, 78, 91
第2趟: 17, 25, 3, 32, 43, 55, 67, 78, 91
第3趟: 17, 3, 25, 32, 43, 55, 67, 78, 91
第4趟: 3, 17, 25, 32, 43, 55, 67, 78, 91
第5趟: 3, 17, 25, 32, 43, 55, 67, 78, 91
第5趟无元素交换, 排序结束。
4. 已知序列{491, 77, 572, 16, 996, 101, 863, 258, 689, 325}, 请分别给出采用快速排序、 堆排序和基数排序法对该序列作递增排序时每一趟的结果。
答: 采用快速排序法排序时的各趟结果如下:
初始: 491, 77, 572, 16, 996, 101, 863, 258, 689, 325
第1趟: [325, 77, 258, 16, 101] 491 [863, 996, 689, 572]
第2趟: [101, 77, 258, 16] 325, 491 [863, 996, 689, 572]
第3趟: [16, 77] 101 [258] 325, 491 [863, 996, 689, 572]
第4趟: 16 [77] 101 [258] 325, 491 [863, 996, 689, 572]
第5趟: 16, 77, 101 [258] 325, 491 [863, 996, 689, 572]
第6趟: 16, 77, 101, 258, 325, 491 [863, 996, 689, 572]
第7趟: 16, 77, 101, 258, 325, 491 [572, 689] 863 [996]
第8趟: 16, 77, 101, 258, 325, 491, 572 [689] 863 [996]
第9趟: 16, 77, 101, 258, 325, 491, 572, 689, 863 [996]
第10趟: 16, 77, 101, 258, 325, 491, 572, 689, 863, 996
采用堆排序法排序时各趟的结果如下图所示:
(a) 初始堆 (b) 建堆
(c) 交换996和77, 输出996 (d) 筛选调整
采用基数排序法排序时各趟的结果如下:
初始: 491, 77, 572, 16, 996, 101, 863, 258, 689, 325
第1趟( 按个位排序) : 491, 101, 572, 863, 352, 16, 996, 77, 258, 689
第2趟( 按十位排序) : 101, 16, 352, 258, 863, 572, 77, 689, 491, 996
第3趟( 按百位排序) : 16, 77, 101, 258, 352, 491, 572, 689, 863, 996
5. 已知序列{86, 94, 138, 62, 41, 54, 18, 32}, 请给出采用插入排序法对该序列作递增排序时, 每一趟的结果。
答: 采用插入排序法排序时各趟的结果如下:
初始: (86), 94, 138, 62, 41, 54, 18, 32
第1趟: (86, 94), 138, 62, 41, 54, 18, 32
第2趟: (86, 94, 138), 62, 41, 54, 18, 32
第3趟: (62, 86, 94, 138), 41, 54, 18, 32
第4趟: (41, 62, 86, 94, 138), 54, 18, 32
第5趟: (41, 54, 62, 86, 94, 138), 18, 32
第6趟: (18, 41, 54, 62, 86, 94, 138), 32
第7趟: (18, 32, 41, 54, 62, 86, 94, 138)
6. 已知序列{27, 35, 11, 9, 18, 30, 3, 23, 35, 20}, 请给出采用归并排序法对该序列作递增排序时的每一趟的结果。
答: 采用归并排序法排序时各趟的结果如下:
初始: 27, 35, 11, 9, 18, 30, 3, 23, 35, 20
第1趟: [27, 35] [9, 11] [18, 30] [3, 23] [20, 35]
第2趟: [9, 11, 27, 35] [3, 18, 23, 30] [20, 35]
第3趟: [9, 11, 27, 35] [3, 18, 20, 23, 30, 35]
第4趟: [3, 9, 11, 18, 20, 23, 27, 30, 35, 35]
二、 算法设计题答案
1. 二、 算法设计题
1. 一个线性表中的元素为全部为正或者负整数, 试设计一算法, 在尽可能少的时间内重排该表, 将正、 负整数分开, 使线性表中所有负整数在正整数前面。
解: 本题的算法思想是: 设置两个变量分别指向表的首尾, 它们分别向中间移动, 指向表首的
如果遇到正整数, 指向表尾的如果遇到负整数则互相交换, 然后继续移动直至两者相遇。实现本
题功能的算法如下:
void part(int array[],int n)
{
int i,j;
i=1;
j=n;
while(i<j)
{ while(i<j && array[i]<0)
i++;
while(i<j && array[j]>=0)
j--;
if(i<j)
{ array[0]=array[i];
array[i]=array[j];
array[j]=array[0];
}
}
}
2. 设计一个用单链表作存储结构的直接插入排序算法。
解: 实现本题功能的算法如下:
void insertsort(node *head)
{
node *p,*q,*pre;
pre=head;
p=head->next; /*p指向待插入的元素*/
while(p!=NULL)
{
q=head;
if(p->key<q->key) /*插到表首*/
{ pre->next =p->next;
p->next =head;
head=p;
}
else
{
while(q->next!=p && q->next ->key<p->key)
q=q->next;
if(q->next ==p)
{
pre=p;
p=p->next;
}
else
{ pre->next =p->next;
p->next =q->next;
q->next =p;
p=pre->next;
}
}
}
}
3. 试设计一个算法实现双向冒泡排序。( 双向冒泡排序就是在排序的过程中交替改变扫描方向。)
解: 实现本题功能的算法如下:
void dbubblesort(sqlist r,int n)
{
int i,j,flag;
flag=1;
i=1;
while(flag!=0)
{
flag=0;
for(j=i;j<n-i;j++)
{
if(r[j]>r[j+1])
{
flag=1;
r[0]=r[j];
r[j]=r[j+1];
r[j+1]=r[0];
}
}
for(j=n-i;j>i;j--)
{
if(r[j]<r[j-1])
{ flag=1;
r[0]=r[j];
r[j]=r[j-1];
r[j-1]=r[0];
}
}
i++;
}
}
4.设一个一维数组A[n]中存储了n个互不相同的整数, 且这些整数的值都在0到n-1之间, 即A中存储了从0到n-1这n个整数。试编写一算法将A排序, 结果存放在数组B[n]中, 要求算法的时间复杂性为O(n)。
解: 实现本题功能的算法如下:
void sort(int A[n],int B[n])
{
int i;
for(i=0;i<n;i++)
B[A[i]]=A[i];
}
第九章
一、 基础知识题
1.(1)查找: 查找又称为查询或检索, 是在一批记录中依照某个域的指定域值, 找出相应的记录的操作。
(2)树型查找: 将原始数据表示成二叉排序树, 树的每个结点对应一个记录, 利用此二叉排序树进行类似于二分查找思想的数据查找, 这种查找方法称为树型查找。
(3)平衡因子: 二叉树中每一结点的左子树高度减右子树高度为该结点的平衡因子。
(4)散列函数: 根据关键字求存储地址的函数称为散列函数。
(5)两个不同的关键字, 其散列函数值相同, 因而被映射到同一个表位置上的现象称为冲突。
2. 设有序表为{a,b,c,d,e,f,g}, 请分别画出对给定值f,g和h进行拆半查找的过程。
答: 查找f的过程如下:
查找成功, 找到k=f值
查找g的过程如下:
查找成功, 找到k=g值
查找h的过程如下:
3. 试述顺序查找法、 二分查找法和分块查找法对被查找表中元素的要求, 每种查找法对长度为n的表的等概率查找长度是多少
答: 顺序查找法: 表中元素能够任意存放。查找成功的平均查找长度为(n+1)/2。
二分查找法: 表中元素必须以关键字的值递增或递减地存放且只能以顺序表存放。查找成功的平均查找长度为log2(n+1)-1。
分块查找法: 表中每块内的元素能够任意存放, 但块与块之间必须按关键字的大小递增或递减地存放, 即前一块内所有元素的关键字不能大( 或小) 于后一块内任意一个元素的关键字。若用顺序查找确定所在块, 平均查找长度为1/2(n/s+s)+1; 若用二分查找确定所在块, 平均查找长度为log2(n/s+1)+s/2。
4. 设散列表长m=14, 哈希函数为H(k)=k mod 11, 表中一共有8个元素{15,27,50,73,49,61,37,60} , 试画出采用二次探测法处理冲突的散列表。
答: 采用二次探测法处理冲突的散列表如下:
5. 线性表的关键字集合为{113,12,180,138,92,67,94,134,252,6,70,323,60}, 共有13个元素, 已知散列函数为: H( k) =k mod 13, 采用链接表处理冲突, 试设计这种链表结构。
答: 由题意, 可得:
H(113) = 113 % 13 =9
H(12) = 12 % 13 =12
H(180) = 180 % 13 =11
H(138) =138 % 13 =8
H(92) = 92 % 13 =1
H(67) = 67 % 13 =2
H(94) = 94% 13 =3
H(134) = 134% 13 =4
H(252) = 252 % 13 =5
H(6) = 6% 13 =6
H(70) = 70 % 13 =5
H(323) = 323% 13 =11
H(60) = 60 % 13 =8
链接表法的散列表如下图所示:
6. 设关键字集合为{27,49,79,5,37,1,56,65,83}, 散列函数为: H( k) =k mod 7, 散列表长度m=10, 起始地址为0, 分别用线性探测和链接表法来解决冲突。试画出对应的散列表。
答: 线性探测法的散列表如下图所示:
链接表法的散列表如下图所示:
二、 算法设计题
1.从小到大排列的, 试写出对此链表的查找算法, 并说明是否能够采用折半查找。解: 实现本题功能的算法如下, 如果查找成功, 则返回指向关键字为x的结点的指针, 否则返回NULL。
node *sqsearch(node *head,int x)
{
node *p=head;
while(p!=NULL)
if(x>p->key)
p=p->link;
else if(x==p->key)
return p;
else
{
p=NULL;
return p;
}
}
虽然链表中的结点是按递增顺序排列的, 可是其存储结构为单链表, 查找结点时只能从头指针开始逐步进行搜索, 因此不能用折半查找。
2.如果线性表中各结点查找概率不等, 则能够使用下面的策略提高顺序表的查找效率: 如果找到指定的结点, 则将该结点和其前趋( 若存在) 结点交换, 使得经常被查找的结点尽量位于表的前端。试对线性表的顺序存储结构和链式存储结构写出实现上述策略的顺序查找算法( 注意查找时必须从表头开始向后扫描) 。
解: 采用顺序存储结构的算法如下, 设记录存储在线性表的1~n单元中。如果查找成功, 返回关键字为k的记录在线性表中的位置, 如果失败则返回0。
int seqsearch(sqlist r,int n,int k)
{
int i,j;
i=1;
while((r[i].key!=k) && (i<=n))
i++;
if(i<=n)
{
r[0]=r[i];
r[i]=r[i-1];
r[i-1]=r[i];
i--;
return(i);
}
else return(0);
}
采用链式存储结构的算法如下。如果查找成功, 则返回指向关键字为k的结点的指针, 否则返回NULL。
node *seqsearch(node *head,int k)
{
if(head->key==k)
return(head);
else
{
node *p,*q;
int x;
p=head;
q=head->link;
while(q!=NULL && q->key!=k)
{
p=q;
q=q->link;
}
if(q!=NULL)
{
x=p->key;
p->key=q->key;
q->key=x;
q=p;
}
return(q);
}
}
3. 试设计一个在用开放地址法解决冲突的散列表上删除一个指定结点的算法。
解: 本题的算法思想是: 首先计算要删除的关键字为k的记录所在的位置, 将其置为空( 即删除) , 然后利用线性探测法查找是否有与k发生冲突而存储到下一地址的记录, 如果有则将记录移到原来k所在的位置, 直至表中没有与k冲突的记录为止。实现本题功能的算法如下:
void delete(sqlist r,int n,int k)
{
int h,h0,h1;
h=k%n;
while(r[h].key!=k)
h=(h+1)%n;
r[h]=NULL;
h0=h;
h1=(h+1)%n;
while(h1!=h)
{ while(r[h1].key%n!=h)
h1=(h1+1)%n;
r[h0]=r[h1];
r[h1]=NULL;
h0=h1;
h1=(h1+1)%n;
}
}
4. 设给定的散列表存储空间为H[1~m], 每个单元可存放一个记录, H[i](1≤i≤m)的初始值为零, 选取散列函数为H(R.key), 其中key为记录R的关键字, 解决冲突方法为线性探测法, 编写一个函数将某记录R填入到散列表H中。
解: 本题的算法思想: 先计算地址H(R.key), 如果没有冲突, 则直接填入; 否则利用线性探测法求出下一地址, 直到找到一个为零的地址, 然后填入。实现本题功能的函数如下:
void insert(record H,int m,record R)
{
int i;
i=H(R.key);
if(H[i]==NULL)
H[i]=R;
else
{
while(H[i]!=NULL)
{
i=(i+1)%(m+1);
}
H[i]=R;
}
}
第七章
一、 基本知识题
1. 图的逻辑结构特点是什么? 什么是无向图和有向图? 什么是子图? 什么是网络?
答: 图是比树更为复杂的一种非线性数据结构, 在图结构中, 每个结点都能够和其它任何结点相连接。
无向图: 对于一个图G, 若边集合E( G) 为无向边的集合, 则称该图为无向图。
有向图: 对于一个图G, 若边集合E( G) 为有向边的集合, 则称该图为有向图。
子图: 设有两个图G =(V,E)和G’=(V’,E’), 若V(G’)是V(G)的子集, 且E(G’)是E(G)的子集, 则称G’是G的子图(Subgraph)。
网络: 有些图, 对应每条边有一相应的数值, 这个数值叫做该边的权。边上带权的图称为带权图, 也称为网络。
2. 什么是顶点的度? 什么是路径? 什么是连通图和非连通图? 什么是非连通图的连通分量?
答: 顶点的度: 图中与每个顶点相连的边数, 叫该顶点的度。
在一个图中, 若从某顶点Vp出发, 沿一些边经过顶点V1,V2,…,Vm到达, Vq, 则称顶点序列(Vp, V1,V2,…,Vm, Vq)为从Vp到Vq的路径。
在无向图中, 如果从顶点Vi到顶点Vj之间有路径, 则称这两个顶点是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。
非连通图的连通分量: 非连通图的每一个连通的部分叫连通分量。
3. 给出图6.25所示的无向图G的邻接矩阵和邻接表两种存储结构。
答: 图G所对应的邻接矩阵如下: 图G所对应的邻接表如下:
图25
4. 假设图的顶点是A、 B……请根据下面的邻接矩阵画出相应的无向图或有向图。
答: (a)所对应的无向图如下图(a)所示, (b)所对应的有向图如下图(b)所示:
5.5. 分别给出图6.26所示G图的深度优先搜索和广度优先搜索得到的顶点访问序列。
图26
答: 深度优先搜索得到的顶点访问序列: 0、 1、 3、 7、 8、 4、 9、 5、 6、 2;
广度优先搜索得到的顶点访问序列: 0、 1、 2、 3、 4、 5、 6、 7、 8、 9。
6. 应用prim算法求图6.27所示带权连通图的最小生成树。
答: 该图的最小生成树如下:
图27
7. 写出图6.28所示有向图的拓朴排序序列
答: 该有向图的拓朴排序序列为: 3、 1、 4、 5、 2、 6。
二、 算法设计题 图28
二、 算法设计题答案
1. 如图6.29所示图G, 试给出其对应的邻接表, 并写出深度优先算法。解: 该图对应的邻接表如下:
深度优先算法:
void dfsgraph(adjlist adj, int n)
/*深度优先遍历整个图*/
{
int i;
for(i=1;i<=n;i++)
visited[i]=0;
for(i=1;i<=n;i++)
if(!visited[i])
dfs(adj,i);
}
void dfs(adjlist adj,int v)
/*以v为出发点, 对图进行dfs遍历*/
{ struct edgenode *p;
visited[v]=1;
printf("%d",v);
p=adj[v]→link;
while(p!=NULL)
{ if(visited[p→adjvex]==0)
dfs(adjlist,p→adjvex);
p=p→next;
}
}
2. 如图6.29所示图G, 试给出其对应的邻接矩阵, 并写出广度优先算法。
解: 该图对应的邻接矩阵如下:
广度优先算法:
void bfsgraph(int adjarray[n][n],int n)
/*广度优先遍历整个图*/
{
int i;
for(i=0;i<n;i++)
visited[i]=0;
for(i=0;i<n;i++) 图29
if(!visited[i])
bfs(adjarray,i);
}
void bfs(int adjarray[][],int v)
/*以v为出发点, 对图进行bfs遍历*/
{
int i,j;
queue q;
printf("%d",v);
visited[v]=1;
enqueue(&q,v);
while(!queueemty(&q))
{
i=dequeue(&q);
for(j=0;j<n;j++)
if(adjarray[i][j]==1 && !visited[j])
{
printf("%d",j);
visited[j]=1;
enqueue(&q,j);
}
}
}
3. 编写一个函数经过与用户交互建立一个有向图的邻接表。
解: 实现本题功能的算法如下:
void creategraph(adjlist g)
{
int e,i,s,d,n;
struct edgenode *p ;
printf("请输入结点数(n)和边数(e):\n");
scanf("%d,%d",&n,&e);
for(i=1;i<=n;i++)
{
printf("\n请输入第%d个顶点信息: ",i);
scanf("%c",&g[i].data);
g[i].link=NULL;
}
for(i=1;i<=e;i++)
{ printf("\n请输入第%d条边起点序号, 终点序号: ",i);
scanf("%d,%d",&s,&d);
p=(struct edgenode *)malloc(sizeof(edgenode));
p→adjvex=d;
p→next=g[s].link;
g[s].link=p;
}
}
4. 编写一个无向图的邻接矩阵转换成邻接表的算法。
解: 本题的算法思想是: 逐个扫描邻接矩阵的各个元素, 如第i行第j列的元素为1, 则相应的邻接表的第i个单链表上增加一个j结点。实现本题功能的算法如下:
void transform(int adjarray[n][n],adjlist adj)
{
int i,j;
edgenode *p;
for(i=0;i<n;i++)
{
adj[i].data=i;
adj[i].link=NULL;
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{ if(adjarray[i][j]==1)
{ p=(edgenode *)malloc(sizeof(edgenode));
p→adjvex=j;
p→next=adj[i].link;
adj[i].link=p;
}
}
}
5.已知一个有n个顶点的有向图的邻接表, 设计算法分别实现
1) 求出图中每个顶点的出度。
2) 求出图中每个顶点的入度。
3) 求出图中出度最大的一个顶点, 输出其顶点序号。
4) 计算图中出度为0的顶点个数。
解: (1) 本题的算法思想是: 计算出邻接表中第i个单链表的结点数, 即为i顶点的出度。求顶点的出度数的算法如下:
int outdegree(adjlist adj,int v)
{ int degree=0;
edgenode *p;
p=adj[v].link;
while(p!=NULL)
{ degree++;
p=p->next;
}
return degree;
}
void printout(adjlist adj,int n)
{
int i,degree;
printf("The outdegrees are:\n");
for(i=0;i<n;i++)
{
degree=outdegree(adj,i);
printf("(%d,%d)",i,degree);
}
}
(2)本题的算法思想是: 计算出整个邻接表中所具有的结点为i的结点数, 这就是i顶点的入度。求顶点的入度数的算法:
int indegree(adjlist adj,int n,int v)
{
int i,j,degree;
edgenode *p;
for(i=0;i<n;i++)
{
p=adj[i].link;
while(p!=NULL)
{
if(p->adjvex==v)
degree++;
p=p->next;
}
}
return degree;
}
void printin(adjlist adj,int n)
{
int i,degree;
printf("The indegrees are:\n");
for(i=0;i<n;i++)
{
degree=indegree(adj,n,i);
printf("(%d,%d)",i,degree);
}
}
(3)求最大出度的算法:
void maxoutdegree(adjlist adj,int n)
{
int maxdegree=0,maxv=0, degree, i;
for(i=0;i<n;i++)
{
degree=outdegree(adj,i);
if(degree>maxdegree)
{
maxdegree=degree;
maxv=i;
}
}
printf("maxoutdegree = %d,
maxvertex = %d",maxdegree,maxv);
}
(4)求出度数为0的顶点数的算法: int outzero(adjlist adj,int n)
{
int num=0,i;
for(i=0;i<n;i++)
{
if(outdegree(adj,i)==0)
num++;
}
return num;
}
第六章
一、 基础知识题
1. 就如图5.21所示的树回答下面问题:
1) 哪个是根结点?
2) 哪些是叶子结点?
3) 哪个是E的父结点?
4) 哪些是E的子孙结点?
5) 哪些是E的兄弟结点? 哪些是C的兄弟结点?
6) 结点B和结点I的层数分别是多少?
7) 树的深度是多少?
8) 以结点G为根的子树的深度是多少?
9) 树的度是多少?
答: 1) A是根结点
2) D、 H、 I、 J、 F、 G是叶子结点
3) B是E的父结点
4) H、 I、 J是E的子孙结点
5) D是E的兄弟结点, B是C的兄弟结点
6) B的层数是2, I的层数是4
7) 树的深度是4
8) 以结点G为根的子树的深度是1
9) 树的度是3
2.分别画出含3个结点的树与二叉树的所有不同形态。
答: 3个结点的树:
3个结点的二叉树:
3. 高度为h的完全二叉树至少有多少个结点? 最多有多少个结点?
答: 高度为h的完全二叉树至少有个结点, 最多有个结点。
4. 采用顺序存储方法和链式存储方法分别画出图5.22所示二叉树的存储结构。
答: 该二叉树的顺序存储:
该二叉树的链式存储:
5. 分别写出图5.22所示二叉树的前序、 中序和后序遍历序列。
图22
答: 先序遍历序列: 1、 2、 4、 7、 3、 5、 8、 6、 9
中序遍历序列: 7、 4、 2、 1、 8、 5、 3、 6、 9
后序遍历序列: 7、 4、 2、 8、 5、 9、 6、 3、 1
6.若二叉树中各结点值均不相同。
1)已知一个二叉树的中序和后序遍历序列分别为GDHBAECIF和GHDBEIFCA, 请画出此二叉树。
2)已知一个二叉树的前序和中序分别为ABCDEFGH和BDCEAFHG, 请画出此二叉树。
答:
7. 一个二叉树如图5.23所示,分别写出其前序、 中序、 后序的遍历序列。
答: 先序遍历序列: A、 B、 D、 E、 F、 C、 G
中序遍历序列: D、 F、 E、 B、 A、 G、 C
后序遍历序列: F、 E、 D、 B、 G、 C、 A
8.输入一个正整数序列{55,34,18,88,119,11,76,9,97,99,46}, 试构造一个二叉排序树。
9. 有一份电文中共使用5个字符: a、 b、 c、 d、 e, 它们的出现频率依次
为5、 2、 1、 6、 4。试画出对应的哈夫曼树, 并求出每个字符的哈夫曼编码。
第8题 各字符对应的哈夫曼编码如
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
