数据结构与算法知识点

选择题

数据结构是研究程序设计中数据的 C.逻辑存储 及它们之间计算方法和运算的学科。
数据结构是研究程序设计中数据的元素及它们之间的 A.元素 和运算的学科。
数据的逻辑结构分为 C.线性结构和非线性结构 两类。
数据的逻辑结构是 A.数据元素之间逻辑 关系的整体。
在线性表的下列存储结构中，读取指定序号的元素所花费的时间最少的是 D.顺序表 。
链表不具有的特点是（）。
A.可随机访问任一元素
栈是一种（）。
B.先进后出的线性结构
队列中出队操作发生在（）。
A.队头
在环形队列中元素的排列顺序（）。
A.由元素进队的先后顺序确定
若某环形队列有队头指针 front和队尾指针 rear，在队不满时进队操作会改变（）。
B.rear
顺序表与链表的主要区别在于（）
A.存储结构不同
在单链表中查找第 i个元素的时间复杂度是（）
C. O(n)
串是一种特殊的线性表，其特殊性体现在（）。
B.数据元素是一个在字符
以下关于串的叙述中正确的是（）。
A.串是一种特殊的线性表
两个字符串相等的条件是（）。
D.串的长度相等且对应的字符相同
设有两个串 s和 t，判断 t是否为 s的子串的算法称为（）。
C.串匹配
一个正确的递归算法通常包含（）。
C.递归出口和递归体
一个正确的递归算法通常包含（）。
C.递归出口和递归体
递归函数 f(1)=1，f(n)=f(n-1)+n(n>1)的递归体是（）。
C.f(n)=f(n-1)+n
递归函数 f(1)=1，f(n)=f(n-1)+n(n>1)的递归出口是（）。
A.f(1)=1

回到 21 题

在下列 4个广义表中，长度为 1、深度为 4的广义表是（）。
D.（（（a，（b），c）））
空的广义表是指（）。
D.不含任何元素
对于广义表（（a，b）（（）），（a，（b）））来说，其（）。
D.有 3个元素
广义表（（a，b），c，（（d），e），（f，j，（g），（h）））第 4个元素的第 3个元素是（）。
B.子表（g）

回到 25 题

度为 4、高度为 h的树（）。
A.至少有 h+3个结点

解题思路：
- 度为4的树，每个非叶节点最多有4个子节点
- 高度为h，意味着从根到叶子的最长路径为h
- 要求最少节点数，应该让每层只有1个节点(除最后一层)
- 从根到叶子形成一条链，每层1个节点，共h+1个节点
- 最后一个非叶节点至少要有2个子节点才能成为度为4的树
- 所以最少需要h+3个节点

对于一颗具有 n个结点、度为 4的树来说，（）。
A.树的高度最多是 n-3

解题思路：
- 度为4的树，每个非叶节点最多有4个子节点
- 要使高度最大，应该让每层只有1个节点(除最后一层)
- n个节点中，除去根节点和路径上的节点，剩余节点都是叶子
- 最少需要2个叶子节点才能构成度为4的树
- 所以高度最多为n-3

对于一颗具有 n个结点、度为 4的树来说，树的高度至少是（）。
D.⌈log4(2n+1)⌉

解题思路：
- 度为4时，每层节点数最多是上一层的4倍
- 第i层最多有4^(i-1)个节点
- 总节点数n满足：n ≤ 1 + 4 + 4^2 + ... + 4^(h-1)
- 等比数列求和：n ≤ (4^h - 1)/3
- 解出h ≥ log4(3n + 1)
- 取上限得到⌈log4(2n+1)⌉

在一棵 3次树中，度为 3的结点数为两个，度为 2 的结点数为一个，度为 1 的结点数为两个，则度为 0 的结点数为（）个。
B.5

解题思路：
- 设度为0的节点数为x
- 总节点数 = 2(度为3) + 1(度为2) + 2(度为1) + x(度为0) = 5 + x
- 总边数 = 节点数 - 1 = 4 + x
- 另一方面，总边数 = 3×2 + 2×1 + 1×2 = 8
- 所以 4 + x = 8
- 解得 x = 5

求解单源最短路径的常用算法是：（）
C. Dijkstra算法

