川大考研辅导:2018四川大学874计算机科学专业考研真题.pdf
第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 , 有一个 5050 的整型数组, 按行为主 序连续存放,每个整数占 2B ,将数组初始化为 0 的程序描述如下: int A(50)(50); for (int i=0; i50; i+) for (int j=0; j50; 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 分)