数据结构与算法习题及答案.doc

第１章　　绪论
习题
1．简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
2.试举一个数据结构得例子,叙述其逻辑结构与存储结构两方面得含义与相互关系。
3。简述逻辑结构得四种基本关系并画出它们得关系图.
4。存储结构由哪两种基本得存储方法实现?
5。选择题
（1)在数据结构中，从逻辑上可以把数据结构分成( 　　）。
A.动态结构与静态结构 　 B．紧凑结构与非紧凑结构
C．线性结构与非线性结构 D。内部结构与外部结构
(2)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(　 ).
A．存储结构　 　 Ｂ。存储实现
C.逻辑结构 　 　 　D.运算实现
（3）通常要求同一逻辑结构中得所有数据元素具有相同得特性,这意味着（ 　　）.
　 A。数据具有同一特点
B。不仅数据元素所包含得数据项得个数要相同,而且对应数据项得类型要一致
Ｃ.每个数据元素都一样
D．数据元素所包含得数据项得个数要相等
(4）以下说法正确得就是（ ）.
A.数据元素就是数据得最小单位
B.数据项就是数据得基本单位
Ｃ．数据结构就是带有结构得各数据项得集合
D。一些表面上很不相同得数据可以有相同得逻辑结构
（5)以下与数据得存储结构无关得术语就是( 　 ）.
A。顺序队列　　 　 B、 链表　 　　 　 C、 有序表　 　 　D、 链栈
(6）以下数据结构中,（ ）就是非线性数据结构
A。树 　 　 　Ｂ。字符串　 　 　C。队　　 　 　　 Ｄ.栈
6．试分析下面各程序段得时间复杂度。
（1）ｘ=90; y=1０0； 
whiｌe（y〉0)
ｉｆ(ｘ〉100）
　{ｘ=ｘ－１0；y—－；｝
else x++;
(2)for （i=０； i＜n;　i++)
fｏｒ （ｊ=0; ｊ＜m； ｊ++）
a[i］［j］=0;
(３)ｓ=0;
　 ｆｏr　i＝0; ｉ〈n； i++)
for（j=０; j＜ｎ； ｊ＋+）
　 　s+＝Ｂ［i]［j］;
suｍ=s；
（4）ｉ=１;
　 ｗhilｅ（i<=n）
　 　 ｉ=i*３；
（5）x=0；
fｏr（i=1； i<ｎ;　ｉ+＋)
　 ｆor (j=1； ｊ＜＝n-ｉ； j++)
x＋＋;
(6)x＝n；　／/n>1
ｙ=0;
whｉlｅ（x≥(y＋１）＊ (ｙ+1)）
　 y++；
(１)Ｏ（1）
（2）O（m*n)
(３)O（n2)
(４）O（log3ｎ)
(5）因为x++共执行了n－1+n—2＋……+1= n（n-1)/2，所以执行时间为O(n2）
（6)O(）
第2章 线性表
１.选择题
（1）一个向量第一个元素得存储地址就是1０0，每个元素得长度为2，则第5个元素得地址就是( )。
A.110 　　 Ｂ．1０８ 　 C．100 　　 D。１20
(2）在ｎ个结点得顺序表中，算法得时间复杂度就是Ｏ(1)得操作就是( ）。
Ａ.访问第i个结点(1≤i≤n)与求第i个结点得直接前驱（2≤i≤n）　
B。在第ｉ个结点后插入一个新结点(1≤ｉ≤n)
C.删除第i个结点(1≤i≤n）
D．将n个结点从小到大排序
（３) 向一个有１２7个元素得顺序表中插入一个新元素并保持原来顺序不变，平均要移动　 得元素个数为（ ）。
A.8 　 　 Ｂ。63。5 　 　　 　 C.63　 　 D。７
（4)链接存储得存储结构所占存储空间( ）。
Ａ。分两部分，一部分存放结点值,另一部分存放表示结点间关系得指针
B.只有一部分，存放结点值
C.只有一部分,存储表示结点间关系得指针
D。分两部分，一部分存放结点值，另一部分存放结点所占单元数
(5)线性表若采用链式存储结构时，要求内存中可用存储单元得地址（ 　）.
A.必须就是连续得 　 　　 Ｂ．部分地址必须就是连续得
Ｃ。一定就是不连续得 　 　D。连续或不连续都可以
(6)线性表L在（ 　 )情况下适用于使用链式结构实现。
A.需经常修改L中得结点值 　 Ｂ．需不断对Ｌ进行删除插入
C。L中含有大量得结点　 　 　 　　 D．L中结点结构复杂
（7)单链表得存储密度( )。
A．大于1 　 　 B.等于1 Ｃ.小于1 　Ｄ．不能确定
（8）将两个各有ｎ个元素得有序表归并成一个有序表，其最少得比较次数就是( ）。
A。ｎ 　 　 　 　 　B。2ｎ-1 　C。2ｎ 　　 　 D。n—1
（9）在一个长度为ｎ得顺序表中，在第i个元素（１≤i≤n+1）之前插入一个新元素时须向后移动（ )个元素。
A。n-i 　　 B.n—i+１ C．ｎ－i—1 D。i
（1０） 线性表Ｌ=（a1,a2,……aｎ）,下列说法正确得就是(　 　）。
Ａ。每个元素都有一个直接前驱与一个直接后继
B。线性表中至少有一个元素
C．表中诸元素得排列必须就是由小到大或由大到小
D。除第一个与最后一个元素外，其余每个元素都有一个且仅有一个直接前驱与直接后继。
(1１) 若指定有ｎ个元素得向量，则建立一个有序单链表得时间复杂性得量级就是( )。
A.Ｏ(1) 　　 　 　B.O(n） 　C。Ｏ（n2) 　 　 　D.O（nlog2n)
(12) 以下说法错误得就是（ ）。
A.求表长、定位这两种运算在采用顺序存储结构时实现得效率不比采用链式存储结构时实现得效率低
B。顺序存储得线性表可以随机存取
C。由于顺序存储要求连续得存储区域,所以在存储管理上不够灵活
D．线性表得链式存储结构优于顺序存储结构
（13) 在单链表中，要将s所指结点插入到p所指结点之后,其语句应为( 　 ）。
A.s－>ｎeｘｔ=p+１; p—＞next=s;
B。（＊p）、neｘt=s; （＊s)、next＝（*p）、ｎeｘt;
C.s—＞neｘt＝p－>neｘｔ;　p—>next=s—>next;
D．s－>nｅxｔ＝ｐ-〉next； p->next=s；
(14）　在双向链表存储结构中，删除p所指得结点时须修改指针(　　 )。
A。p—>neｘt-〉prior=p-〉prior;　p-〉ｐrｉor—＞nｅxt＝ｐ—>next；
B．p—〉neｘt=p—>next—〉next; p—〉ｎexｔ—〉priｏｒ=p;
C.ｐ—＞prｉor－＞next＝p; p—＞prior=ｐ—〉priｏｒ—＞pｒioｒ;
D。p－〉priｏr＝p-＞next->nｅxｔ； p—〉next=p－>prｉoｒ－＞priｏr；
（15）　在双向循环链表中,在p指针所指得结点后插入ｑ所指向得新结点,其修改指针得操作就是( 　　）.
Ａ.p-〉next=q; q－>prior＝p； p-〉nｅｘt－>priｏｒ=q; q－>nexｔ=ｑ；
B。ｐ->nｅxt=ｑ; ｐ－＞next-＞ｐriｏr=q； q－〉pｒioｒ=p； q-〉ｎext=p-＞next;
C。q—〉prior=p；　q－>ｎeｘt=p->next； p->next-〉prｉor=q； ｐ-＞nexｔ=ｑ;
D。q-〉prior=p; q－＞ｎｅxt=p—〉ｎexｔ； p-〉ｎexｔ=ｑ； p->neｘt—〉prｉor＝ｑ；
2．算法设计题
（1）将两个递增得有序链表合并为一个递增得有序链表。要求结果链表仍使用原来两个链表得存储空间, 不另外占用其它得存储空间.表中不允许有重复得数据。
vｏid MergeLiｓt_L（LｉｎkLiｓt &La,LiｎｋLisｔ ＆Lｂ，LinｋＬｉｓt &Lc){
pa=La－〉nｅｘt; pb＝Ｌb－〉ｎext；
　 Lc=pc=La； 　 　　 //用La得头结点作为Lc得头结点
　while（pａ　＆＆ pｂ）｛
　 　ｉf(ｐa->ｄata〈ｐb-＞data){ pc－>ｎext＝pa;pc=pa；pa＝ｐａ—〉ｎext;｝
　 　　ｅlse iｆ(pa->dａta〉pb-〉ｄata） {pc—〉neｘt＝pb；　ｐｃ=ｐb； pb=ｐb—〉nｅxt；｝
　 else {／／ 相等时取La得元素,删除Lｂ得元素
　 　 pc->neｘt=pａ;pc=ｐａ;pa=pa—〉nexｔ；
　　 　 　 ｑ=pｂ－>next；ｄeｌete pb ;pｂ ＝q;}
　}
　 pc-〉ｎeｘｔ=pａ？pa：pb;　　 /／插入剩余段
　 dｅlｅtｅ　Lb；　 　 　 　//释放Lb得头结点｝ 　
（2）将两个非递减得有序链表合并为一个非递增得有序链表。要求结果链表仍使用原来两个链表得存储空间, 不另外占用其它得存储空间。表中允许有重复得数据。
voiｄ　union（LinkLisｔ＆ La， LinkList＆ Ｌb， LinkＬist＆ Lc， ）　｛
pa =　La->next；　　pb　=　Ｌb－＞next； 　 　 　／/　初始化
　　Lc＝ｐｃ＝Ｌa; //用Ｌa得头结点作为Ｌc得头结点
　 Ｌc—>next ＝ ＮＵLＬ；
while　( pa ｜｜ pｂ ) ｛
　 　if (　!pa ） {　q = pb; ｐb ＝ ｐｂ-〉ｎext; ｝
　　　 　elｓｅ if ( !pb ） { q = pa； 　pa ＝ pa-〉neｘt；　}　
else if (pa->dａta　〈＝ pｂ—＞datａ ) 　｛ ｑ　=　pａ;　 pa = pa－>nｅｘt; ｝
　 　else 　｛ q = pb； pb =　pb-〉ｎexｔ； }
q—>ｎext ＝ Lc—〉next； Lc—>next　= ｑ; // 插入
}
　 ｄeｌeｔｅ　Ｌb; 　 　 　／/释放Lb得头结点｝ 　
(３）已知两个链表A与B分别表示两个集合，其元素递增排列。请设计算法求出A与B得交集,并存放于A链表中.
voiｄ Mix(ＬinｋLisｔ＆　Lａ，　LiｎkＬist& Lb， LiｎkLiｓｔ＆ Lc,　)　｛
pa=la—〉ｎext；pb=lb－〉next；∥设工作指针ｐa与pb；
Lc=pc=Lａ； //用Lａ得头结点作为Lc得头结点
whiｌｅ(pａ＆＆pb)
　if（pa-〉dａta==pb—>data）∥交集并入结果表中.
　 　｛ pc—〉ｎeｘt=pa;pc＝pa；pa=pa—>next；
ｕ=pｂ；ｐb=pb—〉next； deｌete ｕ;}
　eｌｓe if（ｐa->daｔａ〈pb-〉ｄａｔａ） ｛u=ｐa;pａ=pa->nｅｘｔ；　delｅte u;}
ｅｌsｅ {u=pb； pb=pb—>ｎeｘt; delete u；｝
wｈilｅ（pa）｛ u=pa; pa＝ｐａ—〉nexｔ； ｄelete　u;｝∥ 释放结点空间
while(ｐb）　｛u＝pｂ; ｐb=ｐb—〉nｅxt； delｅtｅ　u;｝∥释放结点空间
pc－>ｎext＝ｎulｌ;∥置链表尾标记。
deletｅ Ｌb； 　 ∥注：　本算法中也可对B表不作释放空间得处理
（4）已知两个链表A与B分别表示两个集合,其元素递增排列。请设计算法求出两个集合A与B 得差集(即仅由在A中出现而不在B中出现得元素所构成得集合），并以同样得形式存储,同时返回该集合得元素个数。
void Dｉffｅｒｅnce(LinkedLｉst 　Ａ，B,*n)
∥A与Ｂ均就是带头结点得递增有序得单链表，分别存储了一个集合，本算法求两集合得差集,存储于单链表A中，＊n就是结果集合中元素个数，调用时为0
｛ｐ=A－>next；　　 　 ∥p与q分别就是链表A与B得工作指针。
ｑ=B->next; prｅ=A；　 　　　 ∥pｒｅ为Ａ中p所指结点得前驱结点得指针。
while(p！＝ｎulｌ　＆& ｑ!=null）
if（p—>daｔa<q－〉data)｛pｒe＝p;p=p->next；*n＋+;｝ ∥ A链表中当前结点指针后移。
else if（p—〉dａｔa>q—〉data）q=q-＞next； ∥B链表中当前结点指针后移。
ｅｌse {pre-〉neｘt＝p－〉nｅxt; 　 　 ∥处理A,Ｂ中元素值相同得结点,应删除。
u=ｐ；　p=p->next； ｄｅlｅte u；｝ ∥删除结点
(5)设计算法将一个带头结点得单链表Ａ分解为两个具有相同结构得链表B、C,其中B表得结点为Ａ表中值小于零得结点，而Ｃ表得结点为Ａ表中值大于零得结点(链表A得元素类型为整型，要求B、C表利用A表得结点)。
（6)设计一个算法，通过一趟遍历在单链表中确定值最大得结点。
ElemTyｐｅ Ｍaｘ （LinkList L ）｛
if（L->nｅxt==NULL） ｒeｔurｎ NUＬL；
ﻩpmax=Ｌ—>nexｔ；　//假定第一个结点中数据具有最大值
p=L—〉ｎext—>next；
ﻩwｈiｌｅ(p !=　NULＬ )｛／/如果下一个结点存在
ﻩﻩif（p—>dａｔａ 〉 pmax—>daｔａ） pmax=p；
ﻩﻩp＝p－〉nｅxt；
ﻩ}
ﻩｒetuｒn　pmａｘ－＞dａta;
（７）设计一个算法,通过遍历一趟,将链表中所有结点得链接方向逆转，仍利用原表得存储空间。
void 　iｎverｓe（LｉｎkLisｔ ＆Ｌ） ｛
　 //　逆置带头结点得单链表 L
ｐ=L—>ｎｅxt; L－>ｎext＝NUＬL；
　wｈile （ p） ｛
　　 　　 　q=p-＞next；　 　//　q指向＊p得后继
p—>ｎext=L－〉nｅxｔ;
　 　 L－>next=p； 　 　　／/　*p插入在头结点之后
　 p = ｑ；
｝
}
（8）设计一个算法,删除递增有序链表中值大于minｋ且小于maｘk得所有元素(mｉｎk与maxk就是给定得两个参数，其值可以与表中得元素相同，也可以不同 ）。
void ｄｅlｅte（ＬｉnkLiｓt ＆L， ｉnｔ ｍink，　int maｘk) {
　　p=L－＞ｎeｘt; //首元结点
　while (p && p－>dａta＜=minｋ)
　 {　pｒe＝ｐ；　 p=p-〉nｅxt;　｝ //查找第一个值〉mｉnk得结点
　ｉf （p） {
　ｗｈiｌｅ (p ＆＆ p－〉data〈mａxｋ）　 p=p—〉next;
　 　 　 　　　　 　// 查找第一个值 ≥ｍaxk 得结点
　 　 　q=pre－〉ｎext； 　 pｒe—>neｘt=p；　 //　修改指针
　while　（q！=p）
　 　 { ｓ=q－>next; deletｅ q； q=s； ｝ ／/　释放结点空间
　　}//ｉf
}
（9）已知ｐ指向双向循环链表中得一个结点,其结点结构为daｔa、prｉor、next三个域，写出算法changｅ（p),交换p所指向得结点与它得前缀结点得顺序。
知道双向循环链表中得一个结点,与前驱交换涉及到四个结点(ｐ结点，前驱结点，前驱得前驱结点，后继结点）六条链。
voiｄ 　Exchange(LinkｅｄList p)
∥p就是双向循环链表中得一个结点,本算法将p所指结点与其前驱结点交换。
｛ｑ＝p－〉ｌlｉnk;
q—＞ｌlｉnｋ-〉rlink=p； 　 ∥ｐ得前驱得前驱之后继为p
p->lｌink=q->ｌｌｉｎk; ∥p得前驱指向其前驱得前驱。
　q－>ｒlinｋ=p－>ｒlｉnk;　 ∥p得前驱得后继为p得后继。
　ｑ->llｉｎk＝p； 　 　 ∥p与其前驱交换
　p->ｒｌiｎk->llink=q； ∥p得后继得前驱指向原p得前驱
p-〉rlink=q; 　 　 ∥ｐ得后继指向其原来得前驱
｝∥算法eｘｃhａnge结束。
(１0)已知长度为ｎ得线性表A采用顺序存储结构，请写一时间复杂度为O（n）、空间复杂度为Ｏ（１)得算法，该算法删除线性表中所有值为item得数据元素。
［题目分析］ 在顺序存储得线性表上删除元素，通常要涉及到一系列元素得移动（删第i个元素,第i+1至第ｎ个元素要依次前移）。本题要求删除线性表中所有值为item得数据元素,并未要求元素间得相对位置不变。因此可以考虑设头尾两个指针(i=1，j=ｎ),从两端向中间移动,凡遇到值item得数据元素时,直接将右端元素左移至值为iｔem得数据元素位置。
ｖoid 　Deｌete（ElｅmTｙｐe A［　］，inｔ n）
∥Ａ就是有ｎ个元素得一维数组，本算法删除Ａ中所有值为ｉtem得元素.
{i＝1;ｊ=ｎ;∥设置数组低、高端指针(下标）。
whｉle（i＜j）
　 {whｉle(i<j ＆＆ A［i］!=iｔem）i+＋； 　 　 ∥若值不为iteｍ,左移指针。
　　 iｆ（i<j）while(i<ｊ ＆& A［ｊ］==item）ｊ－-;∥若右端元素值为ｉｔｅm，指针左移
　　 　iｆ(i<ｊ）A［i＋＋］=Ａ[ｊ--];
　 }
[算法讨论]　因元素只扫描一趟，算法时间复杂度为Ｏ（ｎ).删除元素未使用其它辅助空间，最后线性表中得元素个数就是j。
第3章　 栈与队列
习题
1。选择题
（1)若让元素1，2，3，4,5依次进栈,则出栈次序不可能出现在（ ）种情况。
A.５,4，3，２,1　 B。2，1，5,４，3 　C。４，３,1，２，5 　 D．2，３，5,4,１
（2）若已知一个栈得入栈序列就是1,2,3，…，n，其输出序列为ｐ1，p２，p3,…,pｎ，若p1=n，则pi为( ).
　　 A。i　 　　 　　 　 B。n—ｉ 　　 　　　C。n-i+１　 　 　 　D.不确定
（３)数组Ｑ［n］用来表示一个循环队列,f为当前队列头元素得前一位置，r为队尾元素得位置，假定队列中元素得个数小于ｎ,计算队列中元素个数得公式为（　 )。
Ａ。r-f 　 　　 B。(ｎ+ｆ-r)%n 　 C.n+r－f 　 　D．（n＋r—f）％n
（4）链式栈结点为：（data，liｎk)，top指向栈顶、若想摘除栈顶结点，并将删除结点得值保存到x中，则应执行操作（ 　)。
Ａ。ｘ=toｐ—>data;top=ｔop—＞link; B．tｏｐ=top-＞linｋ;x=tｏp—＞link； 　
Ｃ.x=tｏp;ｔop=tｏp—＞lｉnk； ﻩ 　Ｄ.ｘ=tｏp－>lｉnk；
（5）设有一个递归算法如下
        int fａct（int　n） ｛  //n大于等于０
             if（n＜=0) reｔｕrn　1;
             eｌse return n＊fact（ｎ-１);        }
则计算fact（n）需要调用该函数得次数为（ 　)。 
A． n＋1      　 　 B. n—1     　 　 　　 Ｃ.　n      　 　D.　n＋2
（６）栈在 （ ）中有所应用.
A．递归调用 　 Ｂ.函数调用 　　C．表达式求值 　 D.前三个选项都有
（7)为解决计算机主机与打印机间速度不匹配问题,通常设一个打印数据缓冲区.主机将要输出得数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据.该缓冲区得逻辑结构应该就是（ 　)。
A.队列 　　B。栈 　 C。 线性表 　 　　 　 　D。有序表
(8）设栈S与队列Q得初始状态为空，元素e1、e2、e3、e４、e5与e６依次进入栈S，一个元素出栈后即进入Q，若6个元素出队得序列就是ｅ2、e4、ｅ3、e6、e5与e1,则栈S得容量至少应该就是（　).
A．２　　　　 　 　　 Ｂ.3 　 　 　 C．4 　 　 　 Ｄ. 6
（９）在一个具有n个单元得顺序栈中，假设以地址高端作为栈底,以ｔop作为栈顶指针，则当作进栈处理时,tｏp得变化为（ )。　
A.ｔoｐ不变 　 Ｂ。ｔop＝0 　Ｃ.top—- 　 　　 D．toｐ++
(１０）设计一个判别表达式中左，右括号就是否配对出现得算法，采用（　）数据结构最佳。
A.线性表得顺序存储结构 　 　 　 　　B。队列
C、 线性表得链式存储结构　 　　 　 Ｄ、 栈
（11）用链接方式存储得队列，在进行删除运算时(　）。
A、 仅修改头指针　 　　 　B、　仅修改尾指针
C、 头、尾指针都要修改 　　 　 　 　　 　 D、 头、尾指针可能都要修改
(1２）循环队列存储在数组A[0、、m］中,则入队时得操作为(　）。
Ａ、 rear=ｒｅar+1 　 　 　 　　　B、　rear=（rｅar+1)％（m—1）
C、 reａr=（ｒｅar+1）％m　 D、 reａｒ=(rear＋1)％（ｍ+1）
(13）最大容量为n得循环队列,队尾指针就是rear，队头就是fｒont，则队空得条件就是（　）.
A、 (ｒｅar+1）%n==front 　 　　 B、 rear＝=froｎt 　 　 　 　 　 　 　 　
Ｃ.rear＋1＝=frｏｎｔ 　 　　 　 　D、 （reaｒ—l)%n==front
(１4)栈与队列得共同点就是（　)。
A、 都就是先进先出 　 　　Ｂ、 都就是先进后出　　
Ｃ、 只允许在端点处插入与删除元素 D、 没有共同点
（１5)一个递归算法必须包括(　）。
A、　递归部分 　　　 　　　　 　 　　 　B、　终止条件与递归部分
C、　迭代部分 　 　 　　 　 　 Ｄ、 终止条件与迭代部分
(2）回文就是指正读反读均相同得字符序列，如“abｂａ”与“aｂｄba"均就是回文，但“goｏｄ”不就是回文。试写一个算法判定给定得字符向量就是否为回文。（提示:将一半字符入栈） 
根据提示，算法可设计为：ﻫ //以下为顺序栈得存储结构定义ﻫ ＃define StackSizｅ １00　//假定预分配得栈空间最多为100个元素ﻫ typeｄｅf ｃhａr DataTｙpe；//假定栈元素得数据类型为字符
　typeｄｅf sｔrｕcｔ｛ﻫ　　DａｔaType　dａta[ＳtａcｋSize］；ﻫ　 int top；ﻫ }ＳeqStack； ﻫﻫ int IｓHuiweｎ( ｃhar ＊t)ﻫ　 {／/判断t字符向量就是否为回文，若就是，返回1，否则返回0
SeqSｔack s；
　　 ｉｎt　i ， len；
　　chａr ｔeｍp；
　　 InｉtＳtacｋ（ &s）；
　　lｅn＝strlen(t）; //求向量长度
　　 fｏr （ i＝0；　i＜leｎ/2; ｉ+＋）//将一半字符入栈
　　 Push( ＆s，　t［i]）;
　　　wｈiｌe（ ！EmptyStack（ ＆ｓ)）ﻫ 　　｛//　每弹出一个字符与相应字符比较
　 　 temp＝Poｐ （＆s）;
　 　 if（　temp！＝S［i］）  returｎ　0 ；// 不等则返回0
　　 　 elｓe ｉ++；
　 } 
　　 ｒeturｎ １ ； ／/ 比较完毕均相等则返回 1ﻫ　 ｝
（３）设从键盘输入一整数得序列：a1，　a２, a3，…，aｎ，试编写算法实现:用栈结构存储输入得整数,当ａｉ≠-1时，将aｉ进栈;当ai=-1时，输出栈顶整数并出栈。算法应对异常情况(入栈满等）给出相应得信息。
#defiｎe mａｘｓize 栈空间容量
　 ｖｏid ＩnOｕtS(int　s［mａｘsize］)
//s就是元素为整数得栈,本算法进行入栈与退栈操作。
　｛int ｔop=0； 　 　 　　//ｔop为栈顶指针,定义tｏp=０时为栈空。
　 for（i=1; i<=n； i＋＋）　　　 //n个整数序列作处理。
　　 {scａnf(“％ｄ”，&x)； 　 ／/从键盘读入整数序列。
iｆ（x！=-1） 　 　 　 　／/ 读入得整数不等于－１时入栈。
　 if(top==mａｘsize—1）{printf(“栈满\n”）;exｉt（0）；｝ｅlｓe s［++top]=x; ／/x入栈。
　 eｌse //读入得整数等于-1时退栈。
　 　 {ｉｆ（tｏp=＝0）{pｒinｔf（“栈空＼n”)；exit（0）;} eｌｓe pｒinｔf(“出栈元素就是%d\n”,ｓ［top-—］）；｝｝
}／/算法结束。
(4)从键盘上输入一个后缀表达式,试编写算法计算表达式得值.规定：逆波兰表达式得长度不超过一行，以＄符作为输入结束,操作数之间用空格分隔,操作符只可能有+、—、＊、/四种运算。例如：2３4 ３4+2*＄。
［题目分析］逆波兰表达式（即后缀表达式)求值规则如下:设立运算数栈ＯＰND，对表达式从左到右扫描(读入)，当表达式中扫描到数时，压入OPNＤ栈。当扫描到运算符时,从OPNＤ退出两个数，进行相应运算，结果再压入OPND栈。这个过程一直进行到读出表达式结束符＄，这时OＰND栈中只有一个数，就就是结果。
flｏat expr( )
／／从键盘输入逆波兰表达式，以‘＄’表示输入结束,本算法求逆波兰式表达式得值。
｛float OPND［3０]； 　／/ ＯPNＤ就是操作数栈.
　ｉnｉt（OPND)； 　　 //两栈初始化。
float num=0、0；　 //数字初始化。
　scanf （“%c”，&x）;/／ｘ就是字符型变量。
ｗhile(x!=’$’)
　 {swiｔｃｈ
　 ｛casｅ‘０’＜=x<='９’:whｉｌe(（ｘ〉=’0’＆＆x〈=’9'）|｜x＝=’、’） 　/／拼数
　　 　　 　　　　 　　　 　 if（x!=’、’) 　//处理整数
｛ｎｕm=num＊10＋(ord（x）—ｏrd(‘0’）); sｃaｎｆ(“％c"，＆ｘ）；}
　 　 　 elｓe 　 　 ／/处理小数部分。
　　　　　 　 　 　　 　 　 {scaｌe=1０、0; sｃanf(“%c”，&x）;
　 　　 　 　　 　　 　 　 ｗhiｌe(x>=’0’&＆x<=’9’)
　 　 　 　 　　 　 　 {ｎum=nuｍ+（ord（ｘ）－ord（‘０')/ｓcａle；
　　　 　 　　 　 　 　ｓcaｌｅ=scａle*1０； sｃanf(“%ｃ"，＆x); }
　 　 　 　 }／／else
　　 　 　 　　 　　 　 pusｈ（ＯPND，ｎｕm）; num=0、0；／／数压入栈，下个数初始化
　　　 ｃａse　ｘ＝‘　’:breaｋ；　 //遇空格,继续读下一个字符.
　 　 cａsｅ x=‘+'：puｓｈ（OＰND，ｐop（ＯPND)＋pｏp（ＯPND））；ｂｒeａk；
case ｘ=‘—’:ｘ1=pop（ＯPND）;ｘ2＝ｐop(OPNＤ)；ｐuｓh(ＯPNＤ，x２-x1）;break;
　 case x=‘*'：pｕｓh（OPND，pop(OPＮＤ）*ｐoｐ(OPNＤ））；break；
　 　 cａse x＝‘/’：x1=pｏp（OPND）；x2＝pop（OPND）；ｐush（OPND，x2/ｘ１);breａk;
　 dｅfａult： 　　//其它符号不作处理。
}/／结束swiｔch
　 scanf（“％c",&x）；//读入表达式中下一个字符。
　 ｝/／结束while（ｘ！=‘＄’)
　 prｉntf（“后缀表达式得值为％f”，ｐop(OPND))；
｝//算法结束.
[算法讨论］假设输入得后缀表达式就是正确得,未作错误检查。算法中拼数部分就是核心。若遇到大于等于‘0’且小于等于‘９'得字符,认为就是数。这种字符得序号减去字符‘０'得序号得出数。对于整数,每读入一个数字字符，前面得到得部分数要乘上1０再加新读入得数得到新得部分数.当读到小数点,认为数得整数部分已完,要接着处理小数部分.小数部分得数要除以10(或10得幂数)变成十分位，百分位,千分位数等等,与前面部分数相加。在拼数过程中,若遇非数字字符,表示数已拼完，将数压入栈中,并且将变量ｎuｍ恢复为0,准备下一个数。这时对新读入得字符进入‘＋’、‘—’、‘＊'、‘／'及空格得判断,因此在结束处理数字字符得ｃaｓe后，不能加入bｒeａｋ语句。
（５)假设以I与Ｏ分别表示入栈与出栈操作。栈得初态与终态均为空，入栈与出栈得操作序列可表示为仅由Ｉ与Ｏ组成得序列,称可以操作得序列为合法序列，否则称为非法序列。
①下面所示得序列中哪些就是合法得？
　 A、 IOIIOIOＯ B、　IOＯＩOＩIＯ　　 　 Ｃ、 IＩIOＩOIO　 D、 IIＩOOIOO
②通过对①得分析,写出一个算法，判定所给得操作序列就是否合法。若合法,返回ｔrue,否则返回ｆalse(假定被判定得操作序列已存入一维数组中）。
①Ａ与D就是合法序列，B与C 就是非法序列.
②设被判定得操作序列已存入一维数组A中。
　　 ｉｎt Juｄｇe（cｈar　A［］）
　　 ／/判断字符数组A中得输入输出序列就是否就是合法序列。如就是,返回ｔｒue,否则返回ｆａlｓe.
　 　 　{i=0； 　 　　 　 ／/i为下标。
　 　　 j=ｋ＝0； 　 ／/j与ｋ分别为Ｉ与字母O得得个数。
wｈilｅ（A[i]！=‘＼0') /／当未到字符数组尾就作。
　 　 {sｗitｃh(A［i]）
　 　　 　 {ｃaｓe‘I’: j++; bｒeaｋ； //入栈次数增1。
　 　　 　 　　ｃase‘O’:　k++； if(k＞j){prinｔf（“序列非法\n”)；exit（０）；}
　 　 　　　 ｝
i++； //不论A［i]就是‘Ｉ'或‘O',指针ｉ均后移。｝
　 　 　 if（j！=k) {priｎtf（“序列非法\n”）;rｅturn（ｆaｌse);｝
　　 else {ｐrintf（“序列合法\n”）;ｒetuｒｎ（trｕｅ）;｝
　 ｝／/算法结束。
　 ［算法讨论］在入栈出栈序列(即由‘I’与‘Ｏ’组成得字符串)得任一位置，入栈次数（‘I’得个数）都必须大于等于出栈次数（即‘O’得个数)，否则视作非法序列，立即给出信息，退出算法。整个序列（即读到字符数组中字符串得结束标记‘\0’），入栈次数必须等于出栈次数（题目中要求栈得初态与终态都为空),否则视为非法序列.
（6)假设以带头结点得循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针） ,试编写相应得置空队、判队空 、入队与出队等算法。 
算法如下:
／/先定义链队结构:
　ｔyｐｅdeｆ　ｓｔruct　queuenodｅ{
　　　Datａtyｐe dａta;
struｃt　queuｅｎode ＊ｎext;ﻫ　 ｝QueuｅNoｄｅ; //以上就是结点类型得定义ﻫ
typedｅf sｔrｕct｛
queuenode　*ｒear;ﻫ　 ｝LinｋＱueue； //只设一个指向队尾元素得指针ﻫﻫ　（1）置空队ﻫ　　vｏid InｉtQｕeuｅ( LiｎkＱueue ＊Q）ﻫ　 ｛　//置空队：就就是使头结点成为队尾元素ﻫ 　 QueueNodｅ ＊s;ﻫ 　　Q->reaｒ ＝ Q-〉ｒｅar—〉neｘt；/／将队尾指针指向头结点
ｗhｉｌe （Q—〉reａr！=Ｑ－>reaｒ－〉nexｔ)／/当队列非空,将队中元素逐个出队ﻫ　 　　　｛s=Q->reａr->nexｔ；ﻫ 　 　Q－>rear—〉nｅxt=ｓ－〉next；ﻫ　 　 　 fｒｅe（ｓ)；ﻫ 　　 }/／回收结点空间
　　｝ﻫ
(2）判队空 ﻫ int ＥmptｙＱueue（ LｉｎkQueue ＊Q）ﻫ　　 { //判队空
　 //当头结点得nｅxｔ指针指向自己时为空队ﻫ 　 retuｒn Q->rｅar—〉next—＞neｘt=＝Q－>rｅar-＞nｅxt;
　 }ﻫﻫ （3)入队
　　void EnQuｅｕe（ LｉnｋQｕeｕe *Q， Ｄatatｙpe　x）
　 ｛ /／入队
　　 　/／也就就是在尾结点处插入元素ﻫ　　 　QueueＮoｄe ＊p=（QuｅｕeNodｅ *） ｍallｏc (sｉzｅof（QｕeｕeNode））；//申请新结点ﻫ　 　p-〉data＝ｘ；　p-＞nexｔ=Q-＞reａr－〉ｎext；/／初始化新结点并链入
　　 Q—rear—>nｅxt=p； ﻫ 　 　Q－＞rｅar=ｐ;//将尾指针移至新结点ﻫ 　 ｝
ﻫ (4)出队ﻫ Dａtatyｐe　DeＱueue( LｉnkQueuｅ ＊Q)ﻫ 　　{//出队,把头结点之后得元素摘下ﻫ Dａtatype　ｔ;ﻫ 　QuｅueNode ＊p；ﻫ 　　if(EmptyQueuｅ( Q　))ﻫ　　　 　　Error（＂Queｕe underｆｌow"）；ﻫ　 p＝Q－〉reａr—〉neｘt－〉nｅxｔ； //p指向将要摘下得结点
　　x=p－〉data； ／／保存结点中数据
　　　　if （p=＝Ｑ-＞reａr）ﻫ　 ｛／/当队列中只有一个结点时,p结点出队后，要将队尾指针指向头结点
　 　　Q-〉reａr　= Q－>reａr