二级公共知识笔记

返回主页

1.算法 （1~2分）

两大要素：”确定方法” “确定步骤”

1.1 算法的特征 *

特征 含义
确定性 就是每条代码都有明确的含义，让其他人明确器含义及如何执行
可行性 就是这个算法得有用，可以实现运算结果
有穷性 算法得在”有限时间”，”有限步骤”得到结果
有足够的数据 算法要有输入和输出，要不然就不是算法

1.2算法设计的基本方法

基本方法 含义
举例法 就是把每个结果都罗列出来
归纳法 从特殊到一般，例如：猫A爱吃鱼，猫B爱吃鱼，所以猫爱吃鱼
递推法 从条件出发，推出结论，就是自己条件调用自己，例如S=300 ，递推公式：S=S*数字
递归法 函数自己调用自己，把问题逐层分解，最后归结为简单的问题
减半递推技术 把问题减半，在对比，例如：在0123456789，中查找7，就可以吧7跟5对比，，然后就只需要找3次
回溯法 试错法，一次一次式出答案

1.3 算法的复杂度(重点)

复杂度 含义
时间复杂度 执行算法过程中，所需要的基本运算次数
空间复杂度 执行算法过程中，所需要的内存空间(储存空间)

注意：一个算法的时间复杂度越高，消耗的时间不一定越长

执行算法过程中，所需要的内存空间(储存空间)

内存空间（包括”常用空间”,”临时空间”）

内存与外存

注意：算法的时间复杂度与空间复杂度”不相关”！

2.数据结构 (3~4分)

image-20220227204638412

数据结构：相互关联的数据元素的集合，例如：春夏春冬

程序设计的实质就是：好算法+好结构

2.1 线性表的基本概念

线性结构的4个的特征：

image-20220227205625415

2.2顺序表

线性表的顺序存储结构，简称：顺序表

顺序表的特点

2.3顺序表的运算

小贴士：遇到

image-20220227210315397

这种题，就直接模拟场景，带入值就行了

2.4 栈

栈就是个瓶子（一端开口，一端封闭），先进后出

img

栈顶(top)：可操作的端

栈底(bottom)：不可操作的端

2.4.1 栈的特点

1.先进后出

2.栈的基本运算：

3.只能操作栈顶(top)

提示：带链的栈就是每个元素都有一个指针

所以：

带链的栈：栈底指针在操作过程中会改变，

顺序栈：栈底指针在操作过程中不会改变

​ 栈顶的指针都是动态的

栈中，栈底指针不变，栈中指针随栈顶指针的变化而变化

2.5 队列

队列(queue) 就像管道， 两端开口 ， 先进先出，

是仅限于在队尾(rear)插入，在队头(front)删除的线性表

image-20220227213427466

2.5.1循环队列

就是将队列存储空间的最后一个位置绕道第一个位置，形成逻辑上的环状空间(没啥用)

小提示：循环队列中头指针(front)，和尾指针(rear),在题目中可以随便定义，因为是循环队列，因为是一个○圆圈

image-20220228091233248

考点总结

1.队列“先进先出”，出口为队头，进入为队尾

2.循环队列是队列的一种顺序储存结构，因此储存空间按顺序连续定义

3.循环队列是线性结构

4.队列元素的个数计算方法

2.6 线性链表

线性结构的顺序存储，为顺序表（栈，队列）

线性结构的链式存储，为线性链表

线性链表

里面每个元素是有2个部分组成：

2.6.1 线性链表的基本概念

2.6.2 带链的栈

栈是线性表，所以也可以采用链式存储

image-20220228201311384

an为栈顶指针指向第二个元素，a1位栈底指针为0

就是在每个元素都加上一个指针

2.6.3 带链的队列

队列是线性表，所以也可以采用链式存储

image-20220228201638959

a1为队头指向后件a2，an为队尾指向0

2.6.4 线性链表的基本运算

2.6.5 循环链表

对比与普通线性链表的特点：

本来an的指针为Null，现在指向了表头结点

image-20220228204558864

image-20220228204523729

image-20220228204535354

考点总结

真题(1):

image-20220228205042111

答案为：C

真题(2):

image-20220228205321710

答案为：A

小提示：顺序栈栈底操作不变，带链的栈所有元素都会变

真题(3):

image-20220228205618296

答案为：B

真题(4):

