2015-17试题涉及内容

2015年

第一部分， 数据结构
一、选择题

三对角矩阵
排序稳定性

(前中后序线索树哪种)遍历需要用到栈

n顶点连通无向图，边数最少多少

排序题:希尔排序，快速排序

哈希表可能冲突情况哪种

图的邻接矩阵是对称矩阵(有向图 无向图 AOV AOE)

二、简答题

1. 网的最小生成树哪两种方式? 以及区别 ? 为什么 ?

2. 给一个序列，构造二叉排序树。再构造二叉平衡树， 讨论二叉排序树与二叉平衡树的区别。

3.给一个序列， 建立堆。

三、算法题

两个单链表是从小到大顺序排列的。 合成一个链表， 从大到小。

第二部分， 操作系统

重点: 设备管理， 索引文件系统

四、选择题

1. 3级索引文件系统，仅有文件控制信息， 每次访问文件时访问磁盘几次?

2.文件物理结构， 不利于长度动态增长的物理结构是?

3.段页式访问内存几次?

4.系统调用I/O设备时，通常使用的设备标示符是什么

5.程序与实际使用的物理设备无关，由什么实现?

6.文件的相对路径， 从什么开始?

五、简答题

1. 预防死锁和避免死锁的区别 ?

2. p1 p2 p3 p4四个进程并发执行，用PV操作表示。

3. 文件系统物理结构采用索引文件，一级二级三级

4 .I/O控制中断功能,1/O进程实现方式有哪三种？

六、大题

轮转法和多级反馈轮转法

2016年

第一部分， 数据结构

一、选择
那种排序算法占用空间大算法的时间复杂度

二、简答
1.给出了树的中序和后序，构造一个森林，并画出来。
2.给一个链接矩阵，写出深度和广度遍历序列

3.哈希表的链地址法

三、算法题
删除数组中等于item的元素，用时间复杂度低的方并求时间法。复杂度低的方法。

第二部分， 操作系统

四、简答题
1.什么是进程?进程与程序的区别 ?

2.什么是临界区?临界区为什么不能交叉运行?请举例说明。
3.什么是死锁?画一个死锁图，死锁产生的条件。
4.为什么使用缓冲?缓冲有哪几种?

五、大题

短进程优先和高响应比算法

两个生产者一个消费者

2017

数据结构

一、选择题

1.N个节点，K条边。则一定有几棵树？

2.静态链表指针是什么: 数组下标 内存地址.

3.空间复杂度的决定因素。

4.什么情况下一定有无拓扑序列;

5.M阶B-树有: m-1阶平衡二叉排序树，

6.选择快速排序树比较次数最少的队列

二、简答题

1.有向网: 画邻接表 ；PRIM算法最小生成树一组元素

2.平衡二叉排序树形成过程；写出中序遍历队列

3.给一个队列，在升序条件下的第一趟冒泡排序， 步长为4希尔排序， 2路归并排序结果和以其为基础的初始堆。

三、算法题

孩子-兄弟节点存储二叉树

操作系统

一、选择题

1.轮转法的时间片一定, 响应时间减少的有关因素。

2.I/O设备不可以控制什么东西，什么与其控制内容无关。

二、简答题

多道程序设计及其优点。

进程调度的时机。

文件物理结构适用情况。

什么是系统调用, 函数子程序和系统调用的区别。

段页式管理系统优缺点。

三、综合题

1.页面置换过程LRU,FIFO缺页率。

2.PV原语P1,P2,P3,produce();Put();Get();统计次品个数中转区。