数据结构c语言版课后习题答案资料

1、WOR格式绪论n-1+n-2+ ?+ 1= n(n-第1章5 .选择题：CCBDCA6 .试分析下面各程序段的时间复杂度。（1）O（ 1）（2）O （ m*n ）（3）O（ n2）（4） O（ log 3n）（5 ）因为x+共执行了1）/2 ，所以执行时间为 0（ n2）r（6）0（ n ）第2章线性表1 .选择题babadbcabdcddac2 .算法设计题（6 ）设计一个算法，通过一趟遍历在单链表中确定值最大的结点ElemType Max （LinkList L ）if（L->next=NULL） return NULL;pmax=L->next; /假定第一个结点中数据具有最

2、大值p=L->next->next;专业资料整理WOR格式专业资料整理WOR格式while(p != NULL )/如果下一个结点存在if(p->data > pmax->data) pmax=p;p=p->n ext;return pmax->data;(7)设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。void inverse(LinkList &L) /逆置带头结点的单链表Lp=L->next; L->next=NULL;while ( p) q=p->next; / q 指向*p 的

3、后继 p->next=L->next;L->next=p;/ *p插入在头结点之后p = q;、空间(10 )已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为0(n)复杂度为0(1)的算法，该算法删除线性表中所有值为item的数据元素。题目分析在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动(删第专业资料整理WOR格式专业资料整理WOR格式个元素， 第i+1至第n个元素要依次前移)。本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针(i=1 ，j=n )，从两端向中间移动，凡遇到值item的数据元素时，

4、直接将右端元素左移至值为item的数据元素位void Delete ( ElemType A ， int n )II A是有n个元素的一维数组，本算法删除A中所有值为item的元素i=1 ; j=n ;/设置数组低、高端指针(下标)。while ( ivj ) while ( ivj && Ai!=item)i+ ;/若值不为item，左移指针if ( i<j ) while ( i<j && Aj=item)j-;/若右端元素值为item ，指针左移if ( i<j ) Ai+=Aj-;算法讨论因元素只扫描一趟，算法时间复杂度为0(n )。删

5、除元素未使用其它辅助空间，最后线性表中的元素个数是 j。第3章栈和队列1 .选择题CCDAADABCDDDBCB2.算法设计题(2 )回文是指正读反读均相同的字符序列，如“abba ”和abdba “”均是回文，但“ good不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)专业资料整理WOR格式根据提示，算法可设计为：/以下为顺序栈的存储结构定义#define StackSize 100 /假定预分配的 100个元栈空间最多为素typedef char DataType;/假定栈元素的数据类型为字符typedef structDataType dataStackSi

6、ze;int top;SeqStack;int lsHuiwen( char *t)/判断t字符向量是否为回文，若是，返回1,否则返回 0SeqStack s;int i , len;char temp;InitStack( &s);len=strlen(t); / 求向量长度for ( i=0; i<len/2; i+)/将一半字符入栈Push( &s, ti);while( !EmptyStack( &s)/每弹出一个字符与相应字符比较temp=Pop (&s);if( temp!=Si)return 0 ;/ 不等则返回 0专业资料整理WOR格式专业

7、资料整理WOR格式else i+;return 1 ; /比较完毕均相等则返回1tag =(7 )假设以数组 Q m存放循环队列中的元素，同时设置一个标志tag，以tag = 0 和1来区别在队头指针(front )和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue )和删除(dlqueue ) 算法。【解答】循环队列类定义#include <assert.h>template <class Type> classQueue / 循环队列的类定义public:Queue ( int =10 );Queue ( ) dele

8、te Q; void EnQueue ( Type & item );Type DeQueue ();Type GetFront ();void MakeEmpty ( ) front = rear = tag = 0 ; /置空队列int IsEmpty ( ) const return front = rear && tag = 0; /判队列空否int IsFull ( ) const return 列满否front = rear && tag = 1; /判队private:专业资料整理WOR格式int rear, front, tag ;/队尾

9、指针、队头指针和队满标志专业资料整理WOR格式Type *Q;int m;/存放队列元素的数组/队列最大可容纳元素个数构造函数template vclass Type>Queue <Type>: Queue ( int sz ) : rear (0), front (0), tag(O) , m (sz ) /建立一个最大具有 m个元素的空队列。new Type ; Q =massert ( Q != 0 );/创建队列 空间/断言：动态存储分配成功与否插入函数templatevclass Type>void Queue <Type > : EnQueue

