<4D F736F F D C4EAC8ABB9FAD1D0BEBFC9FABFBCCAD4BCC6CBE3BBFACDB3BFBCCAD4CCE2BCB0B4F0B0B82E646F63>

Size: px

Start display at page:

Download "<4D6963726F736F667420576F7264202D2032303130C4EAC8ABB9FAD1D0BEBFC9FABFBCCAD4BCC6CBE3BBFACDB3BFBCCAD4CCE2BCB0B4F0B0B82E646F63>"

窕狂
7 years ago
Views:

1 2010 年全国研究生考试计算机统考试题及答案一单选题 1 若元素 a,b,c,d,e,f 依次进栈, 允许进栈退栈操作交替进行但不允许连续三次进行退栈工作, 则不可能得到的出栈序列是 ( D ) A:dcebfa B:cbdaef C:dbcaef D:afedcb 2 某队列允许在其两端进行入队操作, 但仅允许在一端进行出队操作, 则不可能得到的顺序是 ( C ) A:bacde B:dbace C:dbcae D:ecbad 3 下列线索二叉树中 ( 用虚线表示线索 ), 符合后序线索树定义的是 ( B ) 4 在下列所示的平衡二叉树中插入关键字 48 后得到一棵新平衡二叉树, 在新平衡二叉树中, 关键字 37 所在结点的左右子结点中保存的关键字分别是 ( C ) A:13,48 B:24,48 C:24,53 D:24,90

序是 ( C ) A:bacde B:dbace C:dbcae D:ecbad 3 下列线索二叉树中 ( 用虚线表示线索 ), 符合后序线索树定义的是 ( B ) 4 在下列所示的平衡二叉树中插入

2 5 在一棵度为 4 的树 T 中, 若有 20 个度为 4 的结点,10 个度为 3 的结点,1 个度为 2 的结点,10 个度为 1 的结点, 则树 T 的叶节点个数是 (B) A:41 B:82 C:113 D:122 的是 (B) 6 对 n(n 大于等于 2) 个权值均不相同的字符构成哈夫曼树, 关于该树的叙述中, 错误 A: 该树一定是一棵完全二叉树 B: 树中一定没有度为 1 的结点 C: 树中两个权值最小的结点一定是兄弟结点 D: 树中任一非叶结点的权值一定不小于下一任一结点的权值 7 若无向图 G-(V.E) 中含 7 个顶点, 则保证图 G 在任何情况下都是连通的, 则需要的边数最少是 (A) A :6 B:15 C:16 D:21 8 对下图进行拓补排序, 可以得到不同的拓补序列的个数是 (B ) A:4 B:3 C:2 D:1 9 已知一个长度为 16 的顺序表 L, 其元素按关键字有序排列, 若采用折半查找法查找一个不存在的元素, 则比较次数最多是 (A) A:4 B:5 C:6 D:7 10 采用递归方式对顺序表进行快速排序, 下列关于递归次数的叙述中, 正确的是 (D) A: 递归次数与初始数据的排列次序无关 B: 每次划分后, 先处理较长的分区可以减少递归次数 C: 每次划分后, 先处理较短的分区可以减少递归次数 D: 递归次数与每次划分后得到的分区处理顺序无关 11 对一组数据 (2,12,16,88,5,10) 进行排序, 若前三趟排序结果如下 (A) 第一趟 :2,12,16,5,10,88 第二趟 :2,12,5,10,16,88

E) 中含 7 个顶点, 则保证图 G 在任何情况下都是连通的, 则需要的边数最少是 (A) A :6 B:15 C:16 D:21 8 对下图进行拓补排序, 可以得到不同的拓补序列的个数是 (B ) A:4 B:3 C:2 D:1 9 已知一个长度为 16 的顺序表 L, 其元素

