5 在一棵度为 4 的树 T 中, 若有 20 个度为 4 的结点,10 个度为 3 的结点,1 个度为 2 的结点,10 个度为 1 的结点, 则树 T 的叶节点个数是 (B) A:41 B:82 C:113 D:122 6 对 n(n 大于等于 2) 个权值均不相同的字符构成哈夫曼树, 关于该树

Size: px

Start display at page:

Download "5 在一棵度为 4 的树 T 中, 若有 20 个度为 4 的结点,10 个度为 3 的结点,1 个度为 2 的结点,10 个度为 1 的结点, 则树 T 的叶节点个数是 (B) A:41 B:82 C:113 D:122 6 对 n(n 大于等于 2) 个权值均不相同的字符构成哈夫曼树, 关于该树"

亦汤
5 years ago
Views:

一单选题 2010 年全国研究生考试计算机统考试题及答案 1 若元素 a,b,c,d,e,f 依次进栈, 允许进栈退栈操作交替进行但不允许连续三次进行退栈工作, 则不可能得到的出栈序列是 ( D ) A:dcebfa B:cbdaef C:dbcaef D:afedcb 2 某队列允许在其两端进行入队操作, 但仅允许在一端进行出队操作, 则不可能得到的顺序是 ( C )

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 1

2 5 在一棵度为 4 的树 T 中, 若有 20 个度为 4 的结点,10 个度为 3 的结点,1 个度为 2 的结点,10 个度为 1 的结点, 则树 T 的叶节点个数是 (B) A:41 B:82 C:113 D:122 6 对 n(n 大于等于 2) 个权值均不相同的字符构成哈夫曼树, 关于该树的叙述中, 错误的是 (B) 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 第三趟 :2,5,10,12,16,88 则采用的排序方法可能是 : 2

3 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 都需要进行刷新 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) 3

4 A: 存储器地址寄存器 (MAR) B: 程序计数器 (PC) C: 存储器数据寄存器 (MDR) D: 指令寄存器 (IR) 19 下列不会引起指令流水阻塞的是 (A) A: 数据旁路 B: 数据相关 C: 条件转移 D: 资源冲突 20 下列选项中的英文缩写均为总线标准的是 (D) A:PCI CRT USB EISA C:ISA SCSI RAM MIPS B:ISA CPI VESA EISA D:ISA EISA PCI PCI-Express 21 单级中断系统中, 中断服务程序执行顺序是 (A) I 保护现场 II 开中断 III 关中断 IV 保存断点 V 中断事件处理 VI 恢复现场 VII 中断返回 A:I V VI II VII C:III IV V VI VII B:III I V VII D:IV I V VI VII 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 D:2,0 4

5 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 {while(ture)} Flag[0]=TURE;ture=1 Void p1()// 进程 p1 {while(ture)} 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: 不能保证进程互斥进入临界区, 不会出现饥饿现象 C: 能保证进程互斥进入临界区, 会出现饥饿现象 D: 能保证进程互斥进入临界区, 不会出现饥饿现象 28 某基于动态分区存储管理的计算机, 其主存容量为 55mb( 初试为空间 ), 采用最佳适配 (Best fit) 算法, 分配和释放的顺序为 : 分配 15mb, 分配 30mb, 释放 15mb, 分配 8mb, 此时主存中最大空闲分区的大小是 ( B ) A:7mb B:9mb C:10mb D:15mb 29 某计算机采用二级页表的分页存储管理方式, 按字节编制, 页大小为 216 字节, 页表项大小为 2 字节, 逻辑地址结构为 5

页目编号页号页内偏移量逻辑地址空间大小为 216 页, 则表示整个逻辑地址空间的页目录表中包含表项的个数至少是 ( B ) A:64 B:128 C:256 D:512 30 设文件索引节点中有 7 个地址项, 其中 4 个地址项为直接地址索引,2 个地址项是一级间接地址索引,1 个地址项是二级间接地址索引, 每个地址项大小为 4 字节, 若磁盘索引块和磁盘数据块大小均为 256 字节,

6 页目编号页号页内偏移量逻辑地址空间大小为 216 页, 则表示整个逻辑地址空间的页目录表中包含表项的个数至少是 ( B ) A:64 B:128 C:256 D: 设文件索引节点中有 7 个地址项, 其中 4 个地址项为直接地址索引,2 个地址项是一级间接地址索引,1 个地址项是二级间接地址索引, 每个地址项大小为 4 字节, 若磁盘索引块和磁盘数据块大小均为 256 字节, 则可表示的单个文件的最大长度是 ( C ) A:33kb B:519kb C:1057kb 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 ) A:80ms B:80.08ms C:80.16ms D:80.24ms 35 某自治系统采用 RIP 协议, 若该自治系统内的路由器 R1 收到其邻居路由器 R2 的距离矢量中包含信息 <net1,16>, 则可能得出的结论是 ( A ) 6

