第一部分：数据结构一、填空题（每题2分，共20分）1、一个循环队列Q的存储空间大小为M,其队头和队尾指针分别为front和rear，则循环队列中元素的个数为：。2、两个串相等的充分必要条件是两个串的长度相等且。3、一个连通图的生成树是一个，它包含图中所有顶点，但只有足以构成一棵树的n-1条边。4、一个图的表示法是惟一的。5、已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半查找90时，需进行次查找可确定成功。6、在线性结构中，第一个结点前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点后续结点，其余每个结点有且只有1个后续结点。7、一棵具有个结点的完全二叉树，它的深度为。8、n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为；若采 用邻接表存储时，该算法的时间复杂度为。9、线性表若采用链式存储结构时，要求内存中可用存储单元的地址:10、一个具有n个顶点的有向图最多有条边。二、判断题（每题2分，共20分）（）1、算法独立于具体的程序设计语言，与具体的计算机无关。（）2、线性表采用链式存储时，结点内部的存储空间可以是不连续的。（）3、栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（）4、哈夫曼树的结点总个数一定是偶数。（）5、已知二叉树的先序遍历序列和中序遍历序列，可以画出这棵二叉树。（）6、有e条边的无向图，在其对应的邻接表中有e个结点。（）7、连通分量指的是无向图的极大连通子图。（）8、在哈希表的查找过程中的“比较”操作是无法避免的。（）9、完全二叉树肯定是平衡二叉树。（）10、堆排序是稳定的排序算法。 三、（10分）试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？四、（10分）写出下图中全部可能的拓扑排序序列。五、（10分）已知图G如下，根据克鲁斯卡尔算法求图G的一棵最小生成树。（要求给出构造过程） 六、（10分）设散列表容量为7（散列地址空间0.6），给定表（30，36，47，52，34）,散列函数H（K）=Kmod6，采用线性探测法解决冲突，要求：（1）构造散列表；（2）求查找数34需要比较的次数。七、（20分）二路插入排序是将待排关键字序列r1.n中关键字分二路分别按序插入到辅助向量d1.n前半部和后半部（注:向量d可视为循环表），其原则为，先将rl赋给d1，再从r2记录开始分二路插入。编写实现二路插入排序算法。第二部分：操作系统一、单项选择题（在每小题的四个备选答案中，只有一个是正确的，将其号码写在题干的括号中。每小题2分，共20分）1可能出现抖动的存储管理方式是（） A固定式分区分配B动态分区分配C动态重定位分区分配D请求分页存储管理2批处理系统的主要缺点是（）A输入输出设备利用率低B失去了多道性C无交互性D需要人工干预3进程间的同步是指进程间在逻辑上的相互（）关系A制约B联接C调用D合作4SPOOLING技术的实质是（）A以空间换取时间B将独享设备改造为共享设备C虚拟设备D在进程和进程之间切换设备5我们称磁盘是共享设备，是因为（）A磁盘空间可以让多个用户共享B磁盘可支持SPOOLING技术C多个用户对磁盘的访问可同时进行D一台磁盘机可有很多盘片6提出以下哪一种是不可能的进程状态变化（）A阻塞就绪B执行阻塞C执行就绪D阻塞执行7某页式管理系统中，地址寄存器的低10位表示页内地址，则页面大小为（） A、1024字节B、1024K C、512字节D、512K8资源采用按序分配能达到（）的目的。A、避免死锁B、解除死锁C、防止死锁D、检测死锁9将文件加密不是为了防止（）A文件被他人修改B文件被他人阅读C文件被他人执行D文件被他人复制10建立多级目录（）A便于文件的保护B便于关闭文件C解决文件的重名与共享D便于提高系统的效率一、名词解释（每小题3分，共15分）1、抖动：2、内核：3、临界资源： 4、进程：5、共享设备： 二、判断改错题（判断正误，并改正错误，每小题2分，共20分）1、分时系统具有交互性，而实时系统无交互性。（）2、若用信号量作为同步工具，多个P和V顺序不当，也会产生死锁。（）3、在存储管理技术中，固定式分区分配产生“外零头”，而可变式分区分配方式产生“外零头”（）4、当进程已分配到除CPU以外的所有必要资源时，便处于阻塞状态。（）5、操作系统的任务之一就是提高系统的软硬件资源。（）6、死锁定理是用于预防死锁，破坏死锁条件。（）7、动态重定位的地址变换是在装入时一次完成的，以后不再改变。（）8、分页请求系统的置换以段为单位。（）9、访问控制表是以一个用户建立的。（）10、系统调用在本质上是一种过程调用，但它是一种特殊的过程调用。（）三、简答题（每小题5分，共25分） 1操作系统的目标是什么？2程序链接的方法有哪几种，请分别作简要阐述。3什么叫虚拟存储器？实现方式有哪些？4简述引起进程调度的原因。5操作系统的基本特征是什么？四、综合应用题（每小题10分，共20分）1在采用分页存贮管理系统中，地址结构长度为18位，其中11至17位表示页号，0至10位表示页内位移量。若有一作业依次被放入2、3、7号物理块中，相对地址1500处有一条指令store1,2500。请问： （1）主存容量最大可为多少K？分为多少块？每块有多大？（2）上述指令和存数地址分别在几号页内？对应的物理地址又分别为多少？2在一个请求式存储管理系统中，采用FIFO页面置换算法，假设一进程分配了4个页框，按下面页面进行：1、8、1、7、8、2、7、6、5、8、3、6请给出缺页的次数和缺页率。