《软件技术基础》习题解答docx.docx
- 文档编号:6235850
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:15
- 大小:250.80KB
《软件技术基础》习题解答docx.docx
《《软件技术基础》习题解答docx.docx》由会员分享,可在线阅读,更多相关《《软件技术基础》习题解答docx.docx(15页珍藏版)》请在冰点文库上搜索。
《软件技术基础》习题解答docx
第二章
2.1什么是数据结构?
它对算法有什么影响?
数据结构是指同一数据对象中各数据元素间存在的关系。
数据结构对算法的影响:
算法的实现必须借助程序设计语言中提供的数据类型及其运算。
一个算法的效率往往与数据的表达形式有关,因此数据结构的选择对数据处理的效率起着至关重要的作用。
它是算法和程序设计的基本部分,它对程序的质量影响很大。
2.2何谓算法?
它与程序有何区别?
广义地说,为解决一个问题而采取的方法和步骤,就称为“算法”。
计算机算法是通过计算机能执行的算法语言来表达的。
和程序的区别:
一个程序包括两个方面的内容:
(1)对数据的描述,即数据结构。
(2)对操作的描述,即算法。
所以算法是程序的一个要素。
2・12试编写算法求已知单链表长度,并考虑表空的情况。
head
p=head
i=0
While(p!
=nil)//表不为空
P<-next(p)〃移动到下一个元素
i++
End(while)
Returni〃返回数据的个数
2.14已知一循环链表中数值已按递增有序排列现要插入一个新结点,并使插入一个新节点,并使插入后链表仍为有序序列
LinkST(head,b)
{
Getnode(p);data(p)<—b;
lf(head=nil)then{head*—head;head*—p;return;
}
lf(b } q<—head While(next(q)^nil)and(b>data(next(q)))do q<—head(q)lf(next(q)^nil)then{next(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},画出由此生成的哈夫曼树。 2.34.有一图如题图2.4所示: (2) VI作深度优先搜索: f勾Ff抵f巧3-勾Q VI作广度优先搜索: ffKeT均G-*焉0 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 第口趟: 13,15,35,39,41,57,61,62,79,83,84,96 堆排序: 41,62,13,84,35,96,57,39,79,61,15,83 输出13: 96 79 61 62 输出79: 调整成堆: 输出83: 调整成堆: 输出84: 输出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, 第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, 第09趟: 13,15, 35,39, 84,96 第10趟: 13,15, 35,39, 84,96 第LL趟: 13,15, 35,39, 84,96 41, 57, 61, 62, 79, 83, 41, 57, 61, 62, 79, 83, 41, 57, 61, 62, 79, 83, 快速排序: 41,62,13,84,35,96,57,39,79,61, 15,83x=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 第三章 3.1操作系统的基本功能是什么? 它包括哪些部分? 基本功能: 操作系统应该具有处理器管理,存储管理,设备管理和文件管理功能,同时,为了使用户能方便地使用机器,操作系统还应提供用户接口功能。 构成部分: (1)•对CPU的使用进行管理的进程调度程序。 (2).对内存分配进行管理的内存管理程序。 (3)•对输入输出设备进行管理的设备驱动程序。 (4)•对外存中信息进行管理的文件系统。 3.7存储管理器的功能是什么? 为什么要引入虚拟存储器的概念? 虚存的容量由什么决定? 存储管理的功能主要分为: 内存分配、地址转换、存储保护和内存扩充。 虚拟存储器能提供给用户一个比实际内存大得多的存储空间,使用户在编制程序时可以不必考虑存储空间的限制。 虚存的容量受两个条件约束: 指令中地址场长度的限制、外存储器容量的限制。 3.12什么是进程的同步和互斥? 什么是临界区? “同步”是指两个事件的发生存在某种时序上的关系,如果系统中有若干个进程要共同完成某一任务,那么它们相互之间必须协调配合。 “互斥”是指当多个进程要求共享系统中某些硬件或软件资源,而这些资源却又要求排它性使用时,这样往往引起由于多个进程竞争同一资源使运行结果出现问题。 如果在两个进程Pl、P2中加入P、V操作后,可以实现对公用变量count的互斥使用。 其中P(s)、V(s)之间的程序段称为临界区。 3.16死锁产生的必要条件是什么? 死锁的预防、避免和检测各有什么不同? 各举一种相应的方法。 死锁产生的必要条件有: 1.所涉及的资源是非共享的;2.进程在等待新资源时,继续占用已分配到的资源;3.—个进程占有的资源不能被别的进程强行抢占;4.一个进程获得的资源同时被另一个进程所请求,从而形成一个进程的循环链。 死锁的预防是研究如何破坏产生死锁的必要条件之一,从而达到不使死锁发生地目的。 死锁的避免与死锁的预防区别在于,死锁的预防是严格破坏形成死锁的必要条件之一,使得死锁不在系统中出现。 预防方法之一,采用假脱机技术将非共享设备变成共享设备来实现O 而死锁的避免并不严格限制必要条件的存在,因为必要条件存在并不一定产生死锁。 而进程推进顺序不当,也可以导致系统发生死锁,因此死锁的避免是考虑万一当死锁有可能出现时,就小心地避免这种情况的最终发生。 避免方法有采用相应的银行算法和方法。 死锁的检测和恢复,这是一种变通的方法,它允许死锁的发生,但能在适当时间检测出来,并设法进行恢复。 利用化简进程-资源有向图的方法来检测系统在某一特定状态时是否处于死锁状态。 3.22什么是文件目录? 有几种目录结构形式? 各有什么特点? 为了便于对文件进行存取和管理,所有计算机系统都设置一个文件目录,每个文件目录中都有一个表目,存放描述该文件的有关信息。 通常有一级目录、二级目录和多级目录结构。 一级目录: 把系统中所有文件都建立在一张目录表中,整个目录结构是一个线性表,所以查找的时间会增加,不允许用户对不同的文件取相同的名字,主要用于单用户的操作系统中。 二级目录: 在主目录文件中每一个用户有一个表目,指出各用户文件目录的所在位置,而各用户文件目录才指出其所属各具体文件的描述信息,不同用户的文件可以起相同的名字。 多级目录: 是树形结构,每一个结点出来的分支可以是文件,也可以是下一级,在一定时间内以某一级目录作为当前目录,用户只需从“当前目录”查看即可。 3章设备独立性? 好处? 设备独立性,即应用程序独立于具体使用的物理设备。 为了实现设备独立性而引入了逻辑设备和物理设备这两个概念。 在应用程序中,使用逻辑设备名称来请求使用某类设备;而系统在实际执行时,还必须使用物理设备名称。 因此,系统须具有将逻辑设备名称转换为某物理设备名称的功能,这非常类似于存储器管理中所介绍的逻辑地址和物理地址的概念。 优点: 在实现了设备独立性的功能后,可带来以下两方面的好处。 1)设备分配时的灵活性 2)易于实现I/O重定向 3)X窗口系统是个分布的,网络透明的,独立于设备的多任务窗口和图形系统,它采用顾客/服务员模式,把画窗工作分面二部分,从而取得了设备独立性,它提供了在网络上传送图形信息的标准协议,X窗口系统是网络图形工作站和高档PC机理想的窗口系统。 4.7 (5)查询工程号J1提供零件号P1的供应商SNO SelectSNOfromSPJ WherePNO=,pl, AndJNO='jl' (6)查询提供零件名PN3的供应商SNO Selectsnofromspjinnerjoinpartonspj.pno=part.pname='pn3'groupbysno (7)查询供应商S3提供的零件名PNAME Selectpnamefrompartinnerjoinspjonspj.pno=part.pno,andspj.sno='S3'groupbypname (8)查询为工程号j1和j2提供零件的供应商号SNO SelectSNOfromSPJ WhereJNO='jl' OrJNO=,j2, (10)取出上海供应商为在上海的工程提供零件的所有供应商号SNO SelectJNAMEfromJ,S,P,SPJ WhereJ.JNO=SPJ.NO AndSPJ.SNO=S.SNO AndS.city=,_h海, Andp.city='上海, (11)取出北京供应商不提供红色零件的供应商号SNO SelectSNfromSPJ WhereJNin (selectJNfromJ Wherecity=,北京, ) AndPNin (selectPNfromP Wherecoloro'红色, ) (12)取出至少一种由S1供应商提供零件的工程号JN0 SELECTJN FROMSPJ WHERESN='S1' 4.8工厂产品生产管理系统 (1)工人与产品管理子系统 (2) 产品与零件、材料资管理系统 (3)零件与材料子系统
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 软件技术基础 软件技术 基础 习题 解答 docx