算法的有穷性是指算法必须能在有限的时间里做完

全国计算机二级公共基础知识必背考点1. 算法的有穷性是指算法必须能执行有限个步骤之后终止.2. 算法的时间复杂度是指算法在执行过程中所需要的基本运算次数3. 队列、栈、线性表属于线性数据结构，二叉树不属于4. 数据的存储结构是指：数据的逻辑结构在计算机中的表示5. 一个逻辑数据结构可有多种存储结构，且各种存储结构影响数据处理的效率6. 线性链表是线性表的链式存储结构7. 栈是先进后出、后进先出的线性链表，具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针，是特殊的线性表，只能在一端插入或者删除元素8. 线性链表存储空间不一定连续，且各元素的存储顺序是任意的9. 在深度为7 的满二叉树中，叶子节点的个数为：6410. 能用二分法查找的是顺序存储的有序线性表11. 对长度为N 的线性表进行顺序查找，在最坏的情况下需要比较的次数为：N12. 对于长度为N 的线性表，在最坏的情况下，下列各排序法所对应的比较次数中正确的是：快速排序为N(N-1)/213. 算法的复杂度包括时间复杂度和空间复杂度14. 算法在执行过程中所需要的存储空间称为算法的空间复杂度15. 问题处理方案的正确而完整的描述称为算法16. 数据的逻辑结构在计算机存储控件中的存放方式称为数据的存储结构或者物理结构或者物理存储结构17. 按照逻辑结构分类，数据结构可以分为线性结构和非线性结构，二叉树属于非线性结构18. 数据结构分为逻辑结构和存储结构，循环队列属于存储结构19. 某二叉树中度为2 的结点有18 个，则该二叉树中共有19 个叶子结点20. 一颗二叉树第六层(根节点为第一层)的结点数最多为32 个21. 对长度为10 的线性表进行冒泡排序，最坏的情况下需要比较的次数为4522. 程序经调试改错后还应进行再调试23. 符合结构化程序设计风格的是使用顺序、选择和重复三种基本控制结构标示程序的控制结构24. 结构化程序设计的一种基本方法是逐步求精法、自顶向下、模块法25. 在面向对象的方法中，一个对象请求另一个对象为其服务的方式是通过发送消息26. 在软件工程学中，我们把一组具有相同的数据结构和相同的行为特征的对象的集合定义为类27. 面向对象的方法有对象/继承/类28. 在面向对象的方法中，类的实例称为对象9. 在面向对象的方法中，类描述的是具有相同属性与操作的一组对象30. 结构化程序设计的3 种基本逻辑机构为顺序、选择和重复(循环)31. 在面向对象的方法中，类之间共享属性和操作的机制称为继承32. 软件是程序、数据与相关文档的集合33. 在软件开发中，属于设计阶段的是：数据结构设计、给出系统模块结构、定义模块算法34. 软件工程的主要思想是强调在软件开发的过程中需要应用工程化原则35. 软件交付使用后还应进行维护36. 在结构化方法中，用数据流程图(DFD )作为描述工具的软件开发阶段是需求分析37. 软件设计的原则有抽象、模块化、信息隐蔽38. 为了是模块尽可能独立，需求模块的内聚程度要尽量高，且各模块的耦合程度要尽量弱39. 在软件设计中，属于过程设计工具的是：PDL 过程设计语言、PAD 图、N-S 图40. 软件测试的目的是尽可能多地发现程序中的错误41. 软件需求阶段的工作，可以分为四个方面：需求获取、需求分析、编写需求规格说明书和需求评审42. 在结构化方法中，软件功能分解属于总体设计阶段43. 软件工程的三要素：工具过程方法44. 若按功能划分，软件测试的方法通常分为白盒测试和黑盒测试45. 在进行模块测试时，要为每个被测试的模块另外设计两类模块：驱动模块和承接模块(桩模块)，其中驱动模块的作用是将测试数据传送给被测试的模块，并显示被测试模块的测试结果46. 程序测试分为静态分析和动态测试，其中静态分析(静态测试)是指不执行程序，而只是对程序文本进行检查，通过阅读和讨论，分析和发现程序中的错误47. 诊断和改正程序中错误的工作通常称为调试48. 软件是程序、数据和文档的集合49. 软件工程研究的内容主要是软件开发技术和软件工程管理50. 数据库系统的核心是数据库管理系统51. 数据库系统的根本目标是解决数据共享问题52. 能给出数据库物理存储与物理存取方法的是内模式53. 在数据库的两极映射中，从概念模式到内模式的映射一般由数据库管理系统实现54. 支持数据库各种操作的软件系统叫作数据库管理系统55. 数据库(DB )\数据库系统(DBS )、数据库管理系统(DBMS )之间的关系是：DBS 包含DB 和DBMS56. 在关系数据库模型中，通常可以把字段称为属性，其值称为属性值57. 用树形结构来表示实体之间联系的模型称为层次模型58. 在E-R 图中，用来表示实体的图形是矩形59. 商品与顾客两个实体之间的联系一般是多对多60. 数据库系统在其内部分为三级模式，即概念模式、内模式和外模式，其中内模式给出了数据库中物理存储结构与物理存取方法62. 数据管理技术发展过程经过人工管理、文件系统和数据库系统三个阶段，其中数据独立性最高的阶段是数据库系统62. 数据独立性分为逻辑独立性和物理独立性，当数据的存储结构改变时，其逻辑结构可以不变，因此，基于逻辑结构的应用程序不必修改，称为物理独立性63.如果一个工人可以管理多台设备，而一个设备只被一个工人管理，则实体工人与实体设备之间存在一对多的关系64. 关系模型的完整性规则是对关系的某种约束条件，包括实体完整性、参照完整性和自定义完整性65. 在关系数据库中，把数据表示成二维表，每一个二维表称为关系或关系表66. 关系数据库管理系统能实现的专门关系运算包括选择、连接和投影。

