13181 数据结构-第2章习题和答案

发布网友 发布时间：2024-10-04 18:14

我来回答

共1个回答

热心网友 时间：2024-10-04 19:31

线性表是一种基本的数据结构，它由一系列元素组成，这些元素按照线性顺序排列。线性表中的每个元素都有一个前驱和一个后继（除了头和尾元素）。在不同场景下，线性表可以通过不同的数据结构（如数组、链表）进行存储。以下是关于线性表和数据结构的一些习题及其解答。

一、单项选择题

1. 下列选项中，不是链表特点的是________。

A. 插入、删除时不需要移动元素

B. 可随机访问任一元素

C. 不必事先估计存储空间

D. 所需空间与元素个数成正比

答案：B。链表不支持随机访问，而只能顺序访问。

2. 下列关于线性表的叙述中，错误的是________。

A. 线性表采用链式存储方式，便于进行插入和删除操作

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

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

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

答案：B。顺序存储方式不便于插入和删除操作，因为需要移动元素。

3. 若线性表L最常用的操作是访问任一位置的元素和在最后进行插入和删除运算，为使操作的时间复杂度好，则下列选项中，为L选择的存储结构为________。

A. 顺序表

B. 双向链表

C. 带头结点的双向循环链表

D. 单循环链表

答案：A。顺序表在访问任意位置元素和插入/删除操作上时间复杂度较低。

4. 线性表L中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，为使操作的时间复杂度好，则下列选项中，为L选择的存储结构为________。

A. 单链表

B. 仅有头指针的单循环链表

C. 双向链表

D. 仅有尾指针的单循环链表

答案：D。仅尾指针的单循环链表便于插入和删除操作。

5. 为了提供全程对号的高速铁路售票系统，保证每一位旅客从上车到下车期间都有独立座位，短途乘客下车后该座位可以销售给其他乘客，铁路公司设计了基于内存的系统，系统中需要描述座位信息和每个座位的售票情况。保存座位信息和每个座位售票情况的数据结构分别是________。

A. 数组，数组

B. 数组，链表

C. 链表，数组

D. 链表，链表

答案：B。数组适合描述座位信息，链表适合描述售票情况。

6. 若长度为n的线性表采用顺序存储结构，则在其第i(0≤i≤n)个位置插入一个新元素的算法的时间复杂度为________。

A. O(1) B. O(i) C. O(n) D. O(n2)

答案：C。平均情况下，时间复杂度为O(n)。

7. 对于含n个元素采用顺序存储的线性表，访问位置i（0≤i≤n-1）处的元素和在位置i（0≤i≤n）插入元素的时间复杂度分别为________。

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

答案：C。访问元素的时间复杂度为O(1)，插入元素的时间复杂度为O(n)。

8. 线性表(a0,a1,…,an-1)以链接方式存储时，访问位置i的元素的时间复杂度为________。

A. O(1) B. O(i-1) C. O(i) D. O(n)

答案：D。访问元素的时间复杂度为O(n)。

9. 在带头结点的非空单循环链表head中，指向尾结点的指针p满足的条件是________。

A. p==NULL B. p==head

C. p->next==head D. p->next==NULL

答案：C。尾结点的next指针指向头结点。

10. 带头结点的单链表head为空的判定条件是________。

A. head==NULL B. head!=NULL

C. head->next==head D. head->next==NULL

答案：D。头结点的next指针为空表示链表为空。

11. 在双向循环链表中，在指针p所指结点之后插入指针s所指结点的操作是________。

A. p->next=s;s->prev=p;p->next->prev=s;s->next=p->next;

B. p->next =s;p->next->prev=s; s->prev=p;s->next=p->next;

C. s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;

D. s->prev=p; s->next=p->next;p->next->prev=s; p->next=s;

答案：D。正确地插入s结点。

12. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行的操作是________。

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

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

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

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

答案：C。正确地插入s结点。

13. 在一个单链表中，若p所指结点不是终端结点，在p所指结点之后插入s所指结点，则执行的操作是________。

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

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

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

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

答案：B。正确地插入s结点。