数据结构与算法复习提纲 – 404-502的个人博客

*考试题型

单选题 20 * 2 = 40分

填空题 10 * 1= 10分

综合题 5 * 10 = 50分

第1章绪论

1.1 基本概念

数据：是信息的载体，是描述客观事物的数、字符以及所有能输入到计算机中被计算机程序识别和处理的符号的集合。
数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。
数据对象：是具有相同性质的数据元素的集合，是数据的一个子集。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。包括三方面内容：逻辑结构、存储结构和数据的运算。

1.2 逻辑结构与存储结构

逻辑结构：数据元素之间的逻辑关系。主要分为两大类：
线性结构：线性表、栈、队列、串、数组
非线性结构：树、图、集合
存储结构（物理结构）：数据结构在计算机中的表示（映像）。
顺序存储结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
链式存储结构：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

1.3 算法与算法分析

算法：是对特定问题求解步骤的一种描述，是指令的有限序列。算法具有五个特性：有穷性、确定性、可行性、输入、输出。
算法设计目标：正确性、可读性、健壮性、高效率与低存储量需求。
算法效率度量：主要关注时间复杂度和空间复杂度。
时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，记作T(n)=O(f(n))。它衡量算法执行时间的增长率。
常见时间复杂度：O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) < O(n³) < O(2ⁿ)

1.4 例题

算法的时间复杂度与( )有关。
A. 问题规模
B. 程序设计语言
C. 计算机硬件性能
D. 编译程序质量
答案：A
数据的逻辑结构是指( )的整体。
A. 存储结构之间关系
B. 数据类型之间关系
C. 数据元素之间逻辑关系
D. 数据项之间逻辑关系
答案：C
执行下面程序段的时间复杂度为( )。

for(i=0;i<m;i++)
    for(j=0;j<n;j++)
        a[i][j]=i*j;

A. O(n²)
B. O(mn)
C. O(m+n)
D. O(m²)
答案：B

数据结构是一门研究非数值计算的程序设计问题中计算机的( )以及它们之间的关系和操作等的学科。
A. 操作对象
B. 计算方法
C. 逻辑存储
D. 物理存储
答案：A
算法最基本的特性是( )。
A. 有穷性、可行性、确定性
B. 可执行性、可移植性、可扩充性
C. 可执行性、确定性、有穷性
D. 易读性、稳定性、安全性
答案：A
( )是利用数据元素在存储器中的相对位置来表示数据元素间的逻辑顺序，通常把逻辑上相邻的元素存储在物理相邻的存储单元中。
A. 链式存储结构
B. 顺序存储结构
C. 逻辑结构
D. 以上都对
答案：B
执行下面程序段的时间复杂度为( )。

x=0;
y=0;
for(k=1;k<n;k++)
    x++;
for(i=1;i<n;i++)
    for(j=1;j<n;j++)
        y++;

A. O(n²)
B. O(n)
C. O(1)
D. O(2n)
答案：A

执行下面程序段的时间复杂度为( )。

if(x>n)
    x++;
else
    for(j=1;j<n;j++)
        x++;

A. O(2n)
B. O(n²)
C. O(n)
D. O(1)
答案：C

执行下面程序段的时间复杂度为( )。

i=1;
j=0;
while (i+j<n)
    if (i>j)
        j++;
    else
        i++;

A. O(2n)
B. O(n²)
C. O(n)
D. O(1)
答案：C

在数据结构中，从逻辑上可以把数据结构分为( )两大类。
A. 线性结构和非线性结构
B. 紧凑结构和非紧凑结构
C. 静态结构和动态结构
D. 内部结构和外部结构
答案：A

第2章线性表

2.1 线性表的定义

线性表：是具有相同数据类型的n(n≥0)个数据元素的有限序列。
特点：存在唯一的第一个元素和最后一个元素；除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

2.2 线性表的顺序表示（顺序表）

用一组地址连续的存储单元依次存储线性表的元素。
特点：逻辑上相邻的元素物理上也相邻。
元素位置计算公式：LOC(aᵢ) = LOC(a₁) + (i-1) * sizeof(ElemType)
优点：随机存取。
缺点：插入、删除需要移动大量元素。

2.3 线性表的链式表示（链表）

用一组任意的存储单元存储线性表的数据元素，通过指针表示逻辑关系。
结点结构：数据域 + 指针域。
分类：
单链表：每个结点包含数据域和指向下一个结点的指针。
双链表：每个结点包含指向前驱和后继结点的指针。
循环链表：尾结点的指针指向头结点。
静态链表：借助数组描述链表。

2.4 顺序表与链表的比较

比较项目	顺序表	链表
存储空间	预先分配，易产生碎片	动态分配，空间利用率高
存取方式	随机存取	顺序存取
插入/删除	平均移动n/2个元素	修改指针，效率高
适用情况	表长变化不大，频繁查询	表长变化大，频繁插入/删除

2.5 例题

