1、计算机学科专业基础综合模拟1 模拟 计算机学科专业基础综合模拟1单项选择题第1题：利用栈求表达式的值时，设立运算数栈OPND。假设OPND只有两个存储单元，在下列表达式中，不发生溢出的是( )。A.AB*(CD)B.(AB)*CDC.(AB*C)DD.(AB)*(CD)参考答案：B 第2题：已知输入序列为abcd，经过输出受限的双端队列后，能得到的输出序列是( )。A.dacbB.cadbC.dbcaD.以上答案都不对参考答案：B 输出受限的双端队列是指删除限制在一端进行，而插入允许在两端进行的队列。 分析选项A，输入序列为abcd，输出序列为dacb，由输出受限性质可知以da开头的结果只有d
2、abc，选项A为错误答案。 分析选项B，输入序列为abcd，输出序列为cadb，其输入输出顺序为：先在输出端输入a，然后在非输出端输入b，这时队列中的序列为ba，再在输出端输入c，这时队列中的序列为bac：；输出c，再输出a；再在输出端输入d，这时队列中的序列为bd；输出d，再输出b。最后得到输出序列为cadb。 分析选项C，输入序列为abcd，输出序列为dbca，由输出受限性质可知以db开头的结果只有dbad，选项C为错误答案。第3题：一个具有1025个结点的二叉树的高度为( )。A.11B.10C.11至1025之间D.10至1024之间参考答案：C 一棵二叉树每层只有1个结点，则具有10
3、25个结点的二叉树的最大高度为1025。一个具有1025个结点的完全二叉树的高度为11。这一个具有1025个结点的二叉树的高h为11至1025之间。第4题：以下关于二叉排序树的说法正确的是( )。 在二叉排序树中，每个结点的关键字都比左孩子关键字大，比右孩子关键字小 每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树都是二又排序树 在二叉排序树中，新插入的关键字总是处于最底层 在二叉排序树中，新结点总是作为叶子结点来插入的 二叉排序树的查找效率和二叉排序树的高度有关A.、B.、C.、D.、参考答案：D 对于二叉排序树，左子树上所有记录的关键字均小于根记录的关键字；右子树上所有记
4、录的关键字均大于根记录的关键字。而不是仅仅与左、右孩子的关键字进行比较。 在二叉排序树中，新插入的关键字总是作为叶子结点来插入的，但是叶子结点不一定总是处于最底层。 对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的ASL值，显然，由值相同的n个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大。最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log2n成正比。第5题：简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻接矩阵为A1.n，1.n，且压缩存储在B1.k，则k的值至少为( )。A.n(n+1)
5、/2B.n2/2C.(n-1)(n+1)/2D.n(n-1)/2参考答案：D 简单无向图的邻接矩阵是对称的，且对角线元素均是0，故压缩存储只需存储下三角或是上三角(均不包括对角线)即可。故有(上三角形式)： k=(n-1)+(n-2)+1+0=n2-(1+2+n)=n(n-1)/2。第6题：若无向图G=(V，E)中含8个顶点，为保证图G在任何情况下都是连通的，则需要的边数最少是( )。A.7B.21C.22D.28参考答案：C 本题考查图的基本概念。 要保证无向图G在任何情况下都是连通的，即任意变动图G中的边，G始终保持连通。首先需要图G的任意7个结点构成完全连通子图G1，需n(n-1)/2=
6、7(7-1)/2=21条边，然后再添加一条边将第8个结点与G1连接起来，共需22条边。 本题非常容易错误地选择选项A，主要原因是对“保证图G在任何情况下都是连通的”的理解，分析选项A，在图G中，具有8个顶点7条边并不能保证其一定是连通图，即有n-1条边的图不一定是连通图。 分析选项D，图G有8个顶点28条边，那么图G一定是无向完全图，无向完全图能保证其在任何情况下都是连通的，但是这不符合题目中所需边数最少的要求。第7题：在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值( )。A.一定都是同义词B.一定都不是同义词C.不一定都是同义
7、词D.都相同参考答案：C 采用线性探测法处理冲突会产生堆积，即非同义词争夺同一个后继地址。第8题：如果将中国人按照生日(不考虑年份，只考虑月、日)来排序，那么使用下列排序算法中最快的是( )。A.归并排序B.希尔排序C.快速排序D.基数排序参考答案：D 按照所有中国人的生日(月、日)排序，一方面待排序记录个数n是非常大的，另一方面关键字所含的排序码为2，且一个排序码基数为12，另一个为31，都是较小的常数值，采用基数排序可以在O(n)内完成排序过程。第9题：用某种排序方法对线性表(25，84，21，47，15，27，68，35，20)进行排序时，元素序列的变化情况如下： (1)25，84，21
8、，47，15，27，68，35，20 (2)20，15，21，25，47，27，68，35，84 (3)15，20，21，25，35，27，47，68，84 (4)15，20，21，25，27，35，47，68，84 则采用的排序方法是( )。A.选择排序B.希尔排序C.二路归并排序D.快速排序参考答案：D 本题主要考查各种排序的手工排序过程。 选择排序在每趟结束后可以确定一个元素的最终位置，而题中第一趟结束后最小关键字并未出现在第一个位置；归并排序会在第一趟结束后，形成若干个部分有序的子序列，并且长度递增，直到最后的一个有序的完整序列；希尔排序也是形成部分有序的序列；快速排序以某个元素为界将
9、大于它和小于它的关键字划分为两个子序列，再将该元素放在中间。观察题中的元素排序过程，可知是快速排序。第10题：15的八位二进制反码表示为( )。A.00001111B.10001111C.11110000D.11110001参考答案：C A选项为+15，B选项为-15的原码，D选项为-15的补码。 归纳总结 正数的原码、补码和反码的表示形式是相同的，都等于真值本身，而负数的原码、补码和反码各有不同的表示，其中反码表示法是将真值的数值部分按位取反。 解题技巧 因为这是一个负数，所以可以首先排除掉选项A。然后可以看出选项B、C、D分别代表-15的原码、反码和补码。第11题：设数据码字为100100
10、11，采用海明码进行校验，若仅考虑纠正一位错，则必须加入的(冗余)位数是( )。A.2B.3C.4D.5参考答案：C 如果仅考虑纠正1位错的情况，只要满足2kn+k+1就可以了(设校验位的位数为k，信息位的位数为n)。此题中因为n=8，所以k4。如果在纠正l位错的同时还要能发现2位错，则满足2k-1n+k+1。海明码实现原理是：在有效信息位中加入几个校验位形成海明码，使码距比较均匀地拉大，并把海明码的每一个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现错误，还能指出错误的位置，为自动纠错提供了依据。第12题：如果X为负数，则已知X补求-X补
11、的方法是( )。A.X补各值保持不变B.X补符号位变反，其他各位不变C.X补除符号位外，各位变反，末位加1D.X补连同符号位一起，各位变反，末位加1参考答案：D -X补被称为X补的机器负数，由X补求-X补的过程称为对X补变补(求补)，这是做减法运算时必须要完成的操作。不管X的真值为正或为负，已知X补求-X补的方法是：将X补连同符号位一起求反，末尾加“1”。X补表示的真值如果是正数，则变补后X补所表示的真值变为负数；反过来，X补表示的真值如果是负数，则变补后一X补所表示的真值变为正数。此题容易错选选项C。如果除符号位外，各位变反，末位加1，得到的是X原而不是-X补，且只有X为负数时成立。第13题
12、：下面是有关DRAM和SRAM存储器芯片的叙述： DRAM芯片的集成度比SRAM高 DRAM芯片的成本比SRAM高 DRAM芯片的速度比SRAM快 DRAM芯片工作时需要刷新，SRAM芯片工作时不需要刷新 通常情况下，错误的是( )。A.和B.和C.和D.和参考答案：B DRAM的集成度高于SRAM，SRAM的速度高于DRAM，可以推出DRAM的成本低于SRAM，SRAM 芯片工作时不需要刷新，DRAM芯片工作时需要刷新。 随机存储器RAM又可分为静态RAM(SRAM)和动态RAM(DRAM)两种。SRAM由6个MOS管组成一个记忆单元，它的存取速度快，但集成度低，功耗也较大；DRAM由4个M
13、OS管或单个MOS管组成一个记忆单元，它的集成度高，功耗小，但存取速度慢。DRAM是靠MOs电路中的栅极电容来存储信息的，栅极电容上的电荷数目会随着时间推移逐步泄漏，因此每隔一定的时间必须向栅极电容补充一次电荷，这个过程称为“刷新”。这类选择题是由多选题改造而来的单选题，其难度高于普通的单选题。在解题时需要首先判断多段叙述中各自的正确性，然后再在四个选项中挑选正确的选项。第14题：若想对某个寄存器中的某几位清零，可以使用的一条指令是( )。A.ANDB.ORC.NOTD.XOR参考答案：A 对某个寄存器中的某几位清零又称为按位清，将此寄存器的内容和一个特定的源操作数做“与”运算，即可得到。一般
14、计算机都具有与、或、非和异或等逻辑运算指令。这类指令在没有设置专门的位操作指令的计算机中常用于对数据字(字节)中某些位(一位或多位)进行操作。如利用“与”指令还可以使目的操作数的某些位置为“0”。只要源操作数的相应位为“0”，其余位为“1”，然后执行“与”指令即可。利用“或”指令可以使目的操作数的某些位置为“1”。只要源操作数的相应位为“1”，其余位为“0”，然后执行“或”指令即可。 此题容易错选选项D，XOR指令可以实现对整个寄存器的全部位清零的功能，但不能实现对指定的某几位清零的功能。第15题：设指令由取指、分析、执行3个子部件完成，每个子部件的工作周期均为t，采用常规标量流水线处理机。若
15、连续执行10条指令，则共需时间是( )。A.8tB.10 tC.12tD.14t参考答案：C 具有3个功能段的流水线连续执行10条指令共需时间=3t+9t=12t。 流水线在开始时总要有一段建立时间，结束时又需要有排空的时间，设-m段流水线的各段经过时间均为t，则需要T。一mt的流水建立时间，之后每隔t就可流出一条指令，完成n个任务共需时间Tmt+(n一1)t。第16题：某计算机的指令系统中共有101条不同的指令，采用微程序控制方式时，控制存储器中具有的微程序数目至少是( )。A.101B.102C.103D.104参考答案：B 除去101条机器指令所对应的101个微程序外，至少还有一个取指微
16、程序，所以至少有102个微程序。通常，一条机器指令对应一个微程序。由于任何一条机器指令的取指令操作都是相同的，因此可以将取指令操作抽出来编成一个独立的微程序，这个微程序只负责将指令从主存中取出送至指令寄存器。此外，也可以编出对应间址周期的微程序和中断周期的微程序。这样，控制存储器中的微程序个数应等于指令系统中的机器指令数再加上对应的取指、间址和中断周期等公用的微程序数。若指令系统中具有n种机器指令，则控制存储器中的微程序数至少有n+1个。第17题：某总线有104根信号线，其中数据总线(DB)32根，若总线工作频率为33MHz，则其理论最大传输率是( )。A.33 MB/sB.64MB/sC.1
17、32 MB/sD.164 MB/s参考答案：C 在总线的104根信号线中，数据总线占32根，也就是4个字节，由于总线工作频率为33MHz，所以理论的最大数据传输率=4B33MHz=132MB/s。总线的最大数据传输率又称总线带宽，即每秒传输的字节数。总线带宽=总线宽度总线频率。第18题：RGB8:8:8表示一帧彩色图像的颜色数是( )。A.23B.28C.224D.2512参考答案：C RGB8:8:8是指红、绿、蓝3种颜色都各有8位，总共的颜色深度为24位，所以颜色数为224种。颜色深度与颜色数的对应关系是：颜色数=2颜色深度。第19题：关于程序中断方式和DMA方式的叙述中错误的是( )。
18、若同时接到DMA请求和中断请求，CPU优先响应DMA请求 程序中断需要保护现场，DMA方式不需要保护现场 程序中断方式的中断请求是为了报告CPU数据的传输结束，而DMA方式的中断请求完全是为了传送数据 中断方式和DMA方式中，快速I/O设备更适合采用中断方式传递数据A.、B.、C.、D.、参考答案：C 中断和DMA方式是I/O设备与主机间交换数据常采用的传送控制方式，在这两种控制方式下，CPU和I/O设备可以并行工作。DMA方式的中断请求是为了报告CPU数据的传输结束。中断方式需要执行中断服务程序，并且完成一次程序中断还需要许多辅助操作，所以它主要适用于中、低速外设。 中断方式下，外设在做好输
19、入输出准备时，向主机发中断请求，主机接到请求后就暂时中止原来执行的程序，转去执行中断服务程序对外部请求进行处理，在中断处理完毕后返回原来的程序继续执行。DMA方式是在主存和外设之间开辟直接的数据通路，可以进行基本上不需要CPU介入的主存和外设之间的信息传送，这样不仅能保证CPU的高效率，而且能满足高速外设的需要。 中断方式和DMA方式的主要区别为： (1)中断方式是程序切换，需要保护和恢复现场；而DMA方式除了开始和结尾时，不占用CPU的任何资源。 (2)对中断请求的响应时间只能发生在每条指令执行完毕时；而对DMA请求的响应时间可以发生在每个机器周期结束时。 (3)中断传送过程需要CPU的干预
20、；而DMA传送过程不需要CPU的干预，故数据传输速率非常高，适合于高速外设的成组数据传送。 (4)DMA请求的优先级高于中断请求。 (5)中断方式具有对异常事件的处理能力，而DMA方式仅局限于完成传送数据块的I/O操作。第20题：构造操作系统的主要结构模式是( )。 整体式结构 层次式结构 微内核结构(客户/服务器) 对称式结构A.和B.和C.、和D.、和参考答案：C 操作系统是一种大型的、复杂的系统软件，为了合理地使用操作系统，必须分析、了解并掌握其结构。在操作系统的发展过程中，出现了多种操作系统结构，整体式结构是早期操作系统设计中所采用的方法，即首先确定操作系统的总体功能，然后将总功能分解
21、为若干个子功能，实现每个子功能的程序称为模块。层次式结构力求使模块间调用的无序性变为有序性。因此层次式结构最内层是裸机，裸机的外层是操作系统的第一层，以后每增加一层软件就是在原虚拟机上的又一次扩充，又成为一个新的虚拟机。微内核(客户/服务器)结构的操作系统适宜于应用在网络环境下分布式处理的计算环境中。内核只提供了一个很小的功能集合。除内核部分外，操作系统所有的其它部分被分成若干个相对独立的进程，每一个进程实现一组服务，称为服务进程。这些服务进程可以提供各种系统功能、文件系统服务以及网络服务等。对称式结构在操作系统结构设计中是不存在的。第21题：一个支持并发的操作系统在运行过程中，调度模块会不断
22、地选择新进程运行。在非抢先式操作系统中，下面不是引起操作系统重新选择新进程的直接原因是( )。A.分配的时间片用完B.运行着的进程要等待某一信号到来C.正在运行的进程出错D.有新进程进入就绪队列参考答案：D 本题考查进程调度的时机。在所列出的四个选项中，A、B和C的情况一旦发生，处理机空闲，操作系统必须立即调度其他进程，而D选项有新的进程进入就绪状态，如果操作系统采用的是抢先式调度，则立即激活调度模块，进行进程调度，进程调度的结果可能引起进程切换，也可能维持当前进程运行而不切换；而当操作系统采用非抢先式调度方式时，当新进程进入就绪状态，若此时处理机正在忙于处理当前运行进程的请求，则不会激活调度
23、模块。这里需要了解进程调度的细节问题。第22题：一个正在访问临界资源的进程由于申请等待IO操作而被中断时，它是( )。A.可以允许其它进程进入与该进程相关的临界区B.不允许其它进程进入任何临界区C.可以允许其它进程抢占处理机，但不得进入该进程的临界区D.不允许任何进程抢占处理机参考答案：C 进程进入临界区必须满足互斥条件，当进程进入临界区但是尚未离开时就被迫进入阻塞是可以的，系统中经常有这样的情形。在此状态下，只要其它进程在运行过程中不寻求进入该进程的临界区，就应该允许其运行。该进程所锁定的临界区是不允许其他进程访问的，其他进程若要访问，必定会在临界区的“锁”上阻塞，期待该进程下次运行时可以离
24、开并将临界区交给它。所以正确选项为C。第23题：在连续内存分配管理中，分区分配是最简单的实现并发的内存管理方法。对于该方法，进行内存保护的措施是( )。A.存取控制列表B.用户权限保护C.程序状态保护D.界地址保护参考答案：D 本题考查分区保护的主要措施。在分区分配内存管理方法中，最常采用的方法是界地址保护法和基址、限长寄存器保护法。界地址保护法将每一个进程在内存中的物理位置的上界和下界值存放到上下界地址寄存器中，进程的每一条指令或数据的物理地址均与这两个上下界寄存器比较，一旦低于下界寄存器或大于上界寄存器均发生越界中断，从而起到保护作用。基址、限长寄存器保护法是上述方法的改进。将进程的逻辑地
25、址与限长寄存器比较，一旦越界就发出中断，从而保护内存。基址寄存器主要是用来进行逻辑地址到物理地址的转换。第24题：某简单分页式存储管理中，地址空间分页为每页1KB，对应相应的物理块。设主存总容量为256KB，描述主存分配情况的位示图如下所示(0表示未分配，1表示已分配)，此时，操作系统创建了一个新进程，大小为2.5KB，按首先分配低址空间的策略，那么，分配给该进程的页面的页号分别是( )。A.17、21和22B.21、22和23C.23、24和25D.29、30和31参考答案：A 本题考查简单页式地址分配和转换的计算。根据题目给出的条件，进程的大小为2.5KB，它所需要占用的空间为3页，对应3
26、个物理块。按题意是从地址的低址部分开始分配，因此，查看位示图，我们看到从低到高分别是17、21和22空闲，则进行分配。若考虑程序运行的优化，则希望这3页装入内存时放到一起，则21-25以及29-31均可以使用，而29-31的分配更加有利，可以使得内存效率更高，硬件使用更均衡。由于页式分配的特点，虽然页面的分配可以离散化，理论上可以分配在内存中的任何地方，但是从内存使用的效率和均衡，以及对于代码优化，快表更新和减少转移引起的缺页中断等方面考虑，尽量集中分配对整个系统还是更加有利的。本题并不考查这一点，所以按最简单的算法去分配即可。第25题：分页式虚拟存储管理系统中，页面的大小与可能产生的缺页中断
27、次数是( )。A.成正比B.成反比C.无关系D.固定值参考答案：C 在分页存储管理系统中，页面的大小是由计算机系统的地址结构所决定的，一般由软硬件共同决定。对于某一种系统一般采用一种大小的页面(也有部分现代操作系统采用双页面系统的)。在确定地址结构时，若选择的页面较小，一方面可使内碎片减小，并减少了内碎片的总空问，有利于提高内存利用率。另一方面，也会使每个进程要求较多的页面，从而导致页表过长，占用大量内存。此外还会降低页面换进换出的效率。若选择的页面较大，虽然可减少页表长度，提高换进换出效率，但却又会使页内碎片增大。由于内存的大小是固定的，所以无论页面是大是小，可以进入内存的作业大小也是固定的
28、，最多不超过内存的大小。实际上，分页的大小并不影响进入内存作业的数量。从宏观上看，进入内存的页面内容是没有变化的。所以分页式虚拟存储管理系统中，页面的大小与可能产生的缺页中断次数关系并没有确定的关系。正确答案为c。第26题：某一个磁盘共有16个盘面，每个盘面上从外到内共有30000个磁道(或称30000个柱面)，每个磁道有250个扇区。假定存储信息时以一个扇区作为一个存储块，盘面号(磁头号)、磁道号和扇区号均从0开始编号，那么，盘块号1002578对应的盘面号、磁道号和扇区号是( )。A.1，2500，78B.10，250，78C.2，250，161D.0，4010，78参考答案：C 本题考查
29、磁盘的结构。磁盘的存储是按照磁头(或盘面)，磁道(或柱面)和扇区三要素唯一确定的，但是，在具体的使用时，是将所有的可用存储块按一维编号来进行分配的，称为逻辑地址。由于多盘面的磁盘系统中所有的磁头装在同一个转动轴上，是同步一起移动的，所以选择高效的编址方式能够提高磁盘的读写时间。不同于按磁头、磁道、扇区的顺序编址，多盘组磁盘的编址首先是按磁道来编，从磁盘外边缘到磁盘中心从0开始编号，本题中是0到29999。确定了磁道，接下去随着磁盘的转动，所有磁头一起从某一起始点开始，寻找扇区，扇区的编号也是从O开始，本题中是0到249。找到扇区后再按磁头寻找，磁头从上到下从0开始编号，本题中是0到15。在了解
30、了盘组磁盘的编址方式后，下面的计算就比较简单了。首先确定磁道，1002578(25016)并下取整(即舍去小数部分)得250，得到磁道号，余下逻辑块编号的偏移量是2578，接下去确定扇区号，257816并下取整得161，得到扇区号，余下逻辑块编号的偏移量是2，此号便是磁头号了，所以，其对应的三要素单位为2，250，161。第27题：现代操作系统中，文件系统都有效地解决了重名问题，允许不同的文件可以有相同的文件名。那么，实现该功能的主要方法是( )。A.重名翻译机构B.建立索引表C.建立指针D.建立树形目录结构参考答案：D 本题考查文件系统重名问题的解决。树形目录的引入使文件重名的问题得到解决。树形文件目录是多级目录，最初的目录称为根目录，其余目录称为子目录。每一个目录下可以存放不同的文件，相同文件名的文件(可能内容是不同的)，可以存放在不同的目录下，从而解决了文件重名问题。第28题：设备管理中，能够用空间换取时间的技术是( )。A.SPOOLing技术B.虚拟存储技术C.覆盖与交换技术D.通道技术参考答案：A 本题考查SPOO
