严飞_《软件技术基础》沈被娜习题解答

第二章 什么是数据结构？它对算法有什么影响？ 数据结构是指同一数据对象中各数据元素间存在的关系。 数据结构对算法的 影响：算法的实现必须借助程序设计语言中提供的数据类型及其运算。一个算法的效率往往与数据的表达形式有关，因此数据结构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的基本部分，它对程序的质量影响很大。 谓算法？它与程序有何区别？ 广义地说，为解决一个问题而采取的方法和步骤，就称为 “算法 ”。计算机算法是通过计算机能执行的算法语言来表达的。 和程序的区别：一 个程序包括两个方面的内容： （ 1） 对数据的描述，即数据结构。 （ 2） 对操作的描述，即算法。 所以算法是程序的一个要素。 何谓频度，时间复杂度，空间复杂度？说明其含义。 频度：在某个算法中某个语句被重复执行的次数就是此语句的频度。 时间复杂度：是用来估算一个算法的执行时间的量，以算法中频度最大的语句来度量。 空间复杂度：指在算法中所需的辅助空间的单元，而不包括问题的原始数据占用的空间。 编写一个求多项式 值 Pn(x 0)的算法，要求用乘法次 数最少，并说明算法中主要语句的执行次数及整个算法的时间复杂度。 A=(a n) 1 / a0 i=1 to n x / x Ai* /求和 i) 进行了 n 次 时间复杂度为： 2n 算下列各片段程序中 X X+1 执行次数 (1) i=1 to n j=1 to i k=1 to j x x+1 k) j) i) 执行次数： n*n*n (2) i 1 i=c / 找到第 1 个大于等于 c 的元素 s = i t = -1 Li d / 找到第 1 个大于 d 的元素 t = i ; i) s != -1 t !=-1 i = s i n A 字符串中第 i 个字符开始的子串与 B 匹配 ) i) 找不到匹配的子串 ) 设 A， B 两个线性表的元素个数为 m， n -;/ -;/ - / / / T=T-; /2) 在这里要对一种情况进行说明 当 左子树与 左子树相同， 右子树与 右子树相同时，这两颗二叉树相同。 当 左子树与 右子树相同， 右子树与 左子树相同时，这两颗二叉树同样相同。 以下是实现代码 & | = 3） 4） 计算叶子数和树的深度。计算叶子：递归每个节点，当没有左孩子和右孩子时即为叶子。计算深度：对每个节点计算左右子树的深度，节点的最终深度是其子树深度的最大值加 1，空树返回 ; T) 0; T != - - T-= & T-= ; T) T = 1; - - 1 + ( 17,28,36,54,30,27,94,15,21,83,40,画出由此生成的二叉排序树。 解： 17 15 28 27 54 36 94 21 30 40 83 定一组权值 W=8,2,5,3,2,17,4,画出由此生成的哈夫曼树。 示： （ 1）写出此图的邻接表与邻接矩阵； （ 2）由给点 深度优先搜索和广度优先搜索； （ 3） 试说明上述搜索的用途。 17 5 4 3 8 2 2 1 8 12 11 10 9 7 2 3 13 16 17 18 19 20 解：（ 1） 1 2 5 8 2 3 4 2 12 4 3 5 14 5 1 4 6 6 5 7 15 7 6 8 17 1 8 11 7 5 9 8 10 18 10 2 9 11 11 10 12 19 12 3 11 13 13 12 14 20 14 4 13 15 15 6 14 16 1 3 10 （ 2） 深度优先搜索 : 广度优先搜索 : (3)为了避免同一顶点被多次访问。 示： （ 1）写出每一结点的入度和出度各为多少； （ 2）写出上 图的邻接矩阵和邻接表。 解： 度 =3 出度 =0 度 =2 出度 =2 度 =1 出度 =2 1 5 3 6 4 2 16 15 17 20 17 7 16 18 18 9 17 19 19 11 18 20 20 13 16 19 度 =2 出度 =2 度 =2 出度 =1 度 =0 出度 =4 题图 结点 a 到各结点之间最短路径。 2 2 2 2 1 2 3 3 1 4 1 解： 1 2 3 4 5 6 1 4 2 4 5 2 1 6 a b c d e g f h 3 5 1 题图 所示 所有可能的拓扑顺序结果。 解 : 拓扑排序： 5-4-3-8 2 4 6 0 0 0 0 0 1 3 8 6 8 4 8 0 0 0 8 4 2 1 7 3 8 5 4 6 图 示 ，求 : (1) (2) 解 : 活动最早最迟开始时间 a1 a2 a3 a4 a5 a6 a7 a8 a9 0 0 5 6 6 12 12 12 19 19 16 20 23 25 L 4 0 9 6 16 12 19 16 19 19 23 20 23 25 0 4 0 10 0 7 4 0 0 7 0 0 0 事件最早最迟开始时间 2 4 6 8 10 5 6 12 19 16 20 23 25 27 9 6 12 19 23 20 23 25 27 出进行分块查找的数据组织形式。 解 :设将数据分成 4 块，每块中记录个数 5， 先查找索引值 97451 97517 97528 97543 第 1 块 2 3 4 97321,97421,97451, 97241,97118 97250,97407,97239, 97227,97517 97438,97102,97528 97136,07338 97543,97309 一棵对 20 个记录进行对分查找的判定树 ,并求等概率情况下的平均查找长度。 1+2*2+3*4+4*8+5*5)/20=据的存储结构主要有哪两种 ?它们之间的本质区别是什么？ 数据的存储结构：向量和链表。 本质区别： 向量是连续存放的，其存储空间是静态分配的，以存放顺序来表达元素的前后件的关系。 链式存储结果不需要一组连续的存储单元，其数据元素可以分散存放在存储空间中，其元素关系由指针来指向。 比较顺序表和链表的优缺点。 1. 线性表的长度是否固定方面：由于向量的存储空间是静态分配的，链表的存储空间是动态分配的，因此若表长不固定时采用线性链表较好。 2. 线性表的主要操作是什么：由于向量是连续存放的，所以适用于查找操作，不适用插入、删除操作。由于线性链表只能顺序存取，所以适用于插入、删除操作，不适用于查找操作。 3. 采用的算法语言：线性链表要求所使用的语言工具提供指针类型变量。 比较单向链表与双向链表的优缺点。 1. 单向链表只能单方向地寻找表中的结点，双向链表具有对称性，从表中某一给定的结点可随意向前或向后查找。 2. 在作插入、删除运算时，双向链表需同时修改两个方向上的指针，单向链表则简便些。 试说明树与二叉树有何不同？为何要将 一般树转换为二叉树？ 树与二叉树区别：树是由 n 个（ n=0）结点组成的有限集合 T，其中有且仅有一个结点称为根结点，在此类元素结点之间存在明显的分支和层次关系。 二叉树是一种特殊的树结构，每一个结点最多只有两个孩子，即最多只有两个分支。 为何要转换：一般树，树中结点次序没有要求，分支庞杂。而二叉树，元素之间存在严谨的前后代关系，在对数据元素进行删除、查找、插入等运算时更加有效率。 一棵排序二叉树的关键字输入序列为 80， 6， 10， 7， 8， 25， 100， 90，请画出该二叉树。 解：二叉排序树为 ： 80 6 100 90 10 7 25 8 于关键字序列 49， 38， 65， 97， 76， 13，回答下述问题。（共 12 分） （ 1）写出一趟冒泡排序的结果。（ 6 分） （ 2）写出一趟快速排序的结果。 参考答案如下： （ 1）写出一趟冒泡排序的结果。（ 6 分） 38,49,65,76,13,97 （ 2）写出一趟快速排序的结果。（ 6 分） 13,38,49,97,76,65 给出图 1 的所有最小生成树。（ 10 分） 答：共有两颗： a e b d f c 1 2 3 8 6 6 5 图 1 a e b d f c 1 2 3 6 5 a e b d f c 1 2 3 6 6 5 给出图 2 的所有拓扑排序序列。（ 16） 答案如下：仅有两个 第一个： 第二个： 知某二叉树的前序遍历序列为： A B C D E F G 和中序遍历序列为： C B E D A F G。请画出该二叉树。 答案如下： 造该图的最小生成树。 图的最小生成树如下 图 2 a b d f g c e h a e f g d b h c 2 1 1 1 1 2 2 2 2 4 3 第三章 操作系统的基本功能是什么？它包括哪些部分？ 基本功能： 操作系统应该具有处理器管理，存储管理，设备管理和文件管理功能，同时，为了使用户能方便地使用机器，操作系统还应提供用户接口功能。 构成部分： （ 1） . 对 使用进行管理的进程调度程序 。 （ 2） . 对内存分配进行管理的内存管理程序。 （ 3） . 对输入输出设备进行管理的设备驱动程序。 （ 4） . 对外存中信息进行 管理的文件系统。 说明虚拟机的概念以及实现的方法。 在裸机外面每增加一个软件层后就会变成一台功能更强的机器，我们通常把这 种计算机系统称为虚拟机。 虚拟机的实现方法：在裸机上装上操作系统对机器进行首次扩展，再在操作系统的基础上增加其他软件，这样就可以实现 “虚拟机 ”。 常操作系统有哪几种基本类型？各有什么特点及适用于何种场合？ 三大类：（ 1）多道批处理系统：计算机内存中同时可以存放多道作业，用户与作业之间没有交互作用，用户不能直接控制作业的运行。此类系统一般用于计算中心等较大型的计算机系统中 。（ 2）分时系统：多个用户通过终端分享同一台计算机，并通过终端直接控制程序运行，进行人与机器之间的交互。此类系统适用于程序的开发。（ 3）实时系a e f g d b h c 2 1 1 1 1 2 2 统：对外部发生的随机事件作出及时的响应，并对它进行处理。此类系统一般用于工业控制系统或事物处理系统。 说明你所使用过的操作系统的类型和特点。 统：多用户多任务操作系统。 特点：全新的、友善的用户界面。 提供了功能强大的应用程序。 具有多任务并行处理能力，各种应用程序之间可以方便地进行切换和交换信息。 具有强大 的内存管理能力，支持扩展内存功能，提高系统运行效率。 释名空间、作业地址空间和存储空间的关系以及逻辑地址和物理地址的区别。 存放源程序的空间称为名空间。当汇编或编译程序将源程序转换成目标程序后，一个目标程序所占有的地址范围称为地址空间，这些地址的编号是相对于起始地址而定的，一般定起始位零，称为逻辑地址或相对地址。存储空间是指当目标程序装入主存后占用的一系列物理单元的集合，这些单元编号称为物理地址或绝对地址。 什么是重定位？静态重定位和动态重定位的区别是什么？各举一例说明。 当用户程序要调入内存时 ，必须把相对地址转换为绝对地址，同时要包括对程序中与地址有关的指令进行修改，这一过程称为重定位。静态重定位是在程序装入时进行，一般通过处理机中一对界地址寄存器来实现。动态重定位是在程序执行过程中进行的，当处理器访问主存指令时由动态变换机构自动进行地址转换。 存储管理器的功能是什么？为什么要引入虚拟存储器的概念？虚存的容量由什么决定？ 存储管理的功能主要分为：内存分配、地址转换、存储保护和内存扩充。 虚拟存储器能提供给用户一个比实际内存大得多的存储空间，使用户在编制程序时可以不必考虑存储空间的限制。 虚存的容量受两个条件约束：指令中地址场长度的限制、外存储器容量的限制。 什么是作业、作业步和进程？ 作业是用户在一次算题过程中或一个事务处理中要求计算机系统所做的集合。 一个作业是由一系列有序的作业步所组成。一个作业步运行的结果产生下一个作业步所需的文件。 进程可以看成是程序的一次执行，即是在指定内存区域的一组指令序列的执行过程。 处理器管理主要解决什么问题？ 在大型通用系统中，可能数百个批处理作业存放在磁盘中，又有数百个终端用户与主机联接，如何从这些作业中挑选一些作业进入主存运行 ，又如何在主存各进程间分配处理器，是操作系统资源管理的一个重要问题，处理器管理就是用来解决此问题的。 什么是进程的同步和互斥？什么是临界区？ “同步 ”是指两个事件的发生存在某种时序上的关系，如果系统中有若干个进程要共同完成某一任务，那么它们相互之间必须协调配合。 “互斥 ”是指当多个进程要求共享系统中某些硬件或软件资源，而这些资源却又要求排它性使用时，这样往往引起由于多个进程竞争同一资源使运行结果出现问题。 如果在两个进程 、 V 操作后，可以实现对公用变量互斥使用。其中 P（ s）、 V（ s）之间的程序段称为临界区。 进程间的通信可以由哪些方式进行？ 低级通信方式： 作。 高级通信方式：直接通信、信箱通信。 死锁产生的必要条件是什么？死锁的预防、避免和检测各有什么不同？各举一种相应的方法。 死锁产生的必要条件有： 续占用已分配到的资源； 而形成一个进程的循环链。 死锁的预防是研究如何破坏产生死锁的必要条件之 一，从而达到不使死锁发生地目的。死锁的避免与死锁的 预防区别在于，死锁的 预防是严格破坏形成死锁的必要条件之一，使得死锁不在系统中出现。预防方法之一，采用假脱机技术将非共享设备变成共享设备来实现。 而死锁的避免并不严格限制必要条件的存在，因为必要条件存在并不一定产生死锁。而进程推进顺序不当，也可以导致系统发生死锁，因此死锁的避免是考虑万一当死锁有可能出现时，就小心地避免这种情况的最终发生。避免方法有采用相应的银行算法和方法。 死锁的检测和恢复，这是一种变通的方法，它允许死锁的发生，但能在适当时间检测出来，并设法 进行恢复。利用化简进程 通道、控制器和设备的各种不同连接方式各有什么特点？ 第一种连接方式（书中图 a）：控制器与设备是一一对应的，当系统对某设备提出申请时， 设备号及有关操作要求传递给通道，由通道启动该设备，并完成对该设备的操作。 第二种连接方式（书中图 b）：是一个控制器控制若干个设备，只有当被申请的设备及相应的控制器均为空闲状态时才能启动。 第三种连接方式（书中图 c）：是同道、控制器与设备交 叉连接，提高了控制的灵活性，但必须在相应的设备、控制器、同道均为空闲时才能工作。 什么是 “瓶颈 ”问题？引入缓冲区为何可以解决这一问题？ 系统中的独占类型设备，只能由单个作业独占，这样使其他需要改设备的进程由于等待设备而被阻塞，称为系统的 “瓶颈 ”。 缓冲技术是指在内存中划出一个由 n 个单元组成的区域，称为缓冲区，作为外部设备在进行数据传输时的暂存区。引入缓冲技术的根本原因是 据处理速度与设备传输数据速度不相匹配，利用缓冲区来缓解其间的速度矛盾，减少瓶颈现象。 设备管理的功能是什么？ 怎样把一台物理设备虚拟为多台设备？ 设备管理的功能：设备驱动程序； 即插即用； 通用即插即用； 集中、同一管理；添加硬件。 通过虚拟机软件，就可以在一台物理计算机上模拟出一台或多台虚拟的计算机。 什么是记录、文件、文件系统？ 记录：文件由若干个记录组成，每一个记录是一些相关信息的集合。 文件：在逻辑上具有完整意义的数据或字符序列的集合。 文件系统：负责存取和管理文件的机构，又称为文件管理系统。 文件的逻辑结构和物理结构有何区别？文件的存储方 式与文件的存取有何关系？ 文件的逻辑结构是从用户的角度看到的文件面貌，也就是它的记录结构。文件的物理结构是指一个逻辑文件在外存储器上的存放形式。 各种文件应用场合不同，对文件的存取要求也就不同，对应不同的存取方式，对文件的物理结构即存储方式有不同的要求 什么是文件目录？有几种目录结构形式？各有什么特点？ 为了便于对文件进行存取和管理，所有计算机系统都设置一个文件目录，每个文件目录中都有一个表目，存放描述该文件的有关信息。 通常有一级目录、二级目录和多级目录结构。 一级目录：把系统中所有文件都建立 在一张目录表中，整个目录结构是一个线性表，所以查找的时间会增加，不允许用户对不同的文件取相同的名字，主要用于单用户的操作系统中。 二级目录：在主目录文件中每一个用户有一个表目，指出各用户文件目录的所在位置，而各用户文件目录才指出其所属各具体文件的描述信息，不同用户的文件可以起相同的名字。 多级目录：是树形结构，每一个结点出来的分支可以是文件，也可以是下一级，在一定时间内以某一级目录作为当前目录，用户只需从 “当前目录 ”查看即可。 文件的共享与安全保密问题如何解决？ 共享 的实现：通过文件路径实现共享； 通过联接实现共享。 保密问题的解决：采用存取控制矩阵方法； 采用按用户分类的存取控制的方法； 采用口令设置。 什么是文件操作指令？每个命令的具体功能是什么？ 文件操作指令：是指文件系统提供给用户的一系列操作使用命令，其中最基本的命令是查询文件目录。 建立文件：当用户需要将 其信息作为文件保存时，向系统提出建立文件指令，系统按照用户提供的参数为该文件建立一个表目，放入相应的文件目录中。 打开文件：当用户需要访问文件中某个记录时，首先要进行打开文件操作，此时系统将欲访问的文件表目从目录文件调入活动文件表中。 读文件： 把文件中相关的记录从外存储器的文件区中读入主存用户工作区中。 写文件：把用户要求插入、增加或删除的记录写入文件区相应位置。 关闭文件：文件暂时不用时，必须将它 操作系统与用户的接口有几种？各有什么特点？试举例说明你所使用过的接口形式。 通常操作系统为用户提供两种接口：一类是程序接口；另一类是作业控制方面的接口。 程序一级接口是由一组系统调用命令组成，它是操作系统提供给用户的各种服务，以子程序的形式供用户在程序中调用。当程序执行该系统调用命令时便暂时中断当前执行的程序去执行该系统调用命令子程序，完成后自动返回当前执行程序。 作业控制方面的接口与操作系统的类型有关。在批处理系统中，当用户一旦提交了作业，就无法对作业的运行作更多的控制，因此用户必须事先用 该操作系统提供的作业控制语言告诉操作系统对进程的运行意图、资源的需求以及一旦出现问题作何种选择等。对于分时系统，则提供一组操作命令，通常称为语言命令，它采用人机交互回话方式来控制作业的运行。我所使用的 P 操作系统中，用户通过键盘操作，也可以在多窗口图形化环境中通过鼠标器选择各种操作。 第六章 简要回答下列问题： （ 1） 软件生命周期为什么要划分成阶段？应怎样来划分阶段？在软件开发过程中，为什么要强调文档编写？ 在运用工程的方法来进行软件开发时，必须遵守一些工程性的基本原则：分解 、计划、规范。相应的软件工程的一些基本原则包括软件周期的划分，这要求在时间上进行分解，即将软件开发过程分解为一系列的分阶段的任务。这也有利于降低软件开发的难度。 一般来说，软件从产生、发展到淘汰要经历定义、开发和维护三大阶段。具体地来说，即定义阶段的可行性论证与开发计划、需求分析，开发阶段的概要计、详细设计和编码，维护阶段的测试、运行维护。 强调文档的编制是因为它有以下主要作用： a. 作为开发人员在一定阶段内承担任务的工作结果和结束标志。 b. 向管理人员提供软件开发工作的进展情况，白软件开发过程中的一些 “不可见 ”的 事物转换成 “可见 ”的文字资料，以便管理人员在各个阶段检查开发计划的实施情况，使之能够对工作结果进行清晰的审计。 c. 记录开发过程中的技术信息，以便协调工作，并作为下一阶段工作的基础。 d. 提供有关