单选题

链表不具备的特点是()

A. 不必事先估计存储空间 B. 随机访问 C. 插入删除时不需移动元素 D. 所需空间与线性表成正比

答案:B

解释:链表的访问是需要从头结点/无头结点的第一个节点开始顺序的访问。一个个的遍历过去。所以链表不具备随机访问的特点。只有顺序表才具有随机访问的特点。因为顺序表是由数组构成的。

在单链表指针为p的结点之后插入指针为s的结点,正确的操作是()

A. p->next=s;s->next=p->next; B. p->next=s;p->next=s->next; C. s->next=p->next;p->next=s; D. p->next=s->next;p->next=s

答案:C

解释:

在顺序表中,只要知道(),就可以求出任意一个结点的存储地址

A. 向量大小 B. 结点大小 C. 基地址 D. 基地址和结点大小

答案:D

解释:基地址相当于顺序表的起始地址。按照节点大小开始计算。基地址=0x02,结点大小为4. 0x02+4

两个指针P和Q,分别指向单链表的两个元素,P所指元素是Q所指元素前驱的条件是()

A. P==Q B. P->next==Q->next C. Q->next==P D. P->next==Q

答案:D

解释:

在单链表中,增加头结点的目的是()

A. 方便运算的实现 B. 使单链表至少有一个结点 C. 说明该单链表是线性表的链式存储结构 D. 标志表中首结点的位置

答案:A

解释:头结点在单链表中通常用来简化操作的实现，因为它避免了对链表特殊位置（如第一个结点）的特殊处理。在有头结点的单链表中，插入、删除等操作可以在所有结点位置使用统一的方法处理，而不必单独考虑头部位置的不同情况。这提高了算法的通用性和代码的简洁性。

对具有n个结点的线性表进行插入或删除操作,所需的算法时间复杂度为()

A. O(nlog2n) B. O(log2n) C. O(n2) D. O(n)

答案:D

解释:

假设有4个节点。需要进行插入。在头部插入一个元素就需要移动4-1次。在尾部插入不需要移动。如果删除的是头部元素就需要移动4-1次。在尾部删除就不需要移动。将节点数量扩大也类似。

移动元素的数量最多是n-1个。不会达到n，因为不需要移动要插入的位置或者删除的位置本身

设p为指向单循环链表上某结点的指针,则*p的直接前驱()

A. 查找时间复杂度为O(n) B. 查找结点的次数约为n C. 找不到 D. 查找时间复杂度为0(1)

答案:A

解释:要寻找*p的直接前驱，就需要一个个的遍历。

用链表表示线性表的优点是()

A. 便于进行插入和删除操作 B. 元素的物理顺序与与逻辑顺序一致 C. 占用的存储空间较顺序表少 D. 便于随机存取

答案:A

解释:链表的插入和删除都是由指针实现的。只要改变next指针即可。

在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为()。

A. O(log2n) B. O(n2) C. 0(1) D. O(n)

答案:D

解释:假设在4个节点的顺序表上进行插入或者删除。插入1个元素就需要移动3个元素。即n-1个元素。删除也想通。

在一个长度为n的顺序表中,若要在第i(1≤i≤n)个元素前插入一个元素时,则需向后移动()个元素。

A. i B. n-1+1 C. n-i-1 D. n-i

答案:D

解释:假设长度为4，若要在第2个元素前插入一个元素k(k表示整数)时。

1 2 3 4 -> 1 k 2 3 4。 这里移动了3个元素。k之前的元素不需要移动。扩大范围之后就是n-i

在这种情况下，答案中并没有包含插入位置本身，所以不是n-i-1而是n-1个元素。因此对于在位置i前插入一个元素的情况，所需要移动的元素个数是n-i个。

出现n-i-1的情况是题目中需要出现移动插入元素本身。

出现n-i+1的情况是在位置i及其之后的元素都需要后移。这种情况一般都是包含了插入点位置上的元素。

以下链表结构中,从当前结点出发能够访问到任意结点的是()。

A. 循环链表和单向链表 B. 单向链表和双向链表 C. 单向链表、双向链表和循环链表 D. 循环链表和双向链表

答案:D

解释:只有循环链表和双向链表可以访问任意节点。

循环链表包含了pre指针和next指针。他可以向前或者向后移动。

双向链表的特点是尾结点指向头结点，形成一个环状结构。这样，无论从哪个节点出发，都能遍历整个链表。

单链表因为只有一个next指针,无法保证在一个方向上访问到链表中的所有结点。

等概率情况下,在有n个结点的顺序表上做插入结点运算,需平均移动结点的数目为()。

A. n/2 B. (n-1)/2 C. (n+1)/2 D. n

答案:A

解释:

A的情况

1.若要在头部插入一个元素(i=1),则需要移动n个节点。

2.若要在尾部插入一个元素(i=n+1),则需要移动0个节点。

3.若要在中间插入一个元素(i=n/2),需要移动n/2个节点。

假设所有的位置概率相同=n,1+2+3+…+n=>(n+1)*n/2