解题思路：
- Dijkstra算法是解决带权有向图上单源最短路径的经典算法
- 基于贪心策略，每次选择当前最短路径
- 时间复杂度为O(V^2)，V为顶点数
- 不能处理负权边的情况

图的邻接矩阵的空间复杂度是：（）
B.O(V^2)

解题思路：
- 邻接矩阵用V×V的二维数组表示图
- V是图中顶点的个数
- 无论图是稠密还是稀疏，都需要V^2的空间
- 所以空间复杂度是O(V^2)

填空题

在线性表的链式存储结构中，元素之间的逻辑关系是通过 指针 决定的。
在线性表的顺序存储结构中，元素之间的逻辑关系是通过 物理位置 决定的。
若用不带头结点的单链表 st表示链栈，则创建一个空栈时所要执行的操作是 st = NULL;。
若用带头结点的单链表 st表示链栈，则栈空的标志是 st->next == NULL。

若 n为主串的长度，m为子串的长度，采用 BF模式匹配算法，在最好的情况下需要的字符比较次数为 m。

 解题思路：
 - 最好情况是第一次比较就匹配成功
 - 需要逐个比较子串的每个字符
 - 所以最少需要比较m次

三维数组 a[0..4][0..6][0..8]中共含有 315 个元素。

 解题思路：
 - 第一维度范围是0..4，共5个元素
 - 第二维度范围是0..6，共7个元素  
 - 第三维度范围是0..8，共9个元素
 - 总元素个数 = 5 × 7 × 9 = 315个元素

若 n为主串的长度，m为子串的长度，采用 BF模式匹配算法，在最坏的情况下需要的字符比较次数为 (n-m+1)*m。

 解题思路：
 - 最坏情况是每次比较都失败，直到最后一个位置
 - 主串中有n-m+1个可能的起始位置
 - 每个位置都需要比较m个字符
 - 总比较次数为(n-m+1)*m

一维数组 a采用顺序存储结构，下标从 0开始，每个元素占 4个存储单元，a[8] 的起始地址为 100，则 a[11]的起始地址为 112。

 解题思路：
 - a[8]的起始地址是100
 - a[11]比a[8]大3个位置
 - 每个元素占4个存储单元
 - 所以地址增加3*4=12
 - 因此a[11]的起始地址是100+12=112

一棵具有 n个结点的非空树，其中所有度之和等于 n-1。

 解题思路：
 - 树中每个边连接两个节点
 - 边数等于节点数减1
 - 每条边对应一个节点的度数
 - 所以所有节点的度数之和等于边数
 - 因此等于n-1

设某棵树中的结点值为单个字符，其后根遍历序列为 ABCDEFG，则根结点值为 G。

解题思路：
- 后根遍历的顺序是：左子树、右子树、根节点
- 遍历序列中最后一个元素就是根节点
- 序列ABCDEFG中最后一个字符是G
- 所以根节点的值为G

判断题

数据结构是带有结构的数据元素的集合。 对
空的单链表不含有任何结点。 对
算法可以用计算机语言描述，所以算法等同于程序。 错
算法是可以用计算机语言来实现，但算法并不等同于程序。算法是对问题求解步骤的一种描述，而程序是算法的具体实现。
空的单链表不含有任何结点。 对
栈和线性表是两种不同的数据结构，他们的数据元素的逻辑关系也不同。 错
栈是一种特殊的线性表，其特点是后进先出（LIFO）。因此，它们的基本逻辑关系是相同的，只是操作上有所限制。
设串 s1=”I 櫄 am 櫄 a 櫄 student”，该字符串串长为 11。 错
该字符串包含了文字、空格和特殊字符”櫄”，总长度应为19个字符（包括所有空格和特殊字符）。
设串 s1=”I am 櫄 english teacher”，该字符串串长为 15。 错
该字符串包含了文字、空格和特殊字符”櫄”，总长度应为21个字符（包括所有空格和特殊字符）。

在有向图中，各顶点的入度之和等于各顶点的出度之和。 对

 解题思路：
 - 在有向图中，每条边都有一个起点和一个终点
 - 每条边对一个顶点的出度贡献1，对另一个顶点的入度贡献1
 - 所有边的总和就是所有顶点的入度之和
 - 同时也是所有顶点的出度之和
 - 因此入度之和必然等于出度之和