二级MS Office分类模拟8一、选择题1、算法的有穷性是指A．算法程序的运行时间是有限的B．算法程序所处理的数据量是有限的C．算法程序的长度是有限的D．算法只能被有限的用户使用2、下列关于栈的描述中，正确的是A．在栈中只能插入元素B．在栈中只能删除元素C．只能在一端插入或删除元素D．只能在一端插入元素，而在另一端删除元素3、在一棵二叉树中，叶子结点共有30个，度为1的结点共有40个，则该二叉树中的总结点数共有______个。

A．89 B．93C．99 D．1004、对下列二叉树进行中序遍历的结果是A．ABCDEFGH B．ABDGEHCFC．GDBEHACF D．GDHEBFCA5、设有表示学生选课的三张表，学生表(学号，姓名，性别)，课程表(课程号，课程名)，选课成绩表(学号，课程号，成绩)，则选课成绩表的关键字为A．课程号，成绩 B．学号，成绩C．学号，课程号 D．学号，课程号，成绩6、详细设计主要确定每个模块具体执行过程，也称过程设计，下列不属于过程设计工具的是A．DFD图 B．PAD图C．N-S图 D．PDL7、下列关于软件测试的目的和准则的叙述中，正确的是A．软件测试是证明软件没有错误B．主要目的是发现程序中的错误C．主要目的是确定程序中错误的位置D．测试最好由程序员自己来检查自己的程序8、在E-R图中，用______来表示实体之间联系。

A．矩形 B．菱形C．椭圆形 D．正方形9、在数据库系统中，数据库用户能够看见和使用的局部数据的逻辑结构和特征的描述是 A．外模式 B．逻辑模式C．概念模式 D．物理模式10、A．C．T=R×S D．T=R/S11、现代计算机中采用二进制数字系统，是因为它A．代码表示简短，易读B．物理上容易表示和实现，运算规则简单，可节省设备且便于设计C．容易阅读，不易出错D．只有0和1两个数字符号，容易书写12、二进制数1001001转换成十进制数是A．72 B．71C．75 D．7313、下列叙述中，正确的是A．用高级程序语言编写的程序称为源程序B．计算机能直接识别并执行用汇编语言编写的程序C．机器语言编写的程序执行效率最低D．高级语言编写的程序的可移植性最差14、王码五笔字型输入法属于A．音码输入法 B．形码输入法C．音形结合的输入法 D．联想输入法15、操作系统的主要功能是A．对用户的数据文件进行管理，为用户管理文件提供方便B．对计算机的所有资源进行统一控制和管理，为用户使用计算机提供方便C．对源程序进行编译和运行D．对汇编语言程序进行翻译16、随机存储器中，有一种存储器需要周期性的补充电荷以保证所存储信息的正确，它称为A．静态RAM(SRAM) B．动态RAM(DRAM)C．RAM D．Cache17、 KB(千字节)是度量存储器容量大小的常用单位之一，1KB等于A．1000个字节 B．1024个字节C．1000个二进制位 D．1024个字18、 Internet中不同网络和不同计算机相互通信的基础是A．ATM B．TCP/IPC．Novell D．X.2519、电话拨号连接是计算机个人用户常用的接入因特网的方式。

