答案《数据结构》试卷

厦门大学?—数据结构—?课程期中试卷信息科学与技术学院计算机科学系2003年级 专业主考教师： 试卷类型：(A卷/B卷)任选5题((1,2),(3,4),(5,6),(7,8)中必须至少做一题)，每题20分一、试设计一个双栈结构，它有两个端点endl和end2,满足从endl端插入的表目只能从endl端被删除，从end2端插入的表目只能从end2端被删除，并给出指定端i(i=1,2)的进栈push(S,e,i和出栈pop(S,e,i)操作的算法描述。再设计一个算法，它能够将一个有限长度的数据序列a1,a2,…，an,按照下标奇偶序号交替的方式将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)和出栈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=*--S.top[1]=e;returnOK;}elseif(i==2){if(S.top[2]==S.base+STACK_SIZE-1)returnERROR;e=*++S.top[2];returnOK;}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;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(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;}}

StatusDeQueue(DataType&x){if!StackEmpty(S2){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=〞bcaacabaca，请给出它的next函数值及nextval函数值。解：在主串中寻找模式的KMP算法的时间复杂度是O(n+m)。模式p=^abcaacabaca,它的next函数值及nextval函数值分别是：j 1 2模式 j 1 2模式 a bnext[j] 0 1nextval[j]0 13 4 5 6 7c a a c a1 1 2 2 11 0 2 2 08 9 10 11b a c a2 3 2 11 3 2 0四、编写算法对读入的一段文字(设以字符“＃〞结束)，统计其中所出现的字符及其频度要求采用双向循环链表存储，每读入一个字符就扫描链表，假设在表中已有该字符，那么其频度增加1，同时调整链表中各结点之间的次序，使其按频度非递增排列，假设表中尚无该字符,那么在表尾插入该字符的一个结点，相应的频度设为1。typedefstructElemType{charkey;unsignedintfreq;}ElemType;typedefstructDuLNode{ElemTypeData;StructDuLNode*prior,*next;}DuLNode,*DuLinkList;//设带头结点，其freq=0StatusStat(DuLinkList&L){getchar(ch);while(ch!='#'{p=L;while((p->next!=L)&&(p->data.key!=ch))p=p->next;if(p->data.key==ch){p->data.freq++;q=p->prior;while((q!=L)&&(q->data.freqvp->data.freq)q=q->prior;if((q!=p->prior)&&(q->data.freq>=p->data.freq){p->prior->next=p->next;p->next->prior=p->prior;p->next=q->next;p->prior=q;q->next=p;p->next->prior=p;}}else{if(!(p=(DuLiinkList)malloc(sizeof(DuLNode))))returnERROR;p->data.key=ch;p->data.freq=1;p->prior=L->prior;p->next=L;L->prior->next=p;L->prior=p;}getchar(ch);}}五、设矩阵A是一个n阶稀疏方阵，下标分别从0到n—1。A中对角线上有t个m阶下三角阵A0、A1、……、At—1〔如以下图〕，且mxt=n。在为矩阵A设计的压缩存储方案中，问用于存储矩阵A的一维数组B的大小？假设将这些下三角阵中的元素以行序为主序存放，设A中某元素a[i][j]存放在b[k]中，试给出求解k的计算公式。〔数组B的下标也从0开始〕一维数组B的大小为(1+m)/2*m*t=(1+m)*n/2k丄m(m1)/2(iMODm1)iMODm/2jMODmm六、对下面给出的广义表做：(1)给出广义表的数据结构(2)画出以下广义表的存储结构图(3)利用取表头和表尾的操别离出原子e(给出GetHeadGetTail的操作序列)(a,((),b),(((e))))答：(1)广义表有两种存储结构，头尾链和扩展线性链(写出其中一个即可)头尾链typedefenum{ATOM,LIST}ElemTag;typedefstructGLNode{ElemTagtag;union{AtomTypeatom;struct{structGLNode*hp,*tp;}ptr;};}*GList扩展线性链typedefenum{ATOM,LIST}ElemTag;typedefstructGLNode{ElemTagtag;union{AtomTypeatom;structGLNode*hp;};structGLNode*tp;}*GList(2)两种存储结构下的存储结构图如下(只要写出对应的一种即可) ：头尾链(a,(().b),(((e)))) ((().b),(((e))))10a10b((((e))))(((e)))((e))(e)0e扩展线性链(a,(().b),(((e)))) ((().b),(((e))))10a10b((((e))))(((e)))((e))(e)0e扩展线性链((e))(e)(3)别离出来的序列为：GetHead(GetHead(GetHead(GetHead(GetTail(GetTail(L))))))七、编写算法求二叉树中任意两个结点最近的共同祖先，并分析算法的时间复杂性。自然语言描述:1．[初始化]获取二叉树T，任意两结点P，Q2．[查找到任意两点的路径]使用递归算法做：A•假设树根为结点P,那么返回。B.记录当前树根为路径中的一点。C.递归遍历树根的左子树D.递归遍历树根的右子树E.假设左右子树中都找不到，那么从路径中删除树根结点[查找最近祖先]遍历树根到结点P和Q的路径，找到两条路径上最后一个相同结点，该结点为最近祖先[算法结束]程序描述：intfound=FALSE;Bitree*Find_Near_Ancient(BitreeT,Bitreep,Bitreeq)//求二叉树T中结点p和q的最近共同祖先{Bitreepathp[100],pathq[100]//设立两个辅助数组暂存从根到p,q的路径Findpath(T,p,pathp,0);found=FALSE;Findpath(T,q,pathq,0);//求从根到p,q的路径放在pathp和pathq中for(i=0;pathp[i]==pathq[i]&&pathp[i];i++);//查找两条路径上最后一个相同结点returnpathp[--i];}//Find_Near_AncientvoidFindpath(BitreeT,Bitreep,Bitreepath[],inti)//求从T到p路径的递归算法{if(T==p){found=TRUE;return;//找到}path[i]=T;//当前结点存入路径if(T->lchild)Findpath(T->lchild,p,path,i+1);//在左子树中继续寻找if(T->rchild&&!found)Findpath(T->rchild,p,path,i+1);//在右子树中继续寻找if(!found)path[i]=NULL;//回溯}//Findpath算法复杂性分析：算法中Findpath的时间复杂性为：0(n)(因为最坏情况下需要遍历所有的二叉树结点)查找最后一个相同结点的复杂性为：O(n)(因为最坏情况下路径为二叉树所有结点)所以算法的时间复杂性为：0(n)八、编写算法判断一棵用二叉链表存储的二叉树是否为完全二叉树。自然语言描述：[初始化]初始化一个队列Q,将二叉树的根结点入队，置flag=O表示未发现存在某个结点的孩子为空；[按层序遍历二叉树，并相应修改flag]循环直到队列为空将队首结点出队；假设该结点有左子树且flag=O，那么将左子树的根结点入队；假设该结点无左子树且 flag=O，那么flag=1；假设该结点有左子树且flag=1，那么不是完全二叉树，退出；假设该结点有右子树且flag=O，那么将右子树的根结点入队；假设该结点无右子树且 flag=O，那么flag=1；假设该结点有右子树且flag=1，那么不是完全二叉树，退出；[算法