牛客刷题笔记--(链表专项练习)

采用二分查找的数据只适合采用顺序存储结构，不适用于链式存储结构。 折半查找（二分查找）的要求 1必须采用顺序存储结构 2必须按关键字大小有序排列 头指针是链表的必要元素，不管链表是否为空，头指针都不为空

链表所需空间与线性长度成正比 一个非空广义表的表头可以是原子或子表，表尾一定是子表 删除节点时，首先要更新p结点前后结点的指针域，然后再删除P. 二维数组是其数组元素为线性表的线性表 线性结构：没有分叉的，只有唯一一条路径走到底

插入节点 存储地址是否连续 广义表 广义表的Head运算和Tail运算

1 判断一个单向链表中是否存在环的最佳方法是（快慢指针）

让快慢指针都从链表表头开始，快指针一次向前移动连个位置，慢指针每次向前移动一个位置。如果快指针到达了NULL，说明不存在环，但如果快指针追上了慢指针，说明存在环。

线性链表，它在内存的存储不一定是连续的，因为它只需要指针指向下一节点就可以形成一个链表。 而且存储的顺序也是任意的，因为在内存中，不是连续存储的，线性链表只是逻辑上的连续。

2 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用（D）存储方式最节省运算时间。

设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next和rear,查找时间都是O(1)。 若用头指针来表示该链表，则查找终端结点的时间为O(n)。

3 在双向链表中指针p的结点前插入一个指针q的结点操作是 q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q; 关键在先插入再断开

4 静态链表中指针表示的是（B）

静态链表是用数组实现链表 指向的不是下一元素的地址，下一元素的地址这里指的应该是物理地址。静态链表指针指向的是是下一元素的相对地址，也就是数组下标。

5 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 。B

需要分配较大的空间，故A,C排除，因为它们是动态结构，不需要提前分配空间，插入和删除不需要移动元素，而线性结构的插入，删除若是在中间，最极端的是在左边，需要移动右边的全部数据，而静态链表的插入，删除只需要改游标，添加元素方可实现

6已知广义表（a,b,c）,（d,e,f），从A中取出原子e的运算是（D）

首先这个广义表A有两个子表，每个子表有三个原子。 head（A）：=（a,b,c）是A的头部，是个子表，去掉头部的全是尾部tail（A）：=（d,e,f）。 head(tail(A)):=head((d,e,f))=d，是个原子，剩下的是尾部tail(tail(A)):=(e,f) 再继续取头部就得到了原子e

7 将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为(C ).

选C。考察的是合并两个单链表的时间复杂度。 根据题目的描述属于“尾插法”。

由于将长度为n的单链表链接在长度为m的单链表之后的操作，需要把长度为m的单链表遍历一遍，找到最后一个节点，所以时间复杂度为O(m)。

8广义表即我们通常所说的列表（lists)。它放松了对表元素的原子性限制，允许他们有自身结构。那么广义表E((a,(a,b),((a,b),c)))的长度和深度分别为：B

广义表长度=属于最外层括号的逗号数加一。本题逗号为0 所以长度为1

广义表深度=删除几层括号后可成为一个序列。 广义表的长度指的是广义表中所包含的数据元素的个数 例如，在广义表 {a,{b,c,d}} 中，它包含一个原子和一个子表，因此该广义表的长度为 2。 再比如，广义表 {{a,b,c}} 中只有一个子表 {a,b,c}，因此它的长度为 1。

广义表长度的求法：长度的求法为最大括号中的逗号数加1。

广义表深度的求法：深度的求法为每个元素的括号匹配数加1的最大值。

广义表的长度和深度计算 长度：去掉一层括号剩下的是几部分。 深度：去掉几层括号可以到最后一部分，（我理解的是，再没有左括号了）。

9 若线性表最常用的操作是存取第n个元素及其前驱和后继元素的值,为节省时间应采用的存储方式(D)

存取不涉及插入和删除，所以不选链表，选择顺序表

10 利用二叉链表存储树,则根结点的右指针是©

二叉链表： 左孩子右兄弟

根节点没有兄弟，所以为空

二叉链表根节点的左指针指向树的根节点，右指针指向树的根节点的兄弟。 树的根节点没有兄弟，因此为空。

