《《软件技术基础》习题解答(共20页)》由会员分享，可在线阅读，更多相关《《软件技术基础》习题解答(共20页)（20页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上第二章2.1 什么是数据结构？它对算法有什么影响？ 数据结构是指同一数据对象中各数据元素间存在的关系。 数据结构对算法的影响：算法的实现必须借助程序设计语言中提供的数据类型及其运算。一个算法的效率往往与数据的表达形式有关，因此数据结构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的基本部分，它对程序的质量影响很大。2.2 何谓算法？它与程序有何区别？广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。计算机算法是通过计算机能执行的算法语言来表达的。和程序的区别：一个程序包括两个方面的内容：（1）对数据的描述，即数据结构。（2）对操作的描述，即算法
2、。所以算法是程序的一个要素。2.12试编写算法求已知单链表长度，并考虑表空的情况。p = headi = 0While(p!=nil) /表不为空P- next(p)/移动到下一个元素i+End(while)Return i /返回数据的个数2.14 已知一循环链表中数值已按递增有序排列现要插入一个新结点，并使插入一个新节点，并使插入后链表仍为有序序列Link ST (head ,b) Get node (p);data(p)b; If(head=nil) then headhead;headp;return; If(bdata(next(q)do qhead(q) If(next(q)nil
3、)thennext(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作广度优先搜索:2.42 对给定的一组关键字：41，62，13，84，35，96，57，39，79，61，15，83.2.42 对于给定的一组关键字：41，62，13，84，35，96，57
4、，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，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，6
5、1，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，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，834113628435965739796
6、11583生成的完全二叉树：134115393583578479616296调整成的小堆： 9641153935835784796162输出13：1541353961835784799662调整成堆：62413539618357847996输出15：35413962618357847996调整成堆：964139626183578479输出35：394161629683578479调整成堆：调整成堆：7941616296835784输出39：4157616296837984调整成堆：84576162968379输出41：57796162968384调整成堆：847961629683输出57：61
7、7962849683调整成堆：输出61：83796284966279838496调整成堆：96798384输出62：79968384调整成堆：输出79：849683839684调整成堆：9684输出83：8496输出96：96输出84：线性插入排序：41，62，13，84，35，96，57，39，79，61，15，83第01趟：41，62，13，84，35，96，57，39，79，61，15，83第02趟：13，41，62，84，35，96，57，39，79，61，15，83第03趟：13，41，62，84，35，96，57，39，79，61，15，83第04趟：13，35，41，62，84，
8、96，57，39，79，61，15，83第05趟：13，35，41，62，84，96，57，39，79，61，15，83第06趟：13，35，41，57，62，84，96，39，79，61，15，83第07趟：13，35，39，41，57，62，84，96，79，61，15，83第08趟：13，35，39，41，57，62，79，84，96，61，15，83第09趟：13，35，39，41，57，61，62，79，84，96，15，83第10趟：13，15，35，39，41，57，61，62，79，84，96，83第11趟：13，15，35，39，41，57，61，62，79，83，84，96
9、冒泡排序：41，62，13，84，35，96，57，39，79，61，15，83第01趟：41，13，62，35，84，57，39，79，61，15，83，96第02趟：13，41，35，62，57，39，79，61，15，83，84，96第03趟：13，35，41，57，39，62，61，15，79，83，84，96第04趟：13，35，41，39，57，61，15，62，79，83，84，96第05趟：13，35，39，41，57，15，61，62，79，83，84，96第06趟：13，35，39，41，15，57，61，62，79，83，84，96第07趟：13，35，39，15，41，
10、57，61，62，79，83，84，96第08趟：13，35，15，39，41，57，61，62，79，83，84，96第09趟：13，15，35，39，41，57，61，62，79，83，84，96第10趟：13，15，35，39，41，57，61，62，79，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，83 x=41第一次划分：15，39，13，35，41，96，57，84，79，61，62，83二叉排序树：41，62，13，84，35，96，57，39，79，6
11、1，15，83416213843596573979611583第三章3.1 操作系统的基本功能是什么？它包括哪些部分？ 基本功能： 操作系统应该具有处理器管理，存储管理，设备管理和文件管理功能，同时，为了使用户能方便地使用机器，操作系统还应提供用户接口功能。 构成部分： （1）. 对CPU的使用进行管理的进程调度程序 。 （2）. 对内存分配进行管理的内存管理程序。 （3）. 对输入输出设备进行管理的设备驱动程序。（4） . 对外存中信息进行管理的文件系统。3.7 存储管理器的功能是什么？为什么要引入虚拟存储器的概念？虚存的容量由什么决定？存储管理的功能主要分为：内存分配、地址转换、存储保护和
12、内存扩充。虚拟存储器能提供给用户一个比实际内存大得多的存储空间，使用户在编制程序时可以不必考虑存储空间的限制。虚存的容量受两个条件约束：指令中地址场长度的限制、外存储器容量的限制。3.12 什么是进程的同步和互斥？什么是临界区？ “同步”是指两个事件的发生存在某种时序上的关系，如果系统中有若干个进程要共同完成某一任务，那么它们相互之间必须协调配合。“互斥”是指当多个进程要求共享系统中某些硬件或软件资源，而这些资源却又要求排它性使用时，这样往往引起由于多个进程竞争同一资源使运行结果出现问题。如果在两个进程P1、P2中加入P、V操作后，可以实现对公用变量count的互斥使用。其中P（s）、V（s）之间的程序段称为临界区。3.16 死锁产生的必要条件是什么？死锁的预防、避免和检测各有什么不同？各举一种相应的方法。死锁产生的必要条件有：1.所涉及的资源是非共享的；2.进程在等待新资源时，继续占用已分配到的资源；3.一个进程占有的资源不能被别的进程强行抢占；4.一个进程获得的资源同时被另一个进程所请求，从
