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

《考研计算机学科专业基础综合-20》由会员分享，可在线阅读，更多相关《考研计算机学科专业基础综合-20（16页珍藏版）》请在装配图网上搜索。

1、考研计算机学科专业基础综合 -20( 总分： 150.00 ，做题时间： 90 分钟 )一、 单项选择题 ( 总题数： 40，分数： 80.00)1. 下列有关数据存储结构的叙述中，正确的是 ( ) 。A. 顺序存储方式只能用于存储线性结构B. 顺序存储方式的优点是占用存储空间小，插入、删除等操作效率高C. 链表的每个结点中都恰好含有一个指针D. Hash存储的基本思想是由关键词的值决定数据的存储地址(分数： 2.00 )A.B.C.D. V解析：顺序存储方式除了用于存储线性结构外，还能存储数组或完全二叉树等非线性结构。插入、删除操 作时，由于要移动大量的数据，执行效率低，链表的形式有单链表、

2、双链表和多重链表，除了单链表外， 其他链表中的结点需要两个以上的指针。2. 以数组Datam+1作为循环队列SQ的存储空间，front为头指针，rear为队尾指针，则执行出队操作的 语句是 ( ) 。A. front=front+1 B . front=(front+1)%mC. front=(front+1)%(m+1) D . rear=(rear+1)%m(分数： 2.00 )A.B.C. VD.解析：3. 设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是()。A. n在m右方B . n是m祖先C . n在m左方D . n是m子孙(分数： 2.00 )A.B.C. VD.

3、解析：中序遍历时，先访问左子树，再访问根结点。n在m前，则n必须在m的左子树中。因此本题答案为 C。4. 前序遍历和后序遍历结果相同的二叉树为( ) 。A. 只有根结点的二叉树 B .根结点无左孩子的二叉树C. 根结点无右孩子的二叉树D 所有结点只有左子树的二叉树分数： 2.00 )B.C.D.解析：使用特值法，排除 B、C D选项。5. 已知一个线性表为(38 , 25, 74, 63, 52, 48)，假定采用H(K)=Kmod7计算散列地址进行散列存储，若利 用线性探测的开放定址法处理冲突，则在该散列表上进行查找的平均查找长度为( )；若利用链地址法处理冲突,则在该散列上进行查找的平均查

4、找长度为 ( ) 。A1.5, 1 B1.7, 3/2 C 2, 4/3 D 2.3, 7/6(分数： 2.00 )A.B.C. VD.解析：若利用线性探测的开放定址法处理冲突,发生 0次冲突的关键字有 3个, 1次冲突的 1个, 2次冲突 的1 个, 3次冲突的 1 个,因而在该散列表上进行查找的平均查找长度为 ASL=(3*1+1*2+1*3+1*4)/6=2 ；若 利用链地址法处理冲突,同一链表上有 1 个元素的线性链表有 2 个,有 2 个元素的线性链表有 2 个,因此 ASL=(4*1+2*2)/6=4/3 。6. 关于AVL(平衡二叉树)，下列说法错误的是()。A. 左子树与右子树

5、高度差最多为1B. 插入操作的时间复杂度为O(log n)C. 平衡二叉树是二叉排序树中的一种D. 使用平衡二叉树的目的是为了节省空间(分数： 2.00 )A.B.C.D. V 解析：平衡二叉树没有节省空间,引入其目的是防止排序二叉树左、右子树高度失衡7. 下面关于对图的操作的说法不正确的是 ( ) 。A. 寻找关键路径是关于带权有向图的操作B. 寻找关键路径是关于带权无向图的操作C. 连通图的生成树不一定是唯一的D. 带权无向图的最小生成树不一定是唯一的(分数： 2.00 )A.B. VC.D.解析：8. 在文件局部有序或文件长度较少的情况下,最佳的内部排序方法是 ( )A. 直接插入排序B

