计算机学院-课件数据结构-第三章 特殊线性表

第三章特殊线性表

一、选择题

1、设n个元素进栈序列是1,2,3…，n,其输出序列是PLP2,…,Pn,若Pl=3,则P2

可能的值是（）。

A.可能是2B.一定是2C.可能是1D.一定是1

2、循环队列的长度计算公式为()。

A.rear-frontB.(rear-front+MAXSIZE)%MAXSIZE

C.front-rparD.(front-rear+MAXSTZlt)%MAXST7E

3、设数组A[m]作为循环队列sq的存储空间，front为队头指针，rear为队尾指针,则执行

入队操作时修改指针的语句是()。

A.sq.rear=（sq.rear+l）%mB.sq.front=(sq.front+l)%(m+l)

C.sq.front=（sq.front+l）%mD.sq.rear=(sq.rear+l)%(m+l)

4、下面关于串的的叙述中，（)是不正确的。

A.串是字符的有限序列

B.串既可以采用顺序存储，也可以采用链式存储

C.模式匹配是串的一种重要运算

D.空串是由空格构成的申

5、设栈S和队列Q的初始状态为空，元素el,e2,e3,e4,e5和e6依次通过栈S,一个元

素出栈后即进队列Q若6个元素出队的序列是e2,e4,e3,e6,e5,el,则栈S的容量至

少应该是（）o

A.2B.3C.4D.6

6、在一个链队列中,假定front和rear分别为队首指针和队尾指针,则进行插入s所指向

结点的操作是（）。

A.rear->next=s;rear=s;B.front=front->next;

C.front->next=s;front=s;D.front=rear->next;

7、串是--种特殊的线性表,其特殊性体现在（）。

A.可以顺序存储B.数据元素可以是一个字符

C.可以链式存储D.数据元素可以是多个字符

8、栈和队列都是（）。

A.顺序存储的线性结构B.限制存取点的线性结构

C.链接存储的线性结构D.限制存取点的非线性结构

9、经过以下队列运算后，QueueEmpty（qu）的值是（）。

initQueue(qu)；enQueue(qu,a)：enQueue(qu,b)：deQueue(qu,x)；deQueue(qu,x)：

A.aB.bC.0I).1

10、串是（）°

A.一些符号构成的序列B.任意有限个字符构成的序列

C.一些字母构成的序列D.一个以上的字符构成的序列

11、六个元素按6、5、4、3、2、1的顺序进栈，则（）不是合法的出栈序列。

A.453126B.346521

C.543612D.234156

12、一个栈的入栈序列是a、b、c、d、e,则栈的输出序列不可能是（）o

A.dceabB.decbaC.edcbaD.abcde

13、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾

指针，则判断队列为空的条件是()。

A.front==rear+lB.front==rearC.front+l==rearD.front==0

14、设栈S和队列Q的初始状态为空，元素el,e2,e3,e4,e5和e6依次通过栈S,一个

元素出栈后即进队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,el,则栈S的容

量至少应该是()。

A.2B.3C.4D.6

15、设有两个串p和q,具中q是p的子串，求q在p中首次出现的位置的算法称为()。

A.求子串B.串联接C.模式匹配【).求串长

16、若进栈序列为1,2,3,4,则不可能得到的出栈序列是()。

A.3,2,1,4B.3,2,4,1C.2,3,4,1D.4,2,3,1

17、若用一个大小为m的数组来实现循环队列，用front和rear分别表示队头和队尾，则

当前队列中的元素数是()。

A.rear-front-1B.rear-front+1C.(rear-front+m)%mD.rear-front

18、若用一个大小为6的数组来实现循环队列，队头指针front指向队头元素，队尾指针rear

指向队尾元素的下一个位置"若当前rear和front的值分别为0和3,当从队列中删除两个

元素，再加入两个元素后，rear和front的值分别为()。

A.1和5B.2和5

C.4和2D.5和1

19、设有两个串p和q,其中q是p的子串，求q在P中首次出现的位置的算法称为()。

A.求子串B.匹配C.联接D.求串长

20、设有一顺序栈，元素a、b、c、d、e、f依次进栈，若6个元素出栈的顺序是b、d、c、

f、e、a,则栈的容量至少应该是()o

A.2B.3C.5D.6

21、设数组ALm」作为循环队列sq的存储空间,front为队头指针，rear为队尾指针，则执

行入队操作时修改指针的语句是()。

A.sq.front=(sq.front+l)%mB.sq.front=(sq.front+l)%(m+l)

