第一部分习题答案

A x=Top->data;Top=Top->next B Top=Top->next;x=Top->data

C x=Top;Top=Top->next D x=Top->data

36.在一个链队中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为（ B ）

A f->next=c;f=s B r->next=s;r=s C s->next=r;r=s D s->next=f;f=s 37．链栈与顺序栈相比，有一个比较明显的优点即 （ B ）

A插入操作更方便 B 通常不会出现栈满的情况 C不会出现栈空的情况 D 删除操作更方便

38.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是 （ C ）

A e d c b a B d e c b a C d c e a b D a b c d e 39.一个队列的入队列顺序是1，2，3，4，则队列的输出系列是 （ B ）

A 4，3，2，1 B 1，2，3，4， C1，4，3，2 D 3，2，4，1 40．设计一个判别表达式中左、右括号是否配对的算法，采用（ B ）数据结构最佳。

A线性标的顺序存储结构 B栈C 队列 D 线性表的链式存储结构 41设循环队列中数组的下标范围是0—n-1，其头尾指针分别为f和r，则其元素的个数为（ D ）

A、r-f B、r-f +1 C、(r-f)%n+1 D、(r-f+n) %n

42若一个栈的输入序列是1、2??N，输出序列的第一个元素是N，则第I个输出元素为（C ）

A、N-I B、 I C、N-I+1 D、N-I-1

43队列操作的原则是（ A）

A先进先出B、后进先出C、只能进行插入D、只能进行删除

44线性表是( A ) 。

A 一个有限序列，可以为空； B 一个有限序列，不能为空； C 一个无限序列，可以为空； D 一个无序序列，不能为空。

二填空题、

1.以下为求单链表表长的运算，分析算法，请在____处填上正确的语句。 int length_linklist(linklist head) /*求表head的长度*/ {____p=head____;

j=0;

while(p->next)

{___p=p->next_____________; j++;}

return(j); /*回传表长*/ }该算法也可以写成:

int length_linklist(linklist head) /*求表head的长度*/ {p=head->next;

j=0;

while(p)

{p=p->next;

j++;}

return(j);比较一下,特别是初始化与循环条件.原题中是while(p->next)即若p有后继,则j加1,所以p的初始化为p=head

5

2.以下为单链表按序号查找的运算，分析算法，请在____处填上正确的语句。 linklist find_lklist(linklist head,int i)//查找第i个结点 { p=head;j=0;

while(_p&&(j

{ p=p->next; j++; } if(i==j) return(p); else return(NULL);

}

因为返回i结点的地址,所以函数类型为linklist,如果找到就不需要访问链表了,

所以应该是访问部分结点的这种情况,所以在循环条件中至少要有两个. 3.以下为单链表的定位运算，分析算法，请在____处填上正确的语句。 int locate_lklist(lklist head,datatype x)

/*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/ { p=head;j=0;

while(p->next&&p->next->data!=x){p=p->next;j++;} if ( p->next ) return( j+1 );

else return(0); }

这题也要注意处始化,p初值为head,即指向头结点的,所以是让*p的后继结点的数据域和x进行比较.若p的初值指向第一个结点,循环条件就发生了变化,具体算法为: int locate_lklist(lklist head,datatype x)

/*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/ { p=head->next;j=1;

while(p &&pdata!=x){p=p->next;j++;} if ( p ) return( j );

else return(0); }

这两个算法也要比较一下.在回顾一下我们上课所说采用链表编写算法的格式,这个格式一定要放在脑子中.

4.以下为单链表的删除运算，分析算法，请在____处填上正确的语句。 void delete_lklist(linklist head,int i)

{ p=find_lklist(head,i-1);//调用第2题

if(____p&&p->next_)//必须第i-1结点与第i结点存在 { q=__p->next___; p->next=q->next; free(q); }

else error(“不存在第i个结点”) }

5.以下为单链表的插入运算，分析算法，请在____处填上正确的语句。 void insert_lklist(linklist head,datatype x,int i) /*在表head的第I个位置上插入一个以x为值的新结点*/ { p=find_lklist(head,i-1);

if(p==NULL)error(“不存在第i个位置”)；

6

else {s=(linklist)malloc(sizeof(lnode));s->data=x; s->next=__p->next;__; p->next=s; } }

6.以下为单链表的建表算法，分析算法，请在____处填上正确的语句。 Linklist create_lklist1()

/*通过调用initiate_lklist和insert_lklist算法实现的建表算法。假定$是结束标志*/

{ ininiate_lklist(head);

i=1;

scanf(“%f”,&x);

while(x!=’$’)

{_ insert_lklist(head, x,int i)__; _____i++___________; scanf(“%f”,&x); }

return(head); }

改建表算法的时间复杂性约等于___O(N)_____。

7.以下为单链表的建表算法，分析算法，请在____处填上正确的语句。 linklist create_lklist2() /*直接实现的建表算法。*/

{ head=malloc(size); p=head;

scanf(“%f”,&x);

while(x!=’$’)

{ q=(linklist)malloc(sizeof(lnode)); q->data=x; p->next=q;

_____p=q;___________; scanf(“%f”,&x); }

______p->next=null__________;//让最后一个结点的指针域为空 return(head);

}

这题是从前往后建立单链表的与课本上算法2.11不一样,2.11是逆序建立的,大家把这两个算法对比一下.

8．循环链表与单链表的区别仅仅在于其尾结点的链域值不是空指针，而是一个指向__头结点_的指针。

9．在单链表中若在每个结点中增加一个指针域,所含指针指向前驱结点，这样构成的链表中有两个方向不同的链，称为双向链表。

10、一个好的算法应当具有下列好的特性：正确性、（可读性）、（ 健壮性 ）和效率和低存储需求。

11、算法的五个重要特征为（确定性 ）、（ 有穷性 ）、（ 可行性）和输入、输出。

2

7

12、采用顺序存储结构的线性表，其每个元素占用Ｌ个单元。第一个元素的地址为Ｎ，则第i个元素的存储位置为（ N+(i-1)*L ）。

13、数据元素之间的关系在计算机中的表示有两种不同的表示方法，即（顺序映像 ）和（非顺序映像 ），从而得到两种不同的存储结构（顺序存储结构 ）和（ 链式存储结构 ）。 14、已知栈的输入序列为1、2、3??n 输出序列为a1,a2??,an 符合a2=n的输出序列共有（ n-1 ）种。

15．带头结点的单链表H为空的条件是__H->nexy==NULL_______。 16非空单循环链表L中*p是尾结点的条件是_p->next==l__。

17．在一个单链表中p所指结点之后插入一个由指针s所指结点，应执行s->next=__p->next_;和p->next=__s___的操作。

18．在一个单链表中p所指结点之前插入一个由指针s所指结点，可执行以下操作：

s->next=___p->next___;

p->next=s;

t=p->data;

p->data=_s->data___;

s->data=__t____;

19．在顺序表中做插入操作时首先检查_是否溢出___ 三判断题

1 在顺序表中取出第i个元素所花费的时间与i成正比 不对,因为是可以随机存取.

2线性表的长度是线性表所占用的存储空间的大小 不对

3在对链队列作出队列操作，不会改变front指针的值 对

4双循环链表中，任一个结点的后继指针均指向其逻辑后继 不对,最后一个结点的后继指针不是指向其逻辑后继

5已知指针P指向链表L中某结点，执行语句P=P->next不会删除该链表中结点 对

6在链队列中，即便不设置尾指针也能进行入队列操作 对,但花费的时间较多

7栈和队列都是运算受限的线性表

对

8在带头结点的单循环链表中，任一结点的后继指针均不空

对

9线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间复杂度都是O(N)，因而两种存储方式的插入、删除运算所花费的时间相同 不对

四、算法设计

(算法大多数是习题集上的,大家参考习题集答案,如果哪道题,有什么问题,我再给出具体的分析和答案)

1． 设A=（a1,a2,a3,......an）和B=(b1,b2,.. .,bm)是两个线性表（假定所含数据元素均为整数）。若n=m且ai=bi(i=1,.. .,n),则称A=B;若ai=bi(i=1,.. .,j)且aj+1B。是编写一个比较A和B的算法，当AB是分别输出-1，

8

0或者1。

2．试编写在不带头结点的单链表上实现线性表基本运算LENGTH(L)的算法。

3．假设有两个按数据元素值递增有序排列的线性表A和B，均以单链表作存储结构。 编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列 的线性表C，并要求利用原表(即A表和B表的)结点空间存放表C。

4．设有线性表A=(a1,a2,.. .,am)和B=(b1,b2,.. .,bn).试写合并A、B为线性表C的算法，使得：

?(a1,b1,...,am,bm,bm?1,bn)当m??n;C=?

(a1,b1,...,an,bn,an?1,...,am)当m?n;?假设A、B均以单链表为存储结构(并且m、n显示保存)。要求C也以单链表为存储 结构并利用单链表A、B的结点空间。

5．已知单链表L中的结点是按值非递减有序排列的，试写一算法将值为x的结点插 大表L申，使得L仍然有序。

6，试分别以顺序表和单链表作存储结构，各写一个实现线性表的就地(即使用尽可

能少的附加空间)逆置的算法，在原表的存储空间内将线性表(a1，a2,.. .,an)逆置为(an,.. .,a2,a1)。

7．假设分别以两个元素值递增有序的线性表A、B表示两个集合(即统一线性表中的元素各不相同)，现要求构成一个新的线性表C，C表示集合A与B的交，且C中元素也递增有序。试分别以顺序表和单链表为存储结构，填写实现上述运算的算法。

8．假设在长度大于1的循环链表中，既无头结点也无头指针。s为指向链表中某个 结点的指针，试编写算法删除结点*s的前趋结点。

9．已知一单链表中的数据元素含有三个字符(即:字母字符、数字字符和其它字符)。试编写算法，构造三个循环链表，使每个循环链表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间(头结点可另辟空间)。

10、已知数据A[1。。K]中K个元素，另有一双向循环链表da，试以过程实现将数组中元素插入到da中第i个结点之后。

11、已给单链表的表头指针H和一个元素x，设计一个过程，实现：若x在单链表H中，则将x移到链尾；否则将x插入到链尾。

12．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不舌头指针），试编写相应的初始化队列、入队列和出队列算法。

13．假设以数组cycque[m](假设数组范围在0..m)存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队尾元素位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法。

14．假设一个算术表达式中可以包含三中括号：圆括号“（”和“）”，方括号“[”和“]”以及花括号与“{”和“}”，且这三种括号可按任意的次序嵌套试用，如（.. .[.. .{.. .}.. .[.. .].. .].. .( .. .[.. .].. .)。试利用栈的运算编写判断给定表达式中所含括号是否正确 配对出现的算法（可设表达式已存入字符型数组中）。 15．借助栈(可用栈的基本运算)来实现单链表的逆置运算。

16编写一个函数，从一给定的顺序表A中删除值在x~y(x<=y)之间的所有元素，要求以较高的效率来实现。

9