6、 冒泡排序C. 简单选择排序D 堆排序(分数： 2.00 )A. VB.C.D.解析：9. 下列( ) 是一个堆。A19，75，34，26，97，56 B 97， 26， 34， 75， 19， 56C19，56，26，97，34，75 D 19， 34， 26， 97， 56， 75(分数： 2.00 )A.B.C.D. V解析：完全二叉树中所有非终端结点的值均不大于(或不小于 ) 其左、右孩子结点的值， 则此序列可称为堆据此，可画出二叉树来判断答案为D。10. 以下有关二叉树的描述中正确的是 ( ) 。(1) 二叉树按某种右岸序线索化后，任一结点均有指向其前驱和后继的线索(2) 二叉树的前

7、序遍历序列中，任意一个结点均处在其子女结点的前面A. 只有(1) B 只有(2)C(1) 和(2) D 以上全不对(分数： 2.00 )A.B. VC.D.解析：11. 某定点机字长n位，其中包含一位符号位。若采用补码一位乘(Booth算法)实现乘法运算，则最多需要做( ) 次移位运算。A. n-1 B . nC. n+1 D. n+2(分数： 2.00 )A. VB.C.D.解析：12. 若某浮点机基数为 4，尾数采用补码表示，则该浮点机的规格化尾数形式为 ( ) 。A. 最高两位数值位与符号位相反B. 最高两位数值位与符号位相同C. 最高两位数值位至少有一位与符号位相反D. 最高两位数值位

8、至少有一位与符号位相同（分数： 2.00 ）A.B.C. VD.解析：13. 用74181和74182芯片构成小组内并行进位， 小组间并行进位，大组间串行进位的 32位ALU需要74182 芯片的片数为 （ ） 。A. 0 B. 1 C. 2 D. 3（分数： 2.00 ）A.B.C. VD.解析：74181是内部并行进位的4位ALU芯片，74182是4位先行进位芯片，故 4片74181和1片74182可构成小组内并行进位。小组间并行进位的16位ALU;又题目要求构成小组内并行进位，大组内串行进位的32位ALU,故只需将2个前述16位ALU串联即可，共需2片74182芯片，选 G14. 某机字

9、长32位，它的存储容量为 256MB按字节编址，则它的寻址范围大小为（）。A. 256MB B. （256-1）MBC. 64MB D. （64-1）MB（分数： 2.00 ）A. VB.C.D.解析：该机存储容量为 256MB又按字节编址，故其寻址范围为0256 M-1，寻址空间大小为 256MB15. 采用了虚拟存储器的计算机系统中，逻辑地址与物理地址相比 （ ） 。A. 两者位数相等 B .逻辑地址位数多C. 物理地址位数多 D 无法判断（分数： 2.00 ）A.B. VC.D.解析：虚拟存储器主要是为了解决存储系统的容量问题，引入虚拟存储器后，程序员编程可使用的虚拟空 间要远大于物理内

10、存容量，故逻辑地址位数要大于物理地址位数，选B。16. 下列关于RISC的叙述中，错误的是（）。A. RISC普遍采用微程序控制器B. RISC大多数指令在一个时钟周期内完成C. RISC的内部通用寄存器数量相对CISC多（分数： 2.00 ）A. VB.C.D.解析：与CISC相比，RISC的特点是：指令数量和寻址方式少，指令格式简单，大多数指令在一个时钟周 期内完成；CPU内部通用寄存器数量多；控制器多采用硬布线逻辑，且多采用流水线技术，执行速度较快。 故 A 选项错误。17. 下列寻址方式中，执行速度最快的是 （ ） 。A. 立即数寻址 B 直接寻址C.间接寻址D 寄存器间接寻址（分数：

11、 2.00 ）A. VB.C.D.解析：四个选项中，只有立即数寻址不需要访存，故其执行速度最快。18. CPU在响应中断的过程中，保护现场的工作由（）完成。A. 中断隐指令B 中断服务程序C. A或B之一完成D . A和B共同完成（分数： 2.00 ）A.B.C.D. V解析：保护现场包括保护程序断点和保护CPU内部各寄存器内容，其中，保护程序断点的任务由中断隐指令完成；而保护CPU内部其他寄存器的任务由中断服务程序来完成，故D为正确选项。19. CPU的中断周期前可能是（）。A. 取指周期B 间址周期C.执行周期D 以上都有可能（分数： 2.00 ）A.B.C. VD.解析：CPU在一个指令