C.sq.rear=(sq.rear+l)%mD.sq.rear=(sq.rear+l)%(m+l)

22、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾

指针，则判断队列为空的条件是()。

A.front==rear+lB.front==rear

C.front+l=rearD.front==0

23、经过以下队列运算后，QueueEmply(qu)的值是().

initQueue(qu)；enQueue(qu,a)；enQueue(qu,b)；deQueue(qu,x)：deQueue(qu,x)；

A.aB.bC.0D.1

24、设已将元素a1、a?、@3依次入栈，元素正等待入栈。那么下列4个序列中不可能出

现的出栈序列是()。

A.43、—4、82B.—3、32、—4、ai

C.93'34%己2、31D.己4、d3、d2>81

25、假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear,则当前队列

中的元素个数为()。

A.(rear-front)%mB.rear-front+1

C.（front-rear+m）%mD.（rear-front+m）%m

26、六个元素按6、5、4、3、2、1的顺序进栈，则（）不是合法的出栈序列。

A.346521B.453126C.543612I）.234156

27、若用一个大小为6的数组来实现循环队列，队头指针front指向队头元素，队尾指针

rear指向队尾元素的下一个位置。若当前rear和front的值分别为0和3,当从队列中删

除两个元素，再加入两个元素后，rear和front的值分别为（）。

A.2和5B.1和5C.4和2D.5和1

28、设计一个判别表达式中左、右括号是否配对出现的算法，采用（）数据结构最佳。

A.线性表的顺序存储结构B.栈

C.线性表的链式存储结构D.队列

29、在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入s所指

向结点的操作是（）。

A.front->next=s;front=s;B.front=front->next;

C.rear->next=s;rear=s;D.front=rear->next;

30、用链表作为栈的存储结构则退栈操作（）。

A.必须判别栈是否为满B.必须判别栈是否为空

C.判别栈元素的类型D.对栈不作任何判别

31、一个栈的输入序列为12345,则下列序列中不可能是栈的输出序列的是（）,

A.54132B.23415C.23145D.15432

32、若循环队列的队头指针为front,队尾指针为rear,则队长的计算公式为（）。

A.rear-frontB.front-rearC.rear-front+1D.都不正确

33、栈和队列都是（）。

A.顺序存储的线性结构B.限制存取点的线性结构

C.链接存储的线性结构D.限制存取点的非线性结构

34、串是（）。

A.一些符号构成的序列B.任意有限个字符构成的序列

C.一些字母构成的序列【）.一个以上的字符构成的序列

35、设已将元素aI、a2,a3依次入栈，元素正等待入栈。那么下列4个序列中不可能出

现的出栈序列是（）。

A.83>8i>a<j、32B.83、32>己4、81C.33>己4、32>81D>34>合3、①、81

36、一个栈的输入序列为12345,则下列序列中不可能是栈的输出序列的是（）。

A.54132B.23415C.23145D.15432

37.若循环队列的队头指针为front,队尾指针为rear,则队长的计算公式为（

A.rear-frontB.frort-rearC.rear-front+1D.都不正确

37、下面关于串的的叙述中，（）是不正确的。

A.空串是由空格构成的串

B.串可以顺序存储

C.模式匹配是串的一种重要运算

D.串可以链式存储

38、设已将元素a1、a?、a3依次入栈，元素正等待入栈。那么下列4个序列中不可能出

现的出栈序列是（）。

A.—3、己1、34>32B.-3、-2、己4、31

C.a?、84>a2、8iD.24、a?、a2、3i

39、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指

针，则判断队列为空的条件是（）o

A.front==rear+lB.front==rearC.front+l==rearD.front==0

40、串是〜种特殊的线性表，其特殊性体现在（）o

A.可以顺序存储B.数据元素可以是一个字符

C.可以链式存储D.数据元素可以是多个字符

41、设计一个判别表达式中左、右括号是否配对出现的算法，采用（）数据结构最佳。

A.线性表的顺序存储结构B.栈

C.线性表的链式存储结构D.队列

42、若用一个大小为6的数组来实现循环队列，队头指针front指向队头元素，队尾指针rear

指向队尾元素的下一个位置。若当前rear和front的值分别为。和3,当从队列中删除两个

元素,再加入两个元素后，rear和front的值分别为（）。

A.2和5B.1和5C.4和2D.5和1

43、若进栈序列为1,234,则不可能得到的出栈序列是（）。

A.3,2,1,4B.3,2,44

C.2,3,4,1D.4,2,34