采用顺序存储结构存储的线性表，其第一个的地址为100，每个元素的长度为2，则第5个元素的地址为( )。
A. 110
B. 108
C. 100
D. 120
答案：B (LOC = 100 + (5-1)*2 = 108)
不带头结点的单链表head为空的判定条件是( )。
A. head==NULL
B. head->next==NULL
C. head->next==head
D. head!=NULL
答案：A
带头结点的单链表head为空的判定条件是( )。
A. head==NULL
B. head->next==NULL
C. head->next==head
D. head!=NULL
答案：B
非空循环单链表head的尾结点(由p指向)满足( )。
A. p->next==NULL
B. p==NULL
C. p->next==head
D. p=head
答案：C
在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行( )。
A. s->next=p;p->next=s
B. s->next=p->next;p->next=s
C. s->next=p->next;p=s
D. p->next=s;s->next=p
答案：B
从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需要平均比较( )个结点。
A. n
B. n/2
C. (n-1)/2
D. (n+1)/2
答案：D (平均查找长度ASL = (n+1)/2)
在一个具有n个结点的有序单链表中插人一个新结点并仍然有序的时间复杂度是( )。
A. 0(1)
B. O(n²）
C. O(n)
D. O(log₂n)
答案：C
在一个长度为n的顺序表中，向第i个元素(1<=i<=n+1)位置插入一个新元素时需要移动( )个元素。
A. n-i
B. n-i+1
C. n-i-1
D. i
答案：B (移动从第i个到第n个元素，共n-i+1个)
线性表若采用链表存储结构时，要求内存中可用存储单元的地址（）。
A. 必须是连续的
B. 部分地址必须是连续的
C. 一定是不连续的
D. 连续不连续都可以
答案：D
链表不具有的特点是（）。
A. 可随机访问任一个元素
B. 不必事先估计存储空间
C. 插入删除不需要移动元素
D. 所需空间及线性表长度成正比
答案：A
若线性表最常用的操作是存取第i个元素及其前趋的值，那么最节省操作时间的存储方式是（）。
A. 单链表
B. 双链表
C. 单循环链表
D. 顺序表
答案：D
对于一个线性表，若既要求能够进行较快地插入和删除，又要求存储结构能够反映出数据元素之间的关系，则应该以( )。
A. 顺序方式存储
B. 链式存储
C. 散列方式存储
D. 散列方式存储
答案：B
在一个长度为n的顺序表中，删除下标为i的元素（0<=i<=n-1）时，需向前移动（）个元素。
A. n-i
B. n-i+1
C. i
D. n-i-1
答案：D (移动从第i+1个到第n个元素，共n-i-1个)
在一个具有n个结点的单链表的p结点之后插入一个新结点s的算法时间复杂度为（）。
A. O(n)
B. O(1)
C. O(n²)
D. O(log₂n)
答案：B

第3章栈和队列

3.1 栈

定义：只允许在一端进行插入和删除的线性表。
操作特性：后进先出（LIFO）。
基本操作：InitStack, Push, Pop, GetTop。
存储结构：顺序栈、链栈。
应用：递归调用、函数调用、表达式求值、括号匹配。

3.2 队列

定义：只允许在一端插入，在另一端删除的线性表。
操作特性：先进先出（FIFO）。
基本操作：InitQueue, EnQueue, DeQueue, GetHead。
存储结构：
顺序队列：易产生”假溢出”。
循环队列：解决假溢出问题。
队空条件：Q.front == Q.rear
队满条件：(Q.rear+1) % MaxSize == Q.front
队列长度：(Q.rear - Q.front + MaxSize) % MaxSize

3.3 栈和队列的比较

结构	操作规则	插入/删除位置
栈	LIFO	同一端（栈顶）
队列	FIFO	不同端（队尾插入，队头删除）

3.4 例题

一个栈的输人序列为1，2，3，…，n，若输出序列的第1个元素为n，输出第i(1<=i<=n)个元素是( )。
A. 不确定
B. n-i+1
C. i
D. n-i
答案：B
如果用数组A[1…100]来实现一个大小为100的栈，并且用变量top来指示栈顶，top的初值为0，表示栈空。请问在top为100时，再进行入栈操作，会产生( )。
A. 正常入栈
B. 上溢
C. 下溢
D. 同步
答案：B
栈可以在( )中应用。
A. 递归调用
B. 子程序调用
C. 表达式求值
D. A，B，C
答案：D
链式存储的队列，在进行删除运算时，( )。
A. 仅修改头指针
B. 仅修改尾指针
C. 头、尾指针都要修改
D. 头、尾指针可能都要修改
答案：D (若删除后队列为空，则需修改尾指针)
循环队列A[0…m-1]存放其元素值，分别用front和rear表示队头和队尾，则当前队列中的元素个数是( )。
A. (rear- front+ m) %m
B. rear- front+ 1
C. rear- front- 1
D. rear- front
答案：A
将一个递归算法改为对应的非递归算法时，通常需要使用（）。
A. 栈
B. 队列
C. 循环队列
D. 优先队列
答案：A
循环队列sq的队满条件为（）。
A. (sq.rear+1)%maxsize==(sq.front+1)%maxsize
B. sq.(rear+1)%maxsize==sq.front
C. (sq.rear)%maxsize==sq.front+1
D. sq.rear==sq.front
答案：B
一个栈的输入序列是1 2 3 4 5，则下列序列中是栈的输出序列的是（）。
A. 2,4,3,1,5
B. 5,1,4,3,2
C. 3,1,2,5,4
D. 1,4,2,5,3
答案：A
若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除两个元素，再加入一个元素后，rear和front的值分别为多少？（）
A. 1和5
B. 2和4
C. 4和2
D. 5和1
答案：A (删除两个：front=(3+2)%6=5；加入一个：rear=(0+1)%6=1)
循环队列的队空条件为（）。
A. sq.rear==sq.front
B. (sq.rear+1)%maxsize==sq.front+1
C. sq.(rear+1)%maxsize==sq.front
D. (sq.rear+1)%maxsize==(sq.front+1)%maxsize
答案：A
设计一个判别表达式中左、右括号是否配对出现的算法，采用（）数据结构最佳。
A. 线性表的顺序存储结构
B. 栈
C. 队列
D. 线性表的链式存储结构
答案：B
队和栈的主要区别是( )。
A. 所包含的运算个数不同
B. 存储结构不同
C. 逻辑结构不同
D. 限定插入和删除的位置不同
答案：D
假设栈初始为空，push和pop操作交替进行，且pop操作总是针对栈顶元素。给定一个栈的push和pop操作序列，以下哪个序列是无效的？（）
A. push A, push B, pop B, push C, pop C, pop A
B. push A, push B, push C, pop C, pop A, pop B
C. push A, pop A, push B, push C, pop C, pop B
D. push A, push B, pop B, pop A, push C, pop C
答案：B (pop A时，栈顶元素是B，无法直接pop A)
在一个空队列中，依次入队元素1、2、3，然后出队两个元素，再入队元素4。此时队列中的元素顺序是（）。
A. 1, 2, 3, 4
B. 3, 4
C. 1, 2, 4
D. 3, 4, 1, 2
答案：B (出队1,2后，队列剩3；入队4后，队列为3,4)
假设遇到左括号则push，遇到右括号则pop并检查匹配。使用栈检查括号字符串”({[]})”是否匹配时，栈的操作序列是（）
A. push ‘(‘, push ‘{‘, push ‘[‘, pop ‘[‘, pop ‘{‘, pop ‘(‘
B. push ‘(‘, push ‘{‘, push ‘[‘, pop ‘(‘, pop ‘{‘, pop ‘[‘
C. push ‘(‘, push ‘{‘, pop ‘{‘, push ‘[‘, pop ‘[‘, pop ‘(‘
D. push ‘(‘, pop ‘(‘, push ‘{‘, pop ‘{‘, push ‘[‘, pop ‘[‘
答案：A
在一个大小为5的循环队列中，front指向队首元素，rear指向队尾元素的下一个位置（即下一个入队位置）。初始状态为front=0, rear=3。经过两次出队操作和一次入队操作后，front和rear的值分别是多少?( )
A. front=2, rear=4
B. front=3, rear=4
C. front=2, rear=3
D. front=3, rear=3
答案：A (两次出队：front=(0+2)%5=2；一次入队：rear=(3+1)%5=4)
用两个栈S1和S2模拟一个队列。入队操作直接push到S1，出队操作从S2 pop；如果S2为空，则将S1中的所有元素pop并push到S2。依次执行入队1、2、3，然后出队一次，再入队4，再出队两次。第二次出队的元素是什么？( )
A. 1
B. 2
C. 3
D. 4
答案：B (入队1,2,3(S1: 栈顶->3,2,1)；出队：S1倒入S2(S2: 栈顶->1,2,3)，pop S2得1；入队4(S1: 4)；出队：S2不空，pop S2得2)

第4章树和二叉树

4.1 树的基本概念

树的定义：n(n≥0)个结点的有限集。n=0时为空树。
基本术语：
结点：树中的每个元素称为结点。包含一个数据元素的值和若干指向结点的指针。
结点的度：结点的子树个数。
叶结点：度为的结点。又称为终端结点。
分支结点：除叶结点外的结点。又称为非终端结点。
子女结点：结点的子树的根结点称为该结点的子女结点。
双亲结点：若结点是结点的子女结点，则结点是结点的双亲结点。
兄弟结点：同一双亲结点的子女结点之间互称为兄弟结点。
祖先结点：从根结点到该结点的路径上的所有结点。
子孙结点：以某结点为根的子树中除了根结点之外的所有结点。
结点间的路径：从一个结点到另一个结点的分支构成的序列。
结点的深度：即结点到根结点的路径长度 + 1，根结点的深度为。
结点的高度：空树的高度为，叶结点的高度为，非叶结点的高度为其所有子女结点的最大高度 + 1。
树的深度：树中所有结点的最大深度。
树的高度：根结点的高度。树的高度与树的深度相等。
树的宽度：树中各层结点的最大个数。
树的度：树中结点的最大度数。
有序树：树中结点的各子树有序排列。其中是第一个子树，是第二个子树，。
无序树：树中结点的各子树无序排列，各棵子树之间的顺序不重要。
森林：棵互不相交的树的集合。

4.2 二叉树

定义：每个结点至多有两棵子树，且子树有左右之分。
性质：

在非空二叉树的第i层上至多有$2^i$个结点（i>=0）。
深度为k的二叉树至多有 $2^{k+1}-1$个结点。
对任何二叉树，若叶子结点数为n₀，度为2的结点数为n₂，则$n_₀ = n_₂ + 1$ 。
具有n个结点的完全二叉树的深度k为$log_2n$
如果对一棵有n个结点的完全二叉树按层次次序从0开始编号，则对任一结点 $ i$ $ (0\leq i\leq n-1)$，有：
在满二叉树中，叶结点的个数比分支结点个数多1
在扩充二叉树中，外部结点的个数比内部结点的个数多1

特殊二叉树：满二叉树、完全二叉树。
存储结构：顺序存储、链式存储（二叉链表）。

4.3 二叉树的遍历

先序遍历：根 -> 左 -> 右
中序遍历：左 -> 根 -> 右
后序遍历：左 -> 右 -> 根
层次遍历：按层从左到右

4.4 哈夫曼树

定义：带权路径长度(WPL)最小的二叉树。
构造方法：每次选两棵根结点权值最小的树作为左右子树构造新树。
性质：没有度为1的结点；n个叶子结点的哈夫曼树共有2n-1个结点。
应用：哈夫曼编码（前缀编码）:

4.5 树和森林

树和树林的遍历:
树的存储表示：方法优点缺点树的双亲表示法容易找到父结点及其所有的祖先；
能找到结点的子女和兄弟；找结点的子女和兄弟比较费事，需要查询整个数组；
没有表示出结点之间的左右次序；改进先根序列树的长子兄弟表示法容易找到的子女和右兄弟；找结点的父结点难；树的子表表示法求某个结点的最左子女运算很容易实现
找到结点的全部子女也很容易求某个结点的父母实现起来比较费事
求某个结点的右兄弟实现起来比较费事
森林与二叉树的转换：树的孩子兄弟表示法可将其转换为二叉树。
- 树、树林转换为二叉树
- 二叉树转换为树或树林（转化成的树与森林是唯一的）
树和森林的遍历： 树的遍历：
先序遍历：根结点 -> 第一个子女结点 -> 第一个子女结点的子树 -> 第二个子女结点 -> 第二个子女结点的子树 ->
后序遍历：第一个子女结点 -> 第一个子女结点的子树 -> 第二个子女结点 -> 第二个子女结点的子树 ->
层次遍历：从上到下，从左到右树的先序遍历与其转化成二叉树后的先序遍历是一致的。树的后序遍历与其转化成二叉树后的中序遍历是一致的。 森林的遍历：
先根次序遍历：对每一课树进行先序遍历。
中根次序遍历：对每一课树进行后序遍历。
层次遍历：从上到下，从左到右，不要每棵树单独解决，而是将森林看作一个树（忽略最外层的根结点）。

4.6 例题

设有n个结点的二叉树上只有度为0和度为2的结点，则此二叉树中叶子结点数为( )。
A. n/2
B. (n-1)/2
C. (n+1)/2
D. 不能确定
答案：C (由性质n₀ = n₂ + 1，且n = n₀ + n₂，联立解得n₀ = (n+1)/2)
已知某二叉树的后序遍历序列是DABEC，中序遍历序列是DEBAC，则其先序遍历的结点访问序列是（）。
A. ACBED
B. DECAB
C. DEABC
D. CEDBA
答案：D (后序最后一个C是根；中序划分左子树DEBA，右子树空；递归求解)
已知某二叉树的先序遍历序列是ABDGCEFH，中序遍历序列是DGBAECHF，则其后序遍历的结点访问序列是（）。
A. BDGCEFHA
B. GDBECFHA
C. BDGAECHF
D. GDBEHFCA
答案：D
根为第1层，深度为5的二叉树至多有（）个结点。
A. 15
B. 31
C. 16
D. 10
答案：B (2^5 - 1 = 31)
哈夫曼树中度为1的结点个数为（）。
A. 0
B. 1
C. 2
D. 不确定
答案：A
设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1、m2和m3。与森林F对应的二叉树根结点的右子树上的结点个数是（ )。
A. m2
B. m2+m3
C. m3
D. m1+m2
答案：B (森林转二叉树：第一棵树为根，第二棵树为右子树，第三棵树接在第二棵树后面)
一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )。
A. 501
B. 500
C. 254
D. 505
答案：A (n=1001为奇数，则n₀ = (n+1)/2 = 501)
利用二叉链表存储树，则根结点的右指针是( )。
A. 指向最左孩子
B. 指向最右孩子
C. 空
D. 非空
答案：C (树的孩子兄弟表示法中，根结点没有兄弟，故右指针为空)
下述编码中哪一个不是前缀码( )。
A. (00,01,10,11)
B. (0,1,00,11)
C. (0,10,110,111)
D. (1,01,000,001)
答案：B (0是00的前缀)
在树中除根结点外，其余结点分成m(m≥0)个（）的集合T1，T2，T3…Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。
A. 互不相交
B. 可以相交
C. 叶子结点可以相交
D. 树枝结点可以相交
答案：A
假设在一个二叉树中，双分支结点数为14，单分支结点数为32，则叶子结点数为（）个。
A. 14
B. 15
C. 16
D. 17
答案：B (n₂=14, n₁=32, n₀ = n₂ + 1 = 15)
在有n个叶子结点的哈夫曼树中，其结点总数为（）。
A. 不确定
B. 2n
C. 2n+1
D. 2n-1
答案：D
已知一棵完全二叉树的结点总数为10个，则最后一层的结点数为（）。
A. 1
B. 2
C. 3
D. 4
答案：C (深度为4的满二叉树有15个结点，深度为3的满二叉树有7个结点。10-7=3)
二叉排序树（）遍历是一个有序序列。
A. 中序
B. 前序
C. 后序
D. 层次
答案：A
在完全二叉树（根结点从1开始编号）中，当i为奇数且不等于1时，结点i的左兄弟是结点（），否则没有左兄弟。
A. i+1
B. 2i-1
C. 2i+1
D. i-1
答案：D
假设根结点为第1层，则在一棵二叉树上第5层的结点数最多为（）。
A. 4
B. 32
C. 8
D. 16
答案：D (2^(5-1) = 16)

第5章搜索树 + 第7章字典

5.1 二分查找

适用条件：顺序存储结构、按关键字有序。
基本思想：每次将待查区间缩小一半。
时间复杂度：O(log₂n)。
平均查找长度ASL：成功情况下ASL ≈ log₂(n+1)-1。

5.2 二叉排序树（BST）

定义：左子树所有结点值 < 根结点值 < 右子树所有结点值。
性质：中序遍历序列是递增有序序列。
查找：从根开始，比较关键字，小则左查，大则右查。
插入：查找不成功时，插入位置必为叶子结点。
删除：
叶子结点：直接删除。
只有一棵子树：用子树替代。
有两棵子树：用中序前驱或后继替代，再删除那个结点。
效率：平均O(log₂n)，最坏O(n)（单支树）。

5.3 哈希表（散列表）

基本思想：根据关键字直接访问存储位置。
哈希函数构造方法：直接定址法、除留余数法、数字分析法、平方取中法。
处理冲突的方法：
开放定址法：线性探测法、二次探测法、伪随机探测法。
链地址法：将所有同义词存储在一个链表中。
性能分析：装填因子α = 表中记录数n / 散列表长度m。ASL与α有关。

5.4 例题

二分查找法适用于存储结构为( )的，且按关键字排好序的线性表。
A. 顺序存储
B. 链式存储
C. 顺序存储或链式存储
D. 索引存储
答案：A
对于长度为18的顺序存储的有序表，若采用二分查找，则查找第1个元素的比较次数为（）。
A. 3
B. 4
C. 5
D. 6
答案：B (查找过程：mid=9, mid=4, mid=2, mid=1，共4次比较)
对于一组记录的关键字值(25，38，63，74)，采用折半查找25时，( )次查找成功。
A. 4
B. 3
C. 2
D. 1
答案：C (第一次mid=(1+4)/2=2, 关键字38>25；第二次mid=1, 关键字25，找到)
对于顺序存储的有序表(6,10,22,26,38,41,46,50,66)，若采用折半查找，则查找元素50的比较次数为（）。
A. 2
B. 3
C. 4
D. 5
答案：B (low=1, high=9, mid1=5(38), mid2=7(46), mid3=8(50))
具有12个关键字的有序表，等概率的情况下二分查找的平均检索长度ASL约为（）。
A. 38/12
B. 3
C. 4
D. 5
答案：A (ASL = (1 * 1 + 2 * 2 + 3 * 4 + 4 * 5) / 12 = 37/12 ≈ 38/12)
二叉排序树的查找效率与二叉树的树形有关，在（）时其查找效率最低。
A. 结点太多
B. 完全二叉树
C. 结点太复杂
D. 呈单支树
答案：D
关于二叉排序树（Binary Search Tree），以下哪项描述是正确的？
A. 中序遍历二叉排序树可得到一个有序序列
B. 插入操作的最坏时间复杂度为 O(log n)
C. 删除结点时一定会改变树的结构
D. 任意结点的左子树包含比该结点值大的元素
答案：A
在长度为 n 的有序数组中进行二分查找，以下哪项说法是错误的？
A. 查找过程每次将搜索范围减半
B. 最坏情况下需要比较 O(log n) 次
C. 二分查找要求数据必须存储在数组中
D. 平均时间复杂度为 O(log n)
答案：C (也可用其他顺序存储结构)
哈希表中解决冲突的“链地址法”是指（）。
A. 将所有冲突元素存储在一个链表中
B. 在哈希表外另建一个链表存储冲突元素
C. 通过线性探测寻找下一个空闲位置
D. 使用第二个哈希函数计算新地址
答案：A
** 对二叉排序树进行查找操作，最坏情况下的时间复杂度是( )。**
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
答案：C
二分查找算法适用于以下哪种存储结构？
A. 双向链表
B. 顺序存储的有序表
C. 二叉链表
D. 图结构
答案：B
在二叉排序树中插入一个新节点时，该节点最终被插入的位置是（）。
A. 作为根节点
B. 作为最后一个访问节点的子节点
C. 作为第一个比它大的节点的左子节点
D. 根据其关键字大小找到的叶子节点位置
答案：D
哈希函数的目标是（）。
A. 尽可能减少冲突
B. 将关键字均匀映射到哈希表地址空间中
C. 避免使用取模运算
D. 确保每个关键字映射到唯一地址
答案：B
若二叉排序树的所有非叶子节点都有左右子节点，则以下哪种说法正确？
A. 树的高度为 O(log n)
B. 树是完全二叉树
C. 查找效率一定优于哈希表
D. 中序遍历结果为升序序列
答案：D
关于开放地址法（Open Addressing）解决哈希冲突，错误的是( )。
A. 线性探测可能导致“聚集”现象
B. 二次探测可以避免“聚集”问题
C. 删除操作需要特殊标记而非直接删除
D. 所有元素都存储在哈希表数组内
答案：B (二次探测只能减少聚集，不能完全避免)

第6章图

6.1 图的基本概念

定义：G=(V, E)，V是顶点集，E是边集。
分类：
无向图：边无方向。
有向图：边有方向（弧）。
完全图：无向完全图边数=n(n-1)/2；有向完全图边数=n(n-1)。
连通图：任意两顶点间有路径。
强连通图：有向图中任意两顶点间双向有路径。
基本术语：顶点的度、入度、出度、路径、路径长度、回路、简单路径、简单回路、连通分量、强连通分量、生成树、生成森林。

6.2 图的存储结构

邻接矩阵：用二维数组表示顶点间相邻关系。
无向图：对称矩阵；第i行非零元素个数=顶点i的度。
有向图：第i行非零元素个数=顶点i的出度；第i列非零元素个数=顶点i的入度。
邻接表：为每个顶点建立单链表，存放其邻接点。
无向图：边结点数为2|E|。
有向图：边结点数为|E|。
空间开销：
无论有向图还是无向图，其邻接矩阵表示的空间代价O(n2)
如果G为无向图，其邻接表的空间代价O(n+2e)
如果G为有向图，其邻接表的空间代价O(n+e)
邻接矩阵只与顶点数有关；邻接表与顶点数和边数有关；
如果e<<n2，采用邻接表较为省空间开销；
如果e接近n2,采用邻接矩阵更省空间（因为邻接表中要有指针域的开销）；

6.3 图的周游

深度优先搜索(DFS)：类似树的先序遍历。递归或栈实现。
指定顶点v出发，先访问顶点v，并将其标记为已访问过；
如果存在与v邻接顶点没有被访问，则选择其中的一个w出发进行深度优先搜索DFS(W)
否则，返回；
如果图中还有未被访问的顶点，则从另一未被访问过的顶点出发重复上述过程，直到图中所有顶点都被访问过为止
广度优先搜索(BFS)：类似树的层次遍历。队列实现。
从指定顶点v出发，先访问顶点v，并将其标记为已访问过
依次访问v的所有相邻结点w1，w2，…，wn
再依次访问与w1，w2，…，wn邻接的所有未被访问过的顶点
以此类推，直到所有已访问顶点的相邻结点都被访问过为止

6.4 图的应用

最小生成树(MST)：权值和最小的生成树。
Prim（普里姆）算法：从顶点出发，每次选连接当前树的最小权边。
设$G=(V, E)$，最小生成树$Tmst=(V_T,E_T)$
1. 从图G中任意顶点Vm（$V_m∈V$）开始，将$Vm$加入到最小生成树；
2. 选择代价最小的边（$V_k,V_j$）加入到最小生成树中，并将顶点$V_j$加入到最小生成树；要求：
- 两个顶点属于不同的集合，$V_k∈V_T , V_j∈V−V_T$；
- 加入的边不能产生回路；
1. 重复这个过程，直到$Tmst$中有n-1条边为止，即$V_T=V$
设置三个数组
1. component [j]数组用来记录已加入最小生成树的顶点j，初始化component [j]=0，当顶点j加入最小生成树后，设置component [j]=1
2. distance[j]数组用来记录代价最小的边$（V_k,V_j）$的权值，其中V_k∈component[] 初始化distance[j]=graphMatrix->graph[0][j]
3. neighbor[j] 数组用来记录代价最小的边$（V_k,V_j）$对应的顶点V_k，初始化neighbor[j] = 0;
Kruskal（克鲁斯卡尔）算法：每次选不构成回路的权最小边。
设$G=(V, E)$，最小生成树$Tmst=(V_T,E_T)$
1. 将图G中边的代价按照非递减的顺序排序；
2. 在E中选择最小的边$e_i,j（V_i,V_j）$，如果顶点V_i,V_j属于两个不同连通分量加入到最小生成树$Tmst$
3. $E=E−e_i,j$
4. 重复这个过程，直到$Tmst$中有n-1条边为止（即只有一个连通分量）

最短路径：
Dijkstra算法：单源最短路径（权值非负）。
Dijkstra算法时间复杂度：
- 算法中的初始化部分的时间复杂度为O(n)，
- 求最短路径部分由一个大循环组成，其中外循环运行n-1次，内循环为两个，均运行n-1次。
- 算法的时间复杂度为O(n2)
Dijkstra算法空间复杂度：
- 空间开销需要distance[]和path[]数组，大小为O(n)
Floyd算法：各顶点对间最短路径。
拓扑排序：AOV网中，顶点表示活动，边表示先后关系。找入度为0的顶点并删除其出边，重复。
拓扑排序算法核心过程：
1. 计算各个顶点的入度；
2. 将入度为0的顶点入栈；
3. 如果栈不空，从栈中取出一个元素v，输出到拓扑序列中；
4. 检查顶点v的出边表，将出边表中的每个顶点w的入度减1（即删除顶点v为弧头的边表），如果w的入度为0，则顶点w入栈
5. 重复第三步和第四步，直到栈为空结束
关键路径：AOE网中，从源点到汇点的最长路径。

带权的有向图；
顶点表示事件，有向边表示活动；
边上的权值表示活动持续的时间；
顶点所表示的事件实际上就是它的入边所表示的活动都已完成，它的出边所表示的活动可以开始这样一种状态；
只有一个入度为0的顶点
只有一个出度为0的顶点

事件的最早发生时间(earliestTime):
- 事件V_i的最早可能的开始时间，是从开始顶点V_0到顶点V_i的最长路径的长度。计算事件的最早发生时间。
- 采用正向递推方式：初始earliestTime[0] = 0；
- $earliestTime[j] = max{ earliestTime[i]+weight}$
- 其中，是以顶点vj为终点的所有有向边
事件的最迟发生时间(latestTime):
- 事件V_i最迟允许的开始时间，是指在不推迟整个工期的前提下，事件V_i允许的最晚时间。
- 采用反向递推方式：初始$latestTime[n-1] = earliestTime[n-1]$
- $latestTime[j] = min{ latestTime[i]- weight}$
- 其中，$$是以顶点vj为起点的所有有向边
活动的最早发生时间计算activityEarliestTime:
- 设Ck是边< vi,vj >上的活动，则activityEarliestTime是源点v0到起始顶点vi的最长路径长度，即为： activityEarliestTime[k] = earliestTime[i]

6.5 例题

具有4个结点的无向图最多有（）条边。
A. 6
B. 12
C. 16
D. 20
答案：A (4 * 3/2=6)
对于具有n个顶点的连通无向图，其边的个数至少为( )。
A. n-1
B. n
C. n+1
D. nlog₂n
答案：A (树是边最少的连通图)
在一个无向图中，所有顶点的度之和等于所有边数的( )倍。
A. 1/2
B. 2
C. 1
D. 4
答案：B (每条边贡献2度)
在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的( )倍。
A. 1/2
B. 2
C. 1
D. 4
答案：C (都等于边数)
对于一个具有n（n>1）个顶点的有向图，其为强连通图时，该图中弧的条数的最小值为( )。
A. n+1
B. n
C. n-1
D. n-2
答案：B (环，n条弧)
图的深度、广度优先遍历算法分别类似于二叉树的( )。
A. 先序遍历和中序遍历
B. 先序遍历和层序遍历
C. 后序遍历和中序遍历
D. 层序遍历和先序遍历
答案：B
有n个顶点e条边的无向图G，它的邻接表表示中单链表的结点总数是( )。
A. 2n
B. n
C. 2e
D. e
答案：C (无向图每条边存两次)
连通图G中有n个顶点，G的生成树是( )的连通子图。
A. 包含G的所有顶点
B. 不必包含G的所有顶点
C. 包含G的所有边
D. 包含G的所有顶点和所有边
答案：A
对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为（）。
A. 0
B. 1
C. n
D. n+1
答案：B
下面关于图的存储的叙述中正确的是( )。
A. 用邻接矩阵法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关
B. 用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
C. 邻接表法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关
D. 用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
答案：A (邻接矩阵空间为O(n²))
在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于（）。
A. 1
B. 0
C. i-j
D. 不确定
答案：A (无向图邻接矩阵对称)
导致图的遍历序列不唯一的因素有( )。
A. 出发点不同、遍历方法不同
B. 出发点不同、存储结构不同
C. 遍历方法不同、存储结构不同
D. 出发点不同、存储结构不同、遍历方法不同
答案：D
对于一个有向图，若一个顶点的入度为k1、出度为k2，则对应邻接表中该顶点单链表中的结点数为（）。
A. k1
B. k2
C. k1+k2
D. k1-k2
答案：B (邻接表存出边)
在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为（）。
A. n
B. e
C. 2e
D. n+e
答案：C
在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（）。
A. n
B. e
C. 2e
D. n+e
答案：C (无向图对称，每条边存两次)
由一个具有n个顶点的连通图生成的最小生成树中，具有（）条边。
A. n
B. n+1
C. n-1
D. 2n
答案：C (树的性质)

第8章排序

8.1 排序的基本概念

排序：将一组无序序列按关键字递增或递减重新排列。
稳定性：关键字相同的元素，排序后相对位置不变。
内部排序：数据全部在内存中。
外部排序：数据量大，需内外存交换。

8.2 插入排序

直接插入排序：将待排序记录插入已排好序的子序列中。
时间复杂度：最好O(n)，最坏/平均O(n²)。
空间复杂度：O(1)。
稳定。
希尔排序：分组进行直接插入排序，增量逐渐缩小至1。
时间复杂度：约O(n^1.3)，最坏O(n²)。
空间复杂度：O(1)。
不稳定。

8.3 交换排序

冒泡排序：相邻元素比较交换，将最大/最小元素”冒泡”到最终位置。
时间复杂度：最好O(n)，最坏/平均O(n²)。
空间复杂度：O(1)。
稳定。
快速排序：选一基准，将序列分为两部分，递归排序。
时间复杂度：平均/最好O(nlog₂n)，最坏O(n²)。
空间复杂度：平均O(log₂n)，最坏O(n)。
不稳定。

8.4 选择排序

简单选择排序：每次选最小/最大元素放最终位置。
时间复杂度：O(n²)。
空间复杂度：O(1)。
不稳定。
堆排序：将序列构建成大顶堆/小顶堆，交换堆顶与堆底元素，调整堆。
时间复杂度：O(nlog₂n)。
空间复杂度：O(1)。
不稳定。

8.5 归并排序

二路归并排序：将两个有序子序列合并成一个有序序列。
时间复杂度：O(nlog₂n)。
空间复杂度：O(n)。
稳定。

8.6 基数排序

多关键字排序：按位排序，从低位到高位。
时间复杂度：O(d(n+r))。
空间复杂度：O(n+r)。
稳定。

8.7 各种排序方法的比较

排序方法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
直接插入排序	O(n²)	O(n²)	O(1)	稳定
希尔排序	O(n^1.3)	O(n²)	O(1)	不稳定
冒泡排序	O(n²)	O(n²)	O(1)	稳定
快速排序	O(nlog₂n)	O(n²)	O(log₂n)	不稳定
简单选择排序	O(n²)	O(n²)	O(1)	不稳定
堆排序	O(nlog₂n)	O(nlog₂n)	O(1)	不稳定
二路归并排序	O(nlog₂n)	O(nlog₂n)	O(n)	稳定
基数排序	O(d(n+r))	O(d(n+r))	O(n+r)	稳定

8.8 例题

下列排序算法中，第一趟排序结束后其最大或最小元素一定在其最终位置上的算法是( )。
A. 归并排序
B. 直接插入排序
C. 快速排序
D. 冒泡排序
答案：D
其比较次数与待排序的记录的初始状态无关的是( )。
A. 插人排序
B. 简单选择排序
C. 快速排序
D. 冒泡排序
答案：B
一组记录的关键字值为(45，79，56，38，40，86)，以第一个记录为基准，利用快速排序算法得到的第一次排序结果是( )。
A. {38,40,45,56,79,86}
B. {40,38,45,79,56,86}
C. {40,38,45,56,79,86}
D. {40,38,45,86,56,79}
答案：C (基准45，划分后左子序列40,38，右子序列56,79,86)
采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（）。
A. 插入和快速
B. 冒泡和快速
C. 选择和插入
D. 选择和冒泡
答案：C
排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置，这是( )的基本思想。
A. 插入排序
B. 归并排序
C. 冒泡排序
D. 堆排序
答案：C
下列排序算法中，平均时间复杂度为O(nlog₂n)的是( )。
A. 直接插人排序
B. 冒泡排序
C. 归并排序
D. 简单选择排序
答案：C
在对n个元素进行直接插入排序的过程中，共需进行（）趟。
A. n
B. n-1
C. n+1
D. 2n
答案：B
对序列{15,9,7,8,20,-1,4}进行排序，进行一趟后数据的排列变为{4,9,-1,8,20,7,15}；则采用的是（）排序。
A. 冒泡
B. 选择
C. 希尔
D. 快速
答案：C (希尔排序，增量分组)
在对n个元素进行简单选择排序的过程中，需要进行（）趟选择和交换。
A. n
B. n+1
C. n-1
D. n/2
答案：C
设一组初始记录关键字序列为(50，40，95，25，10，70，60，45)，则以增量d=3的一趟希尔排序结束后前4条记录关键字为( )。
A. 25，40，50，95
B. 10，40，60，25
C. 10，25，40，45
D. 25，10，70，50
答案：D (分组：50-25-60, 40-10-45, 95-70。组内排序后为25,50,60; 10,40,45; 70,95。序列前4个为25,10,70,50)

2025 年 11 月
一	二	三	四	五	六	日
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30