无论是有向图还是无向图，其邻接矩阵表示都是唯一的。 对
对于同一个图，给定相同的顶点顺序，其邻接矩阵表示是唯一的。
环形队列不存在空间上溢出的问题。 错
环形队列虽然可以有效地利用存储空间，但在物理存储有限的情况下，仍然存在空间溢出的可能性。

程序分析题

1. 分析以下算法中各语句的频度：

设n为正整数，分析以下算法中各语句的频度

void fun ( int n )
{	
    int i, j, k;
    for( i=0; i<n; i++ )                //语句1
    {								
        for( j=0; j<n; j++ ) 
        {	c[i][j]=0; 			        //语句2
            for( k=0; k<n; k++ )        //语句3
                c[i][j]= c[i][j]+ a[i][k]* b[k][j];  //语句4
        }
    }
}

总结一下：
语句1的频度是 n + 1
语句2的频度是 n^2^
语句3的频度是 n^2^ * (n + 1)
语句4的频度是 n^3^

频度是指在算法执行过程中，某条语句的执行次数。

在分析算法时，我们通常关注：

语句的实际执行次数（精确频度）
最坏情况下的执行次数（最大频度）
平均情况下的执行次数（平均频度）

语句1 (for( i=0; i<n; i++ ))：

这是最外层的循环
循环会执行n次，每次迭代后变量i增加1
检查条件 i<n 会在循环开始前和每次循环结束后执行
因此检查条件会被执行 n+1 次
所以这个语句的频度是 n + 1

语句2 (c[i][j]=0;)：

位于第二层循环内
每当第二层循环(j)开始时执行一次
对于每个i值都会执行 n 次
外层循环执行n次
所以总执行次数为n * n = n^2^次

语句3 (for( k=0; k<n; k++ ))：

这是最内层的循环
在每次第二层循环(j)迭代中都会被初始化和检查
初始化和检查条件将在n * n次第二层循环中各发生n + 1次
即(n + 1) * n * n = n^2^ * (n + 1)次
注意:通常讨论循环频度时指的是循环体内的操作,而不是循环条件检查

语句4 (c[i][j]= c[i][j]+ a[i][k]* b[k][j]; )：

位于最内层循环中
对于每个i和j组合,执行n次(k从0到n-1)
有n * n个不同的i和j组合
因此总执行次数为n * n * n = n^3^次

2. 试举一个实例，简要说明栈和队列在程序设计中所起的作用。

栈的应用实例：

程序中的函数调用过程就是一个典型的栈操作。每当一个函数被调用时，它的参数、返回地址等信息会被压入栈中；当函数返回时，这些信息会被弹出栈。

队列的应用实例：

操作系统中的打印任务队列。多个打印任务按照先来先服务的原则排队等待打印，新任务加入队尾，打印机从队首取任务执行。

3. 假设3个元素a、b、c依次进栈，进栈和出栈操作可以交替进行，试写出所有可能的出栈序列。

a、b、c依次进栈，可能的出栈序列有 abc、acb、bac、bca、cab、cba。

4. 下面是一段简单的算法代码，请分析其功能，描述它的作用。

void bubble_sort(int arr[ ], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

（1）这段代码的核心功能是什么？

这段代码实现了一个简单的冒泡排序算法。其功能是将输入的数组 arr按从小到大的顺序排列。

（2）代码中双重循环的作用分别是什么？

外层循环：控制需要进行排序的轮数，每一轮会将当前未排序部分的最大值"冒泡"到最后。
内层循环：在每一轮中，比较相邻两个元素的大小，将较大的元素向后交换，从而逐步把最大值移动到未排序部分的末尾。

（3）如果输入数组为 [9, 1, 4, 3]，输出结果是什么？

输入数组为 [9, 1, 4, 3]，输出结果是 [1, 3, 4, 9]。

5. 下面是一段简单的算法代码，请分析其功能，描述它的作用。

int binary_search(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; 
        if (arr[mid] == target) {
            return mid;  
        } else if (arr[mid] < target) {
            left = mid + 1; 
        } else {
            right = mid - 1; 
        }
    }
return -1;
}

