【笔试】春招秋招技术岗笔试必考题归纳总结_n个节点的满二叉树调整成一个最小堆的最优复杂度

一、数据结构必考

1. 排序算法

1）什么时候用什么排序算法类

1. – 如果当前数据基本有序，什么算法比较合适？
   – 插入排序
2. – 哪种排序算法对[1, 3, 2, 4, 5, 6, 7, 8, 9]进行排序最快？
   – 改良的冒泡排序。当一轮循环中没有交换就结束排序，只需要2轮循环。改良的冒泡在序列基本有序的情况下，时间复杂度能达到O(n)
3. – 已知表 A 中每个元素距其最终位置不远，则哪种排序最省时间？
   – 直接插入排序。基本有序的情况下，插入排序只需要比较n-1次
4. – 在最后一趟开始之前，所有元素都有可能不在其最终的位置上的是？
   – 插入排序。如从小到大插入排序，最后一个插入的是最小的元素，此时最后一次前所有的数都不在正确的位置上。
5. – 如果只想得到5000个元素组成的序列中第10个最小元素之前的部分排序的序列，使用哪种排序方法最快？
   – 堆排序。只有前10个小元素进入堆，其他不进入，logK，K为堆中元素值。
6. –下列排序方法中，若将顺序存储更换为链式存储，则算法的时间效率会降低的是 (仅Ⅳ、Ⅴ)。
   Ⅰ．插入排序 Ⅱ．选择排序 Ⅲ．起泡排序 Ⅳ．希尔排序 Ⅴ．堆排序
   解析：
   插入排序、选择排序、起泡排序原本时间复杂度是O(n2)，更换为链式存储后的时间复杂度还是O(n2)。希尔排序和堆排序都利用了顺序存储的随机访问特性，而链式存储不支持这种性质，所以时间复杂度会增加。

2）排序算法的稳定性

• 稳定的排序算法：插入排序（直接、折半），冒泡排序，归并排序
• 不稳定的排序算法：希尔排序，快速排序，选择排序，堆排序

3）排序算法的时间复杂度&空间复杂度

4）不同时间复杂度的大小关系

Ο(1)＜Ο(log₂n)＜Ο(n)＜Ο(nlog₂n)＜Ο(n²)＜Ο(n³)＜Ο(2ⁿ)＜Ο(n!)

5）时间复杂度与空间复杂度的关系

无直接关系

6）快速排序

（1）对长度为n的线性表作快速排序，在最坏情况下，比较次数为（ n(n-1)/2 ）。
解析：
快速排序最坏的情况是对有序数列排序，那么第一个元素需要比较n-1次，第2个元素需要比较n-2次，以此来推需要比较1……n-1次，等差数列求和得到n(n-1)/2 。

（2）快速排序在哪种情况下最不利于发挥其长处？ 要排序的数据已基本有序.
解析：
快排在数据基本有序的时间复杂度为$O(n^2)$。因其退化为了冒泡排序，而冒泡排序的时间复杂度为$O(n^2)$。

（3）给定一组数：71、39、80、25、50、42、91。对其进行排序操作，排序过程中出现如下顺序：42、39、50、25、71、80、91。那么可能使用的是哪种排序算法？ 快速排序。

（4）如果待排序的数组近似递减排序，则此时使用快排算法进行递增排序的时间复杂度为( $O(n^2)$ ).
解析：
快速排序最坏的情况，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个的子序列，另外一个为空。如果递归树画出来，就是一颗斜树。此时需要执行n-1次递归调用，且第i次划分需要经（n-i）次关键字比较才能找到才能找到第i个记录，因此比较的次数为(n-1)+(n-2)+…+1 = n*(n-1)/2，最终时间复杂度为$O(n^2)$.

7）堆排序

例：对初始序列18625473采用堆排序，当建堆（小顶堆）完毕时，堆所对应的二叉树中序遍历序列为（ 83251647 ）。
解析：

2. 二叉树

二叉树第K层上至多有（2^k-1）个节点。（根从第1层开始）
整棵二叉树至多有（2^k-1）个节点。

1）二叉树的三种遍历

前序遍历：根左右
中序遍历：左根右
后序遍历：左右根

例1：根据二叉树的图写出其前序、中序、后序遍历。

前序遍历：abdcfeg
中序遍历：dbaefcg
后序遍历：dbefgca

例2：已知二叉树的两种遍历方式，写出第三种遍历。
已知二叉树的中序遍历为fcaegbd，后序遍历为fcgedba，前序遍历序列为：acfbegd.
解析：
从后序遍历可知，二叉树的根节点为a，再带入到中序遍历中看，可以将二叉树以根a为中心分为左右两个子树，再看后序遍历的倒数第二个结点为b，b位于右子树，因此b是右子树的根节点，以此类推，可以画出二叉树如下，这样就能根据图写出前序遍历了：

例3：深入理解三种遍历的特点。
对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ 后序 ）遍历实现编号。
解析：后序遍历（左<右<根）

例4：一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ B ）

A. CABDEFG

B. ABCDEFG

C. DACEFBG

D. ADCFEG

解析：只要将前序入栈，然后判断中序是不是他的出栈顺序就好。

2）二叉树结点计算问题

叶节点：n0
非叶节点：n1，n2
二叉树的结点数计算公式：n=n0+n1+n2，n=n1+2n2，n0=n2+1.
①n为奇数，没有度为1的结点，n=n0+n2
②n为偶数，只有一个度为1的结点，n=n0+1+n2

例1：若一棵二叉树有 102 片叶子结点，则度二叉树度为 2 的结点数是（ 101 ）。
解析：
度数为0的节点个数比度数为2的节点个数多1。即n0 = n2 + 1，所以n0=102，n2=101。

例2：在具有 2n 个结点的完全二叉树中，叶子结点个数为（ n ）。
解析：
完全二叉树中，有n2 = n0 - 1
根据题设条件，有n0 + n1 + n2 = 2n
两式相减，可得：2n0 + n1 - 1 = 2n
完全二叉树中，n1只能为0或1，由于2n为偶数，故n1 = 1
因此，n0 = n.

例3：在一棵度为3的树中，度为3的节点个数为2，度为2的节点个数为1，则度为0的节点个数为（ 6 ）。
解析：
设该树总共有n个节点，则n=n0+n1+n2+n3.
该树中除了根节点没有前驱以外，每个节点有且只有一个前驱，因此有n个节点的树的总边数为n-1条。根据度的定义，总边数与度之间的关系为：n-1=0*n0+1*n1+2*n2+3*n3。
联立两个方程求解，可以得到n0=6。

