数据结构(c语言版-)课后习题'答案完整编辑资料.doc

《数据结构(c语言版-)课后习题'答案完整编辑资料.doc》由会员分享，可在线阅读，更多相关《数据结构(c语言版-)课后习题'答案完整编辑资料.doc（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 1 章 绪论5选择题：CCBDCA 6试分析下面各程序段的时间复杂度。 （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; /假定第一个结点中数据具有最大值p=L-next-next; whil

2、e(p != NULL )/如果下一个结点存在if(p-data pmax-data) pmax=p; p=p-next; return pmax-data;（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表 的存储空间。void inverse(LinkList L-next=NULL;while ( p) q=p-next; / q 指向*p 的后继p-next=L-next;L-next=p; / *p 插入在头结点之后p = q;（10）已知长度为 n 的线性表 A 采用顺序存储结构，请写一时间复杂度为 O(n)、空间 复杂度为 O(1)的算法，该算法删除线性

3、表中所有值为 item 的数据元素。 题目分析 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第 i 个元素，第 i+1 至第 n 个元素要依次前移） 。本题要求删除线性表中所有值为 item 的数 据元素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针（i=1，j=n） ，从 两端向中间移动，凡遇到值 item 的数据元素时，直接将右端元素左移至值为 item 的数据 元素位置。 voidvoid Delete（ElemType A ，intint n） A 是有 n 个元素的一维数组，本算法删除 A 中所有值为 item 的元素。 i=1；j=n；设置数组低、高端

4、指针（下标） 。whilewhile（itemplate class Queue /循环队列的类定义public: Queue ( int=10 );Queue ( ) delete Q; void EnQueue ( Type Type DeQueue ( );Type GetFront ( );void MakeEmpty ( ) front = rear = tag = 0; /置空队列int IsEmpty ( ) const return front = rear /判队列空否int IsFull ( ) const return front = rear /判队列满否private

5、:int rear, front, tag;/队尾指针、队头指针和队满标志Type *Q;/存放队列元素的数组int m;/队列最大可容纳元素个数构造函数template Queue: Queue ( int sz ) : rear (0), front (0), tag(0), m (sz) /建立一个最大具有 m 个元素的空队列。Q = new Typem;/创建队列空间assert ( Q != 0 );/断言: 动态存储分配成功与否插入函数template void Queue : EnQueue ( Type /判队列是否不满，满则出错处理rear = ( rear + 1 ) %

6、m;/队尾位置进 1, 队尾指针指示实际队尾位置Qrear = item;/进队列tag = 1;/标志改 1，表示队列不空删除函数template Type Queue : DeQueue ( ) assert ( ! IsEmpty ( ) );/判断队列是否不空，空则出错处理front = ( front + 1 ) % m;/队头位置进 1, 队头指针指示实际队头的前一位置tag = 0;/标志改 0, 表示栈不满return Qfront;/返回原队头元素的值读取队头元素函数template Type Queue : GetFront ( ) assert ( ! IsEmpty (

7、 ) );/判断队列是否不空，空则出错处理return Q(front + 1) % m;/返回队头元素的值第 4 章 串、数组和广义表1选择题 BBCAB BBCBB ABDCB C 2.综合应用题 （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 bnextj0 1 1 1 2 2 3 1 2 3 4 5nextvalj0 1 1 0 2 1 3 0 1 1

8、0 5（3）数组 A 中，每个元素 Ai,j的长度均为 32 个二进位,行下标从-1 到 9，列下标 从 1 到 11，从首地址 S 开始连续存放主存储器中，主存储器字长为 16 位。求： 存放该数组所需多少单元？ 存放数组第 4 列所有元素至少需多少单元？ 数组按行存放时，元素 A7,4的起始地址是多少？ 数组按列存放时，元素 A4,7的起始地址是多少？ 每个元素 32 个二进制位，主存字长 16 位，故每个元素占 2 个字长，行下标可平移至 1 到 11。 （1）242 （2）22 （3）s+182 （4）s+142(4)请将香蕉 banana 用工具 H( )Head( )，T( )Ta

9、il( )从 L 中取出。L=(apple,(orange,(strawberry,(banana),peach),pear) H（H（T（H（T（H（T（L） ） ） ） ） ） ）（5）写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字 符串中的合法字符为 A-Z 这 26 个字母和 0-9 这 10 个数字）。voidvoid Count（） /统计输入字符串中数字字符和字母字符的个数。 intint i，num36； charchar ch；forfor（i0；ilchild=NULL /判断该结点是否是叶子结点（左孩子右孩子都为空） ，若是 则返回 1else r

10、eturn LeafNodeCount(T-lchild)+LeafNodeCount(T-rchild); （3）交换二叉树每个结点的左孩子和右孩子。 void ChangeLR(BiTree if(T-lchild=NULL else temp = T-lchild; T-lchild = T-rchild; T-rchild = temp; ChangeLR(T-lchild); ChangeLR(T-rchild); 第 6 章图1选择题 CBBBCBABAADCCDDB 2应用题 （1）已知如图6.27 所示的有向图，请给出： 每个顶点的入度和出度； 邻接矩阵； 邻接表； 逆邻接表。

11、 （2）已知如图6.28 所示的无向网，请给出： 邻接矩阵； 邻接表； 最小生成树ab4c3ba4c5d5e9ca3b5d5h5db5c5e7f6g5h4eb9d7f3fd6e3g2gd5f2h6hc5d4g6图 6.28 无向网6456252363794567555553955434（3）已知图的邻接矩阵如 6.29 所示。试分别画出自顶点 1 出发进行遍历所得的深度 优先生成树和广度优先生成树。（4）有向网如图 6.29 所示，试用迪杰斯特拉算法求出从顶点 a 到其他各顶点间的最短路径，完成表 6.9。 D终点i=1i=2i=3i=4i=5i=6b15(a,b)15(a,b)15(a,b)

12、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图 6.29 邻接矩阵第 7 章 查找1选择题CDCABCCCDCBCADA 2 2应用应用题题 （1）假定对有序表：（假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查）进行折半查 找，试回答下列

13、问题：找，试回答下列问题： 画出描述折半查找过程的判定树；画出描述折半查找过程的判定树； 若查找元素若查找元素 54，需依次与哪些元素比较？，需依次与哪些元素比较？ 若查找元素若查找元素 90，需依次与哪些元素比较？，需依次与哪些元素比较？ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。假定每个元素的查找概率相等，求查找成功时的平均查找长度。 先画出判定树如下（注：mid=(1+12)/2=6）：30 5 633 7 42 874 24 54 72 95查找元素 54，需依次与 30, 63, 42, 54 元素比较； 查找元素 90，需依次与 30, 63,87, 95 元素比较；

14、 求 ASL 之前，需要统计每个元素的查找次数。判定树的前 3 层共查找 12243=17 次；但最后一层未满，不能用 84，只能用 54=20 次， 所以 ASL1/12（1720）37/123.08（2）在一棵空的二叉排序树中依次插入关键字序列为在一棵空的二叉排序树中依次插入关键字序列为 12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。，请画出所得到的二叉排序树。12 7 172 11 16 21 4 9 13 验算方法： 用中序遍历应得到排序结果： 2,4,7,9,11,12,13,16,17，21（5）设哈希表的地址范围为设哈希表的地址范围为 017，哈希

15、函数为：，哈希函数为：H（key）=key%16。用线性探测法。用线性探测法 处理冲突，输入关键字序列：（处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49） ，构造哈，构造哈 希表，试回答下列问题：希表，试回答下列问题： 画出哈希表的示意图；画出哈希表的示意图； 若查找关键字若查找关键字 63，需要依次与哪些关键字进行比较？，需要依次与哪些关键字进行比较？ 若查找关键字若查找关键字 60，需要依次与哪些关键字比较？，需要依次与哪些关键字比较？ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。假定每个关键字的查找概率相等，求查找成功时的平均查

16、找长度。 画表如下：012345678910111213141516173217634924401030314647查找 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”需要

17、 3 次， “47”需要 3 次， 所以 ASL=1/11（6233+6）23/11（6）设有一组关键字（设有一组关键字（9 9，0101，2323，1414，5555，2020，8484，2727） ，采用哈希函数：，采用哈希函数：H H（keykey）=key=key %7%7 ，表长为，表长为 1010，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希 表，并计算查找成功的平均查找长度。表，并计算查找成功的平均查找长度。散列地址0123456789 关键字140192384275520 比较次数1112 3 4

18、12 平均查找长度：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选择题 CDBDCBCDBCBCCCA 2应用题 （1）设待排序的关键字序列为12，2，16，30，28，10，16*，20，6，18，试分别 写出使用以下排序方法，每趟排序结束后关键字序列的状态。 直接插入排序 折半插入排序 希尔排序（增量选取 5，3，1） 冒泡排序 快速排序 简单选择排序 堆排序 二路归并排序

19、直接插入排序 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

20、 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

21、 16 16* 18 20 28 30 2 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

22、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

23、 2 6 10 12 16 16* 18 20 28 30 堆排序 第一步,形成初始大根堆（详细过程略） ，第二步做堆排序。1221620103016*28618302816102016*182126初始排序 不是大根堆 形成初始大根堆1228162102016*18630282016101216*182306交换交换 1 与与 10 对象对象 从 1 到 9 重新形成堆620162101216*182830201816101216*623028交换交换 1 与与 9 对象对象 从 1 到 8 重新形成堆2181620101216*6283018121610216*12203028交换交换 1

24、 与与 8 对象对象 从 1 到 7 重新形成堆16*121620102186283016*1216102186203028交换交换 1 与与 7 对象对象 从 1 到 6 重新形成堆1012162016*2186283016121016*2186203028交换交换 1 与与 6 对象对象 从 1 到 5 重新形成堆612102016*2181628301261016*21816203028交换交换 1 与与 5 对象对象 从 1 到 4 重新形成堆126102016*1218162830106216*121816203028交换交换 1 与与 4 对象对象 从 1 到 3 重新形成堆261

25、02016*1218162830621016*121816203028交换交换 1 与与 3 对象对象 从 1 到 2 重新形成堆26102016*1218162830261016*121816203028交换交换 1 与与 2 对象对象 得到结果3算法设计题（1）试以单链表为存储结构，实现简单选择排序算法。voidvoid LinkedListSelectSort(LinkedList head) /本算法一趟找出一个关键字最小的结点，其数据和当前结点进行交换;若要交换指针，则 须记下 /当前结点和最小结点的前驱指针p=head-next; while(while(p!=null)q=p-next; r=p; /设 r 是指向关键字最小的结点的指针whilewhile (q!=null)(q!=null)if(q-datadata) r=q;q:=q-next; if(r!=if(r!=p) r-datap-data;p=p-next;