公共基础知识部分

公共基础知识部分第1页，课件共73页，创作于2023年2月一、数据结构与算法1、数据的存储结构是指（）A、存储在外存中的数据B、数据所占的存储空间量C、数据在计算机中的顺序存储方式D、数据的逻辑结构在计算机中的表示分析:

数据的存储结构:数据的逻辑结构在计算机存储空间中的存放形式。也称为物理结构。数据的逻辑结构：反映数据元素之间关系的数据元素集合（数据对象）的表示。包括：元素的信息、数据元素之间的前后件关系。结构：集合、线性结构、树形结构、图形结构四种。

一种逻辑结构的数据可以表示成多种存储结构：顺序、链式、索引等。第2页，课件共73页，创作于2023年2月2、下列关于栈的描述中错误的是（）A、栈是先进后出的线性表B、栈只能顺序存储C、栈具有记忆作用D、对栈的插入与删除操作中，不需要改变栈底指针分析：栈：特殊的线性表。限定只在一端进行插入与删除的线性表，这一端称为栈顶，另一端称为栈底。栈是按照“先进后出”或“后进先出”的原则组织数据的。栈具有记忆作用。第3页，课件共73页，创作于2023年2月3、对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是（）A、冒泡排序为n/2B、冒泡排序为nC、快速排序为nD、快速排序为n(n-1)/2分析：冒泡排序和快速排序在最坏的情况下，需要比较n(n-1)/2次。第4页，课件共73页，创作于2023年2月4、对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为（）A、log2nB、n/2C、nD、n+1分析：1、查找可分为：顺序查找和二分查找两种。2、对于长度为n的有序线性表，在最坏情况下，顺序查找需要比较n次，而二分查找只需要log2n次。第5页，课件共73页，创作于2023年2月5、下列对于线性链表的描述正确的是（）A、存储空间不一定连续，且各元素的存储顺序是任意的B、存储空间不一定连续，且前件元素一定存储在后件元素的前面C、存储空间必须连续，且前件元素一定存储在后件元素的前面D、存储空间必须连续，且各元素的存储顺序是任意的分析：

1、线性链表：就是线性表的链式存储。存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。

2、线性表的顺序存储：用一组地址连续的存储单元依次存储线性表的数据元素。缺点：插入删除时移动大量元素；有“上溢”情况；空间不便于动态分配。第6页，课件共73页，创作于2023年2月6、某二叉树中度为2的结点有18个，则该二叉树中有（）个叶子结点。分析：1、二叉树的定义二叉树只有一个根结点，每个结点最多只有两棵树（左子树、右子树）。2、二叉树的性质：性质1：在二叉树的第k层上至多有2k-1个结点（k>=1）;

性质2：深度为m的二叉树至多有2k-1个结点。性质3：对任意一棵二叉树，度为0的结点数总比度为2的结点数多1。性质4：具有n个结点的完全二叉树深度至少为[log2n]+1。第7页，课件共73页，创作于2023年2月7、下列数据结构中，能用二分法进行查找的是（）A、顺序存储的有序线性表B、线性链表C、二叉链表D、有序线性链表分析：二分查找只适用于顺序存储的有序表。第8页，课件共73页，创作于2023年2月8、下列关于栈的描述正确的是（）A、在栈中只能插入元素而不能删除元素B、在栈中只能删除元素而不能插入元素C、栈是特殊的线性表，只能在一端插入或删除D、栈是特殊的线性表，只能在一端插入元素，而字另一端删除元素第9页，课件共73页，创作于2023年2月9、下列叙述中正确的是（）A、一个逻辑数据结构只能有一种存储结构B、数据的逻辑结构属于线性结构，存储结构属于非线性结构C、一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D、一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率第10页，课件共73页，创作于2023年2月10、算法复杂度主要包括时间复杂度和（）复杂度。分析:1、算法的复杂度主要包括时间复杂度和空间复杂度.2、算法的时间复杂度：指执行算法所需要的计算工作量；

3、算法的空间复杂度：指执行这个算法所需要的内存空间；

4、算法的时间复杂度与空间复杂度并不相关。5、一棵二叉树第六层(根结点为第一层)的结点数最多为（）个。6、数据结构分为逻辑结构和存储结构，循环队列属于（）结构。第11页，课件共73页，创作于2023年2月11、按照”后进先出”原则组织数据的数据结构是（）

A、队列B、栈

C、双向链表D、二叉树

第12页，课件共73页，创作于2023年2月12、下列叙述中正确的是（）

A、线性链表是线性表的链式存储结构

B、栈与队列是非线性结构

C、双向链表是非线性结构

D、只有根结点的二叉树是线性结构分析：

1、栈、队列和双向链表都是线性结构，而二叉树是非线性结构。

2、线性结构和非线性结构是从数据的逻辑结构角度而言，与该数据结构中有多少个元素没有关系，即使是空二叉树也是非线性结构的。第13页，课件共73页，创作于2023年2月13、对如下二叉树

进行后序遍历的结果为（）

A、ABCDEFB、DBEAFC

C、ABDECFD、DEBFCA

分析：二叉树的遍历：就是按某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。1.前序遍历（根-左-右）2.中序遍历（左-根-右）3.后序遍历（左-右-根）

ABCDEF第14页，课件共73页，创作于2023年2月14、在深度为7的满二叉树中,叶子结点的个数为（）

A、32B、31C、64D、63

分析：第15页，课件共73页，创作于2023年2月15、对长度为10的线性表进行冒泡排序,最坏情况下需要比较的次数为（）。16、设一棵完全二叉树共有839个结点，则在该二叉树中有__________个叶子结点。第16页，课件共73页，创作于2023年2月17、下列叙述中正确的是________。A、一个算法的空间复杂度大，则其时间复杂度也必定大B、一个算法的空间复杂度大，则其时间复杂度必定小C、一个算法的时间复杂度大，则其空间可复杂度必定小D、上述三种说法都不对第17页，课件共73页，创作于2023年2月18、在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为________。A、63B、64C、6D、7第18页，课件共73页，创作于2023年2月19、对下列二叉树

进行中序遍历的结果是________。A、ACBDFEGB、ACBDFGEC、ABDCGEFD、FCADBEG第19页，课件共73页，创作于2023年2月20、按“先进后出”原则组织数据的数据结构是______________。21、数据结构分为线性结构和非线性结构，带链的队列属于_______________。第20页，课件共73页，创作于2023年2月22、下列叙述中正确的是（）A、算法的效率只与问题的规模有关，而与数据的存储结构无关B、算法的时间复杂度是指执行算法所需要的计算工作量C、数据的逻辑结构与存储结构是一一对应的D、算法的时间复杂度与空间复杂度一定相关第21页，课件共73页，创作于2023年2月23、下列对队列的叙述中正确的是（）A、队列属于非线性表B、队列按“先进后出”原则组织数据C、队列在队尾删除数据D、队列按“先进先出”原则组织数据分析：队列：是一种操作受限的线性表。他只允许在线性表的一端进行插入操作，另一端进行删除操作。其中，允许插入的一端称为队尾，允许删除的一端称为队首。队列具有“先进先出”的特点。第22页，课件共73页，创作于2023年2月24、对下列二叉树：进行前序遍历的结果是（）A、DYBEAFCZXB、YDEBFZXCAC、ABDYECFXZD、ABCDEFXYZABCDEFXYZ第23页，课件共73页，创作于2023年2月25、某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为（）。26、在深度为7的满二叉树中，度为2的结点个数为（）。第24页，课件共73页，创作于2023年2月27、下列叙述中正确的是（）A、数据的逻辑结构与存储结构必定是一一对应的B、由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构C、程序设计语言中的数据一般是顺序存储结构，因此，利用数组只能处理线性结构D、以上三种说法都不对第25页，课件共73页，创作于2023年2月28、冒泡排序在最坏情况下的比较次数是（）A、n(n+1)/2B、nlog2nC、n(n-1)/2D、n/229、一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为（）A、219B、221C、229D、231第26页，课件共73页，创作于2023年2月30、线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的_______存储结构。31、对下列二叉树进行中序遍历的结果是______________。FCEADGBHP第27页，课件共73页，创作于2023年2月二、程序设计基础1、在面向对象方法中，类的实例称为（）2、在面向对象方法中，（）描述的是具有相似属性与操作的一组对象。第28页，课件共73页，创作于2023年2月3、下面关于类、对象、属性和方法的叙述中，错误的是（）A、类是对一类相似对象的描述，这些对象具有相同种类的属性和方法B、属性用于描述对象的状态，方法用于表示对象的行为C、基于同一个类产生的两个对象可以分别设置自己的属性值D、通过执行不同对象的同名方法，其结果必然是相同的第29页，课件共73页，创作于2023年2月4、下列选项中不属于结构化程序设计方法的是（）

A)自顶向下B)逐步求精

c)模块化D)可复用分析：

1、结构化程序设计方法的主要原则：自顶向下，逐步求精，模块化，限制使用goto语句。

2、可复用性：是软件工程追求的目标之一，是提高软件产品效率的最主要的方法。第30页，课件共73页，创作于2023年2月5、下面选项中不属于面向对象程序设计特征的是_________.A．继承性B．多态性C．类比性D．封装性第31页，课件共73页，创作于2023年2月6、在面向对象方法中，实现信息隐蔽是依靠（）A．对象的继承B．对象的多态C．对象的封装D．对象的分类7、下列叙述中，不符合良好程序设计风格要求的是（）A．程序的效率第一，清晰第二B．程序的可读性好C．程序中要有必要的注释D．输入数据前要有提示信息第32页，课件共73页，创作于2023年2月三、软件工程基础1、下列对于软件测试的描述中正确的是（）A、软件测试的目的是证明程序是否正确B、软件测试的目的是使程序运行结果正确C、软件测试的目的是尽可能多地发现程序中的错误D、软件测试的目的是使程序符合结构化原则分析：软件测试的目的：尽可能多地发现软件产品中的错误和缺陷。软件测试一般不由开发人员测试自己的程序。测试发现错误后，可以立即进行调试并改正错误，经调试改错后还应进行测试。第33页，课件共73页，创作于2023年2月2、为了使模块尽可能独立，要求（）A、模块的内聚程度要尽量高，且各模块间的耦合程度要尽量强B、模块的内聚程度要尽量高，且各模块间的耦合程度要尽量弱C、模块的内聚程度要尽量低，且各模块间的耦合程度要尽量弱D、模块的内聚程度要尽量低，且各模块间的耦合程度要尽量强分析：耦合：两个或两个以上模块之间关联的紧密程度。内聚：衡量一个模块内部各个元素彼此结合的紧密程度。耦合性和内聚性是模块独立的两个定性标准。耦合与内聚是相互关联的。一般较优秀的软件设计，应尽量做到高内聚，低耦合，即减弱模块之间的耦合性和提高模块的内聚性，有利于提高模块的独立性。第34页，课件共73页，创作于2023年2月3、下列描述中正确的是（）A、程序就是软件B、软件开发不受计算机系统的限制C、软件既是逻辑实体，又是物理实体D、软件是程序、数据与相关文档的集合分析：1、软件：是计算机系统中与硬件相互依赖的另一部分，包括程序、数据和相关文档的完整集合；2、程序：是软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算机执行的指令序列。3、数据：是使程序能正常操纵信息的数据结构。4、文档：是与程序的开发、维护和使用有关的图文资料。第35页，课件共73页，创作于2023年2月4、诊断和改正程序中错误的工作通常称为______________。分析：程序调试：指在发生程序错误的情况下，确定出错的位置并纠正错误，其中关键是要确定出错的位置。程序调试主要在开发阶段。第36页，课件共73页，创作于2023年2月5、下列叙述中正确的是（）A、程序设计就是编制程序B、程序的测试必须由程序员自己去完成C、程序经调试改错后还应进行再测试D、程序经调试改错后不必进行再测试6、下列描述中正确的是（）A、软件工程只是解决软件项目的管理问题B、软件工程主要解决软件产品的生产率问题C、软件工程的主要思想是强调在软件开发过程中需要应用工程化原则D、软件工程只是解决软件开发中的技术问题分析：软件工程是用工程、科学和数学的原则与方法研制、维护计算机软件的有关技术及管理方法，由于软件开发中面临着纷繁复杂的问题，所以强调用工程化的原则去处理。第37页，课件共73页，创作于2023年2月7、在软件设计中，不属于过程设计工具的是（）A、PDL(过程设计语言)B、PAD图C、N-S图D、DFD图分析：

DFD(数据流图)是常用的结构化分析工具；

PDL、PAD、N-S是常见的过程设计工具，其中PAD、N-S属于图形工具，PDL属于语言工具。第38页，课件共73页，创作于2023年2月8、下列叙述中正确的是（）A、软件交付使用后还需要再进行维护B、软件工具交付使用就不需要再进行维护C、软件交付使用后其生命周期就结束D、软件维护是指修复程序中被破坏的指令9、两个或两个以上模块之间关联的紧密程度称为

A、耦合度B、内聚度

C、复杂度D、数据传输特性

第39页，课件共73页，创作于2023年2月10、下列叙述中正确的是（）

