院校：西交
875-计算机软件基础（含数据结构、程序设计）
参考书目
1、《数据结构（第二版）》 清华大学出版社 1992年6月 严蔚敏 第二版 2、《程序设计与C语言》 西安交通大学出版社 2005年8月 梁力 第二版
单项选择题5小题，每小题2分，共10分
填空题10小题，每小题3分，共30分
解答题6-8小题，共80分
程序设计题2-3小题，共30分
皮皮灰数据结构+程序设计
仅供测试
一、单项选择题 5小题，每小题2分，共10分
1.下面哪个选项中的函数是按照渐进大小的增序排列？（）
A. 2ⁿ, n + (log n)², n³, 10n², n log n
B. n + (log n)², n³, 10n², n log n, 2ⁿ
C. n + (log n)², n log n, 10n², n³, 2ⁿ
D. n + (log n)², 10n², n log n, n³, 2ⁿ
2.哪种字符串的存储结构可以方便地进行插入、删除、并联以及重新安排子字符串？（）
A. 固定长度的存储结构
B. 链表存储结构
C. 具有固定最大长度的变长存储结构
D. 数组存储结构
3.存储 10 个元素到一个哈希表，这 10 个元素的 key 是 {5,28,19,15,20,12,33,17,10,18}。哈希表总共有 9 个 slots，哈希函数是 h (k) = k mod 9，并用链表解决冲突。哈希表中最长的链表长度是？（ ）
A. 1
B. 2
C. 3
D. 4
4.满二叉树的所有中间节点都有两个孩子节点。一个有 500 个叶子节点的满二叉树有多少个中间节点？（）
A. 250
B. 499
C. 500
D. 501
5.以下哪一个关于树的描述是错误的？（）
A. 非叶节点有可能没有孩子
B. 在一棵树中加一条边会形成一个环
C. 一棵树中并非每个节点都有父亲节点
D. 一棵包含一个节点的树高度为 0
6.Prim 算法是一种计算图的最小生成树算法，Floyd - Warshall 算法可用于计算有向图中所有节点对之间的最短路径。以下哪些表述肯定是正确的？（）
i. Prim 算法是一种贪心算法。
ii. Prim 算法是一种动态规划算法。
iii. Floyd - Warshall 算法是一种贪心算法。
iv. Floyd - Warshall 算法是一种动态规划算法。
A. i 和 iii
B. i 和 iv
C. ii 和 iii
D. ii 和 iv
7.以下哪一个图的问题可以在线性时间内解决？（）
A. 找到一个无向图中的最长简单环
B. 计算有向图的强连通分量
C. 解决带权有向图的单源最短路径问题
D. 找到一个无向图的最大团
8.下列关于归并排序和快速排序的陈述哪一项是对的？（）
A. 都是用分治法
B. 给定一个长度为 n 的输入数组，都是需要 Θ(n) 的时间进行每一次切分
C. 都有相同的最坏时间复杂度
D. 以上都对
9.任何一个基于比较的算法在一个长度为 n 的数组中同时找出最大和最小值，至少需要数组元素之间的比较的次数与下列哪个最接近？（）
A. n
B. 1.5n
C. 2n
D. n²
10.对图片的像素颜色进行分类，以下哪个算法的效率最快
A. HashTable
B. Heap
C. 并查集
D. AVL
哈希表通过哈希函数将数据映射到特定的存储位置。在处理像素颜色分类时，如果哈希函数设计合理，哈希表可以在平均情况下实现接近的查找、插入和删除操作。对于像素颜色分类，主要操作是判断颜色是否已经存在于分类中，哈希表能够快速地完成这个操作。
二、填空题 10小题，每小题3分，共30分
1.已知有以下几种时间复杂度表示：，，，，，。当相同时，请将它们按照增长率从低到高的顺序依次填写在横线上：、、、、、。
2.一棵高度为5的 AVL 树（规定树根高度为），其最少拥有____个结点，最多拥有____个结点。
3.在数据结构相关知识中，一个正序数组之所以可以看作一个小根堆，是因为____（简要阐述原因）。
4.若有一个有向图，其中结点编号范围是从到，并且两点存在边的条件是当且仅当结点编号，那么该图中边的数量是____条，其拓扑排序的可能情况有____种。
5.根结点右子树的最左的无左子树结点的前驱是根结点左子树最右无右子树的结点，这棵树不可能是一颗________序线索化二叉树
6.对于所有元素都相同的数组，归并排序的算法复杂度用大表示为____，快速排序的算法复杂度用大表示为____。
7.给定中缀表达式 “（）（）”，它对应的后缀表达式为____。
8.在排序算法中，每次从未排序的部分选择一个元素，然后和已经排序的部分进行比较，这种排序方法是____排序。
9.若要逆序输出一棵含有个元素的 AVL 树中的所有偶数，其时间复杂度为____。
10.对于一个循环队列，已知队头指针指向的位置为，队尾指针指向的位置为，队列的长度为，那么该队列现有元素的个数为____（队头指向第一个结点，队尾指向最后一个结点的后面一个）。
三、解答题，共80分
1.用数学归纳法证明在一个有个顶点的无向简单图中，如果每个顶点的度数至少为，那么这个图是连通的。
皮皮灰：
证明：
当时：
此时只有一个顶点，显然是连通的，命题成立。
假设当时命题成立，即一个有个顶点且每个顶点度数至少为的无向简单图是连通的。
当时：
考虑从这个图中去掉一个顶点及与它相连的边。此时剩下的图有个顶点。
对于剩下的个顶点的图，由于顶点的度数至少为，所以去掉顶点后，其他每个顶点的度数至少为。
根据归纳假设，这个个顶点的子图是连通的。
现在把顶点再加回图中。因为的度数至少为，而子图有个顶点，所以至少与子图中的一个顶点相连。
这样就可以通过这个相连的顶点使得整个个顶点的图是连通的。
由数学归纳法可知，对于任意正整数，一个有个顶点的无向简单图中，如果每个顶点的度数至少为，那么这个图是连通的。
证明题汇总
题目一：
证明在一个有个顶点的无向完全图中，边的数量为。
证明：
对于一个有个顶点的无向完全图，每个顶点都与其他个顶点相连。
所以每个顶点有条边与之关联。
但每条边被两个顶点共享，所以总的边数为。
题目二：
证明在一个有个顶点的二叉树中，若叶子节点数为，度为的节点数为，则。
证明：
设度为的节点数为。
因为二叉树中边的数量等于节点数减一，即，同时边的数量也等于度为的节点数乘以加上度为的节点数乘以，即。
而总的节点数，将其代入可得，化简后得到。
题目三：
证明一个有向图是强连通的当且仅当对于任意两个不同的顶点和，都存在从到的路径和从到的路径。
证明：
必要性：
若有向图是强连通的，那么对于任意两个不同的顶点和，必然存在从到的路径，因为强连通意味着任意两个顶点之间都有路径可达。同理，也存在从到的路径。
充分性：
若对于任意两个不同的顶点和，都存在从到的路径和从到的路径，那么对于任意一对顶点都能互相到达，这就满足强连通的定义。
题目四：
证明在一个有个顶点的无向树中，添加一条边会形成一个唯一的圈。
证明：
由于树是无环的连通图，当添加一条边时，必然会连接两个原本不直接相连的顶点。
这样就会形成一个路径，而这个路径加上新添加的边就构成了一个圈。
因为树的性质决定了任意两个顶点之间只有一条路径，所以添加一条边后形成的圈是唯一的。
题目五：
证明在一个有个顶点的无向连通图中，如果边的数量等于，那么这个图是一棵树。
证明：
首先，已知图是无向连通图。
若边的数量等于，根据树的定义，有个顶点的树恰好有条边。
假设这个图不是树，那么它必然存在环或者不连通。但如果有环，那么边的数量会大于；如果不连通，那么边的数量也会小于。这与已知条件矛盾，所以这个图是一棵树。
题目六：
证明在一个有向无环图（DAG）中，存在一个拓扑排序。
证明：
因为有向无环图中不存在环，所以必然存在一些入度为的顶点。
选择一个入度为的顶点，将其加入拓扑排序序列中，并从图中删除该顶点及其发出的边。
重复这个过程，每次都选择一个入度为的顶点加入序列，直到所有顶点都被加入序列。
由于图是有向无环图，所以这个过程一定可以完成，从而存在一个拓扑排序。
题目七：
证明在一个二叉搜索树中，中序遍历得到的序列是一个有序序列。
证明：
二叉搜索树的定义是对于任意一个节点，其左子树中的所有节点的值都小于该节点的值，其右子树中的所有节点的值都大于该节点的值。
中序遍历的顺序是先遍历左子树，然后访问根节点，最后遍历右子树。
由于左子树中的值都小于根节点的值，右子树中的值都大于根节点的值，并且左子树和右子树也都是二叉搜索树，所以中序遍历得到的序列是一个有序序列。
题目八：
证明在一个有个顶点的无向图中，如果每个顶点的度数都至少为，那么这个图是连通的。
证明：
假设这个图不连通，那么它可以分为多个连通分量。
考虑其中一个连通分量，设其顶点数为，那么这个连通分量中每个顶点的度数最多为。
因为整个图有个顶点，所以。
但题目中每个顶点的度数都至少为，这与假设矛盾，所以这个图是连通的。
题目九：
证明在一个满二叉树中，叶子节点的数量为，其中为总节点数。
证明：
设满二叉树的高度为，根据满二叉树的性质，总节点数。
满二叉树的叶子节点数量为。
由可得，即叶子节点的数量为。
题目十：
证明在一个有向图中，如果存在一个顶点，对于任意其他顶点，都存在从到的路径，那么这个有向图存在一个有向生成树。
证明：
从顶点出发，对于任意一个顶点，如果存在从到的路径，那么在这些路径中选择一条最短的路径。
这些最短路径构成的子图就是一个有向生成树。
因为对于任意顶点，都有从到的路径，所以这个子图包含了所有的顶点，并且是一个有向树，即有向生成树。
2.(1) 对于下面的函数，问calc(4321)的值是多少，时间复杂度是多少？
int calc(int N) {
if (N < 5) return N * 5 + N;
int a = calc(N / 5);
int b = calc(N % 5);
return a * 10 + b;
}
(2) 对于上述函数，结合数据结构栈，把递归改成递推，写出相关代码加上必要注释。
3.使用两个队列（Queue）来模拟一个栈（Stack）的操作。需要实现以下功能：
push(int x)：将元素x压入栈中。pop()：移除并返回栈顶元素。如果栈为空，返回 -1。top()：返回栈顶元素，但不移除它。如果栈为空，返回 -1。empty()：检查栈是否为空，为空返回true，否则返回false。
请用你熟悉的编程语言实现上述功能。
4.
画出二叉树
(a) 画出一棵先序和中序遍历结果相同的二叉树，该二叉树至少包含五个节点，并写出其先序和中序遍历结果。
(b) 画出一棵中序和后序遍历结果相同的二叉树，该二叉树至少包含五个节点，并写出其中序和后序遍历结果。
分析中序遍历代码
给定以下两段不同的二叉树中序递归遍历的 C 语言代码：
// 代码段1
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void inorderTraversal1(struct TreeNode* root, int* result, int* returnSize) {
if (root) {
inorderTraversal1(root->left, result, returnSize);
result[(*returnSize)++] = root->val;
inorderTraversal1(root->right, result, returnSize);
}
}
// 代码段2
void inorderTraversal2(struct TreeNode* root, int* result, int* returnSize) {
if (root == NULL) return;
if (root->left!= NULL) {
inorderTraversal2(root->left, result, returnSize);
}
result[(*returnSize)++] = root->val;
if (root->right!= NULL) {
inorderTraversal2(root->right, result, returnSize);
}
}分析这两段代码在执行中序遍历操作时的区别，包括时间复杂度、空间复杂度、以及在不同形态二叉树上的执行效率等方面。
编写判断二叉树相似性的函数
使用 C 语言编写一个递归函数来判断两棵二叉树是否相似。两棵二叉树相似的定义是：它们具有相同的结构，但节点的值可以不同。函数的原型如下：
int isSimilar(struct TreeNode* root1, struct TreeNode* root2);函数返回 1 表示两棵树相似，返回 0 表示两棵树不相似。
5.
给定一个有向图的邻接矩阵
(1) 以节点 1 为起始点，按照节点编号顺序优先，写出深度优先搜索（DFS）和广度优先搜索（BFS）序列。
(2) 分别写出使用普里姆（Prim）和克鲁斯卡尔（Kruskal）算法求该有向图最小生成树（如果存在）的过程，按照选边的顺序（例如：(1, 2)），普里姆算法以节点 1 为起始点。若该有向图不存在最小生成树，请说明原因。
(3) 求出贝尔曼 - 福特（Bellman - Ford）算法以节点 1 为起点到其他所有节点的最短路径，并写出最短路径生成树（如果存在）。若存在负权环，请指出并解释其对最短路径计算的影响。
(4) 对比迪杰斯特拉（Dijkstra）算法和贝尔曼 - 福特算法在处理该有向图最短路径问题上的异同点，分析两种算法在时间复杂度和空间复杂度方面的差异，并举例说明在何种情况下只能使用贝尔曼 - 福特算法而不能使用迪杰斯特拉算法。
6.给定长度为 11 的哈希表，哈希函数是。
(1) 若哈希表中都是普通链表，插入元素23, 45, 12, 37, 58, 92, 73, 61, 89, 44, 77，画出哈希表并求平均查找长度。
(2) 若哈希表中都是AVL树，插入上述元素，画出哈希表并求平均查找长度。
7.假设我们把快速排序算法用在一个包含 n 个整数的数组 E，将这 n 个元素排为升序，我们用元素之间的比较次数来衡量时间复杂度，而每一次元素间的比较需要常数时间
（1）假设一个快速排序算法的版本总是选数组里最左边的元素作为基准。对这样一个快速排序算法，找到一个最坏情况的包含 n 个元素的输入数组，用集合 {1, 2, …, n} 中的所有整数的一个排列来表示。对这样的输入，推导这个算法的渐近时间复杂度，用来表示。
（2）作为一个递归算法，快速排序算法一般要对很多小的子数组进行递归调用，从而影响了时间效率。而插入排序算法在小数组上运行效率很高。描述一个修改快速排序算法的方法，利用插入排序算法来解决上述的问题。假设插入排序算法处理的每一个子数组的长度不超过 k 个元素。推导证明这个修改过的快速排序算法的平均时间复杂度是 O (nk + n lg (n/k))。
（3）假设快速排序算法总是从输入数组的第一个、最后一个和中间位置这三个元素中选择中位数作为基准。证明该快速排序算法在最坏情况下完成排序需作不超过次元素间的比较。
四、程序设计题 ，共30分
1.完全数是指一个数等于其所有真因子（即除了自身以外的约数）的和。例如，6 是完全数，因为 6 = 1 + 2 + 3。求 1000 以内的所有完全数，给出完整代码。
样例输出：
6：1 2 3
28：1 2 4 7 14
2.给定一个正整数 n，找出所有小于 n 的质数，给出完整代码。
样例输出（n = 20）：
2 3 5 7 11 13 17 19
3.梅森数是指形如的数，其中 p 是质数。找出所有小于 10000 的梅森数，给出完整代码。
样例输出：
3
7
31
127
4.给定两个整数数组 nums1 和 nums2，数组长度最大是 n，判断 nums1 和 nums2 中相同数字出现的次数是否相等，时间复杂度要求在 O (n)，给出完整代码。如果是则输出 true，不是输出 false。
5.a、b、c、d是0到9的整数，abcd和cadb是两个四位数，把满足abcd+cabd=2024的a、b、c、d全部求出来。
6.首先在第一行输入一个整数。接下来的行，每行输入对整数。对于每一对整数，计算它们的和，再分别求出这个和以及这两个整数各自逆转后相加的和。如果这两个和相等，那么输出这两个整数的和；若不相等，则输出 “NO”。这里所谓的 “逆转”，例如数字，它的逆转结果是。
7.第一行输入n；接着来n行，分别输入a1、a2、……an，都是整数(范围在0到200之间)。输出和等于2025的所有组合。
8.编写函数分别计算字符串中数字、字母和其他字符的个数
9.编写函数实现二维数组对角元素的和
10.给定两个字符串s和t，s和t的长度最大是n，判断s和t的相同字母的数量是否相等，大小写敏感，且时间复杂度要求在O(n)，除了输入输出不能用字符串相关的函数，如果是则输出true，不是输出false，给出完整代码