树的二叉链表，就是孩子兄弟表示法，树的双亲表示法也叫顺序表示法，树的孩子表示法也叫链接表表示法，孩子链表表示法也叫单链表表示法，二叉树的二叉链表是双孩子表示法，三叉链表加了双亲指针。

11 下列叙述中，有关线性链表叙述正确的是（D）

线性链表的顺序取决于由指针构成链，与各元素在存储空间上的地址没有关系，所以表头元素也不一定存储在其他元素的前面，故各元素的存储顺序也是任意的。

12 如果使用比较高效的算法判断单链表有没有环的算法中，至少需要几个指针？2 判断链表有没有环，可以用快慢指针来实现，两指针的移动速度不一样。如果相遇，则表示有环，否则表示无环

13 循环链表不是线性表，这样的说法正确吗？(错)

链表都是线性数据结构，图与树是非线性数据结构 1.线性表是n个元素的有限序列，是线性结构，线性结构中的元素具有单一的前驱和后继； 2.循环链表是线性表的基础上扩展的线性结构，可以从任何一个元素节点遍历整个表

14 完成在双向循环链表结点 p 之后插入 s 的操作是（D）

p->next=s;s->prior=p;p->next->prior=s;s-next=p->next

p->next->prior=s;p->next=s;s->prior=p;s->next=p->next

s->prior=p;s->next=p->next;p->next=s;p->next->prior=s

s->prior=p;s->next=p->next;p->next->prior=s;p->next=s

D.这种主要关注是否断链。先把待插入的结点的两个链安排好，再去调整原来的结点。如果先安排原来的结点的链，则几乎都会产生断链的情况。所以A,B不可选，不用多看。C项中，调整原来结点时，先调整的是p->next = s，最后还用p->next->prior,此时的p->next已经是s了。

先处理要插入结点的前驱和后继 再处理后继结点的前驱 最后才是前驱结点的后继

15 某带链的队列初始状态为 front=rear=NULL 。经过一系列正常的入队与退队操作后， front=rear=10 。该队列中的元素个数为（1 ）

在队列为链栈时，除了初始构造是皆为空外，当这两个指针再次相遇时，这个链队列的元素为一个。注意和循环队列区别

往队列的队尾插入一个元素为入队，从队列的排头删除一个元素称为退队。初始时 front=rear=0 ， front 总是指向队头元素的前一位置，入队一次 rear+1 ，退队一次 front+1 。队列队头队尾指针相同时队列为空。而带链的队列，由于每个元素都包含一个指针域指向下一个元素，当带链队列为空时 front=rear=Null ，插入第 1 个元素时， rear+1 指向该元素， front+1 也指向该元素，插入第 2 个元素时 rear+1 ， front 不变，删除 1 个元素时 front+1 。即 front=rear 不为空时带链的队列中只有一个元素。

16 现有线性表（16，37, 43，55, 73，97，110，100），对其进行散列存储， 若选用H(K)=K%9作为散列函数，则散列地址为1的元素有（4）个。

把上面元素mod9运算 结果为1的有4个。就是除以9余数为1

考查哈希表的查找----哈希函数的构造方法—除留余数法是用关键字k除以某个不大于哈希表长度m的整数p所得的余数作为哈希地址的方法。 即求余运算得到为1的个数。

17 下列叙述中错误的是（ B）

循环队列是队列的一种顺序存储结构，用队尾指针 rear 指向队列中的队尾元素，用排头指针 front 指向排头元素的前一个位置。循环链表是用不连续的存储单元存储数据，它有一个表头结点，队头指针指向表头结点，最后一个结点的指针域指向表头结点。二叉链表是树的二叉链表实现方式。栈是一种特殊存取方式的线性表。故本题答案为 B 选项。

18 从一个具有 n 个结点的单链表中查找其值等于 x 结点时，在查找成功的情况下，需平均比较（ ）个结点。 D

最少1次 最多n次 平均(n+1)/2次 （1+2+3+…+n）/n=（n（n+1）/2）/n=（n+1）/2

19 以下关于线性表的说法不正确的是____C__。

A，可以，比如java可以不设泛形或者设置为Object。 B，线性表元素个数要有限，对。 C，除头尾节点外。 D，一个元素的线性表或者空表可以符合条件。对

20 关于双链表的搜索给定元素操作的说法正确的是?B

