一、填空（每空1分，共13分）
1.
2.
3.
1.
2.
3.
新浪博客
FONT>≤n+1)之前插入一个元素时，需向后移动
4.
5.
6.
7.
8．
二、判断正误（在正确的说法后面打勾，反之打叉）（每小题1分，共10分）
（
答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。
（
（
（
错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。
（
错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”
（
错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。
（
错，线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。
（
错误。线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。
（
错误。顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍）
（
错，理由同7。链式存储就无需一致。
三、单项选择题（每小题1分，共10分）
（
（A）存储结构
（
（A）110
（
（A）
（B）
（C）
（D）
（
（A）8
（
（A）
（B）
（C）
（D）
（
（A）顺序
（
（A）必须是连续的
（C）一定是不连续的
（
（Ａ）需经常修改Ｌ中的结点值
（Ｃ）Ｌ中含有大量的结点
（
（Ａ）大于1；
（
（Ａ）循环链表
四、简答题（每小题5分，共10分）
1.
答：①
优点：存储密度大（＝1？），存储空间利用率高。缺点：插入或删除元素时不方便。
②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。
顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。
若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
2
答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。
简而言之，
头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；
头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针！！！）
首元素结点是指链表中存储线性表中第一个数据元素a1的结点。
五、【软考题】线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L={23，17，47，05，31}，若它以链接方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下所示：
其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？（10分）
答：X=
六、阅读分析题（10分）
【严题集2.10②】指出以下算法中的错误和低效（即费时）之处，并将它改写为一个既正确又高效的算法。
![线性表部分习题及答案]( "线性表部分习题及答案")
![线性表部分习题及答案]( "线性表部分习题及答案")
答：错误有两处：
①
合法的入口参数条件为（0<i≤a.length）^
应将if
改为：if
第二个FOR语句中，元素前移的次序错误。应将for
改为for
七、编程题（每题10分，共40分）
![线性表部分习题及答案]( "线性表部分习题及答案")
1.
解：输入：长度为n的线性表数组A(1:n)
输出：逆转后的长度为n的线性表数组A(1:n)。
C语言描述如下（其中ET为数据元素的类型）：
2.
![线性表部分习题及答案]( "线性表部分习题及答案")
答：
3.
解：编写C程序如下(已上机通过)：
全局变量及函数提前说明：
---------------------------------
#include<stdio.h>
#include<stdlib.h>
typedef
text
int
void
{int
head=(test*)malloc(m);
p=head;
while
{
scanf('%d',&i);
p->data=i;
p->link=(test*)malloc(m);
q=p;
p=p->link;
}
q->link=NULL;
p=head;
while
{printf('%d',p->data);
p=p->link;
i++;
}
printf('
}
法二：
#include<stdio.h>
#include<stdlib.h>
typedef
lnode
int
void
{int
head=(struct
head->link=NULL;
q=head;
scanf('%d',&i);
while
{
p->link=NULL;
q->link=p;
q=p;
scanf('%d',&i);
}
p=head;
while
{printf('%d',p->data);
p=p->link;
i++;
}
printf('
}
4.
答：
#include<stdio.h>
#include<stdlib.h>
typedef
liuyu
int
int
void
void
int
int
void
{int
head=(test*)malloc(m);
p=head;
for(i=1;i<L;i++)
{
p->link=(test*)malloc(m);
p=p->link;
p->data=i+'a'-1;
p->link=NULL;
}
void
{p=head;
while
{
p=p->link;
printf('%c',p->data);
}
int
{p=head;
r=(test*)malloc(m);
r->data=X;
if(head->data==Y)
else{
L++;
return(0);
}
int
{
if(head->data==X){head=head->link;free(p);}
else{
{q=p;
if(p->data==X)
}
L--;
return(0);
}
void
{
display();
printf('insert
display();
printf('delete
display();
}
附：屏幕上显示的执行结果是：
a
insert
a
delete
a
4.
5.
6.
7.
8．
二、判断正误（在正确的说法后面打勾，反之打叉）（每小题1分，共10分）
（
答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。
（
（
（
错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。
（
错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”
（
错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。
（
错，线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。
（
错误。线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。
（
错误。顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍）
（
错，理由同7。链式存储就无需一致。
三、单项选择题（每小题1分，共10分）
（
（A）存储结构
（
（A）110
（
（A）
（B）
（C）
（D）
（
（A）8
（
（A）
（B）
（C）
（D）
（
（A）顺序
（
（A）必须是连续的
（C）一定是不连续的
（
（Ａ）需经常修改Ｌ中的结点值
（Ｃ）Ｌ中含有大量的结点
（
（Ａ）大于1；
（
| P0 |
3 |
4 |
|||||||
| P0 |
à |
a1 |
3 |
à |
a2 |
4 |
à |
A3 |
0 |
（Ａ）循环链表
四、简答题（每小题5分，共10分）
1.
答：①
优点：存储密度大（＝1？），存储空间利用率高。缺点：插入或删除元素时不方便。
②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。
顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。
若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
2
答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。
| head |
à |
data |
link |
简而言之，
头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；
头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针！！！）
首元素结点是指链表中存储线性表中第一个数据元素a1的结点。
五、【软考题】线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L={23，17，47，05，31}，若它以链接方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下所示：
| 05 |
U |
17 |
X |
23 |
V |
31 |
Y |
47 |
Z |
|
| ^ |
^ |
|||||||||
| 100 |
120 |
答：X=
六、阅读分析题（10分）
【严题集2.10②】指出以下算法中的错误和低效（即费时）之处，并将它改写为一个既正确又高效的算法。
答：错误有两处：
①
合法的入口参数条件为（0<i≤a.length）^
应将if
改为：if
第二个FOR语句中，元素前移的次序错误。应将for
改为for
七、编程题（每题10分，共40分）
解：输入：长度为n的线性表数组A(1:n)
输出：逆转后的长度为n的线性表数组A(1:n)。
C语言描述如下（其中ET为数据元素的类型）：
2.
3.
解：编写C程序如下(已上机通过)：
全局变量及函数提前说明：
---------------------------------
#include<stdio.h>
#include<stdlib.h>
typedef
text
int
void
{int
head=(test*)malloc(m);
p=head;
while
{
scanf('%d',&i);
p->data=i;
p->link=(test*)malloc(m);
q=p;
p=p->link;
}
q->link=NULL;
p=head;
while
{printf('%d',p->data);
p=p->link;
i++;
}
printf('
}
法二：
#include<stdio.h>
#include<stdlib.h>
typedef
lnode
int
void
{int
head=(struct
head->link=NULL;
q=head;
scanf('%d',&i);
while
{
p->link=NULL;
q->link=p;
q=p;
scanf('%d',&i);
}
p=head;
while
{printf('%d',p->data);
p=p->link;
i++;
}
printf('
}
4.
答：
#include<stdio.h>
#include<stdlib.h>
typedef
liuyu
int
int
void
void
int
int
void
{int
head=(test*)malloc(m);
p=head;
for(i=1;i<L;i++)
{
p->link=(test*)malloc(m);
p=p->link;
p->data=i+'a'-1;
p->link=NULL;
}
void
{p=head;
while
{
p=p->link;
printf('%c',p->data);
}
int
{p=head;
r=(test*)malloc(m);
r->data=X;
if(head->data==Y)
else{
L++;
return(0);
}
int
{
if(head->data==X){head=head->link;free(p);}
else{
{q=p;
if(p->data==X)
}
L--;
return(0);
}
void
{
display();
printf('insert
display();
printf('delete
display();
}
附：屏幕上显示的执行结果是：
a
insert
a
delete
a