2005上半年软件技术基础试卷A（带答案）

一、填空题（每空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 页

虚拟存储器的功能由（C）完成。 A、B：（1）页失效；（2）1E5C；（3）2A5C；（4）165C；（5）125C C：（1）硬件；（2）软件；（3）软硬件结合

1）在需求分析阶段，开发人员需要从用户那里获得的最重要的信息是_______。

A．用户要让软件做什么 B．用户能够接受的开发周期 C．用户能够接受的开发费用

D．用户要让软件具有各种结构

2）在度量模块独立程度时，用 衡量不同模块间互相依赖的紧密程度 。 A、耦合 B、内聚 C、信息隐藏 D、局部化

3）在度量模块独立程度时，用 衡量一个模块内部个元素彼此结合的紧密程度。

A、耦合 B、内聚 C、信息隐藏 D、局部化 4）软件开发的结构化分析(SA)方法，常用的描述软件功能需求的工具是_______。

A、系统流程图、程序编码 B、软件流程图、模块说明

C、数据流程图、数据字典 D、业务流程图、处理说明

5) 软件设计分为总体(概要)设计和详细设计两个阶段,下列哪一项是总体设计中的任务？ A) 设计软件结构 B) 制定测试计划C) 设计测试用例 D) 设计算法和数据结构

１）ER 模型可以转换成关系模型。当两个实体间联系是 M:N 联系时,它通常可转换成 个关系模式。

A.2 B.3 C.M+N D.M*N

2)三个模式之间存在下列映射关系，将正确的是 。

A．外模式/内模式 B．外模式/模式 C．模式/模式 D．内模式/外模式 3）已知三个关系：

学生（学号，姓名，性别）

课程（课程编号，课程名称，学时） 成绩（学号，课程编号，分数） 若要列出选修课程名称为“ DB ”，且分数低于 60 的学生姓名和分数，则应使用的关系代数运算有 。

A. 选择、投影、自然连接 B. 选择、投影 C. 选择、自然连接 D. 投影、自然连接

4）若关系模式R的所有候选码均为单个属性，则R最高必达到 。A．1NF B．2NF C．3NF D．4NF 5） 在数据库逻辑设计中,当将E-R图转换为关系模式时,下面的做法哪一个是不正确的?

A) 一个实体类型转换为一个关系模式 B) 一个联系类型转换为一个关系模式

C) 由实体类型转换成的关系模式的主键是该实体类型的主键

D) 由联系类型转换成的关系模式的属性是与该联系类型相关的诸实体类型的属

性的全体

第 6 页 共 10 页

6）在已知教学环境中，一名学生可以选择多门课程，一门课程可以被多名学生选择，这说明学生记录型与课程记录型之间的联系是 。 A）一对一 B）多对多 C）一对多 D）未知 三、判断

1．处理死锁的四种方法中，预防策略是不容许死锁的出现的，而其他三种方法都是容许的。为了预防死锁，系统必须至少产生死锁的四个必要条件之一不成立，例如银行家算法就是预防死锁最有代表性的一个算法。

2、文件的外存分配方式有连续分配、链接分配和索引分配；其中链接结构可以提高文件存储空间的利用率，但不适合文件的随机存取；对物理文件来说，顺序文件必须采用连续分配方式，而链接文件和索引文件可以采用离散分配方式。

3．进程处于就绪状态，是指它正等待着某个事件的发生，这时，即使给它CPU控制权，它也无法执行。

4、若无进程处于运行状态，则就绪队列和等待队列均为空。（ ） 5、银行家算法是防止死锁发生的方法之一。（ ）

6、SPOOLing系统实现设备管理的虚拟技术，即：将独占设备改造为共享设备。它由专门负责I/O的常驻内存的进程以及输入、输出井组成。（ ）

7、虚拟设备是指允许用户程序不必全部装入内存就可以使用系统中的设备。（ ） 8、对顺序文件进行检索时，首先从FCB中读出文件的第一个盘块号；而对索引文件进行检索时，应先从FCB中读出文件索引表的起始地址。（ ）

1）白盒测试时，既要考虑程序的内部逻辑结构又要考虑其外部特性。（ 错 ） 2）软件开发的主要任务是写程序。（ 错 ） 3）测试只能证明程序有错误,不能证明程序没有错误。（ 对 ） 4）软件维护就是改正软件中的错误。（ 错 ）