12、周期结束，即一条指令的执行周期结束后检查是否有中断请求，如果有则进入中断 周期，故中断周期前只可能是执行周期。20. 数据总线、地址总线、控制总线是根据总线 （ ） 来划分的。A. 传送内容的不同 B 所处位置的不同C. 连接部件的不同 D 所使用标准的不同（分数： 2.00 ）A. VB.C.D.解析：根据总线上传输内容的不同，可将总线分为数据总线、地址总线和控制总线21. 采用DMA方式传送数据时，每传送一个数据要占用（）。A. 个指令周期B 一个机器周期C. 一个存取周期 D 一个时钟周期（分数： 2.00 ）A.B.C. VD.CPU解析：采用DMA方式传送数据时，每传送一个数据需要占

13、用CPU一个存取周期，即在该存取周期内,不能访存。22. 中断系统中，中断屏蔽字的作用是 （ ） 。A. 暂停对所有中断源的响应B 暂停对所有可屏蔽中断源的响应C. 暂停对某些可屏蔽中断源的响应D 暂停对主存的访问（分数： 2.00 ）A.B.C. VD.解析：CPU通过设置中断屏蔽字来中断对某些可屏蔽中断源的响应。23. 分页式虚拟存储管理系统中，一般来说页面的大小与可能产生缺页中断的次数（ ） 。A. 成正比B .成反比C. 无关D.成固定比值（分数： 2.00 ）A.B. VC.D.解析：页面越小发生缺页中断次数的可能性越大。24. 请求分页存储管理方案中，如果所需的页面不在内存中，则产

14、生缺页中断，它属于（ ） 中断。A. 硬件故障B . I/O C .外D .程序中断分数： 2.00 ）A.B.C.D. V解析：本题考查中断的概念。25. 页式虚拟存储管理的主要特点是 （ ） 。A. 不要求将作业装入到主存的连续区域B. 不要求将作业同时全部装入到主存的连续区域C. 不要求进行缺页中断处理D. 不要求进行页面置换（分数： 2.00 ）A.B. VC.D.解析：本题考查页式存储的概念。26. 分区分配内存管理方式的主要保护措施是 （ ） 。A.界地址保护B 程序代码保护C 数据保护D 栈保护（分数： 2.00 ）A. VB.C.D.解析：界地址寄存器来保护内存管理方式的主要措

15、施。27. 在存储系统管理中，采用覆盖与交换技术的目的是 （ ）A.节省主存空间B .物理上扩充主存容量C.提高CPU效率D 实现主存共存（分数： 2.00 ）A. VB.C.D.解析：覆盖和交换是虚拟上扩充内存的技术。28. 既考虑作业等待时间又考虑作业执行时间的调度算法是 （ ）A.响应比高者优先B .短作业优先C.优先级调度D .先来先服务（分数： 2.00 ）A. VB.C.D.解析：响应比 =（ 等待时间 +执行时间 ）/ 执行时间29. 下列死锁的论述中，正确的论述是 （ ） 。A. 由于产生死锁的基本原因是系统资源不足，因而预防死锁最常用方法，是根据系统规模，配置足够的系统资源B

16、. 由于产生死锁的另一个基本原因是进程推进顺序不当，因而预防死锁的常用方法，是使进程的推进顺序 合法C. 因为只要系统不进入不安全状态，便不会产生死锁，故预防死锁的常用方法，是防止系统进入不安全状态D. 可以通过破坏产生死锁的四个必要条件之一或其中几个方法，来预防发生死锁（分数： 2.00 ）A.B.C.D. V解析：A:不可能根据系统的规模，配置足够的系统资源，因为系统的资源是有限的。B:这种方法不能保证死锁不发生，而且进程推进过程很复杂，实现合理的顺序不太可能。C:系统进入不安全状态不一定会产生死锁，防止系统进入不安全状态不太可能，故不是常用的方法。30. 设m为同类资源数，n为系统中并发

