数据结构阶段测试2–（试题解析）
选择题
- 将⻓度为n的单链表连接在⻓度为m的单链表之后,其算法的时间复杂度为()
A. O(m)
B. O(1)
C. O(n)
D. O(m+n)
解析思路
链表的尾插操作
???? 答案：A
单链表由于需要找到最后⼀个⾮空节点，所以需要遍历⻓度为m的单链表；
连接的过程只需要修改找到的最后⼀个⾮空节点的next指针，指向⻓度为n的单链表即可，复杂度为O(1)；
所以总体的时间复杂度就是O(m)。
- 下⾯关于⼆叉树的说法正确的是()
A. 满⼆叉树是完全⼆叉树
B. 满⼆叉树中有可能存在度数为1的节点
C. 完全⼆叉树是满⼆叉树
D. 完全⼆叉树中某个节点可以没有左孩⼦，只有右孩⼦
解析思路
树的术语
???? 答案：A
满⼆叉树指的是除了最后⼀层全部是叶⼦结点，其他层没有叶⼦结点；
完全⼆叉树是除了最后⼀层不满，其他层都是满的，并且最后⼀层是靠左的（没有左孩⼦就不会有右孩⼦）
根据定义可知，满⼆叉树⼀定是完全⼆叉树。
详细解释：
⽗结点/双亲结点：若⼀个结点含有⼦结点，则这个结点称为其⼦结点的⽗结点； 如上图：A是B的⽗ 结点
⼦结点/孩⼦结点：⼀个结点含有的⼦树的根结点称为该结点的⼦结点； 如上图：B是A的孩⼦结点
结点的度：⼀个结点有⼏个孩⼦，他的度就是多少；⽐如A的度为6，F的度为2，K的度为0
树的度：⼀棵树中，最⼤的结点的度称为树的度； 如上图：树的度为 6
叶⼦结点/终端结点：度为 0 的结点称为叶结点； 如上图： B、C、H、I… 等结点为叶结点
分⽀结点/⾮终端结点：度不为 0 的结点； 如上图： D、E、F、G… 等结点为分⽀结点
兄弟结点：具有相同⽗结点的结点互称为兄弟结点(亲兄弟)； 如上图： B、C 是兄弟结点
结点的层次：从根开始定义起，根为第 1 层，根的⼦结点为第 2 层，以此类推；
树的⾼度或深度：树中结点的最⼤层次； 如上图：树的⾼度为 4
结点的祖先：从根到该结点所经分⽀上的所有结点；如上图： A 是所有结点的祖先
- 某⼆叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该⼆叉树中的叶⼦结点数为（）
A. 不存在这样的⼆叉树
B. 200
C. 198
D. 199
解析思路
叶子节点个数的计算
???? 答案：B
设Ni表⽰度为i的节点个数，则节点总数 N = N0 + N1 + N2。（0，1，2表示度的个数）
节点个数与节点边的关系： N个节点的树有N-1个边。
边与度的关系：N - 1 = N1 + 2 * N2。
故：N0 + N1 + N2 - 1 = N1 + 2 * N2。
因此，得：N0 = N2 + 1。
根据⼆叉树的基本性质，对任何⼀棵⼆叉树，度为0的结点(即叶⼦结点)总是⽐度为2的结点多⼀个。
题⽬中度为2的结点为199个，则叶⼦结点为199+1=200。
- 在⼀个⻓度为n的顺序表中删除第i个元素，要移动_______个元素。如果要在第i个元素前插⼊⼀个元素，要后移_________个元素。
A. n-i，n-i+1
B. n-i+1，n-i
C. n-i，n-i
D. n-i+1，n-i+1
解析思路
顺序表的删除指定元素和在指定位置插入元素
???? 答案：A
温馨提⽰：题⽬要求删除的是第i个元素，⽽不是下标为i的元素。第i个元素的i是从1开始计算的，⽽下标是从0开始的。
- 删除第i个元素，则需要将第i+1个元素到第n个元素向前搬移，所以要移动：n -(i+1)+1 = n-i
- 要在第i个元素前插⼊⼀个元素，则需要将第i个元素到第n个元素向后搬移，所以要移动：n - i+1
5.排序的⽅法有很多种，（）法是基于选择排序的⼀种⽅法，是完全⼆叉树结构的⼀个重要应⽤。
A. 快速排序
B. 插⼊排序
C. 归并排序
D. 堆排序
解析思路
???? 答案：D
⾸先思考选择排序的思想是：找到最⼤或者最⼩的元素，放在数组的最前或最后；
然后根据完全⼆叉树⽤于排序就是堆了，堆排序也符合选择排序的思想，所以就是堆排序。
- 以下属于链表的优点的是（ ）
A. ⽤数组可⽅便实现
B. 插⼊操作效率⾼
C. 不⽤为节点间的逻辑关系⽽增加额外的存储开销
D. 可以按元素号随机访问
解析思路
???? 答案：B
链表的优点：
-
插⼊的效率⽐较⾼，时间复杂度为O(1)
-
按需申请空间，不涉及到扩容
链表的缺点：
-
不⽀持随机访问
-
存储空间不连续，不同的节点通过指针链接起来的，会增加额外的存储开销。
链表是每个节点维护next指针，来实现逻辑上的顺序，由于物理上并不连续，所以⽆法使⽤索引访问。
由上可知，A，C，D是错误的，链表插⼊是O(1)的时间复杂度，所以插⼊操作效率⾼。
- 已知⼆叉树的前序序列为BCDEFAG，中序序列为DCFAEGB，请问后序序列为()
A. DAFEGCB
B. DAEGFCB
C. DAFGECB
D. DAEFGCB
解析思路
二叉树的前中后序遍历
前序遍历：根节点，左⼦树，右⼦树。
中序遍历：左⼦树，根节点，右⼦树。
后序遍历：左⼦树，右⼦树，根节点。
口诀：前 根左右
中 左根右
后 左右根
答案：C
- 对于双向循环链表，每个结点有两个指针域next和prior，分别指向前驱和后继。在p指针所指向的结点之后插⼊s指针所指结点的操作应为()
A. p->next = s; p->next ->prior = s; s ->prior = p; s->next = P->next;
B. s->prior = p; s->next = p ->next; p ->next = s; p->next ->prior = s;
C. p ->next = s; s ->prior = p; p->next ->prior =s; s ->next = p ->next;
D. s->prior = p; s->next =p->next; p->next ->prior = s; p ->next = s;
解析思路
???? 答案：D
s->prior=p; //把p赋值给s的前驱
s->next=p->next; //把p->next赋值给s的后继
p->next->prior=s; //把s赋值给p->next的前驱
p->next=s; //把s赋值给p 的后继
顺序：先搞定插⼊结点的前驱和后继，再搞定后结点的前驱，最后解决结点的后继。
- 借助于栈输⼊A、B、C、D四个元素（进栈和出栈可以穿插进⾏），则不可能出现的输出是（ ）
A. DCBA
B. ABCD
C. CBAD
D. CABD
解析思路
栈的性质
???? 答案：D
A：A B C D依次⼊栈，再依次出栈，则是A选项的输出。
B：A⼊栈，再出栈；B⼊栈，再出栈；C⼊栈，再出栈；D⼊栈，再出栈；则是B选项的输
出。
C：A B C依次⼊栈，再依次出栈。D再⼊栈，再出栈。则是C选项的输出。
D选项，ABC⼊栈后，C先出栈，下⼀个出栈的元素只能是B，A还在B后⾯，所以CAB这个
出栈顺序有误，D是错的
10.若需在O(nlog n)的时间内完成对数组的排序，且要求排序是稳定的，则可选
择的排序⽅法是（）
A. 快速排序
B. 堆排序
C. 归并排序
D. 直接插⼊排序
解题思路
???? 答案：C
排序稳定指的是相同⼤⼩的元素排序后相对位置和排序前是相同的。
⽐如初始排序序列： 2 1 3 3 5 7 6，排序完成后两个相同元素3的相对位置没有发⽣改变，
则认为该排序算法是稳定的。
快速排序不稳定，时间复杂度也不符合；
堆排序时间复杂度符合，但是不稳定；
归并排序时间复杂度O(nlogn)，稳定，正确；
直接插⼊排序时间复杂度O(n^2)，稳定。
下列算法中不属于稳定排序的是()
A. 插⼊排序
B. 冒泡排序
C. 快速排序
D. 归并排序
解题思路
???? 答案：C
概念题，快速排序不稳定，其余都是稳定的
编程题
左叶子之和
描述
计算给定二叉树的左叶子之和。
树上叶子节点指没有后继节点的节点，左叶子指连向父节点的左侧的叶子节点。
样例 2 解释
叶子节点有 4 ， 5 ，3，左叶子只有 4 ，所以答案返回 4
样例 3 解释
叶子节点有 4 ， 5 ，6，左叶子有 4 ， 6，所以答案返回 10
数据范围：树上节点的数量满足 2≤n≤1000 2≤n≤1000 ，节点上的值满足 ∣val∣≤1000 ∣val∣≤1000
示例1
输入：
{1,2}
返回值：
2
示例2
输入：
{1,2,3,4,5}
返回值：
4
示例3
输入：
{1,2,3,4,5,6}
返回值：
10
代码如下：
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int sumOfLeftLeaves(struct TreeNode* root ) {
// write code here
//如果root为NULL，则直接返回0
if(root==NULL)
{
return 0;
}
int sum=0;
//如果左⼦树根节点不为空，且左⼦树根节点的左右⼦树均为空。则进⾏结果累加
if(root->left&&root->left->left==NULL&&root->left->right==NULL)
sum+=root->left->val;
//递归遍历查找左右⼦树中，满⾜左叶⼦节点性质的节点，并进⾏累加
sum+=sumOfLeftLeaves(root->left)+sumOfLeftLeaves(root->right);
//返回sum结果，递归过程中是向上层交付计算结果
return sum;
}
另一棵树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例 1：
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true
示例 2：
输出：false
提示：
-
root树上的节点数量范围是[1, 2000] -
subRoot树上的节点数量范围是[1, 1000] -104 <= root.val <= 104-104 <= subRoot.val <= 104
解题思路：
???? 1. 判断subroot是否为root的⼦树，需要判断subroot是否和root中的某⼀棵⼦树相同。
- 所以该题⽬划分为2部分：
a. 判断两棵树是否相同，递归遍历两棵树的节点进⾏⽐较判断
b. 递归遍历root中的每⼀棵树和subroot进⾏⽐较，判断两棵树是否相同。
代码如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isSameTree(struct TreeNode*p,struct TreeNode*q)
{
if(p==NULL&&q==NULL)
{
return true;
}
if(p==NULL||q==NULL)
{
return false;
}
if(p->val!=q->val)
{
return false;
}
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
if(root==NULL)
{
return false;
}
if(isSameTree(root,subRoot))
{
return true;
}
return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}
链表的回文结构
描述
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
1->2->2->1
返回：true
解题思路：
???? 此题可以先找到中间节点，然后把后半部分逆置，最近前后两部分⼀⼀⽐对，如果节点的值全部相同，则即为回⽂。
- 先通过快慢指针的⽅式，找到链表中间节点。
ListNode*findMidNode(ListNode*phead)
{
ListNode*slow=phead;
ListNode*fast=phead;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
- 再将后半部分链表进⾏反转。
ListNode*reverseList(ListNode*phead)
{
ListNode*n1,*n2,*n3;
n1=NULL,n2=phead,n3=n2->next;
while(n2)
{
n2->next=n1;
n1=n2;
n2=n3;
if(n3)
n3=n3->next;
}
return n1;
}
- 最后将链表前半部分和反转后的后半部分链表逐节点进⾏⽐较判断。
ListNode*left=A;
while(right)
{
if(left->val!=right->val)
{
return false;
}
left=left->next;
right=right->next;
}
return true;
完整的实现：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
ListNode*findMidNode(ListNode*phead)
{
ListNode*slow=phead;
ListNode*fast=phead;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
ListNode*reverseList(ListNode*phead)
{
ListNode*n1,*n2,*n3;
n1=NULL,n2=phead,n3=n2->next;
while(n2)
{
n2->next=n1;
n1=n2;
n2=n3;
if(n3)
n3=n3->next;
}
return n1;
}
bool chkPalindrome(ListNode* A) {
//1.找中间节点
ListNode*mid=findMidNode(A);
//2.根据中间节点反转后面的链表
ListNode*right=reverseList(mid);
//3.从原链表和反转后的链表比较节点的值
ListNode*left=A;
while(right)
{
if(left->val!=right->val)
{
return false;
}
left=left->next;
right=right->next;
}
return true;
}
};
归并排序的实现
归并排序算法思想：
归并排序（MERGE-SORT）是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法（Divide and Conquer）的⼀个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。 归并排序核⼼步骤：
分解的过程是：二叉树的递归思想
合并的过程是：两个有序数组合并
动态开辟一块临时空间用来存放排序好的数组：
int* tmp = (int*)malloc(sizeof(int) * n);
if(tmp==NULL)
{
perror("malloc fail");
return;
}
free(tmp);
分解的过程：
if (left >= right)
{
return;
}//这里返回到单个元素时，需要向上返回
//计算中间位置的下标
int mid = (left + right) / 2;
//左
_MergeSort(arr, left, mid, tmp);
//右
_MergeSort(arr, mid + 1, right, tmp);
合并的过程：
//合并
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
//定义临时数组tmp下标
int index = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = tmp[begin1++];
}
else
{
tmp[index++] = tmp[begin2++];
}
}
//要么begin1越界，要么begin2越界
while (begin1 <= end1)
{
tmp[index++] = tmp[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = tmp[begin2++];
}
拷贝：
tmp数组类似于中转站
//拷贝
for (int i = left; i <=right; i++)
{
arr[i] = tmp[i];
}
代码实现：
void _MergeSort(int* arr, int left, int right, int* tmp)
{
//分解
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid + 1, right, tmp);
//合并
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else
{
tmp[index++] = arr[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}
//拷贝
for (int i = left; i <= right; i++)
{
arr[i] = tmp[i];
}
}
void MergeSort(int* arr, int n)
{
//动态开辟一块空间，使合并完的数组存放到这个临时数组里面，大小是原数组的大小
int* tmp = (int*)malloc(sizeof(int) * n);
if(tmp==NULL)
{
perror("malloc fail");
return;
}
_MergeSort(arr, 0, n - 1, tmp);
free(tmp);
}