数据结构/第二章 线性表/数据结构习题/线性表的习题/考研/期末复习

一、选择题

1. 在线性表中，表尾元素（        ）。

A. 有且仅有一个直接前驱               B. 有且仅有一个直接后继

C. 没有直接前驱                             D. 有多个直接前驱

2. 在顺序表上按位查找一个元素的时间复杂度是（        ）。

A. O(1)               B. O(n)                 C. O(nlogn)               D. O()   

3. 在顺序表上按值查找一个元素的平均时间复杂度是（        ）。

A. O(1)               B. O(n)                 C. O(nlogn)               D. O()   

4. 在长度为n的线性表中删除一个节点的最坏情况需要移动结点的次数是（        ）。

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

5. 现有一个单链表，p所指结点是q所指结点的前驱结点，若在p和q之间插入结点s，执行代码（        ）。

A. s->next = q; p->next = s->next      B. p->next = s; s->next = q->next

C. p->next = s; s->next = q      D. q->next = s; s->next = p

二、填空题

1. 线性表是一种物理结构，表示元素存储后的形状像一条线。  （        ）

2. 线性表是具有相同数据类型的n个（n ≥ 0）数据元素的序列。  （        ）

3. 顺序表是一种随机存取的存储结构。  （        ）

4. 静态链表不需要借助地址连续的存储单元就能实现链式存储结构。  （        ）

5. 头指针始终指向链表的第一个结点。  （        ）

三、答案

选择题：A A B C C

判断题：× × √ × √

选择题提示：

4. 注意问的是时间复杂度还是次数

5. 给了几个结点的指针就能用几个结点的指针，没给就要从给的指针向下去找。

判断题详解：

1. 线性表是一种逻辑结构，表示元素之间一对一的相邻关系。

2. 线性表是具有相同数据类型的n个（n ≥ 0）数据元素的有限序列。

4. 静态链表借助数组描述线性表的链式存储结构，与单链表的指针不同，静态链表的指针是结点的数组下标，又称游标。因此，静态链表要预先分配一块连续的存储空间，而在已分配的数组内，不要求逻辑上相邻的元素物理位置也相邻。

5. 头指针始终指向链表的第一个结点（无论是否带有头结点）。扩展：带有头结点的链表中的第一个结点是头结点，头结点内通常不存储信息或存储表长信息。