数据结构与算法基础知识总结1 算法算法:是指解题方案的准确而完整的描述。

算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。

算法的基本特征：是一组严谨地定义运算顺序的规则,每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。

特征包括:（1）可行性；（2)确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性,算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报.算法的基本要素：一是对数据对象的运算和操作;二是算法的控制结构。

指令系统：一个计算机系统能执行的所有指令的集合.基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输。

算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。

算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。

算法空间复杂度是指执行这个算法所需要的内存空间。

2 数据结构的基本基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构;（2)在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。

数据结构是指相互有关联的数据元素的集合.数据的逻辑结构包含：（1）表示数据元素的信息；（2)表示各数据元素之间的前后件关系.数据的存储结构有顺序、链接、索引等.线性结构条件：（1）有且只有一个根结点；(2）每一个结点最多有一个前件，也最多有一个后件。

非线性结构：不满足线性结构条件的数据结构。

3 线性表及其顺序存储结构线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的.在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件.非空线性表的结构特征：(1）且只有一个根结点a1，它无前件；(2)有且只有一个终端结点an，它无后件；（3)除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件.结点个数n称为线性表的长度，当n=0时，称为空表。

2024年计算机二级MS office真题及解析试卷四考试方式：上机考试，考试时长120分钟，满分100分。

操作系统：中文版Windows7考试环境：Microsoft Office 2016一、单项选择题（每题1分，共20分）1.算法的有穷性是指（ ）A.算法程序的运行时间是有限的B.算法程序所处理的数据量是有限的C.算法程序的长度是有限的D.算法只能被有限的用户使用【解析】算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。

2.下列数据结构中，属于非线性结构的是（ ）A.循环队列B.带链队列C.二叉树D.带链栈【解析】根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类：线性结构和非线性结构。

循环队列、带链队列和带链栈都是线性结构，而二叉树是非线性结构。

3.下列叙述中正确的是（ ）A.栈是“先进先出”的线性表B.队列是“先进后出”的线性表C.循环队列是非线性结构D.）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构【解析】本题主要考查了栈、队列、循环队列的概念，栈是先进后出的线性表，队列是先进先出的线性表。

根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。

有序线性表既可以采用顺序存储结构，又可以采用链式存储结构。

4.下列数据结构中，能够按照“先进后出”原则存取数据的是 （ ）A.循环队列B.栈C.队列D.二叉树【解析】栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据；队列是“先进先出” （FIFO）或“后进后出” （LILO）的线性表。

5.下列选项中不属于结构化程序设计原则的是（ ）A.可封装B.自顶向下C.模块化D.逐步求精【解析】结构化设计方法的主要原则可以概括为自顶向下、逐步求精、模块化、限制使用GOTO语句。

6.软件详细设计产生的图如下图所示，则该图是（ ）A.N-S图B.PAD图C.程序流程图D.E-R【解析】程序流程图是指使用流程图和流程线表示程序的执行流程。

第四章练习题答案(1) 下面叙述正确的是______。

(C)A）算法的执行效率与数据的存储结构无关B）算法的空间复杂度是指算法程序中指令（或语句）的条数C）算法的有穷性是指算法必须能在执行有限个步骤之后终止D）以上三种描述都不对(2) 算法的时间复杂度是指______。

(C)A. 执行算法程序所需要的时间B. 算法程序的长度C. 算法执行过程中所需要的基本运算次数D. 算法程序中的指令条数(3) 算法的空间复杂度是指______。

(D)A. 算法程序的长度B. 算法程序中的指令条数C. 算法程序所占的存储空间D. 算法执行过程中所需要的存储空间(4) 下列叙述中正确的是______。

(B)A) 算法的效率只与问题的规模有关，而与数据的存储结构无关B) 算法的时间复杂度是指执行算法所需要的计算工作量C) 数据的逻辑结构与存储结构是一一对应的D) 算法的时间复杂度与空间复杂度一定相关(5）算法的有穷性是指______。

( A )A）算法程序的运行时间是有限的B）算法程序所处理的数据量是有限的C）算法程序的长度是有限的D）算法只能被有限的用户使用(6) 数据的存储结构是指______。

( B )A. 数据所占的存储空间量B. 数据的逻辑结构在计算机中的表示C. 数据在计算机中的顺序存储方式D. 存储在外存中的数据(7) 下面描述线性表的链式存储结构错误的是______。

(A)A）线性表顺序存储B）线性表随机存储C）线性表的链式存储结构也称为线性链表D）线性表的链式存储结构只能顺序存取(8）数据的存储结构是指______。

（ B）A.数据所占的存储空间量B.数据的逻辑结构在计算机中的表示C.数据在计算机中的顺序存储方式D.存储在外存中的数据(9) 下列叙述中正确的是______。

（D ）A）一个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率(10）下列叙述中正确的是______。

数据结构作业答案单选题1、下列关于算法的基本特征，说法不正确的是（）。

能行性是算法中的每一个步骤必须能够实现且能达到预期的目的。

算法的确定性是指算法中的每一个步骤必须是有明确的定义，不允许模棱两可。

算法的有穷性是指算法必须能在有限的时间内做完。

算法与提供情报无关。

[D] 教师批改：D2、算法的时间复杂度取决于（）。

问题的规模待处理的数据的初态问题的难度 A 和 B[D] 教师批改：D3、下列选项中，不是算法基本特征的是（）。

可行性有穷性确定性高效率[D] 教师批改：D4、通常一个好的算法应达到的目标中，不包括（）。

正确性可读性技巧性健壮性[C] 教师批改：C5、在一般的计算机系统中，基本的运算和操作不包括（）。

语法处理算术运算关系运算数据传输[A] 教师批改：A6、工程上常用的分治法是（）。

列举法归纳法减半递推技术回溯法[C] 教师批改：C多选题7、算法设计的要求包括（）。

正确性可读性健壮性唯一性[ABC] 教师批改：A，B，C8、算法的时间复杂度应该与（）无关。

所使用的计算机程序设计语言基本运算的执行次数程序编制者[ABD] 教师批改：A，B，D9、下列关于算法的描述中，不正确的有（）。

算法即是计算机程序算法是解决问题的计算方法算法是排序方法算法是解决问题的有限运算序列[ABC] 教师批改：A，B，C填空题16、所谓算法是指（）。

教师批改：解题方案的准确而完整的描述17、算法的基本特征有（）、（）、（）和（）教师批改：能行性、确定性、有穷性和拥有足够的情报。

18、一个算法通常由两种基本要素组成，它们是（）和（）。

教师批改：算法中对数据的运算和操作。

算法的控制结构。

19、工程上常用的几种算法设计方法有列举法、（）、（）、（）、（）和回溯法。

教师批改：归纳法、递推、递归、减半递推技术。

20、算法的复杂度主要包括（）复杂度和（）复杂度。

教师批改：时间、空间综合题21、设给定3个整数a，b，c，试写出寻找这3个整数的中数的算法；并分析在平均情况与最坏情况下，该算法分别要做多少次比较？寻找这3个整数的中数的算法用C语言描述如下（中数m由函数值返回）：int mid ( int a, int b, int c){ int m ; m=a ;if ( m>=b ) { if (m>=c) { if ( b>=c ) m=b ; else m=c ; } }else { if ( m<=c) { if (b>=c) m=c; else m=b ; } }return ( m ) ;}假设a，b，c中的每一个数为中数的概率相等（均为1/3）。

数据结构与算法基础知识总结1 算法算法：是指解题方案的准确而完整的描述。

算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。

算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。

特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。

算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。

指令系统：一个计算机系统能执行的所有指令的集合。

基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。

算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。

算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。

算法空间复杂度是指执行这个算法所需要的内存空间。

2 数据结构的基本基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。

数据结构是指相互有关联的数据元素的集合。

数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。

数据的存储结构有顺序、链接、索引等。

线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。

非线性结构：不满足线性结构条件的数据结构。

3 线性表及其顺序存储结构线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。

在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。

无纸化真考试题库第35套1.下列叙述中正确的是A) 程序可以作为算法的一种表达方式B) 算法的有穷性是指算法的规模不能太大C) 算法的复杂度用于衡量算法的控制结构D) 算法的效率与数据的存储结构无关参考答案：A算法的有穷性是指操作步骤有限且能在有限时间内完成，如果一个算法执行耗费的时间太长，即使最终得出了正确结果，也是没有意义的。

