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

软件技术基础习题解答第二章 2.1 什么是数据结构？它对算法有什么影响？ 数据结构是指同一数据对象中各数据元素间存在的关系。 数据结构对算法的影响：算法的实现必须借助程序设计语言中提供的数据类型及其运算。一个算法的效率往往与数据的表达形式有关，因此数据结构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的基本部分，它对程序的质量影响很大。 2.2 何谓算法？它与程序有何区别？ 广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。计算机算法是通过计算机能执行的算法语言来表达的。和程序的区别：一个程序包括两个方面的内容：对数据的描述，即数据结构。 对操作的描述，即算法。 所以算法是程序的一个要素。 2.12试编写算法求已知单链表长度，并考虑表空的情况。 head p = head i = 0 While(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(b<data (head) then next(p)head ;headp;return; qhead While(next(q)nil)and(b>data(next(q)do qhead(q) If(next(q)nil)thennext(p)next(q);next(q)p; Else next(q)p;next(p)nil; return 2.30 设一颗二叉树其中序和后序遍历为 中序：BDCEAFHG 后序：DECBHGFA 答案：ABCDEFHG 2.33给定一组权值W=8,2,5,3,2,17,4,画出由此生成的哈夫曼树。 41 17 24 9 15 4 5 7 8 4 3 2 2 2.34.有一图如题图2.4所示： 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，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，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，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 生成的完全二叉树： 41 62 84 39 79 35 61 15 13 96 83 57 调整成的小堆： 13 15 39 84 79 35 61 62 41 83 96 57 输出13： 96 15 41 35 61 62 83 57 39 84 79 调整成堆： 15 35 41 61 96 39 84 79 83 62 57 输出15： 35 39 84 79 62 41 61 83 57 96 35 调整成堆： 39 62 41 61 83 57 84 79 96 输出35： 39 62 84 79 61 96 41 83 57 调整成堆： 61 62 84 79 96 39 41 83 57 输出39： 79 调整成堆： 41 61 62 96 83 57 84 41 61 62 84 96 57 83 79 84 输出41： 61 62 调整成堆： 57 96 57 61 83 79 79 96 83 84 62 输出57： 84 调整成堆： 输出61： 61 79 62 96 83 61 62 79 84 96 83 83 调整成堆： 62 79 84 96 62 83 79 84 96 输出62： 96 调整成堆： 83 79 84 79 83 96 84 输出79： 84 调整成堆：83 96 83 84 96 输出83： 96 调整成堆： 84 84 96 输出84： 96 输出96： 线性插入排序：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趟：15，83 第04趟：15，83 第05趟：15，83 第06趟：15，83 第07趟：15，83 第08趟：15，83 第09趟：15，83 第10趟：96，83 13，41，13，35，13，35，13，35，13，35，13，35，13，35，13，15，62，84，41，62，41，62，41，57，39，41，39，41，39，41，35，39，35，96，84，96，84，96，62，84，57，62，57，62，57，61，41，57，57，39，57，39，57，39，96，39，84，96，79，84，62，79，61，62，79，61，79，61，79，61，79，61，79，61，96，61，84，96，79，84， 第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 第01趟：83，96 第02趟：84，96 第03趟：84，96 第04趟：84，96 第05趟：84，96 第06趟：84，96 第07趟：84，96 第08趟：84，96 41，13，13，41，13，35，13，35，13，35，13，35，13，35，13，35，62，35，35，62，41，57，41，39，39，41，39，41，39，15，15，39，84，57，57，39，39，62，57，61，57，15，15，57，41，57，41，57，39，79，79，61，61，15，15，62，61，62，61，62，61，62，61，62，61，15，15，83，79，83，79，83，79，83，79，83，79，83，79，83， 第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，61，15，83 41 13 35 15 57 39 61 79 83 62 84 96 第三章 3.1 操作系统的基本功能是什么？它包括哪些部分？ 基本功能： 操作系统应该具有处理器管理，存储管理，设备管理和文件管理功能，同时，为了使用户能方便地使用机器，操作系统还应提供用户接口功能。 构成部分： . 对CPU的使用进行管理的进程调度程序 。 . 对内存分配进行管理的内存管理程序。 . 对输入输出设备进行管理的设备驱动程序。 . 对外存中信息进行管理的文件系统。 3.7 存储管理器的功能是什么？为什么要引入虚拟存储器的概念？虚存的容量由什么决定？ 存储管理的功能主要分为：内存分配、地址转换、存储保护和内存扩充。 虚拟存储器能提供给用户一个比实际内存大得多的存储空间，使用户在编制程序时可以不必考虑存储空间的限制。 虚存的容量受两个条件约束：指令中地址场长度的限制、外存储器容量的限制。 3.12 什么是进程的同步和互斥？什么是临界区？ “同步”是指两个事件的发生存在某种时序上的关系，如果系统中有若干个进程要共同完成某一任务，那么它们相互之间必须协调配合。 “互斥”是指当多个进程要求共享系统中某些硬件或软件资源，而这些资源却又要求排它性使用时，这样往往引起由于多个进程竞争同一资源使运行结果出现问题。 如果在两个进程P1、P2中加入P、V操作后，可以实现对公用变量count的互斥使用。其中P、V之间的程序段称为临界区。 3.16 死锁产生的必要条件是什么？死锁的预防、避免和检测各有什么不同？各举一种相应的方法。 死锁产生的必要条件有：1.所涉及的资源是非共享的；2.进程在等待新资源时，继续占用已分配到的资源；3.一个进程占有的资源不能被别的进程强行抢占；4.一个进程获得的资源同时被另一个进程所请求，从而形成一个进程的循环链。 死锁的预防是研究如何破坏产生死锁的必要条件之一，从而达到不使死锁发生地目的。死锁的避免与死锁的预防区别在于，死锁的预防是严格破坏形成死锁的必要条件之一，使得死锁不在系统中出现。预防方法之一，采用假脱机技术将非共享设备变成共享设备来实现。 而死锁的避免并不严格限制必要条件的存在，因为必要条件存在并不一定产生死锁。而进程推进顺序不当，也可以导致系统发生死锁，因此死锁的避免是考虑万一当死锁有可能出现时，就小心地避免这种情况的最终发生。避免方法有采用相应的银行算法和方法。 死锁的检测和恢复，这是一种变通的方法，它允许死锁的发生，但能在适当时间检测出来，并设法进行恢复。利用化简进程-资源有向图的方法来检测系统在某一特定状态时是否处于死锁状态。 3.22 什么是文件目录？有几种目录结构形式？各有什么特点？ 为了便于对文件进行存取和管理，所有计算机系统都设置一个文件目录，每个文件目录中都有一个表目，存放描述该文件的有关信息。 通常有一级目录、二级目录和多级目录结构。 一级目录：把系统中所有文件都建立在一张目录表中，整个目录结构是一个线性表，所以查找的时间会增加，不允许用户对不同的文件取相同的名字，主要用于单用户的操作系统中。 二级目录：在主目录文件中每一个用户有一个表目，指出各用户文件目录的所在位置，而各用户文件目录才指出其所属各具体文件的描述信息，不同用户的文件可以起相同的名字。 多级目录：是树形结构，每一个结点出来的分支可以是文件，也可以是下一级，在一定时间内以某一级目录作为当前目录，用户只需从“当前目录”查看即可。 3章 设备独立性？好处？ 设备独立性，即应用程序独立于具体使用的物理设备。为了实现设备独立性而引入了逻辑设备和物理设备这两个概念。在应用程序中， 使用逻辑设备名称来请求使用某类设备；而系统在实际执行时， 还必须使用物理设备名称。因此，系统须具有将逻辑设备名称转换为某物理设备名称的功能，这非常类似于存储器管理中所介绍的逻辑地址和物理地址的概念。 优点：在实现了设备独立性的功能后， 可带来以下两方面的好处。 1) 设备分配时的灵活性 2) 易于实现I/O重定向 3)X窗口系统是个分布的，网络透明的，独立于设备的多任务窗口和图形系统，它采用顾客/服务员模式，把画窗工作分面二部分，从而取得了设备独立性，它提供了在网络上传送图形信息的标准协议，X窗口系统是网络图形工作站和高档PC机理想的窗口系统。 4.7 (5)查询工程号J1提供零件号P1的供应商SNO Select SNO from SPJ Where PNO=p1 And JNO=j1 (6)查询提供零件名PN3的供应商SNO Select sno from spj inner join part on spj.pno=part.pname='pn3' group by sno (7)查询供应商S提供的零件名 Select pname from part inner join spj on spj.pno=part.pno,and spj.sno='S3' group by pname (8)查询为工程号和提供零件的供应商号 Select SNO from SPJ Where JNO=j1 Or JNO=j2 (10)取出上海供应商为在上海的工程提供零件的所有供应商号SNO Select JNAME from J,S,P,SPJ Where J.JNO=SPJ.NO And SPJ.SNO=S.SNO And S.city=上海 And p.city=上海 (11)取出北京供应商不提供红色零件的供应商号SNO Select SN from SPJ Where JN in ( select JN from J Where city=北京 ) And PN in (select PN from P Where color<>红色 ) (12)取出至少一种由供应商提供零件的工程号 SELECT JN FROM SPJ WHERE SN='S1' 4.8工厂产品生产管理系统 工人与产品管理子系统 名称 工种 工资 性能参数 代号 姓名 代号 产品 m 生产 n 工人产品与零件、材料资管理系统 零件名 代号 产地 名称 性能参数 代号 零件 n m 组装 m 组装 产品 n n 组装 材料 m 代号 库存名称单价 零件与材料子系统 代号 零件名 库存产地 名称 代号 材料 零件 组装 名称 汇总ER图 代号 工资 工种 姓名 代号 n 生产 m 工人 产品 n m 组装 组装 m n n m 零件 材料 组装 代号 产地 代号 零件名 名称 单价 性能参数 库存 单价