计算机二级公共基础知识高频考点归纳总结

计算机二级公共基础知识高频考点归纳总结数据结构与算法算法算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令。算法的基本特征可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成。确定性：算法的每一步骤都必须有明确的定义，不允许有歧义。有穷性：算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。拥有足够的情报：算法的执行结果与输入的初始数据有关，必须有足够的输入信息才能使算法正常执行。算法复杂度时间复杂度：是指执行算法所需要的计算工作量。一般来说，算法的时间复杂度是问题规模n的函数，记作T(n)=O(f(n))，表示随问题规模n的增大，算法执行时间的增长率和f(n例如，对于一个简单的线性查找算法，在最坏情况下，需要遍历整个数组，时间复杂度为O(```pythondeflinear_search(arr,target):foriinrange(len(arr)):ifarr[i]==target:returnireturn-1```空间复杂度：是指执行这个算法所需要的内存空间。同样，空间复杂度也是问题规模n的函数，记作S(n)```pythondeffibonacci(n):ifn<=1:returnnreturnfibonacci(n1)+fibonacci(n2)```数据结构的基本概念数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据的逻辑结构线性结构：数据元素之间存在一对一的线性关系，如线性表、栈、队列等。非线性结构：数据元素之间存在一对多或多对多的关系，如树、图等。数据的存储结构顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元里，其优点是可以随机存取，缺点是插入和删除操作效率低。链式存储：不要求逻辑上相邻的元素在物理位置上也相邻，而是通过指针来表示元素之间的逻辑关系，其优点是插入和删除操作效率高，缺点是不能随机存取。线性表及其顺序存储结构线性表是由n(顺序表的基本操作插入操作：在顺序表的第i个位置插入一个新元素，需要将第i个及以后的元素依次后移一位。插入操作的时间复杂度为O(```pythondefinsert(arr,i,value):ifi<0ori>len(arr):returnarrarr.append(None)forjinrange(len(arr)1,i,-1):arr[j]=arr[j1]arr[i]=valuereturnarr```删除操作：删除顺序表的第i个元素，需要将第i+1个及以后的元素依次前移一位。删除操作的时间复杂度为```pythondefdelete(arr,i):ifi<0ori>=len(arr):returnarrforjinrange(i,len(arr)1):arr[j]=arr[j+1]arr.pop()returnarr```栈和队列栈栈是一种后进先出（LIFO）的线性表，只能在栈顶进行插入和删除操作。栈的基本操作：入栈：将元素插入栈顶。出栈：将栈顶元素删除。```pythonclassStack:def__init__(self):self.items=[]defpush(self,item):self.items.append(item)defpop(self):ifnotself.is_empty():returnself.items.pop()returnNonedefis_empty(self):returnlen(self.items)==0```栈的应用：表达式求值、括号匹配等。队列队列是一种先进先出（FIFO）的线性表，只能在队尾进行插入操作，在队头进行删除操作。队列的基本操作：入队：将元素插入队尾。出队：将队头元素删除。```pythonclassQueue:def__init__(self):self.items=[]defenqueue(self,item):self.items.append(item)defdequeue(self):ifnotself.is_empty():returnself.items.pop(0)returnNonedefis_empty(self):returnlen(self.items)==0```队列的应用：任务调度、广度优先搜索等。树与二叉树树的基本概念树是n(n≥0)个结点的有限集合，当n=0二叉树的定义及其性质定义：二叉树是每个结点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。性质：在二叉树的第i层上至多有个结点（i≥1深度为k的二叉树至多有1个结点（k≥对任何一棵二叉树T，如果其终端结点数为，度为2的结点数为，则=+1。二叉树的遍历前序遍历：根结点->左子树->右子树。```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefpreorder_traversal(root):ifrootisNone:return[]return[root.val]+preorder_traversal(root.left)+preorder_traversal(root.right)```中序遍历：左子树->根结点->右子树。```pythondefinorder_traversal(root):ifrootisNone:return[]returninorder_traversal(root.left)+[root.val]+inorder_traversal(root.right)```后序遍历：左子树->右子树->根结点。```pythondefpostorder_traversal(root):ifrootisNone:return[]returnpostorder_traversal(root.left)+postorder_traversal(root.right)+[root.val]```查找技术顺序查找顺序查找是一种最简单的查找方法，它从线性表的一端开始，依次将线性表中的元素与给定的值进行比较，直到找到匹配的元素或遍历完整个线性表。顺序查找的时间复杂度为O(二分查找二分查找要求线性表必须是有序的。它的基本思想是将线性表分成两部分，取中间元素与给定的值进行比较，如果中间元素等于给定的值，则查找成功；如果中间元素大于给定的值，则在左半部分继续查找；如果中间元素小于给定的值，则在右半部分继续查找。二分查找的时间复杂度为O(```pythondefbinary_search(arr,target):left,right=0,len(arr)1whileleft<=right:mid=(left+right)//2ifarr[mid]==target:returnmidelifarr[mid]<target:left=mid+1else:right=mid1return-1```排序技术冒泡排序冒泡排序是一种简单的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。冒泡排序的时间复杂度为O(```pythondefbubble_sort(arr):n=len(arr)foriinrange(n):forjinrange(0,ni1):ifarr[j]>arr[j+1]:arr[j],arr[j+1]=arr[j+1],arr[j]returnarr```选择排序选择排序是一种简单直观的排序算法，它首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。选择排序的时间复杂度为O(```pythondefselection_sort(arr):n=len(arr)foriinrange(n):min_idx=iforjinrange(i+1,n):ifarr[j]<arr[min_idx]:min_idx=jarr[i],arr[min_idx]=arr[min_idx],arr[i]returnarr```插入排序插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序的时间复杂度为O(```pythondefinsertion_sort(arr):foriinrange(1,len(arr)):key=arr[i]j=i1whilej>=0andkey<arr[j]:arr[j+1]=arr[j]j-=1arr[j+1]=keyreturnarr```程序设计基础程序设计方法与风格良好的程序设计风格可以提高程序的可读性、可维护性和可扩展性。以下是一些建议：源程序文档化：包括程序注释、变量命名等。注释可以分为序言性注释和功能性注释，变量命名应具有一定的含义。数据说明的方法：数据说明的次序应规范化，例如按常量、变量的顺序说明。语句的结构：语句应该简单直接，避免复杂的嵌套和转向。输入和输出：输入输出的方式和格式应尽量方便用户使用。结构化程序设计结构化程序设计的基本思想是采用自顶向下、逐步求精的设计方法和单入口单出口的控制结构。结构化程序的基本结构顺序结构：按照语句的先后顺序依次执行。选择结构：根据条件的真假选择不同的执行路径，如`if-else`语句。```pythonx=10ifx>5:print("x大于5")else:print("x小于等于5")```循环结构：根据条件的真假重复执行一段代码，如`for`循环和`while`循环。```pythonfor循环foriinrange(5):print(i)while循环i=0whilei<5:print(i)i+=1```面向对象的程序设计面向对象的程序设计以对象为核心，将数据和操作数据的方法封装在一起。面向对象的基本概念对象：是系统中用来描述客观事物的一个实体，它是构成系统的一个基本单位。对象由属性和方法组成。类：是具有相同属性和方法的对象的集合，它是对象的抽象。继承：是指一个类可以继承另一个类的属性和方法，从而实现代码的复用。多态：是指同一个方法可以根据对象的不同类型而表现出不同的行为。```python定义一个类classAnimal:def__init__(self,name):=namedefspeak(self):pass定义一个子类，继承自Animal类classDog(Animal):defspeak(self):returnf"{}汪汪叫"创建对象dog=Dog("旺财")print(dog.speak())```软件工程基础软件工程基本概念软件工程是应用计算机科学、数学及管理科学等原理，开发软件的工程。它采用工程的概念、原理、技术和方法来开发与维护软件。软件生命周期软件生命周期是指软件产品从提出、实现、使用维护到停止使用退役的整个过程，一般包括可行性研究与计划制定、需求分析、软件设计、软件实现、软件测试、运行和维护等阶段。结构化分析方法结构化分析方法是一种面向数据流的需求分析方法，它的基本思想是自顶向下、逐步分解。数据流图（DFD）数据流图是一种图形化的工具，用于描述系统中数据的流动和处理过程。它主要由数据流、加工、数据存储和外部实体组成。数据字典（DD）数据字典是对数据流图中所有元素的定义和说明，它是数据流图的补充和细化。结构化设计方法结构化设计方法是一种面向数据流的设计方法，它的基本思想是将软件系统划分为若干个模块，每个模块具有相对独立的功能。软件设计的基本原理抽象：将事物的本质特征抽取出来，忽略非本质特征。模块化：将软件系统分解为若干个模块，每个模块具有相对独立的功能。信息隐蔽：将模块的实现细节隐藏起来，只对外提供必要的接口。模块独立性：衡量模块独立性的两个标准是内聚性和耦合性。内聚性是指模块内部各元素之间的联系紧密程度，耦合性是指模块之间的联系紧密程度。软件测试软件测试是为了发现软件中的错误而执行程序的过程。测试方法静态测试：不执行程序，通过对程序的代码、文档等进行审查来发现错误。动态测试：执行程序，通过输入测试用例来发现错误。测试用例设计黑盒测试：不考虑程序的内部结构，只根据程序的功能来设计测试用例。常见的黑盒测试方法有等价类划分法、边界值分析法等。白盒测试：考虑程序的内部结构，根据程序的逻辑来设计测试用例。常见的白盒测试方法有语句覆盖、判定覆盖、条件覆盖等。软件维护软件维护是指在软件运行和使用过程中，对软件进行修改