一、数据结构部分 1、选择题 （1）一个运算次数为 n*n+nlog2n+n+1 的程序时间复杂度为多少 A.O(n*n) B.O(nlog2n) C.O(n) D.O(1) （2）下列哪个算法适合求稀疏图的最小生成树 A.Prim B.Kruskal C.Dijkstra D.Floyd （3）....... 2、判断题(5 个） （1）栈和队列是双端队列的特殊情况 （2）树的子结点可以有任意多个，二叉树的孩子节点至多有两个，所有二叉 树是树的特殊情况 （3）一个带有头结点的单链表，结点数据类型为整形（1）编写算法将结点 元素为负整数的放 到链表前面，将结点元素为正整数的放到链表后面（2）对于 上述问题用何种物理结构实现 较好 （4）对于一颗二叉树，打印从根节点到先序遍历下最后一个节点的路径 （5）图用邻接表实现，打印从顶点 i 到顶点 j 的所有简单路径 二、操作系统部分 一、判断题(5 个） （1）最早的 gui 界面是在 window 系统上 二、操作计算题 1. 一个可抢占的动态优先级调度算法，优先数大的优先级高 

（1）等待状态下，进程优先级以 a 速度变化 （2）运行状态下，进程优先级以 b 速度变化 2. 进程优先级变化不同，会成为不同的调度算法 问：（1）a>b>0 时是什么调度算法 （2）a< b< 0 时是什么调度算法 3. 一个含有一百万条记录的文件，每个文件 16kb 到 到 32kb 不等，每个 物理块 4kb （1）如何设计文件目录，目录文件如何实现 （2） （3）设计文件的物理结构 （4）基于上述设计，访问某个文件的某个字节信息，最多访问几次磁盘，最少 访问几次 4. 磁盘 16 年第七题原题 有一个计算机的虚存系统采用请求式分页机制。其中，从内存读/写-个单元需要 花费 100ms。 该虚存系统由内存和硬盘组成，硬盘具有以下参数:转速 7200RPM,磁盘块大小 4KB,平均寻道 时间 5ms,传输率 16b/s,控制开销为 0.1ms。请回答以下问题: (1) 假如缺页率为 0,则该虚存系统的有效访问时间是多少? (2) 从硬盘读入或写出一个磁盘块的平均时间是多少? (3)如果缺页率为 1%，缺页时页面被修改的比例是 20%，不考虑缺页时的系 统开销，则该虚存系统的有效访问时间是多少? 5. 2016pv 操作题稍作修改: 有四个进程 S1、S2、 R1 和 R2，其中 S1、S2 向缓冲区 BUFF 发送消息， 

R1 和 R2 从缓冲区 BUFF 接收消息。发送和接收规则如下:: (a)S1,S2 向有可以存放两个消息的缓冲区发送消息: (b)进程 S1 发送消息 M1,M2,进程 S2 发送 E1,E2;: (c)缓冲区只能存放一 S1 发送的消息和一个 S2 发送的消息,不能存放同一进 程发送的两个消 息;(一共有四种可能< M1,E1>,< M2,E1>,< M1,E2>< M2,E2>): (d)接收进程 R1 只能接收接收进程 R2 只能接收: (e)当接收进程接收完成后清空缓冲区 请用信号量机制来实现这 4 个进程间 的同步。: