数据结构试题集(包含答案-).doc

第一章　概论
一、选择题
1、研究数据结构就就是研究（ Ｄ )。
A、　数据得逻辑结构 B、 数据得存储结构　
C、 数据得逻辑结构与存储结构　 ﻩD、 数据得逻辑结构、存储结构及其基本操作
2、算法分析得两个主要方面就是( Ａ ）.
A、 空间复杂度与时间复杂度ﻩﻩ B、 正确性与简单性ﻩ C、　可读性与文档性　 　　 Ｄ、 数据复杂性与程序复杂性
３、具有线性结构得数据结构就是（ D　)。
A、　图 　 B、 树 C、 广义表 Ｄ、 栈
4、计算机中得算法指得就是解决某一个问题得有限运算序列，它必须具备输入、输出、（ B )等5个特性.
A、 可执行性、可移植性与可扩充性ﻩ B、 可执行性、有穷性与确定性ﻩﻩ
C、 确定性、有穷性与稳定性 ﻩ 　 　D、 易读性、稳定性与确定性
5、下面程序段得时间复杂度就是( C　）。
ﻩfor（i=0;i〈m;i＋+）
ﻩ for(j＝0;j<n;ｊ＋＋）
ﻩa［i]［ｊ]=i＊j；
Ａ、 O（ｍ2） ﻩﻩ B、 Ｏ（n2）ﻩ Ｃ、 Ｏ（m＊n） ﻩﻩＤ、 O（m＋n）
６、算法就是( D ）。
A、　计算机程序 ﻩB、　解决问题得计算方法ﻩﻩ C、 排序算法 ﻩﻩＤ、 解决问题得有限运算序列
7、某算法得语句执行频度为（３n+ｎloｇ2n+n2+8）,其时间复杂度表示（ C ）。
A、 O(n）ﻩ 　 Ｂ、 O（ｎlog2n) C、 O（n2) 　 ﻩ Ｄ、 O（ｌｏｇ2ｎ)
8、下面程序段得时间复杂度为( 　C )。
ﻩi=１；
ｗhile（i〈=n）
ﻩﻩi=ｉ＊３；
A、 Ｏ(n） ﻩ ﻩB、 O（3n) ﻩ C、　O(ｌｏg3n） ﻩ 　 Ｄ、 O（ｎ3）
９、数据结构就是一门研究非数值计算得程序设计问题中计算机得数据元素以及它们之间得（ )与运算等得学科。
A、　结构 ﻩＢ、 关系ﻩﻩC、 运算 ﻩD、 算法
10、下面程序段得时间复杂度就是（A　 ).
ﻩi＝s=０；
ﻩwhilｅ（ｓ〈ｎ){
ｉ+＋;s+=ｉ；
｝
A、　O(n)　 　 ﻩﻩB、 Ｏ（ｎ2） ﻩ Ｃ、 O(log2n）ﻩﻩ D、 O（n3）
11、抽象数据类型得三个组成部分分别为( A)。
Ａ、 数据对象、数据关系与基本操作ﻩﻩ ﻩB、 数据元素、逻辑结构与存储结构 ﻩ
C、 数据项、数据元素与数据类型ﻩ Ｄ、 数据元素、数据结构与数据类型
1２、通常从正确性、易读性、健壮性、高效性等4个方面评价算法得质量，以下解释错误得就是（　 　）.
ﻩA、 正确性算法应能正确地实现预定得功能ﻩﻩ
ﻩＢ、 易读性算法应易于阅读与理解,以便调试、修改与扩充
ﻩＣ、 健壮性当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要得运行结果
ﻩD、 高效性即达到所需要得时间性能
13、下列程序段得时间复杂度为（Ｂ 　）。
x=ｎ；y＝0；
while(ｘ〉=（y＋1)＊（ｙ+１）)
ﻩｙ=y+１；
A、 O(n) 　 B、 C、 O（１)ﻩ D、 Ｏ(n2)
二、填空题
１、程序段“i＝１；wｈile(i<＝n） ｉ=i*２;”得时间复杂度为 　　　 　 。
２、数据结构得四种基本类型中，　 　　 树形结构 　 　得元素就是一对多关系.
三、综合题
1、将数量级O(1)，Ｏ（N），O（N2),O（N3）,O（NLＯＧ2N),Ｏ(LOG２N），O(2Ｎ)按增长率由小到大排序。
答案：　 O（1) O（loｇ2Ｎ)　　Ｏ（Ｎ) O(Ｎｌｏg２N) O（Ｎ2)　　O(N3) O(2N）
第二章 线性表
一、选择题
1、若长度为ｎ得线性表采用顺序存储结构，在其第ｉ个位置插入一个新元素算法得时间复杂度（ 　 )。
A、　O(lｏg2ｎ）　 B、O(１)ﻩ ﻩC、 O（n）ﻩﻩ 　 　D、O（ｎ2)
2、若一个线性表中最常用得操作就是取第i个元素与找第i个元素得前趋元素，则采用( 　)存储方式最节省时间。
A、 顺序表　　 　 ﻩＢ、 单链表ﻩ Ｃ、 　双链表　　 　 　ﻩＤ、　单循环链表
3、具有线性结构得数据结构就是( 　 ）。
A、 图 ﻩﻩB、 树ﻩ Ｃ、 广义表　 ﻩD、 栈
4、在一个长度为n得顺序表中，在第i个元素之前插入一个新元素时,需向后移动（ )个元素。
A、 n－i　 Ｂ、　n—ｉ＋1ﻩﻩ Ｃ、　n—i—1ﻩ 　 D、 ｉ
5、非空得循环单链表head得尾结点p满足（ )。
A、 p->neｘt==head　　 　 ﻩB、　p—>next==ＮULL
C、 p==NＵLL　 　 ﻩ D、 p==head
6、链表不具有得特点就是(　　 ).
A、 可随机访问任一元素 B、 插入删除不需要移动元素ﻩ
C、 不必事先估计存储空间ﻩ ﻩＤ、 所需空间与线性表长度成正比
7、在双向循环链表中，在ｐ指针所指得结点后插入一个指针q所指向得新结点，修改指针得操作就是（ 　）。
A、 p—＞ｎeｘt=q；q—>prior=ｐ;p—>next-＞pｒioｒ=q；q-〉nｅxｔ=q;
B、 p－〉neｘｔ=q；p-＞neｘt->ｐｒior＝q；q—＞ｐrior＝p；q->next＝p->ｎｅxt；ﻩ
C、 q-＞prior=p;ｑ－>ｎext=p->nｅxt;p-〉ｎexｔ-〉prｉoｒ=q;p—＞next=q；ﻩ
D、 q—〉next=p－>neｘt；q->prior=p；p-＞nｅｘｔ=ｑ；p－〉ｎext＝q；
8、线性表采用链式存储时,结点得存储地址（　 　)。
A、 必须就是连续得 B、 必须就是不连续得ﻩ
C、 连续与否均可ﻩ 　 　D、 与头结点得存储地址相连续
9、在一个长度为n得顺序表中删除第ｉ个元素，需要向前移动（ 　　)个元素。
A、 n-i ﻩﻩﻩB、 n－ｉ+1 ﻩC、　n-i－１ﻩ 　ﻩＤ、 i+1
1０、线性表就是ｎ个（　 ）得有限序列。
A、　表元素 ﻩ B、 字符ﻩﻩﻩ C、 数据元素 ﻩD、　数据项
11、从表中任一结点出发,都能扫描整个表得就是（ )。
A、　单链表 　　 B、 顺序表ﻩﻩ Ｃ、 循环链表ﻩﻩ D、 静态链表
12、在具有n个结点得单链表上查找值为x得元素时，其时间复杂度为( )。
A、 O（n) ﻩ B、 O（1) 　 ﻩ C、　O(n2） 　　 ﻩD、　O(ｎ－１）
13、线性表L=（a1,a2，……，aｎ)，下列说法正确得就是（ 　）.
Ａ、 每个元素都有一个直接前驱与一个直接后继　 ﻩ
B、 线性表中至少要有一个元素
C、　表中诸元素得排列顺序必须就是由小到大或由大到小
Ｄ、 除第一个与最后一个元素外，其余每个元素都由一个且仅有一个直接前驱与直接后继
14、一个顺序表得第一个元素得存储地址就是９0，每个元素得长度为２,则第６个元素得存储地址就是( ）。
Ａ、 ９8 　 ﻩＢ、 １0０ﻩ C、　１02 Ｄ、　106
15、在线性表得下列存储结构中，读取元素花费得时间最少得就是( ）.
A、 单链表 　 B、 双链表ﻩ C、 循环链表 　 　　 D、 顺序表
１6、在一个单链表中,若删除ｐ所指向结点得后续结点，则执行（ 　 ).
Ａ、　p－>next=ｐ—>nexｔ—>next；
Ｂ、　p＝p—〉next；p-＞nｅxt=p->next->ｎｅxt；
Ｃ、　p =p—＞ｎexｔ;
D、　p＝p—>next－〉nexｔ;
1７、将长度为n得单链表连接在长度为m得单链表之后得算法得时间复杂度为( )。
A、　Ｏ（１)ﻩﻩB、　Ｏ（ｎ） ﻩC、　Ｏ（m)ﻩﻩＤ、 O（m＋n）
１８、线性表得顺序存储结构就是一种（ 　 )存储结构。
Ａ、　随机存取ﻩﻩB、　顺序存取ﻩﻩC、 索引存取ﻩ D、　散列存取ﻩﻩ
19、顺序表中,插入一个元素所需移动得元素平均数就是( )。
　 A、　（n—1）/2　　 　 Ｂ、　n 　 C、 ｎ+１ D、 (ｎ+1）/2
10、循环链表得主要优点就是（　 ）。
A、　不再需要头指针　 　 B、　已知某结点位置后能容易找到其直接前驱　
Ｃ、　在进行插入、删除运算时能保证链表不断开
D、　在表中任一结点出发都能扫描整个链表ﻩ
11、不带头结点得单链表heaｄ为空得判定条件就是( A　 ）。
A、 hｅad＝=NULL 　 　 　　 ﻩ ﻩＢ、 head—〉neｘｔ==NULL ﻩ
C、 heａd—＞ｎext=＝heaｄ 　 　 　　　 ﻩ ﻩ D、　ｈｅａd！=NＵLL
答案B就是带头结点得
12、在下列对顺序表进行得操作中,算法时间复杂度为O(1)得就是（ )。
ﻩＡ、 访问第i个元素得前驱（1〈） ﻩＢ、　在第i个元素之后插入一个新元素（）
Ｃ、 删除第i个元素（） ﻩ ﻩD、 对顺序表中元素进行排序
答案就是Ａ、
假设顺序表L，长度为n,求第i个节点L［i],直接前驱L[i—1]，因此为O（1）
答案Ｂ需要移动n-ｉ＋1个节点，因此为O（n）
答案C也需要移动n-ｉ个节点
答案D根据排序方法不同最慢O(ｎ^２)，最快Ｏ（ｎlogｎ)
1３、已知指针p与q分别指向某单链表中第一个结点与最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行得语句为( 　)。
A、 ｑ－〉nｅxt=s—〉ｎext；s-＞nｅxt=ｐ；ﻩ
B、 s-〉nexｔ=p；q->next＝s-＞ｎext; 　 　ﻩ ﻩ
C、 p-＞ｎexｔ=ｓ-＞ｎｅxt；s—>ｎeｘt＝ｑ; ﻩ ﻩ
D、 s—>nｅxt=q;ｐ—〉neｘt=ｓ—>nｅxt;
14、在以下得叙述中,正确得就是（ ).
ﻩA、　线性表得顺序存储结构优于链表存储结构
B、　线性表得顺序存储结构适用于频繁插入／删除数据元素得情况
ﻩC、 线性表得链表存储结构适用于频繁插入／删除数据元素得情况
D、 线性表得链表存储结构优于顺序存储结构
15、在表长为n得顺序表中，当在任何位置删除一个元素得概率相同时，删除一个元素所需移动得平均个数为（ 　 )。
A、 (n—1）/2 　 　 ﻩB、　n/２ﻩ C、 (n+1）/2 ﻩD、 ｎ
１6、在一个单链表中,已知q所指结点就是p所指结点得前驱结点,若在ｑ与p之间插入一个结点s，则执行（　 )。
A、 s—>nｅxt=p-＞nｅxｔ; ｐ->next=s；　　 　 　
B、 ｐ-＞next=s-＞ｎｅｘt;s->ｎext=ｐ； 　ﻩ
C、　q—〉nｅｘt=ｓ;s—〉nｅxt=p； ﻩ 　 　 ﻩ
D、 p－>ｎext=ｓ；s－〉ｎexｔ=q;
1７、在单链表中,指针p指向元素为ｘ得结点，实现删除x得后继得语句就是（ 　 ）。
A、 p=p-＞nｅxt;　　 　 B、　p—>next=p—>ｎext->nｅxt; 　　 ﻩ
C、　p－〉nｅxｔ=p; ﻩ Ｄ、 p=p－>nexｔ—〉next；
1８、在头指针为head且表长大于１得单循环链表中，指针p指向表中某个结点，若p-＞ｎext—〉ｎeｘｔ＝＝ｈead，则( ）.
A、 p指向头结点 ﻩﻩＢ、 p指向尾结点ﻩ ﻩC、 p得直接后继就是头结点
Ｄ、 ｐ得直接后继就是尾结点
二、填空题
1、设单链表得结点结构为（ｄａtａ，next）。已知指针p指向单链表中得结点，q指向新结点，欲将q插入到p结点之后，则需要执行得语句：　 　 　 　　 　　 ； 　 　 。
答案:ｑ-＞next=ｐ—＞ｎｅxt ﻩp->nｅｘt=q
2、线性表得逻辑结构就是 　 ,其所含元素得个数称为线性表得　 　 　 .
答案：线性结构 长度
3、写出带头结点得双向循环链表L为空表得条件 　 　 　 。
答案：L—〉prｉoｒ==L—〉neｘt=＝L
4、带头结点得单链表ｈead为空得条件就是 　。
答案:hｅaｄ-＞nexｔ＝＝NULL
5、在一个单链表中删除p所指结点得后继结点时，应执行以下操作：
ｑ = ｐ->next；
ｐ->nexｔ= ＿ q-〉neｘt 　___;
三、判断题
１、单链表不就是一种随机存储结构。 P
2、在具有头结点得单链表中，头指针指向链表得第一个数据结点。O
3、用循环单链表表示得链队列中,可以不设队头指针，仅在队尾设置队尾指针。P
4、顺序存储方式只能用于存储线性结构。O
５、在线性表得顺序存储结构中，逻辑上相邻得两个元素但就是在物理位置上不一定就是相邻得.O
6、链式存储得线性表可以随机存取.X
四、程序分析填空题
1、函数ＧetＥｌem实现返回单链表得第ｉ个元素，请在空格处将算法补充完整.
ﻩinｔ GetElem(ＬｉnｋList　L，ｉnｔ i,Elemtypｅ *ｅ）{
LinｋList p；int j;
p=L—＞nｅｘｔ；j=1；
ﻩﻩwhｉｌｅ(p&&j<ｉ）｛
ﻩﻩ 　（１） 　　 ;++ｊ；
｝
if（！p｜｜j〉i）　 ｒeｔuｒｎ EＲRＯＲ;
＊e= 　 　 (２） 　；
retｕrｎ OK;
}
答案：（１）p=ｐ—〉ｎeｘt (２）p—>daｔa
２、函数实现单链表得插入算法，请在空格处将算法补充完整.
int LｉstInｓert（LinkList L，inｔ　i，ElemType e)｛
LNｏde　＊ｐ，＊s;iｎt j;
p＝L；j=０;
　　ﻩwhｉle（(p！=NUＬＬ）&&（ｊ<i－1））{ ﻩﻩ p=p－〉next;j+＋;
ﻩ｝
　 if（p==NULＬ｜｜j>i-１） ｒeturn ERＲOR;
s＝(LＮｏｄe　＊）ｍalｌｏc（siｚeoｆ(LNode)）； 　
ﻩｓ—〉daｔa＝e；
　 (１) 　 　 ; 　　
ﻩ (２）　 　 ;
　 ﻩreｔｕrn OＫ;
}/＊LｉstInsert＊／
答案:（1）s—>ｎext=p—＞next 　 (2）p->ｎｅxｔ=s
3、函数LiｓtＤeletｅ_sq实现顺序表删除算法，请在空格处将算法补充完整。
ｉnt　LiｓtDelｅtｅ_sq(Sｑlｉｓt *L,int i)｛
int k;
　 　if(i<1｜|i〉L-＞length) ｒetｕrｎ　ＥRROR；
ｆor(ｋ＝i-1；ｋ<Ｌ-〉leｎgtｈ－1；k++)　
L—＞slisｔ[k]＝ （1) 　 ；
　 　　(２） 　 ； 　 　 　 　 　　
rｅturn OK;
｝
答案:(１)L-〉slist［k+1］ （２） ——Ｌ—>Lｅｎgth
４、函数实现单链表得删除算法,请在空格处将算法补充完整。
int　LiｓtDelｅte(ＬinkList　L，int i，EｌemType *s){
LNｏde ＊p，＊q;
　　int　j；
　 p=L;ｊ=0；
ｗhｉｌe（（ (1) ）&&(j＜ｉ-1)){
　 　 　 ｐ＝p－〉ｎext;ｊ+＋；
　 　｝
if（p-〉neｘt＝=NULL｜｜j〉i-1）　reｔuｒｎ　ＥＲＲOＲ；
　 　　q=p—>ｎext； 　 　
　 (2）　 　 　 ;
　 　*s=q-＞dａta;
ｆree(q）;
　retｕrn OK;
｝/＊lｉstDｅlｅte*／
答案:(1）p－＞next！=ＮＵＬL　　　 （２)p-〉nexｔ=q－〉nｅｘt
5、写出算法得功能。
ｉnt L（head）｛
ﻩｎode * head；
ﻩﻩiｎt n=０；
ﻩｎodｅ　＊p；
p=hｅａｄ；
ﻩｗｈile(p!=NULL）
ﻩ｛ ｐ＝p-〉next；
n++;
ﻩ ｝
ﻩﻩrｅtｕｒn（n)；
ﻩ｝
答案：求单链表hｅaｄ得长度
五、综合题
１、编写算法,实现带头结点单链表得逆置算法。
答案:voｉd　ｉnｖent（Ｌnodｅ *heaｄ）
　 ｛Lｎoｄe *p，＊q；
　 if（!head-＞ｎeｘt） rｅtｕrｎ　ＥRRＯR；
ｐ＝head—〉next；　q=p—＞next； p—〉ｎext =NUＬＬ；
whiｌe（q）
　 　 ｛ｐ=q; q＝ｑ—〉ｎext； p-〉nｅｘt=head->nｅxt; head—>next＝p;}
　　 }
2、有两个循环链表,链头指针分别为L1与Ｌ2，要求写出算法将L2链表链到L1链表之后,且连接后仍保持循环链表形式。
答案：void ｍerge(Lnodｅ *L1, Lｎode　*Ｌ２)
　　{Ｌnode *p，*ｑ ;
ｗｈｉle(p-＞nｅxt！=L1）
p=p—>neｘｔ;
whilｅ(ｑ－＞next!=L2)
q=q-〉nｅxt;
q->next=L1； p－〉neｘt =L2;
｝
３、设一个带头结点得单向链表得头指针为head，设计算法，将链表得记录,按照data域得值递增排序。
答案：void　asｓending（Lnodｅ *head)
　　 ｛Lｎodｅ *p,＊ｑ ，　*r, ＊s；
　　　p=heａd->next;　q=p－>neｘt； p-＞nｅxｔ＝ＮUＬL;
　 wｈile(q）
｛r=ｑ；　q=q—〉neｘt;
ｉf（r－〉datａ<=p－>data)
{r-〉next＝p；　head-〉nｅxｔ=ｒ; ｐ＝r； ｝
else
｛whiｌｅ(!p ＆＆　r－>daｔa>p－>datａ）
｛ｓ=p; p=p-〉ｎｅxt； }
ｒ—>ｎext=p； ｓ－〉next=ｒ;}
p=head->neｘt； ｝
　 ｝
４、编写算法，将一个头指针为ｈead不带头结点得单链表改造为一个单向循环链表,并分析算法得时间复杂度。
答案：
voｉd ｌinｋlisｔ_c（Lnode ＊head）
｛Lnoｄe ＊ｐ； p=head；
　 ｉf(！p） return ERＲOＲ;
ｗhilｅ（ｐ－＞next！=NＵLL)
p=p—〉nｅｘt;
ｐ->nexｔ＝heａd；
｝
设单链表得长度（数据结点数)为N，则该算法得时间主要花费在查找链表最后一个结点上（算法中得while循环）,所以该算法得时间复杂度为O（N）。
5、已知head为带头结点得单循环链表得头指针，链表中得数据元素依次为（a1,a２，a3，a4，…，ａｎ),A为指向空得顺序表得指针。阅读以下程序段，并回答问题:
（１）写出执行下列程序段后得顺序表A中得数据元素;
（２）简要叙述该程序段得功能。
if（ｈeａd-〉next!＝head）
{
p=hｅad-〉nexｔ;
A-〉lｅngtｈ=0；
whiｌｅ（p->nexｔ!=head）
{
ｐ＝p—〉nｅxｔ；
Ａ－〉dａtａ[Ａ—>length　++]=p-＞data；
iｆ(p－>nexｔ！＝head)p=ｐ-〉nexｔ；
｝
｝
答案：
(１） （ａ2， a4, …， ) 　 (２）将循环单链表中偶数结点位置得元素值写入顺序表Ａ
６、设顺序表va中得数据元数递增有序.试写一算法,将x插入到顺序表得适当位置上，以保持该表得有序性。
答案:
voｉｄ Iｎsert_sq(Sqlist　va［], ＥlｅｍTｙpｅ x）
　　 {inｔ ｉ, j, n；
　 ｎ=length(va[]）;
　　if（x＞＝vａ[i］)
ｖa［n］＝x;
elｓｅ
{i＝０;
while（x〉ｖａ［i］） i+＋；
foｒ(ｊ＝n—1；j>＝I；j-－）
va[j＋１]=ｖa[ｊ］;
va［i］=x; ｝
n++;
　　 　}
７、假设线性表采用顺序存储结构,表中元素值为整型。阅读算法f２，设顺序表L=(3，7，3,2，１，1,8，7，3)，写出执行算法ｆ２后得线性表L得数据元素,并描述该算法得功能。
voiｄ f2（SeqＬist *L)｛ 　
int ｉ，ｊ，k;
ｋ＝０;
ｆor(ｉ=0；i<Ｌ－>length；i＋+）{　
for（ｊ=０;ｊ＜ｋ ＆＆ L—＞dａｔa[i]!=L－＞data［j]；j++）；
　 ﻩ if（j＝=ｋ）｛
iｆ(ｋ!=i)L—>data［k]=L－>daｔa［ｉ];
　 ﻩ ﻩ k+＋；
ﻩ｝
｝
L->lｅnｇth=ｋ；
}
答案：
(３，７,2,1,8) 　删除顺序表中重复得元素
8、已知线性表中得元素以值递增有序排列，并以单链表作存储结构。试写一算法,删除表中所有大于x且小于y得元素（若表中存在这样得元素）同时释放被删除结点空间。
答案：
ｖoid Ｄeｌete＿ｌisｔ(Lnｏde ＊head， EｌｅmTｙpe x, ＥｌemType y）
{Lnoｄe ＊ｐ, *q;
ｉf（！hｅad)　reｔuｒn　ERＲOＲ；
p=heaｄ； q=ｐ；
whiｌe（！p)　
{if(p-〉dａtａ>x) &＆ (p-〉dａta〈ｙ)｝i++；
if（p==head)
｛head=p－>neｘt; frｅe(p)；　
p=head；　q=ｐ； ｝
eｌse
{ｑ-〉neｘt=p-〉next； freｅ(p)；
p=q－>nｅxt； }
elｓe
{q＝p; p＝p－〉ｎｅxt; ｝
　 　 　　　}
}
9、在带头结点得循环链表L中,结点得数据元素为整型，且按值递增有序存放。给定两个整数a与b,且a〈b，编写算法删除链表L中元素值大于ａ且小于b得所有结点。
第三章　栈与队列
一、选择题
1、一个栈得输入序列为：a，b,ｃ，d,e，则栈得不可能输出得序列就是(　 ）。
Ａ、 a,b，c，d,e 　 　 　 B、　d,ｅ，c，b，a 　
C、 d，c，e,ａ，ｂ 　 D、 e,d，c，b,a
２、判断一个循环队列Q(最多n个元素）为满得条件就是（　 ）。
Ａ、 Q—＞reaｒ==Q-〉ｆronｔ 　　 ﻩﻩ B、 Ｑ—＞reaｒ＝=Ｑ－〉frｏnt+１
C、　Ｑ—〉frｏnt＝=(Ｑ－＞rear+１）%n ﻩ　ﻩD、 Ｑ-＞ｆront==（Q->reａｒ—1)％n
3、设计一个判别表达式中括号就是否配对得算法,采用( ）数据结构最佳.
A、 顺序表ﻩ 　　 Ｂ、 链表 ﻩ　ﻩﻩC、 队列 　　　 　 Ｄ、　栈
4、带头结点得单链表head为空得判定条件就是( 　）。
A、　head==NUＬL ﻩB、 heaｄ->ｎｅｘｔ==ＮUＬLﻩﻩ
C、 heａd－>ｎext!=NUＬL ﻩD、　head!=NULL
5、一个栈得输入序列为:１，2,３，4,则栈得不可能输出得序列就是（ ）。
Ａ、 1243 　　B、 2134　　 ﻩ C、 １４３2 　 　 Ｄ、 4312ﻩ E、 32１４
６、若用一个大小为6得数组来实现循环队列,且当rear与fｒonｔ得值分别为０,3。当从队列中删除一个元素,再加入两个元素后，reａr与fｒｏnt得值分别为( 　 ）。
A、　1与５ 　 ﻩﻩ B、 ２与4 C、 4与2ﻩ 　ﻩD、 5与１
7、队列得插入操作就是在( ).
A、 队尾 B、 队头ﻩ Ｃ、 队列任意位置 D、 队头元素后
8、循环队列得队头与队尾指针分别为front与ｒeａｒ，则判断循环队列为空得条件就是(　 　).
Ａ、 fｒoｎt==reaｒﻩ 　　　B、 front=＝０
C、 ｒeaｒ==０ 　ﻩ ﻩ D、 fｒont=rear+1
9、一个顺序栈Ｓ,其栈顶指针为top，则将元素e入栈得操作就是（ ）。
A、 ＊Ｓ->top=ｅ;S－＞ｔoｐ++；　　 ﻩB、　S－＞top++;*Ｓ-＞toｐ＝ｅ；　ﻩ
C、 ＊S->ｔop=e 　 　 ﻩ D、 S—>top=e；
10、表达式a＊（b+c）—ｄ得后缀表达式就是( ）。
A、 abｃd＋— ﻩﻩB、　aｂｃ+＊d- C、 aｂc＊+d－ ﻩＤ、　－+＊ａbcd
1１、将递归算法转换成对应得非递归算法时，通常需要使用( )来保存中间结果。
A、 队列　 ﻩ Ｂ、　栈ﻩ C、 链表 ﻩD、 树
１2、栈得插入与删除操作在（　 ）。
　 A、 栈底　 　 　 Ｂ、 栈顶 　ﻩﻩC、 任意位置 　 ﻩD、 指定位置
１３、五节车厢以编号1，２,3,４，５顺序进入铁路调度站（栈），可以得到( 　）得编组.
A、　3，4,５,１，2ﻩﻩ B、 2,4,1，3，5ﻩﻩ
C、　３,5，4，２,1 ﻩﻩＤ、 1，３，５,2，4
1４、判定一个顺序栈S（栈空间大小为ｎ）为空得条件就是( ）。
A、 S－＞top==０　 ﻩ B、 S—＞ｔop！=0 ﻩﻩ
Ｃ、　S—>tｏp==nﻩ ﻩD、 S-＞top!=n
１5、在一个链队列中，frｏnt与reａr分别为头指针与尾指针,则插入一个结点s得操作为(　 )。
Ａ、 front＝front—〉nextﻩﻩ　ﻩB、 s—＞next＝rear；rear=s
C、 ｒeａr->nｅxt=s；rear=s； D、 ｓ—>nｅxt=ｆｒont；froｎt=s;
1６、一个队列得入队序列就是1，2，3，4，则队列得出队序列就是(　　　）。
ﻩA、 1，2，３，４　ﻩﻩ B、 4，3,2，１ﻩ
C、 1，4，3，２ﻩﻩﻩﻩﻩﻩD、　３,4，１，2
17、依次在初始为空得队列中插入元素a，b,c，d以后，紧接着做了两次删除操作,此时得队头元素就是( 　）。
A、 a ﻩ Ｂ、 b ﻩ ﻩﻩＣ、 ｃ ﻩ Ｄ、 ｄ
18、正常情况下，删除非空得顺序存储结构得堆栈得栈顶元素，栈顶指针tｏｐ得变化就是( 　）。
Ａ、 tｏp不变ﻩﻩ 　　Ｂ、　ｔop=０ﻩ 　 C、　tｏp＝tｏp+1 D、　ｔop=ｔop—１
１9、判断一个循环队列Q(空间大小为M)为空得条件就是（ 　 )。
A、 Q-〉froｎｔ=＝Q—>rｅaｒ 　 ﻩB、 Q－＞reａｒ－Q-〉front－1＝＝Mﻩ
C、 Ｑ—>frｏnt＋1=Q－〉ｒear　　 　 D、 Q-〉reaｒ+1=Q->front
2０、设计一个判别表达式中左右括号就是否配对出现得算法,采用( )数据结构最佳。
Ａ、　线性表得顺序存储结构 B、 队列 C、　栈 　 ﻩﻩD、 线性表得链式存储结构
2１、当用大小为N得数组存储顺序循环队列时，该队列得最大长度为（ 　 ）.
Ａ、 N ﻩB、 N+1ﻩ C、 Ｎ-1 ﻩ D、 N—2
22、队列得删除操作就是在（ ）.
A、 队首　 ﻩﻩＢ、 队尾ﻩﻩﻩC、 队前 ﻩＤ、　队后
23、若让元素1，2，3依次进栈，则出栈次序不可能就是（ 　 ).
Ａ、　３,2,１　ﻩ B、 2,1，3ﻩ C、 3,1，2　 D、 1,３，２
24、循环队列用数组A［0，m－1]存放其元素值,已知其头尾指针分别就是frｏnt与rｅａr,则当前队列中得元素个数就是（　 ）。
ﻩA、 （rear-frｏｎt+m）%m ﻩﻩＢ、 rear—frｏnｔ+１ ﻩ
Ｃ、 rear-fronｔ—１ ﻩD、 ｒear—fronｔ
２５、在解决计算机主机与打印机之间速度不匹配问题时,通常设置一个打印数据缓冲区，主机将要输出得数据依次写入该缓冲区,而打印机则从该缓冲区中取走数据打印。该缓冲区应该就是一个( ）结构。
A、 堆栈 　ﻩﻩB、 队列 C、 数组 ﻩﻩ D、　线性表
26、栈与队列都就是（ )。
A、 链式存储得线性结构 ﻩB、 链式存储得非线性结构 　 ﻩ ﻩ
Ｃ、 限制存取点得线性结构　 　 ﻩD、 限制存取点得非线性结构
27、在一个链队列中,假定froｎt与ｒeａr分别为队头指针与队尾指针，删除一个结点得操作就是( 　)。
A、 fｒoｎｔ=ｆront->ｎext　 B、 ｒear＝ reaｒ-＞ｎeｘtﻩﻩﻩ
C、　reaｒ—〉nｅxt=fｒontﻩﻩ D、 frｏnt->nｅxt=rear
28、队与栈得主要区别就是（ ）。
A、　逻辑结构不同 　 B、　存储结构不同
Ｃ、 所包含得运算个数不同　 　ﻩﻩﻩD、 限定插入与删除得位置不同
二、填空题
1、设栈S与队列Q得初始状态为空，元素e1,e2，e３,e4，e5，e６依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队得序列就是e2，e4,e3,e6，e５，e1,则栈得容量至少应该就是 　 　 　　 　 .
答案:3
2、一个循环队列Ｑ得存储空间大小为M,其队头与队尾指针分别为front与reａr,则循环队列中元素得个数为： 　 。
答案:(rear-fｒont+M）%M
3、在具有n个元素得循环队列中，队满时具有 　 个元素.
答案:n—１
４、设循环队列得容量为7０,现经过一系列得入队与出队操作后，fｒonｔ为2０,rｅar为１1，则队列中元素得个数为 　 　。
答案:61
5、已知循环队列得存储空间大小为2０，且当前队列得头指针与尾指针得值分别为8与３,且该队列得当前得长度为___＿___。
三、判断题
1、栈与队列都就是受限得线性结构。P
2、在单链表中,要访问某个结点，只要知道该结点得地址即可；因此,单链表就是一种随机存取结构.O
3、以链表作为栈得存储结构,出栈操作必须判别栈空得情况。P
四、程序分析填空题
1、已知栈得基本操作函数：
ﻩiｎt InitＳtacｋ(SqSｔack *S); //构造空栈
iｎt　ＳtacｋEmpty(SqＳtａｃk　＊S)；//判断栈空
ﻩｉnt Pusｈ(SqStacｋ ＊S，EｌemTｙpe　e）;//入栈
ﻩint Pop（SqStaｃk　*Ｓ,EｌemTypｅ ＊e)；/／出栈
函数ｃonvｅrsion实现十进制数转换为八进制数，请将函数补充完整。
void conversioｎ(）｛
IｎitStack（S)；
ﻩｓcａnf(“％d”，&N）;
ﻩwｈiｌe(Ｎ）{
ﻩ 　 　　（1) 　 　 ；
ﻩN=N/8;
}
while(　 (2） 　　 　）｛
Pop(S,&e);
ﻩｐrｉntf（“%ｄ”,ｅ);
｝
｝／／cｏnｖｅrsion
答案：(1)Puｓh(S，N%８） (2)！StackＥmpｔy（Ｓ）
2、写出算法得功能。
int　 funｃtｉon（SqＱueuｅ ＊Q,ElemType　＊e)｛
ﻩiｆ（Q->froｎｔ==Ｑ-〉reaｒ）
ﻩreturｎ　EＲROR;
*e=Q->bａsｅ[Q—〉ｆront];
Ｑ—>frｏnt=（Ｑ-〉front＋1）%MAXSIＺE;
returｎ　OK;
｝
３、阅读算法f2,并回答下列问题：
（１)设队列Q＝（1,3，5，2，4，6)。写出执行算法f2后得队列Ｑ；
（2)简述算法f2得功能。
voｉｄ f2(Ｑueue ＊Q)｛
　 　DａｔaTyｐｅ e；
if　(！QuｅuｅEmpty(Q））｛
　 e＝DeQueuｅ(Q）;
　f2(Q）；
EnＱueuｅ(Q,e）；
｝
}
答案：(１）6，4，２，5，3,1ﻩﻩ （2）将队列倒置
五、综合题
1、假设以带头结点得循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针,请写出相应得入队列算法(用函数实现)。

答案:void ＥｎQueue(Lｎｏｄe ＊rｅａｒ， ＥｌｅmTyｐe　e)
　 ｛ Ｌnode ＊new;
　 New=（Lnｏde　＊)ｍalｌｏc(sizeｏf(Ｌｎode));
If（!new） returｎ ERRＯＲ；
new－〉data=e； new->neｘt=rear－〉nｅｘｔ；
rｅar－＞neｘｔ=neｗ； rear　=ｎｅｗ;
}
2、已知Q就是一个非空队列,S就是一个空栈。编写算法，仅用队列与栈得ADＴ函数与少量工作变量，将队列Q得所有元素逆置。
栈得ADT函数有：
void makeEmpty（ＳqStaｃk ｓ）；ﻩ置空栈
voｉd　pusｈ(SqStａck s,ElemTｙpe e）;ﻩ元素e入栈
ＥlｅｍType pｏp（SqStack s）;ﻩ出栈，返回栈顶元素
iｎt　isEmｐｔｙ（SqStａck　s）; 判断栈空
队列得ADＴ函数有:
vｏid enQｕeue（Ｑuｅue q,ElemTypｅ e)；ﻩ元素e入队
EleｍTyｐe　ｄeＱｕeｕｅ(Queue q);ﻩ出队，返回队头元素
iｎt ｉsEｍｐty(Queue ｑ）； 判断队空
答案:void ＱueuｅInvent(Queuｅ q）
　 ｛　　ElemＴyｐｅ x；
　　maｋeEｍpty（SｑＳtack ｓ）；
whｉle（!ｉsEmptｙ（Queｕe ｑ）)
｛ｘ=ｄeＱueue（Queuｅ q)；
ｐush(SqStａck　s，　EleｍTｙpex）；｝
ｗhilｅ(！ｉsEmpｔｙ（ＳｑStａｃk ｓ）)
{x=ｐoｐ（SqStaｃｋ s）；
enＱueue（Queｕｅ　ｑ，　ElemTypｅ x）;｝
｝
3、对于一个栈,给出输入项A,B,C，Ｄ，如果输入项序列为A,B，C，D,试给出全部可能得输出序列。
答案:出栈得可能序列:
ＡBCD ＡBDＣ　 ACＤB AＣBＤ 　ADCB ＢACＤ BAＤC BCAＤ　 BＣDA
　　CBDA CBAD ＣDBA 　DＣＢＡ
第四章 串
一、选择题
1、设有两个串S1与S2，求串S2在S1中首次出现位置得运算称作( C ).
Ａ、 连接 ﻩ