![Image description](f

ile:///https://sharenjun.github.io/media/posts/13/image-20241011234944425.png =1875x316)

B的情况

去掉头部或尾部的插入/删除次数。假设n=4,则算出来平均次数为1.5次。

C的情况

所有结点移动的次数再加上x部分。假设n=4,则算出来的平均次数为2.5次。超出需要移动的次数了。这一部分理解的并不深刻。不知道这样的解释正确不正确。

在()的运算中,使用顺序表比链表好

A. 根据序号查找 B. 根据元素查找 C. 删除 D. 插入

答案:A

解释:顺序表按照序号查找最快。

在一个长度为n的顺序表中,若要删除第i(1≤i≤n)个元素,则需向前移动()个元素。

A. i B. n-i-1 C. n-i D. n-i+1

答案:C

解释:与插入类似。

下而关于线性表的叙述中,错误的是()。

A. 线性表采用链接存储,便于插入和删除操作。 B. 线性表采用顺序存储,必须占用一片连续的存储单元。 C. 线性表采用链接存储,不必占用一片连续的存储单元。 D. 线性表采用顺序存储,便于进行插入和删除操作。

答案:D

解释:

A. 线性表采用链接存储，便于插入和删除操作。

正确。链式存储（如单链表、双链表）允许在任意位置方便地插入或删除元素，只需调整指针而无需大规模的数据移动。

B. 线性表采用顺序存储，必须占用一片连续的存储单元。

正确。顺序存储（如数组）需要在内存中分配一片连续的存储空间，以存放所有元素。

C. 线性表采用链接存储，不必占用一片连续的存储单元。

正确。链式存储中各结点通过指针连接，因此不需要连续的存储单元，各结点可以分布在内存的不同位置。

D. 线性表采用顺序存储，便于进行插入和删除操作。

错误。顺序存储在插入和删除操作时，需要移动大量元素，尤其在表头或表中间位置操作时会显著增加操作时间，因此不方便。

填空题

1

若对一个线性表经常进行查找操作，而很少进行插入和删除操作时，则采用____存储结构为宜，相反，若经常进行的是插入和删除操作时，则采用____存储结构为宜。 我的答案： (1) 顺序 (2) 链式

2

线性表L=(a1,a2,…，an)采用顺序存储，假定删除表中任意元素的概率相同，则删除一个元素平均需要移动元素的个数是

(1) (n-1)/2

假设n=4. L=(a1,a2,a3,a4);

删除 a1，需要移动3个元素(a2,a3,a4)。 n-1

删除 a2，需要移动2个元素(a3,a4)。 n-2

删除 a3，需要移动1个元素(a4)。 n-3

删除 a4，需要移动0个元素。

(3+2+1+0)/n=1.5

(n-1)+(n-2)+(n-3)+…+0=n(n-1)/2 再利用(n(n-1)/2)/n得到(n-1)/2

3

在长度为n的顺序表中，如果要在第n个元素前插入一个元素，要后移____个元素。

(1) 1

长度为n，在n前插入一个元素。只要移动1个即可。就是n本身。

4

链表相对于顺序表的优点是插入、删除方便;缺点是存储密度__小__。

解释:这是因为链表中的每个节点不仅需要存储数据本身，还需要存储指向下一个节点的指针（在双向链表中还需存储指向前一个节点的指针），这会额外占用存储空间。因此，链表的存储密度（即数据元素所占用的总存储空间与链表的实际存储空间之比）低于顺序表。

5

顺序表相对于链表的优点是：____和随机存取;链表相对于顺序表的优点是：____方便。

(1) 节省存储 (2) 插入删除

6

链式存储的特点是利用____来表示数据元素之间的逻辑关系。

(1) 指针

7

在单链表中要在已知结点p之前插入一个新结点，需找到p的直接前趋结点的地址，其查找的时间复杂度为____。

(1) O(n)

8

在双向链表中，每个结点有两个指针域，一个指向其____结点，另一个指向其____结点。

(1) 前驱 (2) 后继

9

在一个双链表中，设指针p是指向该表中待删除的结点，则需要执行的操作为：____。

(1):

p->pre->next=p->next;//p的前驱节点的next指针,指向p->next个元素。

p->next->pre=p->pre;//p的后继节点的pre指针,指向p->pre个元素

//以上实现断链的效果。

free(p);

判断题

1

线性表的链式存储结构优于顺序存储结构。 x

2

顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 x

解释:

顺序表（例如数组）适合 随机存取，因为每个元素的地址是连续的，访问第i个元素的时间复杂度是O(1)即可以通过直接计算内存地址快速访问。

链表 适合 顺序存取，因为链表的节点在内存中不是连续的，访问某个特定位置的元素需要从头开始逐个遍历，时间复杂度为O(n)

3

在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。√

4

顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。x

5

线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 x

6

插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。 x

解释:数组适合随机存取。并不适合插入、删除。

7

线性表采用顺序存储，必须占用一片连续的存储单元。√

8

线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。√

9

顺序存储方式的优点是存储密度大，插入、删除效率高。 x

10

链表的每个结点都恰好包含一个指针域。√