数据结构 第2章 线性表.doc

第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）连续或不连续都可以
（ B ）7． 线性表Ｌ在 情况下适用于使用链式结构实现。
（Ａ）需经常修改Ｌ中的结点值 （Ｂ）需不断对Ｌ进行删除插入
（Ｃ）Ｌ中含有大量的结点 （Ｄ）Ｌ中结点结构复杂
（ C ）8． 单链表的存储密度
（Ａ）大于1； （Ｂ）等于1； （Ｃ）小于1； （Ｄ）不能确定
（ B ）9． 设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为

P0

3

4

P0
à
a1
3
à
a2
4
à
a3
0
（Ａ）循环链表 （Ｂ）单链表 （Ｃ）双向循环链表 （Ｄ）双向链表
（ 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;
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
^

^
100

120
其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？

答：X=116，Y=120，Z=100，首结点起始地址：108，末结点起始地址：112。

五、编程题
1. 写出顺序创建单链表的程序，即按从a1到an顺序创建。
答：void ListInsert(Node &La, int i, ElemType &e)
{
int j = 0;
Node * t = &La;
while (t->next&&j<i)
{
j++;
t = t->next;
}

Node * newnode = (Node *)malloc(sizeof(Node));
Node * nex = t->next;
t->next = newnode;
newnode->data = e;
newnode->next = next;
}
Node La;
for(int i= 0; i <n; i++)
{
ListInsert(La, i, ai);
}
2. 已知一个带头结点的单链表L，请编程求该单链表中数据元素的个数。
答： int ListLength(Node & La)//返回链表中元素个数
{
int count = 0;
Node * t = &La;
while (t->next)
{
count++;
t = t->next;
}
return count;
}
3. 设有一带头结点的单链表,编程将链表颠倒过来，即（a1...an）逆置为(an...a1)，要求不用另外的数组或结点完成.
答： Node * Reverse(Node * front, Node * behind)
If(behind)
{
Node * t = Reverse(behind, behind->next);
behind->next = front;
return t;
}
else
{
return front;
}
}
4．请写一个算法将顺序存储结构的线性表（a1...an）逆置为(an...a1)，要求使用最少的附加空间。
答： if(n%2==0)
{
For(int i = 1; i<=n/2; i++)
{
Data d = L[i].data;
L[i].data = L[n-i].data;
………………..
L[n-i].data = d;
}
}
else
{
For(int i= 1; i<(n+1)/2; i++)
{
Data d = L[i].data;
L[i].data = L[n-i].data;
………………..
L[n-i].data = d;
}
}

5