2. 分别编写在顺序表和带表头结点的单链表中删除其值等于x的所有元素的函数。 3. 编写在单链表中删除具有重复值的多余结点，使每个结点的值均不同的函数。
参考答案
一、单选题
1.B 2.A 3.C 4.C 5.A 6.C 7.B 8.D 9.A 10.C 11.B 12.B 13.A 14.D 15.C 16.B 17.A 18.A
二、填空题
1. 没有，1，没有，1 2. 序号 3. 长度，空表 4. 相同
5. 移动大量 6. 顺序存储结构，链式存储结构 7. 顺序表，线性链表 8. 移动，指针域
9. 移动，前一个结点 10. 头指针出发，链域逐个向下 11. p->next 12. p->next->next 13. p->next，q 14. 相同
15. 不相同 16. 前件，后件 17. 前件，后件 18. 运算统一
三、简答题
1. 答案：非空线性表的结构特征为： ① 有且只有一个根结点 a1 ,它无前件； ② 有且只有一个终端结点 an ,它无后件；
③ 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。 2. 答案：线性表的顺序存储结构具有如下两个基本特点： ① 线性表中所有元素所占的存储空间是连续的；
② 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
3. 答案：用一维数组存放线性表时，应注意数组的基本类型，要与线性表中数据元素的类型相同，而且该一维数组的长度，通常要定义得比线性表的实际长度大一些，以便对线性表进行各种运算。
4. 答案：线性表顺序存储结构的优点是：简单、存储密度大、空间利用率高，对表中任意元素可直接确定其存储地址，随机访问存取效率高。
缺点是，在顺序表中进行插入与删除操作时，需大量移动数据元素，时间开销大；再者，在顺序存储结构下，线性表的长度估计困难，并且当有多个顺序表同时共享计算机的存储空间时，不便于对存储空间进行动态分配。
5. 答案：假设数据结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。若每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点（即
11
前件或后件）。通过每个结点的指针域，将n个结点按其逻辑顺序连接在一起而构成的数据存储结构，称为链式存储结构。
6．答案：在带表头结点的单链表中进行查找操作，不能像在顺序表中那样根据序号直接访问表中的元素，而只能依据给定数据元素值item，在带表头结点的单链表中从头指针出发，沿着结点的链域逐个向下进行查找。若查找成功，则返回首次找到的结点的地址。若查找失败，则返回NULL。
7．答案：带表头结点的循环链表与前面所讨论的单链表相比具有以下两个特点： ① 循环链表的头结点的数据域为任意或者根据需要来设置，头结点的指针域指向线性表的第一个元素的结点（首结点）。头指针指向表头结点。
② 循环链表中最后一个结点的指针域不是NULL，而是指向表头结点。即在循环链表中，没有空指针，所有结点的指针构成了一个环状链。
四、算法设计
1. 算法由函数Count1( ) 和Count2( )所示：
// Count1( )从顺序表上统计出值为x的元素个数的算法
int Count1(SeqList &L,ElemType x ) //使用&的参数L为引用参数 { int i=0,j;
for(j=0;j
i++;
return i; }
// Count2从单链表上统计出值为x的元素个数的算法 int Count2(LinkList &H,ElemTtype x) {
node *p=H.head->next; //将指向第1个结点的指针赋给p int i=0; //将i作为统计变量 while(p!=NULL) {
if(p->data==x)
i++;
p=p->next; } return i; }
12
2. 算法由函数Delete1( )和Delete2( ) 所示：
//Delete1( )从顺序表中删除具有给定值x的所有元素
void Delete1(SeqList &L,ElemType x) { int j,i=0; while(i
if(L.list[i]==x) {
for(j=i+1;j
// Delete2( )从单链表中删除具有给定值x的所有元素 void Delete2(LinkList &H,ElemType x) {
node *q,*p=H.head; //将指向附加头结点的指针赋给p while(p->next!=NULL) {
q=p->next; if(q->data==x) {
p->next=q->next; //删除p 的后继结点，即q 结点 delete q; } else
p=p->next;
13
} }
3. 算法由Delete3( )所示：
// Delete3( )从单链表中删除具有重复值的多余结点，可使所有结点的值均不同
void Delete3(LinkList &H) {
node *p=H.head; //p链表的第1个结点 while(p!=NULL) {
node *t1=p,*t2=p->next; //t2指向待处理的结点 while(t2!=NULL) {
if(t2->data==p->data) //删除t2结点 {
t1->next=t2->next; delete t2;
t2=t1->next; //t2指向新的结点 } else { t1=t2;
t2=t2->next;
} }
p=p->next; //p指向下一个结点 } }
第4章 栈和队列
一、单选题
1.下列叙述中正确的是（ ）。
A）线性表是线性结构 B）栈与队列是非线性结构
14
C）线性链表是非线性结构 D）树是线性结构 2.下列关于栈的叙述中正确的是（ ）。
A）在栈中只能插入数据 B）在栈中只能删除数据 C）栈是先进先出的线性表 D）栈是先进后出的线性表 3.栈的插入和删除操作在（ ）进行。
A）栈顶 B）栈底 C）任意位置 D）指定位置
4.当利用大小为N的一维数组，顺序存储一个栈时，用top表示栈顶指针（指示器），用top==N表示栈空，则向这个栈插入一个元素时，首先应执行（ ）语句修改top指针。
A）top++; B）top--; C）top=0; D）top=N-1;
5. 利用数组a[N]顺序存储一个栈时，用top表示栈顶元素的下标位置，用top==-1表示栈空，用top==N-1表示栈满，则该数组所能存储栈的最大长度为（ ）。
A）N-1 B）N C）N+1 D）N+2
6. 利用数组a[N]顺序存储一个栈时，用top表示栈顶指针，用top==N+1表示栈空，则该数组所能存储栈的最大长度为为N，则表示栈满的条件为（ ）。
A）top==1; B）top==-1; C）top==0; D）top>1;
7. 利用数组a[N]顺序存储一个栈时，用top表示栈顶指针，用top==-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作是（ ）。
A）a[--top]=x; B）a[top--]=x; C）a[++top]=x; D）a[top++]=x;
8. 利用数组a[N]顺序存储一个栈时，用top表示栈顶指针，用top==-1表示栈空，并已知栈未空，当退栈并返回栈顶元素时所执行的操作是（ ）。
A）return a[--top]; B）return a[top--]; C）return a[++top]; D）return a[top++];
9. 假定一个链栈的栈顶指针用top表示，则该链栈为空的条件是（ ）。 A）top!=NULL; B）top==top->next; C）top==NULL; D）top!=top->next; 10.假定一个链栈的栈顶指针用top表示，每个结点的结构由一个数据域data和一个指针域组成，当p指向的结点进栈时，执行的操作为（ ）。
A）p->next=top;top=top->next; B）top=p;p->next=top;
C）p->next=top->next;top->next=p; D）p->next=top;top=p;
11.假定一个链栈的栈顶指针用top表示，每个结点的结构由一个数据域data和一个指针域组成，退栈时所执行的指针操作为（ ）。
A）p->next=top; B）top=top->data;
C）top=top->next; D）top->next=top->next->next;
12.若让元素1，2，3依次进栈，则出栈次数不可能出现（ ）的情况。 A）3，2，1 B）2，1，3 C）3，1，2 D）1，3，2
13.若让元素1，2，3，4依次进栈，则出栈次序不可能出现（ ）的情况。
15