考研计算机学科专业基础综合-25
(总分80,考试时间90分钟)
一、单项选择题
在每小题给出的四个选项中，请选出一项最符合题目要求的。
1. 设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。
A．O(n2log2n) B．O(nlog5n) C．O(n2log5n) D．O(n3)
2. 利用栈求表达式的值时，设立运算数栈OPND。假设OPND只有两个存储单元，在下列表达式中，不发生溢出的是( )。
A．A—B*(C—D) B．(A—B)*C—D C．(A—B*C)—D D．(A—B)*(C—D)
3. 已知输入序列为abcd，经过输出受限的双端队列后，能得到的输出序列是( )。 A．dacb B．cadb
C．dbca D．以上答案都不对
4. 一个具有1025个结点的二叉树的高度为( )。 A．11 B．10
C．11至1025之间 D．10至1024之间
5. 以下关于二叉排序树的说法正确的是( )。
Ⅰ在二叉排序树中，每个结点的关键字都比左孩子关键字大，比右孩子关键字小
Ⅱ每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树都是二又排序树
Ⅲ在二叉排序树中，新插入的关键字总是处于最底层 Ⅳ在二叉排序树中，新结点总是作为叶子结点来插入的 Ⅴ二叉排序树的查找效率和二叉排序树的高度有关
A．Ⅰ、Ⅱ、Ⅳ、Ⅴ B．Ⅱ、Ⅲ、Ⅳ C．Ⅰ、Ⅲ、Ⅴ D．Ⅰ、Ⅳ、Ⅴ
6. 简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻接矩阵为A[1..n，1..n]，且压缩存储在B[1..k]，则k的值至少为( )。 A．n(n+1)/2 B．n2/2
C．(n-1)(n+1)/2 D．n(n-1)/2
7. 若无向图G=(V，E)中含8个顶点，为保证图G在任何情况下都是连通的，则需要的边数最少是( )。
A．7 B．21 C．22 D．28
8. 用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。
9. 在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值( )。 A．一定都是同义词 B．一定都不是同义词 C．不一定都是同义词 D．都相同
10. 如果将中国人按照生日(不考虑年份，只考虑月、日)来排序，那么使用下列排序算法中最快的是( )。
A．归并排序 B．希尔排序 C．快速排序 D．基数排序
11. 用某种排序方法对线性表(25，84，21，47，15，27，68，35，20)进行排序时，元素序列的变化情况如下：
(1)25，84，21，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．快速排序
12. 下图中计算机硬件系统基本组成部件①、②、③、④和⑤的名称是( )。
A．①控制器、②运算器、③存储器、④输入设备、⑤输出设备 B．①运算器、②控制器、③存储器、④输入设备、⑤输出设备 C．①运算器、②存储器、③控制器、④输入设备、⑤输出设备 D．①运算器、②控制器、③存储器、④输出设备、⑤输入设备
13. —15的八位二进制反码表示为( )。
A．00001111 B．10001111 C．11110000 D．11110001
14. 设数据码字为10010011，采用海明码进行校验，若仅考虑纠正一位错，则必须加入的(冗余)位数是( )。
A．2 B．3 C．4 D．5
15. 如果X为负数，则已知[X]补求[-X]补的方法是( )。 A．[X]补各值保持不变
B．[X]补符号位变反，其他各位不变
C．[X]补除符号位外，各位变反，末位加1
D．[X]补连同符号位一起，各位变反，末位加1
16. 下面是有关DRAM和SRAM存储器芯片的叙述： ⅠDRAM芯片的集成度比SRAM高 ⅡDRAM芯片的成本比SRAM高 ⅢDRAM芯片的速度比SRAM快
ⅣDRAM芯片工作时需要刷新，SRAM芯片工作时不需要刷新 通常情况下，错误的是( )。
A．Ⅰ和Ⅱ B．Ⅱ和Ⅲ C．Ⅲ和Ⅳ D．Ⅰ和Ⅳ
17. 若想对某个寄存器中的某几位清零，可以使用的一条指令是( )。 A．AND B．OR C．NOT D．XOR
18. 设指令由取指、分析、执行3个子部件完成，每个子部件的工作周期均为△t，采用常规标量流水线处理机。若连续执行10条指令，则共需时间是( )。 A．8△t B．10 △t C．12△t D．14△t
19. 某计算机的指令系统中共有101条不同的指令，采用微程序控制方式时，控制存储器中具有的微程序数目至少是( )。
A．101 B．102 C．103 D．104
20. 某总线有104根信号线，其中数据总线(DB)32根，若总线工作频率为33MHz，则其理论最大传输率是( )。
A．33 MB/s B．64MB/s C．132 MB/s D．164 MB/s
21. RGB8:8:8表示一帧彩色图像的颜色数是( )。 A．23 B．28 C．224 D．2512
22. 关于程序中断方式和DMA方式的叙述中错误的是( )。
Ⅰ若同时接到DMA请求和中断请求，CPU优先响应DMA请求 Ⅱ程序中断需要保护现场，DMA方式不需要保护现场
Ⅲ程序中断方式的中断请求是为了报告CPU数据的传输结束，而DMA方式的中断请求完全是为了传送数据
Ⅳ中断方式和DMA方式中，快速I/O设备更适合采用中断方式传递数据 A．Ⅱ、Ⅳ B．Ⅱ、Ⅲ、Ⅳ C．Ⅲ、Ⅳ D．Ⅰ、Ⅲ、Ⅳ
23. 构造操作系统的主要结构模式是( )。
Ⅰ整体式结构 Ⅱ层次式结构 Ⅲ微内核结构(客户/服务器) Ⅳ对称式结构 A．Ⅰ和Ⅲ B．Ⅱ和Ⅳ C．Ⅰ、Ⅱ和Ⅲ D．Ⅱ、Ⅲ和Ⅳ
24. 有2个优先级相同的并发进程P1和P2，它们的执行过程如下图所示，x、y和z是共享变量。假设，当前信号量s1=0，s2=0，已知z=2，进程运行结束后，则x、y和z的可能值分别是( )。
A．8、7和4 B．5、7和4 C．5、8和9 D．以上都不是
25. 一个支持并发的操作系统在运行过程中，调度模块会不断地选择新进程运行。在非抢先式操作系统中，下面不是引起操作系统重新选择新进程的直接原因是( )。 A．分配的时间片用完 B．运行着的进程要等待某一信号到来 C．正在运行的进程出错 D．有新进程进入就绪队列
26. 一个正在访问临界资源的进程由于申请等待IO操作而被中断时，它是( )。 A．可以允许其它进程进入与该进程相关的临界区 B．不允许其它进程进入任何临界区
C．可以允许其它进程抢占处理机，但不得进入该进程的临界区 D．不允许任何进程抢占处理机
27. 在连续内存分配管理中，分区分配是最简单的实现并发的内存管理方法。对于该方法，进行内存保护的措施是( )。
A．存取控制列表 B．用户权限保护 C．程序状态保护 D．界地址保护
28. 某简单分页式存储管理中，地址空间分页为每页1KB，对应相应的物理块。设主存总容量为256KB，描述主存分配情况的位示图如下所示(0表示未分配，1表示已分配)， 起始页号 位示网
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 16 1 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0 32 1 1 1 1 1 1 1 1 1 1 1 1 1......
此时，操作系统创建了一个新进程，大小为2.5KB，按首先分配低址空间的策略，那么，分配给该进程的页面的页号分别是( )。
A．17、21和22 B．21、22和23 C．23、24和25 D．29、30和31
29. 分页式虚拟存储管理系统中，页面的大小与可能产生的缺页中断次数是( )。 A．成正比 B．成反比 C．无关系 D．固定值
30. 某一个磁盘共有16个盘面，每个盘面上从外到内共有30000个磁道(或称30000个柱面)，每个磁道有250个扇区。假定存储信息时以一个扇区作为一个存储块，盘面号(磁头号)、磁道号和扇区号均从0开始编号，那么，盘块号1002578对应的盘面号、磁道号和扇区号是( )。
A．1，2500，78 B．10，250，78 C．2，250，161 D．0，4010，78
31. 现代操作系统中，文件系统都有效地解决了重名问题，允许不同的文件可以有相同的文件名。那么，实现该功能的主要方法是( )。 A．重名翻译机构 B．建立索引表 C．建立指针 D．建立树形目录结构
32. 设备管理中，能够用空间换取时间的技术是( )。
A．SPOOLing技术 B．虚拟存储技术 C．覆盖与交换技术 D．通道技术
33. 关于OSI参考模型和TCP/IP模型在网络层提供的服务，正确的说法是( )。 A．OSI模型在网络层仅提供面向连接服务 B．TCP/IP模型在网络层提供无连接服务 C．OSI模型在网络层仅提供无连接服务
D．TCP/IP模型在网络层提供无连接和面向连接服务
34. 光纤分为单模光纤和多模光纤，这两种光纤的区别是( )。
A．单模光纤的数据速率比多模光纤低 B．多模光纤比单模光纤传输距离更远 C．单模光纤比多模光纤的价格更便宜 D．多模光纤比单模光纤的纤芯直径粗
35. 使用HDLC时，位串XX1110进行位填充后的位模式是( )。 A．XX1110110 B．XX11110 C．XX11100 D．XX111100
36. 在可靠传输机制中，发送窗口的位置由窗口前沿和后沿的位置共同确定，经过一段时间，发送窗口的后沿的变化情况可能是( )。 Ⅰ原地不动 Ⅱ向前移动 Ⅲ向后移动
A．Ⅰ、Ⅲ B．Ⅰ、Ⅱ C．Ⅱ、Ⅲ D．都有可能
37. CRC校验是目前常用的检错方式。如果采用的多项式为G(X)=x4+x2+x+1，那么对于要传的信息串1010001的CRC校验码是( )。 A．1011 B．1101 C．1110 D．1100
38. 关于因特网中的主机和路由器，以下说法正确的是( )。 Ⅰ主机通常需要实现TCP协议 Ⅱ路由器必须实现TCP协议 Ⅲ主机必须实现IP协议 Ⅳ路由器必须实现IP协议
A．Ⅰ、Ⅱ和Ⅲ B．Ⅰ、Ⅱ和Ⅳ C．Ⅰ、Ⅲ和Ⅳ D．Ⅱ、Ⅲ和Ⅳ
39. 下面包含在TcP头中而不包含在UDP头中的信息是( )。 A．目标端口号 B．序号 C．源端口号 D．校验号
40. DNS服务器在名称解析过程中正确的查询顺序是( )。
A．本地缓存记录→区域记录→转发域名服务器→根域名服务器 B．区域记录→本地缓存记录→转发域名服务器→根域名服务器 C．本地缓存记录→区域记录→根域名服务器→转发域名服务器 D．区域记录→本地缓存记录→根域名服务器→转发域名服务器
二、综合应用题
1. 现有一个解决无向连通图的最小生成树的一种方法如下： 将图中所有边按权重从大到小排序为(e1，e2，…，em)； i=1；
while(所剩边数＞=顶点数) 从图中删去ei；
若图不再连通，则恢复ei；
i=i+1：
请问上述方法能否求得原图的最小生成树?若该方法可行，请证明之；否则请举例说明。
2. 设有带头结点的循环双链表表示的线性表L=(a1，a2，……，an-1，an)。设计在时
间和空间上都尽可能高效的算法，将L改造成L=(a1，a3，……，an,……a4，a2)。要求： (1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。
3. 下图是某存储芯片的引脚图，请回答：
(1)这个存储芯片的类型(是RAM还是ROM)?这个存储芯片的容量? (2)若地址线增加一根，存储芯片的容量将变为多少?
(3)这个芯片是否需要刷新?为什么?刷新和重写有什么区别? (4)如果需要刷新，请指出芯片刷新一遍需要的时间(设存取周期为0.5μs)及你准备选择的刷新方式，需说明理由。
4. 磁盘机由6个盘片组成，其中专设1个盘面为伺服面，其他的盘面作为记录数据的盘面。盘存储区域内直径为6.1cm，外直径为12.9cm，道密度为22TPM，位密度为6000bpm，平均寻道时间为10ms，磁盘转速为7200RPM。假定π=3，试计算： (1)数据盘面数和柱面数。 (2)盘组容量是多少字节?
(3)数据传输率是多少字节/秒?
(4)从任一磁道读取80000个字节数据的平均存取时间是多少?
(5)假定系统配备上述磁盘机15台，每个磁道分为64个扇区，试为该磁盘系统设计一个地址方案。
5. 有n个生产者进程向1个有限的缓冲区不断地发送消息，这些消息通过缓冲区分发到m个消费者，缓冲区的大小只可以存放1条消息。生产者和消费者的工作遵循如下规则： (1)生产者和消费者对缓冲区的访问互斥；
(2)对每1条放入缓冲区的消息，所有消费者都必须接收1次； (3)缓冲区满时，生产者必须阻塞，缓冲区空时，消费者阻塞。
请用信号量和P、V操作组织正确的发送和接收。用类c语言进行描述。
6. 并发使得处理机的利用率得到提高，其主要原因是处理机与IO可以同时为多个进程服务，也即处理机与IO设备真正地并行。但是处理机的利用率提高并不是简单地将二个进程的处理机利用率相加，而是遵循一定的规律。现在有一个计算机系统采用多道程序技术实现了并发，调度算法采用时间片轮转，时间片很小可以不计，忽略系统的开销，请分析以下问
题：
假设每个进程的处理机的利用率为u1=20%。
(1)进程并发时，处理机的利用率与并发进程数的关系是什么? (2)假设某一计算机系统拥有20MB内存，以等额分区的方式实现了多道程序设计并运行，每个分区为4MB，其中操作系统占一个分区，请问此时处理机的利用率最大为多少?
(3)假设为这个系统增加了16MB内存，系统有足够的并发度，此时处理机的利用率最大为多少?系统的吞吐量比(2)增加了多少?
(4)在(3)的基础上继续增加16MB内存，此时处理机的利用率最大为多少?系统的吞吐量比(3)增加了多少?分析此时增加的内存是否合算?说明为什么。
7. 假设路由器R存在两个接口，接口R1连接标准局域网，接口R2连接限制最大传输单元(MTU)的局域网，现在一个IP数据包从接口R1转发到接口R2，从R2链路上截获两个数据包的IP报头，如题47-a表所示，请回答如下问题： 题47-a表
编号 IP分组内容(十六进制)
1 45 00 00 64 00 1e 20 00 ff 01 18 27 c0 a8 01 01 c0 a8 01 02 2 45 00 00 58 00 1e 00 1e ff 01 38 15 c0 a8 01 01 c0 a8 01 02 (1)接口R2的最大传输单元是多少?
(2)所传输的IP数据包的数据大小是多少?分为了几个IP分片?
(3)根据截获的IP报头，请填充没有截获的数据报，注意不包含头部校验和。 注：IP分组头结构分别如题47-b图所示。
因篇幅问题不能全部显示，请点此查看更多更全内容