专业名称：计算机应用技术、计算机软件以理论考试科目：数据结构与操作系统（B）卷一．数据结构部分注意：算法可以用类C、类C++、类JAVA或类PASCAL任一语言编写，并有类型说明。1、（15分）名词解释（1）堆栈（2）最小生成数（3）折半（二分）查找（4）堆排序（5）连通分量2、(15分)双端队列是限定插入和删除操作在表的两端进行的线性表。假设依次输入数据元素为1、2、3、4、5和6，试问通过使用（a）队列；（b）双端队列，能否得到下列输出序列？（1）123456（2）243651（3）152436（4）421356（5）126453（6）5263413、（15分）试设计一个算法，将二叉树中的叶子结点按从左到右的顺序放入一个线性表。假设二叉树采用二叉链表存储结构，线性表采用动态分配顺序存储结构。4、（15分）子串的定位操作index(s,t)通常称为串的模式匹配（其中t称为模式），试编写一个模式匹配算法，匹配过程为：先匹配模式的首尾字符，若匹配成功，调用函数substr（取子串）求检查模式的首尾之间的字符是否与目标的相应字符相匹配，若匹配不成功，则进行下一次匹配。5、（15分）请采用递归方式对一单链表进行归并排序。假设单链表中每个元素皆为整数，试设计算法完成次操作。二、操作系统部分6、（15分）请判断以下说法是否正确，并说明理由。（1）在单CPU的计算机系统中，进程是不能并行操作的。（2）在死锁发生后，参与死锁的所有进程都占有资源。（3）存储管理中的请求式分页系统必定需要重定位机制的支持。7、（15分）请解释以下的概念：（1）中断（2）虚拟设备（3）中级调度（4）Cache（5）LRU算法8、（15分）在虚拟存储技术中，系统将进行进程运行时所缺的页面调入内存的时机有预调页策略和请求式调页策略两种。请说明这两种策略的原理，并结合具体的实例比较这两种策略的优劣。9、（15分）有一个数据采集和处理系统，出3个负责采集数据的设备，一个缓冲区和2个数据处理程序组成。其工作原理如下：（1）每个采集数据的设备分别由一个进程控制，标记为D1、，D2和D3，并且每次采集到的数据大小固定为K。（2）缓冲区的大小为2*K（可以存放采集到的2份数据）。（3）两个数据处理程序运行后，演变为进程P1和P2。（4）仅当缓冲区中有D1和D2采集到的各一份数据时，P1取出这两份数据并处理。（5）仅当缓冲区中有D1和D3采集到的各一份数据时，P2取出这两份数据并处理。请用信号量机制实现以上5个进程的同步，并保证系统不会发生死锁。10、（15分）有一批数据，共有32000条记...
