1、2010年计算机学科专业基础综合试题参考答案一、单项选择题1.D2.3.D4.C5.B6.A7.C8.B9.B10.D11.A12.D13.B14.B15.D16.A17.D18.B19.A20.D21.A22.D23.A24.C25.B26.A27.D28.B29.B30.C31.C32.B33.C34.C35.D36.C37.B38.D39.A40.A1.解析：选项A可由in、in、in、in、out、out、in、out、out、in、out、out得到；选项B可由in、in、in、out、out、in、out、out、in、out、in、out得到；选项C可由in、in、out、in、
2、out、out、in、in、out、in、out、out得到；选项D可由in、out、in、in、in、in、in、out、out、out、out、out得到，但题意要求不允许连续三次退栈操作，故D不可能得到。【另解】先进栈的元素后出栈，进栈顺序为a、b、c、d、e、f,故连续出栈时的序列必然是按字母表逆序的，若出栈序列中出现了长度大于等于3的连续逆序子序列，即为不符合要求的出栈序列。2.解析：本题的队列实际上是一个输出受限的双端队列。A操作：a左入（或右入）、b左入、c右入、d右入、e右入。B操作：a左入（或右入）、b左入、c右入、d左入、e右入。D操作：a左入（或右入)、b左入、c左入、d
3、右入、e左入。C操作：a左入（或右入）、b右入、因d未出，此时只能进队，c怎么进都不可能在b和a之间。【另解】初始时队列为空，第1个元素a左入（或右入），而第2个元素b无论是左入还是右入都必与a相邻，而选项D中a与b不相邻，不合题意。3.解析：题中所给二叉树的后序序列为d,b,c,a。结点d无前驱和左子树，左链域空，无右子树，右链域指向其后继结点b;结点b无左子树，左链域指向其前驱结点d;结点c无左子树，左链域指向其前驱结点b,无右子树，右链域指向其后继结点a。故选D。4.解析：插入48以后，该二叉树根结点的平衡因子由-1变为-2，在最小不平衡子树根结点的右子树(R)的左子树(L)中插入新结点
4、引起的不平衡属于L型平衡旋转，需要做两次旋转操作（先右旋后左旋)。242413532453379037(9013908。144.调整后，关键字37所在结点的左、右子结点中保存的关键字分别是24、53。5.解析：设树中度为i(=0,1,2,3,4)的结点数分别为N,树中结点总数为N,则树中各结点的度之和等于N-1,即N=1+N,+2N2+3N3+4N4=No+N1+N2+N3+N4,根据题设中的数据，即可得到No82,即树T的叶结点的个数是82。6.解析：哈夫曼树为带权路径长度最小的二叉树，不一定是完全二叉树。哈夫曼树中没有度为1的结点，B正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左、
5、右子树构造一棵新的二叉树，C正确：哈夫曼树中任一非叶结点P的权值为其左、右子树根结点权值之和，其权值不小于其左、右子树根结点的权值，在与结点P的左、右子树根结点处于同一层的结点中，若存在权值大于结点P权值的结点Q,那么结点Q的兄弟结点中权值较小的一个应该与结点P作为左、右子树构造新的二叉树。综上可知，哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。7.解析：要保证无向图G在任何情况下都是连通的，即任意变动图G中的边，G始终保持连通，首先需要G的任意6个结点构成完全连通子图G1,需n(n-1)/2=6(6-1)/2=15条边，然后再添一条边将第7个结点与G1连接起来，共需16条边。8
6、.解析：拓扑排序的过程如下图所示。a输出e一又输出b输出b输出e输出c)输出c输出c输出e又输出d,得到aebed输出d得到abecd输出d,得到abced可以得到3个不同的拓扑序列，分别为：abced、.abecd、aebcd。9.解析：折半查找法在查找成功时进行的关键字比较次数最多为1og2+1,即判定树的高度；折半查找法在查找不成功时进行的关键字比较次数最多为1og2+1。题中n=16,因此最多比较1og216+1=5次。也可以画出草图求解。思考：若本题题干改为求最少的比较次数呢？10.解析：快递排序的递归次数与元素的初始排列有关。如果每一次划分后分区比较平衡，则递归次数少：如果划分后分
7、区不平衡，则递归次数多。但快速排序的递归次数与分区处理顺序无关，即先处理较长的分区或先处理较短的分区都不影响递归次数。145第三组(2个芯片并联)：1000H17FFH。第四组(2个芯片并联)：1800H1FFFH。地址0B1FH所在的芯片属于第二组，故其所在芯片的最小地址为0800H16.解析：RAM(分为DRAM和SRAM)断电后会失去信息，而ROM断电后不会丢失信息，它们都采用随机存取方式（注意，采用随机存取方式的存储器并不一定就是随机存储器）。Cache一般采用高速的SRAM制成，而ROM只可读，不能用作Cache,I错误。DRAM需要定期刷新，而ROM不需要刷新，故IV错误。17.解
8、析：Cache中存放的是主存的一部分副本，TLB(快表)中存放的是Pagc(页表)的一部分副本。在同时具有虚拟页式存储器（有TLB)和Cache的系统中，CPU发出访存命令，先查找对应的Cache块。I)若Cache命中，则说明所需内容在Cache内，其所在页面必然已调入主存，因此Page必然命中，但TLB不一定命中；2)若Cache不命中，并不能说明所需内容未调入主存，和TLB、Page命中与否没有联系。但若TLB命中，Page也必然命中；而当Page命中，TLB则未必命中，故D不可能发生。主存、Cache、TLB和Page的关系如下图所示。主存PageTLBCache【提示】本题看似既涉及
9、虚拟存储器又涉及Cache,实际上这里并不需要考虑Cache命中与否。因为一旦缺页，说明信息不在主存，那么TLB中就一定没有该页表项，所以不存在TLB命中、Page缺失的情况，也根本谈不上访问Cache是否命中。18.解析：读者首先必须明白“汇编语言程序员可见”的含义，即汇编语言程序员通过汇编程序可以对某个寄存器进行访问。汇编程序员可以通过指定待执行指令的地址来设置PC的值，如转移指令、子程序调用指令等。而IR、MAR、MDR是CPU的内部工作寄存器，程序员无法直接获取和设置它们的值，也无法直接对它们进行其他操作，所以对程序员不可见。【提示】指令寄存器R中的内容总是根据PC所取出的指令代码。在
10、CPU的专用寄存器中，只有PC和PSWR是汇编程序员可见的。19.解析：采用流水线方式，相邻或相近的两条指令可能会因为存在某种关联，后一条指令不能按照原指定的时钟周期运行，从而使流水线断流。有三种相关可能引起指令流水线阻塞：结构相关，又称资源相关；数据相关：控制相关，主要由转移指令引起。而数据旁路技术，其主要思想是不必待某条指令的执行结果送回到寄存器，再从寄存器中取出该结果，作为下一条指令的源操作数，而是直接将执行结果送到其他指令所需要的地方，这样可以使流水线不发生停顿。20.解析：典型的总线标准有：ISA、EISA、VESA、PCI、PCI-Express、AGP、USB、RS-232C等。
11、A中的CRT是纯平显示器：B中的CPI是每条指令的时钟周期数；C中的RAM是半导体随机存储器、MPS是每秒执行多少百万条指令数。21.解析：147允许进入表示，这样可以保证当两个进程同时要求进入临界区时只允许一个进程进入临界区。保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入。先到先入，后到等待，从而完成临界区访问的要求。其实这里可以想象为两个人进门，每个人进门前都会和对方客套一句“你走先”。如果进门时没别人，就当和空气说句废话，然后大步登门入室；如果两人同时进门，就互相请先，但各自只客套一次，所以先客套的人请完对方，就等着对方请自己，然后光明正大地进门。28.解析：最佳适配算法是指每
12、次为作业分配内存空间时，总是找到能满足空间大小需要的最小的空闲分区给作业，可以产生最小的内存空闲分区，如图3-2所示。6MB15MB15MB15MB15MB9MB55MB30MB30MB30MB30MB40MB8MB10MB10MB8MB2MB2MB初始分配分配释放分配分配15MB30MB15MB8MB6MB29.解析：页大小为2B,页表项大小为2B,故一页可以存放2”个页表项，逻辑地址空间大小为26页，即共需216个页表项，则需要2162=2=128个页面保存页表项，即页目录表中包含表项的个数至少是128。30.解析：每个磁盘索引块和磁盘数据块大小均为256B,每个磁盘索引块有256/4=6
13、4个地址项。因此，4个直接地址索引指向的数据块大小为4256B:2个一级间接索引包含的直接地址索引数为2(256/4),即其指向的数据块大小为2(256/4)256B。1个二级间接索引所包含的直接地址索引数为(256/4)(256/4)，即其所指向的数据块大小为(256/4)(256/4)256B。即7个地址项所指向的数据块总大小为4256+2(256/4)256+(256/4)(256/4)256=1082368B=1057KB。31.解析：当一个文件系统含有多级目录时，每访问一个文件，都要使用从树根开始到树叶为止、包括各中间结点名的全路径名。当前目录又称工作目录，进程对各个文件的访问都相对于当前目录进行，而不需要从根目录一层一层的检索，加快了文件的检索速度。选项AB都与相对目录无关：选项D,文件的读/写速度取决于磁盘的性能。32.解析：键盘是典型的通过中断/O方式工作的外设，当用户输入信息时，计算机响应中断并通过中断处理程序获得输入信息。33.解析计算机网络的各层及其协议的集合称为体系结构，分层就涉及到对各层功能的划分，因此A、B、D正确。体系结构是抽象的，它不包括各层协议的具体实现细节。计算机网络中在讲解网络层次时，仅有讲各层的协议和功能，而内部实现细节则没有提及。内部实现细节是由具体设备厂家来确定的。149