数据结构c语言版课后习题答案完整版.pdf

第 1 章绪论5选择题： CCBDCA6试分析下面各程序段的时间复杂度1）O （1）（2）O （m*n）（3）O （n2）（4）O （log3n）（5）因为 x+共执行了n-1+n-2+ 1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第 2 章线性表1选择题babadbcabdcddac 2算法设计题（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点ElemType Max (LinkList L ) if(L-next=NULL) return NULL; pmax=L-next; 法设计题（2）回文是指正读反读均相同的字符序列，如“abba”和 “abdba”均是回文， 但“good”不是回文试写一个算法判定给定的字符向量是否为回文 提示：将一半字符入栈)?根据提示，算法可设计为：合应用题（1）已知模式串t= abcaabbabcab 写出用KMP法求得的每个字符对应的next和nextval函数值模式串 t 的 next 和 nextval值如下：j1 2 3 4 5 6 7 8 9 10 11 12 t 串a b c a a b b a b c a b nextj 0 1 1 1 2 2 3 1 2 3 4 5 nextvalj 0 1 1 0 2 1 3 0 1 1 0 5 （3）数组 A中，每个元素Ai,j的长度均为32 个二进位 , 行下标从 -1 到 9，列下标从1 到 11，从首地址S开始连续存放主存储器中，主存储器字长为16 位。

求： 存放该数组所需多少单元 存放数组第4 列所有元素至少需多少单元 数组按行存放时，元素A7,4 的起始地址是多少 数组按列存放时，元素A4,7 的起始地址是多少每个元素 32 个二进制位，主存字长16 位，故每个元素占2 个字长，行下标可平移至1到 111）242 （2）22 （3） s+182 （4）s+142 (4) 请将香蕉banana 用工具 H( )Head( ) ，T( ) Tail( )从 L 中取出L=(apple,(orange,(strawberry,(banana),peach),pear) H（H（T（H（ T（H（T（L） ） ） ） ） ） ）（5）写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z 这 26 个字母和0-9 这 10 个数字）void Count （）/ 统计输入字符串中数字字符和字母字符的个数int i ，num36 ；char ch ；for （i 0；i36 ； i+ ）numi ； / 初始化while （ （chgetchar （） ） != # ） / #表示输入字符串结束if （ 0=ch=9 ） i=ch 48;numi+； / 数字字符elseif （ A=ch=Z ） i=ch-65+10;numi+； / 字母字符for （i=0 ； i10 ；i+ ） / 输出数字字符的个数printf（ “数字 d 的个数 dn ” ，i ， numi ） ；for （i 10；ilchild=NULL&T-rchild=NULL) return 1; /判断该结点是否是叶子结点（左孩子右孩子都为空），若是则返回 1 else return LeafNodeCount(T-lchild)+LeafNodeCount(T-rchild); （3）交换二叉树每个结点的左孩子和右孩子。

void ChangeLR(BiTree &T)BiTree temp;if(T-lchild=NULL&T-rchild=NULL)return;elsetemp = T-lchild;T-lchild = T-rchild;T-rchild = temp;ChangeLR(T-lchild);ChangeLR(T-rchild);第6章图1选择题CBBBCBABAADCCDDB2应用题（1）已知如图所示的有向图，请给出： 每个顶点的入度和出度； 邻接矩阵； 邻接表； 逆邻接表2）已知如图所示的无向网，请给出： 邻接矩阵； 邻接表； 最小生成树ab4c3ba4c5d5e9ca3b5d5h5db5c5e7f6g5 h4eb9d7f3fd6e3g2gd5f2h6hc5d4g6图无向网6456252363794567555553955434（3）已知图的邻接矩阵如所示试分别画出自顶点1 出发进行遍历所得的深度优先生成树和广度优先生成树4）有向网如图所示， 试用迪杰斯特拉算法求出从顶点a 到其他各顶点间的最短路径，完成表D终点i=1i=2i=3i=4i=5i=6b15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)c2(a,c)d12(a,d)12(a,d)11(a,c,f,d)11(a,c,f,d)e10(a,c,e)10(a,c,e)f6(a,c,f)g16(a,c,f,g)16(a,c,f,g)14(a,c,f,d,g)S终点集a,ca,c,fa,c,f,ea,c,f,e,da,c,f,e,d,ga,c,f,e,d,g,b图邻接矩阵第 7 章查找1选择题CDCABCCCDCBCADA 2应用题（1）假定对有序表： （3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题： 画出描述折半查找过程的判定树； 若查找元素54，需依次与哪些元素比较 若查找元素90，需依次与哪些元素比较 假定每个元素的查找概率相等，求查找成功时的平均查找长度。

