1、 试题科目代码:823科目名称:数据结构+操作系统注意：答案必须全部写在考点提供的答题纸上，写在试题上无效；答案要标注题号，答题纸要填写姓名和考号，并标注页码与总页数；交卷时，将答题纸与试题一起装入原试卷袋，用我校提供的密封条密封并签名。Part ：数据结构部分一、 单选题（每小题2分，共10小题，合计20分）1.判定一个队列QU（最多元素为m0）为满队列的条件是（A）QU-rear QU-front = = m0 （B）QU-rear QU-front 1= = m0 （C）QU-front = = QU-rear （D）QU-front = = QU-rear+12. 链表是一种采用（ ）
2、存储结构存储的线性表（A）顺序 （B）链式 （C）星式 （D）网状3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（A）必须是连续的 （B）部分地址必须是连续的（C）一定是不连续的 （D）连续或不连续都可以4 线性表在（ ）情况下适用于使用链式结构实现。（A）需经常修改中的结点值 （B）需不断对进行删除插入 （C）中含有大量的结点 （D）中结点结构复杂5. 若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为（ ） （A）i （B）n=i （C）n-i+1 （D）不确定6.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除
3、第一个元素， 则最节 省运算时间的存储方式是（ ）（A) 单链表 （B）双链表 （C）仅有头指针的单循环链表（D） 仅有尾指针的单循环链表7. 树中所有结点的度之和等于所有结点数（ ）（A) 加0 （B）加1 （C）减1 （D）加n8 在一棵具有 n 个结点的二叉链表中，所有结点的空域个数等于（ ）（A) n （B） n-1 （C） n+1 （D）2n9. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）（A） 空或只有一个结点 （B） 任一结点无左孩子（C） 高度等于其节点数 （D） 任一结点无右孩子 10.有 10 个结点的二叉树中，度为 0 的结点数为4，则度为2 的结点数为
4、（ ）。（A）3 （B）4 （C）5 （D）6二、 算法应用题（每小题10分，共3小题，合计30分）1、已知散列函数为H(key)=key%7，散列表长度为7(散列地址空间为0.6)，待散列序列为：(25，48，32，50，68)。要求：(1)根据以上条件构造一散列表，并用线性探测法解决有关地址冲突；(2)若要用该散列表查找元素68，给出所需的比较次数。2、给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：1）归并排序， 每归并一次书写一个次序。2）快速排序， 每划分一次书写一个次序。3、已知一个表jan,feb,mar,apr,m
5、ay,june,july,aug,sep，使按表中元素的次序依次插入一棵初始为空的二叉排序树，画出表中元素构成的二叉排序树。三、算法设计题（2小题，共25分）1、已知两个链表A和B，其元素值递增排列。写出编程将A和B合并成一个递增有序（相同值只保留一个）的链表C的思想，并要求利用原表结点。（10分）2、编写算法，计算二叉树中分支节点（除叶子节点之外的节点）个数。（15分）Part ：操作系统部分一、单选题（每小题2分，共10小题，合计20分）1. 从资源管理的角度出发，将处理器执行的指令分成两类，其中的特权指令只允许_使用。 A.应用程序 B.联机用户 C.操作系统程序 D.目标程序2. 设计
6、操作系统的主要目的是_。 A.提高系统软件的运行速度 B. 提高系统资源的利用率 C.增强计算机硬件的功能 D. 提高用户软件的运行速度3. 在进程的基本状态转换中，以下状态转换不正确的是_。A.就绪运行 B. 运行就绪 C. 等待就绪 D.等待运行4. 为了使系统具有最高的吞吐率，作业调度算法应_。 A.满足所有用户 B.设计简单一些 C.在较短的时间内能够处理尽可能多的作业 D.借助于进程调度5. 对于N并发进程，设互斥信号量为S=1，则当S=0时，表示_。 A.有一个进程进入了临界区, 没有进程等待进入 B.有一个进程进入了临界区，并有多个进程等待进入 C.没有进程进入临界区 D.有不止
7、一个进程进入了临界区6. 当采用按序分配资源方法预防死锁时，它破坏了产生死锁的四个必要条件中的_。A. 循环等待条件 B. 互斥条件 C. 占有和等待 D. 不剥夺条件7. 下列存储管理方案中，_存在内部碎片问题。A可变分区管理 B. 请求分段管理 C. 页式管理 D. 段式管理8. 在操作系统中，用户在使用I/O设备时，通常不指定物理设备，而是指定逻辑设备，系统建立逻辑设备与物理设备的映射，这种设备特性称为_。A.设备虚拟性 B.设备独立性 C.设备互斥性 D.设备共享性9. 进程需要读取磁盘上的多个数据块，数据传输方式效率最高的是_。A程序直接控制方式 B中断控制方式CDMA方式 D通道方
8、式10. 以下_是操作系统中树形目录结构的优点。A.提高文件查找效率 B.节省存储空间C.减少文件的传送时间 D.存储更多的文件二、简答题（每小题5分，共3小题，合计15分）1.在操作系统中引入进程的概念后又引入了线程的概念，请解释为什么要引入线程，它与进程有何区别与联系？2.缺页是请求分页系统中的一个现象，缺页率为系统不成功访问次数与访问总次数的比率，请分析影响缺页中断率的因素有哪些？3.什么是死锁？当死锁发生时，系统会出现哪些必要条件？三、计算题（每小题10分，共3小题，合计30分）1设系统中有三种类型的资源(A、B、C)，其数量分别为(18,6,20)和5个进程P1,P2,P3,P4,P
9、5。在T0时刻系统状态如下表所示，系统采用银行家算法实现死锁避免策略。最大资源需求量（Claim）已分配资源量（Allocation）剩余资源量（Available）A B CA B CA B CP15 5 92 1 22 3 2P25 3 64 0 2P34 1 134 1 6P45 3 53 0 4P54 2 43 1 4(1)T0时刻是否为安全状态，若是，请给出安全系列。(2)在T0时刻若进程P2请求资源request2(0,3,2)，是否能实施资源分配？为什么？2.一个具有快表的页式虚拟存储管理系统，设主存访问周期为6微秒，内、外存传送一个页面的平均时间为5毫秒。如果快表的命中率为80
10、%，缺页中断率为5%，忽略快表的访问时间，分析并计算主存的有效存取时间。3.旋转型设备的优化分布能减少I/O服务的时间，设磁盘转速为3000转/分钟，磁盘格式化时每个盘面被分为8个扇区，现有一个文件共有A-H共8个逻辑记录，每个记录的大小与扇区的大小相同，每个扇区存放一条逻辑记录。处理程序每次从磁盘读出一个记录后要花5ms的时间处理该记录。忽略其他辅助时间，请回答下列问题： （1）磁盘读每个记录的时间是多少？（2）在假设已经顺序存放好这8个记录，那么读出并处理该文件需要多少时间？ （3）采用一个优化的数据存放方法，画出各个记录的存放位置，计算该方案所花费的总时间，并与（2）进行比较说明。四、编程题（10分）某理发厅有3个理发师和10个供顾客等待的座位。顾客和理发的活动过程描述如下：顾客到达理发厅时，若有空座位，则到取号机上领取一个号，等待叫号；若没有空座位，则离开。取号机每次仅允许一位顾客使用。当理发师空闲时，通过叫号选取一位顾客，并为其服务。（1）给出系统设计所用到的信号量及其初值，以及进程的数量；（2）请用PV操作和信号量给出正确的进程同步程序。第 5 页 共 5 页
