CSAI软件设计师辅导与培训资料模拟试题三分析与解答

CSAI软件设计师辅导与培训资料：模拟试题三分析与解答版权所有，严禁转载！2004年度软件设计师级考试模拟试题三上午试题分析与解答试题1已知图G=(V,E),其中V={a,b,c,d,e,f},E={a,b,a,d,a,e,d,e,e,b,c,b,c,e,c,f,f,e},则从该图的顶点a出发的深度优先遍历序列是（1），广度优先遍历序列是（2），其深度优先生成树(或森林)是（3），广度优先生成树(或森林)是（4），该图的一个拓扑序列是（5）。供选择的答案：（1）A.abdecfB.abdcefC.aebdcfD.adebfe（2）A.abcedfB.abdcefC.aebcdfD.abdecf（3）A.B.abedcfabedcfCD.abedcfabedcf（4）A.B.abedcfabedcfC.D.中国系统分析员，，0731-8662005-8000第1页CSAI软件设计师辅导与培训资料：模拟试题三分析与解答版权所有，严禁转载！abedcfabedcf（5）A.abcdefB.aedbefC.adcfebD.acdebf试题1分析：图的深度优先遍历是从图中的某个节点V1出发，访问此节点，然后依次从V1的未被访问的邻接点进行深度优先遍历，直到图中所有和V1有路径相通的节点都被访问到。若此时图中尚有节点未被访问，则选图中的一个未被访问的接点作起点。重复此过程。因此此图的深度优先遍历序列是abdecfaedbCf广度优先遍历是先访问结点V1，然后访问V1连接到的所有未被访问的结点V2，V3，…，Vt，再依次访问V2，V3，…，Vt连接到的所有未被访问的结点。如此进行下去，直到访问遍所有结点.因此此图的广度优先遍历序列是abdecf对于连通图，从图的任一顶点出发进行深度优先遍历时，所经过的边与连通图的所有顶点构成的生成树为图的深度优先生成树；从图的任一顶点出发进行广度优先遍历时，所经过的边与连通图的所有顶点构成的生成树为图的广度优先生成树。对于非连通图，图中的每一个连通分量的生成树的集合为生成森林；按深度优先遍历得到的为深度优先生成森林，按广度优先遍历得到的为广度优先生成森林。因此，图G的深度优先生成森林和广度优先生成森林分别为：abedcfabedcf如果有向图的某个结点序列满足如下条件：若从结点Vi到Vj有一条路径，则在序列中结点Vi必定在Vj之前，则称该序列是一个拓扑序列。任何无环有向图的结点都可以排在一个拓扑序列中。　中国系统分析员，，0731-8662005-8000第2页CSAI软件设计师辅导与培训资料：模拟试题三分析与解答版权所有，严禁转载！拓扑排序的方法是重复执行下列步骤(1)和(2)，直到所有结点均已被输出。　(1)从图中选择一个入度为0的结点且输出之；　(2)从图中删除此结点及其所有的出边。　在可供选择的答案中，C是一个拓扑序列。试题1答案：（1）A（2）D（3）B（4）B（5）C试题2从下列叙述中找出５条正确的叙述：供选择的答案：A.在所有的排序方法中，快速排序的速度昀快，切所需要的附加空间也昀少。B.负载因子是散列表的一个重要参数，它反映散列表的装满程度。C.若一个叶结点是某二叉树中的中序遍历的昀后一个结点，同时它也是该二叉树前序遍历的昀后一个结点。D.在m阶B-树中，所有的非终端节点至少包含[m/2]个结点。E.数据结构是带有结构数据的数据元素的集合。F.具有n个权值的哈夫曼树，其结点数为2n+1。G.用向量和单链表表示的有序表均可使用折半方法来提高查找速度。H.有n个顶点的无向图，采用邻接矩阵表示，图中边数等于邻接矩阵中非零元素之和的一半。I.一个无向连通图的昀小生成树有一棵或多棵J.任何一个有向图的结点都可以排成拓扑排序，而且拓扑排序不唯一试题2分析：A错误。快速排序需要一个额外的栈空间，比堆排序所需要的空间更大。B正确。负载因子＝散列表中填入的记录数哈希表的长度，标志哈希表的装满程度，C正确。D错误。在B-树中，除根结点和叶子结点外，每个结点都至少包含[m/2]个结点。E正确。数据结构DS是数据元素的集合D和D上关系R构成的二元组。F错误。具有n个权值的哈夫曼树，其结点数为2n-1G错误.链表表示的有序表不能用折半法查找H正确.I正确.J错误.试题2答案：（6）B（7）C（8）E（9）H（10）I试题3在一个四道作业的操作系统中，设在一段时间内先后到达6个作业，他们的提交时刻和运行时间如下表所示：---------------------------------------------------------------作业号提交时刻运行时间（分钟）---------------------------------------------------------------中国系统分析员，，0731-8662005-8000第3页CSAI软件设计师辅导与培训资料：模拟试题三分析与解答版权所有，严禁转载！JOB18:0060JOB28:2035JOB38:2520JOB48:3025JOB58:355JOB68:4010---------------------------------------------------------------系统采用短作业优先的调度算法，作业被调入运行后不再退出，但每当一作业进入运行时，可以调整运行的优先次序。按照上述调度原则，JOB1、JOB3、JOB5、JOB6的结束时间分别是（11）、（12）、（13）、（14），作业的平均周转时间是（15）分钟。供选择的答案：（11）A.9:00B.9:20C.9:25D.10:35（12）A.8:45B.9:00C.9:25D.9:55（13）A.8:40B.8:50C.9:00D.9:25（14）A.8:50B.9:00C.9:25D.10:35（15）A.45B.50C.60D.80试题3分析：该题是多道程序设计方式，在有作业到达和离开时，都要选择作业运行。按照短作业优先的调度原则，根据题意，作业一旦进入内存便不离开，因此要考虑当有新作业到来时，尽管该作业可能是昀短的，但内存中已经有了四道作业，该新作业就应该等待哟作业离开是才可以进入内存运行。如下图所示：J1J2J3J3J3J3J5J6J4J2J18:008:208:258:308:358:408:458:509:009:259:5510:35根据图示:8:00J1到达，无竞争者，进入内存8:20J1运行20分钟，剩余40分钟；J2到达，运行时间为35分钟，小于J1,取代J1运行；8:25J1剩余40分钟，J2剩余30分钟；J3到达，运行时间为20分钟，取代J2运行。8:30J1剩余40分钟，J2剩余30分钟，J3剩余15分钟，J4到达，运行时间为25分钟，J3继续运行。8:35J3剩余10分钟，J5到达，运行时间为5分钟，尽管昀短，但内存已经有四道作业，因此，J5不可进入内存，J3继续运行。8:40J3剩余5分钟；J6到达，同理不可以进入内存，J3继续运行。8:45J3运行结束，离开主存。J5昀短，进入内存。8:50J5结束,离开.J6进入,运行时间为10分钟,为昀短,开始运行.9:00J6结束,离开.J1剩余40分钟,J2剩余30分钟，J4剩余25分钟，J4昀短,开始运行.9:25J4结束,离开.J2昀短,开始运行9:55J2结束.J1运行10:35J1结束.中国系统分析员，，0731-8662005-8000第4页CSAI软件设计师辅导与培训资料：模拟试题三分析与解答版权所有，严禁转载！每道作业的周转时间=结束时刻-提交时间J1:8:00—10:35周转时间155分钟J2:8:20—9:55周转时间95分钟J3:8:25—8:45周转时间20分钟J4:8:30—9:25周转时间55分钟J5:8:35—8:50周转时间15分钟J6:8:40—9:00周转时间20分钟平均周转时间=360/6=60分钟.试题3答案：（11）D（12）A（13）B（14）B（15）C试题4(16)操作系统中基本的并行单位、资源分配单位和调度单位.一个(16)通常是(17).，进程可分为(18)进程和(19)进程两类。在多进程的系统中,为了保证公共变量的完整性,各进程应互斥进入临界区.所谓临界区是指(20).供选择的答案：（16）A.过程B.进程C.线程D.作业（17）A.又协处理机执行的一个程序B.一个独立的程序+数据集C.PCB结构与程序与数据的组合D.一个独立的程序（18）A.用户B.静态C.动态D.系统（19）A.用户B.静态C.动态D.系统（20）A.一个缓冲区B.一段数据C.同步机制D.一段程序试题4分析：进程是操作系统中基本的并行单位、资源分配单位和调度单位.通常，进程可分为用户进程和系统进程两类，前者控制用户作业的运行，后者完成系统内部分工的管理工作。进程的静态描述由三部分组成:进程控制块、有关的程序段和该程序段对其进行操作的数据结构的集合.所谓临界区是指不允许多个并发进程交叉执行的一段程序,他是由属于不同并发进程的程序段共享公用数据或公用变量引起的.试题4答案：（16）B（17）C（18）A（19）D（20）D或（18）D（19）A试题5某盘组有5个盘片,其中1个盘面为伺服面,其他盘面为记录数据的盘面,盘面转速为7200RPM.盘存储区域直径为4.1cm,外直径为8.9cm,道密度为40TPM,位密度为300bpm,则该盘的数据盘面数是(21),柱面数是(22),盘组的容量是(23)字节,平均等待时间是(24)ms,数据的传输速率是(25)字节/秒.供选择的答案：（21）A.4B.5C.9D.10（22）A.960B.961C.1920D.1921（23）A.13297837B.13297837.5∏C.106382700D.106382700∏（24）A.0.004167B.0.08334C.4.167D.8.334（25）A.1476000B.1476000∏C.184500D.184500∏试题5分析：中国系统分析员，，0731-8662005-8000第5页CSAI软件设计师辅导与培训资料：模拟试题三分析与解答版权所有，严禁转载！5各盘面共有10面,其中1个伺服盘面不能存放数据,所以共有9各数据盘面.柱面数和每面的磁道数相同,磁道数=道密度*(外道半径-内道半径)+1=40*(89-41)/2+1=961.注意:TPM为每毫米的磁道数盘组容量=数据盘面数*磁道数*内径周长*位密度=9*961*41*300∏=106382700∏bit=13297837.5∏B平均等待时间=每转时间的一半=60/7200/2=0.004167s=4.167ms数据传输率为每秒传输的数据量.即每磁道的数据和传输这些数据的时间的比值.数据传输率41*300*7200∏/60=1476000∏bit/s=184500∏Byte/s.试题5答案：（21）C（22）B（23）B（24）C（25）D试题6存储器是计算机系统的记忆设备,它主要用于存放(26),而存储单元是指(27).存储器系统由分布在计算机各个不同部件的多种存储设备组成：位于CPU内部的寄存器，以及用于CPU的控制存储器。内部存储器是可以被处理器直接存取的存储器，又称为主存储器.它主要由(28)半导体存储器构成.存储器系统的性能主要由存取时间、存储器带宽、存储器周期和数据传输率等来衡量,其中存储周期指的是(29).若一存储器的存储器周期是500ns，而每个周期可访问4字节,则该存储器的带宽是(30).供选择的答案：（26）A.程序B.微程序C.数据D.三者均正确（27）A.存放一个二进制信息位的单元集合B.存放一个字节的单元信息C.存放一个数据的单元集合D.存放一个字的单元集合（28）A.RAM