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

第二章 什么是数据结构？它对算法有什么影响？ 数据结构是指同一数据对象中各数据元素间存在的关系。 数据结构对算法的影响：算法的实现必须借助程序设计语言中提供的数据类型及其运算。一个算法的效率往往与数据的表达形式有关，因此数据结构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的基本部分，它对程序的质量影响很大。 谓算法？它与程序有何区别？ 广义地说，为解决一个问题而采取的方法和步骤，就称为 “算法 ”。计算机算法是通过计算机能执行的算法语言来表达的。 和程序的区别：一 个程序包括两个方面的内容： （ 1）对数据的描述，即数据结构。 （ 2）对操作的描述，即算法。 所以算法是程序的一个要素。 编写算法求已知单链表长度，并考虑表空的情况。 p = i = 0 p!=(q)do q q) If(q)p) q);q) p; q) p;p) 一颗二叉树其中序和后序遍历为 中序： 序： 答案： 定一组权值 W=8,2,5,3,2,17,4,画出由此生成的哈夫曼树。 41 24 17 15 9 8 7 3 4 4 5 2 2 示： （ 2） 深度优先搜索 : 广度优先搜索 : 给定的一组关键字： 41， 62， 13， 84， 35， 96， 57， 39， 79， 61， 15，83. 于给定的一组关键字： 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 13 62 84 35 96 57 39 79 61 15 83 生成的完全二叉树： 13 41 15 39 35 83 57 84 79 61 62 96 调整成的小堆： 96 41 15 39 35 83 57 84 79 61 62 输出 13： 15 41 35 39 61 83 57 84 79 96 62 调整成堆： 62 41 35 39 61 83 57 84 79 96 输出 15： 96 41 39 62 61 83 57 84 79 输出 35： 35 41 39 62 61 83 57 84 79 96 调整成堆： 39 41 61 62 96 83 57 84 79 调整成堆： 79 41 61 62 96 83 57 84 输出 39： 84 57 61 62 96 83 79 输出 41： 41 57 61 62 96 83 79 84 57 79 61 62 96 83 84 调整成堆： 调整成堆： 84 79 61 62 96 83 输出 57： 83 79 62 84 96 61 79 62 84 96 83 62 79 83 84 96 调整成堆： 输出 61： 调整成堆： 96 79 83 84 输出 62： 84 96 83 96 84 输出 83： 96 输出 84： 79 96 83 84 83 96 84 84 96 调整成堆： 输出 79： 调整成堆： 调整成堆： 输出 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 趟： 13， 41， 62， 84， 35， 96， 57， 39， 79， 61，15， 83 第 04 趟： 13， 35， 41， 62， 84， 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 冒泡排序： 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， 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，61， 15， 83 41 62 13 84 35 96 57 39 79 61 15 83 第三章 操作系统的基本功能是什么？它包括哪些部分？ 基本功能： 操作系统应该具有处理器管理，存储管理，设备管理和文件管理功能，同时，为了使用户能方便地使用机器，操作系统还应提供用户接口功能。 构成部分： （ 1） . 对 使用进行管理的进程调度程序 。 （ 2） . 对内存分配进行管理的内存管理程序。 （ 3） . 对输入输出设备进行管理的设备驱动程序。 （ 4） . 对外存中信息进行管理的文件系统。 存储管理器的功能是什么？为什么要引入虚拟存储器的概念？虚存的容量由什么决定？ 存储管理的功能主要分为：内存分配、地址转换、存储保护和内存扩充。 虚拟存储器能提供给用户一个比实际内存大得多的存储空间，使用户在编制程序时可以不必考虑存储空间的限制。 虚存的容量受两个条件约束：指令中地址场长度的限制、外存储器容量的限制。 什么是进程的同步和互斥？什么是临界区？ “同步 ”是指两个事件的发生存在某 种时序上的关系，如果系统中有若干个进程要共同完成某一任务，那么它们相互之间必须协调配合。 “互斥 ”是指当多个进程要求共享系统中某些硬件或软件资源，而这些资源却又要求排它性使用时，这样往往引起由于多个进程竞争同一资源使运行结果出现问题。 如果在两个进程 、 V 操作后，可以实现对公用变量互斥使用。其中 P（ s）、 V（ s）之间的程序段称为临界区。 死锁产生的必要条件是什么？死锁的预防、避免和检测各有什么不同？各举一种相应的方法。 死锁产生的必要条件有： 续占用已分配到的资源； 而形成一个进程的循环链。 死锁的预防是研究如何破坏产生死锁的必要条件之一，从而达到不使死锁发生地目的。死锁的避免与死锁的预防区别在于，死锁的预防是严格破坏形成死锁的必要条件之一，使得死锁不在系统中出现。预防方法之一，采用假脱机技术将非共享设备变成共享设备来实现。 而死锁的避免并不严格限制必要条件的存在，因为必要条件存在并不一定产生死锁。而进程推进顺序不当，也可以导致 系统发生死锁，因此死锁的避免是考虑万一当死锁有可能出现时，就小心地避免这种情况的最终发生。避免方法有采用相应的银行算法和方法。 死锁的检测和恢复，这是一种变通的方法，它允许死锁的发生，但能在适当时间检测出来，并设法进行恢复。利用化简进程 什么是文件目录？有几种目录结构形式？各有什么特点？ 为了便于对文件进行存取和管理，所有计算机系统都设置一个文件目录，每个文件目录中都有一个表目，存放描述该文件的有关信息。 通常有一级目录、二级目录和多 级目录结构。 一级目录：把系统中所有文件都建立在一张目录表中，整个目录结构是一个线性表，所以查找的时间会增加，不允许用户对不同的文件取相同的名字，主要用于单用户的操作系统中。 二级目录：在主目录文件中每一个用户有一个表目，指出各用户文件目录的所在位置，而各用户文件目录才指出其所属各具体文件的描述信息，不同用户的文件可以起相同的名字。 多级目录：是树形结构，每一个结点出来的分支可以是文件，也可以是下一级，在一定时间内以某一级目录作为当前目录，用户只需从 “当前目录 ”查看即可。 3 章 设备独立性？好处？ 设备 独立性，即 应用程序 独立于具体使用的 物理设备 。为了实现 设备 独立性而引入了逻辑设备和 物理设备 这两个概念。在 应用程序 中， 使用逻辑 设备 名称来请求使用某类设备；而系统在实际执行时， 还必须使用 物理设备 名称。因此，系统须具有将逻辑 设备 名称转换为某 物理设备 名称的功能，这非常类似于 存储器管理 中所介绍的 逻辑地址 和 物理地址的概念。 优点： 在实现了 设备 独立性的功能后， 可带来以下两方面的好处。 1) 设备 分配时的灵活性 2) 易于实现 I/O 重定向 3)X 窗口系统是个分 布的，网络透明的，独立于 设备 的多任务窗口和 图形系统 ，它采用顾客 /服务员模式，把画窗工作分面二部分，从而取得了设备独立性，它提供了在网络上传送图形信息的标准协议， X 窗口系统是网络图形工作站和高档 理想的窗口系统。 5)查询工程号 供零件号 供应商 (6)查询提供零件名 供应商 on by 7)查询供应商 on by 8)查询为工程号和提供零件的供 应商号 (10)取出上海供应商为在上海的工程提供零件的所有供应商号 ,S,P,上海 上海 (11)取出北京供应商不提供红色零件的供应商号 N N N 北京 ) N N 红色 ) (12)取出至少一种由供应商提供零件的工程号 N N=厂