3 第三趟 :2,5,10,12,16,88 则采用的排序方法可能是 : A: 起泡排序 B: 希尔排序 C: 归并排序 D: 基数排序 12 下列选项中, 能缩短程序执行时间的措施是 (D) I 提高 CPU 时钟频率,II 优化数据通过结构,III 对程序进行编译优化 A: 仅 I 和 II B: 仅 I 和 III C: 仅 II 和 III D:I,II,III 13 假定有 4 个整数用 8 位补码分别表示 r1=feh,r2=f2h,r3=90h,r4=f8h, 若将运算结果存放在一个 8 位的寄存器中, 则下列运算会发生溢出的是 (C) A: r1*r2 B :r2*r3 C:r1*r4 D:r2*r4 14 假定变量 I,f,d 数据类型分别为 int,float 和 double(int 用补码表示,float 和 double 分别用 IEEE754 单精度和双精度浮点数据格式表示 ), 已知 i=785,f=1.5678,d=1.5 若在 32 位机器中执行下列关系表达式, 则结果为真是 (C) (I) f=(int)(float)i (II)f=(float)(int)f (III)f=(float)(double) (IV)=(d +f)-d=f A: 仅 I 和 II B: 仅 I 和 III C: 仅 II 和 III D: 仅 III 和 IV 15 假定用若干个 2k*4 位芯片组成一个 8*8 位存储器, 则地址 0B1FH 所在芯片的最小地址是 (D) A:0000H B:0600H C: 0700H D:0800H 16 下列有关 RAM 和 ROM 的叙述中, 正确的是 (A) I RAM 是易失性存储器,ROM 是非易失性存储器 II RAM 和 ROM 都是采用随机存取的方式进行信息访问 III RAM 和 ROM 都可用作 Cache IV RAM 和 ROM 都需要进行刷新

D:r2*r4 14 假定变量 I,f,d 数据类型分别为 int,float 和 double(int 用补码表示,float 和 double 分别用 IEEE754 单精度和双精度浮点数据格式表示 ), 已知 i=785,f=1.5678,d=1.

4 A: 仅 I 和 II B: 仅 II 和 III C: 仅 I,II,III D: 仅 II,III,IV 17 下列命令组合情况中, 一次访存过程中, 不可能发生的是 (D) A:TLB 未命中,Cache 未命中,Page 未命中 B:TLB 未命中,Cache 命中,Page 命中 C:TLB 命中,Cache 未命中,Page 命中 D:TLB 命中,Cache 命中,Page 未命中 18 下列存储器中, 汇编语言程序员可见的是 (B) A: 存储器地址寄存器 (MAR) B: 程序计数器 (PC) C: 存储器数据寄存器 (MDR) D: 指令寄存器 (IR) 19 下列不会引起指令流水阻塞的是 (A) A: 数据旁路 B: 数据相关 C: 条件转移 D: 资源冲突 20 下列选项中的英文缩写均为总线标准的是 (D) A:PCI CRT USB EISA B:ISA CPI VESA EISA C:ISA SCSI RAM MIPS D:ISA EISA PCI PCI-Express 21 单级中断系统中, 中断服务程序执行顺序是 (A) I 保护现场 II 开中断 III 关中断 IV 保存断点 V 中断事件处理 VI 恢复现场 VII 中断返回 A:I V VI II VII B:III I V VII C:III IV V VI VII D:IV I V VI VII

不会引起指令流水阻塞的是 (A) A: 数据旁路 B: 数据相关 C: 条件转移 D: 资源冲突 20 下列选项中的英文缩写均为总线标准的是 (D) A:PCI CRT USB EISA B:ISA CPI VESA EISA C:ISA SCSI RAM MIPS D:ISA EISA PCI

5 22 假定一台计算机的显示存储器用 DRAM 芯片实现, 若要求显示分辨率为 1600*1200, 颜色深度为 24 位, 帧频为 85Hz, 显示总带宽的 50% 用来刷新屏幕, 则需要的显存总带宽至少约为 (D) A :245 Mbps B:979 Mbps C:1958 Mbps D:7834Mbps 23 下列选项中, 操作 S 提供的给应用程序的接口是 (A) A: 系统调用 B: 中断 C: 库函数 D: 原语 24 下列选项中, 导致创进新进程的操作是 (C) I 用户成功登陆 II 设备分配 III 启动程序执行 A: 仅 I 和 II B: 仅 II 和 III C: 仅 I 和 III D:I,II,III 25 设与某资源相关联的信号量初值为 3, 当前值为 1, 若 M 表示该资源的可用个数, N 表示等待资源的进程数, 则 M,N 分别是 (B ) A:0,1 B:1,0 C:1,2

