数据结构阶段测试2--(试题解析)

时间:2024-10-06 20:29:18

数据结构阶段测试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,则直接返回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;
}

另一棵树的子树

给你两棵二叉树 rootsubRoot 。检验 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);
}