44、设栈5和队列Q的初始状态为空，元素el,e2,e3,e4,e5和e6依次通过找S,一个

元素出栈后即进队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,el,则板S的容

量至少应该是（）。

A.2B.3C.4D.6

45、设有一顺序栈，元素a、b、c、d、e、f依次进栈，若6个元素出栈的顺序是b、d、c、

f、e、a,则栈的容量至少应该是（

A.2B.5C.3D.6

46、在一个链队列中，假定front和rear■分别为队首指针和队尾指针，则进行插入s所指向

结点的操作是（）。

A.rear->next=s;rear=s;B.front=front->next;

C.front->next=s;front=s;D.front=rear->next;

47、下面关于串的的叙述中，（）是不正确的。

A.串可以顺序存储B.空串是由空格构成的串

C.模式匹配是市的一种重要运算D.串可以链式存储

48、栈和队列都是（）。

A.顺序存储的线性结构B.限制存取点的线性结构

C.链接存储的线性结构D.限制存取点的非线性结构

49、设n个元素进栈序列是1,2,3,n,其输出序列是Pl，P2，…，Pn，若Pl=3,则P2

可能的值是（）。

A.可能是1B.一定是2

C.可能是2D.一定是1

50、若用一个大小为6的数组来实现循环队列，队头指针front指向队头元素，队尾指针rear

指向队尾元素的下一个位置。若当前rear和front的值分别为。和3,当从队列中删除两个

元素,再加入两个元素后，rear和front的值分别为（）。

A.1和5B.2和5

C.4和2D.5和1

51、设有两个串p和q,其中q是p的子串，求q在p中首次出现的位置的算法称为()。

A.匹配B.联接

C.求子串D.求串长

52、若进栈序列为1,2,3,4,则不可能得到的出栈序列是(

A.3,2,1,4B.3,2,4」C.4,2,3,1D.2,3,4,1

53、循环队列的长度计算公式为()。

A.(rear-front+MAXSIZE)%MAXSIZE

B.rear-front

C.front-rear

D.(front-rear+MAXSIZE)%MAXSIZE

54、串是一种特殊的线性表，其特殊性体现在()。

A.可以顺序存储

B.数据元素可以是多个字符

C.可以链式存储

D.数据元素可以是一个字符

55、栈和队列共同的特点是()。

A.先进先出B.先进后出

C.后进先出D.仅在表的一端进行插入、删除操作

56、设数组A[m]作为循环队列sq的存储空间，front为队头指针，rear为队尾指针,则执行

入队操作时修改指针的语句是(

A.sq.rear=(sq.rear+1)%m

B.sq.front=(sq.front+l)%(m+l)

C.sq.front=(sq.front+l)%m

D.sq.rear=(sq.rear+l)%(m+l)

57、六个元素按6、5、4、3、2、1的顺序进栈，则()不是合法的出栈序列。

A.453126B.346521

C.543612D.234156

58、假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear,则当前队列中

的元素个数为()。

A.(rear-front)%m

B.rear-front+1

C.(rear-front+m)%m

D.(front-rear+m)%m

59、设有两个串p和q,其中q是p的子串，求q在p中首次出现的位置的算法称为()。

A.匹配B.求子串

C.联接D.求串长

二、判断题

1、引入循环队列的目的是为了克服假溢出时大量移动数据元素。

2、若一个栈的输入序列为1,2,3,则3,1,2是不可能的栈输出序列。

3、串的模式匹配是一种定位操作。

4、栈是限定仅在表尾进行插入和删除操作的线性表。

5、表达式求值是队列应用的一个典型例子。

6、区分循环队列的满与空，有牺牲一个存储单元和设标记两种方法。

7、栈是可以在表尾和表头进行插入和删除操作的线性表。

8、循环队列也存在空间溢出的问题。

9、栈也是一种线性表，只是在插入和删除时受到一些限制。

10、栈是一种特殊的线性表。

11、队列的特点是先进不一定先出。

12、区分循环队列的满与空，有牺牲一个存储单元和设标记两种方法。

13、循环队列也存在空间溢出的问题。

14、串的模式匹配是一种定位操作。

15栈是可以在表尾和表头进行插入和删除操作的线性表。

16、表达式求值是队列应用的一个典型例子。

”、栈也是一种线性表，只是在插入和删除时受到一些限制。

18、设用链表作为栈的存储结构则出栈操作，不需对栈作任何判别。

19、引入循环队列的目的是为了克服假溢出时大量移动数据元素。

20、区分循环队列的满与空，有牺牲一个存储单元和设标记两种方法。

21、若一个栈的输入序列为1,2,3,则3,1,2是不可能的栈输出序列。

22、空串就是空格串。

23、栈操作的特点是先进先出。

24、表达式求值是队列应用的一个典型例子。

25、串的模式匹配是一种定位操作。

26、栈是可以在表尾和表头进行插入和删除操作的线性表。

三、应用题

1、设有编号为123,4,5的五辆列车顺序进入一个栈式结构的站台，已知最先开出车站的前

两辆车的编号依次为3和4,请写出这五辆列车开出车站的所有可能的顺序。

2、设有编号为123,4,5的五辆列车顺序进入一个栈式结构的站台，已知最先开出车站的前

两辆车的编号依次为3和4,请写出这五辆列车开出车站的所有可能的顺序。

3、设有编号为1,2,3,4,5的五辆列车顺序进入一个栈式结构的站台，已知最先开出车站的前

两辆车的编号依次为3和4,请写出这五辆列车开出车站的所有可能的顺序。

4、设有编号为1,234,5的五辆列车顺序进入一个栈式结构的站台，已知最先开出车站的前

两辆车的编号依次为3和4,请写出这五辆列车开出车站的所有可能的顺序。

5、设有编号为123,4,5的五辆列车顺序进入一个栈式结构的站台，己知最先开出车站的前

两辆车的编号依次为3和4,请写出这五辆列车开出车站的所有可能的顺序。

四、程序填空题

1、已知压栈函数intpush(sqstack*S,ElemTypex),

弹栈函数intpop(sqstack*S,ElemType*e),

初始化栈函数voidinitstack(sqstack*S),

判栈空函数intempty(sqstackS)。

以下算法是将任意一个十进制整数m转换为n(2W〃49)进制数输出，请填空。

jzzh(intm,intn)/*将十进制整数m转换为n(2<n<9)进制数*/

inte;

sqstackS;

initstack(&S);

while(m!=0)

(①

②

}

while(!empty(S))

(③

printfe);}

)