如果链表数据是无序的，则单向搜索与双向搜索平均速度相同 如果链表是有序的，而要搜索的数据距离最小值（最大值）较近，这种情况下双向搜索平均速度更快。 因此双向搜索更稳定，方差更小

21 单向链表不满足的描述是（ AD）

22在一个单链表中，q 的前一个节点为 p，删除 q 所指向节点，则执行 D

【解析】 让p指向q的下一个节点； 再删除q 23 将两个长度为 len1 和 len2 的升序链表，合并为一个长度为 len1+len2 的降序列表，采用 归并算法，在最坏情况下，比较操作的次数与（ ）最接近 . A

首先链表反转的时间复杂度是O(n)和 O(m)，然后将两个链表连接，（最优情况）当两个链表一个先走完，另一个没有动的时候结果最优，最优的时间为min(len1,len2);（最坏情况）当两个链表交替进行的时候，连接两个链表的时间最长len1+len2。

24 广义表运算式 Tail(((a,b),(c,d)))的操作结果是（ C ）。

取表尾tail表头head操作: 深度为1 head((a,b,c,d))=a; 深度为1 tail((a,b,c,d))=(b,c,d); 深度为2 head(((a,b),(c,d)))=(a,b) 深度为2 tail(((a,b),(c,d)))=((c,d)) 这里的深度有个小技巧:从最右边看半括号个数(注意最外一层是不算的，它是作为head或者tail运算时整体的一部分的)。 如果计算的是head操作，会发现计算结果的右半括号个数是深度–1; 如果计算的是tail操作，会发现计算结果的右半括号个数是=深度; 25 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( )存储方式最节省运算时间。D

1,单链表只能单向遍历，即只能由链表头向链表尾遍历。 2，单循环链表也只能单向遍历：链表头->链表尾->链表头； 对于A,B，C要想在尾端插入结点，需要遍历整个链表。对于D，要插入结点，只要改变一下指针即可，要删除头结点，只要删除指针.next的元素即可。

单链表只能单向遍历，所以最好是有尾指针的循环链表，可以从尾指针加一到链表头部（头指针不能减一到尾部，因为是单向遍历）

26 栈通常采用的两种存储结构是什么？A

顺序存储结构是 存储结构 类型中的一种，该结构是把逻辑上相邻的 节点 存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。 链式存储结构，又叫链接存储结构。在计算机中用一组任意的 存储单元 存储线性表的 数据元素 (这组存储单元可以是连续的,也可以是不连续的).

我们需要区分数据的存储结构与逻辑结构。 存储结构主要是指存储方式，包含线性存储与链式存储，它是从计算机存储的角度去考虑。 逻辑结构指的是数据之间的关系，有线性关系和链式关系等，主要是从人为定义角度去考虑。 数组是一种被人们定义为线性关系的表，至于其存储结构，可以用线性存储也可以是链式存储去存储。 因此C是错误的。

27 将N条长度均为M的有序链表进行合并，合并以后的链表也保持有序，时间复杂度为(A)?

1. 在每一个链表中取出第一个值，然后把它们放在一个大小为N的数组里，然后把这个数组当成heap建成小(大)根堆。此步骤的时间复杂度为O(N)

2. 取出堆中的最小值(也是数组的第一个值), 然后把该最小值所处的链表的下一个值放在数组的第一个位置。如果链表中有一个已经为空（元素已经都被取出），则改变heap的大小。此步骤的时间复杂度为O(lg N).

3. 不断的重复步骤二，直到所有的链表都为空。 建堆只建一次，复杂度为O(N)；调整堆MN-1次，复杂度为(MN-1)O(lg N)。所以为O(MNlg N)

28 在循环双链表的 p 所指的结点之前插入 s 所指结点的操作是 。D

p->prior = s；s->next = p；p->prior->next = s；s->prior = p->prior

p->prior = s；p->prior->next = s；s->next = p；s->prior = p->prior

s->next = p；s->prior = p->prior；p->prior = s；p->prior->next = s

s->next = p；s->prior = p->prior；p->prior->next = s；p->prior = s

29 某一系统功能,需要一次性加载N(N在1000左右)个随机数,后续只对该集合进行遍历.最宜采用哪种结构存放？ C