C: 库函数 D: 原语 24 下列选项中, 导致创进新进程的操作是 (C) I 用户成功登陆 II 设备分配 III 启动程序执行 A: 仅 I 和 II B: 仅 II 和 III C: 仅 I 和 III

6 D:2,0 26 下列选项中, 降低进程优先权级的合理时机是 ( A ) A: 进程的时间片用完 B: 进程刚完成 Z/O, 进入就绪队列 C: 进程长期处于就绪队列中 D: 就绪从就绪状态转为运行态 27 进行 P0 和 P1 的共享变量定义及其初值为 ( A ) boolean flag[2]; int turn=0; flag[0]=faulse;flag[1]=faulse; 若进行 P0 和 P1 访问临界资源的类 C 代码实现如下 : Void p0()// 进程 p0 Void p1()// 进程 p1 {while(ture)} {while(ture)} Flag[0]=TURE;ture=1 Flag[1]=TURE; ture=1 While (flag[1]&&(turn==1)) While (flag[0]&&(turn==0)) 临界区 : Flag[0]=FALSE; Flag[1]=FALSE; } } } } 则并发执行进程 P0 和 P1 时产生的情况是 : A: 不能保证进程互斥进入临界区, 会出现饥饿现象 B: 不能保证进程互斥进入临界区, 不会出现饥饿现象

程 p0 Void p1()// 进程 p1 {while(ture)} {while(ture)} Flag[0]=TURE;ture=1 Flag[1]=TURE; ture=1 While (flag[1]&&(turn==1)) While (flag[0]&&(turn==0)) 临界区 :

7 C: 能保证进程互斥进入临界区, 会出现饥饿现象 D: 能保证进程互斥进入临界区, 不会出现饥饿现象 28 某基于动态分区存储管理的计算机, 其主存容量为 55mb( 初试为空间 ), 采用最佳适配 (Best fit) 算法, 分配和释放的顺序为 : 分配 15mb, 分配 30mb, 释放 15mb, 分配 8mb, 此时主存中最大空闲分区的大小是 ( B ) A:7mb B:9mb C:10mb D:15mb 29 某计算机采用二级页表的分页存储管理方式, 按字节编制, 页大小为 216 字节, 页表项大小为 2 字节, 逻辑地址结构为页目编号页号页内偏移量逻辑地址空间大小为 216 页, 则表示整个逻辑地址空间的页目录表中包含表项的个数至少是 ( B ) A:64 B:128 C:256 D: 设文件索引节点中有 7 个地址项, 其中 4 个地址项为直接地址索引,2 个地址项是一级间接地址索引,1 个地址项是二级间接地址索引, 每个地址项大小为 4 字节, 若磁盘索引块和磁盘数据块大小均为 256 字节, 则可表示的单个文件的最大长度是 ( C ) A:33kb B:519kb C:1057kb

节, 逻辑地址结构为页目编号页号页内偏移量逻辑地址空间大小为 216 页, 则表示整个逻辑地址空间的页目录表中包含表项的个数至少是 ( B ) A:64 B:128 C:256 D:512 30 设文件索引节点中有 7 个地址项, 其中 4 个地址项

8 D:16513kb 31 设置当前工作目录的主要目的是 ( C ) A: 节省外存空间 B: 节省内容空间 C: 加快文件的检索速度 D: 加快文件的读写速度 32 本地用户通过键盘登录系统时, 首先获得键盘输入信息的程序是 (B ) A: 命令解释程序 B: 中断处理程序 C: 系统调用程序 D: 用户登录程序 33 下列选项中, 不属于网络体系结构中所描述的内容是 ( C ) A: 网络的层次 B: 每一层使用的协议 C: 协议的内部实现细节 D: 每一层必须完成的功能 34 在下图所示的采用存储 - 转发方式分组的交换网络中, 所有链路的数据传输速度为 100mbps, 分组大小为 1000B, 其中分组头大小 20B, 若主机 H1 向主机 H2 发送一个大小为 B 的文件, 则在不考虑分组拆装时间和传播延迟的情况下, 从 H1 发送到 H2 接收完为止, 需要的时间至少是 ( A )

一层使用的协议 C: 协议的内部实现细节 D: 每一层必须完成的功能 34 在下图所示的采用存储 - 转发方式分组的交换网络中, 所有链路的数据传输速度为 100mbps, 分组大小为

