中南大学考试试卷
2012 -- 2013 学年上学期时间110分钟
计算机软件技术基础课程32 学时2 学分考试形式：开卷
专业年级：自动化、电气、测控10总分100分，占总评成绩70 % 注：此页不作答题纸，请将答案写在答题纸上，答题时请在答题纸上表明题号
一、填空题（每空1分，共20分，）
1．在同一问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用
和两种方法来分析算法的工作量。
2. 在一个长度为n的顺序存储的线性表中，向第i个元素（1<i<n+1）位置插入一个新元素时，
需要从后向前依次后移个元素。
3. 在一个单向链表中，若要在P所指向的结点之后插入一个新结点，则需要相应修改原链表
的个指针域的值。
4. 操作系统的功能是进行处理机管理、管理、管理、设备管理和文件管理。
5. 在链式存储方式中，每个结点由两部分组成：和。
6. 二叉树每一个结点最多有棵子树，非空二叉树只有个根结点。
7. 一个进程的活动情况至少可以划分为3种基本状态：、和。
8. 在关系模型中，把数据看成一个二维表，表中的每一列称为，相当于记录中
的一个数据项；每一行称为，相当于记录值。
9. 软件定义期包括3个阶段：、和。
10.系统设计的质量主要反映在模块的独立性上。
按照模块之间耦合程度从强到弱的顺序，可
以将模块的耦合分为5级，其中最强的耦合是，最弱的耦合是。
二、问答题（每题8分，共40分）
1．如何提高Hash表的查找效率？简要说明线性Hash表、随机Hash表和溢出Hash表的适用对象及其优缺点？
2．分时系统与实时系统的主要区别是什么？
3．什么是数据字典？数据字典和数据流图的关系是什么？数据字典包括哪些内容？
4．什么是地址重定位？为什么要对程序进行重定位？
5．关系模型和格式化模型比较有哪些主要优点？
三、应用题（第1题10分，第2、3题各15分，共40分）
1.将关键字元素序列（09,12,04,16,19,31,20,45,01,11,25,26）依次填入长度为n=12的线性Hash
表中，并指出各个关键字元素在填入过程中的冲突次数。
设Hash码为i=mod(k*0.618, n)。
2.将表达式f(a*(b+c/d),x/y,s-t,w*v)用表达式树表示，再分别转化成二叉树，最后写出其波兰
表达式。
（15分）
3.用冒泡排序对线性表（81,52,57,22,95,04,83,96,42,32,48,78,14,87,67）进行排序，要求按照
步骤给出中间每一步的结果和最后结果。
（15分）
答案页
一、填空题（每空1分，共20分，）
1．平均性态(Average Behavior)、最坏情况复杂性(Worst-Case Complexity)
(1)平均性态(Average Behavior) 所谓平均性态分析，是指用各种特定输入下的基本运算
次数的加权平均值来度量算法的工作量。
设x是所有可能输入中的某个特定输入，P(x)
是x出现的概率(即输入为x的概率)，t(x)是算法在输入为x时所执行的基本运算次数，
则算法的平均性态定义为
(2)最坏情况复杂性(W orst-Case Complexity) 所谓最坏情况分析，是指在规模为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. 两（2）。
一（1）。
7. 就绪、运行、阻塞
8. 属性。
一元组。
9. 问题定义、可行性研究、需求分析
10. 内容耦合、数据耦合
（1）数据耦合（2）控制耦合（3）特征耦合（4）公共耦合（5）内容耦合；
二、问答题（每题8分，共40分）
1．（1）简化Hash函数，降低函数运行耗时。
优化Hash函数，降低映射冲突（二次冲突）。
良好冲突解决方案，
（2）线性Hash表
优点是简单。
缺点是a 、“堆聚”现象：填入过程发生冲突时，首先考虑的是下一项，因此当冲突较多时，在线性Hash表中就产生“堆聚”。
b、二次冲突：在线性Hash表的填入过程中，处理冲突时会产生二次冲突。
c、装填因子影响查找效率。
平均查找次数为：（2-α）/(2-2α)。
适用小型表。
（3）随机Hash表：
发生冲突时，表项序号改变不是采用加1取模的方法，而是用某种伪随机数来改变
优点是简单、且冲突减少。
缺点：计算耗时增多、冲突仍较多。
适宜中小表。
（4）溢出Hash表：
将冲突的元素安排在另外的空间，而不占用Hash表本身的空间，就不会产生冲突。
优点是简单、且冲突减少。
缺点：需要额外的溢出空间。
适宜大型表。
2 分时系统按相等的时间片调度进程轮流运行，通用性强，交互性强，及时响应性要求一
般（通常数量级为秒）；有调度程序自动计算进程的优先级，而非用户控制优先级。
不能实时响应外部异常事件。
适于科学计算、信息查询等。
实时系统往往是专用的，系统与应用很难分离，常常紧密结合在一起，实时系统并不强调资源利用率，而更关心及时响应性（通常数量级为毫秒或微秒）、可靠性等。
与分时系统相比，实时系统要求有更高的可靠性和更严格的及时性。
限定时间完成监控功能和响应外部异常。
适于：过程控制、数据采集、通信、多媒体信息处理等。
3．所谓数据字典，是数据流程图的基础上，进一步定义和描述所有数据的工具，包括对一切动态数据（数据流）和静态数据（数据存储）的数据结构和相互关系的说明，是数据分析和数据管理的重要工具，是系统设计阶段进行数据库（文件）设计的参考依据。
数据字典（Data dictionary）是一种用户可以访问的记录数据库和应用程序源数据的目录。
数据字典的作用是给数据流图上每个成分加以定义和说明。
换句话说，数据流图上所有的
成分的定义和解释的文字集合就是数据字典，数据流图是描述各个子块之间如何进行数据传递：数据字典相当于数据库中的对照表。
数据字典的内容主要是对数据流程图中的数据项、数据结构、数据流、处理逻辑、数据存储和外部实体等六个方面进行具体的定义。
数据流程图配以数据字典，就可以从图形和文字两个方面对系统的逻辑模型进行完整的描述
4．地址重定位就是把程序中相对地址变换为绝对地址。
有静态重定位和动态重定位两种重定位技术。
便于编程、便于多道程序装入内存运行、便于模块化、程序不连续的存放（段页式管理）、数据和查询分开。
5．关系模型较之格式化模型(网状模型和层次模型)有以下方面的优点：数据结构比较简单、具有很高的数据独立性、可以直接处理多对多的联系、以及有坚实的理论基础。
三、应用题（第1题10分，第2、3题各15分，共40分）
1.将关键字元素序列（09,12,04,16,19,31,20,45,01,11,25,26）依次填入长度为n=12的线性Hash
表中，并指出各个关键字元素在填入过程中的冲突次数。
设Hash码为i=mod(k*0.618, n)。
2.将表达式f(a*(b+c/d),x/y,s-t,w*v)用表达式树表示，再分别转化成二叉树，最后写出其波兰
表达式。
（15分）
3.用冒泡排序对线性表（81,52,57,22,95,04,83,96,42,32,48,78,14,87,67）进行排序，要求按照
步骤给出中间每一步的结果和最后结果。
（15分）。