7 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 C:8,32 B:32,6 D:8,30 38 下列网络设备中, 能够抑制网络风暴的是 ( C ) Ⅰ 中继器 Ⅱ 集线器 Ⅲ 网桥 Ⅳ 路由器 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 分 7

8 41.(10 分 ) 将关键字序列 ( ) 散列存储到散列列表中, 散列表的存储空间是一个下标从 0 开始的一个一维数组散列函数维 :H(key)=(key 3) MODT, 处理冲突采用线性探测再散列法, 要求装填 ( 载 ) 因子为 0.7 问题 : (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) 8

9 43.(11 分 ) 某计算机字长为 16q 位, 主存地址空间大小为 128KB, 按字编址, 采用字长指令格式, 指令名字段定义如下 : 转移指令采用相对寻址方式, 相对偏移是用补码表示, 寻址方式定义如下 : 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)+ ( 逗号前原操作数, 都号后为目的操作数 ) 对应的机器码是什么 ( 用十六进制表示 )? 该指令执行后, 哪些寄存器和存储单元的内容会改变? 改变后的内容是什么? 9

10 解答 : 该题的考点是指令系统设计, 注意操作位数与指令条数的关系, 地址码与寄存器数的关系, 指令字长与 MOR 的关系, 存储容量与 MAR 的关系, 注意补码计算的偏移地址 44.(12 分 ) 某计算机的主存地址空间为 256MB, 按字节编址, 指令 Cache 分离均有 8 个 Cache 行, 每个 Cache 行的大小为 64MB, 数据 Cache 采用直接映射方式, 现有两个功能相同的程序 A 和 B, 其伪代码如下所示 : 假定 int 类型数据用 32 位补码表示, 程序编译时 i,j, sum 均分配在寄存器中, 数据 a 按行优先方式存放, 其地址为 320( 十进制数 ), 请回答下列问题, 要求说明理由或给出计算过程 (1) 若不考虑用于 cache 一致性维护和替换算法的控制位, 则数据 Cache 的总容量是多少? (2) 要组元素 a[0][31] 和 a[1][1] 各自所在的主存块对应的 Cache 行号分别是多少 (Cache 行号从 0 开始 )? 10

11 (3) 程序 A 和 B 的数据访问命令中各是多少? 那个程序的执行时间更短? 简答 : 考点 :Cache 容量计算, 直接映射方式的地址计算, 以及命中率计算 ( 行优先遍历与列优先遍历命中率分别很大 ) 45 ( 7 分 ) 假设计算机系统采用 CSCAN( 循环扫描 ) 磁盘调度策略, 使用 2KB 的内存空间记录个磁盘块的空间状态 (1) 请说明在上述条件下如何进行磁盘块空闲状态管理 (2) 设某单面磁盘旋转速度为每分钟 6000 转每个磁道有 100 个扇区, 相临磁道间的平均移动时间为 1ms. 若在某时刻, 磁头位于 100 号磁道处, 并沿着磁道号大的方向移动 ( 如下图所示 ), 磁道号请求队列为对请求队列中的每个磁道需读取 1 个随机分布的扇区, 则读完这个扇区点共需要多少时间? 要求给出计算过程 11

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

13 解答 :17CAH=( )2 (1) 页大小为 1K, 所以页内偏移地址为 10 位, 于是前 6 位是页号, 所以第一间的解为 :5 (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 13

14 当一方发送的数据马上要到达另一方时, 另一方开始发送数据, 两台主机均检测到冲突所需时间最长 ; 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 14

<4D6963726F736F667420576F7264202D2032303130C4EAC8ABB9FAD1D0BEBFC9FABFBCCAD4BCC6CBE3BBFACDB3BFBCCAD4CCE2BCB0B4F0B0B82E646F63>

<4D6963726F736F667420576F7264202D2032303130C4EAC8ABB9FAD1D0BEBFC9FABFBCCAD4BCC6CBE3BBFACDB3BFBCCAD4CCE2BCB0B4F0B0B82E646F63> 2010 年全国研究生考试计算机统考试题及答案一单选题 1 若元素 a,b,c,d,e,f 依次进栈, 允许进栈退栈操作交替进行但不允许连续三次进行退栈工作, 则不可能得到的出栈序列是 ( D ) A:dcebfa B:cbdaef C:dbcaef D:afedcb 2 某