image-20220228205740962

答案为：C

小提示：插入删除是，只需要改变指针，所以储存空间，和逻辑顺序不需要一致

2.7 非线性结构(必考一题)

主要内容：

2.7.1树的基本概念：

树：最上面为根结点，下面都为结点(除了最后一层)，最后一层为叶子

image-20220301193705549

树是n(n>=0)个结点的有限集合T

T要满足：

1.有且只有特殊的结点，名字为根的结点

2.当你n>1时，其余结点可分为m个互不相等且有限的集T1，T2·········

其中每个集合本身有事一棵树

image-20220301194515118

2.7.2二叉树及其基本性质

二叉树：所有结点的叶子(叶子结点)最多为2

image-20220301194609291

二叉树的形态

image-20220301194849744

二叉树的基本术语

术语 概念
结点 表示数种的元素，包含，数据项，及若干子数的分支
叶子结点 也叫终端结点，是度为0的结点，也就是后件为0的结点
度 某个结点所拥有的后件的个数，例如：二叉树最多度为2
分支结点 度不为0的结点
结点的度 拥有结点子树的个数
数的深度 树中最大的层数

image-20220301200056464

答案为：2 ；2 ；0 ； 4 ；FJDH

二叉树的基本性质

1.一颗非空二叉树的i层最多 \(2^{i-1}\) 个结点

2.一颗深度为K的二叉树，最多有 \(2^k-1\)

个结点

3.一颗二叉树中度为0的结点总是比，度为2的结点多一个

验证：

image-20220301194609291

  1. 深度i为2时，结点为2，公式带入也为2
  2. 深度K为3时，结点一共为7，公式带入也为7

度为0个数：4 ； 度为1个数：2 ； 度为2个数：3

总结点个数=度为0个数+度为1个数+度为2个数

image-20220301203432797

就是在二叉树的基础上，所以结点都占满

image-20220301203921089

在满二叉树的情况下，以根结点分割，右侧最后一层叶子少若干个为完全二叉树

2.7.3 二叉树的存储结构

二叉树通常采用链式存储

image-20220301204612729

2.7.4 二叉树的遍历(难点)

遍历是按照指定的次序访问二叉树的每一个结点，使每个结点访问一次

image-20220301194609291

访问顺序为

2.8 查找技术

2.8.1顺序查找

2.8.2二分法查找

二分查找又称折半查找

总结

2.9 排序技术

image-20220302093628480

最快的为“堆排序法”，其次是“希尔排序法”

其他速度最快一样，速度都为 \(\frac{n(n-1)}{2}\) 的速度

冒泡排序

初始状态【6 8 5 7 4】从小到大

image-20220302095125675

找到最大值放到最后

image-20220302095522229

image-20220302100416337

image-20220302100443962

python中的冒泡排序简单实例

def bubbleSort(arr):
    n = len(arr) # 7
    # 遍历所有数组元素
    for i in range(n):
    	# i = 0~6
        for j in range(0, n-i-1):	# 7-0-1=6
            if arr[j] > arr[j+1] :	# 如果前一个比后一个大，就把两个索引交换位置
                arr[j], arr[j+1] = arr[j+1], arr[j]
 
arr = [64, 34, 25, 12, 22, 11, 90]
 
bubbleSort(arr)
 
print ("排序后的数组:")
for i in range(len(arr)):
    print(arr[i])

选择法排序法

就是第一个跟全表比较，然后找出最大(最小)的放在最前面，然后第二比较，直到最后一个元素为止

image-20220302193224021

堆排序法（效率最高）

堆的定义：

有n个元素，序列为（h1,h2,h3··········hn）当且仅当满足 $$ \begin{cases} hi >=h2i
hi>=h2i+1 \end{cases}

或

\begin{cases} hi <= h2i
hi<=h2i+1 \end{cases}

(i=1,2,3···,n/2) $$ 时称为堆，可以看出，堆顶的元素（第一个元素）必为最大（最小）

将数据以完全二叉树的表示堆结构

原数据：91,85,53,36,47,24,30,12

image-20220302193641101

image-20220302194810726

image-20220302195808410

得出

image-20220302195916590

然后将根结点换到倒数第二索引

image-20220302200104587

然后继续排序：找出所有左子树和右子树（重下往上找）找出最大值给根结点（不包括排好的结点）

image-20220302200228784