9 A:80ms B:80.08ms C:80.16ms D:80.24ms 35 某自治系统采用 RIP 协议, 若该自治系统内的路由器 R1 收到其邻居路由器 R2 的距离矢量中包含信息 <net1,16>, 则可能得出的结论是 ( A ) A:R2 可以经过 R1 到达 net1, 跳数为 17 B:R2 可以到达 net1, 跳数为 16 C:R1 可以经过 R2 到达 net1, 跳数为 17 D:R1 不能进过 R2 到达 net1 36 若路由器 R 因为拥塞丢弃 IP 分组, 则此时 R 可以向发出该 IP 分组的源主机发送的 ICMP 报文件类型是 ( C ) A: 路由重定向 B: 目的不可达 C: 源抑制 D: 超时 37 某网络的 IP 地址为 /24 采用长子网划分, 子网掩码为 , 则该网络的最大子网个数, 每个子网内的最大可分配地址个数为 ( B ) A:32,8 B:32,6 C:8,32 D:8,30 38 下列网络设备中, 能够抑制网络风暴的是 ( C )

数为 17 B:R2 可以到达 net1, 跳数为 16 C:R1 可以经过 R2 到达 net1, 跳数为 17 D:R1 不能进过 R2 到达 net1 36 若路由器 R 因为拥塞丢弃 IP 分组, 则此时 R 可以向发出该 IP 分组的源

10 Ⅰ 中继器 Ⅱ 集线器 Ⅲ 网桥 Ⅳ 路由器 A: 仅 Ⅰ 和 Ⅱ B: 仅 Ⅲ C: 仅 Ⅲ 和 Ⅳ D: 仅 Ⅳ 39 主机甲和主机乙之间已建立一个 TCP 连接,TCP 最大段长度为 1000 字节, 若主机甲的当前拥塞窗口为 4000 字节, 在主机甲向主机乙连接发送 2 个最大段后, 成功收到主机乙发送的第一段的确认段, 确认段中通告的接收窗口大小为 2000 字节, 则此时主机甲还可以向主机乙发送的最大字节数是 ( A ) A:1000 B:2000 C:3000 D: 如果本地域名服务无缓存, 当采用递归方法解析另一网络某主机域名时, 用户主机本地域名服务器发送的域名请求条数分别为 ( A ) A:1 条,1 条 B:1 条, 多条 C: 多条,1 条 D: 多条, 多条二综合应用题 :41-47 小题, 共计 70 分 41.(10 分 ) 将关键字序列 ( ) 散列存储到散列列表中, 散列表的存储空间是一个下标从 0 开始的一个一维数组散列函数维 :H(key)=(key 3)MODT, 处理冲突采用线性探测再散列法, 要求装填 ( 载 ) 因子为 0.7 问题 :

缓存, 当采用递归方法解析另一网络某主机域名时, 用户主机本地域名服务器发送的域名请求条数分别为 ( A ) A:1 条,1 条 B:1 条, 多条 C: 多条,1 条 D: 多条, 多条二综合应用题 :41-47 小题, 共计 70 分 41.

11 (1) 请画出所构造的散列表 ; (2) 分别计算等概率情况下, 查找成功和查找不成功的平均查找长度解答 : (1) 由装载因子 0.7, 数据总数 7 个存储空间长度为 10 P=10 所以, 构造的散列表为 : H(7)=(7 3)MOD10=1 (2) 查找成功的 ASL=( )/7=8/7 查找不成功的 ASL=( )/10= (13 分 ) 设将 n(n,1) 个整数存放到一维数组 R 中, 试设计一个在时间和空间两方面尽可能有效的算法, 将 R 中保有的序列循环左移 P(0<P<n) 个位置, 即将 R 中的数据由 (X0 X1 Xn-1) 变换为 (Xp Xp+1 Xn-1 X0 X1 Xp-1) 要求 : (1) 给出算法的基本设计思想 (2) 根据设计思想, 采用 C 或 C++ 或 JAVA 语言表述算法, 关键之处给出注释 (3) 说明你所设计算法的时间复杂度和空间复杂度解答 : 尾 (1) 前 P 个数依次进队,while(1<n-p)A{i}-{i+p}:p 个数依次出对, 进入数组末 (2) 详细程序略 (3) 时间复杂度 O(N); 空间复杂度 o(p) 43.(11 分 ) 某计算机字长为 16q 位, 主存地址空间大小为 128KB, 按字编址, 采用字长指令格式, 指令名字段定义如下 :