（1）这段代码的核心功能是什么？

这段代码实现了一个折半查找算法，用于在有序数组中查找指定目标值 target 的索引。如果找到，返回目标值所在的索引；如果找不到，返回 -1。

（2）如果输入数组为 [1, 2, 3, 4, 5]，目标值为 3，输出结果是什么？

输入数组为 [1, 2, 3, 4, 5]，目标值为 3，输出结果是 2。因为 3 在数组中的索引是 2。

（3）分析：这段算法在什么条件下才能正常运行？请说明原因。

数组必须是有序的（从小到大或从大到小的顺序）。原因是折半查找通过比较目标值与中间值的大小，决定搜索区间的左右范围。
如果数组是无序的，算法无法正确缩小范围，可能返回错误结果或进入死循环。

编程题

1. 求n!

int fun(int n) {  
    if(n==1) return 1; 
    else return n*fun(n-1); 
}

2. 求正整数n的位数

int fun(int n) {  
    if(n<10) return 1; 
    else return fun(n/ 10)+ 1; 
}

3. 设计一个算法，将一维数组 A（a1, …an）中的元素使用 `尾插法` 插入单链表 L 中。

void insertTail(Node*L, int A[], int n){ 
    Node*tail= L;//初始时尾指针指向头节点 
    for(int i= 0; i< n; i++){ 
        Node*newNode= createNode(A[i]);//创建新节点 
        tail->next= newNode; //将新节点链接到链表尾部 
        tail= newNode; //更新尾指针 
    } 
}

4. 设计一个算法，将一维数组 A（a1, …an）中的元素使用 `头插法` 插入单链表 L 中。

void insertHead(Node*L, int A[], int n){ 
    for(int i= 0; i< n; i++){ 
        Node*newNode= createNode(A[i]);//创建新节点 
        newNode->next= L->next; //新节点指向当前头节点的下一个节点 
        L->next= newNode; //头节点指针指向新节点 
    } 
}

知识点：

广义表

点击回到选择 21 题

长度：数最外层有几个项目。比如 (a, (b, c), d) 的长度是 3。
深度：看括号嵌套得有多深。比如 ((a), b, (c, (d))) 的深度是 3，因为最深的地方有三层括号。
原子数：数所有单独的元素（不带括号的）。在 ((a), b, (c, (d))) 中，原子是 a, b, c, d，所以原子数是 4。
元素数：计算所有的部分，不论是单个元素还是子列表。对于 ((a), b, (c, (d)))，
每个单独的元素和每个子列表都算一个元素，因此元素总数是 5 ((a), b, (c, (d)), c, (d))。

树

点击回到选择 25 题

树的基本概念：
- 树是由结点和边组成的非线性数据结构
- 除根结点外，每个结点都有且仅有一个父结点
- 每个结点可以有零个或多个子结点
度的概念：
- 结点的度：一个结点拥有的子结点数量
- 树的度：所有结点中最大的度数
- 例如：若一个结点有3个子结点，则其度为3
高度/深度：
- 树的高度：从根结点到最远叶子结点的路径长度
- 结点的深度：从根结点到该结点的路径长度
- 层次：根结点在第1层，其子结点在第2层，以此类推
结点分类：
- 根结点：最顶层的结点，没有父结点
- 叶子结点：度为0的结点，没有子结点
- 内部结点：既有父结点又有子结点的结点
- 分支结点：度不为0的结点，有子结点
计算：
- 若已知树的度为m和高度为h：
  - 最少结点数：h个结点(每层1个)
  - 最多结点数：(m^h - 1)/(m-1)个结点(每个结点都有m个子结点)
- 若已知结点数n和度为m：
  - 最小高度：⌈log_m(n(m-1)+1)⌉
  - 最大高度：n-(n-1)/m (向上取整)
树的遍历：
- 先序遍历(Pre-order)：根结点 -> 左子树 -> 右子树
- 中序遍历(In-order)：左子树 -> 根结点 -> 右子树
- 后序遍历(Post-order)：左子树 -> 右子树 -> 根结点

例如对于二叉树:
    A
   / \
  B   C
 / \
D   E

先序遍历结果: A B D E C
中序遍历结果: D B E A C  
后序遍历结果: D E B C A