答案:(1)ｓ-〉next＝p-〉next （2）p->neｘt=s
３、函数ListDeletｅ＿sq实现顺序表删除算法,请在空格处将算法补充完整.
inｔ ListDelete＿sq(Ｓqlist *L,int ｉ）｛ iｎt k；
iｆ(i＜1｜|ｉ>L—>lengtｈ） reｔurｎ ERROＲ;
for(k=i-1;k〈L-〉lenｇｔh—１;k++)
L-〉sliｓt［k]= (１） ;
（２) ; reｔurn OK； ｝
答案:(1)L－〉ｓlist［k＋1] （２) ——Ｌ－〉Lenｇｔｈ 4、函数实现单链表得删除算法，请在空格处将算法补充完整。
int LisｔDｅlｅｔe(LinkＬｉst L，int i,ＥlemＴype *s)｛ LNode ＊p,＊q； ｉnt j; ｐ=L;j＝0；
ｗhilｅ（( (1) )＆＆(j〈ｉ-１）){ p=p-〉neｘt;j++； }
ｉｆ(p—〉nexｔ＝=NULＬ|｜j＞ｉ－1) rｅｔurｎ ＥＲROR; q=p－〉ｎeｘt； (2) ; *s=q-〉dａｔa; fｒee（ｑ)； returｎ ＯＫ; }/*listDeｌｅte*／
答案:(1）p—〉next!=NULL (2)ｐ—〉ｎｅxt=ｑ—＞next 5、写出算法得功能.
ｉｎｔ Ｌ(hｅad）｛ ?node * head； ?int ｎ=0； nｏde *p; ??p＝heａd；
??while(p！=ＮULL） ?{ p=p－〉neｘt; ?? n＋+； ? }
??ｒetｕrn(ｎ)； ?}
答案:求单链表ｈｅaｄ得长度 五、综合题
１、编写算法,实现带头结点单链表得逆置算法． 答案:void invｅｎt（Ｌnode ＊head）
｛Lnodｅ *p,*q；
iｆ(!hｅad-＞next） rｅturn ERROR;
ｐ=heａｄ—〉next; q＝ｐ—〉next； p—〉neｘt ＝ＮULＬ; ｗhｉle（q)
{p=q; q=ｑ—〉ｎeｘt; p->next＝hｅad—〉nexｔ; head—〉nexｔ=ｐ;｝ ｝
２、有两个循环链表,链头指针分别为Ｌ１与L2,要求写出算法将L２链表链到Ｌ1链表之后,且连接后仍保持循环链表形式。
答案：ｖoｉd mergｅ（Ｌnode ＊L1, Lnoｄe *Ｌ2)
{Lｎodｅ *p,＊q ；
ｗhile(p->next！＝Ｌ1)
p=p－＞next;
while（ｑ->next！＝Ｌ2)
q=q-〉next;
q－>neｘt=L１; ｐ—〉next =L2； }
3、设一个带头结点得单向链表得头指针为heａd,设计算法,将链表得记录,按照ｄaｔa域得值递增排序。
答案：voｉｄ aｓsendｉnｇ(Lnｏde *head)
{Lnode ＊p,＊q , ＊r, *ｓ;
p=heａd-〉ｎｅxt； ｑ＝p—〉neｘt; p—＞next＝ＮULL; whiｌｅ（q）
｛r=q； q=q-〉nｅxｔ;
if(ｒ-〉ｄata<=ｐ-〉datａ)
｛ｒ->nｅxt=p; heaｄ-〉neｘt=r; p=r; } ｅlｓｅ
{whｉle(！p &＆ ｒ－＞data〉ｐ－〉datａ）
{s=p; p=p—〉nexｔ； } ｒ—>next＝ｐ; s—〉next=r;} p＝head-＞next； }
}
４、编写算法,将一个头指针为hｅad不带头结点得单链表改造为一个单向循环链表，并分析算法得时间复杂度。 答案:
ｖoid liｎｋlist_c(Lnode ＊head） {Ｌnodｅ ＊p； ｐ=heaｄ； if(!p) return ERＲＯR；
ｗｈｉle(p-〉ｎext！=NUＬL）
p=ｐ->neｘｔ； ｐ—〉ｎext＝heａd; ｝
设单链表得长度（数据结点数）为N，则该算法得时间主要花费在查找链表最后一个结点上（算法中得while循环）,所以该算法得时间复杂度为O（N)．
５、已知heaｄ为带头结点得单循环链表得头指针,链表中得数据元素依次为（a１,ａ２,ａ3,a4,…,an)，A为指向空得顺序表得指针。阅读以下程序段，并回答问题: (１)写出执行下列程序段后得顺序表Ａ中得数据元素； (2)简要叙述该程序段得功能。
if（ｈead->ｎｅｘt！=head) ｛
p=head—＞ｎext; A—>ｌengｔh=0；
wｈiｌe(p—〉next！＝heａd) {
p＝p—〉nexｔ;
A—〉data[A－>lｅｎgth +＋]=p—〉data; if（p－＞nexｔ！=ｈead)p=ｐ—>neｘt； }
｝ 答案：
（1） (a2， a4, …, ) （2)将循环单链表中偶数结点位置得元素值写入顺序表A
6、设顺序表va中得数据元数递增有序。试写一算法,将x插入到顺序表得适当位置上，以保持该表得有序性。 答案:
void Insert_ｓq（Sqｌist va［], ＥlemType ｘ) {inｔ ｉ, ｊ, n； ｎ＝ｌeｎgth(va［］); if（x＞＝vａ[i］）
va［n]=x； elｓe
｛i＝0;
wｈile（x〉va[i］) i++; for(ｊ＝n—１；j>=I；ｊ--)
va[ｊ＋1]＝va［j］； va[i]=x； } n++; }
7、假设线性表采用顺序存储结构，表中元素值为整型。阅读算法f2,设顺序表L=(3,７,３,２，1，1,8，７,３),写出执行算法ｆ2后得线性表L得数据元素,并描述该算法得功能。
void f2(ＳeqLiｓt *L）{
int i,j，k; k=0;
for(ｉ=０;i〈L—>lｅnｇth;i++){
ｆoｒ(ｊ=0;ｊ
?? if(ｊ==ｋ）{
ｉf（k!=i)L—>data［ｋ］＝Ｌ—〉ｄａｔａ［ｉ];
???k++; ? }
｝
Ｌ-〉length=k； }
答案:
(3,7,2,1,8） 删除顺序表中重复得元素
8、已知线性表中得元素以值递增有序排列,并以单链表作存储结构。试写一算法,删除表中所有大于x且小于ｙ得元素（若表中存在这样得元素)同时释放被删除结点空间。 答案：
voｉｄ Delｅte_list（Lnｏde *hｅaｄ， ＥｌemＴype x, ＥleｍTyｐｅ y) ｛Lnoｄe *ｐ， ＊q; if(!hｅad） return ERROR；
p=hｅａd; q=p; while(!p）
{iｆ（ｐ->datａ>x） &＆ (p—＞daｔa ｉf(p==heａd） ｛hｅaｄ=ｐ—〉next; ｆｒee（p)； ｐ＝ｈｅad； ｑ=p; } ｅlｓe ｛q->next＝p->neｘt; ｆree(ｐ)； ｐ＝ｑ—＞ｎext； } else ｛q=p; ｐ＝p->nｅxt; ｝ ｝ } 9、在带头结点得循环链表L中,结点得数据元素为整型,且按值递增有序存放。给定两个整数ａ与ｂ，且ａ〈b，编写算法删除链表Ｌ中元素值大于a且小于b得所有结点。 第三章 栈与队列 一、选择题 1、一个栈得输入序列为:a,ｂ,c,d，e,则栈得不可能输出得序列就是( ）。 A、 a,ｂ,ｃ,ｄ,ｅ Ｂ、 d,e,c，b,ａ ? C、 ｄ,c，e,a,ｂ ?D、 e,ｄ,c，ｂ,ａ 2、判断一个循环队列Q(最多n个元素）为满得条件就是（ ）。 A、 Q->rear＝=Q－〉fronｔ ?? B、 Q—〉reaｒ==Q－〉ｆｒoｎt＋１ Ｃ、 Q—>froｎt==(Q—〉rear+1）%n? ??Ｄ、 Q->ｆｒｏnt==(Q->rｅａr—1）%n ３、设计一个判别表达式中括号就是否配对得算法，采用( ）数据结构最佳。 A、 顺序表 Ｂ、 链表 ? ?C、 队列 D、 栈 4、带头结点得单链表head为空得判定条件就是( ). A、 hｅad==NULL ?B、 ｈｅａｄ—>next＝=ＮUＬL?? C、 heａｄ-〉ｎext！＝NULL ?D、 hｅaｄ!=NＵLＬ ５、一个栈得输入序列为:1,２,3，４,则栈得不可能输出得序列就是( )。 A、 １2４3 B、 ２１３4 ? C、 143２ D、 ４３１２? E、 ３21４ 6、若用一个大小为６得数组来实现循环队列,且当rear与frｏnt得值分别为0,3。当从队列中删除一个元素，再加入两个元素后，rear与froｎt得值分别为( ）。 A、 1与５ ? B、 2与4 ??Ｃ、 4与２? D、 ５与1 7、队列得插入操作就是在( ）。 A、 队尾?? ?Ｂ、 队头 ??C、 队列任意位置 D、 队头元素后 8、循环队列得队头与队尾指针分别为fｒonｔ与reａr,则判断循环队列为空得条件就是( )。 Ａ、 front=＝rear?? B、 fｒont==０ C、 reａr＝=0? ? Ｄ、 front=rear+１ 9、一个顺序栈Ｓ,其栈顶指针为ｔｏp,则将元素e入栈得操作就是( )。 A、 *Ｓ－>ｔoｐ=e;S－〉ｔop++； ??B、 S-＞tｏp+＋;＊S-〉top=e; C、 *S—>top=e ? ??Ｄ、 S-＞tｏｐ=e; １0、表达式a*(b+c）-d得后缀表达式就是（ )。 A、 abcd＋- Ｂ、 ａbｃ+*ｄ-? Ｃ、 aｂc＊+d— ?D、 —+*abcd 11、将递归算法转换成对应得非递归算法时,通常需要使用（ )来保存中间结果。 A、 队列 ?Ｂ、 栈 C、 链表 ? Ｄ、 树 12、栈得插入与删除操作在（ ). Ａ、 栈底 B、 栈顶 C、 任意位置 ?Ｄ、 指定位置 １3、五节车厢以编号1,2,3,4,5顺序进入铁路调度站(栈),可以得到（ )得编组。 A、 3，4，5,１,2? B、 2,4,１，3，５ ? Ｃ、 ３,5,4,2，1 ??D、 1，３，５,2，4 １４、判定一个顺序栈S(栈空间大小为n)为空得条件就是( )。 Ａ、 Ｓ—>top==０ ? B、 S->tｏp!=0? C、 Ｓ->tｏp＝=ｎ? ?D、 S—〉top!＝n 15、在一个链队列中,ｆront与reaｒ分别为头指针与尾指针,则插入一个结点s得操作为( ）。 A、 ｆront=front—＞ｎeｘt ? Ｂ、 s->nexｔ=rear；rear=s Ｃ、 rear—〉ｎeｘｔ＝s；rear=s;? D、 s-〉next=fｒonｔ;fronｔ=s; 16、一个队列得入队序列就是1,2,3，４,则队列得出队序列就是（ )。 ?A、 １,２，3，４ ? B、 4,3,2，1 C、 1,4,３,2 ???D、 ３,４,1,2 17、依次在初始为空得队列中插入元素a，ｂ,c,d以后,紧接着做了两次删除操作，此时得队头元素就是( ). A、 ａ B、 b ? ?C、 c ? ?D、 ｄ 1８、正常情况下，删除非空得顺序存储结构得堆栈得栈顶元素,栈顶指针top得变化就是( )。 A、 ｔop不变 ? B、 ｔｏp=0 C、 toｐ=toｐ+1? D、 ｔop=toｐ-1 1９、判断一个循环队列Ｑ(空间大小为M）为空得条件就是( )。 Ａ、 Q->froｎｔ==Q—〉rｅar ?B、 Ｑ－〉rear-Q-〉fｒoｎt－1＝＝M? ? Ｃ、 Q—〉ｆroｎｔ+1=Q－〉rear ??D、 Q-〉rｅar+1=Q—〉fronｔ ２０、设计一个判别表达式中左右括号就是否配对出现得算法,采用（ )数据结构最佳。 A、 线性表得顺序存储结构 B、 队列??Ｃ、 栈 ?D、 线性表得链式存储结构 21、当用大小为N得数组存储顺序循环队列时，该队列得最大长度为（ )。 A、 N ? Ｂ、 N+1???C、 N-1 ?D、 N-2 22、队列得删除操作就是在( ）。 A、 队首 ? ?Ｂ、 队尾 ? C、 队前? ?D、 队后 2３、若让元素1,2,3依次进栈,则出栈次序不可能就是( )。 A、 ３，2，1 ??B、 2,1,3 C、 3,1,2 ??D、 1，3,2 ２4、循环队列用数组A[0,m—1]存放其元素值，已知其头尾指针分别就是fｒoｎt与rear,则当前队列中得元素个数就是( ）。 ?A、 (rear-fｒoｎt+m）%m? ?Ｂ、 ｒeaｒ—fronｔ+１ ? C、 rｅar-front-1????Ｄ、 ｒear－fｒoｎt 25、在解决计算机主机与打印机之间速度不匹配问题时,通常设置一个打印数据缓冲区,主机将要输出得数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该就是一个( )结构。 Ａ、 堆栈 ?B、 队列 ?Ｃ、 数组 ?? Ｄ、 线性表 26、栈与队列都就是( )． Ａ、 链式存储得线性结构 ? B、 链式存储得非线性结构 C、 限制存取点得线性结构 ? Ｄ、 限制存取点得非线性结构 27、在一个链队列中，假定froｎt与rear分别为队头指针与队尾指针,删除一个结点得操作就是（ ). A、 front=froｎt—〉ｎext B、 reａr= rear—〉neｘｔ ? C、 rｅaｒ—〉next＝ｆｒｏnｔ?? D、 front—＞next=ｒｅaｒ 28、队与栈得主要区别就是( )。 A、 逻辑结构不同 ? ?B、 存储结构不同 C、 所包含得运算个数不同 ? Ｄ、 限定插入与删除得位置不同 二、填空题 1、设栈S与队列Q得初始状态为空，元素e1，e2,ｅ3,e４，e5,e6依次通过栈Ｓ,一个元素出栈后即进入队列Ｑ,若6个元素出队得序列就是e２,ｅ4,e３，ｅ6,e5,e１，则栈得容量至少应该就是 。 答案:3 2、一个循环队列Ｑ得存储空间大小为Ｍ,其队头与队尾指针分别为ｆront与reaｒ,则循环队列中元素得个数为: 。 答案：(reａr—fｒont+M)%M 3、在具有n个元素得循环队列中,队满时具有 个元素。 答案：ｎ-1 4、设循环队列得容量为70，现经过一系列得入队与出队操作后,frｏnt为２0，reａr为１1，则队列中元素得个数为 . 答案：61 ５、已知循环队列得存储空间大小为20，且当前队列得头指针与尾指针得值分别为8与3，且该队列得当前得长度为＿______. 三、判断题 1、栈与队列都就是受限得线性结构。? 2、在单链表中，要访问某个结点,只要知道该结点得地址即可;因此，单链表就是一种随机存取结构.? ３、以链表作为栈得存储结构，出栈操作必须判别栈空得情况．? 四、程序分析填空题 1、已知栈得基本操作函数: ?int IniｔSｔack(SqＳtack *Ｓ）; //构造空栈 iｎｔ StackEmpty(ＳqSｔack *S）;//判断栈空 int Ｐush(SｑStacｋ *S，EｌｅmTｙpe ｅ）；/／入栈
数据结构试题库及答案
