资源描述：
《答案《数据结构》试卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、厦门大学《＿数据结构＿》课程期中试卷信息科学与技术学院计算机科学系2003年级＿＿＿专业主考教师：＿＿＿＿试卷类型：（A卷/B卷）任选5题（（1，2），（3，4），（5，6），（7，8）中必须至少做一题），每题20分。一、试设计一个双栈结构，它有两个端点end1和end2，满足从end1端插入的表目只能从end1端被删除，从end2端插入的表目只能从end2端被删除，并给出指定端i（i=1，2）的进栈push(S,e,i)和出栈pop(S,e,i)操作的算法描述。再设计一个算法，它能够将一个有限长度的数据序列a1，a2，…，a
2、n，按照下标奇偶序号交替的方式将ai(1≤i≤n)分别从两端入栈，然后将数据出栈以实现整个数据序列的倒排。该双栈宜采用顺序存储、栈顶迎面增长的存储方式，其形式定义如下：#defineSTACK_SIZE1000typedefstruct{SElemTypebase[STACK_SIZE];SElemType*top[3];//top[1]表示end1端的栈顶指针，top[2]表示end2端的栈顶指针//初始值分别为base和base+STACK_SIZE-1}DSqStack;指定端i（i=1，2）的进栈push(S,e,i)
3、和出栈pop(S,e,i)操作的算法描述如下：Statuspush(DSqStack&S,SElemTypee,inti){if(S.top[1]-S.top[2]==1)//栈满exit(OVERFLOW);elseif(i==1)*S.top[1]++=e;elseif(i==2)*S.top[2]--=e;elsereturnERROR;returnOK;}Statuspop(DSqStack&S,SElemType&e,inti){if(i==1){if(S.top[1]==S.base)returnERROR;e=*
4、--S.top[1]=e;returnOK;}elseif(i==2){if(S.top[2]==S.base+STACK_SIZE-1)returnERROR;e=*++S.top[2];8returnOK;}elsereturnERROR;}基于上述结构的数据序列的倒排算法描述如下：Statusresevers(DSqStack&S,SElemTypea[],intn){for(j=1;j<=n;j++)if(j%2==0)push(S,a[j-1],2);elsepush(S,a[j-1],1);for(j--;j>=1
5、;j--)if(j%2==0)pop(S,a[n-j],2);elsepop(S,a[n-j],1);returnOK;}二、利用两个栈S1、S2模拟一个队列（如客户队列）时，如何用栈的运算实现队列的插入、删除运算。使用算法描述。解：利用两个栈S1、S2模拟一个队列（如客户队列）时，当需要向队列中输入元素时，用S1来存放输入元素，用push运算实现。当需要从队列中输出元素时，到栈S2中去取，如果S2为空，则将S1中的元素全部送入到S2中，然后再从S2中输出元素。判断队空的条件是：S1和S2同时为空。StatusEnQueue(
6、DataTypex){ifStackFull(S1){//S1栈满ifStackEmpty(S2){//S1栈满，S2栈空while(!StackEmpty(S1)){Pop(S1,y);Push(S2,y);//栈S1的内容反向搬到栈S2Push(S1,x);returnOK;}else//S1栈满，S2栈非空，则不可进行插入操作returnERROR；}else{ //S1栈不满，则直接进栈Push(S1,x);returnOK;}}8StatusDeQueue(DataType&x){if!StackEmpty(S2)
7、{Pop(S2,x);returnOK;}else{if!StackEmpty(S1){while(!StackEmpty(S1)){Pop(S1,y);Push(S2,y);}//栈S1的内容反向搬到栈S2Pop(S2,x);returnOK;}else//栈S1和S2都为空returnERROR;}}三、模式匹配算法是在主串中快速寻找模式的一种有效的方法。如果设主串的长度为m，模式串的长度为n，则在主串中寻找模式的KMP算法的时间复杂性是多少？如果某一模式p=”abcaacabaca”，请给出它的next函数值及nextv
8、al函数值。解：在主串中寻找模式的KMP算法的时间复杂度是O（n+m）。模式p=”abcaacabaca”，它的next函数值及nextval函数值分别是：j1234567891011模式abcaacabacanext[j]01112212321nextval[j]01102