B选项错误。

一个算法复杂度的高低体现在运行该算法所需要的计算机资源的多少。

C选项错误。

算法的效率是指算法执行的时间，算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量，这就与算法本身设计的优劣以及具体的编程实现有关，数据的存储结构会极大的影响程序的执行时间。

D选项错误。

算法在实现时需要用具体的程序设计语言来实现，所以程序可以作为实现算法的一种表达方式。

故选A选项2.某循环队列的存储空间为Q(1:m)，初始状态为front=rear=m。

现经过一系列的入队操作和退队操作后，front=m-1，rear=m，则该循环队列中的元素个数为A) m-1B) 1C) mD) 0参考答案：B循环队列长度为m，由初始状态为front=rear=m可知此时循环队列为空。

入队运算时，首先队尾指针(rear)进1（即rear+1），然后在rear指针指向的位置插入新元素。

特别的，当队尾指针rear=m+1时，置rear=1。

退队运算时，排头指针(front)进1（即front+1），然后删除front 指针指向的位置上的元素，当排头指针front=m+1时，置front=1。

从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素，则该循环队列中的元素个数为m-(m-1)=1。

故选择A选项3.能从任意一个结点开始没有重复地扫描到所有结点的数据结构是A) 循环链表B) 双向链表C) 二叉链表D) 有序链表参考答案：A在单链表的第一个结点前增加一个表头结点，队头指针指向表头结点，最后一个结点的指针域的值由NULL改为指向表头结点，这样的链表称为循环链表。

