链表oj题 && 链表与LinkedList && 栈的概念 && 队列的概念 && 树和二叉树

第 1 题（编程题）

题目名称：

求环的入口点

题目内容：

求环的入口点https://leetcode-cn.com/problems/linked-list-cycle-ii/description/

第 2 题（编程题）

题目名称：

判断链表带环

题目内容：

判断链表带环https://leetcode-cn.com/problems/linked-list-cycle/description/

第 3 题（编程题）

题目名称：

判定链表相交

题目内容：

判定链表相交并求出交点https://leetcode-cn.com/problems/intersection-of-two-linked-lists/description/

第 4 题（编程题）

题目名称：

判定链表是否是回文

题目内容：

判定链表是否是回文https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

第 5 题（编程题）

题目名称：

给定 x, 把一个链表整理成前半部分小于 x, 后半部分大于等于 x 的形式

题目内容：

给定 x, 把一个链表整理成前半部分小于 x, 后半部分大于等于 x 的形式https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

 

第 1 题（单选题）

题目名称：

8. 在一个循环双向链表中，要在p所指的节点之前插入s所指节点，以下代码正确的执行次序是（   ）

   ① p.prev.next=s;

   ② p.prev=s;

   ③ s.prev=p.prev;

   ④ s.next=p;

题目内容：

A .④③①②

B .④③②①

C .②①④③

D .②①③④

第 2 题（单选题）

题目名称：

7. 下列判断带头结点双向循环链表为空的语句中，正确的是（   ）

题目内容：

A .head == null;

B .head.next == null;

C .head.next == head;

D .head != null;

第 3 题（编程题）

题目名称：

模拟实现 LinkedList 类

题目内容：

 // 2、无头双向链表实现
 public class LinkedList {
     //头插法
     public void addFirst(int data);
     //尾插法
     public void addLast(int data);
     //任意位置插入,第一个数据节点为0号下标
     public boolean addIndex(int index,int data);
     //查找是否包含关键字key是否在单链表当中
     public boolean contains(int key);
     //删除第一次出现关键字为key的节点
     public void remove(int key);
     //删除所有值为key的节点
     public void removeAllKey(int key);
     //得到单链表的长度
     public int size();
     public void display();
     public void clear();
 }

第 1 题（单选题）

题目名称：

1.下列关于栈的叙述正确的是（ ）

题目内容：

A .栈是一种“先进先出”的数据结构

B .栈可以使用链表或顺序表来实现

C .栈只能在栈底插入数据

D .栈不能删除数据

第 2 题（单选题）

题目名称：

2.一个栈的入栈序列为ABCDE，则不可能的出栈序列为（ ）

题目内容：

A .ABCDE

B .EDCBA

C .DCEBA

D .ECDBA

第 3 题（单选题）

题目名称：

3.链栈与顺序栈相比，比较明显的优点是（ ）

题目内容：

A .插入操作更加方便

B .删除操作更加方便

C .入栈时不需要扩容

第 4 题（单选题）

题目名称：

4.下列关于栈的叙述中，正确的是（）

题目内容：

A .栈底元素一定是最后入栈的元素

B .栈顶元素一定是最先入栈的元素

C .栈操作遵循先进后出的原则

D .以上说法均错误

第 5 题（单选题）

题目名称：

5.借助于栈输入A、B、C、D四个元素（进栈和出栈可以穿插进行），则不可能出现的输出是

题目内容：

A .DCBA

B .ABCD

C .CBAD

D .CABD

第 6 题（编程题）

题目名称：

最小栈

题目内容：

最小栈

第 7 题（编程题）

题目名称：

1.括号匹配问题

题目内容：

1.括号匹配问题。OJ链接

第 8 题（编程题）

题目名称：

3.栈的弹出压入序列

题目内容：

栈的弹出压入序列(仅上传代码即可)。OJ链接

第 9 题（编程题）

题目名称：

4.逆波兰表达式求值

题目内容：

逆波兰表达式求值(仅上传代码即可)。OJ链接

第 1 题（单选题）

题目名称：

7.以下不是队列的基本运算的是（ ）

题目内容：

A .从队尾插入一个新元素

B .从队列中删除队尾元素

C .判断一个队列是否为空

D .读取队头元素的值

第 2 题（多选题）

题目名称：

8.下面关于栈和队列的说法中错误的是（ ）

题目内容：

A .队列和栈通常都使用链表实现

B .队列和栈都只能从两端插入、删除数据

C .队列和栈都不支持随机访问和随机插入

