2016年4月-2009年4月福建省自考07186软件技术基础试题及答案含评分标准10套

第1页共5页2009年4月高等教育自学考试福建省统一命题考试软件技术基础试卷(课程代码7186)本试卷满分100分，考试时间150分钟。一、填空题(本大题共15小题，每小题2分，共30分)请在每小题的空格中填上正确答案。错填、不填均无分。1．数据结构算法中，通常用空间复杂度和两种方法综合衡量算法的效率。2．顺序存储的线性表，若第l个元素的存储地址是200，每个元素的长度为4，则第11个元素的地址是。3．删除长度为n的顺序表中的第k个元素(1≤k≤n)时，需要从前向后依次前移个元素。4．某二叉树的前序遍历序是abdgcefh，中序遍历序是dgbaechf，则后序遍历序是。5．二叉树的三个基本组成单元是左子树，右子树和。6．对序列(1，3，5，8，l0，18，20，22，24，30，40)采用折半查找法查找元素24，需进行次关键字比较。7．所谓进程指的是程序的一次执行过程。8．进程三种基本状态相互转化中不能实现的是阻塞→运行和。9．数据库管理系统是帮助用户创建、维护和使用数据库的软件系统，它是数据库系统的。10．E—R图中采用自考押题微信344647公众号顺通考试资料来表示属性。11．面向对象开发技术追求的是软件系统对的直接模拟。12．在软件设计阶段首先要完成，然后进行洋细设计。13．软件维护一般分为校正性维护、适应性维护、和预防性维护。14．面向对象领域中的UML不是一种具体的方法，而是一种语言。15．面向对象分析模型有三种，分别是：对象模型、和功能模型。二、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。16．若一个算法的运行时间函数T(n)=n2+102n+102，则用O表示的时问复杂度为【】A．O(n)B．O(n3)C．O(n2)D．O(n2+n)17．线性表顺序存储结构的主要特性是能实现数据元素的【】A．顺序存取B．随机存取C．索引存取D．HASH存取18．线性链表不具有的特点是【】A．随机存取B．不必事先估计所需存储空间大小C．插入与删除时不必移动元素D．存储空间与线性表长度成正比19．对二维数组A[1．．20][1．．l5]以列优先顺序将所有元素依次存放于一维数组B[1．．300]中，则A中元素A[1O][11]对应B中的位置k为【】A．210B．2l1C．220D．23020．对线性表进行折半查找时，要求线性表的组织构造必须满足【】A．关键字有序的链接表B．链按表但关键字不一定有序C．顺序但关键字不一定有序D．关键字有序的顺序表21．假设在有序表A[0．．．9]中进行折半查找，比较三次查找成功的结点数为【】A．3B．4C．5D．622．从二叉排序树中查找一个元素时，其时问复杂度大致为【】A．O(n)B．O(long2n)C．O(n2)D．O(nlong2n)23．操作系统的两个最基本特征是并发性和【】A．并行性B．共享性C．多态性D．虚拟性24．从操作系统的发展历史看，最早出现的操作系统类型是【】A．分时操作系统B．实时操作系统C．批处理系统D．分布式操作系统25．以下对操作系统的叙述中不正确的是【】A．操作系统是一种大型的应用软件B．操作系统简称OSC．操作系统是位于硬件之上的第一层软件D．操作系统是用户与硬件之间的接口26．构成关系模型的三个部分是【】A．数据结构、关系操作和关系完整性B．数据模型、关系操作和关系完整性C．数据结构、关系语言和关系完整性D．数据模型、关系语言和约束27．确定待开发系统的总体目标和范围，研究系统的可行性和可能解决方案，对资源、成本及进度进行合理的估算。这在软件开发的哪个阶段完成?【】A．制定计划B．需求分析C．软件设计D．测试28．在软件生命周期中，明确软件系统功能，确定软件系统必须做什么的阶段是【】A．制定计划B．需求分析C．概要设计D．详细设计29．数据流图中→符号表示【】A．数据加工B．数据存储文件C．数据流D．数据源点30以下列对面向对象开发方法的描述，不正确的是【】A．Booch最早描述了面向对象的软件开发方法的基础问题B．Cord／Yourdon方法比较系统地介绍了面向对象分析和面向对象设计C．Cord／Yourdon方法强调技术的创新性．以便提升可复用性D．OMT方法中的功能模型反映的是系统模块的输入值和输出值三、简答题(本大题共5小题，每小题4分，共20分)31．简述后序遍历二叉树的基本过程。32．对于序列(5，3，10，18，1，2，6，7，9，4)，按照直接插入排序法给出第2趟、第4趟、第6趟、第8趟的排序新序列。33．请完成内部排序方法的性能比较的表格。34．什么是操作系统?35．简述面向对象开发方法中Booch方法的分析和设计的基本步骤。四、综合应用题（本大题共2小题，每小题10分，共20分)36．假设两个完整型数组a[n]，b[n]表示两个集合，求c=a∪b，假定c已经分配足够的空间；请依据以下函数声明，完成上述问题的类C语言算法描述，同时给出用O表述的时间复杂度。Voidgetc(inta[]，intb[]，intc[]，intn){}37．构建超市商品销售POS收银系统用例图。提示信息如下：人员有POS收银员，系统管理员；前台POS，后台服务器提供数据支持。操作员扫描商品条形码，读取商品名称、金额等信息，输入购买数量，告知客户结账。

