20121212计算机软件基础试卷及其答案0
- 格式:pdf
- 大小:373.47 KB
- 文档页数:4
12月计算机二级MSoffice基础习题及答案选择题(1)下面不属于软件测试实施步骤的是A.集成测试B.回归测试C.确认测试D.单元测试【答案】B【解析】软件测试主要包括单元测试、集成测试、确认测试和系统测试。
(2)下列叙述中正确的是A.一个算法的空间复杂度大,则其时间复杂度也必定大B.一个算法的空间复杂度大,则其时间复杂度必定小C.一个算法的时间复杂度大,则其空间复杂度必定小D.算法的时间复杂度与空间复杂度没有直接关系【答案】D【解析】算法的空间复杂度是指算法在执行过程中所需要的内存空间,算法的时间复杂度,是指执行算法所需要的计算工作量,两者之间并没有直接关系,答案为D。
(3)下列叙述中正确的是A.算法的效率只与问题的规模有关,而与数据的存储结构无关B.算法的时间复杂度是指执行算法所需要的计算工作量C.数据的逻辑结构与存储结构是一一对应的D.算法的时间复杂度与空间复杂度一定相关【答案】B【解析】算法的效率与问题的规模和数据的.存储结构都有关,A错误。
算法的时间复杂度,是指执行算法所需要的计算工作量,B正确。
由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同,因此数据的逻辑结构和存储结构不是一一对应的,C错误。
算法的时间复杂度和空间复杂度没有直接的联系,D 错误。
(4)下列叙述中正确的是A.程序执行的效率与数据的存储结构密切相关B.程序执行的效率只取决于程序的控制结构C.程序执行的效率只取决于所处理的数据量D.以上说法均错误【答案】A【解析】程序执行的效率与数据的存储结构、数据的逻辑结构、程序的控制结构、所处理的数据量等有关。
(5)下列关于栈的叙述中,正确的是A.栈底元素一定是最后入栈的元素B.栈顶元素一定是最先入栈的元素C.栈操作遵循先进后出的原则D.以上说法均错误【答案】C【解析】栈顶元素总是后插入的元素,从而也是最先被删除的元素;栈底元素总是最先插入的元素,从而也是最后才能被删除的元素。
江苏省2012年普通高校专转本选拔考试计算机基础试题卷(二年级)一、判题(本大题共20小题,每小题1分,共20分。
下列各小题表述正确的在答题卡上将A涂黑,错误的将B涂黑)1.现在广泛使用的公交IC卡和身份证都是接触式IC卡。
B 非接触式的2.卫星通信也是一种微波通信。
A3.PC机主板上的CMOS芯片需要使用电池供电,否则主机断电后其中的信息会丢失。
A4.主频为2GHz的CPU运算速度一定是主频为1GHz的CPU运算速度的2倍。
B5.光电鼠标使用微型镜头拍摄其下方的图像,由DSP分析判断鼠标器的移动方向和距离。
B6.按照软件的开发方式和适用范围,应用软件可分为通用应用软件和定制应用软件。
A7.高级语言解释程序能将高级语言源程序转换成目标程序。
B 编译方式才行8.在局域网中,每台计算机都必须有一个MAC地址,以便相互区别,实现计算机之间的通信。
A9.计算机局域网采用频分多路复用技术共享传输介质。
B 时分10.在广域网中,连接在网络中的主机发生故障不会影响整个网络通信,但若一台节点交换机发生故障,整个网络将陷入瘫痪。
B11.我国采用的PAL制式彩色电视信号在远距离传输时,使用YUV颜色模型。
A12.GIF格式图像在WWW网页中广泛使用的原因是它属于一种真彩色图像。
B 只有256色13.数据库是长期存放在计算机内、有组织、可共享的数据集合。
A14.在记事本中可对同一个文件的不同文字使用不同的字体。
B 不行,记事本属于简单文本格式15.Windows的设备管理程序支持即插即用(PnP)功能。
A16.在Word2003中,可以正确读取在记事本中建立的文件,但记事本无法正确读取Word文档。
A17.在Word2003中,要移动或复制一段文字必须通过剪贴板。
B 例如:可以直接拖到18.在Excel2003中,每一张工作表分别作为一个文件保存。
B一个工作簿保存为一个文件,里面可以含有多个工作表19.在Excel2003中,A2:A4各单元格的数据依次为1、2、3。
2012年下半年软件水平考试(初级)程序员下午(应用技术)真题试卷(题后含答案及解析)题型有:1. 必答题 2. 选答题必答题(共4道大题,每道大题15分)1.阅读以下说明和流程图,填补流程图中的空缺(1)~(5),将解答填入答题纸的对应栏内。
【说明】本流程图用于计算菲波那契数列{a1=1,a2=1,…,an=an-1+an-2,|n=3,4,…}的前n项(n≥2)之和S。
例如,菲波那契数列前6项之和为20。
计算过程中,当前项之前的两项分别动态地保存在变量A 和B中。
【流程图】正确答案:(1)2或A+B或其等价形式(2)n (3)A+B或其等价形式(4)B—A或其等价形式(5)S+B或其等价形式解析:本问题考查考生设计和阅读流程图的能力。
从题目给出的流程图可以看出,(1)需要为S赋值。
由于在初始时,S为前两项之和,因此,(1)处应填入A+B或2。
(2)处需要设置一个循环条件。
本流程图用于计算菲波那契数列的前n项(n≥2)之和S,显然,当循环变量值小于”时会一直循环进行求和,当循环变量值大于获等于”时循环结束,并输出和S的结果。
因此,(2)处应填入n。
(3)~(5)处分别用于计算B、A和S的值。
根据题目的描述,汁算过程中,当前项之前的两项分别动态地保存在变量A和B中。
因此,(3)处应填入A+B。
(4)处A为B的前一项,因此应填入B—A。
(5)处计算S的值,应在上次和的基础上再加上数列中下一项的值,因此应输入S+B。
2.阅读以下说明和C函数,填充函数中的空缺,将解答填入答题纸的对应栏内。
【说明】如果矩阵A中的元素A[i,j]满足条件:A[i,j]是第i行中值最小的元素,且又是第j列中值最大的元素,则称之为该矩阵的一个马鞍点。
一个矩阵可能存在多个马鞍点,也可能不存在马鞍点。
下面的函数用来求解并输出一个矩阵中的所有马鞍点,最后返回该矩阵中马鞍点的个数。
【C函数】Int findSaddle(int a[][N],int M),{ /*a表示M行N列矩阵,N是宏定义符号常量*/int row,column,i,k;int minElem:int COUrtt=0;/*count用于记录矩阵中马鞍点的个数*/for(row= 0;row <(1) ;row++) { /*minElem用于表示第row行的最小元素值,其初值设为该行第0列的元素值*/(2) :for(column= 1;columN<(3) ;column++)if(minElem>a[row][column]) { minElem= a[row][column];} for(k=0;k<N;k++)if(a[row][k]= =minElem){ /*对第row行的每个最小元素,判断其是否为所在列的最大元素*/for(i=0;i<M;i++) if( (4) >minElem)break;if(i>= (5) ){ printf(”(%d,%d):%d\n”,row,k,minElem);/*输出马鞍点*/count++:}/* if * /}/* if* /}/* for * /return count.}/* findSaddle * /正确答案:(1)M (2)minElem=a[row][0]或其等价形式(3)N (4)a[i][k]或其等价形式(5)M解析:本题考查考生综合运用C语言的知识解决实际问题的能力。
2012年全国计算机职称考试真题第一张下列关于个人计算机的叙述中,错误的是________。
A.个人计算机的英文缩写是PCB.个人计算机又称为微机C.世界上第一台计算机是个人计算机D.个人计算机是以微处理器为核心的计算机【正确答案:】C【答题结果:】【你的得分:】0下列关于个人计算机的叙述中,错误的是_________。
A.个人计算机将运算器和控制器做在一块大规模集成电路芯片上B.计算机发展到第五代出现了个人计算机C.个人计算机是大规模、超大规模集成电路发展的产物。
D.以Intel 4004为核心组成微型电子计算机叫MCS-4【正确答案:】B【答题结果:】【你的得分:】0下列叙述中,错误的是______。
A.Apple II是个人计算机B.IBM PC是个人计算机C.个人计算机一词由Apple II而来D.个人计算机一词由IBM PC而来【正确答案:】C【答题结果:】【你的得分:】0下列关于个人计算机硬件构成的叙述中,正确的是_________。
A.CPU可以看作是个人计算机的数据仓库B.主板芯片组可以看作是个人计算机的大脑C.主机箱是个人计算机各部分硬件相互连接的桥梁D.个人计算机的运行能力和运行效率在很大程度上和机器的内存有关【正确答案:】D【答题结果:】【你的得分:】0下列关于硬盘的叙述中,错误的是_________。
A.硬盘读写速度比光盘慢 B.个人计算机硬盘以IDE接口和SATA接口为主C.硬盘存储容量大 D.硬盘存储器系统由硬盘机、硬盘控制适配器组成【正确答案:】A【答题结果:】【你的得分:】0下列关于光盘特点的叙述中,正确的是________。
A.光盘存储容量小 B.光盘位价格低C.光盘携带不便 D.光盘读写速度很低【正确答案:】B【答题结果:】【你的得分:】0下列选项中,不属于输入设备的是_________。
A.键盘 B.光笔C.绘图仪 D.触摸屏【正确答案:】C【答题结果:】【你的得分:】0下列关于鼠标的叙述中,错误的是_________。
一、选择题(1)数据结构作为计算机的一门学科,主要研究数据的逻辑结构、对各种数据结构进行的运算,以及A)数据的存储结构B)计算方法C)数据映象D)逻辑存储正确答案: A(2) 串的长度是A)串中不同字符的个数B)串中不同字母的个数C)串中所含字符的个数且字符个数大于零D)串中所含字符的个数正确答案: D(3)在计算机中,算法是指A)加工方法B)解题方案的准确而完整的描述C)排序方法D)查询方法正确答案: B(4)以下不属于对象的基本特点的是A)分类性B)多态性C)继承性D)封装性正确答案: C(5)开发软件所需高成本和产品的低质量之间有着尖锐的矛盾,这种现象称做A)软件投机B)软件危机C)软件工程D)软件产生正确答案: B(6)下面不属于软件设计原则的是A)抽象B)模块化C)自底向上D)信息隐蔽正确答案: C(7)开发大型软件时,产生困难的根本原因是A)大系统的复杂性B)人员知识不足C)客观世界千变万化D)时间紧、任务重正确答案: A(8)下列SQL语句中,用于修改表结构的是A) ALTERB) CREATEC)UPDATED)INSERT正确答案: A(9)数据库、数据库系统和数据库管理系统之间的关系是A)数据库包括数据库系统和数据库管理系统B)数据库系统包括数据库和数据库管理系统C)数据库管理系统包括数据库和数据库系统D)3者没有明显的包含关系正确答案: B(10)关系模型允许定义3类数据约束,下列不属于数据约束的是A)实体完整性约束B)参照完整性约束C)域完整性约束正确答案: C(11) Visual FoxPro 6.0属于A)网状数据库系统B)层次数据库系统C)关系数据库系统D)分布式数据库系统正确答案: C(12)下列关系表达式中,运算结果为逻辑真.T.的是A)"副教授"$"教授"B)3+5#2*4C)"计算机"<>"计算机世界"D)2004/05/01==CTOD("04/01/03")正确答案: C(13)执行下列命令后,显示的结果是()X=50Y=100Z="X+Y"?50+&ZA)50+&ZB)50+X+YC)200D)数据类型不匹配正确答案: C(14)在Visual FoxPro中,数据库文件和数据表文件的扩展名分别是A).DBF和.DCTB).DBC和.DCTC).DBC和.DCXD).DBC和.DBF正确答案: D(15)建立一个表文件,表中包含字段:姓名(C,6)、出生日期(D)和婚否(L),则该表中每条记录所占的字节宽度为A)15B)16C)17D)18正确答案: B(16)在Visual FoxPro中,可以对字段设置默认值的表是A)自由表B)数据库表C)自由表或数据库表D)都不能设置正确答案: B(17)数据库表的索引类型共有A)1种B)2种C)3种D)4种正确答案: D(18)利用SET RELATION命令可以建立两个表之间的关联,该关联是A)永久性联系B)临时性联系C)任意的联系D)以上说法均不正确正确答案: B(19)要将数据库"考生库"文件及其所包含的数据库表文件放入回收站,下列命令正确的是A)DELETE DATABASE 考生库B)DELETE DATABASE 考生库RECYCLEC)DELETE DATABASE 考生库DELETETABLESD)DELETE DATABASE 考生库DELETETABLES RECYCLE正确答案: D(20)假设表中共有10条记录,执行下列命令后,屏幕所显示的记录号顺序USE ABC.dbfGOTO 6LIST NEXT 5A)1~5B)1~6C)5~10D)6~10正确答案: D(21)惟一索引的"惟一性"是指A)字段值的"惟一"B)表达式的"惟一"C)索引项的"惟一"D)列属性的"惟一"正确答案: C(22)下列关于运行查询的方法中,不正确的一项是A)在项目管理器"数据"选项卡中展开"查询"选项,选择要运行的查询,单击"运行"命令按钮B)单击"查询"菜单中的"运行查询"命令C)利用快捷键CTRL+D运行查询D)在命令窗口输入命令DO <查询文件名.qpr>正确答案: C(23)以下关于视图的描述中,正确的是A)视图结构可以使用MODIFY STRUCTURE命令来修改B)视图不能同数据库表进行联接操作C)视图不能进行更新操作D)视图是从一个或多个数据库表中导出的虚拟表正确答案: D(24)在某个程序模块中使用命令PRIVATE XI定义一个内存变量,则变量XIA)可以在该程序的所有模块中使用B)只能在定义该变量的模块中使用C)只能在定义该变量的模块及其上层模块中使用D)只能在定义该变量的模块及其下属模块中使用正确答案: D(25)执行下列程序:CLEARSET TALK OFFSTORE 1 TO i,a,bDO WHILE i<=3DO PROG1??"P("+STR(i,1)+")="+STR(a,2)+","i=i+1ENDDO??"b="+STR(b,2)RETURNPROCEDURE PROG1a=a*2b=b+aSET TALK ONRETURN程序的运行结果为A)P(1)=2,P(2)=3,P(3)=4,b=15B)P(1)=2,P(2)=4,P(3)=6,b=8C)P(1)=2,P(2)=4,P(3)=6,b=18D)P(1)=2,P(2)=4,P(3)=8,b=15正确答案: D(26)在运行表单时,下列有关表单事件引发次序的叙述正确的是A)Activate -> Init -> LoadB)Load -> Activate -> InitC)Activate -> Load -> InitD)Load -> Init -> Activate正确答案: D(27)如果文本框的SelStart属性值为-1,表示的含义为A)光标定位在文本框的第一个字符位置上B)从当前光标处向前选定一个字符C)从当前光标处向后选定一个字符D)错误属性值,该属性值不能为负数正确答案: D(28)执行SET SYSMENU TO命令后A)将当前菜单设置为默认菜单B)将屏蔽系统菜单,使菜单不可用C)将系统菜单恢复为缺省的配置D)将缺省配置恢复成Visual FoxPro系统菜单的标准配置正确答案: B(29)有报表文件PP1,在报表设计器中修改该报表文件的命令是A)CREATE REPORT PP1B)MODIFY REPORT PP1C)CREATE PP1D)MODIFY PP1正确答案: B(30)在连编对话框中,下列不能生成的文件类型是A).DLLB).APPC).PRGD).EXE正确答案: C(31)SELECT-SQL语句中,条件短语的关键字是A)FORB)FROMC)WHERED)WITH正确答案: C(32)找出平均分大于95分的学生学号和他们所在的班级A)SELECT 学号,班级FROM 成绩;WHERE 平均分>95B)SELECT 学号,班级FROM 班级;WHERE (平均分>95) AND (成绩.学号=班级.学号)C)SELECT 学号,班级FROM 成绩,班级;WHERE (平均分>95) OR (成绩.学号=班级.学号)D)SELECT 学号,班级FROM 成绩,班级;WHERE (平均分>95) AND (成绩.学号=班级.学号)正确答案: D(33)给出在车间"W1"或"W2"工作,并且工资大于3000的职工姓名,正确的命令是A)SELECT 姓名FROM 车间WHERE 工资>3000 AND 车间="W1" OR 车间="W2"B)SELECT 姓名FROM 车间WHERE 工资>3000 AND (车间="W1" OR 车间="W2")C)SELECT 姓名FROM 车间;WHERE 工资>3000 OR 车间="W1" OR 车间="W2"D)SELECT 姓名FROM 车间;WHERE 工资>3000 AND (车间="W1" OR 车间="W2")正确答案: D(34)在当前目录下有数据表文件student.dbf,执行如下SQL语句后SELECT * FORM student INTO DBF student ORDER BY 学号/DA)生成一个按"学号"升序的表文件,将原来的student.dbf文件覆盖B)生成一个按"学号"降序的表文件,将原来的student.dbf文件覆盖C)不会生成新的排序文件,保持原数据表内容不变D)系统提示出错信息正确答案: D(35)有如下SQL语句:SELECT * FROM 仓库WHERE 仓库号="H1";UNION;SELECT * FROM 仓库WHERE 仓库号="H2"该语句的功能是A) 查询在H1或者H2仓库中的职工信息B) 查询仓库号H1或者H2的仓库信息C) 查询即在仓库号H1,又在仓库号H2工作的职工信息D) 语句错误,不能执行正确答案: B二、填空题(1)长度为n的顺序存储线性表中,当在任何位置上插入一个元素概率都相等时,插入一个元素所需移动元素的平均个数为【1】。
2012年计算机软考软件设计师经典真题及答案1.通常在软件的( )活动中无需用户参与。
A. 需求分析B. 维护C. 编码D. 测试参考答案:C2.( )详细描述软件的功能、性能和用户界面,以使用户了解如何使用软件。
A. 概要设计说明书B. 详细设计说明书计C. 用户手册D. 用户需求说明书参考答案:C3.下述任务中,不属于软件工程需求分析阶段的是( )。
A.分析软件系统的数据要求B.确定软件系统的功能需求C.确定软件系统的性能要求D.确定软件系统的运行平台参考答案:D4.在开发信息系统时,用于系统开发人员与项目管理人员沟通的主要文档是( )。
A. 系统开发合同B. 系统设计说明书C. 系统开发计划D. 系统测试报告参考答案:B5.系统测试人员与系统开发人员需要通过文档进行沟通,系统测试人员应根据一系列文档对系统进行测试,然后将工作结果撰写成( ),交给系统开发人员。
A. 系统开发合同B. 系统设计说明书C. 测试计划D. 系统测试报告参考答案:D6.常见的软件开发模型有瀑布模型、演化模型、螺旋模型、喷泉模型等。
其中( )模型适用于需求明确或很少变更的项目,( )模型主要用来描述面向对象的软件开发过程。
A.瀑布模型B.演化模型C.螺旋模型D.喷泉模型参考答案:A、D7.在开发一个系统时,如果用户对系统的目标是不很清楚,难以定义需求,这时最好使用( )。
A.原型法瀑布模型 C.V-模型 D.螺旋模型参考答案:A8.采用瀑布模型进行系统开发的过程中,每个阶段都会产生不同的文档。
以下关于产生这些文档的描述中,正确的是( )。
A.外部设计评审报告在概要设计阶段产生。
B.集成测评计划在程序设计阶段产生。
C.系统计划和需求说明在详细设计阶段产生。
D.在进行编码的同时,独立的设计单元测试计划参考答案:D9.( )是一种面向数据流的开发方法,其基本思想是软件功能的分解和抽象。
A.结构化开发方法B.Jackson系统开发方法C.Booch方法D.UML(统一建模语言)参考答案:A10.软件开发中的瀑布模型典型地刻画了软件生存周期的阶段划分,与其最相适应的软件开发方法是( )。
Ni 在CPU中,(1)不仅要保证指令的正确执行,还要能够处理异常事件。
(1)A.运算器 B.控制器 C.寄存器组 D.内部总线【答案】B【解析】本题考查计算机系统硬件方面的基础知识。
计算机中的CPU是硬件系统的核心,用于数据的加工处理,能完成各种算术、逻辑运算及控制功能。
其中,控制器的作用是控制整个计算机的各个部件有条不紊地工作,它的基本功能就是从内存取指令和执行指令。
循环冗余校验码(CRC)利用生成多项式进行编码。
设数据位为k位,校验位为r位,则CRC码的格式为(2)。
(2)A.k个数据位之后跟r个校验位 B.r个校验位之后跟k个数据位C.r个校验位随机加入k个数据位中D.r个校验位等间隔地加入k个数据位中【答案】A【解析】本题考査数据校验基础知识。
计算机系统运行时,各个部件之间要进行数据交换,为了确保数据在传送过程中正确无误,一是提高硬件电路的可靠性;二是提高代码的校验能力,包括查错和纠错。
常用的三种校验码:奇偶校验码(Parity Codes)、海明码(Hamming Code)和循环冗余校验(Cyclic Redundancy Check,CRC)码。
循环冗余校验码广泛应用于数据通信领域和磁介质存储系统中。
它利用生成多项式为k 个数据位产生r个校验位来进行编码,其编码长度为k+r。
CRC的代码格式为:以下关于数的定点表示和浮点表示的叙述中,不正确的是(3)。
(3)A.定点表示法表示的数(称为定点数)常分为定点整数和定点小数两种B.定点表示法中,小数点需要占用一个存储位C.浮点表示法用阶码和尾数来表示数,称为浮点数D.在总位数相同的情况下,浮点表示法可以表示更大的数【答案】B【解析】本题考查数据表示基础知识。
各种数据在计算机中表示的形式称为机器数,其特点是采用二进制计数制,数的符号用0、1表示,小数点则隐含表示而不占位置。
机器数对应的实际数值称为数的真值。
为了便于运算,带符号的机器数可采用原码、反码、补码和移码等不同的编码方法。
中南大学考试试卷
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分)。