数据结构(c语言)课后习题参考资料

数据构造(c语言版)课后习题参照完满版资料数据构造(c语言版)课后习题参照完满版资料10/10数据构造(c语言版)课后习题参照完满版资料第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．babadbcabdcddac2．算法6）一个算法，通一趟遍在表中确定最大的点。ElemTypeMax(LinkListL){if(L->next==NULL)returnNULL;pmax=L->next;

法（2）回文是指正反均相同的字符序列，如“abba”和“

abdba”均是回文，但“

good”不是回文。写一个算法判判定的字符向量可否回文。(提示：将一半字符入

)?依照提示，算法可设计为：（1）已知模式串

适用t=‘abcaabbabcab’写出用KMP法求得的每个字符的模式串t的next和nextval以下：

next

和

nextval

函数。j

12

34

56

789

101112t串

ab

c

aab

b

ab

cabnext[j]

01

11

22

31

234

5nextval[j]

01

10

21

30

110

5（3）数A中，每个元素A[i,j]的度均32个二位,行下从-1到9，列下从1到开始存放主存器中，主存器字16位。求：①存放数所需多少元？②存放数第4列所有元素最少需多少元？③数按行存放，元素A[7,4]的初步地址是多少？④数按列存放，元素A[4,7]的初步地址是多少？每个元素32个二制位，主存字16位，故每个元素占2个字，行下可平移至（1）242（2）22（3）s+182（4）s+142(4)将香蕉banana用工具H( )—Head( )，T( )—Tail( )从L中取出。

11，从首地址1到11。

SL=(apple,(orange,(strawberry,(banana)),peach),pear)H（H（T（H（T（H（T（L）））））））（5）写一个算法在入字符串中各个不相同字符出的度并将果存入文件（字符串中的合法字符A-Z26个字母和0-910个数字）。voidCount（）入字符串中数字字符和字母字符的个数。｛inti，num[36]；charch；for（i＝0；i<36；i++）num[i]＝０；//初始化while（（ch＝getchar（））!=‘#’）//‘#’表示入字符串束。if（‘0’<=ch<=‘9’）｛i=ch－48;num[i]++；｝//数字字符elseif（‘A’<=ch<=‘Z’）｛i=ch-65+10;num[i]++；｝//字母字符for（i=0；i<10；i++）//出数字字符的个数printf（“数字％d的个数＝％d\n”，i，num[i]）；for（i＝10；i<36；i++）//求出字母字符的个数printf（“字母字符％c的个数＝％d\n”，i＋55，num[i]）；｝//算法束。第5章树和二叉树1．ADDCACCBDCCCACC2．用（2）一棵二叉的先序序列：ABDFCEGH，中序序列：BFDAGEHC①画出棵二叉。②画出棵二叉的后序索。③将棵二叉成的（或森林）。(1)(2)AC（3）假用于通信的文由8个字母成，字母在文中出的率分，，，，，，，。BMDEMH①8个字母赫夫曼。②另一种由二制表示的等方案。③于上述例，比两种方案的缺点。FG解：方案1；哈夫曼先将概率放大100倍，以方便构造哈夫曼。w={7,19,2,6,32,3,21,10}，按哈夫曼：【[（2,3），6],(7,10)】,⋯⋯19,21,32（100）(3)（40）（60）01192132（28）0101（17）19（11）32217106011201073方案比：1061023字母出字母出号率方案1的WPL＝2+++4+++5+=++=率号11100方案2的WPL＝3+++++++=31000200：哈夫曼于等二制20013．算法3111103010以二叉表作二叉的存构，写以下算法：411104011（1）二叉的叶点个数。5105100intLeafNodeCount(BiTreeT)6{101if(T==NULL)return0;

//

若是是空树，则叶子结点个数为

0elseif(T->lchild==NULL&&T->rchild==NULL)return1;

//

判断该结点是否是叶子结点（左孩子右孩子都为空）

，若是则返回

1elsereturnLeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);}（3）交换二叉树每个结点的左孩子和右孩子。voidChangeLR(BiTree&T){BiTreetemp;if(T->lchild==NULL&&T->rchild==NULL)return;else{temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;}ChangeLR(T->lchild);ChangeLR(T->rchild);}第6章图1．选择题CBBBCBABAADCCDDB2．应用题1）已知以下列图的有向图，请给出：每个极点的入度和出度；毗邻矩阵；毗邻表；逆毗邻表。2）已知以下列图的无向网，请给出：①毗邻矩阵；②毗邻表；③最小生成树a→b4→c3图无向网b→a4→c5→d5→e9^c→a3→b5→d5→h5^d→b5→c5→e7→f6→g5→h4^e→b9→d7→f3^f→d6→e3→g2^g→d5→f2→h6^h→c5→d4→g6^（3）已知图的毗邻矩阵如所示。试分别画出自极点树。

1出发进行遍历所得的深度优先生成树和广度优先生成（4）有向网以下列图，试用迪杰

