数据结构阶段测试2--（试题解析）

news/2024/12/21 21:08:45/

数据结构阶段测试2–（试题解析）

在这里插入图片描述

选择题

  1. 将⻓度为n的单链表连接在⻓度为m的单链表之后,其算法的时间复杂度为()

A. O(m)

B. O(1)

C. O(n)

D. O(m+n)

解析思路

链表的尾插操作

💡 答案：A

单链表由于需要找到最后⼀个⾮空节点，所以需要遍历⻓度为m的单链表；

连接的过程只需要修改找到的最后⼀个⾮空节点的next指针，指向⻓度为n的单链表即可，复杂度为O(1)；

所以总体的时间复杂度就是O(m)。

  1. 下⾯关于⼆叉树的说法正确的是()

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 是所有结点的祖先

  1. 某⼆叉树共有 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。

  1. 在⼀个⻓度为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开始的。

  1. 删除第i个元素，则需要将第i+1个元素到第n个元素向前搬移，所以要移动：n -(i+1)+1 = n-i
  2. 要在第i个元素前插⼊⼀个元素，则需要将第i个元素到第n个元素向后搬移，所以要移动：n - i+1

5.排序的⽅法有很多种，（）法是基于选择排序的⼀种⽅法，是完全⼆叉树结构的⼀个重要应⽤。

A. 快速排序

B. 插⼊排序

C. 归并排序

D. 堆排序

解析思路

💡 答案：D

⾸先思考选择排序的思想是：找到最⼤或者最⼩的元素，放在数组的最前或最后；

然后根据完全⼆叉树⽤于排序就是堆了，堆排序也符合选择排序的思想，所以就是堆排序。

在这里插入图片描述

  1. 以下属于链表的优点的是（ ）

A. ⽤数组可⽅便实现

B. 插⼊操作效率⾼

C. 不⽤为节点间的逻辑关系⽽增加额外的存储开销

D. 可以按元素号随机访问

解析思路

💡 答案：B

链表的优点：

  1. 插⼊的效率⽐较⾼，时间复杂度为O(1)

  2. 按需申请空间，不涉及到扩容

链表的缺点：

  1. 不⽀持随机访问

  2. 存储空间不连续，不同的节点通过指针链接起来的，会增加额外的存储开销。

链表是每个节点维护next指针，来实现逻辑上的顺序，由于物理上并不连续，所以⽆法使⽤索引访问。

由上可知，A，C，D是错误的，链表插⼊是O(1)的时间复杂度，所以插⼊操作效率⾼。

  1. 已知⼆叉树的前序序列为BCDEFAG，中序序列为DCFAEGB，请问后序序列为()

A. DAFEGCB

B. DAEGFCB

C. DAFGECB

D. DAEFGCB

解析思路

二叉树的前中后序遍历

前序遍历：根节点，左⼦树，右⼦树。

中序遍历：左⼦树，根节点，右⼦树。

后序遍历：左⼦树，右⼦树，根节点。

口诀：前 根左右

​ 中 左根右

​ 后 左右根

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

答案：C
在这里插入图片描述

  1. 对于双向循环链表，每个结点有两个指针域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 的后继

顺序：先搞定插⼊结点的前驱和后继，再搞定后结点的前驱，最后解决结点的后继。

  1. 借助于栈输⼊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，则直接返回0if(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中的某⼀棵⼦树相同。

  1. 所以该题⽬划分为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

解题思路：

💡 此题可以先找到中间节点，然后把后半部分逆置，最近前后两部分⼀⼀⽐对，如果节点的值全部相同，则即为回⽂。

  1. 先通过快慢指针的⽅式，找到链表中间节点。
ListNode*findMidNode(ListNode*phead){ListNode*slow=phead;ListNode*fast=phead;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}return slow;}
  1. 再将后半部分链表进⾏反转。
 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;}
  1. 最后将链表前半部分和反转后的后半部分链表逐节点进⾏⽐较判断。
 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);
}

http://www.ppmy.cn/news/1534844.html

相关文章

WebGL在低配置电脑的应用

WebGL在低配置电脑的应用

在低配置电脑上实现WebGL渲染&#xff0c;需要采取一系列优化策略来减轻硬件负担&#xff0c;提升渲染性能。以下是一些详细的实现方法&#xff1a; 1. 优化WebGL代码和设置 a. 减少绘制调用次数 通过合并绘制操作、使用批量绘制等方式&#xff0c;尽量减少绘制调用次数。这可以…
阅读更多...
c#中的功能优势

c#中的功能优势

装箱和拆箱 性能消耗的直接体现 int iterations 10000000; // 进行一千万次迭代Stopwatch stopwatch new Stopwatch();// 非装箱测试stopwatch.Start();for (int i 0; i < iterations; i){int x i; // 纯值类型操作&#xff0c;无装箱}stopwatch.Stop();Console.Writ…
阅读更多...
Chromium 硬件加速开关c++

Chromium 硬件加速开关c++

选项页控制硬件加速开关 1、前端代码 <settings-toggle-button id"hardwareAcceleration"pref"{{prefs.hardware_acceleration_mode.enabled}}"label"$i18n{hardwareAccelerationLabel}"><template is"dom-if" if"[…
阅读更多...
BugReport中的App Processor wakeup字段意义

BugReport中的App Processor wakeup字段意义

一、功耗字段意义&#xff1a; App processor wakeup:Netd基于xt_idletimer 待机下监视网络设备的收发工作状态&#xff0c;即当设备发生联网从休眠态变成为唤醒态时&#xff0c;会记录打醒者的uid(uid大于0)和网络类型(wifi或数据类型)、时间戳 实际日志&#xff1a;我们在B…
阅读更多...
基于MATLAB的安全帽检测系统

基于MATLAB的安全帽检测系统

课题名称 课题介绍 众所周知&#xff0c;在一些施工工地&#xff0c;必须明确佩戴安全帽。可以对生命安全起到保障作用。该课题为常见的安全帽的识别&#xff0c;主要分为红色&#xff0c;蓝色&#xff0c;黄色三类安全帽。而安全帽的主要是红色&#xff0c;蓝色&…
阅读更多...
UFS 3.1架构简介

UFS 3.1架构简介

整个UFS协议栈可以分为三层：应用层(UFS Application Layer(UAP))，传输层(UFS Transport Layer(UTP))，链路层(UIC InterConnect Layer(UIC))。应用层发出SCSI命令(UFS没有自己的命令使用的是简化的SCSI命令)，在传输层将SCSI分装为UPIU，再经过链路层将命令发送给Devices。下…
阅读更多...
高通芯片手机查看空口消息工具：QCAT

高通芯片手机查看空口消息工具：QCAT

关于QCAT的作用&#xff0c;之前一直理解的不够&#xff0c;最近查看了GSM网络协议&#xff0c;有进一步理解&#xff0c;记录如下&#xff1a;结论&#xff1a;QCAT是查看空口消息的工具。 一&#xff1a;背景知识。 1. 在GSM 网络协议中&#xff0c;手机设备(MS:mobile stati…
阅读更多...
做数据抓取工作要如何选择ip池

做数据抓取工作要如何选择ip池

选择合适的IP池对于数据抓取工作至关重要。一个优质的IP池可以提高抓取的效率和成功率&#xff0c;同时减少被目标网站封禁的风险。以下是选择IP池时需要考虑的一些关键因素&#xff1a; 1. IP类型 住宅IP&#xff1a;住宅IP通常来自真实用户&#xff0c;难以被识别为代理。它…
阅读更多...
最新文章

Copyright @ 2022~2023