2、以下是循环队列的出队操作，请填空。

#defineMAXSIZE100/*队列存储空间大小*/

typedefintElemType;

typedcfstruct

{ElemType*base;/*队列存储空间基地址*/

intfront;/*队头指针*/

intrear;/*队尾指针*/

}cqucuc;

intoutqueue(cqueue*cq,ElemType*x)

/*出队列*/

(

if(①)

return(0);/*失败，返回0*/

*x=®;

cq->front=®;

return(l);/*成功，返回1*/

3、以下程序分别是顺序栈的入栈和出栈操作，请填空。

^defineINITSIZE100/*存储空间的初始分配量*/

typedefintElemType;/*在实际应用中，根据需要定义所需的数据类型*/

typedefstruct

{inttop;/*栈顶指针,初始top=0*/

ElemType*base;/*存储空间基地址*/

intstacksize;/*栈总存储空间大小*/

}sqstack;

intpush(sqstack*S,ElemTypex)

if(S->top>=S->stacksize)

{S">base=(ElemType*)realloc(S->base,(S->stacksize+l)*sizeof(ElemType));

if(!S->base)return0;

®

)

②

return1;

)

intpop(sqstack*S,ElemType*e)

if(S->top==0)/*栈空*/

return0;

③_______________；

return1;

}

4、下面是循环队列的判队空和取队头元素操作的算法，请填空。

^defineMAXCSIZE100

typedefintElemType;

Typedefstruct

{ElemType*base;/*存放一维数组的基址比/

intfront;/*队头指针，指示队头元素下标*/

intrear;/*队尾指针，指示队尾元素后一位置*/

}cqueue;

intempty(cqueuecq)

/*队空返回1,否则返回0*/

{

return;

)

intgetfront(cqueuecq.ElemType*x)

/*取队头操作，成功返回1,失败返回0*/

(

if(@)

return0;

else

{*x=③；

return1;

)

)

5、以下程序分别是链栈的入栈和出栈操作，栈顶在表头即头结点之后，请填空。

typedefintElemType;

typedefstructnode链栈结点结构*/

{ElemTypedata;

structnode*ncxt;

}linkstack,slink;

intpush(linkstack*S,ElemTypex)/*入栈操作(将值为x的数据元素插入栈S中，使x成为

新的栈顶元素)*/

