院校：南京工业大学
828数据结构与操作系统
闭卷考试，总分150（数据结构90+操作系统60），考试时间为3小时。
题型：
主要包括选择题 、编程题、计算题、综合题等类型，并根据每年的考试要求做相应调整。
是否有答案：有
皮皮灰数据结构+操作系统
仅供测试
第一部分：数据结构（共90分）
一、单项选择题（下列每题给出的四个选项中，只有一项符合试题要求。每小题 2分，共 30分）
1、下列数据中，（）是非线性数据结构。
A.栈
B.队列
C.完全二叉树
D.堆
2、以下属于逻辑结构的是（）。
A.顺序表
B.哈希表
C.有序表
D.单链表
3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A.单链表
B.仅有头指针的单循环链表
C.双向链表
D.仅有尾指针的单循环链表
4、对（）中序遍历必将得到一个树种结点的非递减有后序序列。
A.AVL树
B.扩充二叉树
C.败方树
D.最小堆
5、设散列表ht[11]，散列函数h（key）=key mod11，用关键字序列{24,34,35,39,46}建立散列表，采用二次探查法解决冲突，则46在散列表中的下标为（）。
A.-2
B.2
C.6
D.9
6、已知串 S="abab”，在 KMP 模式匹配算法中，其中 Next 数组值为A.0123
B.0121
C.0112
D.0122
7.以下关于图的说法，不正确的是（）。
A.无向图中的极大连通子图称为连通分量
B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点
C.图的深度优先搜索中一般采用栈暂存刚访问过的顶点
D.有向图的遍历不可采用广度优先搜索方法
8、在下列存储形式中，（）不是树的直接存储形式。
A.双亲表示法
B.三重链表表示法
C.孩子兄弟表示法
D.多重链表表示法
9、下列排序算法中，经过一趟排序后不一定能确定待排序元素的最终位置的算法是（）。
A.直接插入排序
B.冒泡排序
C.快速排序
D.简单选择排序
10、二叉树在线索化后，仍不能有效求解的问题是（）。
A.先序线索二叉树中求先序后继
B.中序线索二叉树中求中序后继
C.中序线索二叉树中求中序前驱
D.后序线索二叉树中求后序后继
11、下面关于哈希查找的说法，不正确的是（）。
A.采用链地址法处理冲突时，查找一个元素的时间是相同的
B.采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的
C.用链地址法处理冲突，不会引起二次聚集现象
D.用链地址法处理冲突，适合表长不确定的情况
12、下面几个编码集合中，不是前缀编码的是（）。
A.{0,10,110,1111}
B.{11,10,001,101,0001}
C.{00,010,0110,1000}
D.{b，c，aa，ac，aba，abb，abc}
13、循环队列存储在数组A[0..m]，则入队时的操作为（）。
A.rear=rear+1
B.rear=（rear+1）mod（m-1）
C.rear=（rear+1）mod m
D.rear=（rear+1）mod（m+1）
14、m阶B-树是一颗（）。
A.m叉排序树
B.m叉平衡排序树
C.m-1叉平衡排序树
D.m+1叉平衡排序树
15、下列关于AOE网的叙述中，不正确的是（）。
A.关键活动不按期完成就会影响整个工程的完成时间
B.任何一个关键活动提前完成，那么整个工程将会提前完成
C.所有的关键果冻提前完成，那么整个工程将会提前完成
D.某些关键活动提前完成，那么整个工程将会提前完成
二、综合应用题（5小题，共60分）；
16.（本题 16 分）写一个算法合并三个已排序的线性表（线性表用指针表示（链表），且三个线性表都是升序排列）要求：
（1）定义线性表节点的结构 celltype，其所包含数据 element 为整型，并定义节点的型 LIST（celltype 指针的类型定义）和位置的型 position。（2）假设线性表的基本操作已经定义。
（3）在 1，2 的基础上，完成本题，即编写函数 void mergeThreeLists (LIST& L, LIST L1, LIST L2, LIST L3)，实现将线性表 L1、L2 和 L3 合并，其结果存放在 L 中。
17.给定一个以二叉链表表示的二叉树，查找值为x的结点，并输出该结点的所有祖先。假设值为x的结点不多于一个。要求给出算法设计思想，并采用C/C++语言描述算法。
18.根据给定的关键字集合（20，15，40，35，45，25，50，30，10）顺序输入，完成：
（1）构造一棵完全二叉树；
（2）要求非递减有序排列，构造初始堆；
（3）输出第一个堆顶元素后重新调整好的堆树
。
19.试将关键码17，9，2，12，14，26，33，15，40，23，25依次插入到一棵初始为空的AVL树中，画出每次完成平衡操作后的AVL树。
20.
操作系统
第二部分：操作系统（共 60分）
一、单项选择题（每小题2分、共24分）
1.若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的操作是______。
I、处理越界错 II、置换页 III、分配内存
A. 仅 I、II
B. 仅 II、III
C. 仅 I、III
D. 仅 I、II、III
2.若某文件系统索引结点中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是______。
A. 索引结点的总数
B. 间接地址索引的级数
C. 地址项的个数
D. 文件块大小
3.设文件索引节点中有 10 个地址项，其中 8 个地址项是直接地址索引，1 个地址项是一级间接地址索引，1 个地址项是二级间接地址索引，每个地址项大小为 4B（4 字节）。若磁盘索引块和磁盘数据块大小均为 1KB（1024 字节），则可表示的单个文件最大长度是______。
A. 1057KB
B. 16513KB
C. 65800KB
D. 163840KB
4.下列文件物理结构中，适合随机访问且易于文件扩展的是______。
A. 连续结构
B. 索引结构
C. 隐式链接结构且磁盘块定长
D. 隐式链接结构且磁盘块变长
5.引入高速缓冲的主要目的是______。
A. 提高 CPU 的利用率
B. 提高 I/O 设备的利用率
C. 改善 CPU 和 I/O 设备之间速度不匹配的情况
D. 节省内存
6.在下列存储管理方式中，不要求将作业全部装入并且不要求一个连续存储空间的管理方式是______。
A. 分页存储管理
B. 单用户连续存储管理
C. 可变换分区式存储管理
D. 请求分段式存储管理
7.考虑一个分页存储管理系统，其页表常驻内存，试回答以下两个问题：
(1) 如果内存访问耗时 200ns，那么访问内存中的数据需要多长时间？
(2) 如果引入快表 (TLB) 机制，而且假如 75% 的页面表项可以从快表中找到，那么此时的有效访问时间为多少？(假如访问快表的时间可以忽略不计)
A. 200ns, 150ns
B. 400ns, 150ns
C. 400ns, 250ns
D. 600ns, 250ns
8.在请求分页系统中，一个进程分配到 m 个物理块，这些物理块初始时全空，页面引用串长度为 p，其中包含了 n 个不同的页号，则无论采用何种页面置换算法，该进程运行过程中的缺页次数 k 满足：
A. m < k < p
B. m <= k <= p
C. n < k < p
D. n <= k <= p
9.在下列文件中，不便于文件增删的是______。
A. 连续文件
B. 链接文件
C. 索引文件
D. Hash 文件
10.考虑一个文件存放在 100 个数据块中，假如文件控制块、索引块或索引信息都已驻留内存。那么如果______，则不需要做任何磁盘 I/O 操作。
A. 采用连续文件物理结构，将最后一个数据块搬到文件头部
B. 采用单级索引文件物理结构，将最后一个数据块插入文件头部
C. 采用链接文件物理结构，将最后一个数据块插入文件头部
D. 采用链接文件物理结构，将最后一个数据块插入文件尾部
11.如果磁盘当前读写头正在 53 号柱面上进行操作，现有 4 个等待访问的请求，请求访问的柱面号依次为 98、37、126、65，当采用______调度算法时，接下来第一个要满足的是 37 号柱面的访问请求。
A. 先来先服务
B. 最短寻道时间优先
C. 电梯调度 (假设当前磁头向着柱面号减小的方向移动)
D. 循环扫描 (假设当前磁头向着柱面号增加的方向移动)
12.引起 I/O 中断的事件有
(1) 数据传送完毕
(2) 设备出错
(3) 设备正在处理数据
(4) 指令错
(5) 缺页
A. (1)(5)
B. (2)(5)
C. (1)(2)(4)(5)
D. 以上答案都错
二、计算（综合）题（3小题，共36分）
13.假设某医院眼科门诊有n个医生，有m个挂号窗口，可以容纳m个病人同时挂号（提示：将病人挂号号码排成一个队列，对该队列的操作要求互斥）。每个病人先挂号，然后在候医大厅等待叫号，当医生空闲时就叫一个号，试用P、V 操作实现上述过程，要求分别写出病人和医生的相应诊疗过程。
14.设有 15 个同类资源可供 4 个进程共享，进程对资源的需求量及资源分配的情况如下：
| 进程 | 已占资源数 | 最大需求量 |
|---|---|---|
| P1 | 3 | 5 |
| P2 | 4 | 7 |
| P3 | 5 | 8 |
| P4 | 1 | 4 |
试回答以下问题：
(1) 目前系统是否处于安全状态？为什么？
(2) 如果这四个进程又都要求系统再分配 1 个资源时，应该先分配给哪个进程？为什么？
15.一个计算机系统有两种实现方案，第一种实现方案是流水线方案，第二种是非流水线方案，两种实现方案的设计参数如下表所示。其中 CPI 表示每条指令的周期数。
| 参数 | 流水线实现 | 非流水线实现 |
|---|---|---|
| 时钟频率 | 500MHz | 350MHz |
| ALU 指令的 CPI | 1 | 1 |
| 控制指令的 CPI | 2 | 1 |
| 内存访问指令的 CPI | 2.7 | 1 |
(1)（5 分）对一个具有 20% 的 ALU 指令，10% 的控制指令和 75% 的内存访问指令的程序，哪种设计更快？
(2)（5 分）对一个具有 80% 的 ALU 指令，10% 的控制指令和 10% 的内存访问指令的程序，哪种设计更快？
可打印精选版本【人工答案】
数据结构汇总【答案不保真】
计算机网络模拟卷汇总【答案不保真】
计算机组成原理模拟卷汇总【答案不保真】
操作系统汇总【答案不保真】
C语言模拟卷汇总【答案不保真】