再把根结点放到倒数第三索引

image-20220302200414426

以此类推

总结与真题

类型 排序方法 含义 时间复杂度
交换类 快速排序 选择基准元素，通过交换划分，成两个序列 n(n-1)\2
交换类 冒泡排序 相邻元素比较，满足条件时交换 n(n-1)\2
插入类 简单插入 自己看去吧 n(n-1)\2
插入类 希尔排序（效率第二） 分割成若干个子序列，分别进行直接插入排序 n(n^1.5)
选择类 简单选择 扫描整个线性表，将最小的元素，交换到表最前面 n(n-1)\2
选择类 堆排序法（效率第一） 建堆，将堆排序，将对顶元素与堆最后一个元素交换，然后在排序 n log2n

真题1

image-20220302202755066

答案为：B

真题2

image-20220302202851802

答案为：A

真题3

image-20220302202954218

答案为：A

真题4

image-20220302203040490

答案为：C

真题5

image-20220302203230264

答案为D

真题6

image-20220302203648937

答案为：C

真题7

image-20220302204723377

答案为：B

3.程序设计

3.1 程序设计方法和风格

3.2 结构化程序设计

3.2.1 结构化程序设计原则和方法(考点)

3.2.2 结构化程序的基本结构和特点

著名的结构化程序由三大结构组成：

1.顺序结构

2.选择结构（分支结构）

3.循环结构（重复结构）

在python里

结构化程序特点：

每个控制结构只有

2.2.3 面向对象的基本概念

相关考题：

image-20220303170409893

答案为：B

image-20220303170454696

答案为：C

image-20220303170533605

答案为：C

image-20220303170629526

答案为：C

image-20220303170750391

答案为：C

4.软件工程基础 (2~3分)

软件定义：程序，数据，相关文档的集合

4.1软件工程基础的概念

4.1.1软件的分类：

4.1.2软件危机

软件危机是指在计算机软件的开发和维护过程中遇到一系列严重的问题

1.软件的需求增长，得不到满足

2.软件的开发成本和进度无法控制

3.软件的质量难以保障

4.软件的不可维护或维护程度低

5.软件的成本不断提高

6.软件开发生产效率赶不上硬件的发展和应用需求的增长

4.1.3 软件工程的概念

为消除软件危机，软件工程师解决问题的途径

软件工程：用工程、科学和数学的原理与方法研制、维护计算机软件的有关技术及管理方法

软件工程的三要素：（考点）

考题为欢乐4选1，

软件过程与软件生命周期：（考点）

软件过程：软件过程通常包含4种基本活动：

软件生命周期：软件周期可以划分成三个阶段（重点）（考点）

​ 定义阶段 —> 开发阶段 —> 维护阶段

软件生命周期，各个阶段的基本任务：（重点）

可行性研究 —> 需求分析 —> 软件设计 (总体设计) —> 软件编码 —> 软件测试 —> 软件运行维护

4.1.4 软件工程的目标与原则

包括了 软件开发技术、软件工程管理技术（基本不考）

4.2 结构化分析方法

主要内容：

4.2.1 需求分析与需求分析方法

1.需求分析

需求分析的工作（考点）

2.常见的需求分析方法

4.2.2 结构化分析方法

1.结构化分析方法的实质：（考点）

- 通过对用户的调查，以软件的需求为线索，获得当前系统的具体模型。

就是画一大堆图

2.结构化分析的常用工具（考点）

(1)数据流图：

数据流图是描述数据处理过程的工具。数据流图中的主要图像元素说明：

image-20220303203703373

一般是 ” 数据流 用什么 图形表示 “ – > 箭头

(2)数据字典（DD）：

例如：

存折 = 户名 + 账户 + 性质 + ······

户名=2{字母}24

性质=“1”··“6”

·····················

(3)判定数（了解）

image-20220303205243437

九折，了解

判定表（了解）

了解！！！！！！！！！！

4.2.3 软件需求规格说明书

软件需求规格说明书是描述需求中的重要文档，是软件需求分析的主要成果

作用：

特点：

4.3 结构化设计方法

4.3.1 软件设计的基本概念

1.软件设计基础

2.软件设计的基本原理

4.3.2 概要设计

1.概要设计（总体设计）的任务：

软件结构图（SC）相关术语（考点）

深度：表示控制的层数