习题一一、选择题1、数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（B）和运算的学科。

A．结构B．关系C．运算D．算法2、在数据结构中，从逻辑上可以把数据结构分成（C）。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．逻辑结构和存储结构3、线性表的逻辑顺序和存储顺序总是一致的，这种说法（B）。

A．正确B．不正确C．无法确定D．以上答案都不对4、算法分析的目的是（C）。

A．找出算法的合理性B．研究算法的输人与输出关系C．分析算法的有效性以求改进D．分析算法的易懂性二、填空题1、数据是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，数据是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。

例如，数学中所用到的整数和实数，文本编辑所用到的字符串等。

2、数据元素是数据的基本单位，有些情况下也称为元素、结点、顶点、记录等。

3、数据项是数据不可分割的最小单元，是具有独立含义的最小标识单位。

例如构成一个数据元素的字段、域、属性等都可称之为_数据项。

4、简而言之，数据结构是数据之间的相互关系，即数据的组织形式。

5、数据的逻辑结构是指数据之间的逻辑关系。

逻辑结构是从逻辑关系上描述数据，它与具体存储无关，是独立于计算机的。

因此逻辑结构可以看作是从具体问题抽象出来的数学模型。

6、数据的存储结构指数据元素及其关系在计算机存储器内的表示。

存储结构是逻辑结构在计算机里的实现，也称之为映像。

7、数据的运算是指对数据施加的操作。

它定义在数据的逻辑结构之上，每种逻辑结构都有一个数据的运算。

常用的有：查找、排序、插人、删除、更新等操作。

8、数据逻辑结构可以分为四种基本的类型，集合结构中的元素除了仅仅只是同属于一个集合_，不存在什么关系。

9、数据逻辑结构的四种基本类型中，线性结构_中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。