北京工业大学软件工程模拟试卷二.pdf
第一部分:数据结构一、填空题(每题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请给出缺页的次数和缺页率。