3）图的遍历与二叉树遍历

• 图的深度优先遍历(DFS)遍历思想实际上是二叉树（先序）遍历方法的推广。
• 图的广度优先遍历(BFS)遍历思想实际上是二叉树（层次）遍历方法的推广。

4）平衡二叉树

1. – 平衡二叉树的插入节点操作平均时间复杂度是？
   – O(log(n))。
   因为平衡二叉树中，查询的时间复杂度为log(n)。
2. – 判断二叉树是否平衡的方法？
   – 任何一个节点的两颗子树的高度差不超过1。
3. – 含有20个结点的平衡二叉树的最大深度为？
   – 6
   平衡二叉树深度为h所需的最小节点数：N(h)=N(h-1)+N(h-2)+1
   N(0)=0,N(1)=1;
   N(6)=20.

5）满二叉树与完全二叉树

例：如果我们定义满二叉树为树的每一层节点都被填满的二叉树叫满二叉树， 那么满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（ √ ）

满二叉树 ≤ 完全二叉树

6）完全二叉树的深度

例：有64个结点的完全二叉树的深度为（ 7 ）（根的层次为1） .
解析：
具有n个结点的完全二叉树的深度必为 ⌊log₂n⌋ ＋1
log₂64 + 1 = 7

7）二叉查找树

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。

（1）怎样遍历二叉查找树可以得到一个从小到大的有序序列（ 中序遍历 ）。

解析：

二叉查找树：对于一个父节点，左边的子节点比它小，右边的子节点比它大。

（2）二叉排序树中的最小值在二叉排序树的何处?

可能在叶子节点， 也可能在根节点，也可能在只有右孩子的父节点.

解析：

二叉排序树中的最小值节点就是最左边的那个，当只有一个根节点的时候，最小值就位于根节点了。

8）满二叉树调整成堆

例：n 个节点的满二叉树调整成一个最小堆的最优复杂度为（ O(n) ）。
解析：n个节点，分支节点n/2，每个分支最多进行两次比较和互换操作，因此整个构建过程时间复杂度为O(n)。

9）B树&B+树

B树只支持随机检索，而B+树既支持随机检索，又支持顺序检索。

例：
下面关于B和B+树的描述中，不正确的是( C )

A. B树和B+树都是平衡的多叉树

B. B树和B+树都可用于文件的索引结构

C. B树和B+树都能有效的支持顺序检索

D. B树和B+树都能有效的支持随机检索

10）树与二叉树的遍历

树的基本遍历策略分为：先根遍历和后根遍历。
二叉树的基本遍历策略分为：先序遍历、中序遍历和后序遍历。
则（树的先根遍历序列与其对应的二叉树的先序遍历序列相同；树的后根遍历序列与其对应的二叉树的中序遍历序列相同）

3. 栈与队列

1）出栈顺序

已知入栈序列，判断出栈顺序是否合理

栈是一种后进先出的数据结构。出栈的每一个元素后面，其中比该元素先入栈的一定按照入栈逆顺序排序。
例1：设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（ B ）。

A. 5，3，4，6，1，2

B. 3，2，5，6，4，1

C. 3，1，2，5，4，6

D. 1，5，4，6，2，3

解析：
A：5，3，4，6，1，2当5首先出栈，意味着1，2，3，4已经入栈，则出栈顺序3不能在4前面，1不能在2前面。
C：3，1，2，5，4，6 当3首先出栈，则说明1，2两个元素已经入栈，则出栈顺序1不能在2前面。
D：1，5，4，6，2，3当1首先出栈，能说通，往后看，当5出栈，意味着2，3，4三个元素已经入栈，则出战顺序2不可能在3前面。

例2：如果一个堆栈的入栈顺序为ABCDE,那么不可能出栈的顺序为：（ D ）

A. ABCDE

B. DECBA

C. EDCBA

D. DCEAB

解析：
先入A再入B，若A不是第一个出栈，B一定比A先出栈。

例3：若一个栈的输入序列是1、2、3、4、5，且第一个输出的元素是3，则最后一个输出的元素是（ 1或4或5 ）。
解析：
1）输入1、2、3，取出3，输入4、5，然后全部取出。最后一个输出为1.
2）输入1、2、3，取出3、2、1，输入4、5，然后全部取出。最后一个输出为4.
3）输入1、2、3，取出3、2、1，输入4，取出4，输入5，取出5，最后一个输出为5.

2） 栈容量

例4：现有初始状态均为空的栈X和队列Y，元素a、b、c、d、e、f、g依次进入栈X，每个元素出栈后即进入队列Y，如果出队列的顺序为b、c、f、e、g、d、a，则要求栈X最小容量为（4）.

解析：栈是先进后出，队列是先进先出。
由于出队列的顺序为b、c、f、e、g、d、a，所以出栈的顺序为b、c、f、e、g、d、a。
a进，栈容量为1；
b进，栈容量为2；
b出，c进，栈容量为2；
c出，d进，e进，f进，栈容量为4；
f出，e出，栈容量为2；
g进，栈容量为3；
g出，d出，a出。
所以栈X最小容量为4。

3）栈的应用

例1：下列情况中，不能使用栈（stack）来解决问题的是（ D ）。

A. 将数学表达式转换为后辍形式

B. 实现递归算法

C. 高级编程语言的过程调用

D. 操作系统分配资源（如CPU）

解析：资源的调度与分配用到了多种分配方式，其中最简单的就是，先来先服务，可以使用队列来完成。后又根据实际情况在此基础上综合了优先权和短进程等方面的考虑，所以像栈这种后进先出的就不合适了。

例2：以下哪些对象是分配在栈上的（ ABD ）

A. 函数内局部变量

B. 函数内局部指针变量

C. 函数内动态申请的对象

D. 函数内指向动态申请的对象的局部指针变量

解析：局部变量是分配在栈上的，new出来的对象是分配在堆上的。因此选项ABD都是局部变量，分配在栈上，C选项中动态申请的对象分配在堆上。

4）线性结构与非线性结构

线性结构：除第一个元素只有一个“后继”和最后一个元素只有一个“前驱”，其它每个元素只有一个“前驱”元素和一个“后继”元素。

