广东工业大学年《计算机软件技术基础》期末试题及答案

1、一、填空题 （每空1分，共20分，）1在同一问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用 和 两种方法来分析算法的工作量。2. 在一个长度为n的顺序存储的线性表中，向第i个元素（1in+1）位置插入一个新元素时，需要从后向前依次后移 个元素。3. 在一个单向链表中，若要在P所指向的结点之后插入一个新结点，则需要相应修改原链表的 个指针域的值。4. 操作系统的功能是进行处理机管理、 管理、 管理、设备管理和文件管理。5. 在链式存储方式中，每个结点由两部分组成： 和 。6. 二叉树每一个结点最多有 棵子树，非空二叉树只有 个根结点。7. 一个进程的活动情况至少可以划分为

2、3种基本状态： 、 和 。8. 在关系模型中，把数据看成一个二维表，表中的每一列称为 ，相当于记录中的一个数据项；每一行称为 ，相当于记录值。9. 软件定义期包括3个阶段： 、 和 。10.系统设计的质量主要反映在模块的独立性上。按照模块之间耦合程度从强到弱的顺序，可以将模块的耦合分为5级，其中最强的耦合是 ，最弱的耦合是 。二、问答题 （每题8分，共40分）1 如何提高Hash表的查找效率？简要说明线性Hash表、随机Hash表和溢出Hash表的适用对象及其优缺点？ 2分时系统与实时系统的主要区别是什么？3什么是数据字典？数据字典和数据流图的关系是什么？数据字典包括哪些内容？4什么是地址重定

3、位？为什么要对程序进行重定位？5关系模型和格式化模型比较有哪些主要优点？ 三、应用题 （第1题10分，第2、3题各15分，共40分）将关键字元素序列（09,12,04,16,19,31,20,45,01,11,25,26）依次填入长度为n=12的线性Hash表中，并指出各个关键字元素在填入过程中的冲突次数。设Hash码为i=mod(k*0.618, n)。将表达式 QUOTE f(a*b+c/d,x/y,s-t,w*v) f(a*(b+c/d),x/y,s-t,w*v)用表达式树表示，再分别转化成二叉树，最后写出其波兰表达式。（15分）用冒泡排序对线性表（81,52,57,22,95,04,8

4、3,96,42,32,48,78,14,87,67）进行排序，要求按照步骤给出中间每一步的结果和最后结果。（15分）答案页一、填空题 （每空1分，共20分，）1平均性态(AverageBehavior)、最坏情况复杂性(Worst-CaseComplexity)(1)平均性态(AverageBehavior)所谓平均性态分析，是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。 设x是所有可能输入中的某个特定输入，P(x)是x出现的概率(即输入为x的概率)，t(x)是算法在输入为x时所执行的基本运算次数，则算法的平均性态定义为(2)最坏情况复杂性(Worst-CaseComple

5、xity)所谓最坏情况分析，是指在规模为n时，算法所执行的基本运算的最大次数。它定义为。显然，W(n)的计算要比A(n)的计算方便得多。由于w(n)实际上是给出了算法工作量的一个上界，因此，它比A(n)更具有实用价值。2. n-(i-1)在顺序表中，结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将表中位置为n ，n-1，i上的结点，依次后移到位置n+1，n，i+1上，空出第i个位置，然后在该位置上插入新结点x。仅当插入位置i=n+1时，才无须移动结点，直接将x插入表的末尾。3. 1个（即p指针指向的结点的指针域修改指向新结点。新结点指针域指向P后的结点）。4. 存储管理。 进程管理。5.

6、 指针域。 数据域。6. 两（2）。 一（1）。7. 就绪、运行、阻塞8. 属性。一元组。9. 问题定义、可行性研究、需求分析10. 内容耦合、数据耦合（1）数据耦合（2）控制耦合（3）特征耦合（4）公共耦合（5）内容耦合；二、问答题 （每题8分，共40分）1（1）简化Hash函数，降低函数运行耗时。优化Hash函数，降低映射冲突（二次冲突）。良好冲突解决方案， （2）线性Hash表优点是简单。缺点是a 、“堆聚”现象：填入过程发生冲突时，首先考虑的是下一项，因此当冲突较多时，在线性Hash表中就产生“堆聚”。b、二次冲突：在线性Hash表的填入过程中，处理冲突时会产生二次冲突。c、装填因子影

7、响查找效率。平均查找次数为：（2-）/(2-2)。适用小型表。 （3）随机Hash表：发生冲突时，表项序号改变不是采用加1取模的方法，而是用某种伪随机数来改变 优点是简单、且冲突减少。缺点：计算耗时增多、冲突仍较多。适宜中小表。 （4）溢出Hash表：将冲突的元素安排在另外的空间，而不占用Hash表本身的空间，就不会产生冲突。优点是简单、且冲突减少。缺点：需要额外的溢出空间。适宜大型表。 2 分时系统按相等的时间片调度进程轮流运行，通用性强，交互性强，及时响应性要求一般（通常数量级为秒）；有调度程序自动计算进程的优先级，而非用户控制优先级。不能实时响应外部异常事件。适于科学计算、信息查询等。实

8、时系统往往是专用的，系统与应用很难分离，常常紧密结合在一起，实时系统并不强调资源利用率，而更关心及时响应性（通常数量级为毫秒或微秒）、可靠性等。与分时系统相比，实时系统要求有更高的可靠性和更严格的及时性。限定时间完成监控功能和响应外部异常。适于：过程控制、数据采集、通信、多媒体信息处理等。3 所谓数据字典，是数据流程图的基础上，进一步定义和描述所有数据的工具，包括对一切动态数据（数据流）和静态数据（数据存储）的数据结构和相互关系的说明，是数据分析和数据管理的重要工具，是系统设计阶段进行数据库（文件）设计的参考依据。数据字典（Data dictionary）是一种用户可以访问的记录数据库和应用程

9、序源数据的目录。数据字典的作用是给 HYPERLINK /view/228931.htm t _blank 数据流图上每个成分加以定义和说明。换句话说， HYPERLINK /view/228931.htm t _blank 数据流图上所有的成分的定义和解释的文字集合就是数据字典，数据流图是描述各个子块之间如何进行数据传递：数据字典相当于数据库中的对照表。数据字典的内容主要是对数据流程图中的数据项、数据结构、数据流、处理逻辑、数据存储和外部实体等六个方面进行具体的定义。数据流程图配以数据字典，就可以从图形和文字两个方面对系统的逻辑模型进行完整的描述4地址重定位就是把程序中相对地址变换为绝对地址

10、。有静态重定位和动态重定位两种重定位技术。便于编程、便于多道程序装入内存运行、便于模块化、程序不连续的存放（段页式管理）、数据和查询分开。5关系模型较之格式化模型(网状模型和层次模型)有以下方面的优点：数据结构比较简单、具有很高的数据独立性、可以直接处理多对多的联系、以及有坚实的理论基础。三、应用题 （第1题10分，第2、3题各15分，共40分）将关键字元素序列（09,12,04,16,19,31,20,45,01,11,25,26）依次填入长度为n=12的线性Hash表中，并指出各个关键字元素在填入过程中的冲突次数。设Hash码为i=mod(k*0.618, n)。表项序号123456789101112关键字010425264509111231161920冲突次数0001021将表达式 QUOTE f(a*b+c