宽度：整体控制的跨度（最大模块的层）

扇入：调用一个给定模块的模块个数

扇出：一个模块直接调用的其他模块的数量

image-20220304162409557

4.3.3 详细设计

详细设计的任务：

​ 为软件结构图（SC）的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构

image-20220304163635062

实例：

image-20220304163849823

image-20220304163955904

image-20220304164958067

while 条件成立 Until条件不成立

image-20220304165149896

4.4 软件测试

4.4.1 软件测试的目的

软件测试是为了发现错误而执行的过程

4.4.2 软件测试的准则

1.所有的测试都应追溯到需求

2.严格执行测试计划，排除测试的随意性

3.充分注意测试中的群集现象

4.程序员应避免检查自己的代码

5.穷举测试不可能

6.妥善保存相关资料

4.4.3 软件测试的方法与技术综述

对软件测试的方法和技术，可以从不同的角度加以分类 \(是否需要执行被测试的角度 \begin{cases} 静态测试\\ 动态测试 \end{cases}\)

image-20220304173409114

4.4.4 软件测试的策略

软件测试过程分4个步骤（黑盒测试）

4.5 软件的调试

4.5.1程序调试的基本概念

4.5.2调试的方法

相关考题

image-20220304200703426

答案为：D 数据流图>数据字典

image-20220304201913133

答案为：D

image-20220304202014491

答案为：B

image-20220304202104808

答案为：B

image-20220304202209822

答案为：C

image-20220304202334360

答案为：A

image-20220304202421588

答案为：A 功能（用户规格说明书有的）

image-20220304202617784

image-20220304203451158

答案为：D 集成测试是将所有模块集成在一起测试

5.数据库设计基础（1~2分S）

5.1 数据库系统的基本概念

5.1.1 数据、数据库、数据库管理系统

1.数据（概念）

​ 数据（data）是描述事物的符号记录

2.数据库

​ 数据库（database 简称DB）数据的集合

3.数据库管理系统

​ 数据库管理系统（database magagement system）DBMS

是一种系统软件，负责数据库中的数据组织、数据操作、数据维护、控制以及保护和数据服务等

​ 数据库系统的核心：是数据库管理系统（考点）

为了完成以上功能，数据库管理系统提供相应数据语言（重点 - 考点）

4.数据库管理员（DBA）

主要工作：数据库设计、数据库维护、改善系统性能

5.数据库系统（DBS）

数据库系统是由数据库（db），数据库管理系统、数据库管理员、平台（硬件、软件（操纵系统））组成

6.数据库应用系统

利用数据库系统进行应用开发可够惨一个数据库应用系统

image-20220304211624721

数据 < 数据库 < 数据库管理系统(系统软件) < 数据库系统

5.1.2数据库的发展（不考了解）

1.人工管理阶段：硬件无磁盘，直接存取

2.文件系统阶段：简单数据共享与数据管理能力

3.数据库系统阶段：统一管理与共享数据

5.1.3 数据库系统的基本特点

数据库系统在文件系统的基础上加入了DBMS对数据库进行管理，使得数据库系统具有以下特点：

5.1.4 数据库的内部结构系统（难点）

image-20220305195403193

5.2 数据模型

5.2.1数据模型的基本概念

数据模型 的三要素：

数据模型按照应用层次分为：

1.概念模型

​ 面向用户的模型，是整个数据模型的基础

​ 考试就考：E-R模型

2.逻辑数据模型

​ 面向数据库的模型

​ 考：关系型

​ 典型的数据模型有：层次型、网状型、关系型、面向对象型

3.物理模型（存储结构）

​ 面向计算机物理表示的模型、给出了数据模型在计算机上的物理结构表示

​

5.2.2 E-R模型（考点）

E-R是常用的概念模型的表示方法、给出数据的概念化结构

1.E-R模型的基本概念

E-R模型的图示法（考点）

​ image-20220305202316995

image-20220305202333523

记住图片中的黄色字都为考点

都是实例自己看去吧 视频链接

​

5.3 关系代数

自己看去吧，看看就行、东西太多，没啥可以记的 视频链接

​

5.4 数据库设计与管理

主要考点就是

其他基本不考，想了解更多就看视频吧，链接放下面了

视频链接

相关考题以及答案

  1. 视频链接 - 1
  2. 视频链接 - 2
  3. 视频链接 - 3