顺序表与链表练习

2024-09-07 14:44
文章标签 链表 练习 顺序 表与

本文主要是介绍顺序表与链表练习,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

1.在长度为n(n > 1)的单链表上,设有头和尾两个引用,执行( )操作与链表的长度有关。

2.下列关于链表的说法那个是正确的( ) 

3. 关于链表和顺序表间的区别,叙述错误的是(    )

 4.在长度为 n 的顺序表下标为 i 的位置前插入一个元素(1 ≤ i ≤ n+1),元素的移动次数为(   )

5.Which statement is true for the class java.util.ArrayList? 

 6.ArrayList和LinkList的描述,下面说法错误的是?

7.杨辉三角

8.链表的中间结点

 9.移除链表元素

 10.反转链表

10.返回倒数第K个节点

1.在长度为n(n > 1)的单链表上,设有头和尾两个引用,执行( )操作与链表的长度有关。

A.在单链表第一个元素前插入一个新元素

B.在单链表最后一个元素后插入一个新元素

C.删除单链表的第一个元素

D.删除单链表中的最后一个元素

答案:D

A错误:头插不需要遍历链表,与链表长度无关

B错误:尾插不需要遍历链表,因为有一个引用指向了尾结点,可以直接插入

C错误:删除第一个节点也不需要遍历链表

D正确:删除最后一个节点之前,先要把倒数第二个节点找到,因为最后一个节点删除之后,需要将倒数第二个节点的next置为null 故需要遍历链表

因此选择D

 

2.下列关于链表的说法那个是正确的( ) 

 A.插入或者删除元素时,无需移动其他元素

B.数据在内存中一定是连续的

C.需要事先估计存储空间

D.可以随时访问表内的元素

答案:A

A正确:链表中节点之间是通过next引用相互指向的,故插入或者删除元素时只需要修改几个引用的指向即可,不需要搬移元素

B错误:链表中的元素在内存中不一定连续,因为new的时候,会从堆上分配空间,具体分配出来的空间是否每次都连续,这个不一定

C错误:链表的空间不连续,插入时也不需要扩容之类的,因此不需要事先预估存储空间大小

D错误:链表不支持随机访问,需要访问任意位置元素时只能通过查找

 

3. 关于链表和顺序表间的区别,叙述错误的是(    )

A.链表和顺序表都属于线性表

B.链表不能随机访问其中的某个元素,顺序表可以

C.链表能做的事,顺序表都可以完成,只是操作方法不同,效率不同

D.链表在进行插入和删除的时候,速度总是比顺序表快

    答案:D

    解析:链表的插入和删除不是所有情况下都比顺序表快,比如尾插尾删,顺序表的时间复杂度为O(1),并且如果是单链表,如果要在中间某个节点的前面插入/删除一个节点,则需要遍历。所以时间的快慢要分情况看待。

 

 4.在长度为 n 的顺序表下标为 i 的位置前插入一个元素(1 ≤ i ≤ n+1),元素的移动次数为(   )

A.n - i + 1

B.n - i

C.i

D.i - 1

   答案:B

   解析:顺序表插入元素,需要移动元素,这里需要把[i, n - 1]区间的元素全部向后移动一次,故移动的次数为n - 1 - i + 1   

 

5.Which statement is true for the class java.util.ArrayList? 

 A.The elements in the ArrayList are ordered.

B.The elements in the ArrayList is guaranteed to be mutable(可变的).

C.The elements in the ArrayList are guaranteed to be unique.

D.The elements in the ArrayList are accessed using a unique key.

答案:B

A错误:ArrayList中的元素不一定有序,ArrayList没有要求里面的元素必须有序,可能有序也可能不有序

B正确:ArrayList中的元素可以通过下标修改

C错误:ArrayList中的元素每一要求必须要唯一,可以唯一也可以重复

D错误:ArrayList中的元素是通过下标访问的,而不是通过key

故正确应该选择B

 

 6.ArrayList和LinkList的描述,下面说法错误的是?

A.ArrayList和LinkedList都实现了List接口

B.ArrayList是可改变大小的数组,而LinkedList是双向链接串列

C.LinkedList不支持高效的随机元素访问

D.在LinkedList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动;而在ArrayList的中间插入或删除一个元素的开销是固定的

答案:D

A正确:ArrayList 和 LinkedList都是实现了List接口

B正确:ArrayList是动态类型顺序表,插入时当空间不足时会自动扩容

C正确:LinkedList底层是链表结构,链表不支持随机访问,如果要访问任意元素只能通过查找处理

D错误:LinkedList中插入或者删除元素,只需要修改几个引用的指向即可,不需要搬移愿意,时间复杂度O(1)。ArrayList任意位置插入和删除时才需要搬移,时间复杂度O(N)

 

