《南邮_数据结构作业答案讲解》由会员分享，可在线阅读，更多相关《南邮_数据结构作业答案讲解（49页珍藏版）》请在金锄头文库上搜索。
1、第一章 习题讲解 1-19.确定下列各程序段的程序步，确定划线语句的执行次数 ，计算它们的渐近时间复杂度。 (1) i=1; k=0;do k=k+10*i; i+; while(i=(y+1)*(y+1) y+; 划线语句的执行次数为 n1/2 ,渐近时间复杂度为O(n1/2)DateDate2 22-4Loc(Aijk)=134+(i*n*p+j*p+k)*2第二章 习题讲解DateDate3 32-9. 设有长度为n 的一维整型数组A，设计一个算法，将原数 组中的元素以逆序排列void Invert(T elements, int length) /length数组长度 /element
2、s为需要逆序的数组 T e;for (int i=1;iLink; p-Link=first; first=p; p=q; return first; DateDate5 53-1. 设A，B，C，D，E五个元素依次进栈（进栈 后可立即出栈），问能否得到下列序列。若能得 到，则给出相应的push和pop序列；若不能，则 说明理由。 （1）A，B，C，D，E（1）能得到该序列。 相应的push和pop序列为：push(A); pop(); push(B); pop(); push(C); pop(); push(D); pop(); push(E); pop(); 第三章 习题讲解DateDat
3、e6 63-1. 设A，B，C，D，E五个元素依次进栈（进栈 后可立即出栈），问能否得到下列序列。若能得 到，则给出相应的push和pop序列；若不能，则 说明理由。 （2）A，C，E，B，D（2）不能得到该序列，在E出栈时，B和D在栈 中，B比D先进栈，所以D应比B先出栈。第三章 习题讲解DateDate7 7（3）不能得到该序列，在C出栈时，A和B在栈中 ，A比B先进栈，所以B应比A先出栈。 3-1. 设A，B，C，D，E五个元素依次进栈（进栈 后可立即出栈），问能否得到下列序列。若能得到 ，则给出相应的push和pop序列；若不能，则说 明理由。 （3）C，A，B，D，EDateDate
4、8 8（4）能得到该序列。 相应的push和pop序列为：push(A); push(B); push(C); push(D); push(E); pop(); pop(); pop(); pop(); pop();3-1. 设A，B，C，D，E五个元素依次进栈（进栈 后可立即出栈），问能否得到下列序列。若能得到 ，则给出相应的push和pop序列；若不能，则说 明理由。 （4）E，D，C，B，ADateDate9 9第四章 习题讲解4-1. 设线性表采用顺序表示方式，并假定顺序表是 有序的（设表中元素已按非递减次序排列）。编写 函数，实现线性表的如下运算： （1）int Search_Ins
5、ert(List *lst,T x) 后置条件：在有序的顺序表中搜索元素x。 若x在表中，则返回x在表中的位置。 否则，若表未满，则在表中插入新元素x，并且插入 后，线性表仍然是有序的，返回新元素x的位置； 若表已满，无法插入新元素，则返回-1。DateDate1010int Search_Insert(List *lst, T x) int i,j;for(i=0; (xlst-Elementsi)i+);/ 查找首个大于等于x的元素位置，并记录在i中if (lst-Elementsi=x) return i;/x在表中时，返回x的位置if (IsFull(lst) /或if(lst-Siz
6、e=lst-maxList) return -1; /表已满时，无法插入，返回-1for (j=lst-Size-1; j=i; j-) lst-Elementj+1=lst-Elementj;lst-Elementi=x; /新元素即插入位置i处lst.Size+;return i;/插入新元素并返回该元素的位置 DateDate11114-1. 设线性表采用顺序表示方式，并假定顺序表是 有序的（设表中元素已按非递减次序排列）。编写 函数，实现线性表的如下运算： （2）void Search_Delete(List *lst, T x,T y) 前置条件：xSize=0) printf(“T
7、he list is empty”);return -1; int i,j,sum=0;for (i=0;tempin-1) return;/没有符合条件的元素 for (j=i;lstjy) /大于y的元素前移 lsti+=lstj+; else/小于等于y的元素删除 j+; n-; DateDate13134.6 给出下列稀疏矩阵的行优先和列优先顺序存储 的行三元组和列三元组表示。列三元组： 4.7 求对题图4-1的稀疏矩阵执行矩阵转置时数组 num和k的值。 col01234 numcol 10212kcol01134行三元组： DateDate14146-2. 对于三个结点A，B和C，
8、可分别组成多少不同 的无序树、有序树和二叉树？（1）无序树：9棵（2）有序树：12棵（3）二叉树：30棵3棵6棵6棵6棵各6棵第六章 习题讲解DateDate15156-3. 设在度为m的树中，度为1，2，m的节点 个数分别为n1,n2,nm，求叶子节点的数目。设度为0的节点个数为n0则： 树的总度数=节点总个数-1 即：1*n1+2*n2+m*nm =n0+ n1+n2+n3+.+ nm-1 因此叶子节点数目为：n0=n2+2*n3+.+ (m-1)nm+1DateDate16166-5. 找出所有二叉树，其节点在下列两种次序下 恰好都以同样的次序出现： （1）先序和中序；（2）先序和后序；
9、（3）中 序和后序（1）或者为空二叉树，或者所有结点的左子树都 是空的单支树 （2）或者为空二叉树，或者只有根结点的二叉树 （3）或者为空二叉树，或者所有结点的右子树都 是空的单支树DateDate17176-6. 设对一棵二叉树进行中序遍历和后序遍历的结果 分别为： （1）中序遍历 （B D C E） A （F H G ）（2）后序遍历 （D E C B）（H G F） A 画出该二叉树。ABFCDEGHDateDate18186-7 写出下图中二叉树的先序、中序和后序遍历结果先序：DEHFJGCKAB中序：HEJFGKCDAB后序：HJKCGFEBADDEAFJGBCHKDateDate1
10、919int SizeL(BTree Bt) return SizeofLeaf(Bt.Root); int SizeofLeaf(BTNode *p) if(!p) return 0;if( (!(p-RChild)return SizeofLeaf(p-LChild)+SizeofLeaf(p-RChild); 6-8.设二叉树以二叉链表存储，试编写求解下列问 题的递归算法： （3）求一棵二叉树中的叶结点个数；DateDate2020（4）设计算法，交换一棵二叉树中每个结点的左 、右子树。void ExchBt(BTree Bt) Exch(Bt.Root); void Exch(BTNo
11、de *p) if (p) BTNode *q=p-LChild; p-LChild=p-RChild; p-RChild=q; Exch(p-LChild);Exch(p-RChild); DateDate21216-13. 将上图中的树转换成二叉树，并将下图中的二 叉树转换成森林。DateDate22226-18. 设S=A,B,C,D,E,F，W=2,3,5,7,9,12， 对字符集合进行哈夫曼编码，W为各字符的频率 （1）画出哈夫曼树 （2）计算带权路径长度 （3）求各字符的编码A:1010 B:1011 C:100 D:00 E:01 F:11加权路径长度：WPL=(2+3)4+53
12、+(7+9+12)2=91 DateDate23237-4为什么说对半搜索算法只适用于顺序有序表的 情况？为什么说顺序搜索可用于顺序表和链表， 也不受表的有序性限制？解：解： 1 1、对半搜索对半搜索算法必须针对顺序存储的有序表，要算法必须针对顺序存储的有序表，要 求满足两个条件：求满足两个条件：1 1）顺序存储，只有顺序存储才可以根据元素下）顺序存储，只有顺序存储才可以根据元素下 标（地址）随机存取元素；标（地址）随机存取元素；2 2）有序存储，只有有序存储才可以其实现对半）有序存储，只有有序存储才可以其实现对半 查找。查找。 2 2、顺序搜索顺序搜索从头到尾逐个查找，所以可用于顺序从头到尾
13、逐个查找，所以可用于顺序 表和链表，也不受表的有序性限制。表和链表，也不受表的有序性限制。DateDate2424补充：已知（1，2，3，4，5，6，7，8，9，10 ，11）找到9比较几次？解：解： 第一次比较：第一次比较：M=(1+11)/2=6M=(1+11)/2=6，6, , , , , , , , , 的次序，通过使用程序10-4的Add函数 插入这些边，建立该图的邻接表结构。请画出所建成 的邻接表结构。524130 0 5 0 123450 3 4 4 0 2 1 1012345DateDate343410-4 已知有向图的邻接表，写出计算各个顶点的入 度的算法。void Degr
14、ee(Graph g, int *d) int i;int n=g.Vertices;Enode* p;for (i=0;inextArc)dp-adjVex+;for (i=0;in;i+) cout“d“i“=“di;DateDate353510-6 在题10-2所建立的邻接表上进行以顶点2为起 点顶点的深度优先搜索和宽度优先搜索。分别画出 遍历所得到的深度优先搜索和宽度优先搜索的生成 森林（或生成树）。5241300 5 0 123450 3 4 4 0 2 1 1012345题10-2所建立的邻 接表对应的图为：DateDate3636以顶点2为起点顶点的深度优先 搜索所得到深度优先搜
15、索生成树 ：0 5 0 123450 3 4 4 0 2 1 1012345524130深度优先遍历：2，4，5，0，1，3DateDate3737以顶点2为起点顶点的宽度优先 搜索所得到宽度优先搜索生成树 ：5241300 5 0 123450 3 4 4 0 2 1 1012345宽度优先遍历：2，4，1，5，0，3DateDate383810-14 使用普里姆算法以1为源点，画出图10-27的 无向图的最小代价生成树。4250311721569242503117215Prim算法以1为源点，生成的最小代价生成树为：DateDate393911-2 设有记录序列：61，87，12，03，08，70， 97，75，53，26。现按下列算法对它分别进行排 序，请手工模拟算法的执行过程，给出每趟排序结 果。 （1）直接插入排序 （3）冒泡排序 （4）快速排序 （5）简单选择排序DateDate4040（1）直接插入排序 初始序列（61）87 12 03 08 70 97 75 53 26 第1趟 （61 87）12 03 08 70 97 75 53 26 第2趟 （12 61 87）03 08 70 97 75 53 26 第3趟 （03 12 61 8