2009年10月高等教育自学考试福建省统一命题考试软件技术基础试卷(课程代码07186)一、填空题(本大题共15小题，每小题2分，共30分)请在每小题的空格中填上正确答案。错填、不填均无分。

2010年4月高等教育自学考试福建省统一命题考试软件技术基础试卷(课程代码07186)一、填空题(本大题共15小题，每空2分，共30分)请在每小题的空格中填上正确答案。错填、不填均不得分。1．一个算法通常是由控制结构和构成。2．非空的线性表(a1,a2,…an-1,an)，元索ai(1<i≤n)的直接前驱是。3．typedefstructnode{Datatypedata;structnode*next;}LinkList；定义的不带头结点的单链表L，将初值为L的指针P移到尾结点的语句是。4．若二叉树的前序遍历和后序遍历序列正好相反，则该二叉树的度为2的结点数=。5．一棵含有n个结点的k叉树(0<k<n)，可能达到的最大深度是。6．对某二叉排序树进行遍历，且保证输出所有结点的值序列按增序排列，对该二叉排序树应采用遍历法。7．排序是将一组任意排列的数据元素按的值递增或递减重新排列成有序的序列。8．操作系统中资源共事的主要方式有同时访问和。9．文件的逻辑结构就是从所看到的文件结构形式。10．进程的基本状态包括就绪状态、运行状态和。11．目前常用的数据组织层模型包括层次模型、网状模型、面向对象模型和。12．软件模块内部的越高则模块的独立性越强。13．维护对软件非常重要，应当在设计和阶段充分考虑软件的可维护性。14．面向对象中的消息指的是对象发出的。15．UML中的状态图所包含的基本元素有状态和。二、单项选择题。(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均不得分。16．以下选项中不属于算法特性的是【】A．输入/输出B．可行性C．完成性D．有穷性17．如果某二叉树的前序遍历为abcdef，后序遍历为efdcba，则其中序遍历为【】A．ecdfbaB．edfcbaCedfbcaD．acbedf18．以下选项中正确的是【】A．串的逻辑结构和线性表相同B．串的长度必须大于零c．串中元索只能是字母和数字D．空串就是空白串19．在长度为n的顺序表的第k个位置(1≤k≤n+1)前插入一个新元素时，需要从后向前依次后移的元素个数为【】A．n-kB．kC．n-k-1D．n-k+120．适于对动态查找表进行高效率查找的组织结构是【】A．二叉排序树B．分块有序表C．有序表D．线性链表21．以下哪种排序法的平均时间复杂度数越级最小【】A．直接插入排序B．冒泡排序C．简单选择排序D．希尔排序22．以下叙述正确的是【】A．直接插入排序是不稳定的排序法B．冒泡排序是不稳定的排序法C．希尔排序是稳定的排序法D．简单选择排序是不稳定的排序法23．操作系统为实现设备无关性，将设备管理软件分成I/O控制系统和【】A．用户程序层B．物理设备层C．硬件抽象层D．设备驱动程序层24．操作系统提供的用户接口不包括【】A．命令接口B．图形用户GUI接口C．系统调用命令D．注册表接口25．对数据库管理系统的特点叙述中，不正确的是【】A．数据结构化B．数据冗余度大C．提高了系统的灵活性D．数据独立性强26．若一个工厂只有一个厂长，则工厂和厂长之间的联系是【】A．一对一B．一对多C．多对多D．不确定27．软件开发中结构化方法的基本要点不包括【】A．自顶向下B．自底向上C．逐步求精D．模块化设计28．软件测试方法中，白盒测试主要用于测试【】A．模块接口B．软件功能C．程序正确性D．程序内部逻辑29．软件工程中仅根据程序的功能说明而不关心程序内部的逻辑结构的测试方法，称为【】A．白盒法B．黑盒法C．综合法D．灰盒法30．UML的模型图中有一大类是属于动态图，以下选项中不属于动态图的是【】A．状态图B．活动图C．构件图D．顺序图三、简答题(本大题共5小题，每小题4分，共20分)31．设二叉树后序遍历结果为BAC，画出所有可能的二叉树。32．简述折半查找的基本思想。33．在操作系统中，文件的逻辑结构和物理结构指什么?34．简述软件工程中需求分析的主要任务。35．请依据测试顺序列出软件测试一般要经历的几个阶段。四、应用题(本大题共2小题，每小题10分，共20分)36．当给定a，b，c三个整数时，判定一元二次方程ax2+bx+c=0实根的个数，如果不是二次方程也不是一次方程则返回-1，如果元实根返回0，如果有2个相等实根或1个实根则返回1，如果有2个不相等实根则返回2；请依据以下函数声明，完成上述问题的类C语言算法描述，同时给出用O表述的时间复杂度。introotnum(inta,intb,intc){}37.typedefstruct{keytypekey[N];intlen}LineTable;//顺序查找表类型，N为最大值，已定义针对上述顺序表定义，完成顺序表的顺序查找算法，要求如下：将监视哨设在下标值的高端，若找到第一个关键字值等于k，则返回其对应的下标，否则返回-1。intsearch_in_linetable(keytypek,LineTablest){intindex;}

2010年10月高等教育自学考试福建省统一命题考试软件技术基础试卷（课程代码07186）一、填空题(本大题共15小题，每小题2分，共30分)请在每小题的空格中填上正确答案。错填、不填均不得分。1．在数据结构中，数据的基本单位是。2．队列的特点是先进先出，为此队列仅在插入元素。3．任何一棵二叉树，如果n1,n2,n3，分别是度为0，1，2的结点的个数，则，n1=。4．树的度是树内各结点度的。5．由判定树可知，折半查找法查找结点F的过程中和关键字比较的次数恰好等于结点F在判定树中的。6．二叉排序树中任意一个结点的关键字小于其中的所有结点的关键字。7．关键字值相等的不同记录排序前后相对次序的排序方法称为稳定的排序方法。8．进程是操作系统进行独立运行及调度的基本单位，也是的基本单位。9．文件的物理结构指的是文件在的存储形式。10．常用的概念模型有语义对象模型和。11．关系的完整性包括用户自定义完整性、实体完整性和。12．结构化设计以为基础，采用自顶向下，逐步求精和模块化的过程得到软件结构图。13．可行性研究通常从操作可行性、社会可行性、经济可行性和四方面进行分析。14．软件系统的模块层次结构是，它反映了整个系统的功能实现。15．面向对象中的继承指的是子类可以自动拥有父类的全部。二、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均不得分。16．对于合法的输入，算法必须在执行有限次后在有限的时间内完成，这体现了算法特性中的【】A．可行性B．确定性C．有穷性D．健壮性17．在线性结构中，数据元素之间存在的关系是【】A．同属一个集合B．一个对一个C．一个对多个D．多个对多个18．一个栈的入栈序列是H，I，J，K，L，则该栈不可能的输出序列是【】A．HIJKLB．LKJIHC．JKLIHD．KLIJH19．假设以行优先存储的二维数组A[1…100，1…100]，设每个数据元素占2个存储单元，基地址为100，则LOC(A[5，5])=【】A．808B．818C．908D．91820．已知一棵二叉树中度为0的结点个数为11个，则度为2的结点个数为【】A．5B．6C．10D．2221．有一个有序表{1，2，4，8，12，22，32，45，48，50，72，80}，用折半法查找关键字为50的结点时，需要几次比较才能成功?【】A．2B．3C．4D．522．直接插入排序法是从第几个元素开始，逐个插入前边适当位置的排序方法?【】A．1B．2C．n／2D．n23．简单选择排序每趟在n-i+1个记录中选取关键字最小的记录放在有序序列的哪个位置?【】A．n-i+lB．i-1C．iD．i+124．下列不属于操作系统的基本类型的类型是【】A．分时操作系统B．个人计算机操作系统C．批处理系统D．实时操作系统25．在操作系统文件的物理结构中，哪个结构必须要求一批相邻的外存块?【】A．链接结构B．索引结构C．连续结构D．记录式结构26．数据库概念中模型如果是面向计算机的，则称该模型为【】A．数据层模型B．概念层模型C．概念模型D．信息模型27．实体内部的联系通常指的是【】A．组成实体的各属性之间的联系B．实体之间的联系C．实体内各属性与候选码之间的联系D．各实体主码之间的联系28．结构化程序设计的概念是由谁最先提出来的?【】A．美国IBM公司研究人员B．WinstonRoyceC．B．W．BoehmD．E．W．Dijkstra29．画某软件系统的数据流图时，其顶层图设计有【】A．0张B．1张C．1个模块1张D．2张或2张以上30．模块独立性最强的耦合是【】A．数据耦合B．非直接耦合C．标记耦合D．外部耦合三、简答题(本大题共5小题，每小题4分，共20分)31．简述数据存储结构的基本类型及主要特点。32．简要分析串顺序存储结构的不足。33．已知某二叉树的顺序存储结构如下图所示，画出该二叉树。34．假定对有序表(5，7，30，54，63，72)进行折半查找，画出其对应的二叉判定树，并计算查找成功时的平均查找次数。35．简述数据库管理系统相对文件管理系统的主要特点。四、应用题(本大题共2小题，每小题10分，共20分)36．#defineN100typedefstruct{intdata[N]；intlen；}QList；根据以上定义的线性表，写出一个函数：对两个线性表La，Lb，实现La=La-Lb，即去掉La表中与Lb表中相同的元素，最后的结果依然以La表返回。voidLa-Lb(QListLa，QListLb){inti，i，k；37．对于序列R(14，12，51，8．42，35，15，6)，请给出简单选择排序的每一趟排序结果。第l趟=第2趟=第3趟=第4趟=第5趟=第6趟=第7趟=

2011年4月高等教育自学考试福建省统一命题考试软件技术基础试卷（课程代码07186）一、填空题(本大题共15小题，每小题2分，共30分)请在每小题的空格中填上正确答案。错填、不填均不得分。1．数据元素存储结构一般采用顺序存储结构和存储结构。2．树中度数为0的结点，即没有子树的结点叫作叶子结点或结点。3．typedefstructnode{Datatypedata；structnode*next；}LinkList；定义的单链表中节点a，b前后相邻且b为非尾节点，则删除结点b的操作为。4．若顺序队列的队头和队尾指针分别是fro和rea，则判断队列为空的条件为。5．二维数组A按行顺序存储，其中每个元素占2个存储单元。若A[1][1]的存储地址为100，A[3][3]的存储地址为l40，则A[5][5]的存储地址为。6．深度为k的二叉树的最大结点数为。7．二叉排序树中任何一棵子树是一棵。8．内部排序是指待排序记录全部存储在计算机的中进行的排序。9．进程的主要特征包括独立性、动态性和。10．操作系统提供的用户接口主要包括命令接口、GUI、JCL和。11．在E—R方法中实体之间的联系主要有一对一联系、一对多联系和。12．软件工程是从——和方法两方面研究如何更好地开发和维护软件的学科。13．结构化分析采用数据流图作为分析工具，其中的长方形图形表示。14．软件测试的主要目的在于。15．面向对象开发方法是研究面向对象分析和的方法。二、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均不得分。16．下列程序段的时间复杂度为for(inti=0；i<m；i++)for(intj=0；j<n；j++)mat[i][j]=i*j；【】A．0(mn)B．D(m2)C．0(n17．线性表采用链式存储结构时，表中各个数据元素的存储地址【】A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续与否均可以18．栈和队列作为特殊的线性表，它们的共同点是【】A．都是先进后出B．都是先进先出C．无共同点D．仅允许在端点处插入和删除元素19．若二叉树的前序遍历和后序遍历序列正好相反，则该二叉树必定是【】A．空或者只有一个结点B．高度等于其结点数C．任一结点无左孩子D．任一结点无右孩子20．下列叙述不正确的是【】A．直接插入排序是稳定的排序法B．冒泡排序是稳定的排序法C．直接插入排序的时间复杂度为0(n)D．简单选择排序是不稳定的排序法21．顺序逐个检索一个具有n个数据元素的线性表，其时间复杂度为【】A．O(n)B．O(log2n)C．D(n222．用冒泡排序法对ll个数据元素进行排序，第一趟共比较多少对关键字【】A．1B．2C．n-lD．n23．下列叙述不正确的是【】A．直接插入排序仅需1个辅助空间B．冒泡排序仅需1个辅助空间C．希尔排序仅需1个辅助空间D．简单选择排序至少需要2个辅助空间24．唯一标志进程存在的数据结构是【】A．JCBB．PCBC．TCBD．DCB25．下列关于进程基本状态转化叙述中不正确的是【】A．就绪→运行B．运行→就绪C．阻塞→就绪D．就绪→阻塞26．用来描述概念模型信息结构的最常用的方法是【】A．语义对象模型B．E—R模型C．关系模型D．层次模型27．在对软件分类中，下列不属于应用领域型软件的是【】A．系统软件B．嵌入式软件C．大型软件D．商业软件28．面向对象方法最早出现在哪个语言中【】A．SmallTlalk80B．Simula67C．C++D．Pascal29．软件开发周期中对软件质量保证工作最关键的环节是【】A．软件开发B．需求分析C．软件维护D．软件测试30.下列对面向对象中的类所作的表述不正确的是【】A.类代表抽象的事物B．类具有封装性C.对象是类的实例D．对象是类的模版三、简答题(本大题共5小题，每小题4分，共20分)31.简述算法的主要特征。32.简述先序遍历二叉树的基本过程。33.对于关键字序列(55，24，12，30，60，58，70)，从空树开始，请画出其二叉排序树。34.简述数据库中常用的组织层模型的主要类型及其数据组织形式。35.简述软件危机的主要表现。四、应用题(本大题共2小题，每小题10分，共20分)37．有一个学生成绩处理系统，功能要求如卜：1．基本信息管理：导入教务处学生选课信息，提取教师、课程、学生三者的对应关系；2．成绩录入：分配人员录入成绩，做好录入日志登记，进度控制；3．成绩查询：学生只能查自己的成绩；教师可以查所授班级的成绩；教学领导可以获得全部成绩的各种统计报表、可以查询每个班级、每个教师的成绩情况；4．成绩处理：系统依据学生平时成绩、期中成绩和期末成绩总和给出学生的最终成绩；5．成绩提交：依据教务处格式，将最终成绩提交给教务处。根据要求画出该系统的顶层数据流图。

2012年4月高等教育自学考试福建省统一命题考试软件技术基础试题课程代码：07186本试卷满分100分，考试时间150分钟。考生答题注意事项：本卷所有试卷必须在答题卡上作答。答在试卷和草稿纸上的无效。第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。第二部分为非选择题。必须注明大、小题号，使用0.5毫米黑色字迹签字笔作答。合理安排答题空间，超出答题区域无效。第一部分选择题一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。未涂、错涂或多涂均无分。1．下列描述中不正确的是A．数据元素是数据的基本单位B．数据元素是数据不可分割的最小单位C．数据元素通常又称为记录D．数据元素通常作为一个整体进行处理2．下列有关线性表的叙述中，正确的是A．同一线性表中的元素具有相同特性B．线性表中任一元素有且仅有一个直接后继C．线性表中任一元素有且仅有一个直接前趋D．线性表至少包含一个元素3．一个队列的入列序列是L，M，N，O，则队列的输出序列是A．O，N，M，LB．L，M，N，OC．L，O，N，MD．N，M，O，L4．假设以行优先存储的二维数组A[1．．100，1．．200]，设每个数据元素占2个存储单元，基地址为100，则LOC(A[6，6])=A．1005B．1105C．2100D．21105．含有3个2度结点和4个叶结点的共7个结点的二叉树含1度结点A．0个B．1个C．2个D．3个6．对于n个记录的序列最多经过几趟冒泡排序就可以变成按关键字有序的顺序序列?A．n/2B．n-lC．nD．n+17．下列对冒泡排序法叙述正确的是A．外部排序法B．不稳定排序法C．稳定排序法D．时间复杂度为O(n)8．设一个顺序表有128个元素，用折半查找法进行查找时，最大比较次数是A．7B．8C．16D．329．进程作为操作系统的一种重要实体具有较多特性，但不包括A．并发性B．动态性C．独立性D．虚拟性10．一个刚刚创建的进程，通常呈现的基本状态是A．就绪态B．运行态C．阻塞态D．挂起态11．下列不属于数据库常用的组织层模型的是A．关系模型B．信息模型C．网状模型D．层次模型12．下列类型表体现了关系类型中的虚表概念的是A．基本关系B．基本表C．查询表D．视图表13．结构化程序设计的基本要点不包括A．使用goto语言实现灵活跳转B．单一入口，单一出口C．自顶向下，逐步求精D．主程序员组14．检查软件产品是否符合用户需求的测试过程称为A．单元测试B．集成测试C．系统测试D．确认测试15．面向对象中构成对象的基本要素是A．实体和服务B．属性和服务C．实体和关系D．实体和属性第二部分非选择题二、填空题(本大题共15小题，每小题2分，共30分)请在答题卡上作答。16．一个算法的执行次数表示为(5n2+2nlog2n+4n)/(4n)，则其时间复杂度表示为__________。17．数据的存储结构包括数据元素的表示和__________的表示。18．线性表L=(α1,α2，…,αn)采用顺序存储结构，假定在每个可能的位置上插入元素的概率都相等，则插入一个新元素平均需要移动的元素个数是__________。19．有三个结点的二叉树，最多有__________种形状。20．树中结点的__________称为树的深度或高度。21．由判定树可知，折半查找法查找结点D的过程恰好走了一条从__________到结点D的路径。22．二叉排序树中任意一个结点的关键字大于其__________中的所有结点的关键字。23．在直接插入排序中，已经进行到要将第i个记录插入时，此时前i-1个记录必定是__________的。24．操作系统的虚拟性指的是使用虚拟技术把__________映射成虚拟的逻辑设备。25．为实现设备无关性，操作系统采用了分层技术，即将设备管理软件分成上层__________和下层设备驱动程序。26．E-R方法中主要有实体、属性和__________三个概念。27．软件的概念可以简单地概括为软件=程序+__________+文档。28．需求分析的基本任务是确定系统的目标，即回答系统必须“__________”的问题。29．在软件的详细设计中使用最广泛的一个描述工具是__________。30．面向对象中的封装在信息处理领域可以说是一种很好的__________技术。三、简答题(本大题共5小题，每小题4分，共20分)请在答题卡上作答。31．简述栈、队列和串的共同点及它们的特殊性。32．简述数据元素之间的四种基本关系及基本结构。33．简述面向对象技术的基本观点。34．简述二叉排序树插入的基本过程。35．简述软件与硬件的本质上的区别以及软件的主要特点表现。四、综合应用题(本大题共2小题，每小题10分，共20分)请在答题卡上作答。36．对于有序表(2,4,6,8,15,20,40,80,100,120,150)进行折半查找，完成如下问题：(1)画出对应的二叉判定树；(2)若查找元素80，则需要依次与哪些元素进行比较?按顺序给出这些元素；(3)计算查找成功所需的平均比较次数。给出求长度为n的一维数值型数组平均值的PAD图。

2013年4月高等教育自学考试福建省统一命题考试软件技术基础试题课程代码：07186本试卷满分100分，考试时间150分钟考生答题注意事项：本卷所有试卷必须在答题卡上作答。答在试卷和草稿纸上的无效。第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。第二部分为非选择题。必须注明大、小题号，使用0.5毫米黑色字迹笔作答。合理安排答题空间，超出答题区域无效。第一部分选择题一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。未涂、错涂或多涂均无分。1．在数据结构中，若数据元素之间存在一个对多个的关系，则该结构是A．集合B．线性结构C．图状结构D．树状结构2．在一个单链表中，若节点P不是尾结点，则在P之后插入S结点，需执行A．S－>next=p;p－>next=s；B．S－>next=P－>next；p－>next=s；C．S－>next=P－>next；p=s；D．P－>next=s；s－>next=p；3．链式栈与顺序栈相比，一个比较明显的优点是A．插入操作更方便B.一般不会出现栈满的情况C．不会出现栈空的情况D．删除操作更方便4．高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为A．h+1B．2h—lC．2hD．2h+15．采用顺序查找法查找长度为n的线性表，则成功查找时每个元素的平均查找长度为A．nB．n／2C．(n+1)／2D．(n-1)／26．稳定的排序方法是指在排序中，关键字值相等的不同记录在排序前后的相对次序A．保持不变B．保持相反C．不定D．正好相邻7．希尔排序法的时间复杂度通常表示为A．o(n)B．o(nlogn)C．o(n2logn)D．o(n2)8．操作系统作为最底层的系统软件，它的主要功能是资源管理和提供A．软件开发B．硬件维护C．系统维护D．用户接口9．操作系统中文件的物理结构不包括A．连续结构B．记录式结构C．串联结构D．索引结构10．E-R图中用来表示实体的图形是A．菱形B．矩形C．椭圆形D．圆形11．关系数据库的标准语言是A．HTMLB．SQLC．DCLD．DDL12．软件危机的主要表现不包括A．开发软件的成本和进度难以控制B．软件的可维护性差C．软件产品的质量不可靠D．软件的可移植性差13．结构化分析方法是一种A．面向数据流的分析方法B．面向过程的分析方法C．面向对象的分析方法D．系统分析方法14．在软件设计阶段应提供的规格文档是A．软件需求规格说明书B．概要及详细设计规格说明书C．数据字典及流程图D．源程序以及源程序的说明书15．UML动态建模采用的状态图中，终态对应的图形是A．实心圆B．空心圆C．带边界的实心圆D．圆角框．第二部分非选择题二、填空题(本大题共15小题，每小题2分，共30分)请在答题卡上作答。16．设有一个递归算法如下intfa(intn)／／n大于等于0{if(n(=0)return1；elsereturnn*fa(n-1);}则计算fa(n)需要调用该函数的次数为次。17．链式存储结构中的结点包含数据域和域。18．栈的特点是后进先出，因此栈只能在插入和删除元素。19．求串T在主串S中首次出现的位置的操作称为。20．已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则前序遍历序列是。21．树中结点所拥有的称为结点的度。22．分块查找中的索引表一定是按照有序的。23．操作系统充当的角色主要包括用户接口、、应用软件的开发平台和运行环境。24．从微观角度讲，操作系统中的并发性指的是多道程序在极短的时间间隔内执行。25．如果进程只需要获得CPU就可以进行运行态，则表明该进程处于态。26．数据模型如果是面向用户的，则称该模型为。27．软件生存周期模型是对软件的建模。28．结构化分析方法总的指导思想是和逐步求精。29．白盒测试主要针对程序逻辑，而黑盒测试主要针对。30．UML语言中的用例图包括的模型元素有用例和。三、简答题(本大题共5小题，每小题4分，共20分)请在答题卡上作答。32．对右图所示的二叉树，给出先序、中序、后序遍历的结果序列。33．简述操作系统如何实现设备无关性?34．软件工程是一门实践学科，请写出它要达到的主要目标。35．简述软件生存周期模型中的瀑布模型的主要特点。

2014年4月高等教育自学考试福建省统一命题考试软件技术基础试卷（课程代码07186）本试卷满分100分，考试时间150分钟。考生答题注意事项：1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3．第二部分为非选择题。必须注明大、小题号，使用0.5毫米黑色字迹签字笔作答。4．合理安排答题空间，超出答题区域无效。第一部分选择题一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。未涂、错涂或多涂均无分。1．算法指的是A．计算机程序B．解决问题的计算方法C．数值方法D．解决问题的有限运算序列2．线性表若采用链式存储结构时，要求内存中可用存储单元的地址A．必须连续B．部分地址必须连续C．一定是不连续的D．连续与否都可以3．判定一个顺序栈stack（栈中元素个数最多为N）满的条件是A.Stack→top!=0B.Stack→top==0C.Stack→top!=ND.Stack→top==N4。按照二叉树的定义，具有3个结点的二叉树共有几种？A．3B．4C．5D．65．在有序表A[O10]中折半查找每个元素（等概率查找），则平均查找长度为A．2B．3C．4D．5.56．排序是根据下列哪个选项值的大小重新安排各数据元素的顺序？A．记录B．关键字C．元素D．结点7．直接插入排序法的时间复杂度是A.o（n）B.o(nlogn)C.o(n2logn)D.o(n2)8．操作系统的特性之一是并发性，下列理解不正确的是A．并发指n个(n>1)事件在同一时间间隔内发生B．多道程序在同一时间间隔内同时执行C．多道程序在极短的时间间隔内交替执行D．多道程序在同一时间点同时执行9．文件的逻辑结构主要采用字符流文件和A．连续文件B．记录式文件C．串联文件D．索引文件10.E-R图中用来表示属性的图形是A．菱形B．矩形C．椭圆形D．圆形11.关系完整性中下列哪项是关系的不变性？A．实体完整性B．参照完整性和用户自定义完整性c．实体完整性和用户自定义完整性D．实体完整性和参照完整性12.系统设计人员依据软件需求规格说明书确定软件的体系结构，进而确定每个模块的实现算法等，这项工作在下列的哪个阶段完成？A．制定计划B．编码实现C．测试阶段D．软件设计13.软件生存周期中时间最长的阶段是A．需求分析B．软件设计C．编码实现D．软件维护14.PAD图（ProblemAnalysisDiagram，问题分析图）主要用于哪个阶段？A．概要设计B．详细设计C．编码实现D．软件测试15.下列对UML的特点表述，不正确的是A．用例图来自OOSEB．类图来自OMT方法C．构件图和配置图来自Booch的模块图和过程图D．UML是一种面向对象方法第二部分非选择题二、填空题（本大题共15小题，每小题2分，共30分）请在答题卡上作答。16.算法：for(i=O;i<n;i++)x=x+sqr(i);的时间复杂度的数量级表示为。17.链式存储结构中数据元素之间的逻辑关系是通过结点中的来指示的。18.链栈和顺序栈相比，在存储元素方面最大的区别是链栈没有问题。19.串中任意个连续的字符组成的子序列称为该串的。20.若结点A有三个兄弟（不含A），而结点B是A的双亲结点，则结点B的度是。21．树的结点包含一个数据元素及若干指向其的分支。22.在分块查找法中，应根据待查值首先查找，然后再查找相应的子块。23.操作系统区别于其他软件的基本特征有共享、虚拟和。24.分时操作系统是把一个时间段分成若干个，使多个用户程序轮流使用CPU并运行。25.操作系统存储管理的主要方式包括分区式、分段式、段页式和一。26.数据模型如果是面向计算机的，则称该模型为。27.结构化方法的基本要点包括自顶向下、逐步求精和。28.耦合性是对模块之间互相连接的的度量。29.构成对象的两个基本要素是属性和。30.在UML语言中，类图显示了一组类以及类之间的关系，图中采用表示类。三、简答题（本大题共5小题，每小题4分，共20分）请在答题卡上作答。 2015年4月高等教育自学考试福建省统一命题考试软件技术基础试卷(课程代码07186)本试卷满分100分，考试时间l50分钟。考生答题注意事项：1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。4．合理安排答题空间，超出答题区域无效。第一部分选择题一、单项选择题(本大题共l5小题。每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。未涂、错涂或多涂均无分。1．算法分析的目的主要是A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的易懂性和文档性D．分析算法的效率以求改进2．在单链表中，若删除结点P的后续结点，则执行3．设某个顺序栈S，元素A，B，C，D，E，F，G依次进栈，如果7个元素的出栈顺序为C，D，E，G，F，B，A，则该顺序栈的容量最小为A．2B．3C.4D.74．如果某二叉树的前序为abcde，中序为cdbea，那么该二叉树的后序为A．cdebaB．edcbaC．dcebaD．dcbae5．下列对直接插入排序法描述正确的是A．是稳定排序法B．是不稳定排序法C．是外部排序法D．时间复杂度为O(n)6．内部排序是指在排序的整个过程中，全部待排序的数据元素都位于计算机的A．内存储器B．外存储器C．内存储器和外存储器D．寄存器7．简单选择排序法的平均时间复杂度是A．o(n)B．o(n2)C．o(nlogn)D．o(n2logn)8．操作系统区别于其它软件的基本特征中不包括A．并发B．共享C．管理D．虚拟9．进程的状态中不包括A．结束状态B．就绪状态C．阻塞状态D．运行状态10．E—R图中用来表示联系的图形是A．菱形B．矩形C．椭圆形D．圆形11．若一个工厂有若干职工，而每个职工只在一个工厂工作，则工厂和职工之间的联系是A．一对一B．一对多C．多对多D．不确定12．瀑布模型的主要特点是A．软件开发过程被严格的划分为一系列有序的活动B．提供了有效的管理模式C．软件开发过程分解为几个独立阶段D．缺乏灵活性13．结构化程序设计的一种基本方法是A．自顶向下逐步求精B．逐步迭代法C．逐步排除法D．递归法14．在数据流图中，圆形代表A．数据源点B．数据终点C．数据加工D．数据流15．UML的模型图中有一大类是属于静态图，下列不属于静态图的是A．类图B．对象图C．包图D．用例图第二部分非选择题二、填空题(本大题共l5小题，每小题2分，共30分)请在答题卡上作答。16．通常根据算法中描述核心问题的______重复执行的次数来作为算法的时间量度。17．非空的线性表(a1，a2，…，an-1，an)，元素ai(1≤i<n)的直接后继是______。18．对于链栈stack而言，判定栈空的条件是______。19．一棵含有n个结点的k叉树(0<k<n)，可能达到的最小深度是______。20．在二叉树的第k层上至多有______个结点。21．假设在有序表A[0…l9]中进行折半查找，比较2次即查找成功的结点为______。22．二叉排序树查找成功的平均查找长度和二叉排序树的形态及______有关。23．操作系统是用户和计算机硬件之间的______。24．所谓通用操作系统指的是一个操作系统兼顾分时、实时和______的全部或两种功能。25．操作系统存储管理中的分页存储的管理方法是将内存空间按照固定大小划分为若干大小相等的页面，这些页面称为______。26．数据层模型描述了数据的______，故又称为组织层模型。27．结构化设计中采用模块化设计的主要目的是降低程序的______，使程序设计、调试和维护操作更简单。28．软件模块之间耦合性越强则模块的______越差。29．类是具有相同属性和服务的一组______的集合。30．UML中的状态图用来描述一个实体基于______的动态行为。三、简答题(本大题共5小题，每小题4分，共20分)请在答题卡上作答。31．#defineNl00typedefstruct{indata[N]；intlens；}QList；请补充完整关于顺序表中查找元素X的操作，若找到则返回基于下标0开始的位置，否则返回-l。intfind(QListL，intX){intj=0；while(①____________________________________){②____________________________________if(③____________________________________)elsereturn-1}}32．对关键字序列(27，21，66，15，45，36，27，10)采用简单选择排序，给出第2，4，5，6四趟的排序结果。33．简述操作系统中分区存储管理的基本思想和特点。34．简述软件工程中软件测试的基本任务。35．简述软件开发计划的主要内容。四、应用题(共2题。每小题10分，共20分)请在答题卡上作答。36．采用带头结点的链队列实现对键盘上输入的字符进行队列管理：1.如果输入的是A…W，则从队尾入队2．如果输入的是Y，则队头元素出队3．如果输入的是Z，则显示队列中剩余元素，然后退出算法37．建立学生成绩管理系统的用例模型。管理人员负责成绩管理；学生查询成绩。成绩管理包括：录入成绩，修改成绩，给出成绩单，学生信