随机数，未经排序，二叉树不适合； 需要遍历，hash表不适合； 不强调数据之间的关系，图不适合； 随机数数据类型不一致，数组不适合。 综上所述，链表最适合。

30若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除进入表中的最后一个元素，则采用（ C　 ）存储方式最节省运算时间和存储空间。

因为删除需要知道前一个元素的指针，这里只知道尾指针，所以删除最后一个元素需要遍历到最后一个元素

单链表：尾插入O(n),尾删O(n) 仅有头的单循环链表：尾插入O(n),尾删O(n) 双向链表：尾插入O(n),尾删O(n) 仅有尾指针的单循环链表：尾插入O(1),尾删O(n) 相比较而言时间上还是D最好。空间上，D项只多用一个尾指针空间复杂度尾O(1)

31 已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是©

若广义表Ls非空(n≥1)，则a l 是LS的表头，其余元素组成的表( a 2 ，a3,…，a n )称为Ls的表尾。 任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。 tail(LS)=((d,e,f)) head(tail(LS))=(d,e,f) tail(head(tail(LS) )) = (e,f) head(tail( head(tail(LS) ) )) = e

32 ( )不带头结点的单链表head为空的判定条件是 A

head==NULL

head->next==NULL

head!=NULL

head->next==head

所谓头结点，是为了使空链表和非空链表的处理统一而在链表的头部增加的一个节点，这样无论链表是否为空，头指针都指向头结点，头结点中不存数据而只是存放指向第一个节点的指针。没有头结点的链表，头指针就指向第一个节点。因此，单链表为空时，head==NULL。

33 当静态链表采用数组实现时，插入与删除操作仍需移动元素，这种说法（错误）

实现静态链表的方法 定义一个较大的结构数组作为备用结点空间 ( 即存储池 ) 。当申请结点时，每个结点应含有两个域： data 域和 cursor 域。 data 域用来存放结点的数据信息，此时的 cursor 域不再是指针而是游标指示器，游标指示器指示其后继结点在结构数组中的相对位置 ( 即 数组下标 ) 。 静态链表采用数组实现链表的存储，用空间换取时间，删除与插入需要改的是游标

34 有一个单向链表，头指针和尾指针分别为p，q，以下哪项操作的复杂度不受队列长度的影响？ACD

B删除尾部元素，需要找到尾部元素的前一个元素，与队列长度有关

虽然给出了尾指针，但是单链表删除还要知道前一节点,所以还是要遍历一遍才能知道尾指针前一节点 既与队列长度有关

35 以下描述中错误的是（B）

顺序表可以存储非线性结构

顺序表的优点是存储密度大，且插入、删除运算效率高

散列法存储的基本思量是由关键字的值决定数据的存储位置

栈和队列存储方式既可是顺序方式，也可是链式方式

A选项：完全二叉树属于非线性结构，但其最佳存储方式是顺序存储方式。所以A对 B选项的前半句没啥问题。错在后半句，插入删除需要移动大量数据。

对 D ： 栈有顺序栈和链栈； 队列有链队列和循环队列。

顺序栈和循环队列为顺序存储结构，链栈和链队列为链式存储 结构。

36 链接线性表是顺序存取的线性表。 (√ )

随机存取——顺序表。 顺序存取——链表。应该是这样理解 线性表的存储和存取结构 链接线性表可以理解为链表 线性表分为顺序表和链表 顺序表是顺序存储结构、随机存取结构 链表是随机存储结构、顺序存取结构

37 若广义表A满足Head(A) = Tail (A), 则A为 B

广义表第一个元素是表头，其余元素是表尾，如果只有一个元素，那么表尾为空即（）， B中head(A)=();tail(A)=(); 但是在选项C中，head(A)=();tail(A)=（（））; D中head(A)=);tail(A)=((),()); 所以重点是求表尾时不要遗忘最外面的那一层括号

对任意一个非空的广义表，其表头可能是单元素，也可能是广义表，而其表尾一定是广义表。注意表尾的深度（即括号的嵌套层数），表尾是由除了表头以外的其余元素组成的广义表，所以，需要在表尾的直接元素外面再加一层括号。

38 双循环链表中，任意一结点的后继指针均指向其逻辑后继。(×) 尾节点的后继指向头结点，而头结点不是尾节点的逻辑后继 逻辑后继:指在存储时按照需要给定的逻辑顺序在其后的数据块。循环链表中尾节点的逻辑后继应该为null而其后继指针指向了头节点。