10、( Type & item ) assert ( ! IsFull ();rear = ( rear + 1 ) % m;Qrear = item;tag = 1 ;删除函数templatevclass Type>Type QueuevType > : DeQueue ( ) assert ( ! IsEmpty ();/判队列是否不满，满则出错处理/队尾位置进1,队尾指针指示实际队尾位置/进队列/标志改1，表示队列不空/判断队列是否不空，空则出错处理专业资料整理WOR格式专业资料整理WOR格式front = ( front + 1 ) % m; 位置tag = 0;ret

11、urn Qfront;/队头位置进1,队头指针指示实际队头的前一/标志改0, 表示栈不满/返回原队头元素的值读取队头元素函数templatevclass Type>Type QueuevType > : GetFront ( ) assert ( ! IsEmpty ();return Q(front + 1) % m;/判断队列是否不空，空则出错处理/返回队头元素的值第4章串、数组和广义表1 .选择题BBCAB BBCBB ABDCB C2.综合应用题'写出用KMP法求得的每个字符1 )已知模式串 t= abcaabbabcab 对应的next和nextval函数值。式串

12、t 的next 和nextval 值如下:12345678910 11专业资料整理WOR格式专业资料整理WOR格式12t串abcaabbabc abnextj0111223123 45nextvalj011021301105(3 )数组A中，每个元素Ai,j的长度均为32个二进位，行下标从-1到9，列下标从1到11 ，从首地址S开始连续存放主存储器中，主存储器字长为16位。求： 存放该数组所需多少单元？ 存放数组第4列所有元素至少需多少单元？数组按行存放时，兀素A7,4的起始地址是多少？数组按列存放时，元素A4,7的起始地址是多少？每个元素32个二进制位，主存字长16位，故每个元素占2个字长，

13、行下标可平移至1到11。(1)242( 2 )22( 3) s+182( 4) s+142 请将香蕉banana 用工具H( ) Head( )，T( ) Tail() 从L中取出L=(apple,(orange,(strawberry,(banana),peach),pear)H( H( T( H( T( H ( T( L)专业资料整理WOR格式专业资料整理WOR格式（5）写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为 A-Z这26个字母和0-9这10个数字）。void Count （）/统计输入字符串中数字字符和字母字符的个数。 i nt i ，n

14、um36 ； charch ;for ( i = 0 ; i<36; i+) numi =0;/ 初始化while ( ch = getchar () != #')/#'表示输入字符串结束。if ( 0' <=ch<=9)'else if ( A' <=ch<= i=ch 48;numi+; Z') i=ch-65+10;numi+/ 数字字符; / 字母字符for(i=0 ；i<10； i+)/ 输出数字字符的个数printf(“数字 d 的个数=% dn ，” i , numi）；for(i = 10;i&

15、lt;36 ; i+）/ 求出字母字符的个数printf（“字母字符c 的个数=% dn ”，i + 55,numi); /算法结束。第5章树和二叉树1.选择题专业资料整理WOR格式专业资料整理WOR格式ADDCA CCBDC CCACC2 .应用题A B D F C E G H，中序序列：B F D A G E H C(2)设一棵二叉树的先序序列: 画出这棵二叉树。 画出这棵二叉树的后序线索树将这棵二叉树转换成对应的树(或森 林)FGHDH(3)假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别 为0.070.19 ，0.02，0.06 ，0.32，0.03，0.21，0.10

16、试为这8个字母设计赫夫曼编码。 试设计另一种由二进制表示的等长编码方案。 对于上述实例，比较两种方案的优缺点。解：方案1;哈夫曼编码先将概率放大100倍，以方便构造哈夫曼树。w=7,19,2,6,32,3,21,10，按哈夫曼规则：【(2,3)， 6, (7,10)】,? 19, 21,32专业资料整理WOR格式专业资料整理WOR格式192132(28)(17)(11)710 6( 5 )方案比较.宀m1r rirr字母彳良口-对 应厶七TT!出现止百编号编码 S 亠J频率十11000.072000.193411110-144007020065100.32出TlTt子母对应现Zt±r

17、 口厶七TT!编号«编码1频率C C71C000CC A0.07r a r20010.19o0100.024011f0.0651000.3261010.03方案1的WPL2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案 2 的 WPL = 3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3结论：哈夫曼编码优于等长二进制编码专业资料整理WOR格式专业资料整理WOR格式3 .算法设计题以二叉链表作为二叉树的存储结构，编写以下算法：(1)统计二叉树的叶结点个数。

18、int LeafNodeCount(BiTree T)if(T=NULL)return 0;/如果是空树，则叶子结点个数为0else if(T->lchild=NULL&&T->rchild=NULL)return 1;/判断该结点是否是叶子结点(左孩子右孩子都为空)，若是则返回1elsereturn LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);(3 )交换二叉树每个结点的左孩子和右孩子。void ChangeLR(BiTree &T)BiTree temp;if(T->lchild=

19、NULL&&T->rchild=NULL)return;elsetemp = T->lchild;专业资料整理WOR格式专业资料整理WOR格式T->lchild = T->rchild;T->rchild = temp;ChangeLR(T->lchild);ChangeLR(T->rchild);1.选择题CBBBCBABAADCCDDB2 .应用题(1)已知如图6.27 所示的有向图，请给出: 每个顶点的入度和出度； 邻接矩阵； 邻接表； 逆邻接表。专业资料整理WOR格式专业资料整理WOR格式(2)(3)韓表(2)已知如图6.28所

20、示的无向网，请给出: 邻接矩阵； 邻接表； 最小生成树图 6.28无°C3-4曲 5异 5X -X576专业资料整理WOR格式专业资料整理WOR格式TdeT6T-gba 4a -b Jb 9ddc4dTdT5TTc3c5b5c5d73f21rJATTTTe9.h .5f6T4A(3 )已知图的邻接矩阵如6.29探度优先生成树D1Dio00 1 0巾6 .6度优先生成树和广度优先生成树。广攬忧先生成树所示。试分别画出自顶点1出发进行遍历所得的深专业资料整理WOR格式(4 )有向网如图 6.29所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表6.9 。图6.29邻接矩

21、阵占八、i=1i=2i=3i=4i=5i=6151515151515(a,b)(a,c)12(a,d)ooooooJ广Ia,c(a,b)(a,b)(a,b)(a,b)(a,b)121111(a,d)10(a,c,e)(a,c,f)ooa,c,f(a,c,f,d)10(a,c,e)16(a,c,f,g)a,c,f,e(a,c,f,d)16(a,c,f,g)a,c,f,e,d专业资料整理14(a,c,f,d,g)a,c,f,e,d,ga,c,f,e, d,g,bWOR格式终点集查找1.选择题CDCABCCCDCBCADA2 .应用题(1)假定对有序表：(3, 4 , 5, 7 , 24 , 30

22、, 42 , 54 , 63 , 72 , 87 , 95 )进行折半查找，试回答下列问题： 画出描述折半查找过程的判定树； 若查找元素54,需依次与哪些元素比较? 若查找元素90，需依次与哪些元素比较? 假定每个元素的查找概率相等，求查找成功时的平均查找长度。 先画出判定树如下(注： mid= (1+12)/2=6):3 742874 2454729554，需依次 查找元素与90，需依次 查找元素与63, 42，元素比30, 54较；30, 63,87, 95 元素比较;专业资料整理WOR格式专业资料整理WOR格式 求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1 + 2 X

23、 2 + 4X 3=17次；但最后一层未满，不能用 8X 4,只能用5 X 4=20次，所以 ASL = 1/12(17 + 20 ) = 37/123.0812, 7, 17 , 11, 16, 2 , 13 , 9,4，请画出所得到的二叉排序树。717(2)在一棵空的二叉排序树中依次插入关键字序列 为21 ,211162149132,4,7,9,11,12,13,16,17验算方法：用中序遍历应得到排序结果:21017，哈希函数为：H (key ) =key%16。用线性探测(5 )设哈希表的地址范围为法处理冲突，输入关键字序列：(10, 24, 32, 17, 31 , 30, 46 ,

24、 47, 40 , 63, 49),构造哈希表，试回答下列问题：画出哈布表的示意图；若查找关键63，需要依次与哪些关键字进行比字较？若查找关键60，需要依次与哪些关键字比字较？假定每个关键字的查找概率相等，求查找成功时的平均查找长度。专业资料整理WOR格式专业资料整理WOR格式然后顺移，与相比，一共比较了46,47,32,17,636 次！ 查找60,首先要与H(60)=60%16=12号单元内容比较，但因为 12号单元为空(应当有空标记)，所以应当只比较这一次即可。 对于黑色数据元素，各比较1次；共6次；对红色元素则各不相同，要统计移位的位数。“63 ”需要6次，“ 49”需要3次，“ 40

25、 ”需要2次，“ 46”需要3次，“ 47”需要3次，所以 ASL=1/11(6 + 2 + 3X 3+6 ) = 23/11(6 )设有一组关键字(9 , 01 , 23 , 14 , 55 , 20 , 84 , 27),采用哈希函数：H ( key )=key %7,表长为10 ,用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并 计算查找成功的平均查找长度。散列地址0123456789关键字140192384275520比较次数 11123412平均查找长度：ASL succ = ( 1+1+1+2+3+4+1+2 ) /8=15/8以关键字 27 为例：H ( 27

26、 ) =27%7=6 (冲突)H 1= ( 6+1 ) %10=7 (冲突)H2= ( 6+2 2) %10=0 (冲突)H3= (6+3 3) %10=5所以比较了 4 次。专业资料整理WOR格式专业资料整理WOR格式第8章排序1.选择题CDBDCBCDBCBCCCA2 .应用题(1)设待排序的关键字序列为 12, 2 , 16 , 30 , 28 , 10 , 16*, 20 , 6,18，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。 直接插入排序 折半插入排序 希尔排序(增量选取5，3 ，1) 冒泡排序 快速排序 简单选择排序 堆排序 二路归并排序直接插入排序212163

27、0281016*206182121630281016*206182121630281016*206182121628301016*206182101216283016*20618专业资料整理WOR格式210121616*283020618210121616*202830618261012161618202830折半插入排序排序过程同希尔排序（增量选取 5, 3 , 1 ）102166181216*621210181616*2610121616*18冒泡排序21216281016*212161016*20212101616*62101216616*2101

28、261616*2106121616*2610121616*2610121616*快速排序12 62101228306 2610122830203028 （增量选取5）203028（增量选取3）202830（增量选取1）20618306182830182028301820283018202830182028301820283018202830* 20161818* 201628 26 10 12 18 1616*20 28 30 专业资料整理WOR格式1826 1012*161820283016*2 6101216* 1618 2028 301，右子序列递归深度左子序列递归深度为为3简单选择排1221630281016*20618261630281016*