四、简答

1、一页式系统中，页面的大小为1KB。现有一长度为4KB的用户程序，其4个页面分别被分配在内存的10，14，15和18块中。当程序中的访问地址为2058时，其物理地址是多少？

2、采用可变分区管理存储空间时，若主存中按地址顺序依次有五个空闲区，大小分别为15K、28K、10K、226K、110K。现有五个作业J1到J5，它们所需的主存空间依次是10K、15K、102K、26K、180K。问如果采用首次适应分配算法，能否把这五个作业按J1到J5的次序全部装入主存。使用哪种分配算法装入这五个作业，可使主存的利用率最高？ 3、某采用页式存储管理的系统，接收了一个共7页的作业，作业执行时依次访问的页为：1、2、3、4、2、1、5、6、2、1、2、3、7。当内存块数量为4时，请分别用先进先出（FIFO）调度算法和最近最少使用（LRU）调度算法，计算作业执行过程中会产生多少次缺页中断？写出依次产生缺页中断后应淘汰的页。（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断。要求写出计算过程）

三、应用题（共8题，建议分数为45分）

1、设用于通信的电文由8个字母{Q、T、Z、A、S、W、E、C}组成，各字母在电文中出现的频率依次为0.07、0.19、0.02、0.06、0.32、0.03、0.21、0.10，请为这8个字母设计哈夫曼编码，并画出建立的哈夫曼树（要求左节点小于右节点）。（8分）。

第 7 页 共 10 页

参考答案： 每个字母的哈夫曼编码为： 1.00 0 1 Q：1010

T：00

0.400.60 Z：10000 0 1 1 A：1001 0 S：11

0.320.280.190.21 W：10001 1 E：01 0 S T E C：1011 0.170.11

0 1 00 1 0.050.060.070.10 0 1

A Q C 0.020.03

Z W 2、定义栈的数据结构为const int maxlen=20; struct seqstack { elemtype stack[maxlen]; int top; };

其中elemtype为入栈元素的数据类型。请你分别用push和pop作为函数名写出进栈和出栈算法（7分）。

参考答案： //入栈

void push(seqstack &s, elemtype x) {

if (s.top == maxlen - 1)

cout<<\ else { s.top++; s.stack[s.top] = x; } }

//出栈

void pop(seqstack &s, elemtype &x) {

if (s.top == 0)

cout<<\ else { x = s.stack[s.top];

1 第 8 页 共 10 页

s.top--; } }

3、一个AOE网络如下，计算完成整个工程至少所需时间，求出关键路径，并计算每个事件的最早开始时间和最迟开始时间（8分）。 a4=3V5 V2 a8=1 a1=3 a3=2 a7=2V1V4 V6 a5=4参考答案：a2=2 Vl (i) 顶点 a6=3V3Ve (i) 0 0 3 2 6 6 8 4 2 6 7 8 关键路径：（V1,V3,V4,V6） 完成整个工程至少所需时间：8天

4、把下列二叉树构造成大根堆，并写出第一趟排序的结果（7分）。

46

55 13

05 17 42 94

70

参考答案：

94

70 17

05 13 46 55

42

6 第 9 页 共 10 页

第一趟排序结果：42，70，17，46，55，05，13，94

5、已知矩阵

?0 2 0 0 4??6 0 8 0 0???，现对该矩阵进行转置（下标从1开始）（8分）。 ?0 10 0 0 0????12 0 0 0 0?（1） 写出其转置前、后的三元组表 （2） 写出NUM向量内容。

（3） 写出POT向量在算法开始前的内容和算法完成后的内容。

参考答案：

（1） 转置前三元组表 转置后三元组表 1 2 2 1 2 6 1 5 4 1 4 12 2 1 6 2 1 2 2 3 8 2 3 10 3 2 10 3 2 8 4 1 12 5 1 4 （2） NUM向量

2 2 1 0 1

（3）POT向量

算法开始前POT向量 算法完成后POT向量 1

3 5 6 6 3 5 6 6 7

第 10 页 共 10 页

本文来源：https://www.bwwdw.com/article/vmb3.html