南邮_数据结构课后习题答案讲解

2020/3/211第一章习题讲解1-19.确定下列各程序段的程序步，确定划线语句的执行次数，计算它们的渐近时间复杂度。(1)i=1;k=0;do{k=k+10*i;i++;}while(i=n-1)划线语句的执行次数为n-1,渐近时间复杂度为O(n)(2）i=1;x=0;do{x++;i=2*i;}while（in）;划线语句的执行次数为log2n,渐近时间复杂度为O(log2n)2020/3/212(3)for(inti=1;i=n;i++)for(intj=1;j=i;j++)for(intk=1;k=j;k++)x++;划线语句的执行次数为n(n+1)(n+2)/6,渐近时间复杂度为O(n3)(4）x=n;y=0;while(x=(y+1)*(y+1))y++;划线语句的执行次数为n1/2,渐近时间复杂度为O(n1/2)2020/3/2132-4．Loc(A[i][j][k])=134+(i*n*p+j*p+k)*2第二章习题讲解2020/3/2142-9.设有长度为n的一维整型数组A，设计一个算法，将原数组中的元素以逆序排列voidInvert(Telements[],intlength)//length数组长度//elements[]为需要逆序的数组{Te;for(inti=1;ilength/2;i++){e=elements[i-1];elements[i-1]=elements[length-i];elements[length-i]=e;}}2020/3/2152-12.设计一个算法，将单链表中结点以逆序排列。逆序的单链表中的结点均为原表中的结点。Node*pInvert(Node*first){Node*p=first,*q;first=NULL;while(p){q=p-Link;p-Link=first;first=p;p=q;}returnfirst;}2020/3/2163-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();第三章习题讲解2020/3/2173-1.设A，B，C，D，E五个元素依次进栈（进栈后可立即出栈），问能否得到下列序列。若能得到，则给出相应的push和pop序列；若不能，则说明理由。（2）A，C，E，B，D（2）不能得到该序列，在E出栈时，B和D在栈中，B比D先进栈，所以D应比B先出栈。第三章习题讲解2020/3/218（3）不能得到该序列，在C出栈时，A和B在栈中，A比B先进栈，所以B应比A先出栈。3-1.设A，B，C，D，E五个元素依次进栈（进栈后可立即出栈），问能否得到下列序列。若能得到，则给出相应的push和pop序列；若不能，则说明理由。（3）C，A，B，D，E2020/3/219（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，A2020/3/2110第四章习题讲解4-1.设线性表采用顺序表示方式，并假定顺序表是有序的（设表中元素已按非递减次序排列）。编写函数，实现线性表的如下运算：（1）intSearch_Insert(List*lst,Tx)后置条件：在有序的顺序表中搜索元素x。•若x在表中，则返回x在表中的位置。•否则，若表未满，则在表中插入新元素x，并且插入后，线性表仍然是有序的，返回新元素x的位置；•若表已满，无法插入新元素，则返回-1。2020/3/2111intSearch_Insert(List*lst,Tx){inti,j;for(i=0;(xlst-Elements[i])&&(ilst-Size);i++);//查找首个大于等于x的元素位置，并记录在i中if(lst-Elements[i]==x)returni;//x在表中时，返回x的位置if(IsFull(lst))//或if(lst-Size==lst-maxList)return-1;//表已满时，无法插入，返回-1for(j=lst-Size-1;j=i;j--)lst-Element[j+1]=lst-Element[j];lst-Element[i]=x;//新元素即插入位置i处lst.Size++;returni;//插入新元素并返回该元素的位置}①②③2020/3/21124-1.设线性表采用顺序表示方式，并假定顺序表是有序的（设表中元素已按非递减次序排列）。编写函数，实现线性表的如下运算：（2）voidSearch_Delete(List*lst,Tx,Ty)前置条件：xy后置条件：删除有序表中元素值在x和y之间（含x和y）的所有元素。2020/3/2113voidSearch_Delete(List*lst,Tx,Ty){if(lst-Size==0){printf(“Thelistisempty”);return-1;}inti,j,sum=0;for(i=0;temp[i]x&∈i++);//找到首个大于等于x的元素位置iif(in-1)return;//没有符合条件的元素for(j=i;lst[j]=y&&jn;j++);//找到首个大于y的元素位置jsum=j-i;while(jn)lst[i++]=lst[j++];//删除sum个元素n=n-sum;}for(j=i;jn;)if(lst[j]y)//大于y的元素前移lst[i++]=lst[j++];else//小于等于y的元素删除{j++;n--;}2020/3/21144.6给出下列稀疏矩阵的行优先和列优先顺序存储的行三元组和列三元组表示。006003000700000008100000090261031473283310449列三元组：10302632833101474494.7求对题图4-1的稀疏矩阵执行矩阵转置时数组num[]和k[]的值。col01234num[col]10212k[col]01134行三元组：2020/3/21156-2.对于三个结点A，B和C，可分别组成多少不同的无序树、有序树和二叉树？（1）无序树：9棵（2）有序树：12棵（3）二叉树：30棵3棵6棵6棵6棵各6棵第六章习题讲解2020/3/21166-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+12020/3/21176-5.找出所有二叉树，其节点在下列两种次序下恰好都以同样的次序出现：（1）先序和中序；（2）先序和后序；（3）中序和后序（1）或者为空二叉树，或者所有结点的左子树都是空的单支树（2）或者为空二叉树，或者只有根结点的二叉树（3）或者为空二叉树，或者所有结点的右子树都是空的单支树2020/3/21186-6.设对一棵二叉树进行中序遍历和后序遍历的结果分别为：（1）中序遍历（BDCE）A（FHG）（2）后序遍历（DECB）（HGF）A画出该二叉树。ABFCDEGH2020/3/21196-7写出下图中二叉树的先序、中序和后序遍历结果先序：DEHFJGCKAB中序：HEJFGKCDAB后序：HJKCGFEBADDEAFJGBCHK2020/3/2120intSizeL(BTreeBt){returnSizeofLeaf(Bt.Root);}intSizeofLeaf(BTNode*p){if(!p)return0;if((!(p-RChild))&&(!(p-LChild)))return1;returnSizeofLeaf(p-LChild)+SizeofLeaf(p-RChild);}6-8.设二叉树以二叉链表存储，试编写求解下列问题的递归算法：（3）求一棵二叉树中的叶结点个数；2020/3/2121（4）设计算法，交换一棵二叉树中每个结点的左、右子树。voidExchBt(BTreeBt){Exch(Bt.Root);}voidExch(BTNode*p){if(p){BTNode*q=p-LChild;p-LChild=p-RChild;p-RChild=q;Exch(p-LChild);Exch(p-RChild);}}2020/3/21226-13.将上图中的树转换成二叉树，并将下图中的二叉树转换成森林。2020/3/21236-18.设S={A,B,C,D,E,F}，W={2,3,5,7,9,12}，对字符集合进行哈夫曼编码，W为各字符的频率（1）画出哈夫曼树（2）计算带权路径长度（3）求各字符的编码A:1010B:1011C:100D:00E:01F:11加权路径长度：WPL=(2+3)×4+5×3+(7+9+12)×2=912020/3/21247-4为什么说对半搜索算法只适用于顺序有序表的情况？为什么说顺序搜索可用于顺序表和链表，也不受表的有序性限制？解：1、对半搜索算法必须针对顺序存储的有序表，要求满足两个条件：1）顺序存储，只有顺序存储才可以根据元素下标（地址）随机存取元素；2）有序存储，只有有序存储才可以其实现对半查找。2、顺序搜索从头到尾逐个查找，所以可用于顺序表和链表，也不受表的有序性限制。2020/3/2125补充：已知（1，2，3，4，5，6，7，8，9，10，11）找到9比较几次？解：第一次比较：M=(1+11)/2=6，69，找[7，11]；第2次比较：M=(7+11)/2=9，9=9，成功。所以一共比较2次成功2020/3/21268-1建立37，45，91，25，14，76，56，65为输入时的二叉搜索树，再从该树上依次删除76，45，则树形分别如何？3725451456659176建成的二叉树2020/3/21278-1建立37，45，91，25，14，76，56，65为输入时的二叉搜索树，再从该树上依次删除76，45，则树形分别如何？37254514566591删除76后2020/3/21288-1建立37，45，91，25，14，76，56，65为输入时的二叉搜索树，再从该树上依次删除76，45，则树形分别如何？372514566591删除45后2020/3/21298-3已知对一棵二叉搜索树进行先序遍历的结果是：28，25，36，33，35，34，43，请画出此二叉搜索树。282536343543332020/3/21309-3设散列表ht[11]，散列函数h(key)=key%11。采用线性探查法、二次探查法解决冲突，试用关键字值序列：70，25，80，35，60，45，50，55分别建立散列表。线性探查法：Keyh(Key)70425380335260545150655005545352570806050123456789102020/3/21319-3设散列表ht[11]，散列函数h(key)=key%11。采用线性探查法、二次探查法解决冲突，试用关键字值序列：70，25，80，35，60，45，50，55分别建立散列表。二次探查法：Keyh(Key)7042538033526054