39 下列叙述中不正确的是（ ACD ）

在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构

在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是非线性结构

在链表中，如果每个结点有两个指针域，则该链表一定是线性结构

在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构

对于数据结构课程而言，简单地说，线性结构是n个数据元素的有序（次序）集合。 1．集合中必存在唯一的一个"第一个元素"； 2．集合中必存在唯一的一个"最后的元素"； 3．除最后元素之外，其它数据元素均有唯一的"后继"； 4．除第一元素之外，其它数据元素均有唯一的"前驱"。 数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。 非线性结构：数学用语，其逻辑特征是一个结点元素可能有多个直接前趋和多个直接后继。 A选项：在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构，错，类似于传统的双链表，一个指向前一个结点，一个指向后一个结点，这种双链表还是一个线性结构。 B选项：在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是非线性结构。对，如果有两个结点的同一个指针域的值，那么被指向的这个点，有两个前驱，违背了唯一的特点，所以必须是非线性结构。 C选项：在链表中，如果每个结点有两个指针域，则该链表一定是线性结构，错。例如变种的双链表，一个指向后继结点，一个指向链表中的任意结点。如果指向同一结点的话，就类似B选项，所以这个选项是错的。 D选项：在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构，错。一个普通的链表中，不同的结点值可以相等，但是这种链表是线性结构。所以这个选项是错的。（这里的指针域应该指的是链表中指向下一个节点的指针,而线性结构的链表的两个节点之间的指针域不可能相等的 ）

40 用邻接表表示图进行深度优先遍历时,通常是采用（）来实现算法的。

深度用栈，广度遍历用队列 图的邻接表表示：包括表头结点和表结点。表头结点存储各顶点以及每个顶点指向的第一条边(指针)。表结点存储顶点下标，权重以及指向的下一条边。

41 下列叙述中正确的是（A ）。

在链式存储结构中，无论是循环链表还是线性链表，插入和删除元素时，只需要改变相应位置的结点指针即可，头指针和尾指针无法确定链表的长度

B：应该是队尾和队头指针共同决定 C、D：如果中间插入和删除，并不影响头指针和尾指针

42 解析XML时，需要校验节点是否闭合，如必须有与之对应，用（）数据结构实现比较好（D）

栈的应用： 1、符号匹配； 2、表达式求值； 3、实现函数调用 栈是解决封闭对应问题的有效方法。 比如在解析XML中，遇到一个标签（左标签）就入栈，遇到其子标签的左标签（如）同样入栈。遇到右标签(如或)就校验栈顶标签是否与该右标签对应，能对应就出栈，不能对应则说明标签不对称，是无效的XML文件

43 设某散列表的当前状态如下:该散列表的负载因子约为( )A

散列表的一个重要参数是负载因子a，a=散列表中结点的数目/基本区域能容纳的结点数。 负载因子的大小体现散列表的装满程度。a越大，发生碰撞的可能性越大，一般取a＜1。 题目中的散列表结点的数目为7，基本区域能容纳的结点数为19，因此a=7/19≈0.37。

44 下列算法的功能是什么？ D

先Q=L，然后从头开始遍历链表，到最后一个结点时，它的指针指向第一个结点，p->next=Q。

45 NumberList是一个顺序容器，以下代码执行后，NumberList里的元素依次为： C

选c，第一次循环删除元素2，因为是顺序容器，容器中后面所有元素需要向前移动一个位置，即{4,1,3,5}。进入第二次循环判断的是i=1位置的元素，并没有对4进行操作，所以4并没有被删除。所以答案选C

46 线性表是具有 n 个（）的有限序列(n>0) C

线性表：零个或多个数据元素的有限序列 数据项：一个数据元素可以由多个数据项组成（例如：人由眼鼻手脚等组成）

数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成，数据项是构成数据元素的不可分割的最小单位。例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成

47 将长度为n的单链表链接在长度为m的单链表后面，其算法的时间复杂度釆用大O形式表示应该是（ C）

需要先遍历长度为m的链表，找到链表尾部，这个时间复杂度为O(m)，再将链表尾部的next指针指向长度为n的链表的头结点即可

48 单链表的存储密度 C