常见的线性结构有: 数组、链表、栈以及队列。
注意：栈和队列本身不是一种数据结构，可通过数组或链表实现。

常见的非线性结构：二维数组、树、图、广义表。

4. 散列表

哈希冲突的解决方法：
1.开放定址法：1）线性探测法、2）平方探测法；
2.链地址法/拉链法.

1）线性探测法

例1：求平均查找长度ASL。
已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key) = key%7 计算散列地址，并散列存储在散列表A[0…6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为（2.0）
解析：
38%7=3 （第1次出现3，无冲突，放在位置3，查找次数为1）
25%7=4（第1次出现4，无冲突，放在位置4，查找次数为1）
74%7=4（第2次出现4，有冲突，放在位置5，查找次数为2）
63%7=0（第1次出现0，无冲突，放在位置0，查找次数为1）
52%7=3（第2次出现3，有冲突，发现冲突3,4,5，故只能放到6，查找次数为4）
48%7=6 （第1次出现6，有冲突，发现冲突6,1，故只能放到1，查找次数为3）
结果：(1+1+2+1+4+3)÷6=2

2）链地址法

例2：计算特定地址的记录数。
关键字序列为{12，11，19，23，1，6，10},哈希函数为H(key)=key MOD 11,用链地址法构造哈希表,哈希地址为1的链中有（ 3 ）个记录。
解析：
12%11=1
11%11=0
19%11=8
23%11=1
1%11=1
6%11=6
10%11=10
哈希地址为1的链中有 12,23,1.

5. 二维数组地址计算

需注意存储方式，是按行存储还是按列存储！！

按行存储计算公式：基地址+(行标之差×每行元素个数+列标之差)×一个元素所占存储单元

按列存储计算公式：基地址+(列标之差×每列元素个数+列标之差)×一个元素所占存储单元

例1：数组A[1…5,1…6]的每个元素占5个单元，将其按行优先顺序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为（1140）。
解析：
(5-1)*6＋5-1＝28,28*5＝1140 .
[5,5]前面有4行，一行6个数据，加第五行前面4个数据，共28个数据，每个数据5个单元.

例2：设有一个 10 阶的对称矩阵 A ，采用压缩存储方式，以行序为主存储， a[1][1] 为第一个元素，其存储地址为 1 ，每个元素占 1 个地址空间，则 a[8][5]的地址为（33）。
解析：
对称矩阵，存储一半， 第一行：1个 第二行：2个 第三行：3个 ……第八行：1~5，前5个。
因此，1+2+3+4+5+6+7，再加 5，得33.

例3：二维数组X按行顺序存储，其中每个元素占1个存储单元。若X[4][4]的存储地址为Oxf8b82140,X[9][9]的存储地址为Oxf8b8221c,则X[7][7]的存储地址为(Oxf8b821c4)。
解析：
[9][9] - [4][4] = 21c-140=5n+5
[7][7] - [4][4]=x-140=3n+3
[7][7] = 140+3/5*（ 21c-140 ）= 1c4

例4：设有数组A[i，j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以行为内存放时，元素A[5，8]的存储首地址为（ BA+141 ）。
解析：
（4*10+7）* 3＝141.

例5：数组A的每个元素需要4个字节存放，数组有8行10列，若数组以行为主顺序存放在内存SA开始的存储区中，则A中8行5列的元素的位置是（SA+296）。
解析：
(7*10+4) * 4 = 296.

例6：数组A[8][10] 中（下标均从0开始）， 每个元素的长度为3个字节，按列存储时，元素A[4][7]的起始地址为（SA为数组存储时的首地址）（SA+180）。
解析：
(8*7+4) * 3 = 180.

6. 二分法查找

二分查找前提：①关键字有序；②顺序存储。

（1）设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为( A[7]，A[3]，A[5]，A[4] )。
解析：
⌊(1+14) / 2⌋ = 7 --> 1 ~ 6
⌊(1+6) / 2⌋ = 3 --> 4 ~ 6
⌊(4+6) / 2⌋ = 5 --> 4 ~ 5
⌊(4+5) / 2⌋ = 4

（2）当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ 在大部分情况下要快 ）。

7. 广义表

1）广义表的深度和广度

广义表的长度：最外层包含的元素个数。
广义表的深度：所含括弧的重数。

例：F=(a,F)是一个递归的广义表，它的深度是1,长度是2。( × ）
解析：
考察广义表以及递归广义表的原理。
F=(a,F)的长度为2，由于属于递归表，所以深度为无穷，F相当于一个无限的表(a,(a,(a,(…))))。

2）广义表取原子项

广义表，除了头，全是尾，只能取头或除头以外的所有元素。

例：已知广义表L=((x,y,z),a,(u,t,w))，从L表中取出原子项u的运算是：head(head(tail(tail(L))))。
解析：
                        tail(L)=(a(u,t,w))
                  tail(tail(L))=((u,t,w))
         head(tail(tail(L)))=(u,t,w)
head(head(tail(tail(L))))=u

8. 图

（1）设有6个结点的无向图，该图至少应有（ 5 ）条边才能是一个连通图。
解析：
连通n个节点的有向图，至少需要n条边；
连通n个节点的无向图，至少需要（n-1）条边。

（2）n个顶点，m条边的全连通图，至少去掉（ m-n+1 ）条边才能构成一棵树。

9. 线性表

对于n个结点的线性表，
①时间复杂度为O(1)的操作：初始化线性表，销毁线性表，判断是否为空表，求长度，求某个数据元素值。
②时间复杂度为O(n)的操作：输出线性表，按元素值查找，插入数据元素，删除数据元素。

（1）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（ 访问第i个结点和求第i个结点的直接前驱 ）。

（2）若长度为n的线性表采用顺序存储结构，在其第i个位置(1<=i<=n+1)插入一个新元素的算法的时间复杂度为（ O(n) ）。

（3）两个单链表L1、L2的长度分别为m、n，两者均有头指针，无尾指针，将L2链接在L1之后的算法的时间复杂度是（ O(m) ）。
解析：O(m)可以遍历到L1的尾部，O(1)时间可以把L2插入到L1尾部。

例：在向1988个有序顺序表中插入一个新元素，并保持原来的顺序不变，平均要移动的元素次数是（994）.

解析：在n个有序顺序表中插入一个新元素，每个位置的插入概率相同时，平均要移动的元素次数是
[n+（n-1）+…+1+0]*[1/(n+1)] = (1+n)*n / [2(n+1)] = n/2次。
因此1988/2=994。

10. 循环队列

队空：front = rear
队满：(rear+1) % Maxsize = front
入队：rear = (rear+1) % Maxsize
出队：front = (front+1) % Maxsize
队列中元素的个数 m = (rear - front + maxSize) % MaxSize

例1：若用一个大小为6的数组来实现循环队列(只能在front删除元素，在rear添加元素)，且当前front和rear的值分别为0和4，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为（ 1和0）。
解析：如下图所示

例2：循环队列的存储空间为 Q(1:40) ，初始状态为 front=rear=40 。经过一系列正常的入队与退队操作后， front=rear=15 ，此后又退出一个元素，则循环队列中的元素个数为（ 39，或0且产生下溢错误 ）。

解析：循环队列是队列的一种顺序存储结构，用队尾指针 rear 指向队列中的队尾元素，用排头指针 front 指向排头元素的前一个位置。入队运算时，队尾指针进 1 （即 rear+1 ），然后在 rear 指针指向的位置插入新元素。退队运算时，排头指针进 1 （即 front+1 ），然后删除 front 指针指向的位置上的元素。当 front=rear=15 时可知队列空或者队列满，此后又退出一个元素，如果之前队列为空，退出操作会产生错误，队列里有 0 个元素；如果退出之前队列已满 (40 个元素 ) ，执行退出后，队列里还有 39 个元素。

11. 哈夫曼树

1）哈夫曼树的性质

对于具有n0个叶子结点的哈夫曼树，共有2n0-1个结点。
在哈夫曼树的构造过程中，每次都是将两棵树合并为一棵树，所以哈夫曼树中不存在度为1的结点，即n1=0。由二叉树的性质有，n0=n2+1，即n2=n0-1，则有n=n0+n1+n2=n0+n2=n0+n0-1=2n0-1。

例1：给定n个权值，其对应哈夫曼树的结点总数为（ 2n-1 ）。

2）哈夫曼编码

例：使用哈夫曼编码来编码字符串"aaaabbcd"时，得到的编码长度为多少? 14
解析：

二、计算机网络必考

1. 各层的协议及设备

例：当一台计算机发送 E-mail 信息给另外一台计算机时，下列的哪一个过程正确描述了数据打包的 5 个转换步骤 ?

答：数据，数据段，数据包，数据帧，比特

解析：

打包是从上往下的，先应用层收到数据，再往下一步一步打包传输，而解包则是从下往上。

从应用层到物理层依次为：

应用层、表示层、会话层：数据(消息)

传输层：数据段(segment)

网络层：分组、数据包(packet)

数据链路层：数据帧(frame)

物理层：P-PDU(bit)

2. 各协议名称及端口号

3. 单工通信/半双工通信/全双工通信

①单工通信：只有通信的一方可以传送数据。
②半双工通信：在同一时间里，只有通信的一方可以传送数据。
③全双工通信：在同一时间里，通信的双方都可以传送数据。

4. 子网掩码

子网掩码：前面全是1，后面为0，从左到右，所有的1必须是连续的。

（1）下列哪个地址不可能是子网掩码( D )

A. 255.224.0.0

B. 255.255.240.0

C. 255.255.255.248

D. 255.255.255.250

解析：

A. 224转换为二进制是1 1 1 0 0 0 0 0 0 可行

B. 240转换为二进制是1 1 1 1 0 0 0 0 0 可行

C. 248转换为二进制是1 1 1 1 1 1 0 0 0 可行

D. 250转换为二进制是1 1 1 1 1 1 0 1 0 不可行

（2）假如正在构建一个有 22 个子网的 B 类网络，但是几个月以后，该网络将增至 80 个子网，每个子网要求支持至少 300 个主机，应该选择下面哪个子网掩码（ B ）？

A. 255.255.0.0

B. 255.255.254.0

C. 255.255.255.0

D. 255.255.248.0

解析：IP地址结构：网络地址+子网地址+主机号地址

本题主要考查对子网划分的理解。由题目可知，我们构建的是一个B类网络，B类IP地址的网络号为16位，主机号为16位。默认子网掩码为255.255.0.0。题目要求我们需要增加到80个子网，80>2⁶=64，所以子网号位数至少为7。另外，每个子网至少支持300个主机，300>2⁸=256,所以主机号位数至少为9。所以，在B类网络16位主机号的基础上，我们需要借用7位来作为子网号。因此，子网掩码为前23位为1，后9位为0。即11111111 11111111 11111110 00000000，换算为点分十进制为255.255.254.0。

（3）若子网掩码为255.255.255.192，下列IP地址对中属于同一个子网的是( C ) 。

A. 156.26.27.71和156.26.101.110

B. 156.26.101.88和156.26.101.132

C. 156.26.27.71和156.26.27.110

D. 156.26.101.88和156.27.101.132

解析：
71二进制：01000011
110二进制：01101110
132二进制：10000100
88二进制：01011000
默认网关最后一位192二进制：11000000；与71和110的最高两位一致

通过子网掩码的 255.255.255，因为前面的都是1，我们只要看两个网络的前3个字节，一样不一样就可以，由此排除 A和D。接下来通过子网掩码的 192 即 1100 0000 可以看出最后一个字节的前两位是网络号。看B选项 ，64<88<128，那么前面一定是 01 ; 128<132<192，那么前面一定是 10 ，网络号不同，因此选C。

5. IP地址分类

例：192.168.1.1代表的是（ C类 ）地址。

三、数据库必考

1. 数据独立性

1）数据独立性定义

例1：数据库系统的独立性是指（ 不会因为系统数据存储结构与数据逻辑结构的变化而影响应用程序 ）。
例2：数据库三级模式体系结构的划分，有利于保持数据库的 ( 数据独立性 )。

2）物理/逻辑独立性

逻辑独立性是模式改变时外模式不变，物理独立性是内模式改变时模式不变。

例3：要保证数据库物理数据独立性，需要修改的是（　模式/内模式映射　）。

外模式/模式的映像保证逻辑独立性，模式/内模式的映像则保证物理独立性。

2. 关系数据库管理系统的基本运算关系及SQL对应的子句

3. SQL语句及其功能

注：DROP、DELETE、TRUNCATE的区别？
①drop语句：删除内容和定义，释放空间。（表结构和数据一同删除）
②truncate语句：删除内容，释放空间，但不删除定义。（表结构还在，数据删除）
③delete语句：删除内容，不释放空间，也不删除定义。（表的结构、属性和索引都是完整的）

编写顺序：

SELECT DISTINCT…FROM…JOIN…ON…WHERE…GROUP BY…HAVING…ORDER BY…LIMIT…

解析顺序：

FROM…ON…JOIN…WHERE…GROUP BY…HAVING…SELECT DISTINCT…ORDER BY…LIMIT…

例：在SQL中语法规范中，having子句的使用下面描述正确的是：
（ A C ）

A. having子句即可包含聚合函数作用的字段也可包括普通的标量字段

B. 使用having的同时不能使用where子句

C. having子句必须于group by 子句同时使用，不能单独使用

D. 使用having子句的作用是限定分组条件

E. Having子句和where子句是等同的

F. 如果select语句中没有聚合函数的使用，就不能使用having子句

解析：
having是在分组后过滤，where在分组前过滤，不冲突，可以同时使用，BE错；
having是用来过滤的，group by是限定分组，D错；
select语句中没有聚合函数的使用时也可以用having，F错。

4.事务的ACID特性

事务的4个特性：
①原子性：Atomicity。事务中包含的操作被看做一个逻辑单元，这个逻辑单元中的操作要么全部成功，要么全部失败。
②一致性：Consistency。事务完成时，数据必须处于一致状态，数据的完整性约束没有被破坏，事务在执行过程中发生错误，会被回滚（Rollback）到事务开始前的状态，就像这个事务从来没有执行过一样。
③隔离性：Isolation。事务允许多个用户对同一个数据进行并发访问，而不破坏数据的正确性和完整性。同时，并行事务的修改必须与其他并行事务的修改相互独立。
④持续性：Durability。事务结束后，事务处理的结果必须能够得到固化。

例：关于ACID下面说法正确的是（ BD ）?

A. 可用性。整个操作中的所有动作是保证高可用性，系统必须提供要求的稳定性，以保证事务的提交。×

B. 一致性。在事务开始之前和结束后，数据库的约束保持不变。 √

C. 隔离性。两个同时运行的事务的执行是互不影响，中间结果不可交叉访问。 ×

D. 持久性。在事务提交以后，该事务所作的更改持久保存在存储介质之中，不会被回滚。 √

解析：

A是原子性；C 能不能互相访问要看隔离等级。中间数据有可能互相访问，比如隔离等级是未授权读取、授权读取、可重复读均可

5. 事务锁

①共享锁【S锁】
又称读锁，若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A，其他事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁。这保证了其他事务可以读A，但在T释放A上的S 锁之前不能对A做任何修改。

②排他锁【X锁】
又称写锁。若事务T对数据对象A加上X锁，事务T可以读A也可以修改A，其他事务不能再对A加任何锁，直到T释放A上的锁。这保证了其他事务在T释放A上的锁之前不能再读取和修改A。

6. 通配符

为在搜索子句中使用通配符，必须使用LIKE操作符.

7. 数据库逻辑设计时E-R图和关系模式的对应关系

8. 数据的完整性约束条件

①实体完整性：规定表的每一行在表中是惟一的实体。
②域完整性：表中的列必须满足某种特定的数据类型约束，其中约束又包括取值范围、精度等规定。
③参照完整性：两个表的主关键字和外关键字的数据应一致，保证了表之间的数据的一致性，防止了数据丢失或无意义的数据在数据库中扩散。
④用户定义的完整性：不同的关系数据库系统根据其应用环境的不同，往往还需要一些特殊的约束条件。用户定义的完整性即是针对某个特定关系数据库的约束条件，它反映某一具体应用必须满足的语义要求。

9. 数据查询

1）等值连接与自然连接

例：一般情况下，当对关系R和S进行等值连接时，要求R和S含有一个或者多个共有的属性。（ × ）

解析： 等值连接是从关系R和S的广义笛卡尔积中选取A和B“属性值”相等的元组，所以只要两个关系里面的有元组属性值相等就可以进行。 而自然连接是要求R和S中有一个或者多个相同的属性组。

2）内连接和外连接

数据库中涉及两个表之间的数据查询通常使用连接的方法实现，连接可以分为内连接和外连接：

• 内连接。内连接也称为等值连接，是最早的一种连接，它还可以被称为普通连接或者自然连接。它指连接结果仅包含符合连接条件的行，参与连接的两个表都应该符合连接条件。
• 外连接。外连接是指连接结果不仅包含符合连接条件的行同时也包含自身不符合条件的行。它可以继续分为3种连接，左外连接，右外连接，全外连接：
  • 左外连接。左边表数据行全部保留，右边表保留符合连接条件的行。
  • 右外连接。右边表数据行全部保留，左边表保留符合连接条件的行。
  • 全外连接。左外连接 union 右外连接。全外连接是在等值连接的基础上将左表和右表的未匹配数据都加上。

例：以A、B表为例，主外键为id。简述INNER JOIN、LEFT JOIN和RIGHT JOIN的区别（ A ）。

A. A INNER JOIN B：返回A和B中符合on条件式的记录

B. A LEFT JOIN B：返回B中的所有记录和A中符合on条件式的记录

C.A RIGHT JOIN B：返回A中的所有记录和B中符合on条件式的记录

D.以上答案都不正确

解析：
A INNER JOIN B：返回A和B中符合on条件式的记录。
A LEFT JOIN B：返回A中的所有记录和B中符合on条件式的记录。
A RIGHT JOIN B：返回B中的所有记录和A中符合on条件式的记录。

10. 基础知识

（1）文件系统与数据库系统的最大区别是（ 数据结构化 ）。
（2）（ 数据库管理系统 ）处于数据库系统的核心位置。
（3）数据库类型是根据（ 数据模型 ）划分的。
（4）数据库管理系统提供的功能有：（完整性、安全性、一致性、可恢复性）。
（5）数据库是（长期存储在计算机内的、有组织的、可共享的大量数据）的集合。
（6）一般关系数据模型和对象数据模型之间有以下对应关系：（表对应类，记录对应对象，表的字段对应类的属性）。
（7）DBS（数据库系统）包含DB（数据库）和 DBMS（数据库管理系统）。
（8）规范化过程主要为克服数据库逻辑结构中的插入异常、删除异常以及 （冗余度大） 的缺陷。

四、计算机操作系统必考

1. 死锁

①定义：如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的。

②产生死锁的必要条件：
1）互斥条件：一个资源每次只能被一个进程使用。
2）请求和保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
3）不可抢占条件：进程已获得的资源，在末使用完之前，不能强行剥夺。
4）循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。

③死锁的预防措施：
1）静态资源分配法：静态分配是指进程在运行之初，一次性请求所有需要的资源，所以破坏了请求和保持的条件。
2）资源顺序分配法：资源顺序分配法规定每个进程必须按编号递增的顺序请求资源，同类资源一次性申请完，所以破坏了循环等待的条件。
3）剥夺控制法：破坏了不可抢占这个条件。

（1）解决死锁问题通常意味着牺牲资源的效率。 （ √ ）
解决死锁通常是释放部分进程资源，故牺牲了资源的效率。

2. 创建进程

例1：下面会引起进程创建的事件是( AC )。

A. 用户登录 √

B. 设备中断 ×

C. 作业调度 √

D. 执行系统调用 ×

导致一个进程创建另一个进程的典型操作有四种：
①用户登录；系统为用户创建一个进程，并插入就绪队列。
②作业调度；系统会为调度的作业分配资源，从后备队列中将其放入内存中，并为其创建进程。
③提供服务；系统为用户请求创建一个进程。
④应用请求；用户程序自己创建进程。

3. 调度算法

①磁盘调度：调整多个磁盘访问请求的服务顺序以降低平均磁盘服务时间。

磁盘调度算法减少的是磁头移动距离(寻道时间)。
注意：磁盘调度强调的是扫描磁盘的顺序，即寻道顺序

磁盘调度算法：

FCFS：先来先服务

SSTF：最短寻道时间优先

SCAN：扫描算法/电梯调度算法

CSCAN：循环扫描算法

NstepSCAN：N步SCAN算法

FSCAN：分步电梯调度算法

②作业调度：负责从磁盘调度进内存的先后顺序。

作业调度算法：

FCFS（first-come first-served）先来先服务调度算法

SJF（short job first）短作业优先的调度算法

PSA（priority-scheduling algorithm）优先级调度算法

HRRN（highest response ratio next）高响应比优先调度算法

③进程调度：从内存进CPU的先后顺序。

进程调度算法：

FCFS（first-come first-served）先来先服务调度算法

RR（round robin）基于时间片轮转的调度算法

HRRN（highest response ratio next）高响应比优先调度算法

SPN（short process next）短进程优先调度算法，和SJF一样

SRT（shortest remaining time）最短剩余时间优先调度算法

PSA（priority-scheduling algorithm）优先级调度算法

多级反馈队列调度算法（multileved feedback queue）

（1）一种既有利于短小作业又兼顾到长作业的作业调度算法是（ 最高响应比优先 ）。
（2）（优先级）进程调度算法会引起进程的饥饿问题。
（3）在单用户系统中，最佳的磁盘调度算法是（ 先来先服务算法FCFS ）。

五、编程基础知识必考

1. 各数据类型取值范围及结构体所占字节数

注：32位系统下

例1：若有以下说明和定义语句：

union uti {
    int n;
    double g;
    char ch[9];
} struct srt {
    float xy;
    union uti uv;
} aa;
1
2
3
4
5
6
7
8

考虑内存对齐，则变量aa所占内存的字节数是（ 24 ）
解析：首先int，float是4字节，double是8字节，char是1字节。 union里面以最大成员计算空间，应该是char［9］，占9字节，然后以8字节为单位对齐，所以uti实际占16字节。 struct srt中，就是4+16＝20字节，同样以8字节对齐，所以应该是24。 假如union把char［9］去掉，uti占用最大与double一样，为8字节，这时srt占用4+8＝12，再对齐则占用16。

例2：在 32 位编译器上，设有定义：

char *str1 = "Hello", str2[] = "Hello"; 
1

则以下语句

printf("%d %d", sizeof(str1), sizeof(str2)); 
1

的输出结果是（4 6）

解析：
本题主要考查了指向字符串的指针和字符数组， str1 为一个字符指针，所以 sizeof 为 4 ， str2 为字符数组，其中包含 6 个字符，所以答案为 4 6.

例3：在32系统下输出的结果为（ 12,16 ）

#include <stdio.h>
#pragma pack(2)
struct Test1{
    int a;
    char b;
    short c;
    int *d;
} A;
#pragma pack()
#pragma pack(4)
struct Test2{
    int *d;
    char b;
    int a;
    short c;
} B;
#pragma pack()

int main(){
    printf("%d,%d\n",sizeof(A),sizeof(B));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

解析：
#pragma pack(n) ：n在其中代表对齐模数，相当于操作系统的位数（换算成字节数），用于指定结构体的对齐，每个成员的对齐模数是该数据成员所占内存与#pragma pack指定的数值中的较小者。
A和B的对齐字节分别是2和4，而且不足者需要补足，溢出时翻倍，所以A为4+2+2+4 = 12；B为4+4+4+4= 16。

2. 三目运算符

例：若有int w=1, x=2, y=3, z=4;则条件表达w < x ? w : y < z ? y : z的值是（ 1 ）.
w<x为真，返回w，即表达式的值为1.

三目运算符的运算顺序是从右到左的结合。

3. 指针

（1） 说明“double(*ptr)[N];”中的标识符ptr是（ 一个指向由N个double类型元素组成的一维数组的指针
或一个指向一维数组的指针，这个数组由N个double类型元素组成 ）。
解析：()的优先级大于[]，因此它是一个指针，指向数组。

（2） 下面程序的输出结果是？ （ 10,20,30 ）

#include<iostream.h>
int main(){
    int n[][3]={10,20,30,40,50,60};
    int (*p)[3];
    p=n;
    cout<<p[0][0]<<","<<*(p[0]+1)<<","<<(*p)[2]<<endl;
    return 0;
}
1
2
3
4
5
6
7
8

解析：
p[0][0]指的是第一个元素；
p[0]+1指的是第一行第二个元素；
(*p)[2]数组指针，表示第一行的第三个元素；
**(p+1)表示第二行第一个元素；

（3）对二维数组a来说,由于a+1与*(a+1)的值相等，因此二者的含义是一样的。请问这句话的说法是正确的吗？（×）
a+1是第二维数组的地址，*(a+1)是第二维数组第一个元素的地址。所以值是相等的，但是意义不一样。

（4）下面3段程序代码的效果一样吗？ (1)=(2)

int b;
(1)const int *a = &b;
(2)int const *a = &b;
(3)int *const a = &b;
1
2
3
4

解析：const在*的左边，则指针指向的变量的值不可直接通过指针改变(可以通过其他途径改变);在*的右边，则指针的指向不可变。简记为"左定值，右定向"。

（5）对于int* pa[5];的描述，以下哪个选项是正确的（ A ）

A. pa是一个具有5个元素的指针数组，每个元素是一个int类型的指针;

B. pa是一个指向数组的指针，所指向的数组是5个int类型的元素;

C. pa[5]表示某个数的第5个元素的值;

D. pa是一个指向某个数组中第5个元素的指针，该元素是int类型的变量

解析：
int* pa[5]表示指针数组，指一个数组里面装着指针
int (*p)[5]表示数组指针，表示一个指向数组的指针

（6）若有如下定义：

    class sam {
    public:
        int num;
        void print() {cout << num;}
    };
     
    sam x, *p = &x;
1
2
3
4
5
6
7

则下列表达式中，正确的是（ BCD ）

p.num		 //×
(*p).print() //√
x.num=5		 //√
p->num=10	 //√
1
2
3
4

解析：

箭头（->）：左边必须为指针；

点号（.）：左边必须为实体。

（7）有以下语句：

    char str[4][12] = {"aaa", "bbbb", "ccccc", "dddddd"}, *strp[4];
    for (int i = 0; i < 4; i++)
        strp[i] = str[i];
1
2
3

对字符串的正确引用是（ ACD ），其中0≤k<4

*strp  //√ *strp = strp[0] = str[0]
strp   //× strp  = &strp[0] =  &str[0]
str[k] //√ str[k] = strp[k] = *(strp + k)
strp[k]//√ strp[k] = *(strp + k) = str[k]
1
2
3
4

解析：对字符串正确引用，就是是字符串地址的！答案B是数组的地址，其余都是字符串的地址！

（8）char * const p, char const * p, const char *p上述三个的区别，说法错误的是( C )？

A. char * const p;p的值不可以修改 √

B. char const * p;p指向的值为只读 √

C. const char *p;p的值不可以改变×

解析：

​ A. p是常量指针，这个指针指向固定的位置，即p的值(地址)不可以修改

​ B. 是指向常量的指针, 指向的常量值 不能被 *p 修改，即 *p 指向的值是常量

​ C. const char* p 和 char const *p 是一样的
（9） 设有定义语句

int x[6] = {2, 4, 6, 8, 5, 7}, *p = x, i;
1

要求依次输出x数组6个元素中的值，不能完成此操作的语句是（ D ）

for(i=0;i<6;i++) printf("%2d",*(p++)); //√
for(i=0;i<6;i++) printf("%2d",*(p+i)); //√
for(i=0;i<6;i++) printf("%2d",*p++);   //√
for(i=0;i<6;i++) printf("%2d",(*p)++); //×
1
2
3
4

解析：++和*都是第二优先级，但注意是右结合律

4. 重载&重写

方法的重写(Override)和方法的重载(Overload)是Java多态性的不同表现。

​重写(Override)是父类与子类之间多态性的一种表现，重载(Overload)是一个类中多态性的一种表现。

①重写(Override)：如果在子类中定义某方法与其父类有相同的名称和参数，那么该方法被重写(Override)。子类的对象在使用这个方法时，将调用子类中的定义，对它而言，父类中的定义如同被“屏蔽”了。

②重载(Overload)：如果在一个类中定义了多个同名的方法，它们或有不同的参数个数，或有不同的参数类型，则称为方法的重载(Overload)。

例：在Java中，以下关于方法重载和方法重写描述正确的是（ D ）？

A. 方法重载和方法的重写实现的功能相同

B. 方法重载出现在父子关系中，方法重写是在同一类中

C. 方法重载的返回值类型必须一致，参数项必须不同

D. 方法重写的返回值类型必须相同或相容

解析：

重载：只要方法名 一致 ，其他（参数列表、返回值）随便。
重写：只有实现的功能代码 不一致 ，其他的（函数名、参数列表、返回值类型）必须都一致。

5. Java编译时会发现的异常

其中，非运行时异常需要进行异常检查，即使用try-catch语句进行捕获，或者使用throws子句抛出，否则无法通过编译。其余异常不需异常检查，即在编译时不会发现。

6. 变量相关

（1） 外部变量可以供其所在的程序文件中的任何函数使用？（ × ）

全局变量也称为外部变量，它是在函数外部定义的变量，其作用域是从定义该变量的位置开始至源文件结束。全局变量不受作用域的影响（也就是说，全局变量的生命期一直到程序的结束）。
· 如果在一个文件中使用extern关键字来声明另一个文件中存在的全局变量，那么这个文件可以使用这个数据。
· 在全局变量前加一个static，使该变量只在这个源文件中可用，称之为全局静态变量。

（2） 下面关于变量及其范围的陈述哪些是不正确的? （ B ）

A. 实例变量是类的成员变量√ 类的成员变量包括实例变量和类变量（静态变量）,成员方法包括实例方法和类方法（静态方法）。

B. 实例变量用关键字static声明× 类变量（静态变量）用关键字static声明。

C. 在方法中定义的局部变量在该方法被执行时创建× 方法中的局部变量在方法被调用加载时开始入栈时创建，方法入栈创建栈帧包括局部变量表操作数栈，局部变量表存放局部变量，并非在执行该方法时被创建。

D.局部变量在使用前必须被初始化√ 局部变量被使用前必须初始化，否则程序报错。

7. 输入输出格式

8. 依赖注入

例：
关于依赖注入，下列选项中说法错误的是( B )

A. 依赖注入能够独立开发各组件，然后根据组件间关系进行组装

B. 依赖注入使组件之间相互依赖，相互制约

C. 依赖注入提供使用接口编程

D. 依赖注入指对象在使用时动态注入

解析：依赖注入可以降低组件之间的耦合度。而不是增加依赖程度。

9. Java运行时的数据区

Java运行时数据区包括：程序计数器、虚拟机栈、本地方法栈、Java堆、方法区以及方法区中的运行时常量池。

① 程序计数器： 线程私有，是当前线程所执行的字节码的行号指示器，如果线程正执行一个Java方法，计数器记录正在执行的虚拟机字节码指令的地址，如果线程正在执行的是Native方法，则计数器值为空；

② 虚拟机栈： 即栈区， 线程私有 ，为虚拟机执行 Java 方法（字节码）服务，每个方法在执行的时会创建一个栈帧用于存放局部变量表、操作数栈、动态链接和方法出口等信息，每个方法的调用直至执行完成对应于栈帧的入栈和出栈；

③ 本地方法栈： 为虚拟机使用的 Native 方法服务，也是 线程私有 ；

④ Java 堆： 在虚拟机启动时创建， 线程共享 ，唯一目的是存放对象实例，是垃圾收集器管理的主要区域——“ GC 堆 ”，可以细分为新生代和老年代，新生代又可以细分为 Eden 空间、 From Survivor 空间和 To Survivor 空间；物理上可以不连续，但逻辑上连续，可以选择固定大小或者扩展；

⑤ 方法区： 线程共享 ，用于存储被虚拟机加载的类信息、常量、静态变量、即时编译器编译后的代码等数据。被称为“永久代”，是因为 HotSpot 虚拟机的设计团队把 GC 分代收集扩展到方法区，即使用永久代来实现方法区，像 GC 管理 Java 堆一样管理方法区，从而省去专门为方法区编写内存管理代码，内存回收目标是针对常量池的回收和堆类型的卸载；

⑥ 运行时常量池： 线程共享 ，是方法区的一部分， Class 文件中存放编译期生成的各种字面量和符号引用，类加载后进入方法区的运行时常量池中。

例：下面有关JVM内存，说法错误的是（ C ）？

A. 程序计数器是一个比较小的内存区域，用于指示当前线程所执行的字节码执行到了第几行，是线程隔离的

B. Java方法执行内存模型，用于存储局部变量，操作数栈，动态链接，方法出口等信息，是线程隔离的

C. 方法区用于存储JVM加载的类信息、常量、静态变量、即时编译器编译后的代码等数据，是线程隔离的

D. 原则上讲，所有的对象都在堆区上分配内存，是线程之间共享的

解析：方法区应该是线程共享的。

10. 宏定义

宏定义即直接替换，不会替你加括号。

（1）下面程序的输出结果是（ 0 ）。

#include <iostream>
using namespace std;
#define SQR(A) A*A
int main() { 
    int x = 6, y = 3, z = 2; 
    x /= SQR(y + z) / SQR(y + z); 
    cout << x << endl; 
}
1
2
3
4
5
6
7
8

解析：
x /= SQR(y+z)/SQR(y+z); 相当于：x /= y+z*y+z/y+z*y+z;

而除等（/=）的优先级低于+、-、*、/。所以先计算/=右边的。又x为int型，结果保留整数位，所以为0。

（2）有如下一段代码：

#define ADD(x,y) x+y
int m=3;
m+=m*ADD(m,m);
1
2
3

最后m的值为（15）。

解析：
m*ADD(m,m)相当于：m*m+m, 等号右边算出来是12，m+=12，即m=m+12，m=3，所以最终结果是m=15。

11. 不能被重载的运算符

能被重载的运算符只有五个，分别是

① . （成员访问运算符）

② .*（成员指针访问运算符）

③ :: （域运算符）

④ sizeof （长度运算符）

⑤ ?: （条件运算符）

前两个运算符不能重载是为了保证访问成员的功能不被改变 ，域运算符和sizeof运算符的运算对象是类型而不是变量或者一般表达式，不具备重载的特征。

12. 访问局部性

时间局部性：一旦一条指令执行了，则在不久的将来它可能再被执行。

空间局部性：一旦一个存储单元被访问，那么它附近的存储单元也很快被访问。

例：某C语言程序段如下：

for(i = 0;i <= 9; i++){
    temp = 1;
    for(j = 0; j <= i; j++)
        temp *= a[j];
    sum += temp;
}
1
2
3
4
5
6

则关于数组a的访问局部性：（时间局部性和空间局部性皆有）

解析：显然，这里的循环指令本身具有时间局部性，它对数组a的访问具有空间局部性。

13. Java抽象类与接口区别

14. 运算符优先级

15. 运算符结合性

优先级由高至低

六、软件工程必考

1. 软件测试步骤

①单元测试：是针对软件中最小单元程序模块进行正确性检查的测试工作，又称为模块测试。一般以白盒为主，以黑盒为辅。
②集成测试：在单元测试的基础上，需要将所有模块按照概要设计说明书和详细设计说明书的要求进行组装，又称为组装测试或联合测试。集成测试通常有两种方式组装：非渐增式测试和渐增式测试。
③确认测试：确认测试的目标是验证软件的功能和性能以及其他特性是否与用户的要求一致。确认测试一般包括有效性测试和软件配置复查。其中配置复查时，Alpha测试由用户在开发者的场所进行，并且在开发者对用户的“指导”下进行测试；Beta测试由软件的最终用户们在一个或多个客房场所进行，即是在开发者不能控制的环境中的“真实”应用。
④系统测试：是在分别完成集成测试和确认测试之后，确保各组成部分不仅已通过了单独的检验而且在系统各部分协调工作的环境下也可正常工作，然后再把软件、硬件和环境连在一起进行全面的测试。

2. 软件开发时的过程模型

①瀑布模型：瀑布模型是将软件生存周期中各个活动规定为依线性顺序连接的若干阶段的模型，包括需求分析、设计、编码、测试、运行与维护。它规定了由前至后、相互衔接的固定次序，如同瀑布流水逐级下落。
②增量模型：把待开发的软件系统模块化，将每个模块作为一个增量组件，从而分批次地分析、设计、编码和测试这些增量组件。
③螺旋模型：将瀑布模型和增量模型结合起来，并加入了风险分析。
④迭代模型：软件开发过程每迭代一次，软件开发又前进一个层次。
⑤原型模型：适用于已有产品或产品原型（样品），只需客户化的工程项目。

3. 基础知识

（1）测试的关键问题是( 如何选择测试用例 )。
测试的关键问题是如何设计测试，也就是如何选择测试用例。
（2）在软件开发的各种资源中，（人员）是最重要的资源。
（3）结构化分析的常用工具有（数据流图（DFD图）、数据字典（DD）、判定树和判定表）。
（4）软件生命周期中所花费用最多的阶段是（软件维护）。