中南大学考试试卷
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分)。