数据结构作业和答案1.doc

第二章 2.22 试写一算法,对单链表实现就地逆置,即利用原表的存储空间将线性表 （a1,a2,…,an）逆置为（an,an-1,…,a1） 提示：将原链表中的头结点和第一个元素结点断开（令其指针域为空），先构成一个空表，然后将原链表中各结点从第一个结点起依次插入这个新表的头部。 答：void LinkList_reverse(Linklist L)//链表的就地逆置;为简化算法,假设表长大于2{??p=L-next;q=p-next;s=q-next;p-next=NULL;??while(s-next)??{????q-next=p;p=q;????q=s;s=s-next; //把L的元素逐个插入新表表头??}??q-next=p;s-next=q;L-next=s;}//LinkList_reverse分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头. 第三章 3.1 设将整数1、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问题： （1）若入栈次序为push(1)，pop()，push(2），push(3)，pop()，pop( )，push(4)，pop( )，则出栈的数字序列为什么？ (2) 能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。 答：(1)1 3 2 4 后进先出，先进后出(2) 1423无法得到，因为只能这样操作，Push(1), Pop(), Push(2), Push(3), Push(4), Pop(),Pop(), Pop(),结果序列是1432 3.12 写出以下程序段的输出结果（队列中的元素类型QElemType 为char）。 Void main( ){ Queue Q; InitQueue(Q); Char x=‘e’, y=‘c’; EnQueue(Q, ‘h’); EnQueue(Q, ‘r’); EnQueue(Q, y); DeQueue(Q, x); EnQueue(Q, x); DeQueue(Q, x); EnQueue(Q, ‘a’); While ( !QueueEmpty(Q) ){ DeQueue(Q, y); Printf(y); } Printf(x); } 答：输出结果是 char。EnQueue (Q,’h’); EnQueue (Q,’r’); EnQueue (Q, y); //hrc入队此时 HYPERLINK /search?word=%E9%98%9F%E5%88%97fr=qb_search_expie=utf8 \t _blank 队列是 hrc(h是头)DeQueue (Q,x); EnQueue (Q,x); //h赋给x出队，然后x再入队此时x=h即h入队,此时 HYPERLINK /search?word=%E9%98%9F%E5%88%97fr=qb_search_expie=utf8 \t _blank 队列是‘rch’。DeQueue (Q,x); EnQueue (Q,’a’); //‘r’赋给x出队，‘a’入队，此时 HYPERLINK /search?word=%E9%98%9F%E5%88%97fr=qb_search_expie=utf8 \t _blank 队列是‘cha’while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y);}; //当队列不为空时依次把队列中元素赋给y出列，并打印。此时打印出的是chaPrintf(x); //打印x的值就是前面赋给x的‘r’ 所以打印出的是 char 第四章 4.3 设 s=‘I AM A STUDENT’，t=‘GOOD’， q=‘WORKER’，求： （1） StrLength(s)，StrLength(t) （2） SubString(s, 8, 7) ，SubString(t, 2, 1) （3） Index(s, ‘A’,1)，Index(s,t,3) （4） Replace(s, ‘STUDENT’, q) （5） Concat(SubString(s,6,2),Concat(t,SubString(s,7,8))) 答： 1) 14，4 2) STUDENT，O 3) 3，0 4) I AM A WORK