《软件技术基础》习题解答.doc

《《软件技术基础》习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章2.1什么是数据结构？它对算法有什么影响？数据结构是指同一数据对象中各数据元素间存在的关系。数据结构对算法的影响：算法的实现必须借助程序设计语言中提供的数据类型及其运算。一个算法的效率往往与数据的表达形式有关，因此数据结构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的基本部分，它对程序的质量影响很大。2.2何谓算法？它与程序有何区别？广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。计算机算法是通过计算机能执行的算法语言来表达的。和程序的区别：一个程序包括两个方面的内容：（1）对数据的描述，即数据结构。（2）对操作的描述，即算法。所以算法是程

2、序的一个要素。2.12试编写算法求已知单链表长度，并考虑表空的情况。p=headi=0While(p!=nil)//表不为空P<--next(p)//移动到下一个元素i++End(while)Returni//返回数据的个数2.14已知一循环链表中数值已按递增有序排列现要插入一个新结点，并使插入一个新节点，并使插入后链表仍为有序序列LinkST(head,b){Getnode(p);data(p)←b;If(head=nil)then{head←head;head←p;return;}If(b

3、rn;}q←headWhile(next(q)≠nil)and(b>data(next(q)))doq←head(q)If(next(q)≠nil)then{next(p)←next(q);next(q)←p;}Else{next(q)←p;next(p)←nil;}return}2.30设一颗二叉树其中序和后序遍历为中序：BDCEAFHG后序：DECBHGFA答案：ABCDEFHG2.33．给定一组权值W={8,2,5,3,2,17,4},画出由此生成的哈夫曼树。411724915547843222.34.有一图如题图2.4所示：（2）V1作深度优先搜索:V1作广度优先搜

4、索:2.42对给定的一组关键字：41，62，13，84，35，96，57，39，79，61，15，83.2.42对于给定的一组关键字：41，62，13，84，35，96，57，39，79，61，15，83。分别写出：插入排序、简单选择排序、堆排序、冒泡排序、快速排序、二叉排序树的排序过程，并对各排序方法进行分析。简单选择排序：41，62，13，84，35，96，57，39，79，61，15，83第一趟：13，62，41，84，35，96，57，39，79，61，15，83第二趟：13，15，41，84，35，96，57，39，79，61，62，83第三趟：13，15，35，

5、84，41，96，57，39，79，61，62，83第四趟：13，15，35，39，41，96，57，84，79，61，62，83第五趟：13，15，35，39，41，96，57，84，79，61，62，83第六趟：13，15，35，39，41，57，96，84，79，61，62，83第七趟：13，15，35，39，41，57，61，84，79，96，62，83第八趟：13，15，35，39，41，57，61，62，79，96，84，83第九趟：13，15，35，39，41，57，61，62，79，96，84，83第十趟：13，15，35，39，41，57，61，62，79

6、，83，84，96第11趟：13，15，35，39，41，57，61，62，79，83，84，96堆排序：41，62，13，84，35，96，57，39，79，61，15，83411362843596573979611583生成的完全二叉树：134115393583578479616296调整成的小堆：9641153935835784796162输出13：1541353961835784799662调整成堆：62413539618357847996输出15：35413962618357847996调整成堆：964139626183578479输出35：39416162968

7、3578479调整成堆：调整成堆：7941616296835784输出39：4157616296837984调整成堆：84576162968379输出41：57796162968384调整成堆：847961629683输出57：617962849683调整成堆：输出61：83796284966279838496调整成堆：96798384输出62：79968384调整成堆：输出79：849683839684调整成堆：9684输出83：8496输出96：96输出84：线性插入排序：41，62，13，84，35，96，5