斯特拉算法求出从顶点a到其他各极点间的最短路径，完成表。D终i=1i=2i=3i=4i=5i=6点b151515151515(a,b)(a,b)(a,b)(a,b)(a,b)(a,b)c2(a,c)d12121111(a,d)(a,d)(a,c,f,d)(a,c,f,d)e∞1010(a,c,e)(a,c,e)f∞6(a,c,f)g∞∞161614(a,c,f,g)(a,c,f,g)(a,c,f,d,g)S终{a,c}{a,c,f}{a,c,f,e}{a,c,f,e,d}{a,c,f,e,d,g}{a,c,f,e,d,g,b}点集第7章查找1．选择题CDCABCCCDCBCADA2．应用题1）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答以下问题：画出描述折半查找过程的判断树；若查找元素54，需依次与哪些元素比较？③若查找元素90，需依次与哪些元素比较？④假定每个元素的查找概率相等，求查找成功时的平均查找长度。①先画出判断树以下（注：mid=(1+12)/2=6）：30563374287424547295②查找元素54，需依次与30,63,42,54元素比较；③查找元素90，需依次与30,63,87,95元素比较；④求ASL从前，需要统计每个元素的查找次数。判断树的前3层共查找1＋2×2＋4×3=17次；但最后一层未满，不能够用8×4，只能用5×4=20次，所以ASL＝1/12（17＋20）＝37/12≈（2）在一棵空的二叉排序树中依次插入要点字序列为12，7，17，11，16，2，13，9，21，4，请画出所获取的二叉排序树。1271721116214913验算方法：用中序遍历应获取排序结果：2,4,7,9,11,12,13,16,17，215）设哈希表的地址范围为0～17，哈希函数为：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

101112

1314

1516173217

6349

2440

10

30314647②查找

63,第一要与

H(63)=63%16=15号单元内容比较，即

63vs31,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（6＋2＋3×3+6）＝23/116）设有一组要点字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key%7，表长为10，用开放地址法的二次探测法办理矛盾。要求：对该要点字序列构造哈希表，并计算查找成功的平均查找长度。散列地址0123456789要点字140192384275520比较次数11123412平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8以要点字27为例：H（27）=27%7=6（矛盾）H1=（6+1）%10=7（矛盾）22334次。H=（6+2）%10=0（矛盾）H=（6+3）%10=5所以比较了第8章排序1．选择题CDBDCBCDBCBCCCA2．应用题（1）设待排序的要点字序列为{12，2，16，30，28，10，16*，20，6，18}，试分别写出使用以下排序方法，每趟排序结束后要点字序列的状态。①直接插入排序②折半插入排序③希尔排序（增量采用5，3，1）④冒泡排序⑤快速排序⑥简单项选择择排序⑦堆排序⑧二路归并排序①直接插入排序[212]1630281016*20618[21216]30281016*20618[2121630]281016*20618[212162830]1016*20618[21012162830]16*20618[210121616*2830]20618[210121616*202830]618[2610121616*202830]18[2610121616*18202830]②折半插入排序排序过程同①③希尔排序（增量采用5，3，1）102166181216*203028（增量采用5）621210181616*203028（增量采用3）2610121616*18202830（增量采用1）④冒泡排序21216281016*20618[30]212161016*20618[2830]212101616*618[202830]2101216616*[18202830]21012616[16*18202830]210612[1616*18202830]2610[121616*18202830]2610121616*18202830]⑤快速排序12[6210]12[283016*201618]6[2]6[10]12[283016*201618]28261012[181616*20]28[30]18261012[16*16]18[20]283016*26101216*[16]18202830左子序列递归深度为1，右子序列递归深度为3⑥简单项选择择排序2[121630281016*20618]26[1630281016*201218]2610[30281616*201218]261012[281616*203018]26101216[2816*203018]2610121616*[28203018]2610121616*18[203028]2610121616*1820[2830]2610121616*182028[30]⑧二路归并排序2121630102816*2061821216301016*2028618210121616*2028306182610121616*18202830⑦堆排序第一步,形成初始大根堆（详细过程略），第二步做堆排序。1230216281630281016*20181016*206182612初始排序不是大根堆形成初始大根堆12282816201620181016*12181016*26302630交换1与10对象从1到9重新形成堆6202016181612181016*1261016*2283022830交换1与9对象从1到8重新形成堆218181612161261016*2121016*202830202830交换1与8对象从1到7重新形成堆16*16*12161216261018261018202830202830交换1与7对象从1到6重新形成堆1016121612102616*182616*18202830202830交换1与6对象从1到5重新形成堆612121061021616*1821616*18202830202830交换1与5对象从1到4重新形成堆121061062121616*18121616*18202830202830交换1与4对象从1到3重新形成堆26610210121616*18121616*18202830202830交换1与3对象从1到2重新形成堆22610610121616*18121616*1820283020