一、填空题（每空1分，共30分）
1、数据的逻辑结构可形式地用一个二元组B＝(K，R)来表示，其中K是一个 数据元素的非空有限集合，R是定义在K上的 关系的非空 的有限集。
2、线性表中的每个元素，除第一个外，都只有一个____直接前驱 ，除最后一个外，都仅有一个___直接后继__。
3、有一个二维数组A[1:m;1:n]，假设A[3，2]地址为1110，A[2，3]地址为1115，若每个单元占一个空间，则A[1，4]的地址是___1120____。
4、假设一个下三角矩阵按行优先存放，行、列编号均从1始，并设第1第1元素的的地址为addr，则位于第i行第j列的元素的地址为addr+i(i-1)/2+(j-1) (1<=j<=i<=n)。 5、设二叉树B中度为2的结点个数是n2，则B中叶子结点的个数是_n2＋1。 6、已知一棵完全二叉树中共有1000该树中共有 __500个叶子结点，有__499个度为2的结点，有___1_个结点只有非空左子树。
7、深度为h的完全二叉树至少有___2h-1___结点；至多有___2h-1___个结点。
8、由3个结点可以构造出__2___种不同形态的树，可以构造出__5__种不同形态的二叉树。
9、在用于表示有向图的邻接矩阵中, 对第I行的元素进行累加, 可得到第I 个顶点的__出__度, 而对第J列的元素进行累加, 可得到第J个顶点的___入__度。
10、 下图中，结点1的度为___3___，该树的深度是___4__，该树的路径长度为___30__。
251 63 7 8 4 10 91112?11、邻接矩阵A?1 ?010?1415?13?01?，可以看出，该图共有 _3_个顶点。如果是有向图，该图??010??2 4 5 共有_4_条弧；如果是无向图，则共有_2_条边。
12、二分查找的效率较高，但要求关键字____有序_____，并且要求表的存储为___ __顺序存储_____。
第 1 页 共 10 页
13、对序列46、55、13、42、94、5、17、70按从小到大顺序排列，若使用冒泡排序法，则第一趟排序的结果为___46、13、42、55、5、17、70、94__，若使用快速排序法，则第一趟排序的结果为_______13、5、17、42、46、94、55、70_______。
1、操作系统最基本的特征是：________________________和________________________，最重要的任务是________________________。
2、当一个进程完成了特定的任务后，系统收回这个进程所占的__________和取消该进程的__________就撤消了该进程。
3、实现SPOOL系统时必须在磁盘上开辟出称为__________和__________的专门区域，以存放作业信息和作业执行结果。
4、_________是指通过破坏死锁产生的必要条件来防止死锁的发生。引起死锁的必要条件中，_________是不应被破坏的，但对某种特殊资源（如打印机），该条件可以通过__________技术来破坏。
5、在用信号量实现对临界资源的互斥访问时，若信号量的初值是2，当前值是-1，表示有_____________个进程等待使用该资源。
6、文件的存取方法有顺序存取和______________两种。
1）软件发展第二阶段的末期，软件开发技术的进步一直未能满足发展的需要。在软件开发中遇到的问题找不到解决办法，使问题积累起来，形成了尖锐的矛盾，因而导致了 。 软件危机
2）需求分析应交付的文档主要是 、初步的用户手册 和确认测试计划。需求规格说明书
3) 数据流图是描述数据在软件中流动和被处理的过程,是软件模型的一种图示,它一般包括四种图形符号:变换/加工、外部实体、数据流和 。数据存储
1) 在关系数据模型中,二维表的列称为属性,二维表的行称为 元组 2) 在数据库的外模式、模式和内模式三级模式的体系结构中,存在两次映象: . 外模式/模式映象提供了数据的 逻辑 独立性。模式/内模式映象提供了数据的 物理
独立性。
3）一个关系框架R是3NF的是指它的 都不传递依赖它的任一候选关键字。任一非主属性
4)关系模式由2NF转化为3NF是消除了非主属性对码的_________________。传递依赖 5) 如果只对关系中的某些属性感兴趣，则可用关系代数的 运算选择这些属性。投影
6) 数据管理技术经历了人工管理、文件管理和 三个阶段。数据库 7) 设有如图所示的关系R，它满足 NF。2
教师 张艺 王武 李斯 职称 教授 讲师 副教授 津贴 800 600 700 第 2 页 共 10 页
赵柳
讲师 600
二、选择题（每空2分，共30分） 1、下列组合中属于线性表的是__D_.
A、队列、哈夫曼树 B、栈、图 C、一维数组、完全二叉树 D、二维数组、链栈
2、构造与关键字集合{48,27,35,15,42,18,87}对应的二叉排序树，如果希望二叉排序树的高度最小，应选择的输入序列是_____B____.
A、42，18，48，15，35，87，27 B、35，18，15，27，48，42，87
C、15，18，27，35，42，48，87 D、27，18，15，35，42，87，483、若进栈序列为3、5、7、9，进栈和出栈可穿插进行，则不可能的出栈序列是_ B__。 A、 7，5，3，9 B、9，5，7，3 C、 9，7，5，3 D、7，5，9，3
4、设栈s的初始状态为空，如果进栈序列为1、2、3、4、5、6，出栈序列为3、2、5、6、4、1，则s的容量至少是_ D___。 A、 6 B、4 C、 2 D、3
5、某二叉树的先序遍历序列为abdgcefh，中序遍历序列为dgbaechf，则其后序遍历序列为_ D__。
A、 bdgcefha B、gdbecfha C、 bdgaechf D、gdbehfca 6、n个叶子结点的哈夫曼树的结点总数是 C
A、 2n＋1 B、2（n＋1） C、2n－1 D、无法确定
7、如果一棵二叉树任何一个结点的值均小于其右子树上所有结点的值，而大于其左子树上所有结点的值，则要得到这棵二叉树中各结点的递增序列，对二叉树应采用的遍历方式是 A 。
A、中序遍历 B、先序遍历 C、后序遍历 D、宽度优先遍历 8、以邻接矩阵存储图G时，邻接矩阵的大小取决于 A 。 A、G中顶点的数目 B、 G中边的数目 C、G中顶点和边的数目 D、 以上都不是
9、四组含C1～C7的结点序列中，哪一种是下列有向图的拓扑序列 B 。
第 3 页 共 10 页
A C1，C2，C6，C7，C5，C4，C3 B C5，C7，C4，C1，C2，C6，C3 C C1，C4，C2，C3，C5，C6，C7
D C1，C2，C6，C3，C4，C5，C7
10、在AOE（以边为活动的网）中关键路径是指从源点到汇点___A___。 A、路径长度最长的路径 B、路径长度最短的路径
C、边数最多的路径 D、顶点数最多的路径
11、设图G为带权的有向图，以下关于最短路径的说法中正确的是__D__。 A、图G的任意两个顶点间都存在最短路径 B、图G的两个顶点间的最短路径只有一条 C、图G中任意两个顶点间都不存在最短路径 D、图G中任意两个顶点间可能有多条最短路径 12、___C___的邻接矩阵是对称的。
A、有向图 B、AOV网 C、无向图 D、AOE网
13、定义哈希表HT[13]，初始时为空，哈希函数为H(key)=key，现要将关键字12、23、45、57、20、3、31依次存放到哈希表中，假设采用线性探测再散列处理冲突，则关键字31在哈希表中的下标是__D___。
A、5 B、6 C、7 D、8
14、在一维数组中，存储了有序整数序列{2，4，7，11，14，15，17，29，34，42，58}，用对分查找法在数组中查找值12，则需要进行的关键字比较次数为__C__。 A、2 B、 3 C、4 D、5
15、有一数列：97 65 76 13 29 49 58 经过一趟排序后得到：
13 65 76 97 29 49 58 请问使用的是_____A___方法？
第 4 页 共 10 页
A、简单选择排序 B、冒泡排序 C、线性插入排序 D、快速排序
1、在计算机系统中配置操作系统的主要目的是（）。
A ：增强计算机系统的功能；B：提高系统资源的利用率；C：提高系统的运行速度；D：合理组织系统的工作流程，以提高系统吞吐量。 2、从静态看，进程是由（ ）、（ ）、（ ）三部分组成，其中（ ）是进程存在的唯一标志。 （1）JCB （2）PCB （3）FCB （4）DCB （5）程序段 （6）数据段 3、下列进程状态转换中，不可能发生的状态转换是（）；
（1）就绪→执行 （2）执行→就绪（3）就绪→阻塞（4）阻塞→就绪 （5）阻塞→执行（6）执行→阻塞
4、用信号量S实现对系统中4台打印机的互斥使用，S的初值应设置为（A），若S的当前值为-1，则表示等待S的队列中有（B）个进程等待。 A：（1）1；（2）0；（3）-1；（4）4 （5）-4 B：（1）0；（2）1；（3）2；（4）3 （5）4 5、死锁的预防是通过破坏产生死锁的四个必要条件实现的。下列方法中，（ ）破坏了“请求与保持”条件，（ ）破坏了“循环等待”条件 （1）银行家算法；（2）一次性分配策略；（3）资源的有序分配策略；（4）SPOOLing技术。
6、静态重定位是在作业的（ ）中进行的，动态重定位是在作业的（ ）中进行的。 （1）编译过程；（2）装入过程；（3） 修改过程；（4） 执行过程
7、在最佳适应算法中，要求空闲分区按照（ ）的顺序形成空闲分区链；最坏适应算法是按（）的顺序形成空闲链。 （1）空闲区起始地址递增；（2）空闲区起始地址递减；（3）空闲区大小递增；（4）空闲区大小递减；
8、在通常情况下，在下列存储管理方式中，（ ）管理最简单，但存储碎片多；（）使内存碎片尽可能少，而且使内存利用率最高。 段式；（2）页式；（3）段页式；（4）固定分区；（5）可变分区 9、虚拟存储器主要是基于（A）；实现虚拟存储器的关键技术是（B） A：（1）计算机的高速性；（2）大容量内存；（3）大容量的硬盘；（4）循环性原理；（5）局部性原理 B：（1）内存分配；（2）置换算法；（3）请求调页（段）；（4）对换空间管理
10、某虚拟存储器的用户编程空间共32个页面，每页1K，主存为16K。假定某时刻用户页表已调入主存的页面的虚页号和物理页号对照表如下：
虚页号 物理页号
0 5
1 10
2 4
3 7
则下面十六进制虚地址相对应的物理地址为（如果主存中找不到，即为页失效）：
虚地址 物理地址 0A5C （A） 1A5C （B）
第 5 页 共 10 页