《计算机软件基础课后习题解答.pdf》由会员分享，可在线阅读，更多相关《计算机软件基础课后习题解答.pdf（55页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机软件基础习题解答第1章概论复习题答案I.怎样的计算机被称为裸机？什么是虚拟计算机？【解答】：对 于 诒 只 有 硬 件 构 成（通常包括：中央处理器cpu,储存器，输入和输出设备），而没仃安装任何软件的计算机被称为裸机.而虚拟计算机则是指以硬件为物质基础，加装软件后的扩充后的计算机系统，2.计算机软件资源的作用如何？在你使用的计算机上仃那些软件资源？【解答工计算机软件资源的作用是只有在软件资源的支挣下，用户所使用的计算机才能极大程度上.满足用户需要的虚拟计算机.软件资源有：汇编程序：各种高级语言：各种语言的解释或编译程序：各种标准程序库：操作系统；数据库系统软件：计算机网络软件；各种应用
2、软件等。3.汇编语言和高级语言仃什么不同？【解答】：汇编语言是面向机器的语言，即不同型号的计算机的汇编语言是各不相同的，进行程序设计时必须 解所使用的计算机的结构性能和指令系统，而II编好的程序也只是针对 类机器，不能通用。高级语言是面对过程的语言，用户不必r解具体机器的细节就能编写程序，方 便r程序的设计，提高了效率，同时也便于人们的交流。4.我们知道计算机只能执行机器指令，为什么它能运行汇编语言和高级语言编写的程序？【解答】：计算机之所以能运行汇褊语言编写的程序是因为计算机系统中装有汇编程序，汇编程序的作用是将源程序翻译成用机潜语言组成的目标程序，从而计算机能运行汇编语言编写的程序.计算M
3、X所以能运行高级语言编写的程序是因为计算机系统中装行解择程序或编泽程序，它们将用高级语言编写的程序翻评成用机器语言生成的目标程序，从而计算机能运行高级语言编写的程序;5.你学习过那些高级语言?试分析它们的特点和适用的范用？【解答】:fortran语言主要用于科学和T程计算:pascal语言则具仃良好的程序结构,cobol语言则是面向事务处理的；1即语言是人工智能语言；c语言则是通用的程序设计语言；C+语言是面向对象的程序设计语言。6.计算机软件的定义是什么？【解答 计算机软件是指：计算机程序，实现程序功能所采用的方法，规则以及相关联的文档和在机罂上运行它所需要的数据。7.操作系统的作用是什么？
4、【解答】：操作系统控制和管理计算机的硬件、软件资源，实现对处理机，存储器，1/0设备，文件等四类资源的管理，同时操作系统还作为用户和计算机系统之间的接U,方使r人机交互。8 .计算机操作系统在发展中经历r 那些阶段？试简述它们的特点？【解答】：主要经历九 手工操作阶段、成批处理系统阶段、执行程序阶段、多道程序系统和分时系统阶段“手工.操作阶段的特点：计算机的全部资源归个用户的个程序独占操作过程仃人T来干预。成批处理系统阶段：相对户手工操作阶段，它提高r 计算机资源的利用率和增强r 系统的处理能力，但由于处理机和L/O设备是中行工作的，大部分时间被消耗在输入输出上，处理机的大部分时间处于等待状态
5、，故处理机和I/O 设备的速度不匹配的矛盾成为进步提高计算机的效率的关键。执行程序阶段：使系统实现 r 模块化结构，易于设计、修改和扩充，但由于计算机本身的顺序性，计算机并不能先全消除对外设传输的等待,多道程序系统：它需要个制度算法来解决c p u的分配问题，需 要 仃，个储存管理程序来解决多道程序在内存中的定位，分配和免遭破坏，需要仃 个设备管理程序来解决外设的分配.鞋放和信息交换，此外还需要仃个文件管网程序来解决以文件形式存放于外存中的程序和数据，分时系统阶段：分时系统阶段采用划分时间片的方法来接受和处理各个用户从终端输入的命令，由于计算机运行的高速性和并行性，使每个用户感觉不到别的用户的
6、存在，好像独占整台机器.9 .计算机应用软件仃那些？【解答】：主要有以下三大领域；事务处理软件，T.程和科学计算软件，实时应用软件.随着计算机技术的发展些新的领域异军突起，如：嵌入式府用软件，微型机T.具软件,人工智能软件.第 2 章数据结构复习题答案一、选择题1 .线性表L在 情况下适用于使用链式结构实现。A)t需经常修改L 中的结点值,(B),需不断对L 进行删除和插入：C)：L 中含有大属的结点；(D),L 中结点结构豆杂；【答案】：应选B.2 .线性表在采用链表存储时其地址_ _ _ _ _ _ _(Ah必须是连续的，(B)：部分地址是连续的；(C)：定不是近续的：(D)：连续不连续都
7、可以；【答案I 应选D.3 .数组Q n 用来表示个循环队列，f为当前队列头兀素的前个位置，r 为队尾兀素的位置，假定队列中元素的个数小于n,计 算 队 列 中 元 素 的 公 式 为.(A)s r-f s (B)：(n+f-r)%n (C)：n+r-f :(D)s (n+r-f)%n(【答案I 应选D.4 .若入栈序列为1,2,3,4,在入栈的过程中允许出栈，则 不可能是个山栈序列.(A)：1,4,3,2：(B)：2,3,4,1：(C)：3,1,4,2 ；(D)t 3,4,2,I t【答案I 应选C.5 .个二维数组M.行下标的范围是1 到 8,列下标的花用是0到 9,悠个数组兀素用相邻的
8、5 个字节存储，存储器按字节编址，设存储数组元素M U,0)的第 个字节的地址是98,1 1 按列存储，则M(3,7 的第 个 字 节 的 地 址 是(A)：1 3 5 t (B)2 3 3,(C)t 2 90：(D)3 8 8：【答案】：应选D.6 .由3个结点所构成的二叉树有 种形态，由3个结点构成的树仃 种形态.(A)t 3：(B),4 ,(C)5：(D)：6 ,【答案】：应选C和 A：7 .不 含 任 何 结 点 的 空 树(A)t 是,棵树；(B)t 是棵二又树：(C)：是 棵 树 也 是 棵 二 又 树；D)：既不是棵树也不是棵二叉树；【答案】：应选B.8 .棵深度为k的满二义树中
9、结点的个数是 o(A)：2-1,(B)：2%(C).(D)：2M:【答案】：应选A.9.棵具有2 5 7 个结点的完全二叉同，它 的 深 度 为.(A)t 8 ；(B)9,(C)：It D)t 1 0.【答案】：应选B.1 0 .二叉树是非线性数据结构，所以。(A)：它不能用顺序存储结构存储；(B)：它不能用链式存储结构存储；(C)：用喉序存储结构和链式存储结构都能存储;(D),顺序存储结构和链式存储结构都不能存储;【答案】：应选C.1 1 .把 棵 树转换为二又树后，这棵二叉 利 的 形 态 是。(A),唯 的：(B),有多种；(C)：行多种，但根结点都没仃左孩7 S (D)t 仃多种，但根
10、结点都没仃右孩汽【答案】：应选A.1 2 .在表长为n 的链表中进行线性查找，它的平均查找K 度为(A)t A S L=n：(B)t A S L=(n+l)/2 (C)t A S L=+1 s (D)：A S L l og,(n+l)-l s【答案】：应选B.二、填空题1 .数 据 的 基 本 单 位 是，它可以由 组成，【答案】：数据元素；数据项.2 .把逻辑上相邻的数据元素存储在物理上 相 邻 的 存 储 单 尤 中 的 存 储 结 构 是.【答案】：顺序存储结构，3 .顺序表结构适宜于进行 存取：链表适宜于进行_ _ _存取：【答案】：随机存取；顺序存取。4 .栈 是种特殊的线性表，允许
11、插入和删除运算的端为，不允许插入和删除运算的端为【答案】：栈顶；栈底.5 .是被限定为只能在表的端进行插入运算，在 表 的 另端进行删除运算的线性表，【答案】：队列.6 .三兀组表中的每个结点对应与稀疏知阵的个非零儿素，它包含仃三个数据项，分别表示该元素的_ _，和【答案】：行下标：列下标：兀素值。7 .对于 棵非空二又树，它的根结点作为第层，则它的第i 层最多能仃一个结点.【答案】：2 1.8 .把棵树转化为二义利以后，这棵二叉树的 根 结 点 没 有。【答案I 右子树.9.在数据的存放无规律而言的线性表中进行检索的最佳方法是.【答案】：线性检索.1 0 .仃 个表长为m 的散列表，初始状态
12、为空，现将n(nlink：return(i)：3.给 定个 n 项元素的线性表%写个算法，将元素津列的次序颠倒过来，要求仍占用原来的空间，并J1用顺序表和单链表两种方法表示。【分析】:将 V与丫交换，V 与 Vn-1交换，,VEn/2与V g/2+l交换.【答案】：顺序表结构下的实现，#define M 1000int vM：int n：void invert()int temp；for(i=0：i1ink；u-link=p：/字将.删除的结点插入到另个链表中/p=u：hcad=p：/新蚀表的头指针*/4 .试设计实现在单例表中删除值相同的多余结点的算法。【答案】：t y pcd cf s t
13、 ru ct s nod c ch a r d a t a：s t ru ct s nod c M i nk：N O D E：v o i d p u r g e _ l k l i st(NO D E *h c a d)NO D E *p,*q,*r；p=h c a d-l i n k i /*p指向当前检查结点的位置，先将其初始化*/i f (p=NU L L)r e t u r n：/*空表返回/w h i l c(p-l i n k t!=NU L L)/*当前结点不是尾结点*/q=p：w h i l o(q-l i n k!=NU L L)/*帆除值与p所指结点的值相同的结点*/i f
14、 (q-l i n k-d a t a=p-d a t a)/*若有值相同的结点字q /r=q-l i n k：q-l i n k =q-l i n k-l i n k；/*删除多余结点/f r e e(r )：e l se q=q-l i n k；/*找下一个可以的多余结点*/p=p-l i n k；/*更新检查结点/5.描述以下三个概念的区别，头指针、头结点、首兀元素结点。【答案】：头指针：是指向单链表的第一 个结点的指针c头结点，在链表的首兀元素结点之前附设的个结点,首元兀素结点：是指用于存储线性表中第个数据的结点。6.写I K计算线性链表长度的算法。【分析】一根据单链表的特性，从单链表
15、第个结点开始访问，只要是非空结点，计数次，直到所仃结点访问 遍。【答案】：t y p c d c f st r u c t sn o d c c h a r d a t a：st r u c t sn o d c *l i n k；NO D E：i n t l e n g t h(NO D E *h c a d)NO D E *p3 i n t i：p=h c a d：i=0；/*初始化*/w h i l e (p!=NU L L)if p =p-l i n k；r e t u r n (i)：)7.设有个线性链表，其结点为正型数，1 1按值从小到大链接。试写I I I 个算法，将此线性链表分
16、解成两个线性链表，其中个链表中的结点值均为奇数，而另个链表中的结点值均为例数，U这两个链表均按值从小到大链接：【分析】：在链表h e a d 中依次取儿素(s-d a t a),若取用的元素是奇数，把它插入到奇数链表a h e a d 中，若取出的兀素是偶数，把它插入到偶数链表b h c a d 中，继续取下个元素，直到链表的尾部，头指针a h e a d 和 b h c a d 分别指向奇数链表和偶数链表，【答案】：t y p e d e f st r u c t sn o d c t i n t d a t a：st r u c t sn o d c M i n k；NO D E；v o
17、i d e x a z u p T (NO D E *h c a d.孝 a h e a d,字 b h c a d)NO D E *p,*q,*s：a h c a d=(NO D E *)m a l l o c(si z c o f(NO D E)；/*建立奇数链表的头结点*/p=a h c a d：,/工作指针p 初始化。/b h c a d=(NO D E *)m a l l o c(si z o o f (NO D E)：/*建立偶数链表的头结点*/q=b h c a d；/手 工作指针q 初始化0 */s=h c a d-l i n k：f r e e (h e a d)；/*s 为
18、原表中的工作指针，睡放原表中的头结点*/w h i l e (sl=NU L L)i f(s-d a t a%2=0)/*是偶数*/q-l i n k =s；q =q-l i n k ；e l se /是奇数*/p-l i n k =s：p =p-l i n k：s=s-l i n k :/*取 下 个结点/p-l i n k =NU L L；/置奇数表的表尾*/q-l i n k =NU L L：/置偶数表的表尾*/8.假设有个循环单链表的尺度大于1,I I 表中既无头结点也无头指针：已知S为指向链表中某结点的指针，试编写算法，在链表中删除S 指针所指结点的前驱结点。【分析】一 设 置 个
19、指 针 P，指向S结点的前驱结点的前驱结点。【答案】：t y p e d e f st r u c t sn o d c c h a r d a t a；st r u c t sn o d c *l i n k：NO D E：NO D E *s：v o i d d e l c t c p r i o r()NO D E *p,*q；p =s：w h i 1 c(p-1 i n k-l i n k!=s)p=p-l i n k；/*让 p 指 向 s 结点的前驱结点的前驱结点*/q=p-l i n k；/*q指向被删除结点*/p-l i n k =q-H n k；/*胴 除/f r e e(q)
20、：9 .已知指针h a和h b分别指向两个单链表的头结点，1 1头结点的数据域中存放链表的K度，试写出个算法将这两个链表连接在起，并要求算法以尽可能短的时间内完成运算，【分析上:令表h b的首兀结点连在表h a中的最后 个结点之后，首先想将T作指针p从h a的首元结点开始遍历到去h a中的母后 个结点，h e指向连接后的链表的头结点。【答案】：t y p e d e f st r u c t sn o d c c h a r d a t a；st r u c t sn o d c *l i n k；NO D E；NO D E *h a,*h b,*h c：v o i d c x a m p l
21、 c 9()NO D E *p；i n t i：h e =h a ：/*h e指向连接后的链表的头结点/p =h a-l i n k：i=l i /*用于表h a中结点的计数器/w h i l e (i d a t a)p =p-l i n k j /*h a-d a t a 是表 h a 的长度*/p-l i n k =h b-l i n k；/连接表h b的首元结点*/h c-d a t a =h a-d a t a +h b-d a t a：/连接后的链表的 K度*/1 0 .对于下面的每步，画出栈元素和栈顶指针示意图.(1)栈空.(2)在栈中入栈个元素机(3)在校中入栈个元素明1 1.
22、设仃编号为1,2,3,4的四辆列车，顺序进入个栈式结构的车站，具体写I H这四辆列车开出车站的所仃可能的顺序:【答案】：1,2/3,4：1/2/4,3：4,3,2：2,1/3,4；2,I,3,3：4,3,1；3,2,L,4：3,2r 4,1；L 3,1,4；b 3,4,2；1,2,3,1,4；2,3,4,1：2,3,4,2,1：%3,2,1：1 2.说明栈和队列的异同点。【答案】：相同点t栈和队列都是线性表结构；不同点t 根是限定在线性表的端进行插入和删除的操作；而队列的插入和删除在线性表的两端进行：13 .顺 序 队 的“假灌出”是怎样产生的？如何知道循环队是空还是满？【答案】：队列的尾指针
23、已经到r 数姐的上界，此时如果还要执行入队运算，就要发生“上涌”，但是数组中还仃空位置，这种现等称为“假溢出二在循环队中，当r c ar=f r o n t 时，表示队空；当(r c ar+D 知f=f r o n t 时，表示队满。14 .设循环队列的容量为如(序号从0到 3 9),现经过 系列的入队和出队运算后，有(1)f r o n t =11,r c ar=19s(2)f r o n t =19,r e ar =11；问在这两种情况下，循环队列中的各4：多少个元素？【答案】：(1)：8 个：(2)3 2 t15.假 设 数 组 sq u m 存放循环队列的元素：若要使m个分这都得到利用
24、，则需要另个标志t ag,以 t ag 为。或 1 来区分队尾指针和队头指针值相同时队列的状态是“空”还是“满”.试编写与此结构相此的入队和川队的算法.【答案】：#d e f i n e M 10 0i n t sq u D l ,f r o n t,r e ar,t ag：/*队列中加个标志域 t ag */i n t ad d q u c(i n t x)/*入队运算*/i f (t ag=l)&(f r o n t=r c ar)p r i n t f(f u l l q u c u c r!n )：r e t u r n (-1)e l se r e ar =(r c ar+1)黜：s
25、q u r e ar =x；i f (r c ar=f r o n t)t ag=L ；/*如果插入后队列满，则置标志*/i n t d c l q u c()/*出队运算*/i f (t ag=0)&(f r o n t=r c ar)p r i n t f (ae m p t y q u e u e r !n )t r e t u r n(-1)：e l se f r o n t =d at a=x：p-l i n k =r c ar-n c x t：r c ar-n c x t =p；/*在队尾插入结点/r e ar =p：/修改队尾指针*/i n t d c l c q u c u c
26、()/*从链队中出列，返回川队的数据元素*/N O D E *p：i f (r c ar-l i n k=r c ar)p r i n t f (t tq u c u c i s e m p t y!n,r)?r e t u r n(-1)：e l se p=r c ar-l i n k：/*p指向头结点*/q=p-l i n k5/*q指向被射除结点*/i f(q=r c ar)r c ar=p；/队列中仅仃,个结点时，先修改尾指针*/p-l i n k=q-l i n k t x=q-d at a：f r e e (q)：r e t u r n (x)：/*删除结点并返回/17.已 知 二
27、 维 数 组0采用按行优先顺序存放，每个人案国K个存储单元，并11第个兀素的存储地址为L O C(a m,请写BL O C(a Q的计算公式。如果采用列优先顺序存放呢？【答案】：按行优先顺序存放：L O CS j h L O CS j J +d i-D+m +(j-l)*K?按列优先顺序存放：L 0 C(aJ=L 0 C(an)+(j-l)*m +(i-L)*K;1 8.用三兀组表表示下列稀疏矩阵；,0000000 0、r 0 0 0 0 0-2、000000000 0 0 0 9 0030008000 0 0 0 0 000000000.(2)o o 5 o o o r000600000 0
28、 0 0 0 0000000001。0 0 0 3 0,000000052000000 0答案】：(1)(2)行 下 标 列 下 标 元 素 值6 6 41 6-22 5 94 3 56 5 3行下标833578列下标元素值85236846851219.下列各三九组表分别表示个稀琉矩阵，试写出它们的稀疏矩阵:(6 41 21 3(3 14 45 3I 6 16 )21 23 46应r 41(2)I 2 335 5 1 L4 92 85 63 7 J(1)：【答案】:r 021 20000300000040060116000)0 0 0 00 0 9 08 0 0 60 7 0 02 0 .什
29、么 样 的 二 义 树不是斜？棵 度 为 2的 树 与 棵二叉树仃何区别？【答案答空机是二义树，但不是树。树定是非空的.在 棵 度 为 2的树中至少有 个结点的度为2：但在 棵二叉.树中每个结点的度可以都小 于 2,比如单枝树.2 1 .试分别画出具仃3个结点的树和仃3个结点的二义制的所仃不同形态：【分析】t无序树的子料没有顺序之分，而二叉树的子树分为左子树和右子树.【答案I 具 仃 3个 结 点 的 树，9AX有3个结点的二叉树:2 2.设 棵兑全二叉树具有1000个结点，问此兑全二叉树（1）有多少个叶子结点？2）有多少个度为2的结点？（3）有多少个结点只仃非空左了树？（4）有多少个结点只有
30、非空右了树？【分析】:有1 0 0 0 个结点的元全二叉树共仃1 0 层，在第1 0 层有1 0 0 0-（21）=1 0 0 0-5 1 1=4 8 9个结点，都是叶子结点，它们共有2 4 4+1 个双亲结点在第9 层，其中仃个双亲结点只有个孩子，其他共2 4 4 个双亲结点的度均为2,所以在第9层还仃2 5 6-2 4 5=1 1 个结点的度为0,既为叶了结点.【答案】：（1）打 5 0 0 个叶子结点，（2）仃 2 5 5+2 4 4=4 9 9 个度为2的结点：寸1个结点只有非空左子树；（4）没仃结点只仃非空右了树；2 3.下面是仃美二叉树的叙述，哪些是正确的？（1）二叉树中每个结点的
31、两棵/例的离度差不大于1.（2）二叉树中每个结点的两棵了树的高度差等于1。（3）二义树中每个结点的两棵广树是有序的，（4）二叉树中每个结点的两棵非空或有两棵空r 树.（5）二又树中每个结点的美键字值大于左子树（若存在的话）上所仃结点的关铤字值，I I 小于其右非空子树（若存在的话）上所有结点的关健字值.（6）二义树中所仃结点个数是二-1,其中k 是科的深度：7）二叉树中所有结点，如果不存在非空左子树，则不存在非空右了树。【答案】：1）错误，A V L 树中每个结点的两棵/树的高度差不大于L 2）错误，（3）正确，错误,二义树中有些结点可以仃棵空r 恻，棵非空了树.5）错误。二叉排序树满足所叙述
32、的条件.-1。（7）错误.二乂树中的结点，可以没有非空左子相，但仃非交右了朝:2 4.用链式结构存储二又树，试写I I I 下列算法：（1）按层次输入所有结点：（2）输出所仃叶了呦点.【答案】：/*先定义二义制的二叉链表结构本/typcdcf struct node int data：struct node 杓child,*rchildi NODE：(1)按层次输入所有结点，【分析】：本算法要借用队列来文成，其基本思想是，只要队列不为空，就出队列,然后判断该结点是否仃左孩了和右孩子，如仃就依次输IH左、右孩子的值，然后让左、右孩子进队列。void layordor(NODE*root)/*设
33、q 是,个队列，函数 initqucue(q)、addqueue(q,x)、dclqucuc(q)N empty(q)在 2 42 队列中已实现*/initqucuc(q)j/初始化个队列*/if(root!=NULL)printf(%d”,root-data)：/*输中结点值*/addqueue(q,root)?/根结点入队*/while(NOT empty(q)/*如果队列不空/p=dclqucuc(q)；/*对头儿素山队/if(p-lchild!=NULL)printf($d，p-lchild-data)：/*输111左核子的值*/addqueue(q,p-lchild)：/*左核了入队
34、*/if(p-rchild!=NULL)printf(，p-rchild-data)?/*愉出右核子的值*/addqueue(q,p-rchild)：/右孩了入队*/)(2)输出所有叶了结点,【分析】：木算法为先根遍历的递归算法。如果树不空，分三步进行：第 步，判断根结点是否为叶子结点，若是，则输出：第二步，调用该算法输出根结点的左广 树上的所仃叶子结点：第三步，调用该算法输出根结点的右子树上的所仃叶了结点；【答案】：typcdcf struct node int data；struct node*lchildr*rchild：NODE；void printlcaf(NODE*root)if(
35、root!=NULL)if(root-lchild=NULL)&(root-rchi ld=NULL)printf(%d,root-data)：/*如根结点是叶子结点，则输出*/printlcaf(root-lchild)：/*输出左子树上的所有叶子结点*/print leaf(root-rchild)；/*输111右子树上的所有叶子结点*/2 5.已知 棵具有n个结点的完全二叉捌被顺序存储十 维数组btrcc中，试 编 写个算法打印用编号为i的结点的双亲和所以孩了【答案】：d e f i n e N 1 0 0i n t b t r e c N /定义完全二叉树的存储结构*/v oi d p
36、ri nt _ pa rc nt _ c h i ld(i nt n,i nt i)/*n 为结点个数*/i f (n=0)pri nt f (a T re e i s c n t y!w)：re t u rn：/*空树*/e lse i f(i n)pri nt f(a ord e r i e rror!)：re t u rn：A 编号Hl错e lse i f (i=l)/根结点无双亲*/pri nt f(N o pa re nt s nw)：i f (2*i =n)pri nt f(L e h i Id i s:%d nw,b t rc e 2*i )：i f (2*i+K=n)pri n
37、t f (Rc h i ld i s:%d n ,b t rc c 2*M)；e lse pri nt f (AP a re nt ,b t rc c i/2)：/*双亲*/i f (2*i =n)pr i nt f (u L e h i Id i s:%d n,f,b t re e /*左孩*/i f (2*i+L =n)pri nt f (z,Rc h i ld i s:i lc h i ld=N U L L)&(root-rc h i ld=X U L L)re t u rn(1)?/*如根结点是叶子结点，则深度为L /e lse (h l=d c pt h(root-lc h i ld
38、)：/左子树的深度*/h r=d c pt h(root-rc h i Id)：/*右了树的深度/i f(h l h r)re t u rn(h l+1)：e lse re t u rn(h r+1)：/*深度为 ma x(h l,h r)+1*/3 0 .对序列12,7,17,11,16,2,13,9,2b 4 构 成 棵 二 叉 排序树。3 1.从供选择的答案中找出应添入下列叙述中的()内的正确答案，(1)要进行线性查找，则线 性 表().(2)要进行二分查找，则线 性 表()：(3)要进行散列查找，则线 性 表(;(A)：必须以顺序方式存储；(B)：必须以链式方式存储(C)：必须以散列方
39、式存储；(D)：既可以以顺序方式存储,也可以以键式方式存储，(E)：必须以顺序方式存储11数据兀素已按值递增或递减的次序排好.(F)：必须以链式方式存储II数据兀素已按值递增或递减的次序播好.【答案】：(1)选择D：(2)选择E,(3)选择A,3 2.用二分查找的查找速度必然比线性查找的速度快.这说法对吗？为什么？【答案】：正确.因为用二分查找法来查找时，在 每次比较之后，如查找不成功，是将待查范闱缩 小半.而采用线性查找时，每次比较之后是将待查范围缩小 个兀案.二分查找的平均查找K 度为，log m；而线性查找的平均查找K 度为：(n+1)/2.3 3 .说明散列查找和其它查找方法的区别.【
40、答案I散列查找是希望平均查找长度与记录的个数无关，既不经过任何比较，“次”存取就能得到所要查找的兀案的查找方法 它要求在兀素的存储位我和它的大键字之间定立个确定的对施关系，使每个大键字和结构中个 唯的存储位我相对应.而其它的查找方法的平均查找长度都与记录的个数有关，但不必在元素的存储位置和它的关键字之间建立个确定的对应关系。3 4.r 是个顺序表结构的有序表，编 写个查找算法，要求在查找失败时做插入操作并保持表r 的有序性。【分析I：用二分查找方法，如查找成功，则返回待查元素在表中的位置，如果查找不成功,既 low h i g h 时，此时h i g h+1的位置为待查兀素所应插入的位置，这样
41、可以保持表r 的仃序性.【答案I#d e f i ne M 50 0t ype d e f st ru c t i nt k e y：c h a r i nf o：N O DE：N O DE r Msi nt b i nsrc h _ i nsc rt (i nt n,i nt k)/*k为要查找的数据，n 为实际的表长*/i nt low,h i g h,mi d*k t N O DE t e mp,low=lj h i g h=nsw h i le(low =h i g h)mi d=(low+h i g h)/2：i f (k=r mi d .k e y)re t u rn(mi d)；
42、/*查找成功,返回*/e lse i f(k =h i g h+l；k)r k+l=r k ,/*从 r h i g h-l 到r n 的所有元素右移一个位置*/r h i g h+1.k e y=kt r h i g h+l.i nf o=r/*数据插入*/)3 5.设记录的关键字集介为K=(3 2,13,49,55,22,3 9,17),用模除散列函数得到散列地址，解决冲突的办法为线性探测法，按上述条件将集合中的各值依次添如下表中.【答案】：0 1 2 3 4 5 6 73 2493 9171322553 6.选取散列函数H(k e y)=(3*k c y)%11,用线性探测法处理冲突，对
43、下列关键码序列构造个散列地址空间为0、10,表长为11的散列表，(22,41,53,0 8,46,3 0,0 1,3 1,66).0 1 2 3 4 5 6 7 8 9 10220 1413 06653463 10 83 7.关键字序列 T=13,6,3,3 1,9,27,5,1 0,分别写III选择排序和直接插入排序的中间过程序列.【答案】：(1)选择排序，i k初始序列：1 3 6 3 31 9兑 成 第 卷 3 6 1 3 31 9先成第二趟：3先成第三趟：35 1 3 31 9i k5 6 31 92 7 5 1 1 /*T 与 T 3 交换*/k2 7 5 1 1 /*T 与 T 交
44、 换*/k2 7 6 1 1 /*T 3 与 T 7 交换*/2 7 1 3 1 口/*T 4 与 T 5 交换*/兑成第四垣：3 5 6 9 31先成第五趟：3完成第六趟：3先成第七趟；35 6 9 1 15 6 9 1 15 6 9 1 12 7 1 3 皂 /*T 5 与 T 8 交换*/i k 2 7 1 3 31 /*T 6 与 T 7 交 换*/i=k1 3 2 7 31 /*不用交换*/A k1 3 2 7 31(2)直接插入排序t初始序列，1 3 6第 趟：1 3第二趟：63631 93 311 3 32 7 5 1 19 2 7 5 1 131 9 2 7 51 1第三趟：3
45、61 331 92 7 51 1第四趟1 361 331 92 7 51 1第五趟t 3691 331 2 7 51 1第六趟t 3691 32 7 31 51 1第七趟：35691 32 7 31 1 1第八趟，35691 1 1 32 7 31 38.对于整数序列1 00,9 9.3,2,1,如果将它完全倒过来，分别用目泡排序和快速排序法，它们的比较次数和交换次数各是多少？【答案】：对目泡排序方法来说，这个序列是最坏的情况，n=1 00个数据，共进行9 9 趟目:序操作,第趟要比较9 9 次，第一趟要比较9 8 次，第 9 9 趟要比较1次，每次比较都执行f 次交换，所以共进行了 9 9+
46、9 8+9 7+1=1 00*9 9/2=4 9 5 0次比较和交换。对快速排序方法来说，这个序列也是最坏的情况，与 可 泡 排 序 样，共进行9 9 趟排序。第 趟 要 比 较 9 9 次，进行 次交换，第二趟要比较9 8 次，不需要交换，第三越要比较9 7 次，进 行 次 交 换，第四趟要比较9 6次，不需要交换，所以总的比较次数为4 9 5 0次，交换的次数为5 0次。39.对关键码值为 35,1 1,5 2,69,6,1 7,7 6,64.8 2）的序列执行以下排序算法，画II I 执行过程中每个中间状态和结束时的状态：2）最近最久未用算法L R U （L e a s t R e c
47、e n t l y U s e d）3）最久母少使用算法 L F U （L e a s t F r e q u e n t l y U s e d）19 .段式系统中的“段”是以什么来划分的？它与页式系统中的“页”仃什么区别？【解答】：段是信息的逻辑单位，它含仃组其意义相对兑整的信息，逻辑信息组的尺度决定r 段的尺度，分段的目的是为 能更好地满足用户的需要。段的改度是不固定的：页是信息的物理单位，分页是为实现离散分配方式，提高内存的利用率，或在说，分页仅仅是由于系统管理的缶要，页的大小固定口由系统决定。此外，分页的作业地址空间是雄的，而分段的作业地址空间是二维的，在标识个地址时，既须给巾段名，
48、乂否给山段内地址.2 0 .8 6 系列C P U 的工作模式寸儿种？D O S 是工作在那种模式？【解答】：8 0 8 6/8 8 只仃 种模式一实地址模式，8 0 2 8 6 则有两种模式：实地址模式和保护模式，8 0 1 8 6 及其后续机型还增加了另 种模式一虚拟8 6 模式*D O S是T作在实地址模式下.2 1 .内存控制块的作用是什么？它提供 什么信息？【解答】：系统运行时，每 当 加 载 个命令程序或#某个进程申请内存空间时.D O S要为它们申请的内存空间建立个内存块供申请者使用，并在该内存块的头部设置1 6 字节的区域头，称之为内存控制块.它提 供 九 标 志：内存块拥仃若
49、；内存块K度：程序等信息。2 2 .什么是文件？文件怎样划分？【解答】：文件是个逻辑上具有完全意义的组相关信息的有序的集合。其通市的划分有：1）按文件的性质和用途可分：系统文件，库文件和用户文件2）按文件的保存期限可分：临时文件，永久文件和档案文件3）按文件的保护级别可分：执行文件，只读文件，读写文件和无保护文件4）按文件的的逻辑结构可分：记录式文件和流式文件5）按文件的的物理结构可分：顺序文件，链接文件和索引文件6）按文件的的存取方式可分：顺序存取文件和随机读取文件2 3.文件系统为用户提供/哪些功能？【解答】：有,1）实现文件从名字空间到外存地址空间的转换2）管理文件的储存空间（即外存）3
50、）建立文件目录4）实现对文件的控制操作和存取操作5）实现文件的共亨、保护和保密2 4.文件的存取方法主要有那些？如 f j 什么特点？【解答】：仃：1）顺序存取.其特点是按照文件的逻辑地址顷序进行，每次存取都是在上次存取的基础上.进行的.2）随机存取.随机存取允许用户以任意的次序读写文件25.文件的物刑组织形式主要仃哪儿种？比较他们的优缺点？【解答】：文件的物理组织形式主要有三种：连续结构、链接结构和索引结构.连续结构的优点是简单只要记住存取信息的当前位苴，则 后 续 信 息 定 在 下 位置上，但要在文件中加载信息时就十分费事链接结构的优点是允许用户扩充或缩小文件，只要词整文件的链接指针就很