链表练习

判断题

1、数据的逻辑结构是指数据的各数据项之间的逻辑关系。  F

数据的逻辑结构是指数据的各数据元素之间的逻辑关系。

2、顺序表中逻辑上相邻的元素,其物理位置也一定相邻。  T

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素,这种表示也称作线性表的顺序存储结构或顺序映像。通常,称这种存储结构的线性表为顺序表。

其特点是,逻辑上相邻的元素,其物理位置也是相邻的。

3、顺序表是一种随机存取的存储结构。  T

随机存取通俗点说就是,想存取哪个位置就能存取哪个位置,而且不需要访问其之前的数据,换种说法就是直接存取。而顺序表是逻辑上相邻,物理位置上连续的,因此,只需要知道顺序表的起始位置,就能对它任意位置进行存取。

4、链表中逻辑上相邻的元素,其物理位置也一定相邻。  F

线性表链式存储结构的特点是:用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。

5、顺序存储设计时,存储单元的地址一定连续。  T

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素,这种表示也称作线性表的顺序存储结构或顺序映像。通常,称这种存储结构的线性表为顺序表。

其特点是,逻辑上相邻的元素,其物理位置也是相邻的。

6、在N个结点的顺序表中访问第i(1<=i<=N)个结点和求第i(2<=i<=N)个结点直接前驱的算法时间复杂度均为O(1)。  T

顺序表可以对结点直接存取,不需要访问其之前的结点,所以与顺序表的长度N无关,因此算法时间复杂度为O(1)。

7、线性表采用链式存储结构时,各个数据元素的存储单元地址一定是不连续的。  F

链式存储用的是任意的存储单元,可以连续,也可以不连续,所以不一定。

8、线性表L如果需要频繁地进行不同下标元素的插入、删除操作,此时选择顺序存储结构更好。  F

顺序表每次插入和删除的算法时间复杂度是O(N),因为在每次插入或删除时,需要让后边的所有结点移动,而链式存储的算法时间复杂度是O(1),只需要两次首尾链接或者一次首位链接。

9、非空线性表可以有多个开始结点。  F

10、非空线性表中每个结点都有一个前驱结点。  F

11、非空线性表除终端结点外,每个结点都有唯一的后继结点。  T

12、非空线性表中每个结点都有一个后继结点。  F

对于非空的线性表或线性结构,其特点是:

1)存在唯一的一个被称作“第一个”的数据元素。(其实就是只有一个开始结点)

2)存在唯一的一个被称作“最后一个”的数据元素。

3)除第一个元素之外,结构中的每个数据元素均只有一个前驱。

4)除最后一个元素之外,结构中的每个数据元素均只有一个后继。

前驱,后继,即为跟它相连的前边的一个或者后边的一个。

13、对于顺序存储的长度为N的线性表,访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。  T

14、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用顺序表存储最节省时间。  T

链式表需要从头开始访问到指定位置或者最后来进行插入和删除,而顺序表不用。

15、对于顺序存储的长度为N的线性表,删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)和O(N)。  F

删除第一个是O(N),插入最后一个是O(1).

16、在线性表的顺序存储结构中,插入和删除元素时,移动元素的个数与该元素的位置有关。  T

17、顺序存储方式只能用于存储线性结构。  F

顺序存储方式不仅能用于存储线性结构,还可以用来存放非线性结构,例如完全二叉树是属于非线性结构,但其最佳存储方式是顺序存储方式。

数据的逻辑结构包括线性结构、树、图、集合这四种,在线性结构里面又有线性表、栈、队列等等。而数据的存储结构只有两种:顺序存储结构和链式存储结构,这两种存储结构,前面一个是利用数据元素在存储器中的相对位置表示其逻辑结构,另外一个是用指针来表示其逻辑关系。

18、顺序存储的线性表可以随机存取。  T

19、顺序存储结构的主要缺点是不利于插入或删除操作。  T

20、在顺序表中逻辑上相邻的元素,其对应的物理位置也是相邻的。  T

21、将长度分别为m,n的两个单链表合并为一个单链表的时间复杂度为O(m+n)。F

O(m)

22.将N个数据按照从小到大顺序组织存放在一个单向链表中。如果采用二分查找,那么查找的平均时间复杂度是 O(logN) F

二分查找的平均复杂度是O(logN)没有错,按顺序存放在单项链表中,二分查找是不可以用链表存储的。

 23.在单链表中,要访问某个结点,只要知道该结点的指针即可。因此,单链表是一种随机存取结构.。  F

线性表分(顺序存储和链式存储):
顺序存储即数组,我们使用数组的时候申请的是连续的内存空间可以直接读取的,a[24],a[25]
链式存储即链表,链表中单个节点的内存地址不是连续的,而是散列在计算机中,通过next指针访问下一个节点,所以所必须遍历链表才能读取数据!

python

评论列表

暂无评论
您尚未登录,登录之后方可评论~ 登录 or 注册