计算机软件课后答案docx.docx
《计算机软件课后答案docx.docx》由会员分享，可在线阅读，更多相关《计算机软件课后答案docx.docx（27页珍藏版）》请在冰点文库上搜索。
计算机软件课后答案docx
图2.5表达式ci*Q+c/（d~H）—g*h/i—的表示
解：
根据给定的条件，在树T中，各结点射出的分支总数为：
4X1+2X2+1X3+4X1=15
树T中的总结点数为：
15（各结点射出的分支总数）+1（根结点）=16
非叶子结点总数为：
4+2+1+1=8
叶子结点数为，
16（总结点数）一8（非叶子结点总数）=8
2.21已知某二叉树的前序序列为DBACFEG,中序序列为ABCDEFG.试画出该二叉树，并写出该二叉树的后序序列。
解：
由于在前序遍历中首先访问根结点，因此，前序序列中的第一个结点为二叉树的根结点，即D为二叉树的根结点。
又由于在中序遍历中访问根结点的次序为居中，而访问左子树上的结点为居先，访问右子树上的结点为最后，因此，在中序序列中，以根结点
图2.6,表达式fka*（6+c/d）»x!
y»s—£,s*p）的表不
图2.7二叉树的恢复
（D）为分界线，前面的子序列（ABC）一定在左子树中，后面的子序列（EFG）一定在右子树中。
同样的道理，对于已经划分出的每一个子序列的所有结点中，位于前序序列最前面的一个结点为子树的根结点，而在中序序列中位于该根结点前面的结点构成左子树上的结点子序列，位于该根结点后面的结点构成右子树上的结点子序列。
这个处理过程直到所有子序列为空为止•
根据上述道理，诙二叉树恢复的过程如图2.7所示.
后序序列为ACBEGFD。
2.22设一棵完全二叉树具有1000个结点。
问该
完全二叉树有多少个叶子结点？
有多少个度为2的结点？
有多少个度为1的结点？
若完全二又树有1001个结点，再回答上述间题.并说明理由。
解:
在-般的二叉树中，叶子结点总是比度为2的
结点多1个。
而在完全二叉树中，度为1的结点最多有
1个•综合以上两点，如果完全二叉树的结点数为奇数,设为2n+l.则没有度为1个的结点，在所有结点中有”个是度为2的结点，”+1个是叶子结点；如果完全二叉树的结点数为偶数.设为2n,则其中有1个是度为1个的结点，剩下的结点中有”一1个是度为2的结点5个是叶子结点。
在本题中，如果完全二又树共有1000个结点，则有500个叶子结点，499个度为2的结点，有1个度为1的结点.如果完全二叉树共有1001个结点，则有501个叶子结点，500个度为2的结点.没有度为1的结点.
2.24试写出由有值图的求值矩阵生成邻接表的算法
纵向优先搜索法遍历图g：
AHGEECBD横向优先搜索法遍历图g：
2.23ahfdcgeb
前序序列：
1836
12
33
620
2547
LO
中序序列：
33126
36
18
25
47209
后序序列：
33612
36
47
25
92018
6.5有人说：
“软件是不会用坏的，因此，经过测试和调试的软件不需要维护。
”你认为这句话有道理吗？
为什么？
解：
这种说法是错误的。
软件的可理解性、可测试性与可修改性将直接影响和决定软件的可维护性，而且软件生命周期的各个阶段也都与可维护性有关。
良好的设计、完善的文档资料以及一系列严格的复审和测试，都会使错误一旦出现就较为容易诊断和纠正，而且当用户有所要求或外部环境有变化时，软件都比较容易适应，并能减少维护所引起的副作用。
因此，在软件生A田丽质久个阶段都必须充分考虑维护的问题，并且为维护做好准备。
6.2什么是数据流程图？
威偶馄程国日饪rr风住四句><一
解：
数据流程图简称DFDCDataFlowDiagram）,是SA方法最主要的一种图形工具，它从数据加工的角度，以图形方式描述信息处理系统的逻辑结构，能比较直观地描述信息处理中的业务情况.
数据流程图中的数据流完全不同于一般程序流程图（即程序框图）中的控制流。
程序流程图中的控制流只是表示程序执行的次序，在其箭头上没有数据的传递；而数据流程图中的数据流箭头表示有数据沿此箭头流动，并不直接反映加工处理的先后次序。
数据流程图是从数据的角度来描述一个系统。
第a章Mmn
4.1什么是操作系统？
它的主要功能是什么？
解：
操作系统实际上是由一些程序模块组成的，它们是系统软件中最基本的部分，其主要作用有以下几个方面.
<1）管理系统资源，包括对CPU,内存储器、输入/输出设备、数据文件和其他软件资源的管理.
<2）为用户提供资源共享的条件和环境，并对资源的使用进行合理的调度。
（3）提供输入/输出的方便环境，简化用户的输入/输出工作，提供良好的用户界面。
（4）规定用户的接口，发现、处理或报告计算机操作过程中所发生的各种错误。
由此可以看出，操作系统既是计算机系统资源的控制和管理者，又是用户和计算机系统之间的接口，当然它本身也是计算机系统的一部分.因此，概略地说，操作系统是用以控制和管理系统资源、方便用户使用计算机的程序的集合.
如果把操作系统看成是计算机系统资源的管理者，则操作系统的功能和任务主要有以下5个方面。
（1）处理机管理
处理机管理的主要任务是：
充分发挥处理机的作用，提高它的使用效率.
（2）存储器管理
存储器管理的主要任务是：
对有限的内存储器进行合理的分配，以满足多个用户程序运行的需要.
<3）设备管理
设备管理的主要任务是：
有效地管理各种外部设备，使这些设备充分发捧效率，并且还要给用户提供简单而易于使用的接口，以便在用户不了解设备性能的情况下，也能很方便地使用它们。
（4）文件管理
文件管理的主要任务是：
实现唯一地标识计算机系统中的每一组信息，以便能够对它们进行合理的访问和控制；以及有条理地组织这些信息，使用户能够方便且安全地使用它们.
（5）作业管理
作业管理的主要任务是：
对所有的用户作业进行分类，弁且根据某种原则，源源不断地选取一些作业交给计算机去处理。
\
4.2分时系统与实时系统的主要区别是什么？
解：
分时系统是指多个用户分享使用同一台计算机，即在一台计算机上连接若干台终端，每个用户可以独占一台终端•分时系统具有以下几方面的特点'
为进程MAIN提供计算结果y的值.其中形参工与计算结果y分别用各自的缓冲单元存放。
为了正确完成计算并输出结果，它们之间必须是同步工作的。
当计算进程F尚未完成y=f（x）的计算，即还没有把结果y送到缓冲单元之前，进程MAIN在需要使用计算值y时应该等待；一旦计算进程F把计算结果送入缓冲单元中，则应给进程MAIN发出一个通知信号，进程MAIN收到通知信号后，便可以从缓冲单元中取出计算结果•反之,在进程MAIN还未将x值送人缓冲单元之前，计算进程F也不能进行计算；一旦进程MAIN将h值送入缓冲单元中，则应绐计算进程F发出一个通知信号，计算进程F收到通知信号后，便可以从缓冲单元中取出x值进行y=/（x）的计算。
4.10P/V操作与消息缓冲通信有什么共同之处？
又有什么区别？
解：
进程之间为了实现互斥或同步，需要有信息传递，也就是说需要进行通信。
为此.需要一种实现进程之间通信的机构，这种机构通常称为通信原语。
P/V操作属于低级通信原语，消息缓冲通信属于高级通信原语，它们都用于实现进程之间的通信.
P/V操作采用信号同步，发送者只给对方发出一个简单的信号，接收者在收到该信号后，就能够知道其中的含义，从而采取相应的操作。
消息缓冲通信采用信件同步，发送者向对方发出的不是简单的信号，而是一个复杂的信件，接收者收到信件后，要对信件进行分析，然后再采取相应的操作.
4.11存储管理系统有哪些主要功能？
解：
在多道程序系统中，存储管理一般应包括以下功能.
（1）地址变换。
要把用户程序中的相对地址转换成实际内存空间的绝对地址。
（2）内存分配。
根据各用户程序的需要以及内存空间的实际大小，按照一定的策略划分内存，以便分配给各个程序使用。
（3）存储共享与保护•由于各用户程序与操作系统同在内存，因此，一方面允许各用户程序能够共享系统或用户的程序和数据•另一方面又要求各程序之间互不干扰或破坏对方。
（4）存储器扩充。
由于多道程序共享内存,使内存资源尤为紧张，这就要求操作系统根据各时刻用户程序允许的情况合理地利用内存，以便确保当前需要的程序和数据在内存中.而其余部分可以暂时放在外存中，等确实需要时再调入内存。
4.12什么是重定位？
为什么要对程序进行重定位？
解：
在进行地址变换时，必须修改程序中所有与地址有关的项，也就是说，要对程序中的指令地址以及指令中有关地址的部分（称为有效地址）进行调整，这个调整过程称为地址重定位。
用户在编写程序时并不知道自己的程序在执行时放在内存空间的什么区域，因此不可能用内存中的实际地址（称为绝对地址）来编写程序，只能用相对于某个基准地址（通常为0地址）来编写程序、安排指令和数据的位置,这种在用户程序中所用的地址通常称为相对地址.当用户程序进入内存执行时，又必须把用户程序中的所有相对地址转换成内存中的实际地址（称为地址变换），否则用户程序就无法执行。
4.13什么是虚拟存储器？
它的大小受什么限制？
进程与程序有关，但它与程序又有本质的区别，主要反映在以下几个方面。
<1）进程是程序在处理机上的一次执行过程，它是一个动态的概念。
而程序只是一组指令的有序集合，其本身没有任何运行的含义，它是一个静态的概念.
（2）进程是程序的执行过程，是一次运行活动。
因此，进程具有一定的生命期,它能够动态地产生和消亡。
即进程可以由创建而产生，由调度而执行，因得不到资源而暂停.以致最后由撤销而消亡。
也就是说,进程的存在是暂时的.而程序是可以作为一种软件资源长期保存的，它的存在是永久的。
（3）进程是程序的执行过程，因此，进程的组成应包括程序和数据，除此之外，进程还包括由记录进程状态信息的进程控制块。
（4）一个程序可能对应多个进程.
（5）一个进程可以包含多个程序。
4.6进程的3种状态之间是如何转换的？
解：
（1）处于就绪状态的进程，一旦分配到CPU,就转为运行状态。
<2）处于运行状态的进程，当需要等待某个事件发生才能继续运行时，则转为等待状态；或者由于分配给它的时间片用完.就让出CPU而转为就绪状态.
（3>处于等待状态的进程，如果它等待的事件已经发生，即条件得到满足，就转为就绪状态.
进程只能在运行状态下结束.
4.7什么是死锁？
为什么会发生死锁？
解：
多个进程并发执行时共享系统的软硬件资源，而当各进程互相独立地动态获得、不断申请和释放系统中的软硬件资源时.就有可能使系统出现这样一种状态：
其中若干个进程均因互相“无知地”等待对方所占有的资源而无限地等待，这种状态称为死锁。
发生死锁的4个必要条件如下：
（1）资源的独占使用；
（2）资源的非抢占分配，
（3）资源的部分分配；
（4）对资源的循环等待.
4.8进程的互斥与同步有什么区别？
它们之间有什么共同之处？
解：
当多个进程共享数据块或其他排他性模块使用的资源时，不能同时进入存取或使用，但进入的次序可以任意，这些进程之间的这种制约关系称为互斥。
进程之间为了合作完成一个任务,而需要互相等待和互相交换信息的相互制约关系称为同步•
互斥也是一种特殊的同步关系.进程之间为了实现互斥或同步,都需要有信息传递，也就是说需要进行通信•
4.9考虑一个主程序用如下方式调用子程序:
y=f（xK如果把子程序/作为进程实现，则要考虑哪些同步间题？
解：
在本问题中，有两个进程合作完成y=f3>的计算工作，其中与主程序对应的进程（假设为MAIN）为子程序对应的计算进程（假设为F）提供形参x的值，而计算进程F
3.4设线性Hash表的长度”=12,分别用下列Hash码将关键字元素序列（09,12,04,16,19,31,20,45,01,11,25,26）填入线性Hash表，并指出各关键字元素在填入过程中的冲突次数。
（1）£=mod（如如）
（2）i=mod（&*0.618,”）
解：
（1）t=
表项序号i
1
2
3
4
5
6
7
8
9
10
11
12
关键字态
01
11
25
04
16
26
19
31
09
20
45
12
冲突次数
0
3
2
0
1
3
0
1
0
2
2
0
（2）t=mod（i*0.618,"）
表项序号i
1
2
3
4
5
6
7
8
9
10
11
12
关健字A
01
04
45
25
09
11
12
31
16
26
19
20
冲突次数
1
0
0
1
0
0
0
1
0
6
0
0
.136.
3.5设溢出Hash表中的关健字元素均为非负整数，其存储空间为数组H（l：
m）.其中Hash表的长度为n（n（1）如何表示Hash表中的空表顾？
（2）给出Hash表与溢出表的初站状态.
（3）编写在溢出Hash表中填入关键字元素的算法。
在此算法中应考虑关键字元素的合法性及表空间是否溢出。
（4）编写在溢出Hash表中查找关键字元素的算法•在此算法中要求检查待查元素的合法性,并要求设置一个标志说明是否查到•
解：
（1）Hash表与溢出Hash津中的空表项值均为0。
<2）Hash表与溢出表中各表项的初始值均为0.溢出表虽然要求是栈结构，但由于在本题中对溢出表只进行填入与查找运算，因此可以将溢出表空间看成是顺序表。
查找溢出表时从顺序空间的最后一项开始。
（3）溢出Hash表的填入。
参看下列溢出Hash表类的成员函数•
（4）溢出Hash表的查找°参看下列溢出Hash表类的成员函数。
2.50设一棵二叉树的前序遍历序列为ACIKNHLM,中序遍历序列为1CNKALMH.试画出此二叉树，并写出后序遍历序列。
解：
恢复二黑树的方法同2.21题。
恢复过程如图2.9所示。
后序序列为INKCMLHA。
解：
一般来说，一个作业的大小不能超过实际内存空间的大小，实际内存空间是用户进行程序设计时可以利用的最大空间。
但在实际上，根据程序的时间局部性和空间局部性，在作业运行过程中可以只让当前用到的信息进入内存，其他当前未用的信息留在外存；而当作业进一步运行需要用到外存中的信息时，再把已经用过但暂时还不会用到的信息换到外存,把当前要用的信息换到已空出的内存区中，从而给用户提供了一个比实际内存空间大得多的地址空间。
对于用户来说，这个特别大的地址空间就好像是可以自由使用的内存空间一样。
这种大容量的地址空间并不是真实的存储空间，而是虚拟的，因此，称这样的存储器为虚拟存储器。
用于支持虚拟存储器的外存称为后备存储器。
虚拟存储器的大小受外存容量的限制。
4.14分页系统与分段系统各有什么优缺点？
解，分页存储管理的优点为，
（1）由于提供了大容量的虚拟存储器，用户的地址空间不再受内存大小的限制，大大方便了用户的程序设计,
（2）由于作业地址空间中的各页面都是按照需要调入内存的，不用的信息不会调入内存，很少用的信息也只是短时间驻留在内存，因此更有效地利用了内存；
（3）由于动态分页管理提供了虚拟存储器，每个作业一般只有一部分信息占用内存，从而可以容纳更多的作业进入系统，这就更有利于多道程序的运行。
分页存储器的缺点是不利于程序的动态连接装配，也不利于程序与数据的共享。
分段存储管理的优点是有利于程序的动态连接装配,也有利于程序与数据的共享，从而更有利于用户的程序设计。
分段存储器的缺点是不利于内存的有效利用。
4.15文件系统的主要任务是什么？
它为用户提供哪些主要功能？
解：
所谓文件系统，是指负责存取和管理文件信息的软件机构。
文件系统的主要任务是：
实现唯一地标识计算机系统中的每一组信息，以便能够对它们进行合理的访问和控制；以及有条理地组织这些信息，使用户能够方便且安全地使用它们。
其主要功能为：
（1）自动处理文件的存储和访问.借助于文件系统.用户可以简单、方便地使用文件，而不必考虑文件存储空间的分配，也无须知道文件的具体存放位置.
（2）通过文件的存取权限，对文件提供保护措施.并提供转储功能，为文件复制后备副本等。
总之，文件系统一方面要方便用户，实现对文件的“按名存取。
另一方面要实现对文件存储空间的组织、分配和文件信息的存储，并且要对文件提供保护和有效的检索等功能.
4.16文件的物理组织形式主要有哪几种？
文件系统对磁盘空闲空间是如何管理的？
解：
根据文件在存储空间中的存放形式，文件可以分为连续文件、链接文件和索引文件。
文件系统对磁盘空闲空间通常有以卜-几种管理方案/
表项序号i
1
2
3
4
5
6
7
8
关健字A
45
26
19
31
20
01
11
25
冲突次数
2
6
0
1
1
2
1
1
3.7Hash表技术的目标是什么？
如何提高Hash表的查找效率？
解；Hash表技术的目标是提高查找效率。
为了提高Hash表查找效率，一方面要使Hash码的均匀性比较好，另一方面要使Hash码的计算比较简单。
3.8简要归纳本章所介绍的几种Hash表的适用对象及其优缺点。
解：
（1）线性Hash表的处理比较简单；适用于Hash码冲突较少并且不应填满的情况，
其主要缺点如下：
1容易产生“堆聚”现象，
2在处理冲突的过程中会产生新的冲突I
3在Hash表填满时，其平均查找次数为无穷。
（2）随机Hash表解决了线性Hash表中存在的“堆聚”现象：
适用于Hash码冲突较少并且不应填满的情况。
其主要缺点如下：
1在处理冲突的过程中会产生新的冲突；
2在Hash表填满时，其平均查找次数为无穷。
（3）溢出Hash表解决了线性Hash表与随机Hash表中的缺点：
适用于Hash码冲突较少的情况。
其主要缺点如下：
1除Hash表本身外,还要增加一个溢出表，当Hash码不能遍历Hash表本身时，额外的溢出表空间是一种浪费；
2在Hash码不太均勾而冲突较多的情况下，溢出表中项数较多，顺序查找的效率会降低。
（4）拉链Hash表,适用于Hash码冲突较多的情况.
其主要缺点为拉链需要额外开销。
（5）指标Hash表：
主要用于关键字元素内容长度不等的情况。
其主要缺点为指标表的存储空间是一种浪费.
3.9分别用冒泡排序及希尔排序对下列线性表进行排序，要求给出中间每一步的结果。
（1）〈81,52,57,22,95,04,83,96,42,32,48,78,14,87,67）
（2）（424,887,807,709,882,616,573,413,679,180,975,264）
解：
⑴
①冒泡排序（其中符号〜表示前后两个元素交换）
原序列8152572295
04839642324878
148767
第1遍（从前向后）81〜52〜57〜22
95〜04〜83
96〜4232〜48〜78〜14〜87〜67
结果’$2*廿7'如28104（从后向前）52~57~22~81~04
8395423248781487回83〜95〜42〜32〜48〜78〜1487〜67
结果04'囱"访228114第2遍（从前向后）'04'5257-2281〜14
954232487867
结果04网兹57
14
（从后向前U04.52-22-57-14结虻％图22第3遍（从前向后）：
，0452〜22结果5232
（从后向前）.,,04..Je4
结果/4［2
57
52〜32
32[52
818342
32
48
78
67
网
95
81〜83〜42〜32
48
78〜67
87
95
328183
42
48
67
78
叵］
95
〜328183〜42〜48〜67〜78
87
95
578142
48
67
网
83
87
95
57〜81〜42
48
67
78
83
87
95
§425781
48
67
四
83
87
95
83
83
95~42~32〜48〜78〜67〜87
第4遍（从前向后？
04
M<：
?
?
32
52〜42
57
81〜48〜67〜78
83
87
95
结果1；04：
'
1482/32
网52
57
4867网81
83
87
95
（从后向前）,.；04
14；3232
4252〜57〜48677881
83
87
95
结果,微4；、
44.•以32
4248
回
5767网81
83
87
95
第5遍（从前向后O4t
14<'?
2&2
4248
52
57677881
83
87
95
最后结果云04?
n!
4册232
4248
52
57677881
83
87
95
②希尔排序
96
96
96
96
96
96
96
96
96
96
96
96
96
96
96
96
96
增量序列一般取知=砂2*以=l,2,・・・，［log2”］）,其中〃为待排序序列的长度。
--.1J11
11LJ
1111
!
1
!
-I-1
一L
1.1
1-1
1--1
人=3674232227804838152574895148796
结果
14
42
04
22
48
32
57
78
52
67
81
95
83
87
96
方=1
14
42
04
22
48
32
57
78
52
67
81
95
83
87
96
最后结果
04
14
22
32
42
48
52
57
67
78
81
83
87
95
96
•141•
3.6设随机Hi曲夜岬长鹿为
（1）利用本章给出的算法，写出伪随机数序列中的前6个随机数。
（2）设Hash码为揄将关键字元素序列（19,31,20,45,01,11
25,26）填入随机Hash表,并性明冲突次数。
解：
（1）伪随机数序列中前6个随机数为，1,6,7,4,5,2°
<2）
①冒泡排序
原序列
424
887
807
709
882
616
573
413
679
180
975
264
第1遍（从前向后）
424
887〜807〜709〜882〜616〜573〜413~679〜180
975〜264
结果
424
807
7
升级会员 