2017年重庆交通大学数据结构(同等学力加试)复试实战预测五套卷
● 摘要
一、应用题
1． 线性表有两种存储结构：一是顺序表，二是链表。试问：
（1）如果有，2个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构? 为什么？
（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构? 为什么？
【答案】（1）应选择链式存储结构。因为它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O （1）。
（2）应选择顺序存储结构。因为顺序表可以随机存取，时间复杂度为O （1）。
2． 设将n （n ＞l ）个整数存放到一维数组R 中。试设计一个在时间和空间两方面都尽可能高效的算法，将R 中存有的序列循环左移P （0＜P ＜n ）个位置，即将R 中的数据由
变换为
（1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或
或JA V A 语言描述算法，关键之处给出注释。
原地逆置，
得到
（3）说明你所设计算法的时间复杂度和空间复杂度。 【答案】（1）算法的基本设计思想：先将n
个数据由然后再将数组R 中的前
，
（2）用C 语言算法描述如下：
（3）说明算法的复杂性：上述算法中3个Reverse 函数的的时间复杂度分别为
第 2 页，共 36 页
要求：
个数和后P 个数分别原地逆置，
最终得到结果
为O 故算法的时间复杂度为，算法的空间复杂度为0（1）。
3． 某请求分页系统的局部页面置换策略如下：系统从0时刻开始扫描，每隔5个时间单位扫描，本轮没有被访问过的页框将被系统回收，并放入到空闲页框链一轮驻留集（扫描时间忽略不计）
尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程
（1）访问（2）访问（3）访问【答案】
（1）页框号为21。因为起始驻留集为空，而0页对应的页框为空闲链表中的第三个空闲页框，其对应的页框号为21。
（2）页框号为32。理由：因11>10故发生第三轮扫描，页号为1、3的页框32、15在第二轮已处于空闲页框链表中，此刻1页又被重新访问，因此应被重新放回到驻留集中。其页框号为32。
（3）页框号为41。理由：因为第2页从来没有被访问过，它不在驻留集中，因此从空闲页框链表中取出链表头的页框41，页框号为41。
（4）适合。理由：如果程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该策略的优势越明显。
4． 如果输入序列为123456, 试问能否通过栈结构得到以下两个序列：435612和135426; 请说明为什么不能或如何才能得到。
【答案】输入序列为123456, 不能得出435612, 其理由是，输出序列最后两元素是12, 前面4个元素（4356）得到后，栈中元素剩12, 且2在栈顶，栈底元素1不可能在栈顶元素2之前出栈。得到135426的过程如下：1入栈并出栈，得到部分输出序列1; 然后2和3入找，3出栈，部分输出序列变为13; 接着4和5入栈，5、4和2依次出栈，部分输出序列变为13542; 最后6入栈并出栈，得到最终结果135426。
5． 某博物馆最多可容纳500人同时参观，有一个出入口，该出入口一次仅允许个通过。参观者的活动描述如下：
参观者进程i :
第 3 页，共 36 页
P 依次访问的<虚拟页号，访问时刻>是
：
请回答下列问题。
时，对应的页框号是什么？
时，对应的页框号是什么? 说明理由。 . 时，对应的页框号是什么? 说明理由。
（4）该策略是否适合于时间局部性好的程序? 说明理由。
进门；
参观;
出门；
coend
请添加必要的信号量和P 、
V 的互斥与同步。
要求写出完整的过程，说明信号量含义并赋初值。 【答案】 定义两个信号量
博物馆可以容纳的最多人数
用于出入口资源的控制
参观者进程i :
进门；
6． 在某程序中，有两个栈共享一个一维数组空间的栈底。
（1）对栈1、栈2, 试分别写出（元素x ）入栈的主要语句和出栈的主要语句。 （2）对栈1、栈2, 试分别写出栈满、栈空的条件。 【答案】（1）入栈主要语句
出栈主要语句
分别是两个栈
操作，以实现上述操作过程中
（2）
第 4 页，共 36 页