0


《每日一套题·提升你我能力》· 第五篇

在这里插入图片描述

大家好,我是安然无虞。

文章目录

每篇前言


博客主页:安然无虞

作者认证:2021年博客新星Top2

咱的口号:🌹小比特,大梦想🌹

作者请求:由于博主水平有限,难免会有错误和不准之处,我也非常渴望知道这些错误,恳请铁汁批评斧正。

火爆专栏:蓝桥杯基础算法剖析
欢迎加入:比特社区
在这里插入图片描述

种一棵树最好的时间是十年前,其次是现在。

各位,共勉。


一、选择填空题

知识点补充

I.满二叉树和完全二叉树:

  • 一个二叉树, 如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说, 如果一个二叉树的层数为K,且结点总数是(2^k) -1 ,则它就是满二叉树;

在这里插入图片描述

  • 对于深度为K且有 n 个结点的二叉树, 当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树 。 要注意的是满二叉树是一种特殊的完全二叉树。(可能这样叙述并不是很清楚,没关系,请看下面)

在这里插入图片描述看过来:在这里插入图片描述
II.二叉树性质:

  • 若规定根节点的层数是1,则一颗非空二叉树的第i层最多有2^(i-1) 个节点;
  • 如规定根节点的层数是1,则深度为h的二叉树的最大节点数是2^h - 1,对,属于满二叉树;
  • 对于任何一棵二叉树来说,如果度为0的叶节点个数是N0,度为2的节点个数是N2,那么总有N0 = N2 + 1;
  • 若规定根节点的层数是1,具有n个节点的满二叉树的深度是h = log(N+1)。

1.题目一:考察性质

1.某二叉树共有399个节点,其中199个是度为2的节点,则该二叉树的叶子节点是:___ 个

本题主要考查性质三,X0 = X2 + 1,所以X0 = 200,即叶子结点个数为200个,这道题目知道性质3就很简单了。


2.题目二:考察性质

2.在具有2n 个节点的完全二叉树中,叶子结点个数为:___ 个。
在这里插入图片描述
需要注意的是,对于完全二叉树来说,度为1的结点个数只可能有0个或者1个。


3.题目三:考察性质

一颗完全二叉树的节点个数为531个,那么这棵树的高度为()
A:11
B:10
C:8
D:12

方法1

在这里插入图片描述

方法2

在这里插入图片描述代入之后很明显,答案选择B


4.题目四:考察性质

一个具有767个节点的完全二叉树,其叶子结点个数为()
A:383
B:384
C:385
D:386
在这里插入图片描述这道题跟第二题很相似,所以能看出什么,性质很重要,需要记住哦。

在这里插入图片描述

二、编程设计题

面试题:反转链表

原题链接:反转链表
题目描述:
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例:
在这里插入图片描述

解题思路1:翻指针方向

不过直接翻指针方向这个方法定义两个指针是翻不动的,需要定义三个指针,可能看下图很难理解,但是要结合代码去理解,最好自己能画一遍,尝试自己写一遍代码。在这里插入图片描述初始代码:

struct ListNode*reverseList(struct ListNode* head){//判断特殊情况if(head ==NULL)returnNULL;struct ListNode* n1 =NULL,*n2 = head,*n3 = n2->next;while(n2){
       n2->next = n1;
       n1 = n2;
       n2 = n3;//注意哦,当n3指向空指针时再执行n3 = n3->next;会导致空指针异常if(n3)
           n3 = n3->next;}return n1;}

完整代码:在这里插入图片描述
优化后的代码:

struct ListNode*reverseList(struct ListNode* head){struct ListNode* n1 =NULL,*n2 = head;while(n2){struct ListNode* n3 = n2->next;
       n2->next = n1;
       n1 = n2;
       n2 = n3;}return n1;}

是不是变得很简单,这样写也无需判断特殊情况。
完整代码:
在这里插入图片描述

解题思路2:头插法

在这里插入图片描述之所以需要多定义一个指针,是因为要保证能找到下一个。
代码执行:

struct ListNode*reverseList(struct ListNode* head){struct ListNode* newHead =NULL;struct ListNode* cur = head;while(cur){//之所以将next定义在循环里是为了防止head为空时造成野指针struct ListNode* next = cur->next;
       cur->next = newHead;
       newHead = cur;
       cur = next;}return newHead;}

完整代码:
在这里插入图片描述

在这里插入图片描述

面试题:链表的中间节点

原题链接:链表的中间节点
题目描述:
给定一个头结点为 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。
示例:
在这里插入图片描述

解题思路

本题比较简单,直接利用快慢指针即可但是有两点需要注意,会在下面给出
代码执行:

struct ListNode*middleNode(struct ListNode* head){struct ListNode* slow = head,*fast = head;//注意循环条件:想的是结束条件,写的是继续条件while(fast && fast->next){
       slow = slow->next;
       fast = fast->next->next;}return slow;}

完整代码:
在这里插入图片描述试想:为什么循环条件不能写成fast->next && fast?
因为如果节点个数是偶数个,那么fast会走到最后一个节点的next位置,也就是NULL,此时再判断循环条件fast->next时会导致野指针。(可能这样叙述不好理解哦,没关系,动手画画图就很容易理解啦。)

在这里插入图片描述

面试题:回文链表

原题链接:回文链表
题目描述:
对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。
示例:
1->2->2->1
返回:true

解题思路

之所以讲解前面两题,实际上都是为这道题准备的,本题的解题步骤是:

  • 找出链表的中间位置;
  • 逆置后半段
  • 最后从头依次比较即可

在这里插入图片描述代码执行:

//回文链表
class PalindromeList {
public://判断中间结点struct ListNode*middleNode(struct ListNode* A){struct ListNode* slow = A,*fast = A;while(fast && fast->next){
           slow = slow->next;
           fast = fast->next->next;}return slow;}//反转后半部分struct ListNode*reverseAfter(struct ListNode* mid){struct ListNode* newHead =NULL,*cur = mid;while(cur){struct ListNode* next = cur->next;
           cur->next = newHead;
           newHead = cur;
           cur = next;}return newHead;}
   bool chkPalindrome(ListNode* A){// write code here//先判断中间结点struct ListNode* mid =middleNode(A);//再反转后半部分struct ListNode* rHead =reverseAfter(mid);while(A && rHead){if(A->val != rHead->val){return false;}else{
               A = A->next;
               rHead = rHead->next;}}return true;}};

完整代码:
在这里插入图片描述

三、遇见安然遇见你,不负代码不负卿。

码字不易,求个三连

抱拳了兄弟们。

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


本文转载自: https://blog.csdn.net/weixin_57544072/article/details/123908553
版权归原作者 安然无虞 所有, 如有侵权,请联系我们删除。

“《每日一套题·提升你我能力》· 第五篇”的评论:

还没有评论