2 42.(13 分 ) 设将 n(n,1) 个整数存放到一维数组 R 中, 试设计一个在时间和空间两方面尽可能有效的算法, 将 R 中保有的序列循环左移 P(0<P<n) 个位置, 即将 R 中的数据由 (X0 X1 Xn-1) 变换为 (Xp Xp+1 Xn-1 X0 X1 Xp-1) 要求

12 转移指令采用相对寻址方式, 相对偏移是用补码表示, 寻址方式定义如下 : Ms/Md 寻址方式助记符含义 000B 寄存器直接 Rn 操作数 =(Rn) 001B 寄存器间接 (Rn) 操作数 =((Rn)) 010B 寄存器间接自增 (Rn)+ 操作数 =((Rn)),(Rn)+1 Rn 011B 相对 D(Rn) 转移目标地址 =(PC)+(Rn) 注 : (X) 表示有储蓄地址 X 或寄存器 X 的内容, 请回答下列问题 : (1) 该指令系统最多可有多少条指令? 该计算机最多有多少个通用寄存器? 存储器地址寄存器 (MDR) 至少各需多少位? (2) 转移指令的目标地址范围是多少? (3) 若操作码 0010B 表示加法操作 ( 助记符为 a d d), 寄存器 R4 和 R5 的编号分别为 100B 和 101B,R4 的内容为 H,R5 的内容为 H, 地址 H 中的内容为 H 中的内容为 H, 则汇编语言为 a d d(r4).(r5)+( 逗号前原操作数, 都号后为目的操作数 ) 对应的机器码是什么 ( 用十六进制表示 )? 该指令执行后, 哪些寄存器和存储单元的内容会改变? 改变后的内容是什么? 解答 : 该题的考点是指令系统设计, 注意操作位数与指令条数的关系, 地址码与寄存器数的关系, 指令字长与 MOR 的关系, 存储容量与 MAR 的关系, 注意补码计算的偏移地址 44.(12 分 ) 某计算机的主存地址空间为 256MB, 按字节编址, 指令 Cache 分离均有 8 个 Cache 行, 每个 Cache 行的大小为 64MB, 数据 Cache 采用直接映射方式, 现有两个功能相同的程序 A 和 B, 其伪代码如下所示 :

13 假定 int 类型数据用 32 位补码表示, 程序编译时 i,j, sum 均分配在寄存器中, 数据 a 按行优先方式存放, 其地址为 320( 十进制数 ), 请回答下列问题, 要求说明理由或给出计算过程 (1) 若不考虑用于 cache 一致性维护和替换算法的控制位, 则数据 Cache 的总容量是多少? (2) 要组元素 a[0][31] 和 a[1][1] 各自所在的主存块对应的 Cache 行号分别是多少 (Cache 行号从 0 开始 )? (3) 程序 A 和 B 的数据访问命令中各是多少? 那个程序的执行时间更短? 简答 : 考点 :Cache 容量计算, 直接映射方式的地址计算, 以及命中率计算 ( 行优先遍历与列优先遍历命中率分别很大 ) 45 (7 分 ) 假设计算机系统采用 CSCAN( 循环扫描 ) 磁盘调度策略, 使用 2KB 的内存空间记录个磁盘块的空间状态 (1) 请说明在上述条件下如何进行磁盘块空闲状态管理 (2) 设某单面磁盘旋转速度为每分钟 6000 转每个磁道有 100 个扇区, 相临磁道间的平均移动时间为 1ms. 若在某时刻, 磁头位于 100 号磁道处, 并沿着磁道号大的方向移动 ( 如下图所示 ), 磁道号请求队列为对请求队列中的每个磁道需读取 1 个随机分布的扇区, 则读完这个扇区点共需要多少时间? 要求给出计算过程