7.杨辉三角

 代码:

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> list = new ArrayList<>();List<Integer> one = new ArrayList<>();one.add(1);list.add(one);for (int i = 1; i < numRows; i++) {List<Integer> cur = new ArrayList<>();cur.add(1);List<Integer> pre = list.get(i - 1);for(int j = 1; j < i ; j++){int ret = pre.get( j - 1) + pre.get(j);cur.add(ret);}cur.add(1);list.add(cur);}return list;}
}

解析: 

 

8.链表的中间结点

 

 

/*解题思路:快慢引用fast一次走两步,slow一次走一步,当fast走到末尾的时候,slow刚好是中间节点注意:while循环条件
*/
class Solution {public ListNode middleNode(ListNode head) {ListNode fast = head;ListNode slow = head;// 注意while循环条件// null != fast成立:可以保证第一步成功// null != fast.next成立:可以保证第二步走成功while(null != fast && null != fast.next){fast = fast.next.next;slow = slow.next;}return slow;}
}

 9.移除链表元素

/*解题思路:遍历链表依次获取每一个节点,如果该节点中的值域与val相等,则删除在删除时候一定要分情况:删除的节点为第一个节点 和 不是第一个节点,两种方式删除是不一样的
*/ 
class Solution {public ListNode removeElements(ListNode head, int val) {if(head == null ){return head;}ListNode cur = head.next;ListNode pre = head;while(cur != null){if(cur.val == val){pre.next = cur.next ;cur = cur.next;}else{pre = cur;cur = cur.next;} }if(head.val == val){head = head.next;}return head;
}

 10.反转链表

class Solution {public ListNode reverseList(ListNode head) {if(head == null){return head;}ListNode cur =  head.next;head.next = null;while(cur != null){ListNode  curN = cur.next;//进行头插法 把首的next当尾置为空 接着把cur结点进行头插cur.next = head;head = cur;cur = curN;}return head;}
}

10.返回倒数第K个节点

class Solution {public int kthToLast(ListNode head, int k) {if(head == null) return  -1;ListNode fast = head;ListNode slow = head;int count = 0;while(count != k - 1){fast = fast.next;count++;}while(fast.next != null){fast = fast.next;slow = slow.next;}return slow.val;}
}

 

 

这篇关于顺序表与链表练习的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1145347

相关文章

Linux链表操作方式

《Linux链表操作方式》:本文主要介绍Linux链表操作方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、链表基础概念与内核链表优势二、内核链表结构与宏解析三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势六、典型应用场景七、调试技巧与

Java中JSON格式反序列化为Map且保证存取顺序一致的问题

《Java中JSON格式反序列化为Map且保证存取顺序一致的问题》:本文主要介绍Java中JSON格式反序列化为Map且保证存取顺序一致的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未... 目录背景问题解决方法总结背景做项目涉及两个微服务之间传数据时,需要提供方将Map类型的数据序列化为co

MySQL中SQL的执行顺序详解

《MySQL中SQL的执行顺序详解》:本文主要介绍MySQL中SQL的执行顺序,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql中SQL的执行顺序SQL执行顺序MySQL的执行顺序SELECT语句定义SELECT语句执行顺序总结MySQL中SQL的执行顺序

SpringBoot中配置文件的加载顺序解读

《SpringBoot中配置文件的加载顺序解读》:本文主要介绍SpringBoot中配置文件的加载顺序,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot配置文件的加载顺序1、命令⾏参数2、Java系统属性3、操作系统环境变量5、项目【外部】的ap

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》:本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句(1)条件语句的定义(2)条件语句的语法(a)单分支 if(b)双分支 if-else(

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明

C++实现封装的顺序表的操作与实践

《C++实现封装的顺序表的操作与实践》在程序设计中,顺序表是一种常见的线性数据结构,通常用于存储具有固定顺序的元素,与链表不同,顺序表中的元素是连续存储的,因此访问速度较快,但插入和删除操作的效率可能... 目录一、顺序表的基本概念二、顺序表类的设计1. 顺序表类的成员变量2. 构造函数和析构函数三、顺序表

JAVA利用顺序表实现“杨辉三角”的思路及代码示例

《JAVA利用顺序表实现“杨辉三角”的思路及代码示例》杨辉三角形是中国古代数学的杰出研究成果之一,是我国北宋数学家贾宪于1050年首先发现并使用的,:本文主要介绍JAVA利用顺序表实现杨辉三角的思... 目录一:“杨辉三角”题目链接二:题解代码:三:题解思路:总结一:“杨辉三角”题目链接题目链接:点击这里