《【考研计算机专业课】2017年北京大学软件与微电子学院831试卷（计算机基础综合）》由会员分享，可在线阅读，更多相关《【考研计算机专业课】2017年北京大学软件与微电子学院831试卷（计算机基础综合）（4页珍藏版）》请在金锄头文库上搜索。
1、20172017 年北京大学软件与微电子学院年北京大学软件与微电子学院 831831 试卷（计算机基础综合）试卷（计算机基础综合）一.选择题：30*2=60 分 数据结构、操作系统、计算机网络各 10 道 1.已知两个长度分别为 m 和 n 的升序链表，若将他们合并为一个长度为 m+n 的降序链表， 则最坏情况下的时间复杂度为（ ）A. O(n). B.O(m*n). C.O(min(m,n). D.O(max(m,n)2.若一个链表最常用的操作是在末尾插入一个结点或删除最后一个结点，则选用（ ）作为 存储结构时间效率最高. A.单链表. B.带尾指针的单循环链表 C.双向链表. D.带尾指针
2、的双向循环链表3.一个栈的入栈顺序序列是 ABCDE，则不可能的出栈序列是（ ）A.ABCDE. B.EDCBA. C.DECBA. D.DCEAB4.若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0 和 3，则 从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别是多少（ ） A.1 和 5. B.2 和 4 C.4 和 2 D.5 和 15.一棵完全二叉树共 626 个结点，则叶子结点的数目为（ ） A.311 B.312. C.313. D.3146.一棵左子树为空的二叉树在先序线索化后，其中空的链域个数是（ ） A.0.
3、B.1. C.2. D.不确定7.设有向图 G 是具有 10 个顶点的强连通图，则 G 至少有（ ）边 A.45 B.90. C.10. D.98.下列关于关键路径的说法不正确的是（ ） A.一个事件的最早开始时间和以该事件为尾的弧的最早开始时间相同 B.所有的关键活动提前完成，整个工程才能提前完成 C.关键活动一定位于关键路径上 D.某些关键活动提前完成，整个工程将会提前完成9.在 AVL 树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A，已知 A 的左孩子 平衡因子为 0，右孩子平衡因子为 1，则应作（ ）型调整使其平衡A.LL. B.LR. C.RL. D.RR10.若需要在 O
4、(nlog2n)的时间内对数组排序，且要求排序是稳定的，则可选择（） A.快速排序. B.堆排序. C.归并排序. D.直接插入排序11.操作系统提供给程序员的接口是（ ）A.进程. B.系统调用. C.库函数. D.系统调用和库函数12.关于特权指令，准确的是（ ） A.可被操作系统内核使用 B.可被系统管理员使用 C.可被授权用户使用 . D.可在用户程序中使用 13. 关于进程描述不准确的是（） A.进程是在多道程序环境中完整的程序 B.进程可以由程序、数据、进程控制块描述 C.进程是一个程序在数据集合上的运行过程，是系统进行资源分配和调度的一个基本单位 D.线程是一种特殊的进程14.用
5、户程序执行时，使模式切换的原因不可能是（） A.出现中断事件 B.发生异常 C.执行系统调用 D.程序内跳转 15. 管程中的条件变量，主要作用是（） A.管理等待程序 B.表示资源数量 C.申请资源 D.回收资源 16. 关于信号，描述不准确的是（） A.信号是进程通信机制 B.信号是软件中断 C.信号是进程同步机制 D.信号可用于程序异常处理过程17.某系统内存容量 4GB，页面大小 4KB，采用反置页表，一个页表项需 4B。当系统中 有 40 个进程（设每个进程用 1GB 地址空间）时，反置页表占用的内存容量是（ ） A. 4MB B. 10MB C. 20MB D. 40MB 18.下
6、面页面替换算法中，缺页率从小到大的顺序通常为（ ） .最佳替换算法 .先进先出 .最近最少使用 A.， B.， C.， D.， 19.系统采用各种读写策略来提高磁盘操作的性能，但不包括 A.预先读 B.延迟读 C.预先写 D.延迟写 20.下列关于文件目录的主要作用描述，正确的是（ ） A.按名存取 B.提高外设利用率 C.节约磁盘空间 D.提高访问速度21.TCP/IP 协议体系结构中的应用层一般包括 OSI 协议体系结构中的（ ） A.应用层和表示层 B.表示层和会话层 C.会话层和运输层 D.应用层，表示层和会话层 22.在局域网内用于确定 IP 地址所对应的 MAC 地址的协议是（ ）
7、 A.ARP B.ICMP C.IGMP D.DHCP 23.某机构的 IP 地址空间是 192.168.5.0/24，现划分第一个子网，要求能同时支持 4 台 笔记本上网，那么最经济合理的划分所需要的网络前缀长度是（ ） A.30 比特 B.29 比特 C.28 比特 D.27 比特 24.以下不属于 TCP 协议的拥塞控制方法的措施是（ ） A.往返传输延迟的采样 B.发送串口的慢启动 C.重复确认多余的报文副本 D.报文重传后定时器时间加倍 25.在以太网的 CSMA/CD 协议中，CD 的含义是（ ） A.码分复用 B.载波侦听 C.多点访问 D.冲突检测 26.WWW 网页中用到的超
8、文本标记语言 HTML 属于 OSI 协议体系中的（ ） A.应用层 B.表示层 C.传输层 D.会话层 27. 一个信道的比特率的 4kb/s，传播延迟是 20ms，要使得停止等待协议有 50%以上的 效率，那么最小帧长是（ ） A.160b B.180b C.80b D.120b28.数据链路层采用了后退 N 帧（GBN）协议，发送方已经发送了编号为 07 的帧。当计 时器超时时，若发送方只收到 0、2、3 号帧的确认，则发送方需要重发的帧数是（ ）A.2. B.3. C.4. D.529.用户代理只能发送却不能接收电子邮件，则可能是（ ）地址错误A.POP3. B.SMTP. C.HTT
9、P. D.Mail30.HTTP 是一个无状态协议，然而 Web 站点经常希望能够识别用户，这时需要用到（ ） A.Web 缓存 B.Cookie. C.条件 GET. D.持久连接二.大题：90 分 1.（5 分）已知一颗二叉树的中序序列为 DCEFBHGAKJLIM，后序序列为 DFECHGBKLJMIA，画出这颗二叉树对应的森林。2.（15 分）有向图采用邻接矩阵结构存储，写个算法判断该有向图是否存在有向回路，若 存在，则以顶点序列的方式输出回路。3.（15 分）对一个数组 An进行排序，要求负数排在正数之前，0 排中间，分析时间复杂 度。4.（10 分）一个文件系统有一个 20MB 大
10、文件和一个 20KB 小文件，采用 LINUX 分配方案， 每块大小为 4096B，每块地址用 4B 表示。 LINUX 混合分配方案：有 12 个直接地址指针，还有一个一级索引，一个二级索引，一个 三级索引。问： (1)文件系统能管理的最大文件是多少？ (2)每对大小两文件各需要用多少专用块来记录文件的物理地址(说明各块的用途)(3)若需要读大文件前面的第 5.5KB 的信息和后面第(16M+5.5KB)的信息，则各需要多少次 盘 I/O 操作？5.(10 分)在一个批处理系统中，有两个作业进程。有一作业序列，其到达时间及估计运行 时间如下表。作业调度采用高响应比优先的算法，进程调度采用短作
11、业优先的抢占式调度 算法。 作业 到达时间 估计运行时间 min1 10:00 35 2 10:10 30 3 10:15 45 4 10:20 20 5 10:30 30 (1) 列出各作业的运行的时间片段；（2）计算这批作业的平均周转时间.6.（15 分）P.V 操作，3 个进程 R,M,P，共享大小为 n 的可循环使用的缓冲区 B，缓冲区互 斥使用。进程 R 负责从输入设备读信息，每读入一个字符，把他们存放在缓冲区 B 的一个 单元中，进程 M 负责处理读入的字符，如果字符是空格，将其改变为；，进程 P 负责从 缓冲区读出处理后的字符并打印。利用 P,V 操作作为同步机制写出他们能正确执行的程序， 注明使用的信号量及其意义。7.（8 分）对于计算机网络分层体系，为什么传输层必不可少？为什么有的应用程序采用 TCP 协议，有的采用 UDP 协议？8.（12 分）路由选择，给了个路由表，判定下一选择的接口
