第2章 线性表
一、判断正误
〔 F 〕1. 链表的每个结点中都恰好包含一个指针。 〔 F 〕2. 链表的物理存储结构具有同链表一样的顺序。
〔 F 〕3. 链表的删除算法很简单，因为当删除链中某个结点后，计算时机自动将后续各个单元向前移
动。
〔 F 〕4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 〔 F 〕5. 顺序表结构适宜于进展顺序存取，而链表适宜于进展随机存取。 〔 F 〕6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 〔 F 〕7. 线性表在物理存储空间中也一定是连续的。
〔 T 〕8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 〔 F 〕9. 顺序存储方式只能用于存储线性结构。 〔F 〕10. 线性表的逻辑顺序与存储顺序总是一致的。
二、单项选择题
〔 C 〕1．数据在计算机存储器表示时，物理地址与逻辑地址一样并且是连续的，称之为：
〔A〕存储结构 〔B〕逻辑结构 〔C〕顺序存储结构 〔D〕链式存储结构
〔 B 〕2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，那么第5个元素的地址是
〔A〕110 〔B〕108 〔C〕100 〔D〕120
〔 A 〕3. 在n个结点的顺序表中，算法的时间复杂度是O〔1〕的操作是：
（A） 访问第i个结点〔1≤i≤n〕和求第i个结点的直接前驱〔2≤i≤n〕 （B） 在第i个结点后插入一个新结点〔1≤i≤n〕 （C） 删除第i个结点〔1≤i≤n〕 〔D〕 将n个结点从小到大排序
〔 B 〕4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素
〔A〕8 〔B〕63.5 〔C〕63 〔D〕7
〔 A 〕5. 链式存储的存储结构所占存储空间：
（A） 分两局部，一局部存放结点值，另一局部存放表示结点间关系的指针 （B） 只有一局部，存放结点值
〔C〕只有一局部，存储表示结点间关系的指针
〔D〕分两局部，一局部存放结点值，另一局部存放结点所占单元数
〔 D 〕6. 线性表假设采用链式存储结构时，要求存中可用存储单元的地址:
〔A〕必须是连续的 〔B〕局部地址必须是连续的 〔C〕一定是不连续的 〔D〕连续或不连续都可以
1 / 5
〔 B 〕7． 线性表Ｌ在情况下适用于使用链式结构实现。
〔Ａ〕需经常修改Ｌ中的结点值 〔Ｂ〕需不断对Ｌ进展删除插入 〔Ｃ〕Ｌ中含有大量的结点 〔Ｄ〕Ｌ中结点结构复杂
〔 C 〕8． 单链表的存储密度
〔Ａ〕大于1； 〔Ｂ〕等于1； 〔Ｃ〕小于1； 〔Ｄ〕不能确定
〔 B 〕9． 设a1、a2、a3为3个结点，整数P0，3，4代表地址，那么如下的链式存储结构称为
P0
a1 3 3
a2 4 4
a3 0 P0
〔Ａ〕循环链表 〔Ｂ〕单链表 〔Ｃ〕双向循环链表 〔Ｄ〕双向链表
〔 B 〕10．下面关于线性表的表达中，错误的选项是哪一个？
A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进展插入和删除操作。 C．线性表采用存储，不必占用一片连续的存储单元。 D．线性表采用存储，便于插入和删除操作。
〔 C 〕11．线性表是具有n个________的有限序列〔n>0〕。
A．表元素 B．字符 C．数据元素 D．数据项
〔 A 〕12．假设某线性表最常用的操作是存取任一指定序号的元素和在最后进展插入和删除运算，那
么利用______存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
〔 D 〕13．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，那么采
用 _______存储方式最节省运算时间。
A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表
〔 B 〕14. 静态链表中指针表示的是________.
A． 存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址
〔 B 〕15. 链表不具有的特点是_________.
A．插入、删除不需要移动元素 B．可随机访问任一元素
C．不必事先估计存储空间 D．所需空间与线性长度成正比 〔 D 〕16．完成在双循环链表结点p之后插入s的操作是〔 〕.
A． p^.next:=s ; s^.priou:=p; p^.next^.prior:=s ; s^.next:=p^.next; B． p^.next^.prior:=s; p^.next:=s; s^.prior:=p; s^.next:=p^.next; C． s^.prior:=p; s^.next:=p^.next; p^.next:=s; p^.next^.prior:=s ; D． s^.prior:=p; s^.next:=p^.next; p^.next^.prior:=s ; p^.next:=s;
〔 B 〕17．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：〔 〕。
A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s;
2 / 5
C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s;
〔 B 〕18．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是〔 〕
A．head==NULL B．head->next==NULL C．head->next==head D．head!=NULL
〔 A 〕19. 在双向链表存储结构中，删除p所指的结点时须修改指针〔 〕。
A． (p^.llink)^.rlink:=p^.rlink (p^.rlink)^.llink:=p^.llink; B． p^.llink:=(p^.llink)^.llink (p^.llink)^.rlink:=p; C． (p^.rlink)^.llink:=p p^.rlink:=(p^.rlink)^.rlink D． p^.rlink:=(p^.llink)^.llink p^.llink:=(p^.rlink)^.rlink;
三、简答题
1．线性表有两种存储结构：一是顺序表，二是链表。试问：
〔1〕如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地
改变。在此情况下，应选用哪种存储结构？ 为什么？
答：链式存储结构。因为长度动态变化是因为要进展插入和删除操作，而进展这些操作，链式结构不需要
移动数据元素，效率较高。所以选用链式结构。
〔2〕假设线性表的总数根本稳定，且很少进展插入和删除，但要求以最快的速度存取线性表中的元素，
那么应采用哪种存储结构？为什么？
答：顺序存储结构。因为顺序存储结构可利用起始地址和偏移量在较短时间完成存取，效率较高。 所以选用顺序存储结构。
2 . 在单链表中设置头结点的作用是什么？
答：①对数据进展插入、删除操作时，可直接通过修改指针完成前驱和后继的处理。 ②表头指针非空，不需要再判断是否为空表。
四、线性表具有两种存储方式，即顺序方式和方式。现有一个具有五个元素的线性表L={23，17，47，05，31}，假设它以方式存储在以下100～119号地址空间中，每个结点由数据〔占2个字节〕和指针〔占2个字节〕组成，如下所示：
05 ^
U 17 X 23 V 31 Y 47 Z
^ 120
100
其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？
答：X=116，Y=120，Z=100，首结点起始地址：108，末结点起始地址：112。
五、编程题
1. 写出顺序创立单链表的程序，即按从a1到an顺序创立。 答：void ListInsert(Node &La, int i, ElemType &e)
3 / 5
数据结构_第2章_线性表