A、软件测试应该由程序开发者来完成

B、程序经调试后一般不需要再测试

C、软件维护只包括对程序代码的维护

D、以上三种说法都不对

第40页，课件共73页，创作于2023年2月11、程序测试分为静态分析和动态测试。其中__________是指不执行程序,而只是对程序

文本进行检查,通过阅读和讨论,分析和发现程序中的错误。分析：1、软件测试的方法：静态测试和动态测试。2、静态分析(静态测试)：无须执行被测代码，而是借助专用的软件测试工具评审软件文档或程序，度量程序静态复杂度，检查软件是否符合编程标准，借以发现编写的程序的不足之处，减少错误出现的概率。3、动态测试：使被测代码在相对真实环境下运行，从多角度观察程序运行时能体现的功能、逻辑、行为、结构等的行为，以发现其中的错误现象。第41页，课件共73页，创作于2023年2月12、下列选项不符合良好程序设计风格的是________。A、源程序要文档化B、数据说明的次序要规范化C、避免滥用goto语句D、模块设主地要保证高耦合、高内聚第42页，课件共73页，创作于2023年2月13、从工程管理角度，软件设计一般分为两步完成，它们是________。A、概要设计与详细设计B、数据设计与接口设计C、软件结构设计与数据设计D、过程设计与数据设计分析：1、从工程管理角度来看，软件设计一般分为两步：概要设计和详细设计。2、从技术观点来看，软件设计包括结构设计、数据设计、接口设计、过程设计四个步骤。第43页，课件共73页，创作于2023年2月14、下列选项中不属于软件生命周期开发阶段任务的是________。A、软件测试B、概要设计C、软件维护D、详细设计分析：1、通常把软件产品从提出、实现、使用、维护到停止使用退役的过程称为软件生命周期。2、软件生命周期分为3个时期共8个阶段：软件定义期：包括问题定义、可行性研究和需求分析三个阶段；软件开发期：包括概要设计、详细设计、实现和测试四个阶段；运行维护期：运行维护阶段。第44页，课件共73页，创作于2023年2月15、下列软件系统结构图

的宽度为__________。分析：宽度：整体控制跨度，即各层中所含的模块数的最大值。16、___________的任务是诊断和改正程序中的错误。第45页，课件共73页，创作于2023年2月17、在结构化程序设计中，模块划分的原则是___________。A）各模块应包括尽量多的功能。B）各模块的规模应尽量大。C）各模块之间的联系应尽量紧密。D）模块内具有高内聚度，模块间具有低耦合度。

