考研计算机学科专业基础综合-8-2

考研计算机学科专业基础综合-8-2（总分：150.00,做题时间：90分钟）一、{{B}}单项选择题{{/B}}（总题数:40,分数:80.00）1.下列排序算法中，（）每一趟都能选出一个元素放在最终位置上，并且是不稳定的。（分数：2.00）A.冒泡排序B.希尔排序C.直接选择排序VD.直接插入排序解析：A、C每一趟都能选出一个元素放在最终位置上，但只有C是不稳定的。.某机器指令字长12位，有零地址、一地址、二地址三种指令，地址码长4位，采用扩展操作码技术。若二地址指令和一地址指令条数都取最大值，则该机指令条数最多为（）。（分数：2.00）A.16B.46VC.48D.4366解析：根据题意，二地址指令的操作码长度为12-4X2=4,留一个编码用于扩展，故最多可定义15条二地址指令；一地址指令扩展长度为4位，留一个编码用于扩展，故最多可定义15条一地址指令；零地址指令可在一地址指令的基础上扩展4位，故最多可定义16条零地址指令，根据题意，该机指令条数最多为（15+15+16=）46条。.条件转移指令执行时所依据的条件来自（）。（分数：2.00）A.指令寄存器IRB.程序计数器PCC.程序状态字寄存器PSWRVD.主存地址寄存器MAR解析：程序状态字寄存器PSWR用来保存根据运算结果设置的各种状态位，这些状态位可以被测试；条件转移指令正是通过测试这些状态位来决定是否跳转。.以下（）协议完成了从网卡到IP地址的映射。（分数：2.00）A.ARP协议VB.RARP协议C.IGMP协议D.ICMP协议解析：地址解析协议ARP用来在局域网上从目的IP地址得到目的MAC地址。.假定一台主机的IP地址是6,子网掩码为,该子网地址为（）。（分数：2.00）A.B.VC.D.解析：240的二进制表示是11110000,74的二进制表示是01001010,子网地址的第3字节是二进制01000000,即64o.为了保证操作系统本身的安全，（）是必须加以保护的。（分数：2.00）A.从内核模式转换到用户模式B.从存储操作系统内核的空间读取数据C.从存储操作系统内核的空间读取指令D.打开定时器V解析：打开定时器会影响系统的时间。.系统功能调用是（）。（分数：2.00）A.用户编写的一个子程序.高级语言中的库程序C.操作系统中的一条命令D.操作系统向用户提供的接口V解析：本题考查系统调用的概念。.下面关于图的存储结构的叙述中正确的是（）。（分数：2.00）A.用邻接矩阵存储图占用空间大小只与图中顶点有关，与边数无关VB.用邻接矩阵存储图占用空间大小只与图中边数有关，与顶点无关C.用邻接表存储图占用空间大小只与图中顶点数有关，与边数无关D.用邻接表存储图占用空间大小只与图中边数有关，与顶点数无关解析：.下列哪个选项不可能是微指令格式中的组成部分（）。（分数：2.00）A.操作码字段VB.操作控制字段C.外部条件字段D.下地址字段解析：操作码字段是机器指令的组成部分，垂直型微指令中可能有微操作码字段，水平型微指令中无相应字段，故选A。.关于临界区问题（criticalsectionproblem）是一个算法（假设只有进程P0和P1可能进入该临界区），算法如下（i为0或1）,该算法（）。reapeatretry:if（turnWT）turn:=i；if（turnWi）gotoretry；turn:=-1；criticalSection（临界区）turn=O：remainderSection（其他区域）untialfalse：（分数：2.00）A.不能保证进程互斥进入临界区，且会出现“饥饿”（Starvation）VB.不能保证进程互斥进入临界区，但不会出现“饥饿”C.保证进程能互斥进入临界区，但会出现“饥饿”D.保证进程互斥进入临界区，不会出现“饥饿”解析：例如当PO执行完语句向皿:=-1；进入临界区时，CPU调度P1执行，P1顺利进入临界区，不能满足互斥。当P0执行完临界区时，CPU调度P1执行，P1在retry循环，CPU调度P0执行，P0继续执行，重复以上过程，会导致P1饥饿。.下列关于机器字长与指令字长的说法正确的是（）。（分数：2.00）A.指令字长等于机器字长B.指令字长一定是机器字长的整数倍C.两者长度没有必然关系 VD.以上说法都不对解析：指令字长取决于操作码的长度、操作数地址的长度和操作数地址的个数，与机器字长没有必然的联系；但为了硬件设计方便，指令字长一般取字节或存储字长的整数倍。.前序遍历和中序遍历结果相同的二叉树为（）。（分数：2.00）A.根结点无左孩子的二叉树B.根结点无右孩子的二叉树C.所有结点只有左子树的二叉树D.所有结点只有右子树的二叉树V解析：前序遍历是根结点，左子树，右子树；中序遍历是左子树，根结点，右子树。易知，如果没有左子树，则两者相同。13.某机中，设备号小的主设备在总线判优时具有较高的优先级，其总线判优方式可能是（）。（分数：2.00）A.链式查询方式B.计数器定时查询方式C.独立请求方式D.以上都有可能V解析：三种集中仲裁方式都有可能，其实现方式分别为：链式请求方式下，将总线同意线上靠近仲裁中心的设备分配较小的设备号；计数器定时方式下，计数器从0开始计时；独立请求方式下，通过程序设置赋予设备号较少的主设备较高的优先级。14.一个16端口的二层以太网交换机，冲突域和广播域的个数分别是（）。（分数：2.00）A.1,1B.16,16C.1,16D.16,1V解析：二层以太网交换机的每个端口都是冲突域的终止点，但LAN交换机不隔离广播，所以本题中，冲突域和广播域的个数分别是16和1。.通常对文件系统来说，文件名及其属性可以集中在（）。（分数：2.00）A.目录VB.索引C.字典D.作业控制块解析：目录里存文件名及其基本信息。.假设系统的所有资源是同类型的，系统中的进程每次申请资源数最多1个，那么，下面列出的4种情况中，（）可能发生死锁。情况序号系统中进程数资源总量（分数：2.00）A.12B.21C.22VD.23解析：C当系统的2个进程各拥有1个资源，都申请另一个资源时，会发生死锁，因为没资源分配给它们。17.系统拥有一个CPU,IO1和IO2为两个不同步的输入/输出装置，它们能够同时工作，当使用CPU之后控制转向IO1、IO2时，或者使用IO1、IO2之后控制转向CPU时，由控制程序执行中断处理，但这段处理时间忽略不计。有A、B两个进程同时被创建，进程B的调度优先权比A高。但是当进程A占有CPU时，即使进程B需要占用CPU,也不能打断进程A的执行。若在同一系统中分别单独执行，则需要占用CPU、101、102的时间如下图所示：进程A（分数：2.00）A.CPUVB.IO1C.CPUD.IO2E.CPUF.IO1G.25msH.30msI.20msJ.20msK.20msL.30ms解析：画出甘特图，可得A。18.在HTTP协议中，一个以2开头的响应报文表示（）。（分数：2.00）A.暂时性失败B.永久性失败C.重定向D.成功V解析：HTTP协议中以2开头的响应报文表示请求成功。19.RS-232-C的电气特性规定逻辑“1”的电平范围为（）。（分数：2.00）A.+5〜+15VB.-5〜-15VVC.0〜+5VD.0〜-5V解析：RS-232-C关于电气信号特性的要求，规定逻辑“1”的电平为低于-3V,为了表示一个逻辑1或MARK条件，驱动器必须提供-5V〜-15V之间的电压；为了表示一个逻辑0或SPACE条件，驱动器必须给出+5V〜+15V之间的电压。.某计算机字长8位，采用补码表示小数。若某数真值为-0.1001,则它在该计算机中的机器数形式为（）。（分数：2.00）A.10111B.10110111C.10111000VD.10110000解析：-0.1001=-0.1001000,将-0.1001000连符号位在内取反加1即可得-0.1001000的补码形式：1.0111000。.下列排序算法中，时间复杂度为O（nlogn）且占用额外空间最少的是（）。（分数：2.00）A.堆排序VB.冒泡排序C.快速排序D.希尔排序解析：堆排序占用额外空间为O（1）。.在一个顺序循环队列中删除元素时，首先需要（）。（分数：2.00）A.前移队首指针B.后移队首指针VC.取出队首指针所指位置上的元素D.取出队尾指针所指位置上的元素解析：23.中断向量表中保存的是（）。（分数：2.00）A.被中断程序的返回地址B.中断服务程序入口地址VC.中断服务程序入口地址的地址D.中断优先级解析：中断向量表中保存的是各中断服务程序的入口地址，CPU响应中断时，由硬件生成中断向量（又称中断向量表指针），CPU通过访问该中断向量指出的主存单元就可得到中断服务程序入口地址。.下列二叉排序树中，满足平衡二叉树定义的是（）。（分数：2.00）A.B.VC.D.解析：.下列说法中错误的是（）。（分数：2.00）A.程序查询方式下，CPU与I/O设备串行工作B.程序中断方式下，CPU与I/O设备并行工作C.DMA方式下，主程序可与I/O数据传送并行工作D.实现了DMA方式的系统中，程序中断方式没有存在的必要V解析：DMA方式比较适合成块数据的I/O传送，但在实现了DMA方式的系统中，DMA传送结束时需要用中断方式来通知CPU进行后处理；当有紧急情况发生时，也需要中断方式来进行处理，故D错误。.下列各选项是采用奇偶校验码编码的ASCII码，所有编码都未发生错误，采用偶校验的是（）。（分数：2.00）A.01001101VB.0011001C.10101101D.1101000解析：编码未发生错误，故编码中1的个数为偶数的就是采用偶校验编码的，只有A选项符合。.某通讯线路每20ms采样一次，每一个信号共有64种不同的状态，那么这个线路的传输速率是（）。（分数：2.00）A.100bpsB.200bpsC.300bpsVD.400bps解析：300bps，每次采样可得到6比特，每秒采样50次，那么线路传输速率为300bps。.在（）的情况下，系统出现死锁。（分数：2.00）A.计算机系统发生重大故障B.有多个封锁的进程同时存在C.若干进程因竞争资源而无休止地相互等待对方释放已占有的资源VD.资源数大大小于进程数或进程同时申请的资源数大大超过资源总数解析：本题考查死锁的概念。29.如下图所示一棵二叉排序，其不成功的平均查找长度为（）。（分数：2.00）A.21/7B.28/7VC.15/6D.21/6解析：不带数字的结点均为查找不成功的位置（如下图所示），其平均查找长度为（3*2+4*3+5*2）/7=28/7。.如果I/O设备和存储设备之间的数据交换不经过CPU来完成，则这种交换方式是（）。（分数：2.00）A.程序查询方式B.中断方式C.DMA方式VD.外部总线方式解析：本题考查DMA方式。.浮点运算结果满足下列哪个条件时，需做中断处理（）。（分数：2.00）A.尾数双符号位为“01”B.尾数双符号位为“10”C.阶码双符号位为“01”VD.阶码双符号位为“10”解析：尾数双符号位为“01”或“10”时，说明尾数溢出，需要右规；阶码双符号位为“10”时，说明浮点数下溢，作机器零处理；阶码双符号位为“01”时，说明阶码上溢，需中断处理。.如果对含有n（n〉1）个元素的线性表的运算只有4种：删除第一个元素，删除最后一个元素，在第一个元素前面插入新元素，在最后一个元素的后面插入新元素，则最好使用（）。（分数：2.00）A.只有尾结点指针没有头结点指针的循环单链表B.只有尾结点指针没有头结点指针的非循环单链表C.只有头结点指针没有尾结点指针的循环单链表VD.既有头结点指针也有尾结点指针的循环单链表解析：对于A的链表，删除最后一个结点p时，需要找到p的前一个结点，其时间复杂度为O（n）；对于B的链表，删除第一个结点的p时，需找到头结点，这里没给出头结点指针，故无法实现这种操作。对于C的链表，这4种操作的时间复杂度都为0（1）,对于D的链表，删除最后一个结点p时，需要找到p的前一个结点，其时间复杂度为0（n）。.一个TCP连接总是以1KB的最大段发送TCP段，发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时，如果接下来的4个RTT（往返时间）时间内的TCP段的传输都是成功的，那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时，拥塞窗口大小是（）。（分数：2.00）A.7KBB.8KBC.9KBVD.16KB解析：在拥塞窗口为16KB时发生了超时，那么拥塞窗口就被设为1KB,而阀值就被设为8KB。在接下来的4个成功的TCP段传输中，拥塞窗口先在前三次传输后安装指数增长到8,而第四次成功传输后拥塞窗口只增长1KB,所以最后大小是9KB。.对包含n个关键码的散列表进行检索，平均检索长度为（）。（分数：2.00）A.O（logn）B.O（n）C.O（nlogn）D.不直接依赖于nV解析：对散列表进行检索，平均检索长度仅与装填因子a有关，而与关键字个数n无关。.下列只读存储器中，可编程且可以实现字擦除的是（）。（分数：2.00）A.掩模ROMB.PROMC.EPROMD.EEPROMV解析：掩模ROM和PROM一旦写入就无法擦除；EPROM擦除采用紫外线照射方式，只能实现全部擦除；EEPROM可以使用电擦除，能够实现字擦除或者页擦除，选D。.如果二叉树T2是由有序树T1转换而来的二叉树，那么T1中结点的后序就是T2中结点的（）。（分数：2.00）A.先序B.中序VC.后序D.层次序解析：一般树中一个结点的孩子是无序的，所谓有序树是指树中任一结点的孩子是有序的。由树转换成二叉树的过程可知本题答案为B。37.一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（）。（分数：2.00）A.28字节B.216字节224字节V232字节解析：段内偏移为24位，所以最大长度为224字节。.定点数采用模4补码，即变形补码进行加减运算时，判断溢出的方法是（）。（分数：2.00）A.符号位进位与最高数值位进位相异时表明溢出B.实际参与运算的两数符号位相同，结果又与原操作数符号不同时表明溢出C.双符号位不同时表明溢出D.以上都正确V解析：采用模4补码进行加减运算时，直接通过判断双符号位是否相同来判断溢出最为方便。.下列交换方式中，（）一次连接沿着一条路由路径发送所有的数据。（分数：2.00）A.分组交换B.报文交换C.电路交换VD.以上都不是解析：电路交换在数据传送之前需要建立一条物理通路，然后所有数据都沿着这条建立的通路发送。.以下关于UNIX操作系统的叙述中，（）是错误的。（分数：2.00）A.UNIX对实时系统是不合适的，因为进程在核心态不可抢占B.UNIX终究会在市场上消失的VC.UNIX是目前最流行的操作系统之一D.UNIX比较适用于高档计算机系统和网络环境，它不能用于普通的微机解析：UNIX比较适用于大型机，市场上有它的位置，B太片面了。二、{{B}}综合应用题{{/B}}（总题数:5,分数:70.00）.设算术表达式由字符串b表示，其中可以包括三种括号：圆括号、方括号以及花括号，嵌套的顺序随意，如：“{[（）]（）}"。试编写算法，实现判定给定表达式中所含括号是否正确配对的出现。（分数：10.00）正确答案：（）解析：设tag为括号是否正确配对的标志，用0表示不正确的配对，1表示正确的配对。另设一个栈S。若当前处理字符为左括号，就将对应的右括号进栈。当遇到右括号时，直接与栈顶元素进行比较，若相等，则退栈；否则返回不正确配对标志。当整个算术表达式检测完毕且栈为空时，表示括号正确配对，否则括号不正确配对。算法描述如下：#defineMAX1000intJudgeExp（char*b）{charS[MAX];inti,top=0,tag=1；for（i=0；tag&&b[i]!='/0'；i++）{switch（b[i]）{case'（':s[top++]='）';break;case'[’:S[top++]=']';break;case/{':S[top++]='};break;case'）’:case']’:case'}’:if（top==0||b[i]!=S[--top]）tag=0；break：}}returntop==0&&tag&&b[i]=='/0';}.带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；②选择离u最近且尚未在最短路径中的一个顶点V，加入到最短路径中，修改当前顶点u=v;③重复步骤②，直到u是目标顶点时为止。请问上述方法能否求得最短路径?若该方法可行，请证明之；否则，请举例说明。(分数:15.00)正确答案：()解析：该方法求得的路径不一定是最短路径。例如，对于下图所示的带权图，如果按照题中的原则，从A到C的最短路径为A-B-C,事实上其最短路径为A-D-C。.某计算机字长16位，采用16位定长指令字结构，部分数据通路结构如下图所示。图中所有控制信号为1时表示有效、为O时表示无效。例如控制信号MDRinE为1表示允许数据从DB打入MDR,MDRin为1表示允许数据从内总线打入MDR。假设MAR的输出一直处于使能状态。加法指令"ADD(R1),R0”的功能为(R0)+((R1))—(R1),即将R0中的数据与R1的内容所指主存单元的数据相加，并将结果送入R1的内容所指主存单元中保存。下表给出了上述指令取值和译码阶段每个节拍(时钟周期)的功能和有效控制信号，请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。{{B}}功能和控制信号{{/B}}时钟功能有效控制信号C1MAR-(PC)PCout,MARinC2MDR-M(MAR)PC-(PC)+1MemR,MDRinEPC+1C3IR-(MDR)MDRout,IRinC4指令译码无(分数：13.00)正确答案：()解析：指令执行阶段每个节拍的功能和有效控制信号如下表所示。时钟功能有效控制信号C5MAR-(R1)Rlout,MARinC6MDR-M(MAR)A-(R0)MemR,MDRinER0out,AinC7AC-(A)+(MDR)MDRout,Add,ACinC8MDR-(AC)ACout,MDRinC9M(MAR)-MDRMemW,MDRoatE注意：C6周期中，MDR-M(MAR)的执行过程中并未使用CPU内部总线，故其执行过程中可同时将RO内容送至暂存器A。.某计算机系统字长为32位，包含2个选择通道和1个字节多路通道，每个选择通道上连接了2台磁盘机和2台磁带机，字节多路通道上连接了2台行式打印机、2台读卡器、10台终端。假定各设备的传输率如下：磁盘机：800KB/s磁带机：200KB/s行打机：6.6KB/s读卡机：1.2KB/s终端：1KB/s计算该计算机系统最大I/O数据传输率。(分数：8.00)正确答案：()解析：字节多路通道的最大数据传输率为连接在该通道上的所有设备最大数据传输率之和，题中字节多路通道连接设备如下：行打机：6.6KB/s2台读卡机：1.2KB/s2台终端：1KB/s10台故字节多路通道的最大数据传输率为6.6X2+1.2X2+1X10=25.6(KB/s)选择通道在一段时间内只能为一台设备传送数据，而且此时通道数据传输率等于这台设备的最大数据传输率，故选择通道的最大数据传输率即为连接在该通道上的最快设备的最大数据传输率，题中每个选择通道连接设备如下：磁盘机：800KB/s2台磁带机：200KB/S2台故每个选择通道的最大数据传输率为800KB/s；题中计算机系统包含2个选择通道和1个字节多路通道，故该计算机系统最大I/O数据传输率为：800X2+25.6=1625.6(KB/s)。某请求页式存储管理，允许用户空间为32个页面(每页1KB),主存为16KB。如果一个用户程序有10页长，且某时刻用户进程的页表如下表所示：虚页号物理页号是否在TLB中08是17是24否310否45否53是62是其他notvalid(分数：24.00).如果程序执行遇到以下两个虚地址：0AC5H、1AC5H,试计算它们对应的物理地址。(分数：3.00)正确答案：()解析：12C5H,0AC