第1 页 2018 年攻读硕 士学位研 究生入学 考试试题 考试科目: 计算机科学专业基础综合 科目代码:874 （试题共 8 页） （答案必须写在答题纸上，写在试题上不给分） 数据结构 与算法（65 分） 一、单项选择题（每小题 2 分，共 17 小题，共 34 分 1. 下面关于“ 算法”的描述，错误的是 （ ） A. 算法必须 是正确的 B. 算法必须要能够结束 C. 一个问题可以有多种算法解决 D. 算法的某 些步骤可以有二义性 2. 下面函数的 时间复杂度是 （ ） void func(int n) int sum 0,i, j; for(i 1; i, , ， 则 G 的 一 个 拓 扑 序 列 （ ） A.V1 ，V3 ，V2 ，V6 ，V4 ，V5 ，V7 B.V1 ，V3 ，V4 ，V6 ，V2 ，V5 ，V7 C.V1 ，V3 ，V4 ，V5 ，V2 ，V6 ，V7 D.V1 ，V2 ，V5 ，V3 ，V4 ，V6 ，V7第3 页 13. 采用 Kruskal 算法求右图的最小生成树时， 依次选择的边是 （ ） A.(a,b)(b,c)(c,d)(d,f)(a,e) B.(d,f)(c,d)(b,c)(a,b)(a,e) C.(a,b)(b,c)(d,f)(c,d)(a,d) D.(a,b)(d,f)(b,c)(c,d)(a,e) 14. 设哈希表 长为 13 ， 哈希函数是 H （key ）=key 13， 表中 已有关键字 18，39，75 ，93 共 四个，现要将关键字为 70 的结点加到表中，用伪随机探测再散列法解决冲突，使用的伪随 机序列为 5 ，8 ，3 ，9 ，7 ，1 ，6 ，4 ，2 ，11 ，13，21 则放入的位置是（ A.8 B.11 C.7 D.5 15. 一棵高度 为 3 的 3 阶 B 树，至少含 有 （ ） 个关键字 A.12 B.10 C.7 D. 都不是 16. 在下列排 序算法中，哪一个算法的时间复杂度与数据的初始排列无关 （ ） A. 直接插入 排序 B. 希尔排序 C. 快速排序 D. 基数排序 17. 数据表中有 10000 个 元素，如果仅要求求出最大的 3 个元素，则采用 （ ） 算法最 节省时间 A. 堆排序 B. 希尔排序 C. 快速排序 D. 直接选择 排序 二、综合应用题（18-20 题，共 31 分 18. （10 分） 对于一个字符集中具有不同权值的字符进行 Huffman 编码时 ， 如果已知某个字 符的 Huffman 编码为 0101 ，对于其他无字符的 Huffman 编码，请分析说明: （1 ）具 有哪 些特征的编码是不可能的 （2 ）具有哪些特征的编码是一定会有的 19. （10 分） 设有向图用邻接表表示，图有 n 个顶点，表示为 0 至 n-1 ，试写一个算法求顶 点 k 的入度（0 k n ） 20. （11 分） 二 叉树结点的平衡因子（bf ）定义为该结点的左子树高度与右子树高度之差。 设二叉树结点结构为： (lchild,data,bf,rchild) ， child ， rchild 左右儿 子指针； data 是数据元素 ； bf 是平衡因子，编写递归算法计算二叉树中各个结点的平衡因子。 第4 页 操作系统 （50 分） 一. 单项选择题（26 分，每题 2 分） 1. 如果一个程 序被多个进程共享， 那么该程序的代码在执行过程中不能被修改， 即程序应该 是？ A 可执行码 B 可重入码 C 可改变码 D 可再现码 2. 当被阻塞进 程所期待的事件出现时，如 I/0 操作 完成或等待的数据到达，则调用唤醒原语 操作，将被阻塞的进程唤醒请问唤醒被阻塞进程的是？ A. 被阻塞进 程的父进程 B. 被阻塞进程的子进程 C. 被阻塞进程自身 D. 与被阻塞 进程相关的进程或其他进程 3. 某基于动态 分区存储管理的计算机，其主存的容量为 55MB ，这些空间在初始为空闲。采 用最佳分配算法， 分配和 释放的顺序分别为: 分配 15MB 、 分配 30MB 、 释放 15MB 、 分配 8MB 、 分配 6MB ，此时主存中最大空闲分区的大小是？ A 7MB B 9MB C 10MB D 15MB 4. 关于 DMA （Direct Memory Access ） ，下列说法 哪个是正确的？ A. 进程可以 直接读写一个外部设各 B. 内核可以直接读写进程的内存而不需要缓冲区 C. 进程可以直接读写内核内存而不需要缓冲区 D. 外部设备 可以直接读写系统内存 5. 当一个程序 被装入内存准备开始执行时，下面哪个段的大小是操作系统不知道的？ A.text B.data C.bss D.heap 6. 假设某系统 中的 TLB 的 命中率大约为 75， 并且使用了 2 级页表， 那么平均内存时间为？ A. 大约是原 来的 1.25 倍 B. 大约是原来的 1.5 倍 C. 大约是原来的 1.75 倍 D. 大约是原 来的 2 倍第5 页 7. 在动态分区 存储系统中，空闲表的内容如下: 空闲块号 1 23 4 块大小 80 7555 90 块的基址 60 150250 350 此时， 进程 P 请求 50KB 内存， 系统从第 1 个空闲块开始查找， 结果把第 4 个空闲块分配给 了进程 P 。请 问系统是采用哪种分区分配算法实现这一方案？ A 首次适应法 B 最佳适应法 C 最差适应 法 D 下次适应法 8. 某系统使 用 32 位逻辑地址，页大小 为 4kbytes ，以及 36 位物理地址。那么该系统中的页 表大小为？ A.220 个页 表项(2(32-12) B.224 个页表项(2(36-12) C.24 个页表项(2(36-32) D.212 个页 表项 9. 在上下文切 换期间，操作系统做了以下哪项工作？ A 修改了页表中的某些项，以反映新进程的内存映射 B 切换页表寄 存器指向另外的页表 C 为新进程 修改页 表中的访问权限 D 因为页表是系统级别的资源，所以并不会修改页表 10. 下列选项 中，降低进程优先权级的合理时机是？ A 、进程的时间片用完 B 、进程刚完成 I/0 ，进入就绪列队 C 、进程长期 处于就绪列队 D 、进程从就绪状态转为运行状态 11. 设与某资 源 相关联的信号量初值为 3 ，当前值为 1 ，若 M 表示该资 源的可用个数，N 表 示等待该资源的进程数，则 M ，N 分别是？ A.0 ，1 B.1 ，0 C.1 ，2 D.2 ，0 12. 有以请求 分页的存储管理系统， 页面大小为 100B ， 有一个 50×50 的整型数组， 按行为主 序连续存放，每个整数占 2B ，将数组初始化为 0 的程序描述如下: int A(50)(50); for (int i=0; i<50; i+) for (int j=0; j<50; j+) A(i,j) 0; 第6 页 若在程序执行时内存只有一个存储块用来存放数组信息， 试问该程序执行时产生多少次缺页 中断？ A.1 B.50 C.100 D.2500 13. 某文件中 共有 3 个记 录，每个记录占用 1 个 磁盘块，在 1 次读文件的操作中，为了读出 最后 1 个记 录，不得不读出了其他的 2 个记录 。根据这个情况可知这个文件所采用的结构 是？ A 顺序结构 B 链接结构 C 索引结构 D 顺序结构或连接结构 二. 综合题（24 分，每题 8 分） 1. 设文件索引 节点中有 8 个地址项， 其中 4 个地址为直接地址索引，2 个地址项是一级间接 地址索引，2 个地址项是二级间接地址索引， 每个地址项的大小为 4 字节， 若磁盘索引块和 磁盘数据块大小均为 256 字节，计算可表示的单个文件最大长度。 （8 分） 2. 已知某系统 页面长 4K 字节，页表项 4 字节，采用多层分页策略映射 64 位虚拟地址空间。 若限定最高层页表占 1 页。问它可以采用几层分页策略。 （8 分） 3. 有一只球框 ， 最多可以容纳两个球。 每次只能放入或取出一个球男教师专门向框中放入白 球(wb) ， 女教 师 专门 向框 中 放入 黑球(bb) 。 男 生专 门 拿框 中 的白球(wb) ， 女 生拿 框中 的 黑球 (bb) 。请用 Wait ，Signal 操作实现男教师，女教师，男生，女生之间的同步关系。（ 8 分） 计算机网 络（共 35 分） 一、选择题（每题 2 分，共 9 题，18 分） 1 关于 ARPANET 特征的描述中，不正确的是 （ ） A. ARPANET 的成功运行证明了交换理论的正确性 B. ARPANET Internet 的基础 C.Web 服务的出现促进了 ARPANET 的发展 D. ARPANET 采用的是 TCP/IP 标准 2. 如果发送数 据比特序列为 11110011，生 成多项式 比特序列为 11001， 那么发送方法给接收 方的比特序列为 （ ） A.111100110001 B.111100111100 C.1111001111001 D.111100111110第7 页 3.IP 分组分片基本方法中，描述错误的是 （ ） A.IP 分组长度大于 MTU 时，就必须对 IP 分组进 行分片 B.DF 1 ，分 组的长度超过 MTU ，则丢弃分组，不需要向源主机报告 C. 分片 MF 值为 1 表示接收的分片不是最后一个分片 D. 片偏移值 是以 8 字节为单位来计数的 4. 假如有一个 公司有一个 A 类 IP 地址 ， 原来内部有 700 个子网， 公司重组之后需要再建 450 个子网，而且要求每个子网最多可以容纳 4092 台主机，含适的子网掩码是 （ ） A./16 B./17 C./18 D./19 5 、以下关于 TCP 支持可 靠传输服务的描述中，错误的是 （ ） A.TCP 使用确 认机制来检查数据是否安全和完整地到达，并提供拥塞控制功能 B.TCP 对发送 和接收的数据进行跟踪、确认和重传，以保证数据能够到达接收端 C.TCP 能够通 过校验和来保证传输的可靠性 D.TCP 采用滑 动窗口方法进行流量控制。 6. 如 果 子 网 掩 码 为 255.255.192.0 ， 那 么 下 列 地 址 的 主 机 中 必 须 通 过 路 由 器 才 能 够 与 主 机 125.2.144.6 通信的是（ ） A.125.2.190.32 B.125.2.144.27 C.125.2.192.160 D.125.2.176.221 7. 一台交换机 具有 24 个 10/100Mbps 的端口和两个 1Gbps 端 口，如果所有端口都工作在全 双工状态，那么交换机的最大带宽为 （ ） A.4.4G B.6.4G C.6.8G D.8.8G 8. 在 MAC 协议中，对正确接收的数据帧 进行确认的是（ A.CDMA B.CSMA C.CSMA/CD D.CSMA/CA 9. 在对 OSI 参考模型中第 n 层与 n 1 层关系的描述中，正确的是（ ） A. 第 n-1 层为第 n 层提供服务 B. 第 n 层和 n 1 层之间是相互独立的 C. 第 n 层利用 n 1 层提供的服务为 n-1 层提供服 务 D. 第 n 1 层 为从 n 层接收的数据添加一个头部 第8 页 二、计算题（共 17 分） （8 分）1. 根 据图 1 所示的网络拓扑结构及地址， 请写出 R1 的路由表， 其中 R1 有两个接口 m1 和 m0 ， 路由表形式如下表所示。 （要求 R1 的路由表的表项在满足路由情况下，尽可能 精简） 图 1 拓扑结 构 目的地址 子网掩码（用点分十进制表示） 下一跳 转发端口 （9 分）2. 假设把一个大小为 3000bit 的数据报从源主机发送到目的主机，中间经过 4 个路 由器，共 5 段链路。每条链路的传输速率是 1Mbps ，每条链 路的传播时延都是 1ms ，忽略 队列时延和处理时延。 （1 ）假设是 一个分组交 换的数据报 网络，使用 了无连接的 服务。现在 假设每个数 据报加 了 200bit 头部，发送这个数据报从源主机到目的主机需要多长时间？（3 分） （2 ） 假 设 是 分 组 交 换 的 虚 电 路 网 络 ， 使 用 了 面 向 连 接 的 服 务 。 现 在 假 设 每 个 数 据 报 加 了 100bit 头部 ，虚电 路建 立的时 间是 8ms ， 发送 这 个数据 报从 源主机 到目 的主机 需要 多长时 间？（3 分） （3 ） 假设使 用电路交换的网络， 电路建立时间是 4ms ， 增 加了 200bit 的头部信息， 发送这 个数据报从源主机到目的主机需要多长时间？（3 分）