1、 科目名称：计算机原理 第 1 页 共 7 页 中国科学院大学中国科学院大学 20202020 年年招收攻读硕士学位研究生入学统一考试试题招收攻读硕士学位研究生入学统一考试试题 科目名称：科目名称：计算机计算机原理原理 考生须知：考生须知： 1本试卷满分为 150 分，全部考试时间总计 180 分钟。 2所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。 一、 单项选择题(每题 4 分，共 80 分) 1. 给定一个十进制数-3 的 32 位字长的二进制机器数，其无符号右移 8 位的结果是 。 A. 8388607 B. -8388607 C. 16777215 D. -1677721
2、5 2. IEEE754 浮点数二进制编码表示中，不在机器数中出现的是 。 A基数 B尾数 C符号 D阶码 3. CPU中的 ALU单元属于 部件。 A. 缓存 B. 内存 C. 运算器 D. 控制器 4. 内存空间是 8GB，如果 32 位计算机字长，按双字编址，其寻址范围是 。 A. 02000K-1 B. 01000M-1 C. 02000M-1 D. 0500M-1 5. 靠电容所存储的电荷表示电压值的电路是 。 ADRAM BCMOS CSRAM DCACHE 6. 如果(SS)=1000H，(SP)=0020H，(AX)=1805H，低位字节存在低地址，执行指令PUSH AX 后，
3、存放数据 05H 的物理地址是 。 A101FH B101EH C1001FH D1001EH 科目名称：计算机原理 第 2 页 共 7 页 7. 硬盘存储器转速为 6000 转/秒，共有 2 个记录盘面，每道记录信息 2GB，共有1K 个磁道，则磁盘数据传输率是 B/s。 A6000T B24000T C24T D6T 8. 采用字节多路通道控制方式的 I/O 系统， 共有 10 个子通道， 每个子通道每次传送 2 个字节，整个通道的最大传输速率为 100KB/s，则每个子通道的最大传输速率是 B/s。 A100K B50K C5K D10K 9. 设某棵二叉树的中序遍历序列为 DBEACF
4、，前序遍历序列为 ABDECF，则后序遍历该二叉树得到序列为是 。 ADEBCFA BDEBFCA CBEDFCA DEDBFCA 10. 设一组初始关键字记录关键字为(20，13，14，17，22，36，41，10)，则以 20为基准记录的一趟快速排序结束后的结果为 。 A13，10，14，17，20，36，41，22 B10，13，14，17，20，41，36，22 C10，13，14，20，17，41，36，22 D10，13，14，17，20，36，41，22 11. 设具有 n 个结点的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树的最大高度为 。 Alog2(n+1)-1
5、Bn-1 C(n-1)/2 D(n+1)/2 12. 下列排序算法中， 是稳定的排序。 A希尔排序 B冒泡排序 C快速排序 D堆排序 13. 在 AVL 树中插入结点和删除结点，以下说法正确的是 。 A 插入结点算法至多引起一次三结点平衡操作， 删除结点算法可能导致多次三结点平衡操作。 B插入结点算法至多引起一次三结点平衡操作，删除结点算法也至多引起一次三 科目名称：计算机原理 第 3 页 共 7 页 结点平衡操作。 C插入结点算法可能导致多次三结点平衡操作，删除结点算法也可能导致多次三结点平衡操作。 D 插入结点算法可能导致多次三结点平衡操作， 删除结点算法至多引起一次三结点平衡操作。 14
6、. 逆波兰表达式 1 2 3 + 4 5 6 7 + 8 9 +的计算结果为 。 A255 B240 C512 D250 15. 给定一串报文 CASTCASTSATATATASA， 使用哈夫曼编码实现报文数据的无损压缩，希望报文总编码长度最短，则下面 字符的编码长度应该最短。 AC BD CA DB 16. 路由器在两个网段之间转发数据包时，读取其中的 地址来确定下一跳的转发路径。 A. IP B. MAC C. 端口 D. ARP 17. 对于窗口大小为 n 的滑动窗口，最多可以有 帧已发送但没有确认。 A. n B. n-1 C. 2n D. n/2 18. 为了保证连接的可靠建立， T
7、CP 通常采用 方法。 A超时重传 B窗口控制 C重发机制 D三次握手 19. 如果一个 C 类网络用掩码 255. 255. 255. 224 划分子网， 那么会有 个可用的子网。 A. 3 B. 6 C. 9 D. 12 20. 如果网络的传输速率为 38.4Kbps， 要传输 4M字节的数据大约需要的时间是 。 A. 15 分钟 B. 30 分钟 C. 1 小时 D. 1 小时 30 分钟 二、 （本题共 6 分）给定一系列关键字的值 12、5、8、-5、5、12、7，分别执行以下两个任务： 科目名称：计算机原理 第 4 页 共 7 页 1. 将这些值按从左到右的顺序使用连续的插入操作构
8、建二叉搜索树，请画出最后形成的二叉搜索树结构图。 （假设关键字相等时始终采用相同的插入规则， 请在答题时写明此规则） 2. 将这些值按从左到右的顺序使用连续的插入操作构建小顶堆，请画出最后形成的小顶堆的结构图。 三、 （本题共 7 分）请从下面时间复杂度中选择，找出与下列函数相匹配的时间复杂度选项。 1. 2. 3. 科目名称：计算机原理 第 5 页 共 7 页 4. 5. 6. 7. 科目名称：计算机原理 第 6 页 共 7 页 四、 （每题 7 分，共 21 分） 1. 计算机网络中的常见的时延有哪些？每种时延的意义是什么？ 2. 说明链路状态路由算法和距离向量路由算法，并进行对比分析。
9、3. TCP 协议与 IP 协议有哪些主要的区别？ 五、 综合应用题 （每题 9 分，共 36 分） 1给定浮点数 0.90625， （1）根据 IEEE754 标准，给出其 32 位宽的二进制机器数表示； （2） 如果用 （1） 问中得到的二进制机器数表示一个整数的补码， 该整数值是多少？ 请给出具体计算过程。 2如果 CPU 的时钟频率为 1GHz，硬盘的传输数据带宽为 64 位，数据传输速率为10MB/s，则： （1）以程序查询方式访问 I/O，为避免数据丢失进行足够的程序 I/O 查询，如果一个查询操作需要 200 个时钟周期，则 CPU在程序查询所耗费的时间之比是多少？ （2）以中断
10、控制方式访问 I/O，每次传输的开销（包括中断处理）为 100 个周期，则 CPU为传输硬盘数据耗费的时间之比； （3）采用 DMA 控制进行输入/输出操作，假定 DMA 的启动操作需要 500 个时钟周期， DMA完成时处理中断需要250个时钟周期， 如果DMA每次传输的数据长度为1MB，则在硬盘工作时处理器将用多少时间比率进行输入/输出操作，忽略 DMA 申请总线的时间。 3假设有如下所示的加权有向图，共有 9 个顶点和 19 条边，图中的边的权重是 1到 19 之间的整数。 科目名称：计算机原理 第 7 页 共 7 页 （1） 按照 Kruskal 算法求解最小生成树， 按求解顺序记录最小生成树的边的权重序列。 （2）按照 Prim 算法求解最小生成树，按求解顺序记录最小生成树的边的权重序列。 4. 主机 A 向主机 B 连续发送了两个 TCP 报文段，其序号分别为 60 和 100。问： （1）第一个报文段携带了多少个字节的数据？ （2）主机 B 收到第一个报文段后发回的确认中的确认号应当是多少？ （3）如果主机 B 收到第二个报文段后发回的确认中的确认号是 150，试问 A 发送的第二个报文段中的数据有多少字节？ （4）如果 A 发送的第一个报文段丢失了，但第二个报文段到达了 B。B 在第二个报文段到达后向 A 发送确认。试问这个确认号应为多少？