先画出判定树如下（注：mid=?(1+12)/2?=6）：305 633 7 42 87 4 24 54 72 95 查找元素54，需依次与30, 63, 42, 54 元素比较；查找元素90，需依次与30, 63,87, 95元素比较；求 ASL之前，需要统计每个元素的查找次数判定树的前3 层共查找12243=17次；但最后一层未满，不能用84，只能用54=20 次，所以 ASL 1/12 （1720） 37/12 （2）在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树 127 17 2 11 16 21 4 9 13验算方法：用中序遍历应得到排序结果： 2,4,7,9,11,12,13,16,17，21（5）设哈希表的地址范围为017，哈希函数为：H（key） =key%16 用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49） ，构造哈希表，试回答下列问题： 画出哈希表的示意图； 若查找关键字63，需要依次与哪些关键字进行比较 若查找关键字60，需要依次与哪些关键字比较 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

画表如下：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32 17 63 49 24 40 10 30 31 46 47 查找 63, 首先要与H(63)=63%16=15 号单元内容比较，即63 vs 31 ,no; 然后顺移，与46,47,32,17,63相比，一共比较了6 次！查找 60, 首先要与H(60)=60%16=12 号单元内容比较，但因为12 号单元为空（应当有空标记） ，所以 应当只比较这一次即可对于黑色数据元素，各比较1次；共 6 次；对红色元素则各不相同，要统计移位的位数63”需要 6 次， “49”需要 3 次， “40”需要2 次， “46”需要 3 次， “ 47”需要 3 次，所以 ASL=1/11（ 6233+6） 23/11（6）设有一组关键字 （9，01，23，14，55，20，84，27） ，采用哈希函数： H （key）=key %7 ，表长为10，用开放地址法的二次探测法处理冲突要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度散列地址0 1 2 3 4 5 6 7 8 9 关键字14 01 9 23 84 27 55 20 ? ? 比较次数1 1 1 2 3 4 1 2 ? ? 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8 以关键字 27 为例： H（27）=27%7=6 （冲突） H1=（6+1）%10=7 （冲突）H2=（6+22）%10=0 （冲突） H3=（6+33）%10=5 所以比较了4 次。

第 8 章排序1选择题CDBDCBCDBCBCCCA2应用题（1）设待排序的关键字序列为12 ，2，16，30，28，10，16* ，20，6，18 ，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态 直接插入排序 折半插入排序 希尔排序（增量选取5，3， 1） 冒泡排序 快速排序 简单选择排序 堆排序 二路归并排序直接插入排序2 12 16 30 28 10 16* 20 6 18 2 12 16 30 28 10 16* 20 6 18 2 12 16 30 28 10 16* 20 6 18 2 12 16 28 30 10 16* 20 6 18 2 10 12 16 28 30 16* 20 6 18 2 10 12 16 16* 28 30 20 6 18 2 10 12 16 16* 20 28 30 6 18 2 6 10 12 16 16* 20 28 30 18 2 6 10 12 16 16* 18 20 28 30 折半插入排序排序过程同 希尔排序（增量选取5，3，1）10 2 16 6 18 12 16* 20 30 28 （增量选取5）6 2 12 10 18 16 16* 20 30 28 （增量选取3）2 6 10 12 16 16* 18 20 28 30 （增量选取1） 冒泡排序2 12 16 28 10 16* 20 6 18 30 2 12 16 10 16* 20 6 18 28 30 2 12 10 16 16* 6 18 20 28 30 2 10 12 16 6 16* 18 20 28 30 2 10 12 6 16 16* 18 20 28 30 2 10 6 12 16 16* 18 20 28 30 2 6 10 12 16 16* 18 20 28 302 6 10 12 16 16* 18 20 28 30 快速排序12 6 2 10 12 28 30 16* 20 16 18 6 2 6 10 12 28 30 16* 20 16 18 28 2 6 10 12 18 16 16* 20 28 30 18 2 6 10 12 16* 16 18 20 28 30 16* 2 6 10 12 16* 16 18 20 28 30左子序列递归深度为1，右子序列递归深度为3 简单选择排序2 12 16 30 28 10 16* 20 6 18 2 6 16 30 28 10 16* 20 12 18 2 6 10 30 28 16 16* 20 12 18 2 6 10 12 28 16 16* 20 30 18 2 6 10 12 16 28 16* 20 30 18 2 6 10 12 16 16* 28 20 30 18 2 6 10 12 16 16* 18 20 30 28 2 6 10 12 16 16* 18 20 28 30 2 6 10 12 16 16* 18 20 28 30 二路归并排序2 12 16 30 10 28 16 * 20 6 18 2 12 16 30 10 16* 20 28 6 18 2 10 12 16 16* 20 28 30 6 18 2 6 10 12 16 16* 18 20 28 30 堆排序第一步 , 形成初始大根堆（详细过程略），第二步做堆排序。

初始排序不是大根堆形成初始大根堆交换 1 与 10 对象从 1 。