第46页，课件共73页，创作于2023年2月18、下列叙述中正确的是______.A）软件测试的主要目的是发现程序中的错误。B）软件测试的主要目的是确定程序中错误的位置。C）为了提高软件测试的效率，最好由程序员自己来完成软件测试的工作。D）软件测试是证明软件没有错误。第47页，课件共73页，创作于2023年2月19、软件测试分为白盒和黑盒测试。等价类划分法属于______测试。分析：1、软件动态测试分为：白盒测试和黑盒测试。2、白盒测试：在程序内部进行，主要用于完成软件内部操作的验证。白盒测试的基本原则是：保证所测模块中每一独立路径至少执行一次；保证所测模块所有判断的每一个分支至少执行一次；验证所有内部数据结构的有效性。主要白盒测试的方法有逻辑覆盖方法和基本基路径测试方法。3、黑盒测试：根据程序规格说明所规定的功能来设计测试用例，它不考虑程序的内部结构和处理过程。常用的黑盒测试方法有：等价类划分法、边界分析法、错误猜测法与因果图等等。第48页，课件共73页，创作于2023年2月20、软件生命周期可以分为多个阶段，一般分为定义阶段、开发阶段和维护阶段。编码和测试属于________阶段。第49页，课件共73页，创作于2023年2月21、在结构化分析使用的数据流图(DFD)中，利用_________对其中的图形元素进行确切解释。分析：数据字典(DD)：用来定义数据流图中的各个成分的具体含义。数据字典的任务是对于数据流图中出现的所有被命名的图形元素在数据字典中作为一个词条加以定义，使得每一个图形元素的名字都有一个确切的定义。第50页，课件共73页，创作于2023年2月22、软件是指____.Ａ）程序Ｂ）程序和文档Ｃ）算法加数据结构Ｄ）程序、数据与相关文档的完整集合第51页，课件共73页，创作于2023年2月23、软件调试的目的是_____.A）发现错误B）改正错误C）改善软件的性能D）验证软件的正确性第52页，课件共73页，创作于2023年2月24、下列叙述中正确的是_____.A）程序执行的效率与数据的存储结构密切相关。B）程序执行的效率只取决于程序的控制结构。C）程序执行的效率只取决与所处理的数据量。D）以上三种说法都不对。第53页，课件共73页，创作于2023年2月25、软件需求规格说明书应具有完整性、无歧义性、可验证性、可修改性等特性，其中最重要的是_____.26、在两种基本测试方法中,________测试的原则之一是保证所测模块中每一个独立路径至少要执行一次。第54页，课件共73页，创作于2023年2月27、在进行模块测试时，要为每个被测试的模块另外设计两类模块：驱动模块和承接模块(桩模块)。其中___________的作用是将测试数据传送给被测试的模块，并显示被测试模块所产生的结果。第55页，课件共73页，创作于2023年2月四、数据库设计基础1、数据库（DB）、数据库系统（DBS）、数据库管理系统（DBMS）三者之间的关系是_____________________.分析：数据库系统(DBS)：由数据库、数据库管理系统、数据库管理员、硬件平台和软件平台五个部分构成的,DBMS是核心。第56页，课件共73页，创作于2023年2月2、数据独立性分为逻辑独立性与物理独立性。当数据的存储结构改变时，其逻辑结构可以不变，因此，基于逻辑结构的应用程序不必修改，称为_______________.分析：物理独立性:指数据的存储结构与逻辑结构之间的转换,即当数据的存储结构改变时,数据的逻辑结构不变,从而使得应用程序不必改变.逻辑独立性:指数据的总体逻辑结构与局部逻辑结构之间的转换,即当数据的总体逻辑结构改变时,可以保持局部逻辑结构不变,因而基于局部逻辑结构的应用程序也可以不必改变.第57页，课件共73页，创作于2023年2月3、用二维表格结构来表示实体及实体之间联系的数据模型称为___________.4、用树型结构表示实体之间联系的模型是___________.5、数据库设计的根本目标是要解决_______问题。第58页，课件共73页，创作于2023年2月6、在关系数据库中，把数据表示成二维表，每一个二维表称为__________.7、对于关系的描述，正确的是（）A、同一个关系中允许有完全相同的元组B、同一个关系中元组必须按关键字升序存放C、在一个关系中必须将关键字作为该关系的第一个属性D、同一个关系中不能出现相同的属性名第59页，课件共73页，创作于2023年2月8、专门的关系运算不包括下列中的（）A、联接运算B、选择运算C、投影运算D、交运算分析：专门的关系运算：选择、投影和联接。传统的集合运算：并、交和差。第60页，课件共73页，创作于2023年2月9、从关系模式中指定若干个属性组成新的关系的运算称为（）A、联接B、投影C、选择D、排序10、关系运算中的选择运算是（）A、从关系中找出满足给定条件的元组的操作B、从关系中选择若干个属性组成新的关系的操作C、从关系中选择满足给定条件的属性的操作D、A和B都对第61页，课件共73页，创作于2023年2月11、设有部门和职员两个实体，每个职员只能属于一个部门，一个部门可以有多名职员，则部门与职员之间的联是_________________.12、如果一个班只能有一个班长，而且一个班长不能同时担任其他班的班长，班级和班长两个实体之间的关系属于________________.13、“商品”和“顾客”两个实体集之间的联系一般是_________________.14、在奥运会游泳比赛中，一个游泳运动员可以参加多项比赛，一个游泳比赛项目可以有多个运动员参加，游泳运动员与游泳比赛项目两个实体之间的联系是_________________.第62页，课件共73页，创作于2023年2月15、数据库系统与文件系统的最主要区别是（）A、数据库系统复杂，而文件系统简单B、文件系统不能解决数据冗余和数据独立性问题，而数据库系统可以解决C、文件系统只能管理程序文件，而数据库系统能够管理各种类型的文件D、文件系统管理的数据量较少，而数据库系统可以管理庞大的数据量第63页，课件共73页，创作于2023年2月16、数据独立性是数据库技术的重要特点之一。所谓数据独立性是指（）A、数据与程序独立存放B、不同的数据被存放在不同的文件中C、不同的数据只能被对应的应用程序所使用D、以上三种说法都不对分析：数据独立性是数据与程序间的互不依赖性，即数据库中数据独立于应用程序而不依赖于应