2022 年天津理工大学研究生招生考试 808 数据结构与操作系统
考试时间 180 分钟，满分 150 分。请将答案写在答题纸上，并标清楚题号。写在卷子上不
得分。交卷时，请将本试卷与答题纸一并装入信封袋中。
数据结构部分
一、选择题部分（20 分）
1、下列算法的时间复杂度是：
while (){
int i , j ;
for ( i =0; i < n ; i ++)
for ( j =1; j < n ; j *=2)
A .O ( n ) B .O(1og2n) C .O(nlog2n) D. O(n ^2)
2、有一个 200*90 的稀疏矩阵，非 0 元素有 10 个，设每个整型数占 2 字节，则用三元组
表示该矩阵时，所需的字节数是（)
A 30 B 60 C 66 D 96
3、关于 B 树和 B ＋树有以下几种叙述，不正确的是（)。
A . B 树和 B ＋树都可以用于文件的索引结构
B . B 树和 B ＋树都是平衡的多分树
C . B 树和 B ＋树都能有效地支持随机检索
D . B 树和 B ＋树有效地支持顺序检索
4、设一个进栈顺序（1,2,3,... n )，一个出栈 p1 ,p2,p3...· pn , p1 对应的是 3，则 p2 对应的
（）
A 一定是 1 B 可能是 1 C 不可能是 1 D 以上都不对
5、向一个栈顶指针为 h 的带头结点的链栈中插入指针 s 所指的结点时，应执行（）
A . h -> next =s ;
B . s -> next = h ;
C . s -> next = h ; h -> next = s ;
D . s -> next = h -> next ; h -> next = s ;
6、对于一个非连通无向图，共有 28 条边，则该图至少有多少个项点？（）
A 8 B 9 C10 D11
7、双向链表中，设 p 指针所指结点之后插入 q 指针所指向的结点，则该怎么操
作（)
A 、 q -> prior = p ; p -> next = q ; p -> next -> prior = q ; q -> next = p -> next
B 、 q -> next = p -> next ; p -> next -> prior = q ; p -> next = q ; q -> prior = pC 、 p -> next = q ; q -> prior = p ; q -> next = p -> next ; p -> next -> prior = q
D 、 q -> prior = p : p -> next = q ; q -> next = p -> next ; p -> next -> prior = q
8、已知循环队列的存储空间为数组 A [21], front 指向队头元素的前一个位置， rear 指向队
尾元素，假设当前 front 和 rear 的值分别为 8 和 3，则该队列的长度为()
A .5 B.6 C.16 D .17
9、已知一棵二树的后序序列为 DABEC ，中序序列为 DEBAC ，则先序序列为（)。
A . ACBED B. DECAB C . DEABC D . CEDBA
10、下面那个序列不是折半查找的访问数值序列()
A 、500,200,450,180
B 、500,450,200,180
C 、180,500,200,450
D 、180,200,500,450
二、综合应用题(60 分)
1、假设你是一名工程师，现在要往 6 个村庄修建网络线路，村庄分布如下。

