计算机统考真题解析.doc
- 文档编号:4708416
- 上传时间:2023-05-07
- 格式:DOC
- 页数:14
- 大小:3.01MB
计算机统考真题解析.doc
《计算机统考真题解析.doc》由会员分享,可在线阅读,更多相关《计算机统考真题解析.doc(14页珍藏版)》请在冰点文库上搜索。
予人玫瑰手留余香 王道论坛
王道考研系列
2011年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合
(科目代码:
408)
特别鸣谢:
阿三(casper08,哈工大)王道考研系列辅导书编写团队
予人玫瑰手留余香
予人玫瑰手留余香 王道论坛
一、单项选择题:
1-40小题,每小题2分,共80分,下列每小题给出的四个选项中,只有一
项符合题目要求的。
请在答题卡上将所选项的字母涂黑。
)
1.设n是描述问题规模的非负整数,下面程序片段的时间复杂度是
x=2;
while(x x=2*x; 2 2 A.O(logn) B.O(n) C.O(nlogn) D.O(n2) 解答: A。 程序中,执行频率最高的语句为“x=2*x”。 设该语句执行了t次,则2t+1=n/2, 故t=log2(n/2)-1=log2n-2=O(log2n)。 2.元素a,b,c,d,e依次进入初始为空的栈中,若元素进栈后可停留、可出栈,直到所有元素都出栈,则在所有可能的出栈序列中,以元素d开头的序列个数是 A.3 B.4 C.5 D.6 解答: B。 出栈顺序必为d_c_b_a_,e的顺序不定,在任意一个“_”上都有可能。 3.已知循环队列存储在一维数组A[0...n-1]中,且队列非空时front和rear分别指向队头元素和队尾元素。 若初始时队列为空,且要求第1个进入队列的元素存储在A[0]处,则初始时front和rear的值分别是 A.0,0 B.0,n-1 C.n-1,0 D.n-1,n-1 解答: B。 插入元素时,front不变,rear+1.而插入第一个元素之后,队尾要指向尾元素,显然,rear初始应该为n-1,front为0。 4.若一棵完全二叉树有768个结点,则该二叉树中叶结点的个数是A.257 B.258 C.384 D.385解答: C。 叶结点数为n,则度为2的结点数为n-1,度为1的结点数为0或1,本题中为1(总 结点数为偶数),故而即2n=768。 5.若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1,则该二叉树的中序遍历序列不会是 A.1,2,3,4 B.2,3,4,1 C.3,2,4,1 D.4,3,2,1 解答: C。 由前序和后序遍历序列可知3为根结点,故(1,2)为左子树,(4)为右子树, C不可能。 或画图即可得出结果。 6.已知一棵有2011个结点的树,其叶结点个数为116,该树对应的二叉树中无右孩子的结点个数是 A.115 B.116 C.1895 D.1896 共1895个中间结点 解答: D。 本题可采用特殊情况法解。 设题意中的树是如下图所示的结构,则对应的二叉树中仅有前115个叶结点有右孩子。 „„ 共116个叶结点 7.对于下列关键字序列,不可能构成某二叉排序树中一条查找路径的序列是 A.95,22,91,24,94,71 B.92,20,91,34,88,35 C.21,89,77,29,36,38 D.12,25,71,68,33,34 予人玫瑰手留余香 王道论坛 解答: A。 选项A中,当查到91后再向24查找,说明这一条路径之后查找的数都要比91小,后面的94就错了。 8.下列关于图的叙述中,正确的是Ⅰ.回路是简单路径Ⅱ.存储稀疏图,用邻接矩阵比邻接表更省空间 Ⅲ.若有向图中存在拓扑序列,则该图不存在回路 A.仅Ⅱ B.仅Ⅰ、Ⅱ C.仅Ⅲ D.仅Ⅰ、Ⅲ解答: C。 Ⅰ.回路对应于路径,简单回路对应于简单路径;Ⅱ.刚好相反;Ⅲ.拓扑有 序的必要条件。 故选C。 9.为提高散列(Hash)表的查找效率,可以采取的正确措施是Ⅰ.增大装填(载)因子Ⅱ.设计冲突(碰撞)少的散列函数Ⅲ.处理冲突(碰撞)时避免产生聚集(堆积)现象 A.仅Ⅰ B.仅Ⅱ C.仅Ⅰ、Ⅱ D.仅Ⅱ、Ⅲ解答: B。 III错在“避免”二字。 10.为实现快速排序算法,待排序序列宜采用的存储方式是 A.顺序存储 B.散列存储 C.链式存储 D.索引存储解答: A。 内部排序采用顺序存储结构。 11.已知序列25,13,10,12,9是大根堆,在序列尾部插入新元素18,将其再调整为大根堆,调整过程中元素之间进行的比较次数是 A.1 B.2 C.4 D.5 解答: B。 首先与10比较,交换位置,再与25比较,不交换位置。 比较了二次。 12.下列选项中,描述浮点数操作速度指标的是 A.MIPS B.CPI C.IPC D.MFLOPS 解答: D。 送分题。 13.float型数据通常用IEEE754单精度浮点数格式表示。 若编译器将float型变量x分配在一个32位浮点寄存器FR1中,且x=-8.25,则FR1的内容是 A.C1040000H B.C2420000H C.C1840000H D.C1C20000H 解答: A。 x的二进制表示为-1000.01﹦-1.00001×211根据IEEE754标准隐藏最高位的 “1”,又E-127=3,所以E=130=10000010 (2)数据存储为1位数符+8位阶码(含阶符)+23位尾数。 故FR1内容为1100000010000010000000000000000000 即11000001000001000000000000000000,即C104000H 14.下列各类存储器中,不采用随机存取方式的是 A.EPROM B.CDROM C.DRAM D.SRAM 解答: B。 光盘采用顺序存取方式。 15.某计算机存储器按字节编址,主存地址空间大小为64MB,现用4M×8位的RAM芯片组成32MB 的主存储器,则存储器地址寄存器MAR的位数至少是 A.22位 B.23位 C.25位 D.26位解答: D。 64MB的主存地址空间,故而MAR的寻址范围是64M,故而是26位。 而实际的主存 的空间不能代表MAR的位数。 16.偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。 下列寻址方式中, 不.属于偏移寻址方式的是 A.间接寻址 B.基址寻址 C.相对寻址 D.变址寻址 解答: A。 间接寻址不需要寄存器,EA=(A)。 基址寻址: EA=A+基址寄存器内同;相对寻址: EA﹦A+PC内容;变址寻址: EA﹦A+变址寄存器内容。 予人玫瑰手留余香 王道论坛 17.某机器有一个标志寄存器,其中有进位/借位标志CF、零标志ZF、符号标志SF和溢出标志OF,条件转移指令bgt(无符号整数比较大于时转移)的转移条件是 A.CF+OF=1 B.SF+ZF=1 C.CF+ZF=1 D.CF+SF=1 解答: C。 无符号整数比较,如A>B,则A-B无进位/借位,也不为0。 故而CF和ZF均为0。 18.下列给出的指令系统特点中,有利于实现指令流水线的是 Ⅰ.指令格式规整且长度一致 Ⅱ.指令和数据按边界对齐存放Ⅲ.只有Load/Store指令才能对操作数进行存储访问 A.仅Ⅰ、Ⅱ B.仅Ⅱ、Ⅲ C.仅Ⅰ、Ⅲ D.Ⅰ、Ⅱ、Ⅲ解答: D。 指令定长、对齐、仅Load/Store指令访存,以上三个都是RISC的特征。 均能 够有效的简化流水线的复杂度。 19.假定不采用Cache和指令预取技术,且机器处于“开中断”状态,则在下列有关指令执 行的叙述中,错.误.的是 A.每个指令周期中CPU都至少访问内存一次 B.每个指令周期一定大于或等于一个CPU时钟周期C.空操作指令的指令周期中任何寄存器的内容都不会被改变D.当前程序在每条指令执行结束时都可能被外部中断打断解答: C。 会自动加1,A取指令要访存、B时钟周期对指令不可分割。 20.在系统总线的数据线上,不.可能传输的是 A.指令 B.操作数 C.握手(应答)信号 D.中断类型号解答: C。 握手(应答)信号在通信总线上传输。 21.某计算机有五级中断L4~L0,中断屏蔽字为M4M3M2M1M0,Mi=1(0≤i≤4)表示对Li级中断进行屏蔽。 若中断响应优先级从高到低的顺序是L4→L0→L2→L1→L3,则L1的中断处理程 序中设置的中断屏蔽字是 A.11110 B.01101 C.00011 D.01010 解答: D。 高等级置0表示可被中断,比该等级低的置1表示不可被中断。 22.某计算机处理器主频为50MHz,采用定时查询方式控制设备A的I/O,查询程序运行一次所用的时钟周期数至少为500。 在设备A工作期间,为保证数据不丢失,每秒需对其查询至少200次,则CPU用于设备A的I/O的时间占整个CPU时间的百分比至少是 A.0.02% B.0.05% C.0.20% D.0.50% 解答: C。 每秒200次查询,每次500个周期,则每秒最少200×500﹦100000个周期,10 0000÷50M=0.20%。 23.下列选项中,满足短任务优先且不会发生饥饿现象的调度算法是A.先来先服务 B.高响应比优先C.时间片轮转 D.非抢占式短任务优先 解答: B。 响应比=作业响应时间/作业执行时间=(作业执行时间+作业等待时间)/作业执行时间。 高响应比算法,在等待时间相同情况下,作业执行时间越少,响应比越高,优先执行,满足短任务优先。 随着等待时间增加,响应比也会变大,执行机会就增大,所以不会产生饥饿现象。 先来先服务和时间片轮转不符合短任务优先,非抢占式短任务优先会产生饥饿现象。 24.下列选项中,在用户态执行的是 A.命令解释程序 B.缺页处理程序C.进程调度程序 D.时钟中断处理程序解答: A。 缺页处理程序和时钟中断都属于中断,在核心态执行。 进程调度属于系统调 用在核心态执行,命令解释程序属于命令接口,它在用户态执行。 予人玫瑰手留余香 王道论坛 25.在支持多线程的系统中,进程P创建的若干个线程不能共享的是A.进程P的代码段 B.进程P中打开的文件C.进程P的全局变量 D.进程P中某线程的栈指针解答: D。 进程中某线程的栈指针,对其它线程透明,不能与其它线程共享。 26.用户程序发出磁盘I/O请求后,系统的正确处理流程是 A.用户程序→系统调用处理程序→中断处理程序→设备驱动程序B.用户程序→系统调用处理程序→设备驱动程序→中断处理程序C.用户程序→设备驱动程序→系统调用处理程序→中断处理程序D.用户程序→设备驱动程序→中断处理程序→系统调用处理程序解答: B。 输入/输出软件一般从上到下分为四个层次: 用户层、与设备无关软件层、 设备驱动程序以及中断处理程序。 与设备无关软件层也就是系统调用的处理程序。 所以争取处理流程为B选项。 27.某时刻进程的资源使用情况如下表所示。 进 程 已分配资源 尚需分配 可用资源 R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 2 0 0 0 0 1 0 2 1 P2 1 2 0 1 3 2 P3 0 1 1 1 3 1 P4 0 0 1 2 0 0 此时的安全序列是 A.P1,P2,P3,P4 B.P1,P3,P2,P4 C.P1,P4,P3,P2 D.不存在解答: D。 使用银行家算法得,不存在安全序列。 28.在缺页处理过程中,操作系统执行的操作可能是Ⅰ.修改页表 Ⅱ.磁盘I/O Ⅲ.分配页框 A.仅Ⅰ、Ⅱ B.仅Ⅱ C.仅Ⅲ D.Ⅰ、Ⅱ和Ⅲ解答: D。 缺页中断调入新页面,肯定要修改页表项和分配页框,所以I、III可能发 生,同时内存没有页面,需要从外存读入,会发生磁盘I/O。 29.当系统发生抖动(thrashing)时,可用采取的有效措施是Ⅰ.撤销部分进程 Ⅱ.增加磁盘交换区的容量Ⅲ.提高用户进程的优先级 A.仅Ⅰ B.仅Ⅱ C.仅Ⅲ D.仅Ⅰ、Ⅱ解答: A。 在具有对换功能的操作系统中,通常把外存分为文件区和对换区。 前者用于 存放文件,后者用于存放从内存换出的进程。 抖动现象是指刚刚被换出的页很快又要被访问为此,又要换出其他页,而该页又快被访问,如此频繁的置换页面,以致大部分时间都花在页面置换上。 撤销部分进程可以减少所要用到的页面数,防止抖动。 对换区大小和进程优先级都与抖动无关。 30.在虚拟内存管理中,地址变换机构将逻辑地址变换为物理地址,形成该逻辑地址的阶段是 A.编辑 B.编译 C.链接 D.装载解答: B。 编译过程指编译程序将用户源代码编译成目标模块。 源地址编译成目标程序 时,会形成逻辑地址。 31.某文件占10个磁盘块,现要把该文件磁盘块逐个读入主存缓冲区,并送用户区进行分析,假设一个缓冲区与一个磁盘块大小相同,把一个磁盘块读入缓冲区的时间为100us, 予人玫瑰手留余香 王道论坛将缓冲区的数据传送到用户区的时间是50us,CPU对一块数据进行分析的时间为50us。 在单缓冲区和双缓冲区结构下,读入并分析完该文件的时间分别是 A.1500us、1000us B.1550us、1100usC.1550us、1550us D.2000us、2000us解答: B。 单缓冲区下当上一个磁盘块从缓冲区读入用户区完成时下一磁盘块才能开始 读入,也就是当最后一块磁盘块读入用户区完毕时所用时间为150×10=1500。 加上处理最后一个磁盘块的时间50为1550。 双缓冲区下,不存在等待磁盘块从缓冲区读入用户区的问题,也就是100×10+100=1100。 32.有两个并发执行的进程P1和P2,共享初值为1的变量x。 P1对x加1,P2对x减1。 加1和减1 操作的指令序列分别如下所示。 //加1操作 //减1操作load R1,x //取x到寄存器R1中 load R2,xinc R1 dec R2 store x,R1 //将R1的内容存入x store x,R2 两个操作完成后,x的值 A.可能为-1或3 B.只能为1 C.可能为0、1或2 D.可能为-1、0、1或2 解答: C。 将P1中3条语句变为1,2,3,P2中3条语句编为4,5,6。 则依次执行1,2,3,4,5得结果1,依次执行1,2,4,5,6,3得结果2,执行4,5,1,2,3,6得结果0。 结果-1不可能得出,选C。 33.TCP/IP参考模型的网络层提供的是 A.无连接不可靠的数据报服务 B.无连接可靠的数据报服务C.有连接不可靠的虚电路服务 D.有连接可靠的虚电路服务解答: A。 TCP/IP的网络层向上只提供简单灵活的、无连接的、尽最大努力交付的数据 报服务。 此外考察IP首部,如果是面向连接的,则应有用于建立连接的字段,但是没有;如果提供可靠的服务,则至少应有序号和校验和两个字段,但是IP分组头中也没有(IP首部中只是首部校验和)。 因此网络层提供的无连接不可靠的数据服务。 有连接可靠的服务由传输层的TCP提供。 34.若某通信链路的数据传输速率为2400bps,采用4相位调制,则该链路的波特率是 A.600波特 B.1200波特 C.4800波特 D.9600波特 解答: B。 有4种相位,则一个码元需要由log24=2个bit表示,则波特率=比特率/2=1200 波特。 35.数据链路层采用选择重传协议(SR)传输数据,发送方已发送了0~3号数据帧,现已收到1号帧的确认,而0、2号帧依次超时,则此时需要重传的帧数是 A.1 B.2 C.3 D.4 解答: B。 选择重传协议中,接收方逐个地确认正确接收的分组,不管接收到的分组是否有序,只要正确接收就发送选择ACK分组进行确认。 因此选择重传协议中的ACK分组不再具有累积确认的作用。 这点要特别注意与GBN协议的区别。 此题中只收到1号帧的确认,0、2号帧超时,由于对于1号帧的确认不具累积确认的作用,因此发送方认为接收方没有收到0、 2号帧,于是重传这两帧。 36.下列选项中,对正确接收到的数据帧进行确认的MAC协议是 A.CSMA B.CDMA C.CSMA/CD D.CSMA/CA 解答: D。 可以用排除法。 首先CDMA即码分多址,是物理层的东西;CSMA/CD即带冲突检测的载波监听多路访问,这个应该比较熟悉,接收方并不需要确认;CSMA,既然CSMA/CD是其超集,CSMA/CD没有的东西,CSMA自然也没有。 于是排除法选D。 CSMA/CA是无线局域网标准802.11中的协议。 CSMA/CA利用ACK信号来避免冲突的发生,也就是说,只有当客户端收到 予人玫瑰手留余香 王道论坛 网络上返回的ACK信号后才确认送出的数据已经正确到达目的地址。 37.某网络拓扑如下图所示,路由器R1只有到达子网192.168.1.0/24的路由。 为使R1可以将IP分组正确地路由到图中所有子网,则在R1中需要增加的一条路由(目的网络,子网掩码,下一跳)是 A.192.168.2.0 255.255.255.128 192.168.1.1 B.192.168.2.0 255.255.255.0 192.168.1.1 C.192.168.2.0 255.255.255.128 192.168.1.2 D.192.168.2.0 255.255.255.0 192.168.1.2 解答: D。 此题主要考察路由聚合。 要使R1能够正确将分组路由到所有子网,则R1中需 要有到192.168.2.0/25和192.168.2.128/25的路由。 观察发现网络192.168.2.0/25和 192.168.2.128/25的网络号的前24位都相同,于是可以聚合成超网192.168.2.0/24。 从图中可以看出下一跳地址应该是192.168.1.2。 38.在子网192.168.4.0/30中,能接收目的地址为192.168.4.3的IP分组的最大主机数是 A.0 B.1 C.2 D.4 解答: C。 首先分析192.168.4.0/30这个网络。 主机号占两位,地址范围192.168.4.0/30~ 192.168.4.3/30,即可以容纳(4-2=2)个主机。 主机位为全1时,即192.168.4.3,是广播地址,因此网内所有主机都能收到,因此选C。 39.主机甲向主机乙发送一个(SYN=1,seq=11220)的TCP段,期望与主机乙建立TCP连接,若主机乙接受该连接请求,则主机乙向主机甲发送的正确的TCP段可能是A.(SYN=0,ACK=0,seq=11221,ack=11221)B.(SYN=1,ACK=1,seq=11220,ack=11220)C.(SYN=1,ACK=1,seq=11221,ack=11221)D.(SYN=0,ACK=0,seq=11220,ack=11220)解答: C。 主机乙收到连接请求报文后,如同意连接,则向甲发送确认。 在确认报文段 中应把SYN位和ACK位都置1,确认号是甲发送的TCP段的初始序号seq=11220加1,即为ack= 11221,同时也要选择并消耗一个初始序号seq,seq值由主机乙的TCP进程确定,本题取seq= 11221与确认号、甲请求报文段的序号没有任何关系。 40.主机甲与主机乙之间已建立一个TCP连接,主机甲向主机乙发送了3个连续的TCP段,分别包含300字节、400字节和500字节的有效载荷,第3个段的序号为900。 若主机乙仅正确接收到第1和第3个段,则主机乙发送给主机甲的确认序号是 A.300 B.500 C.1200 D.1400 解答: B。 TCP段首部中的序号字段是指本报文段所发送的数据的第一个字节的序号。 第三个段的序号为900,则第二个段的序号为900-400=500。 而确认号是期待收到对方下一个报文段的第一个字节的序号。 现在主机乙期待收到第二个段,故甲的确认号是500。 二、综合应用题: 41~47小题,共70分。 请将答案写在答题纸指定位置上。 41.(8分)已知有6个顶点(顶点编号为0~5)的有向带权图G,其邻接矩阵A为上三角 予人玫瑰手留余香 王道论坛 矩阵,按行为主序(行优先)保存在如下的一维数组中。 4 6 ∞ ∞ ∞ 5 ∞ ∞ ∞ 4 3 ∞ ∞ 3 3 要求: (1)写出图G的邻接矩阵A。 (2)画出有向带权图G。 (3)求图G的关键路径,并计算该关键路径的长度。 解答: (1)图G的邻接矩阵A如下所示。 æ0 4 6 ¥ ç ç¥ 0 5 ¥ ç¥ ¥ 0 4 A=ç ç ç¥ ¥ ¥ 0 ç ç¥ ¥ ¥ ¥ è¥ ¥ ¥ ¥ ¥ ¥ö ÷ ¥ ¥÷ 3 ¥÷ ÷ ¥ 3÷ 3 ÷ ÷ 0 ÷ 0 ¥ ø (2)有向带权图G如下图所示。 0 3 6 4 3 4 2 5 5 3 3 1 4 (3)关键路径为0à1à2à3à5(如下图所示粗线表示),长度为4+5+4+3=16。 0 3 6 4 3 4 2 5 5 3 3 1 4 42.(15分)一个长度为L(L≥1)的升序序列S,处在第éL/2ù个位置的数称为S的中位数。 例如,若序列S1=(11,13,15,17,19),则S1的中位数是15,两个序列的中位数是含它们所有元素的升序序列的中位数。 例如,若S2=(2,4,6,8,20),则S1和S2的中位数是11。 现在有两个等长升序序列A和B,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列A和B的中位数。 要求: (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或JAVA语言描述算法,关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。 解答: (1)算法的基本设计思想如下。 分别求出序列A和B的中位数,设为a和b,求序列A和B的中位数过程如下: 1)若a=b,则a或b即为所求中位数,算法结束。 2)若a 3)若a>b,则舍弃序列A中较大的一半,同时舍弃序列B中较小的一半,要求舍弃的 予人玫瑰手留余香 王道论坛 长度相等; 在保留的两个升序序列中,重复过程1)、2)、3),直到两个序列中只含一个元素时为止,较小者即为所求的中位数。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 统考 题解
![提示](https://static.bingdoc.com/images/bang_tan.gif)