第2章习题（带答案）

1．链表不具有的特点是 。

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

2．在一个具有n个结点的单链表中查找值为x的某结点，若查找成功，则平均

比较 个结点。

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

3.在单链表中P所指结点之后插入一个元素x的主要操作语句序列是 s=(node *)malloc(sizeof(node));、 s->data=x;、 s->next=p->next、 p->next=s。 4.在单链表中查找第i个元素所花的时间与i成正比。（√ ）

5．在带头结点的双循环链表中，任一结点的前驱指针均不为空。（ √ ） 6.用链表表示线性表的优点是 ( )。 A. 便于随机存取 C. 便于插入与删除

B. 花费的存储空间比顺序表少

D. 数据元素的物理顺序与逻辑顺序相同

7.在双向链表中删除P所指结点的主要操作语句序列是 p->prior->next=p->next; 、 p->next->prior=p->prior; 、 free(p); 。 8.下述哪一条是顺序存储结构的优点？（ ）

A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示

9．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ ）存储方式最节省运算时间。

A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表 10. 对任何数据结构链式存储结构一定优于顺序存储结构。（×）

11.对于双向链表,在两个结点之间插入一个新结点需修改的指针共 4 个，单链表为____2___个。

12.以下数据结构中，（ ）是非线性数据结构

A．树 B．字符串 C．队列 D．栈

13.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表

14. “线性表的逻辑顺序和物理顺序总是一致的。”这个结论是（ ）。 A、正确的 B、错误的 C、不一定，与具体结构有关。

15.在一个长度为n的顺序表中插入一个数据元素，最少要移动 0 个数据元素，最多要移动 n 个数据元素，平均要移动 n/2 个数据元素。 16.线性表采用链式存储结构时，其地址( )

A) 必须是连续的 B）一定是连续的 C)部分地址必须是连续的 D) 连续与否均可以 17.带头结点的单链表head为空的判断条件是( )。

A)head==NULL B)head->next==NULL C)head->next==head D)head!=NULL 18.线性表的长度是线性表所占用的存储空间的大小。(×)

19.在一个长度为n的顺序表中删除一个数据元素，最少要移动 0 个数据元素，最多要移动 n-1 个数据元素，平均要移动 (n-1)/2 个数据元素。 20. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素需要移动的元素个数为( )。(1≤i≤n+1)

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

21.若长度为n的线性表采用顺序存储结构，在其第i个位置删除一个元素的算法的平均时间复杂度为( )。(1≤i≤n) A．O(0) B．O(1) C.O(n) D．O(n2)

21.带头结点的单循环链表h为空表的条件是 h->next=h; 。 22.线性表采用顺序存储结构时，要求内存中可用存储单元的地址 。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续不连续都可以 23. 线性表是具有N个（ ）的有限序列。

A、表元素 B、字符 C、数据元素 D、数据项 E、信息 24．循环链表主要优点是（ ） A、不再需要头指针了

B、已知某个结点的位置后，能够容易找到它的直接前趋 C、在进行插入、删除运算时，能更好地保证链表不断开 D、从表中任一结点出发都能扫描到整个链表

25. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。

A、顺序表 B、单链表 C、双链表 D、单循环链表 26.在带头结点的单循环链表中，任一结点的后继指针均不空。(√) 27.在双循环链表中，任意一结点的后继指针均指向其逻辑后继。(错)

28.在单链表中，已知r和s是指向链表中两个结点的指针，且满足r->next==s，则删除指针s所指结点的语句序列是 __r->next=s->next__、 free(s) 。 29. 在线性表的下列存储结构中，读取元素花费时间最少的是（ ） A、单链表 B、双链表 C、循环链表 D、顺序表 30.在单链表中指针p所指向结点的后面插入指针q所指结点的语句序列为 q->next=p->next 、 p->next=q 。 31.假设双链表结点的类型如下： typedef struct linknode{

int data; ／／数据域

struct linknode *prior; ／／指向前趋结点的指针域 struct linknode *next; ／／指向后继结点的指针域 }bnode

现将一个q所指新结点作为非空双向链表中的p所指结点的前趋结点插入到该双链表中，能正确完成此要求的语句段是（ ）。

Ａ、q->next=p;q->prior=p->prior;p->prior=q;p->prior->next=q; Ｂ、p->prior=q;q->next=p;p->prior->next=q;q->prior=p->prior Ｃ、q->prior=p->next;q->next=p;p->prior->next=q;p->prior=q; Ｄ、以上都不对

32. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ ）。

A、O(1) B、O(n) C、O(n2) D、O(nlog2n)

33.图2所示的双链表中, _____组语句将s所指结点插入到p所指结点的后面。

p ? 2 5 7 ?

6 s

图2 双链表

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

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

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

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

p->next->prior = s;

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

p->next = s;

D) p->next = s;

s->prior = p;

s->next = p->next;

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

p->next->prior = s;

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

A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表

35.不带头结点的单链表head为空的判断条件是( )。

A)head==NULL B)head->next==NULL C)head->next==head D)head!=NULL

36、在单链表中，指针p所指结点为最后一个结点的条件是__p->next=NULL___。 37、为了便于讨论，有时将含n(n≥0)个结点的线性结构表示成(a1，a2,?,an)，其中每个ai代表一个__数据元素____。a1称为__首元____结点，an称为__尾元____结点，i称为ai在线性表中的___序号_____。对任意一对相邻结点ai、ai┼1(1≤i

本文来源：https://www.bwwdw.com/article/z8c5.html