下载文档原格式
北邮算法与数据结构习题参考答案作业参考答案一、（带头结点）多项式乘法 C = A×B：void PolyAdd ( list &C, list R) // R 为单个结点{p=C;while ((！p->next) && (p->next->exp>R->exp)) p=p->next; if ((p->next) || (p->next->exp<R->exp)){ R->next=p->next; p->next=R; } else{ p->next->inf += R->inf; delete R;if ( ! p->next->inf ){ R=p->next; p->next=R->next; delete R; } }}void PolyMul ( list A, list B, list &C ){C=new struct node; C->next=NULL; q=B->next; While ( q ){p=A->next;while ( p ){r = new struct node; r->exp = p->exp + q->exp;r->inf = p-> inf * q->inf; PolyAdd(C, r);p=p->next;}q=q->next;}}二、梵塔的移动次数：已知移动次数迭代公式为：M ( n ) = 2M ( n-1 ) + 1初值为：M ( 0 ) = 0则：M ( n ) = 2 ( 2M ( n-2 ) + 1 ) + 1= 4M ( n-2 ) + 3= 8M ( n-3 ) + 7= 2i M ( n-i ) + 2i– 1若n=i ,则M ( n-n ) = 0,故：M ( n ) = 2n M ( n-n ) + 2n– 1= 2n– 1所以，梵塔的移动次数为2n– 1次。
第7章 《图》习题参考答案一、单选题（每题1分，共16分）（ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的倍。
A ．1/2 B. 1 C. 2 D. 4 （B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。
A ．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有条边。
A ．14 B. 28 C. 56 D. 112 （ C ）4. 有8个结点的无向连通图最少有条边。
A ．5 B. 6 C. 7 D. 8 （ C ）5. 有8个结点的有向完全图有条边。
A ．14 B. 28 C. 56 D. 112 （B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。
A ．栈 B. 队列 C. 树 D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。
A ．栈 B. 队列 C. 树 D. 图（ C ）8. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ D ）9. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是A ． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 23465 （ D ）10. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（ A ）11. 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是A ．0 2 4 3 1 5 6B. 0 1 3 6 5 4 2C. 0 1 3 4 2 5 6D. 0 3 6 1 5 4 2⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡0100011101100001011010110011001000110010011011110A ．0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3A．0 3 2 1 B. 0 1 2 3C. 0 1 3 2D. 0 3 1 2（A）12. 深度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（D）13. 广度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（A）14. 任何一个无向连通图的最小生成树A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）二、填空题（每空1分，共20分）1. 图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历、广度优先遍历等方法。
第七章图（参考答案）7．1（1）邻接矩阵中非零元素的个数的一半为无向图的边数；（2）A[i][j]= =0为顶点，I 和j无边，否则j和j有边相通；（3）任一顶点I的度是第I行非0元素的个数。
7．2（1）任一顶点间均有通路，故是强连通；（2）简单路径V4 V3 V1 V2;（3）0 1 ∞ 1∞ 0 1 ∞1 ∞ 0 ∞∞∞ 1 0邻接矩阵邻接表（2）从顶点4开始的DFS序列：V5,V3,V4,V6,V2,V1（3）从顶点4开始的BFS序列：V4,V5,V3,V6,V1,V27．4（1）①adjlisttp g; vtxptr i,j; //全程变量② void dfs(vtxptr x)//从顶点x开始深度优先遍历图g。
在遍历中若发现顶点j，则说明顶点i和j间有路径。
{ visited[x]=1; //置访问标记if (y= =j){ found=1;exit(0);}//有通路，退出else { p=g[x].firstarc;//找x的第一邻接点while (p!=null){ k=p->adjvex;if （!visited[k]）dfs(k);p=p->nextarc;//下一邻接点}}③ void connect_DFS (adjlisttp g)//基于图的深度优先遍历策略，本算法判断一邻接表为存储结构的图g种，是否存在顶点i //到顶点j的路径。
设 1<=i ,j<=n,i<>j.{ visited[1..n]=0;found=0;scanf (&i,&j);dfs (i);if (found) printf （” 顶点”,i,”和顶点”,j,”有路径”）；else printf （” 顶点”,i,”和顶点”,j,”无路径”）；}// void connect_DFS(2)宽度优先遍历全程变量，调用函数与（1）相同，下面仅写宽度优先遍历部分。
习题71.填空题（1）由10000个结点构成的二叉排序树，在等概率查找的条件下，查找成功时的平均查找长度的最大值可能达到（___________）。
答案：5000.5（2）长度为11的有序序列：1，12，13，24，35，36，47，58，59，69，71进行等概率查找，如果采用顺序查找，则平均查找长度为（___________），如果采用二分查找，则平均查找长度为（___________），如果采用哈希查找，哈希表长为15，哈希函数为H（key）＝key%13，采用线性探测解决地址冲突，即d i=(H(key)+i)%15，则平均查找长度为（保留1位小数）（___________）。
答案：6，3，1.6（3）在折半查找中，查找终止的条件为（___________）。
答案：找到匹配元素或者low>high?（4）某索引顺序表共有元素275个，平均分成5块。
若先对索引表采用顺序查找，再对块元素进行顺序查找，则等概率情况下，分块查找成功的平均查找长度是（___________）。
答案：31（5）高度为8的平衡二叉树的结点数至少是（___________）。
答案： 54 计算公式：F(n)=F(n-1)+F(n-2)+1（6）对于这个序列{25，43，62，31，48，56}，采用的散列函数为H(k)=k%7，则元素48的同义词是（___________）。
答案：62（7）在各种查找方法中，平均查找长度与结点个数无关的查找方法是（___________）。
答案：散列查找（8）一个按元素值排好的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，平均比较次数分别是s和b，在查找成功的情况下，s和b的关系是（___________）；在查找不成功的情况下，s和b的关系是（___________）。
答案：(1)(2s-1)b=2s([log2(2s-1)]+1)-2[log2(2s-1)]+1+1(2)分两种情况考虑，见解答。
数据结构第七章的习题答案数据结构第七章的习题答案数据结构是计算机科学中非常重要的一门学科，它研究如何组织和管理数据以便高效地访问和操作。
第七章是数据结构课程中的一个关键章节，它涵盖了树和二叉树这两个重要的数据结构。
本文将为读者提供第七章习题的详细解答，帮助读者更好地理解和掌握这些概念。
1. 问题：给定一个二叉树，如何判断它是否是二叉搜索树？解答：要判断一个二叉树是否是二叉搜索树，我们可以使用中序遍历的方法。
中序遍历会按照从小到大的顺序访问二叉树中的节点。
所以，如果一个二叉树是二叉搜索树，那么它的中序遍历结果应该是一个有序的序列。
具体实现时，我们可以使用递归或者迭代的方式进行中序遍历，并将遍历的结果保存在一个数组中。
然后，我们检查这个数组是否是有序的即可判断二叉树是否是二叉搜索树。
2. 问题：给定一个二叉树，如何找到它的最大深度？解答：要找到一个二叉树的最大深度，我们可以使用递归的方式。
对于每个节点，它的最大深度等于其左子树和右子树中的最大深度加1。
递归的终止条件是节点为空，此时深度为0。
具体实现时，我们可以定义一个递归函数，该函数接收一个节点作为参数，并返回以该节点为根节点的子树的最大深度。
在递归函数中，我们先判断节点是否为空，如果为空则返回0；否则，我们分别计算左子树和右子树的最大深度，然后取两者中的较大值加1作为当前节点的最大深度。
3. 问题：给定一个二叉树，如何判断它是否是平衡二叉树？解答：要判断一个二叉树是否是平衡二叉树，我们可以使用递归的方式。
对于每个节点，我们分别计算其左子树和右子树的高度差，如果高度差大于1，则该二叉树不是平衡二叉树。
具体实现时，我们可以定义一个递归函数，该函数接收一个节点作为参数，并返回以该节点为根节点的子树的高度。
在递归函数中，我们先判断节点是否为空，如果为空则返回0；否则，我们分别计算左子树和右子树的高度，然后取两者中的较大值加1作为当前节点的高度。
最后，我们判断左子树和右子树的高度差是否大于1，如果大于1，则该二叉树不是平衡二叉树。
第七章图
1．下面是一个图的邻接表结构，画出此图，并根据此存储结构和深度优先搜索
算法写出从C开始的深度优先搜索序列。
0A13^
1B35^
2C30^
3D4^
4E^
5F4^
【解答】
A B F
C D E
C开始的深度优先搜索序列：CDEABF（唯一的结果）
2．假定要在某县所辖六个镇（含县城）之间修公路，若镇I和镇J之间有可能通
过道路连接，则Wij表示这条路的长度。
要求每个镇都通公路且所修公路总里程
最短，那么应选择哪些线路来修。
I11112233445 J23564546566 W ij1239102626474
(1).画出该图。
(2).用C语言描述该图的数组表示法存储结构，并注明你所使用变量的实际含义。
(3).图示你所定义的数据结构。
(4).标识出你选择的线路。
【解答】
（1）
（2）
#define MAX 6
char vexs[MAX];
出该图的所有强连通分量。
(2).在图中删除弧<2,1>，然后写出从顶点1开始的拓扑有序序列。
【解答】
(1) 共4个强连通分量：
(2) 1,3,2,6,5,4
5 4
6 1 3 2
4
15 10
2
15 20 30 4 10
10。
北邮数据结构与算法课后答案第7章第7章1.选择题（1）A （2）C （3）C （4）D （5）D （6）C （7）B （8）C （9）D （10）C2.判断题（1）√ （2）Ⅹ （3）√ （4）Ⅹ （5）Ⅹ （6）√ （7）Ⅹ （8）√ （9）√ （10）√3.简答题（1）以关键字序列（tim,kay,eva,roy,dot,jon,kim,ann,tom,jim,guy,amy）为例，手工执行以下排序算法（按字典序比较关键字的大小），写出每一趟排序结束时的关键字状态：1）直接插入排序；2）冒泡排序；3）直接选择排序；4）快速排序；5）归并排序；6）基数排序。
【解答】略。
（2）已知序列{50,18,12,61,8,17,87,25}，请给出采用堆排序对该序列做升序排序时的每一趟结果。
【解答】堆排序过程如下图示：1887 12178255061618712178185025（3）有n个不同的英文单词，它们的长度相等，均为m，若n>>50，m<5，试问采用什么排序方法时间复杂度最小？为什么？【提示】采用基数排序。
基数排序是一种借助多关键码排序思想对单关键码进行排序的方法，它适合n很大，而关键码较小的序列。
本题中英文单词数目n>>50，而单词长度m<5，因此采用基数排序方法最佳。
（4）如果只想得到一个含有n个元素的序列中第k（k<<n）小元素之前的部分排序序列，最好采用什么排序方法？为什么？如有这样一个序列：{57,11,25,36,18,80,22}得到其第3个最小元素之前的部分序列{11,18,22}，使用所选择的算法实现时，要执行多少次比较？< p="">【解答】采用堆排序。
简单选择排序和冒泡排序可以在一趟排序后选出一个最大（或最小）元素，要比较n-1次，选次大元素要再比较n-2次,…其时间复杂度是O(n2)。
当k<<n时，从n个元素中选k 个元素不能使用这种方法。
而快速排序、插入排序、归并排序、基数排序等要等到最后才能确定各元素位置。
只有堆排序，在未结束全部排序前，可以有部分排序结果。
建立堆后，堆顶元素就是最大（或最小）元素，然后，调整堆又选出次大（小）元素。
凡要求在n个元素中选出k(k<2)个最大（或最小）元素，一般均使用堆排序。
因为堆排序建堆比较次数至多不超过4n,对深度为k的堆，在调堆算法中进行的关键字的比较次数至多为2(k-1)次，且辅助空间为O(1)。
</n时，从n个元素中选k个元素不能使用这种方法。
而快速排序、插入排序、归并排序、基数排序等要等到最后才能确定各元素位置。
只有堆排序，在未结束全部排序前，可以有部分排序结果。
建立堆后，堆顶元素就是最大（或最小）元素，然后，调整堆又选出次大（小）元素。
凡要求在n个元素中选出k(k<得到序列{57,11,25,36,18,80,22}的第3个最小元素之前的部分序列{11,18,22}共需14次比较：其中建堆输出11比较8次，调堆输出17和25各需要比较4次和2次。
（5）阅读下列排序算法，并与已学的算法比较，讨论算法中基本操作的执行次数。
void sort(datatype R[], int n){i=1;while(i<n-i+1)< p="">{min=max=1;for(j=i+1;j<=n-i+1;++j)if(r[j].keyelse if(r[j].key>r[max].key) max=j;if(min!=i) {w=r[min];r[min]=r[i];r[i]=w;}if(max!=n-i+1){if (max=i) {w=r[min];r[min]=r[n-i+1];r[N-i+1]=w;}else {w=r[max];r[max]=r[n-i+1];r[N-i+1]=w;}}i++;}}【解答】这是一个双向选择排序算法，每次选择关键码最小的记录放在前面，同时选择关键码最大的记录放在后面。
比较n*(n-1)/2次。
最好情况移动记录0次，最坏情况大约移动记录3n次。
（6）请回答以下关于堆的问题：1）堆的存储结构是顺序的，还是链式的?2）设有一个大顶堆，即堆中任意结点的关键码均大于它的左孩子和右孩子的关键码。
其具有最大值的元素可能在什么地方?3）对n个元素进行初始建堆的过程中，最多做多少次数据比较?【解答】1）堆的存储结构是顺序的。
2）堆顶。
3）不超过4n。
2.算法设计题1．请以单链表为存储结构实现简单选择排序的算法。
【提示】每趟从单链表表头开始，顺序查找当前链值最小的结点。
找到后，插入到当前的有序表区的最后。
void SelectSort (LinkList L)/*设链表L带头结点*/{q=L; /*指向第一数据前驱*/while(q->next!=NULL){pl=q->next;minp=pl; /*minp指向当前已知的最小数*/while(pl->next!=NULL){if(pl->next->datadata)minp=pl->next; /*找到了更小数*/pl=pl->next; } /*继续往下找*/if(minp!=q->next) /*将当前最小数交换到第一个位置上*/{rl=minp->next;minp->next=rl->next;r2=q->next;q->next=r2->next;r1->next=q->next;q->next=r1;r2->next=minp->next;minp->next=r2;}q=q>next;}}2．请以单链表为存储结构实现直接插入排序的算法。
【提示】注意在链式结构上插入元素的实现方式。
LinkList Sort (LinkList L) /* L为带头结点的单链表*/{p=L->next->next; /*p指向第二个结点*/L->next->next=NULL; /*设置L为只含有一个结点的单链表/while(p) /*当结点尚未插入结束时，将结点p逐个插入到单链表L 中去，同时要保持其有序性*/ {s=p->next;pre=L;q=L->next;while (q&&p->data.key > q->data.key){pre=q;q=q->next;}/*寻找插入位置*/p->next=q;pre->next=p; /*插入元素*/p=s;}return(L);}3．编写一个双向冒泡的算法，即相邻两遍向相反方向冒泡。
【提示】注意算法的结束条件。
typedef struct{KeyType key;…}datatype;typedef struct{datatype elem[MAXSIZE];int length;}Stable; /*排序表类型定义*/void Sort(Stable *L){flag=1;j=1;while(flag){flag=0 ;for( i=j ; i<=L->length-j; i++) /*正向冒泡*/if(L->elem[i].key>L->elem[i+1].key ){L->elem [i]<=>L->elem[i+1];flag=1;}for (i=L->length-j; i>=j+1; i--) /*反向冒泡*/if(L->elem[i].keyelem[i-1].key){L->elem[i]<=> L->elem[i-1] ;flag=1; }j++;}}4．已知记录序列a[1..n]中的关键字各不相同，可按如下所述实现计数排序：另设数组c[1..n]，对每个记录a[i]，统计序列中关键字比它小的记录个数存于c[i]，则c[i]=0的记录必为关键字最小的记录，然后依c[i]值的大小对a中记录进行重新排列，试编写实现上述排序的算法。
void Sort (datatype *A, datatype *B, int n){int C[n+1] ;for (i=1 ;i<=n; i++) C[i]=0;for (i=1; i<=n ; i++){for (j=1 ; j<=n ; j++)if(A[j].key<="" c[i]="" p="">}for (i=1; i<=n; i++)B[C[i]+1]=A[i] ;}5．已知奇偶交换排序算法如下描述：第一趟对所有奇数的i，将a[i]和a[i+1]进行比较，第二趟对所有偶数的i，将a[i]和a[i+1]进行比较，每次比较时若a[i]>a[i+1]，则将二者交换，以后重复上述二趟过程，直至整个数组有序。
（1）试问排序结束的条件是什么？（2）编写一个实现上述排序过程的算法。
【提示】排序结束的条件是没有交换发生。
void Sort( dataype A[n+1]) /*0号单元不用*/{flag=1;while(flag){flag=0;for(i=1;i+1<=n ; i=i+2) /*奇数i*/if(A[i].key>A[i+1].key ){flag=1;A[i]<=>A[i+1];}for(i=0;i+1<=n ; i=i+2) /*偶数i*/if(A[i].key>A[i+1].key ){flag=1;A[i]<=>A[i+1];}}}6．编写算法，对n个关键字取整数值的记录进行整理，以使得所有关键字为负值的记录排在关键字为非负值的记录之前，要求：（1）采用顺序存储结构，至多使用一个记录的辅助存储空间；（2）算法的时间复杂度为O(n)。
【提示】采用类似快速排序的算法来实现。
void Process (int A[n]){low=0; high=n-1;while(low<high)< p="">{while(low<high&&a[low]<="" p="">while(low<high&&a[high]>0 ) high++;</high&&a[high]> if(low<high)< p="">{A[low]<=>A[high];low++;high--;}}}7．序列的“中值记录”指的是：如果将此序列排序后，它是第n/2个记录。