{linkstack*p;

p=(linkstack*)malloc(sizcof(linkstack));

if(!p)return0;

p->data=x;

①；

②；

returnI;

intpop(linkstack*S,ElemType*e)/*出栈操作(删除栈S的栈顶元素)*/

{linkstack*p;

if(S->ncxt==NL)LL)return0;

p=S->next;

*c=p->data;

③；

free(p);

return1;

I

6、以卜.是循环队列的一些基本操作，请填空。

#defineMAXCSIZE100/*队列存储空间大小*/

typedefintElcmTypc;

lypedefstruct

{ElemType*base;/*队列存储空间基地址*/

intfront;/*队头指针*/

intrear;/*队尾指针*/

}cqucuc;

/*求队列长操作(循环队列中数据元素的个数)*/

intgctlcn(cqucuc*cq)

{return(__________Ql_________);

)

/*入队列操作(在循环队列cq的队尾插入值为x的元素)*/

intenqueue(cqueue*cq,ElemTypex)

{if(②)return0;

cq->base[cq->rear]=x;

_________©__________；

returnI;

)

7、以下程序是顺序栈的求栈长、取栈顶、判栈空算法，请填空。

/*顺序栈存储结构*/

^defineINITSIZE100/*存储空间的初始分配最*/

typedefintElemType;/*在实际应用中，根据需要定义所需的数据类型*/

typedefstruct

{inttop;

ElemType*base;

intstacksize;

Jsqstack;

intgetlen(sqstack*S)/*求栈长操作*/

{return(®);}

intgettop(sqstack*S，日emType*e)/*取栈顶元素操作*/

{if(S->top==0)return0;/*栈空,返回0*/

*e=S->base[②];

return1;/*取栈顶元素*/

)

emptystack(sqstack*S)/*判栈空操作*/

{if(③)/*栈空，返回1,否则返回0*/

return1;

elsereturn0;

)

8、以下是循环队列的一些基本操作，请填空。

#defineMAXCSIZE100六队列存储空间大小*/

typedefintElcniType;

typedefstruct

{ElcmTypc*basc;/*队列存储空间基地址*/

intfront;/*队头指针*/

intrear;/*队尾指针*/

}cqueue;

/*求队列长操作(循环队列中数据元素的个数)*/

intgetlen(cqueue*cq)

(return1①);

)

/*入队列操作(在循环队列cq的队尾插入值为x的元素)*/

intcnqucuc(cqucuc*cq,ElcmTypcx)

{if(⑧)return0;

cq->base[cq->rear]=x;

_________©__________；

return1;

)

9、已知压栈困数intpush(sqstack*5,ElemTypex),

弹栈函数intpop(sqstack*S,ElemType*e),

初始化栈函数voidinitstack(sqstack*S),

判栈空函数intempty(sqstackS)。

以下算法是将任意一个十进制整数m转换为n(2W〃《9)进制数输出，请填空。

jzzh(intm,intn)/*将十进制整数m转换为n(2<n<9)进制数*/

{inte;

sqstackS;

initstack(&S);

while(m!=0)

(①；

②_________；

)

while(!empty(S))

{③；

printfe);}

)

10、以下程序分别是顺序栈的入栈和出栈操作，请填空。

[defineINITSIZE100/*存储空间的初始分配量*/

typedefintElemType;/*在实际应用中，根据需要定义所需的数据类型*/

typcdefstruct

{intlop;/*栈顶指针，初始top=0*/

ElemType*base;/*存储空间基地址*/

intstacksize;/*栈总存储空间大小*/

}sqstack;

intpush(sqstack*S,ElemTypex)

(

if(S->top>=S->stacksizc)

{S->base=(E1emType*)realloc(S->base,(S->stacksize+l)*sizeof(ElemType));

if(!S->base)return0;

①________________；

)

②________________；

return1;

}

intpop(sqstackElemType*e)

{

if(S->top=0)/*栈空*/

return0;

③____________；

return1;

}

11、如果希望循环队列中的向量单元都能得到利用，则可设置一个标志域tag,每当尾指针

和头指针值相同时，以tag的值为0或1来区分队列状态是“空”还是“满北请对下列函

数填空，使其分别实现与此结构相应的入队和出队的算法。

^defineMAXSIZE100

typedefintElemType;

typedefstruct

{ElemType*basc;/*队列元素基地址*/

intfront;/*队头指针*/

intrear;/*队尾指针*/

Jcqueue;

inttag;/*标志域tag*/

intenqueue(cqucuc*q,ElemTypex)

{if(ffi)return0;

q->data[q->rcar]=x;

q->rear=(q->rear+l)%MAXSIZE;

if(q->rear==q->front)②;

return1;

)

intdequeue(cqueue*q,ElemType*x)

{if(