存储密度=单链表数据项所占空间/结点所占空间 结点所占空间由数据项所占空间和存放后继结点地址的链域，所以，存储密度小于1

49 链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，通常有存储器中还有空闲存储空间，就不会产生存储溢出的问题。（ √ ）

50 邻接表是图的一种顺序存储结构，这种说法（×）

应该是 链式存储结构 ； 邻接表指的是：为图的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（对于有向图是以Vi为尾的弧）。 具体可以看看这篇博客： http://www.cnblogs.com/ECJTUACM-873284962/p/6905416.html

邻接矩阵才是顺序存储 邻接表是链式

51 以下关于单向链表说法正确的是 ABC

1.两个链表都为单链表，那么一旦相交意味着两个节点的next相同，之后的也都相同，所以尾节点也相同。 2.一个是单链表，一个是有环，那么就不可能存在相交的情况。这其中判断链表是否有环就是用的快慢指针法：设置两个指针，一个跳一格，一个跳两格(可以想象成环形跑道)，追上自然就有环了。 3.如果都是循环链表，遍历其中一个链表，直到找到与另一链表中某节点相同的节点就算是相交了。 这三方面也就回答了上述的选项，我觉得是ABC。

52 单链表中，增加一个头结点的目的是为了 。C

不论是带头结点的链表还是不带头结点的链表，头指针head都指向链表中的第一个结点。如果该链表有头结点，则头指针head指向头结点，如果没有头结点，则头指针head指向链表的第一个节点。头结点的存在，使得空链表与非空链表的处理变得一致，也方便了对链表的开始结点插入或删除操作。

链表增加头结点的作用： 1.便于首元节点的处理 2.便于空表和非空表的处理

53 若频繁删除某线性表的第1个元素，则不宜采用以下哪种存储方式 B

对顺序表来说，删除第一个元素就需要后续元素都向前移动一个位置。 每删除一次都需要移动大量元素，因此不宜采用。

54 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用（）存储方式最节省运算时间。D

单链表

仅有头指针的单循环链表

双链表

仅有尾指针的单循环链表

带尾指针的单循环链表，就是单独有一个指针指向最有一个元素，这样a1和an的遍历时间复杂度都是O(1) B选项中查找到最后一个元素需要时间O(n)，比D慢 双向链表和尾指针的单循环链表 在最后一个元素插入一个元素时间复杂度都是O（1） 然后添加完后都需要改变尾指针的指向 但是在删除第一个元素的时候 双向链表除了删除第一个元素还需要改变头指针的指向 而尾指针单循环链表不用改尾指针的指向

之前有个题是：某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除元素,则采用（）存储方式最节省运算时间。 答案是双链表，因为删除元素可能删除得是最后一个元素，此时需要找到尾元素得前驱，因为复杂度O(n)。

55 线索二叉链表是利用（C）域存储后继结点的地址。

左孩子域： 0：指示左孩子 1：指示节点的前驱

右孩子域： 0：指示右孩子 1：指示节点的后继 “一个二叉树通过如下的方法“穿起来”：所有原本为空的右(孩子)指针改为指向该节点在中序序列中的后继，所有原本为空的左(孩子)指针改为指向该节点的中序序列的前驱。

56 设有100个元素的有序表，采用折半查找方法，成功时最大的比较次数是（7) 。 就是算100能被2除多少次

57 在表头和表尾都可能有元素被插入的情况下，在单循环链表中设置尾指针比设置头指针好。 （ √） 树的前序遍历 = 二叉树的前序遍历 树的中序遍历 != 二叉树的任何序遍历 树的后序遍历 = 二叉树的中序遍历

使用指向终端节点的尾指针，查找开始节点和终端节点时间复杂度都是O(1) 找开始节点：（rear->next）->next 找终端节点：rear 如果用头指针，找开始节点的时间是O(1)，找终端节点要从头指针开始遍历整个循环链表，时间是O(n)

58 采用二叉链表作为存储结构,树的前序遍历和其相应的二叉树的前序遍历的结果是一样的(√) 树的二叉链表存储时，一个结点有两个指针域，一个指向它第一个孩子，一个指向它第一个兄弟。而将一般树转换为二叉树时，也是一个结点有一个结点有两个指针域，一个指向它第一个孩子，一个指向它第一个兄弟。