二级公共基础知识考点

第一章数据结构和算法笔试部分经常通过算法的复杂性、数据结构的概念、堆栈、二叉树的遍历、二分法查找进行审查，读者应该集中学习这一部分。有关知识点的详细集中学习：1.算法的概念、算法的时间复杂性和空间复杂性的概念2.数据结构的定义、数据逻辑结构和物理结构的定义堆栈定义和计算，如何存储线性链接列表4.树和二叉树的概念，二叉树的基本特征，完整二叉树的概念，二叉树的遍历5.二分法6.气泡对齐方法测试点1算法的基本概念考试链接：试卷点1在笔试中的考试概率为30%，主要以填空形式出现，分值为2分，这个试卷点是知识内容，读者还需要理解算法中对数据的基本运算。测试点2算法复杂性考试链接：试卷点2是笔试中经常考试的内容，笔试中有70%的概率，主要以选择形式出现，2分，这个考试点是集中式内容，读者也应该知道算法时间复杂性和空间复杂性的概念。故障排除：算法的工作量是用什么计算的？算法的工作量计算为算法执行的基本操作数，算法执行的基本操作数为问题规模函数，即算法的工作量=f(n)。其中n是问题的大小。测试点3数据结构定义考试链接：试卷点3是笔试中经常考察的内容，笔试中有70%的概率，主要以选择形式出现，2分，这个考试点是知识内容，读者也应该知道数据的逻辑结构和存储结构的概念。试验点4线性结构和非线性结构考试链接：考试点4是在笔试中，即使考试不是经常审查的内容，读者也清楚笔试中发生的概率为30%，主要以空白填充的形式出现，分数2分被承认的资料。故障排除：空数据结构是线性结构还是非线性结构？空数据结构属于线性结构还是非线性结构取决于情况。如果根据线性结构的规则处理此数据结构的算法，则属于线性结构。否则，属于非线性结构。测试点5堆栈和基本运算考试链接：试卷点5是笔试中必不可少的内容，笔试中出现的概率为100%，主要以选择形式出现，评分值为2分，该试卷点重点讨论内容，读者要掌握堆栈的运算。提示：堆栈根据“先进先出”或“后进先出”原则组织数据，但是堆栈方式有多种，在考试问题中经常审查多种堆栈方式。测试点6线性链表的基本概念考试链接：考试点6在笔试中出现的概率为30%，主要以选择形式出现，分数为2分，这个考试点是认识内容。重点了解节点的配置。故障排除：在链结构中，存储空间位置关系和逻辑关系是什么？在链存储结构中，存储数据结构的存储空间可以是不连续的，每个数据节点的存储顺序和数据元素之间的逻辑关系可能不一致，数据元素之间的逻辑关系由指针域确定。测试点7树和二叉树及其基本特性考试链接：试卷分7是笔试中必须的内容，笔试中出现的概率为100%，主要以选择形式出现，有时也出现在空白的蔡氏，以分值2分的形式重点把握内容的考试场所。主要识别树和二进制树的特性。误解警告：完整的二进制树也是完整的二进制树，完整的二进制树通常不是完整的二进制树。要注意两者的差异。提示：在二叉树遍历中，无论是预遍历、中间遍历还是后遍历，二进制树叶节点的顺序都保持不变。测试点8二叉树遍历考试链接：考试点8在笔试中的考试概率为30%，分数为2分，读者应该熟悉各种巡回的具体算法，从两次巡回的结果中得出另一次巡回的结果。疑难解答：树和二进制树之间有何区别？在二进制树中，每个节点的度数最多为2。也就是说，所有子树(左侧或右侧的子树)也是二进制树，树结构中的每个节点都可以是随机的。寻找考试9顺序考试链接：考试点9在笔试中考试概率为30%，一般在选择题中分配2分，读者应具体掌握顺序查找算法。寻找考试点10二分法考试链接：考试点10在笔试中的考试概率为30%，一般来说，填空问题中的2分，要算出找到更多的比较次数，读者需要具体掌握2分查找法的算法。故障排除：两点查找方法适用于哪些情况？二进制查找方法仅适用于按顺序存储的有序表。此处的已排序表格表示线性表格中的元素没有按值降序排序(即，从小元素到大元素的相邻元素值相同)。此过程将持续到查找成功或子表长度为零。对于长度为n的对齐线性表格，最差的情况是两点查询仅需要进行log2n次比较。考试点11交换类排序方法考试链接：考试点11是比较难的内容，一般用选择题进行考试，考试概率为30%，分数约为2分，读者应该熟悉几种排序算法的基本过程。气泡排序方法和快速排序方法都是交换类排序方法。故障排除：冒泡排序和快速排序的平均运行时间分别是多少？冒泡排序方法的平均运行时间为O(n2)，快速排序方法的平均运行时间为O(nlog2n)。1.7盘柜详细信息一、选择题示例1算法的时间复杂性取决于_ _ _ _ _ _ _ _ _ _。(测试点2)a)问题的规模b)待定数据的初始状态c)问题的难度D)A)和b)解决方法：算法的时间复杂性不仅与问题的规模有关，而且与相同问题大小的输入数据有关。也就是说，与可以输入数据的所有值的范围、输入各种数据或数据集的概率有关。答案：d)示例2数据结构允许数据结构在逻辑上分为_ _ _ _ _ _ _ _ _ _ _ _ _。(测试点3)a)内部和外部结构b)线性和非线性结构c)小型和非小型结构d)动态和静态结构解决：逻辑结构反映数据元素之间的逻辑关系，线性结构表示数据元素之间的一对一关系，非线性结构表示数据元素之间的一对多或多对一关系，因此答案为b。答案：b)以下_ _ _ _ _ _ _ _不是堆栈的基本运算：(测试点5)a)确定堆栈是否为主堆栈b)将堆栈作为空堆栈放置c)删除堆栈顶部元素d)删除堆栈底部元素解释：堆栈的基本操作包括：堆栈、堆栈(删除堆栈顶部元素)、初始化、设置空状态、检查堆栈是空的还是已满的，以及提取堆栈顶部元素。答案：d)示例4不在关联列表中的特征是_ _ _ _ _ _ _ _ _ _ _。(测试点6)a)可以随机访问任何节点b)无需插入和删除元素c)不需要预先估计存储空间d。所需空间与其长度成正比解决方案：顺序表可以访问任何节点，连接的列表必须从第一个数据节点开始逐个查找每个节点。所以答案是a)。答案：a)示例5如果二进制树的后续遍历序列为DACBE，中间遍历序列为DEBAC，则相应的前置遍历序列为_ _ _ _ _ _ _ _ _ _ _ _ _。(测试点8)A)ACBEDB)DEABCC)DECABD)EDBAC语法分析：以下顺序为“左侧子树-右侧子树-根节点”:中间顺序遍历顺序为“左侧子树-根节点-右侧子树”；前顺序遍历顺序为“根节点-左侧子树-右侧子树”。根据各种巡回算法，很容易看出正向巡回序列是EDBAC。所以答案是d)。答案：d)(范例6)根据每个元素的值排序的定线表格(长度大于2)，针对指定的值k，分别使用顺序和次要查询方法寻找与k相同的元素。比较次数为s和b，查找失败时s和b的关系为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。(测试点9)A) s=bb) SBC) s log2n 1。答案：b)示例7在快速排序过程中，每个拆分将拆分的表(或子表)分为左右两个子表，考虑这两个子表，然后得出以下结论：正确的_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _(测试点11)a)左右两侧的子表格将分别对齐b)左侧子表中的元素不大于右侧子表中的元素c)左侧子表的长度小于右侧子表的长度d)左右两个子表中元素的平均值相同解决方案：快速排序的基本思路是：将要排序的表中的元素作为基线(通常是第一个元素)，将要排序的元素按照其左侧和右侧子表元素的排序代码小于或等于基线的排序代码的顺序进行排序，将右侧子表的排序代码设置为大于基线的排序代码，然后继续对两个子表进行排序，直到对整个表进行排序。答案：b)二、填空解决问题的准确完整说明称为_ _ _ _ _ _ _ _ _ _ _ _。(测试点1)解决：计算机故障排除的过程实际上是实现一种称为计算机算法的算法。答案：算法空数据结构被视为线性结构，并被视为_ _ _ _ _ _ _ _ _ _。(测试点4)分析：空数据结构是线性结构还是非线性结构，具体取决于具体情况。如果对数据结构的运算被视为线性结构，则属于线性结构，否则属于非线性结构。答案：路线结构示例3)如果树t的度为4，其中度为1、2、3和4的节点数分别为4、2、1和1，则t的叶节点数为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _(测试点7)解析：根据树状结构的特性：树状结构中的节点数目等于所有节点的度乘以其节点数目的总和加1。因此，树中的节点数为14 22 31 41 1=16。叶节点数等于树节点总数减去非零角度节点数16-(4 2 1)=8。答案：8示例4用二分法查找的存储结构仅限于_ _ _ _ _ _(测试点10)分析：两点查找(也称为半值查找)是一种有效的查找方法。但是，二进制查询有条件限制。这意味着表必须按顺序存储结构，表中的元素必须按关键字排序(升序或降序)。答案：顺序存储结构第二章编程基础对部分考生的调查和近年来的真文问题进行了总结分析，笔试部分经常测试结构程序设计的原则、对象方法的基本概念，因此读者应该重点学习这一部分。有关知识点的详细集中学习：1.结构化编程方法的四个原则2.对象、类、消息、继承的概念以及类和实例之间的区别考试点1结构化编程原理考试链接：试卷点1在笔试中出现的概率为30%，主要以选择题形式出现，分数为2分，该试卷点是知识内容，读者应该知道结构化编程方式的四大原则。故障排除：如何执行自上而下设计方法？编程时，首先要考虑整体，然后考虑细节。首先考虑全局目标，然后考虑本地目标。不要一开始就过分追求很多细节，先从最高综合目标开始设计，逐步完善问题。测试点2面向对象方法的基本概念考试链接：试卷点2是笔试中经常考察的内容，笔试中有70%的概率，主要以填空形式出现，评分值为2分，该试卷点是重点食内容，读者需要知道几个基本要素的定义，对象的特性，信息，继承，类的定义。误解警告：术语“对象”可以指特定对象或常规对象，而术语“实例”必须指向特定对象。故障排除：是否可以使用物理对象及其属性和操作？一辆汽车是包含汽车属性(颜色、型号等)及其行为(例如启动、刹车等)的对象。一个窗口是包含窗口属性(如大小、颜色等)及其操作(如打开、关闭等)的对象2.3案例的详细说明一、选择题【例1】结构化编程方法在_ _ _ _ _ _ _ _ _ _ _ _ _中提出。(测试点1)A) 1950年代b) 1960年代c)20世纪70年代d)20世纪80年代分析：20世纪70年代，有人提出了“结构化计划”的想法和方法。结构化编程方法引入了工程思想和结构化思维，大大改进了大型软件的开发和编程。答案：c)示例2结构化编程方法的主要原理有四种，不正确的是_ _ _ _ _ _ _ _ _ _ _。(测试点1)a)自上而下b)逐步细化c)模块化d) goto语句使用限制解释：结构化编程方法的主要原则如下：(1)由上而下：即先考虑整体，再考虑细节。首先考虑全局目标，然后考虑本地目标。(2)逐步细化：对于复杂的问题，必须设计一些子目标，逐步细化。(3)模块化：将程序要解决的总目标分解为子目标，然后将每个小目标进一步分解为称为一个模块的具体小目标。(4)限制使用goto语句。答案：a)示例3在面向对象的开发方法中，类和对象的关系是_ _ _ _ _ _ _ _ _ _ _。(测试点2)a)抽象和特定b)具体抽象c)部分和完整d)全部和部分解决：现实世界中的很多事物具有相似的特性，对具有相似属性和运算的对象进行分类。换句话说，类是具有公共属性的公共方法的对象的集合，是对象的抽象。描述该物件类型的所有物件性质，而物件是该类别的特定例证。所以这个问题的正确答案是a)项。答案：a)二、填空示例1基于面向对象方法中已存在的类定义创建新的类定义。这种方法称为_ _ _ _ _ _ _ _ _ _ _ _。(测试点2)解决：继承是面向对象方法的主要特征。继承是基于现有类定义创建新类的定义技术。可以将现有类引用为基类时，新类可以引用为派生类。答案：继承示例2对象的基本特征有_ _ _ _ _ _ _ _ _ _ _ _ _、分类、多态、封装和模块独立性良好等五个。(测试点2)解决方案：对象具有以下基本特性：(1)标志唯一性。可以区分对象，并通过对象的本质属性进行区分。(2)分类。属性和操作相同的对象可以抽象到类中。(3)多态性。同一操作可以是其他对象的行为。(4)封装性。可以仅查看对象的外部要素，而无需知道数据的具体结构和实现操作的算法。(5)模块独立性。物件导向是由资料和适用于此资料的作业组成的统一体。答案：标识唯一性根据收到的消息，对象执行操作，当同一消息接收到另一个对象时，可能会发生完全不同的行为，这种现象称为_ _ _ _