简答 : 考点 :Cache 容量计算, 直接映射方式的地址计算, 以及命中率计算 ( 行优先遍历与列优先遍历命中率分别很大 ) 45 (7 分 ) 假设计算机系统采用 CSCAN( 循环扫描 ) 磁盘调度策略, 使用 2KB 的内存空间记录 16384 个磁盘块的

14 46.(8 分 ) 设某计算机的逻辑地址空间和物理地址空间均为 64KB. 按字节编址若某进程最多需要 6 页 (Page) 数据存储空间, 页的大小为 1KB. 操作系统采用固定分配局部置换策略为此进程分配 4 个页框 (Page Fame). 页号页根号装入时刻访问位当该进程执行到时刻 260 时, 要访问逻辑地址为 17CAH 的数据, 请问答下列问题 : (1) 该逻辑地址对应的页号是多少? (2) 若采用先进先出 (FIFO) 置换算法, 该逻辑地址对应的物理地址是多少? 要求给出计算过程 (3) 若采用时钟 (CLOCK) 置换算法, 该逻辑地址对应的物理地址是多少? 要求给出计算过程 ( 设搜索下一页的指针沿顺时针方向移动, 且当前指向 2 号页框, 示意图如下 )

页号页根号装入时刻访问位 0 7 130 1 1 4 230 1 2 2 200 1 3 9 160 1 当该进程执行到时刻 260 时, 要访问逻辑地址为 17CAH 的数据, 请问答下列问题 : (1) 该逻辑

15 解答 :17CAH=( )2 为 :5 (1) 页大小为 1K, 所以页内偏移地址为 10 位, 于是前 6 位是页号, 所以第一间的解 (2)FIFO, 则被置换的页面所在页框为 7, 所以对应的物理地址为 ( )2-IFCAH (3)CLOCK, 则被置换的页面所在页框为 2, 所以对应的物理地址为 ( )2-OBCAH 47 (9 分 ) 某局域网采用 CSMA/CD 协议实现介质访问控制, 数据传输速率为 10MBPS, 主机甲和主机乙之间的距离为 2KM, 信号传播速度是 KMS. 请回答下列问题, 并给出计算过程 (1) 若主机甲和主机乙发送数据时发生冲突, 则从开始发送数据时刻起, 到两台主机均检测到冲突时刻止, 最短需经多长时间? 最长需经过多长时间?( 假设主机甲和主机乙发送数据过程中, 其他主机不发送数据 ) (2) 若网络不存在任何冲突与差错, 主机甲总是以标准的最长以大网数据锁 (1518 字节 ) 向主机乙发送数据, 主机乙每成功收到一个数据锁后, 立即发送下一个数据锁, 此时主机甲的有效数据传输速率是多少?( 不考虑以大网锁的前导码 ) 解答 : (1) 当甲乙同时向对方发送数据时, 两台主机均检测到冲突所需时间最短 ; 1KM/200000KM/S*2=1*10(-5)S 当一方发送的数据马上要到达另一方时, 另一方开始发送数据, 两台主机均检测到冲突所需时间最长 ;

度是 200 000KMS. 请回答下列问题, 并给出计算过程 (1) 若主机甲和主机乙发送数据时发生冲突, 则从开始发送数据时刻起, 到两台主机均检测到冲突时刻止, 最短需经多长时间? 最长需经过多长时间?

16 2KM/ KM/S*2=2*10(-5)S (2) 发送一锁所需时间 ;1518B/10MBPS=1.2144MS 数据传播时间 ;2KM/ KM/S=1*10(-5)S=0.01MS 有效的数据传输速率 =10MBPS*1.2144MS/1.2244MS=9.92MBPS

10. 若数据元素序列 11,12,13,7,8,9,23,4,5 是采用下列排序方法之一得到的第二趟排序后的结果, 则该排序算法只能是 A. 起泡排序 B. 插入排序 C. 选择排序 D. 二路归并排

10. 若数据元素序列 11,12,13,7,8,9,23,4,5 是采用下列排序方法之一得到的第二趟排序后的结果, 则该排序算法只能是 A. 起泡排序 B. 插入排序 C. 选择排序 D. 二路归并排 2009 年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一单项选择题 : 第 1~40 小题, 每小题 2 分, 共 80 分下列每题给出的四个选项中, 只有一个选项最符合试题要求 1. 为解决计算机主机与打