17、进程数。当 n个进程共享m个互斥资源时，每个进程的最大需求是w,则下列情况会出现系统死锁的是（）。A. m=2， n=1， w=2 B. m=2， n=2， w=1C. m=4， n=3， w=2 D. m=4， n=2， w=3（分数: 2.00 ）A.B.C.D. V解析:当 2个进程已经拥有 2个资源，都申请第 3 个资源时，导致死锁。31. MS-DOS中的文件物理结构采用（）。A.连续结构B 链接结构C 索引结构D 哈希表（分数: 2.00 ）A.B. VC.D.解析:本题考查文件物理结构的知识。32. 通过硬件和软件的功能扩充，把原来独占的设备改造成若干用户共享的设备，这种设备称为

18、（ ） 。A.系统设备B .存储设备C .用户设备D .虚拟设备（分数: 2.00 ）A.B.C.D. V 解析：本题考查虚拟设备的概念。33.ICMP在TCP/IP协议集中属于（）。A.数据链路层B 传输层C 网络层D 应用层（分数： 2.00 ）A.B.C. VD.解析：ICMP在TCP/IP协议集中是属于IP层的，即属于网络层。34. 采用8种相位，每种相位各有两种幅度的QAM调制方法，在4800波特率的信号传输速率下能达到的数据传输速率为 （ ） 。A. 4800bps B . 9600bps C19200bps D38400bps（分数： 2.00 ）A.B.C. VD.QAM解析：

19、QAM调制是一种多元制的振幅相位混合调制方法。题目中有8种相位，每种相位各有两种幅度的调制方法，共有16种状态，所以每个Baud为4位。由于是4800波特率的信号传输速率，因此数据传输速 率是 19200bps。35. 两个网段在物理层进行互联时要求 （ ） 。A. 数据传输率和数据链路层协议都不相同B. 数据传输率和数据链路层协议都相同C. 数据传输率相同，数据链路层协议可不同D. 数据传输率可不同，数据链路层协议相同（分数： 2.00 ）A.B.C. VD.解析：数据传输率是物理层的重要参数，两个网段在物理层进行互联，数据传输率必须相同。如果在数据 链路层互联，则要求数据链路层协议也相同。

20、36. 一条线路带宽为1Mbps,往返时延为45ms假设数据帧的大小为1000字节。若采用停一等协议,的数据率是 （ ） 。A. 15Kbps B. 1.5KbpsC. 151Kbps D. 1510Kbps（分数： 2.00 ）A.B.C. VD.解析：往返时延为 45ms,发送一帧的时间是 8X1000*1000000实际的数据率是8X 1000*（8 X 1000* 1000000+45X0.003）=150943（bps）151（Kbps）。37. 若数据链路层采用回退N滑动窗口字而已，发送帧的序列号用7bit表示，发送窗口的最大值为（）。A7 B64 C127 D128（分数： 2.

21、00 ）A.B.B. VD.解析：7位的发送序列号，最大可以有128个序列，采用回退 N帧的协议，发送窗口的最大值应该是最大序列号减 1，即 127。38. 以下地址中的 （ ） 和 匹配。AC（分数： 2.00 ）A. VB.C.D.解析：观察地址的第二个字节0X32=00100000前缀12位，说明第二个字节的前 4位在前缀中。给出的 4个地址的第二字节的前 4位分别是：0010，0100，0011和010。，故只有A是匹配的。39. 在TCP连接中，如果已经接收了1000字节的数据，那么在发送回的数据包头中，确认号为（）。A1000 B1001 C999 D998（分数： 2.00 ）A

22、.B. VC.D.解析：确认号表示接下来希望接收数据的序列号，成功接收1000字节之后，TCP连接希望接收1001号字节，所以答案是 1001。40. FTP客户和服务器间传递 FTP命令时，使用的连接是（）。A.建立在TCP之上的控制连接 B .建立在TCP之上的数据连接C. 建立在UDP之上的控制连接 D .建立在UDP之上的数据连接（分数： 2.00 ）A. VB.C.D.解析：TCP的控制连接用来传输控制命令，数据连接用来传输文件。二、 综合应用题 （ 总题数： 7，分数： 70.00）41. 没有 m 个连续单元供一个栈与队列使用， 且栈与队列的实际占用单元数事先不知道， 但是要求在