D .队列是“先入先出”，栈是“先入后出”

第 3 题（单选题）

题目名称：

9.下列关于顺序结构实现循环队列的说法，正确的是（ ）

题目内容：

A .循环队列的长度通常都不固定

B .直接用队头和队尾在同一个位置可以判断循环队列是否为满

C .通过设置计数的方式可以判断队列空或者满

D .循环队列是一种非线性数据结构

第 4 题（单选题）

题目名称：

10.现有一循环队列，其队头为front，队尾为rear，循环队列长度为N,最多存储N-1个数据。其队内有效长度为（ ）

题目内容：

A .(rear - front + N) % N + 1

B .(rear - front + N) % N

C .(rear - front) % (N + 1)

D .(rear - front + N) % (N - 1)

第 5 题（单选题）

题目名称：

1.对于循环队列，下列叙述中正确的是

题目内容：

A .队头是固定不变的

B .队头一定大于队尾

C .队头一定小于队尾

D .队头可以大于队尾，也可以小于队尾

第 6 题（单选题）

题目名称：

2.下述有关栈和队列的区别，说法错误的是？

题目内容：

A .栈是限定只能在表的一端进行插入和删除操作。

B .队列是限定只能在表的一端进行插入和在另一端进行删除操作。

C .栈和队列都属于线性表

D .栈的插入操作时间复杂度都是o(1)，队列的插入操作时间复杂度是o(n)

第 7 题（单选题）

题目名称：

4.下列关于用栈实现队列的说法中错误的是（ ）

题目内容：

A .用栈模拟实现队列可以使用两个栈，一个栈模拟入队列，一个栈模拟出队列

B .每次出队列时，都需要将一个栈中的全部元素导入到另一个栈中，然后出栈即可

C .入队列时，将元素直接往模拟入队列的栈中存放即可

D .入队列操作时间复杂度为O(1)

第 8 题（单选题）

题目名称：

下列关于队列的叙述错误的是( )

题目内容：

A .队列可以使用链表实现

B .队列是一种"先入先出"的数据结构

C .数据出队列时一定只影响队尾引用

D .数据入队列时一定从尾部插入

第 9 题（编程题）

题目名称：

用队列实现栈

题目内容：

用队列实现栈

第 10 题（编程题）

题目名称：

用栈实现队列

题目内容：

用栈实现队列

第 11 题（编程题）

题目名称：

设计循环队列

题目内容：

设计循环队列

第 12 题（单选题）

题目名称：

用无头单链表存储队列，front引用队头，back引用队尾，则在进行出队列操作时( )

题目内容：

A .仅修改front

B .front 和 back 都要修改

C .front 和 back 可能都要修改

D .仅修改back

第 1 题（单选题）

题目名称：

2.将一颗有 100 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根节点编号为 1 ，则编号为 98 的节点的父节点编号为

题目内容：

A .47

B .48

C .49

D .50

第 2 题（单选题）

题目名称：

3.设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是

题目内容：

A .中序序列

B .前序序列

C .后序序列

D .前序序列或后序序列

第 3 题（单选题）

题目名称：

17.对任意一颗二叉树，设N0、N1、N2分别是度为0、1、2的结点数，则下列式子中一定正确的是（ ）

题目内容：

A .N0 = N2 + 1

B .N1 = N0 + 1

C .N2 = N0 + 1

D .N2 = N1 + 1

第 4 题（单选题）

题目名称：

19.二叉树的( )遍历相当于广度优先遍历，( )遍历相当于深度优先遍历

题目内容：

A .前序 中序

B .中序 前序

C .层序 后序

D .层序 前序

第 5 题（单选题）

题目名称：

20.如果一颗二叉树的前序遍历的结果是ABCD，则满足条件的不同的二叉树有（ ）种

题目内容：

A .13

B .14

C .15

D .16

第 6 题（单选题）

题目名称：

10.有n个元素的完全二叉树的深度是（   ）

题目内容：

A .nlogn

B .nlogn+1

C .logn

D .logn+1

第 7 题（单选题）

题目名称：

1.n个节点的完全二叉树，最多可以有多少层？

题目内容：

A .n/2

B .log(n)+1(向下取整)

C .n-1

D .n

第 8 题（单选题）

题目名称：

4.将一棵二叉树的根结点放入队列，然后递归的执行如下操作，将出队结点所有子结点先左后右式的加入队。以上操作可以实现哪种遍历？

题目内容：

A .前序遍历

B .中序遍历

C .后序遍历

D .层序遍历