(1）请问你将采用什么原理或方法选择修建路线？请举出两个方法。(4 分）
(2）请画出路线图。(6 分）
2、有一电报人员需要发送以下字符 AAABBBBCCDEFAAABBCDEABBCD ，一共 25 个（10
分）
(1）请将上述字符进行哈夫曼编码，并给出编码理由。(6 分）
(2）若编码前缀为 001，则哪些字符一定不是该前缀编码？(2 分）
(3）若编码前缀为 001，则哪些字符一定是该前缀编码？(2 分）
3、有以下关键字序列（55 19 79 24 81 37 24）
(1）请写出冒泡排序和快排序的第一趟结果（标明排序方法）。(6 分）
(2）如果冒泡排序的关键字的移动方向和排序顺序相反，请解释为什么会出现这种情况，并举例说明。快速排序会不会出现这种情况？(4 分）
4、有一长度为 10 的存储空间，现将下列数字通过散列函数（ Key *3%7）散列存
储。
5 7 13 17 9 11 2 1

(1）请补全表格（6 分）
(2）查找成功的平均次数是？(4 分）
5.
(1）请编写算法将 LA 和 LB 两个循环单链表链接成一个循环单链表，其中 A 为 LA 的尾结
点， B 为 LB 的尾结点。(8 分）
(2）请分析以上算法的时间复杂度
6.
(1）请写出二叉链表树的存储结构（2 分）
(2) 若二叉树的根节点为 B ，请编写算法，找出结点值为 X , Y 的结点，并判断两结点是否为
兄弟结点，若是则返回 True ，否则返回 False (8 分）
操作系统部分
一、选择题部分（14 分）
(1）在操作系统中，死锁出现指的是()
A.计算机发生了重大故障
B.资源数远远少于进程数
C.若干进程因竞争资源而无限等待其他进程释放已占有的资源
D.进程同时申请的资源数超过资源总数
(2）在下列死锁的解决办法中，属于预防死锁策略的是()
A.银行家算法
B.资源有序分配法

C.死锁检测法
D.资源分配图化简法
(3）当用户程序执行访管指令时，中断装置将使中央处理器（）工作。
A.维持在目态
B.从目态转换到管态
C.维持在管态
D.从管态转换到目态
(4）若系统中有五台绘图仪，有多个进程均需要使用两台，规定每个进程仅允许申请一台，
则至多允许（）个进程参与竟争，而不会发生死锁。
A .5 B.2 C.3 D.4
(5）原语是一种特殊的系统调用命令，它的特点是（）。
A.执行时不可中断
B.自己调用自已
C.可被外层调用
D.功能强
(6）实时操作系统必须在（）内处理完来自外部的事件。
A.一个机器周期 B.被控对象规定时间 C.周转时间 D.时间片
(7）引入缓冲技术的目的是（）
A .降低计算机的硬件成本
B .改善用户编程环境
C .提高 CPU 的处理速度
D.提高 CPU 与设备之间的并行程度
(8）系统调用的目的是（)
A 请求系统服务 B.中止系统服务 C.申请系统资源 D.释放系统资源
(9)（）有利于 CPU 繁忙型的作业、而不利于 I /0 繁忙型的作业
A 时间片转轮法 B 先来先服务 C 短作业优先 D 优先级调度
(10）设与某资源关联的信号量初值为 3，当前值为 1．若 M 表示该资源的可用个数， N 表
示等待该资源的进程数，则 M , N 分别是（)。
A .0,1 B 1,0 C .1,2 D.2,0
(11）在段页式分配中， CPU 每次从内存中取一次数据需要（）次访问内存
A . 1 B .2 C .3 D .4
(12）在请求分页系统中，页面分配策略与页面置换策略不能组合使用的是（）
A.可变分配，全局置换 B.可变分配，局部置换
C. 固定分配，全局置换 D .固定分配，局部置换

(13）设置当前工作目录的主要目的是()。
A 节省外存空间
B 节省内存空间
C 加快文件检索速度
D 加快文件读／写速度
(14）在磁盘上，最容易导致存储碎片发生的物理文件结构是（)
A 隐式链接 B 顺序存放 C 索引存放 D 显式连接
二、填空题（14 分）
1 为实现 cpu 和设备并行，操作系统引入中断和（）硬件机制
2 有一进程进入时间为 9:15 分，上处理机时间为 12:15 分，要求服务时间为 1 小时，请问该
进程的响应比为（）
3 操作系统的基本特征是并发、共享、虚拟、（）
4 虚拟存储用到了程序的（）原理
5 对记录式文件，操作系统为用户存取文件信息的最小单位是（）
6 将逻辑转换为物理地址称为（）
7略
三、简答题（14 分）
1、请说明设备驱动程序的功能？(4 分）
2、请简述虚拟内存特征？(4 分)
3、请写出进程的特征、三种基本状态以及状态转化图并标出引起转换的事件（6 分）
四、代码和综合分析（28 分）
1.银行家算法（12 分）
设系统中有 3 种类型的资源(A、B、C)和 5 个进程 P1、P2、P3、P4、P5，A 资源的数量为
17，B 资源的数量为 5，C 资源的数量为 20。在 T0 时刻，系统状态见下表。系统采用银行
家算法实现死锁避免。

(1)T0 时刻是否为安全状态？若是，请给出安全序列。
(2)若进程 P4 请求资源(2，0，1)，是否能实施资源分配为什么？
(3)在(2)的基础上，若进程 P1 请求资源(0，2，0)，是否能实施资源分配？
2. 读者写者问题的写者优先算法 : 1）共享读; 2）互斥写、读写互斥; 3）写者优先于读者
（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）
3、已知 32 位实地址，采用 48 位虚拟地址，页面大小 4KB，页表项大小 8B，每段的最大长
度 4GB(6 分）
(1）假设系统使用纯页式存储，页面偏移量为多少？采用几级分页？
(2）假设系统采用一级页表，TLB 命中率为 98%, TLB 访问时间为 10ns，内存访问时间为 100ns,
并假设当 TLB 访问失败后才开始访问内存，问平均页面访问时间是多少？如果是二级页表
呢？
(3）如果采用段页式存储，则每用户最多可以有多少个段？段内采用几级页表？