23、任何时 刻它们占用的单元数量不超过 m,试写出上述栈与队列的插入算法。分数： 10.00 ) 正确答案： ( 算法如下：/ 定义结点的结构为struct Node ElemType data;struct Node* next;/ 定义栈的结构struct Stack Node* base;Node* top ；/ 定义队列的结构 struct Queue Node* front ；Node* tail;/设m个连续单元的数组为 bm，定义全局数组static int am 用以标识m个单元中各个单元是否被占 用表示未被占用 S,ElemType elem)/ai=1 表示已占用, ai=0

24、void InsertStack(struct stackfor(int i=0;i data=elem:P- next=NULL: if(S.base=NULL)S.base=P;S.top=P:elsep- next=P;S.top=P:for(int i=0； i data=elem;P- next=NULL:if(Q.front=NULL)Q.front=p;Q.tail=p;elseQ.tail- next=P;Q.tail=p;)解析：42. 序列的“中值记录”指的是： 如果将此序列排序后， 它是第 n/2 个记录。试写出一个求中值记录的算法。(分数： 15.00 ) 正确答案：

25、( 解析 算法如下：typedef structint gt ； / 大于该记录的个数int lt;/ 小于该记录的个数place;int Get_Mid(int a，int n)place bMAXSIZE;/* 对第 i 个元素统计比它大和比它小的元数的个数，分别为 gt 和 It*/for(int i=0;i n;i+)for(int j=0;j aEi)bi.gt+;if(aj ai)bi.It+;int mid=0;/* 找出 gt 值与 It 值最接近的元素，即为中值记录 */int min_dif=abs(b0.gt-b0.It);for(int i=0;in;i+) min _

26、dif;if（abs（bi.gt_bi.lt）mid=i:return mid;）解析：43. 某浮点机字长16位，其浮点数格式为：阶码 5位（含1位阶符），采用补码表示，尾数 11位（含1位数 符），采用补码表示，且尾数为规格化形式。已知 X=0.1011000011X2 0,0101 , Y=0.0001100000X2 0,1000，试求 X+Y,要求写出详细的计算过程。假设浮点加减过程中阶码和尾数采用双符号位，并使用“0舍1入法”进行舍入。（分数：13.00 ） 正确答案：（写岀X、Y的机器数形式，根据题意，尾数为规格化形式，故Y=0.0001100000X2 0,1000 =0.11

27、00000000X2 0,0101。运算过程中阶码、尾数采用双符号位，X、Y的机器数形式为X=00,0101 ; 00.1011000011，Y=00,0101 ； 00.1100000000，X+Y的计算过程如下： 对阶，X、Y阶码相同，阶差为0，故不需对阶。 尾数求和，即得 X+Y=00,0101; 01.0111000011 o 规格化，尾数双符号位为01,说明尾数溢出，需要右规，尾数右移1位，阶码加1，得X+Y=00,0110; 00.1011100001尾数为规格化数，规格化结束。 舍入，采用“0舍1入法”进行舍入，由于中规格化时丢掉的数位中最高位为1，故需将结果的最低数值位加1，得

28、X+Y=00,0110; 00.1011100010 溢出判断，X+Y阶码双符号位为00,说明未发生溢出。综上，X+Y=0,0110; 0.1011100010，即 X+Y=0.1011100010X2 0,0110。注答案中机器数形式中的逗号、分号只是为了方便区分符号位和数值位、阶码和尾数，并非机器数中实际存在。）解析：某计算机的CPU主频为500MHz CPI为5（即执行每条指令平均需 5个时钟周期）。假定某外设的数据传输率为0.5MB/S，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求

29、给岀计算过程。（分数：8.00 ）（1）.在中断方式下，CPU用于该外设I/O的时间占整个CPU时间的百分比是多少？（分数：4.00 ） 正确答案：（该外设数据传输率为 0.5MB/S，以32位为传输单位，故1s内因外设传输数据而引起的中断次 数为0.5MB/4B=1.25X10 5（次）对应的中断服务程序及其他开销共需18+2=20条指令，CPI为5,故1s内用于该外没I/O的时钟周期数为1.25 X105X20X5=1.25X10 7（个）CPU主频为500MHz即1s内共有500M个时钟周期，故用于该外设I/O的时间占整个 CPU时间的百分比是（1.25 X107）/（500 X106）

30、 X100%=2.5%）解析：(2) .当该外设的数据传输率达到 5MB/S时，改用DMA方式传送数据。假设每次 DMA专送大小为5000B,且 DMA预处理和后处理的总开销为 500个时钟周期，则CPU用于该外设I/O的时间占整个CPU时间的百分比 是多少?(假设DMA与 CPU之间没有访存冲突)(分数：4.00 ) 正确答案：(该外设的数据传输率为 5MB/S，每次DMA专送大小为5000B,故1s内的DMA专输次数为5MB/5000B=(5X10 6B)/(5 X 10 3B)=1000(次)DMA预处理及后处理的总开销为500个时钟周期，故1s内用于该外设传输数据的时钟周期数为1000

31、X 500=5X 10 5( 个)CPU主频为500MHz故用于该外设I/O的时间占整个CPU时间的百分比是(5X105)/(500 X106)X100%=0.1%)解析：44. 分时系统里，在条件相同的情况下，通常KLT(内核级线程)比ULT(用户级线程)得到更多的CPU时间,请简要解释之。分数： 7.00 )正确答案：(KLT(内核级线程)直接参与CPU的调度，得到CPU的时间和进程相当，ULT(用户级线程)由运行 thread Libray的进程控制和管理，是该进程得到的CPU时间总数里再次分配，往往比参加内核调度的其他进程少。 )解析：45. 举例说明P、V操作为什么要求设计成原语 (

32、即对同一信号量上的操作必须互斥)o P(S)操作：S.value-:lf(S.value 0)Add this process to S.L;Block( ):V(S) 操作S.value+;If(S.value =0)Remove a process P from S.L;Wakeup(P):分数： 8.00 )正确答案：(例如，用P, V操作来实现进程对临界资源互斥使用。此时，只需定义一个信号量s,其初值1 , NULL,并在临界区前执行 P(S)操作，而在临界区后执行V(S)操作。此时P, V操作不设计成原语，那么在执行P, V操作时进程可以被中断。由于在初始状态下，临界资源空闲，故应允

33、许第一个申请临界资源 的进程进入临界区使用临界资源，但如果该进程在执行到P操作的语句S.value-后(此时S.value的值为0)便被另一个进程中断，而那个进程也企图通过执行P(S)操作进入临界区，则第二个进程也必须执行语句S.value-，从而将S.value的值为-1，并由于S.value 0而被阻塞，而第一个进程再次获得CPU后，也同样由于 S.value 0而被阻塞， 这就造成了临界资源虽然空闲但进程却申请不到临时资源的情况，也就是说，此时的P, V操作已无法满足同步机制的要求。同样，一个执行P(S)操作的进程被中断后，另一进程去执行V（S）操作，一个执行 V（S）操作的进程被中断后

34、，而另一个进程去执行P（S）或V（S）操作，都将发生混乱，而难以实现进程同步。因此，P, V操作必须设计成原语的方式。）解析：如下图所示为一个TCP主机中的拥塞窗口的变化过程，这里最大数据段长度为1024字节，请回答如下问题：（分数：9.00）（1）.该TCP协议的初始阀值是多少？为什么？（分数：2.25）正确答案：（该TCP协议的初始阀值为16KB最大数据段长度为1KB可以看出来在拥塞窗口到达16KB之后就呈线性增长了，说明初始阀值是16KB ）解析：（2）.本次传输是否有发生超时？如果有是在哪一次传输超时 ？（分数：2.25）正确答案：（该TCP传输在第13次传输时发生了超时，可以看到拥塞窗口在13次传输后变为1KB ）解析：（3）.在14次传输的时候阀值为多少？（分数：2.25）正确答案：（在14次传输的时候拥塞窗口变为了12KB,可以看到在之后的传输中，拥塞窗口到达12KB之后呈线性增长。）解析：（4）.在本例中，采用了什么拥塞控制算法？2.25)正确答案：（采用了慢启动的算法，因为可以看到在发送失败后拥塞窗口马上变为了 了之前的一半。）解析：