数据结构课后答案邹岚

填空题数据元素关系逻辑结构物理结构顺序存储链式存储索引存储哈希存储线性结构树图集合数据描述操作声名联系图树数据元素数据元素有穷性确定性可行性输入输出正确性可读性健壮性效率与存储量的要求O（n）时间空间O（n）O（m*n）O（n）时间复杂度空间复杂度选择题1-5BACAD6-10BCCB11-15BBACB16-20BDDAA21-23ACB判断题FT简答题1、数据的逻辑结构分为线性结构和非线性结构；常用的存储方式有顺序存储、链式存储、索引存储和哈希存储2、例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录(有姓名，学号，成绩等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构。那么我们怎样把这个表中的数据存储到计算机里呢?用高级语言如何表示各结点之间的关系呢?是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢?这就是存储结构的问题，我们都是从高级语言的层次来讨论这个问题的。最后，我们有了这个表(数据结构)，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。3、算法是描述求特定问题而规定的一系列操作步骤集合。特性包括：有穷性、确定性、可行性、有零个或多个输入，有一个或多个输出。4、a—b—c—d—e—f—g—h线性结构(2)树形结构dagbhef（3）图型结构5、解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。6、解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。7、解：8、解：(1)n-1(2)n-1(3)n-1(4)n+(n-1)+(n-2)+...+1=(5)1+(1+2)+(1+2+3)+...+(1+2+3+...+n)===(6)n(7)向下取整(8)1100程序算法题（1）O(n)（2）O(n)（3）O(1)2、解：intmax3(intx,inty,intz){ if(x>y) if(x>z)returnx; elsereturnz; else if(y>z)returny; elsereturnz;}选择题1-5CBABA6-10CACCC11-15ACBCC16-20ABBDD21-25DCADC26-30BBDDA31C判断题1-5FFFFF6-10FFTFT11-15TTFFF16F三综合应用题1、(1)EmemtypeDelete(Elemtypea[],int&Length){Elemtypetag=0;Elemtypemin;if(Length==0)returnERROR;for(inti=1;i<Length-1;i++){if(a[tag]>a[i])tag=i;}min=a[tag];a[tag]=a[Length-1];Length--;returnmin;}(2)StatusListDelete_Sq(SqList*LA,inti,ElemType*e){/*在顺序线性表L中删除第i个元素，并用e返回其值//i的合法值为1≤i≤Listlength_Sq(L)*/ElemType*q,*p;intn=0;/*定义局部变量*/if((i<1)||(i>(*LA).length))returnERROR;/*i值不合法*/p=&((*LA).elem[i-1]);/*p为被删除元素的位置*/*e=*p;/*被删除元素的值赋给e*/q=(*LA).elem+(*LA).length-1;/*表尾元素的位置*/for(++p;p<=q;++p){*(p-1)=*p;++n;}/*被删除元素之后的元素左移*/printf("n=%d\n",n);--(*LA).length;/*表长减1*/returnOK;}(3)StatusListInsert_Sq(SqList*LA,inti,ElemTypee){/*在顺序线性表L中第i个位置之前插入新的元素e,//i的合法值为1≤i≤Listlength_Sq(L)+1*/ElemType*newbase,*q,*p;intn=0;/*定义局部变量*/if(i<1||i>(*LA).length+1)returnERROR;/*值不合法*/if((*LA).length>=(*LA).listsize){/*当前空间已满，增加分配*/newbase=(ElemType*)realloc((*LA).elem,((*LA).listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);/*存储分配失败*/(*LA).elem=newbase;/*新基址*/(*LA).listsize+=LISTINCREMENT;}/*增加存储容量*/q=&((*LA).elem[i-1]);/*q为插入位置*/for(p=&((*LA).elem[(*LA).length-1]);p>=q;--p){*(p+1)=*p;++n;}/*插入位置及之后的元素右移*/printf("n=%d\n",n);*q=e;/*插入e*/++(*LA).length;returnOK;}4、voiddel_x(Sqlist&L,Elemtypex){ intk=0; for(i=0;i<L.length;i++) if(L.data[i]!=x) { L.data[k]=L.data[i]; k++; } L.length=k;}（5）boolDel_s_t(sqList&L,Elemtypes,Elemtypet){ inti,k=0; if(L.length==0||s>=t) returnfalse; for(i=0;i<L.length;i++) { if(L.data[i]>=s&&L.data[i]<=t) k++; else L.data[i-k]=L.data[i]; } L.length-=k; returntrue;}（6）boolDel_s_t(sqList&L,Elemtypes,Elemtypet){ inti,j; if(L.length==0||s>=t) returnfalse; for(i=0;i<L.length&&L.data[i]<s;i++); if(i>=L.length) returnfalse; for(j=i;j<L.length&&L.data[j]<=t;j++); for(;j<L.length;i++,j++) L.data[i]=L.data[j] L.length=i; returntrue;}（7）boolMerge(SqListA,SqListb,SqList&c){ if(A.length+B.length>C.maxSize) returnfalse; inti=0,j=0,k=0; while(i<A.length&&j<B.length) { if(A.data[i]<=B.data[j]) C.data[k++]=A.data[i++]; else C.data[k++]=B.data[j++]; } while(i<A.length) C.data[k++]=A.data[i++]; while(j<B.length) C.data[k++]=B.data[j++]; C.length=k; returntrue;}（8）boolDelete_Same(SqList&L){ if(L.length==0) returnfalse; inti,j; for(i=0,j=1;j<L.length;j++) if(L.data[i]<L.data[j]) L.data[++i]=L.data[j]; L.length=i+1;}2、LinkedListinvert(LinkedListL){p=L->next；∥p为工作指针。L->next=null；∥第一结点成为尾结点。while（p!=null）{r=p->next；p->next=L；∥将p结点插到L结点前面。L=p；∥L指向新的链表“第一”元素结点。p=r；}returnL;}3、LinkListreverse(LinkList&L)//带头结点单链表的就地逆置{ p=L->next; L->next=null; while(p!=NULL) { r=p->next; p->next=L->next; L->next=p; p=r; } returnL;}4、voidMiniValue(LinkedListla){∥la是数据域为正整数且无序的单链表，本算法查找最小值结点且打印。∥若最小值结点的数值是奇数，则与后继结点值交换；否则，就删除其直接后继结点。p=la->next；∥设la是头结点的头指针，p为工作指针。pre=p；∥pre指向最小值结点，初始假定首元结点值最小。while(p->next!=null){∥p->next是待比较的当前结点。if（p->next->data<pre->data）pre=p->next；p=p->next；∥后移指针}printf(“最小值=%d\n”,pre->data)；if(pre->data%2!=0)∥处理奇数if(pre->next!=null){∥若该结点没有后继，则不必交换t=pre->data；pre->data=pre->next->data；pre->next->data=t；}∥交换完毕else∥处理偶数情况if(pre->next!=null){∥若最小值结点是最后一个结点，则无后继u=pre->next；pre->next=u->next；free(u)；}∥释放后继结点空间}5、解法如下：假定链表结点类型如下;structnode{ intdata; node*next;};voidsort(node*head){ node*p=head->next; while(p) { node*q=p->next; while(q) { if(q->data<p->data)//把小的选出来放在前面 { head->data=p->data; p->data=q->data; q->data=head->data; } q=q->next; } p=p->next; }}6、LinkedListUnion(LinkedListla,LinkedListlb){∥la,lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算法将两链表合并成一个按元素值递减次序排列的单链表。pa=la->next;pb=lb->next;∥pa，pb分别是链表la和lb的工作指针la->next=null;∥la作结果链表的头指针，先将结果链表初始化为空。while(pa!=null&&pb!=null)∥当两链表均不为空时作if(pa->data<=pb->data){r=pa->next;∥将pa的后继结点暂存于r。pa->next=la->next;∥将pa结点链于结果表中，同时逆置。la->next=pa;pa=r;∥恢复pa为当前待比较结点。}else{r=pb->next;∥将pb的后继结点暂存于r。pb->next=la->next;∥将pb结点链于结果表中，同时逆置。la->next=pb;pb=r;∥恢复pb为当前待比较结点。}while(pa!=null){∥将la表的剩余部分链入结果表，并逆置。r=pa->next;pa->next=la->next;la->next=pa;pa=r;}while(pb!=null){r=pb->next;pb->next=la->next;la->next=pb;pb=r;}returnla;}7、voidDel_Same(LinkList&L){ LNode*p=L->next,*q; while(p->next!=null) { q=p->next; if(p->data==q->data) { p->next=q->next; free(q); } else p=p->next; }}8、LinkedListDelete（LinkedListL）

∥L是带头结点的单链表，本算法删除其最小值结点。

{p=L->next；∥p为工作指针。指向待处理的结点。假定链表非空。

pre=L；∥pre指向最小值结点的前驱。

q=p；∥q指向最小值结点，初始假定第一元素结点是最小值结点。

while（p->next!=null）

{if（p->next->data<q->data）{pre=p；q=p->next；}∥查最小值结点

p=p->next；∥指针后移。

}

pre->next=q->next；∥从链表上删除最小值结点

free（q）；∥释放最小值结点空间

}∥结束算法delete。9、voidFun(Node**heada,Node**headb,inti,intj,intlen)

{

Node*p,*q,*r;

p=*heada;

q=*heada;

intn=1;

while(n++<i)

p=p->next;

q=p->next;

n=0;

while(n++<len&&q)

q=q->next;

r=p->next;

p->next=q->next;

q->next=NULL;

n=1;

p=*headb;

while(n++<j)

p=p->next;

q->next=p->next;

p->next=r;

}10、LinkedListdelinsert(LinkedListlist)

{

p=list->link;

pre=list;

q=p;

while(p->link!=null)

{

if(p->link->data<q->data)

{

pre=p;q=p->link;

}

if(q!=list->link)

{

pre->link=q->link;

q->link=list->link;

list->link=q;

}

}

}11、LinkedListUnion(LinkedListha,hb)//线性表A和B代表两个集合，以链式存储结构存储，元素递增有序。ha和hb分别是其链表的头指针。本算法求A和B的并集//AuB,仍用线性表表示，结果链表元素也是递增有序{pa=ha->next;pb=hb->next;//设工作指针pa和pb pc=ha;//pb为结果链表当前结点的前驱指针while(pa&&pb) if(pa->data<pb->data) {pc->next=pa;pc=pa;pa=pa->next;} elseif(pa->data>pb->data) { pc->next=pb;pc=pb;pb=pb->next; } else//处理pa->data=pb->data {pc->next=pa;pc=pa;pa=pa->next;u=pb;pb=pb->next;free(u);} if(pa) pc->next=pa;//若ha表未空，则链入结果表。 elsepc->next=pb;//若hb表未空，则链入结果表 free(hb);//释放hb头结点 return(ha);}12、LinkedListUnion(LinkedListla,LinkedListlb){pa=la->next;pb=lb->next;∥设工作指针pa和pb；pc=la;∥结果表中当前合并结点的前驱的指针。while(pa&&pb){if(pa->data==pb->data){∥交集并入结果表中。pc->next=pa;pc=pa;pa=pa->next;u=pb;pb=pb->next;free(u);}elseif(pa->data<pb->data){u=pa;pa=pa->next;free(u);}else{u=pb;pb=pb->next;free(u);}}while(pa){u=pa;pa=pa->next;free(u);∥释放结点空间}while(pb){u=pb;pb=pb->next;free(u);∥释放结点空间}pc->next=null;∥置链表尾标记。free(lb);∥注：本算法中也可对B表不作释放空间的处理returnla;}13、算法的基本设计思想：对两个链表进行归并，但当A的一个元素，不是B中的一个元素时，才将其加入到新链表C中。算法的代码：NODE*difference(NODE*A,NODE*B){NODE*C,*last；C=last=(NODE*)malloc(sizeof(NODE))；while(A!=null&&B!=null){∥两均未空时循环if(A->element<B->element){last=append(last,A->element)；A=A->link；}elseif(A->element==B->element){∥两表中相等元素不作结果元素A=A->link；B=B->link；}elseB=B->link；∥向后移动B表指针}while(A!=null){last=append(last,A->element)；A=A->link；}last->link=null；∥置链表尾last=C；C=C->link；free(last)；returnC；}14、LinkedListLinkListInsertSort(LinkedListla){∥la是带头结点的单链表，其数据域是正整数。本算法利用直接插入原则将链表整理成递增的有序链表。if(la->next!=null){∥链表不为空表。p=la->next->next;∥p指向第一结点的后继。la->next->next=null;∥直接插入原则认为第一元素有序，从第二元素起依次插入。while(p!=null){r=p->next;∥暂存p的后继。q=la;while(q->next!=null&&q->next->data<p->data)∥查找插入位置。q=q->next;p->next=q->next;∥将p结点链入链表。q->next=p;p=r;}}returnla;}15、LinkedListDisCreat(LinkedListA)∥A是带头结点的单链表，链表中结点的数据类型为整型。本算法将A分解成两个单链表B和C，B中结点的数据小于零，C中结点的数据大于零。处理之后，B表的头指针即为A表头指针，只需返回C表头指针即可。{B=A;C=(LinkedList)malloc(sizeof(LNode));∥为C申请结点空间。C->next=null∥C初始化为空表。p=A->next;∥p为工作指针。B->next=null;∥B表初始化。while(p!=null){r=p->next;∥暂存p的后继。if(p->data<0){∥小于0的放入B表。p->next=B->next;B->next=p;∥将小于0的结点链入B表}else{p->next=C->next;C->next=p;}p=r;∥p指向新的待处理结点。}returnC;}16、LinkedListDisCreat(LinkedListA){∥A是带头结点的单链表，本算法将其分解成两个带头结点的单链表，A表中含原表中序号∥为奇数的结点，B表中含原表中序号为偶数的结点。链表中结点的相对顺序同原链表。i=0;∥i记链表中结点的序号。B=(LinkedList)malloc(sizeof(LNode);∥创建B表表头。B->next=null;∥B表的初始化。LinkedListra,rb;∥ra和rb将分别指向将创建的A表和B表的尾结点。ra=A;rb=B;p=A->next;∥p为链表工作指针，指向待分解的结点。A->next=null;∥置空新的A表while(p!=null){r=p->next;∥暂存p的后继。i++;if(i%2==0){∥处理原序号为偶数的链表结点。p->next=null;∥在B表尾插入新结点；rb->next=p;rb=p;∥rb指向新的尾结点；}else{∥处理原序号为奇数的结点。p->next=ra->next;ra->next=p;ra=p;}p=r;∥将p恢复为指向新的待处理结点。}returnB;}17、intPattern(LinkedListA，LinkedListB){∥A和B分别是数据域为整数的单链表，本算法判断B是否是A的子序列。如是，返回1；∥否则，返回0表示不是。p=A；∥p为A链表的工作指针，本题假定A和B均无头结点。pre=p；∥pre记住每趟比较中A链表的开始结点。q=B；∥q是B链表的工作指针。while(p&&q)if(p->data==q->data){p=p->next；q=q->next；}else{pre=pre->next；p=pre；∥A链表新的开始比较结点。q=B；}∥q从B链表第一结点开始。if(q==null)return1；∥B是A的子序列。elsereturn0；∥B不是A的子序列。}18、voidRearrange(SeqLista;intn){∥a是具有n个元素的线性表，以顺序存储结构存储，线性表的元素是整数。本算法重排线∥性表a，使所有值为负数的元素移到所有值为正数的数的前面。i=0;j=n-1;∥i,j为工作指针（下标），初始指向线性表a的第1个和第n个元素。t=a[0];∥暂存枢轴元素。while(i<j){while(i<j&&a[j]>=0)j--;∥若当前元素为大于等于零，则指针前移。if(i<j){∥将负数前移a[i]=a[j];i++;}while(i<j&&a[i]<0)∥当前元素为负数时指针后移。i++;if(i<j)a[j--]=a[i];∥正数后移。}a[i]=t;∥将原第一元素放到最终位置。此枢纽是为了减少交换次数，正负皆可。}19、voidderivative(ha){q=ha;pa=ha->next;while(pa!=null){∥遍历到链表结束if(pa->exp==0){∥若指数为0，即本项为常数项q->next=pa->next;∥删常数项free(pa);pa=q;}else{pa->coef=(pa->coef)*(pa->exp);pa->exp--;∥指数项减1q=pa;}∥前驱后移,或q->nextpa=pa->next;∥取下一元素}}20、voidAdjust(DLinkListL){DLinkListtail=L->prior,p=L->next；inti=0;while(p!=tail){i++;q=p->next;if(i%2==0){p->prior->next=q;q->prior=p->prior;tail->next->prior=p;p->next=tail->next;p->prior=tail;tail->next=p;}p=q;}}21、DLinkListlocate(DLinkListL，ElemTypex){∥L是带头结点的按访问频度递减的双向链表，本算法先查找数据x，∥查找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中适当位置。DLinkListp=L->next,q;∥p为L表的工作指针，q为p的前驱，用于查找插入位置。while(p&&p->data!=x)∥查找值为x的结点。p=p->next;if(!p){printf(“不存在值为x的结点\n”);returnNULL;}else{p->freq++;∥令元素值为x的结点的freq域加1。p->next->pred=p->pred;∥将p结点从链表上摘下。p->pred->next=p->next;q=p->pred;∥以下查找p结点的插入位置while(q!=L&&q->freq<p->freq)q=q->pred;p->next=q->next;q->next->pred=p;∥将p结点插入p->pred=q;q->next=p；}returnp;∥返回值为x的结点的指针}选择题1-5CCCCB6-10DCDCB11-15CCBCA16-20BBBCC21-25CCBAD填空题两端受限栈顶p->next=HS,HS=pHS=HS->next线性任何栈顶对头队尾栈顶栈底先进后出先进先出top==15O（1）ab+c*ef*h-qr+/+3+-134X*+2Y*3/-判断题1-5TTTFF6-10TTTTT11T简答题1、相同点是都属于线性结构，都是两端受限的线性表，不同点是栈只能在栈顶进行插入和删除操作，又称为先进后出表，而队列是在队头删除，队尾插入的线性结构又称先进先出表。2、真溢出是指存储空间已满的情况下继续进行插入操作，假溢出指有存储空间而不能进行插入操作。采用循环队列结构就是为了避免假溢出减少浪费空间。3、stack4、(1）栈中的数据元素逆置（2）如果栈中存在元素e，将其从栈中清除五、程序算法题1、typedefintDatatype;

typedefstructqueuenode

{

Datatypedata;

structqueuenode*next;

}QueueNode;//以上是结点类型的定义

typedefstruct

{

queuenoderear;

}LinkQueue;//只设一个指向队尾元素的指针

voidInitQueue(LinkQueue&Q)

{

//置空队：就是使头结点成为队尾元素

Q.rear=(queuenode*)malloc(sizeof(queuenode))

QueueNode*s;

Q->rear=Q->rear->next;//将队尾指针指向头结点

while(Q->rear!=Q->rear->next)//当队列非空，将队中元素逐个出队

{

s=Q->rear->next;

Q->rear->next=s->next;

free(s);

}//回收结点空间

}

intEmptyQueue(LinkQueue&Q)

{//判队空

//当头结点的next指针指向自己时为空队

returnQ->rear->next->next==Q->rear->next;

}

voidEnQueue(LinkQueue&Q,Datatypex)

{//入队

//也就是在尾结点处插入元素

QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode));//申请新结点

p->data=x;p->next=Q->rear->next;//初始化新结点并链入

Q-rear->next=p;

Q->rear=p;//将尾指针移至新结点

}

DatatypeDeQueue(LinkQueue&Q,Datatype&x)

{

//出队,把头结点之后的元素摘下

Datatypet;

QueueNode*p;

if(EmptyQueue(Q))

Error("Queueunderflow");

p=Q->rear->next->next;//p指向将要摘下的结点

x=p->data;//保存结点中数据

if(p==Q->rear)

{//当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点

Q->rear=Q->rear->next;Q->rear->next=p->next;

}

else

Q->rear->next->next=p->next;//摘下结点p

free(p);//释放被删结点

returnx;

}2、#include"stdio.h"

voidout(intnum)

{inti=0;

if(num==1)

{

printf("%d",num);

}

else

{

for(i=1;i<=num;i++)

{

printf("%d",num);

}

printf("\n");

out(--num);

}

}

voidmain()

{

out(9);

getch();}3、解：因为输入序列是从小到大排列的，所以若pj<pk<pi，则可以理解为通过输入序列pjpkpi可以得到输出序列pipjpk，显然通过序列123是无法得到312的，所以不可能存在着i<j<k使pj<pk<pi。4、解：BC=GG/D=HA-H=IE^F=JI+J=K步骤OPTR栈OPND栈输入字符主要操作1#A-B*C/D+E^F#PUSH(OPND,A)2#A-B*C/D+E^F#PUSH(OPTR,-)3#-AB*C/D+E^F#PUSH(OPND,B)4#-AB*C/D+E^F#PUSH(OPTR,*)5#-*ABC/D+E^F#PUSH(OPND,C)6#-*ABC/D+E^F#Operate(B,*,C)7#-AG/D+E^F#PUSH(OPTR,/)8#-/AGD+E^F#PUSH(OPND,D)9#-/AGD+E^F#Operate(G,/,D)10#-AH+E^F#Operate(A,-,H)11#I+E^F#PUSH(OPTR,+)12#+IE^F#PUSH(OPND,E)13#+IE^F#PUSH(OPTR,^)14#+^IEF#PUSH(OPND,F)15#+^IEF#Operate(E,^,F)16#+IJ#Operate(I,+,J)17#K#RETURN5、解答1.#definem01002./*m0为算术表达式中最多字符个数*/3.decpair(exp,flag)4.charexp［m0］;5.intflag;//flag用于标识是否匹配，flag=0标识不匹配，flag＝1标识匹配6.{7.charst［m0］;8.inttop=0,i=1;9.flag=1;10.while(i<=m0&&tag)11.{12.if(exp［i］=='('‖exp［i］=='［'‖exp［i］=='{'13./*遇到'('、'［'或'{'，则将其入栈*/14.{15.top++;16.st［top］=exp［i］;17.}18.if(exp［i］==')')/*遇到')'，若栈顶是'('，19.则继续处理，否则以不配对返回*/20.if(st［top］=='(')top--;21.elseflag=0;22.if(exp［i］=='］')/*遇到')'，若栈顶是'［'，23.则继续处理，否则以不配对返回*/24.if(st［top］=='［')top--;25.elseflag=0;26.if(exp［i］=='}')/*遇到')'，若栈顶是'{'，27.则继续处理，否则以不配对返回*/28.if(st［top］=='{')top--;29.elseflag=0;30.i++;31.}32.if(top>0)flag=0;/*若栈不空，则不配对*/33.}6、解：假设队列为循环顺序队列。建立一个临时队列，将指定队列中所有元素出队并入队到临时队列中，这样指定队列为空，再将临时队列中所有元素出队并入队到指定队列(因为不能破坏原队列结构，所以需要恢复元素)，最后一个元素即为所求。具体算法如下：datatypelastelem(queue*Q){datatypex；queuetmpQ；initqueue(&tmpQ)while(!emty(Q))//将Q中元素放入tmpQ{x=dequeue(Q)enqueue(&tmpQ，x)；}while(!empty(&tmpQ))//将tmpQ中元素恢复回Q{x=dequeue(&tmpQ)；enqueue(Q，x)；}returnx；}7、解：队列为空：count==0

队列为满：count=MAXLEN

队尾第一个元素位置==(front+count)%MAXLEN

队首第一个元素位置==(front+1)%MAXLEN

const

MAXLEN=100;

int

queue[MAXLEN];

int

front,count;

//

定义队头和计数器count

（1）初始化队列

void

init()

{

front=1;

count=0;

}

（2）判定队空

int

QEmpty()

{

if

(count==0)

return(1);

else

return(0);}

（3）读队头元素

void

ReadFront(int

queue[],x)

{

if

(count==0)

printf("

下溢出\n");

else

{

front=(front+1)%MAXLEN;

x=queue[front];

}

}（4）入队操作

void

InQueue(int

queue[],int

x)

{

int

place;

if

(count==MAXLEN)

printf("

上溢出\n");

else

{

count++;

place=(front+count)%MAXLEN;

queue[MAXLEN]=x;

}

}

（5）出队操作

void

OutQueue(int

queue[])

//

删除队列头元素

{

if

(count==0)

printf("

队列下溢出\n");

else

{

front=(front+1)%MAXLEN;

count--;

}

}

8、解析：定义本题队列类型如下：typedefstruct{linklist*rear;}Queue2(1)队列中人队操作是在队尾进行，即在链尾插入一个新结点。voidenqueue(Queue2*Q，datatypex){linklist*s；s＝(linklist*)malloe(sizeof(linklist))；//建立新结点s—>datda=x；s—>next=Q—>rear—>next；//将新结点插入队尾q—>rear—>next=s；q—>rear=s；}(2)队列中出队操作是在队头进行，即删除链表第一个数据结点。datatypedequeue(Queue2*Q){datatypex；linklist*p；if(Q—>rear—>next==Q—>rear)//队列为空returnNULL；p＝Q一>rear一>next一>next；//p指向队头结点x=p一>data；Q一>rear一>next一>next＝p一>next//删除*p结点free(p)returnx；//返回原队头元素}串选择题A2.C3.C4.D5.D6.D7.B8.D9.A10.C11.D12.D填空题长度为零的串字符串元素只有空格的串子串主串简答题1.答：长度为0的串称为空串；由一个或多个空格组成的串称为空格串。空格也是串的字符集合中的一个元素。2.答：虽然串是由字符组成的，但串和字符是两个不同的概念。串是长度不确定的字符序列，儿子富只是一个字符，即使是长度为1的串也与字符不同。例如，串“a”和字符‘a’就是两个不同的概念，因为在执行时串的结尾通常加上串结束标志“\0”。答：串的顺序存储结构是用一维数组存放串中的字符，用静态内存分配的方法定义数组，数组元素在编译时是确定的，在运行时是不可改变的称为静态顺序存储，用动态内存分配方法定义数组，数组元素个数是在程序运行时用户申请确定的称为动态顺序存储。4.StatusStrDelete(String&S,inti,intj){intlen;len=j-i+1;if(i<1||i>s[0]||j>s[0])returnERROR;S[pos..S[0]-len]=S[pos+len..S[0]];S[0]=S[0]-len;ReturnOK;}一．选择题1.B2.A3.C4.B5.D6.D7.C8.D9.C10.B11.C12.D13.A14.C15.D16.D17.C18.D19.B20.C21.A22.B23.B24.C25.D二．填空题1.i(i+1)/2+j2.1741393.4.对称上三角（下三角）矩阵5.d6.表头表尾7.（2,3,5）8.行列9.3310.O(n)11.O(n2)12.行列13.（）((),(()))3314.(a)((b),((c)))三．判断题1.√2.√3.√4.√5.×6.×7.√8.√9.√10.√四、简答题二维数组存储时，要把它的元素映像存储在一维存储器中，存储时若按先行后列的顺序存储，叫做二维数组的行序优先存储。若按先列后行的顺序存储，叫做二维数组的列序优先存储。元素分布特殊的矩阵，列如三角矩阵，对称矩阵，带状矩阵，稀疏矩阵等，叫做特殊矩阵。特殊矩阵压缩存储的基本思想是压缩存储，即值相同的元素只分配一个存储空间，零元素不分配存储空间。设m*n矩阵中有t个非零元素且t<<m*n,这样的矩阵叫做稀疏矩阵。系数矩阵存储时可只存储非零元素，由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。ije001042204215436(((a,b,()),(),a,(b)),())6.程序设计题1.1.intgenlistDepth(BSLinkListlist){/*list存放广义链表的首地址，该算法返回广义链表的深度*/BSLinkListstack1[M],p;/*stack1用来记录子表的起始位置*//*stack2用来记录子表当前的深度，depth用来表示当前所求子表的深度，maxdep用来记录当前已求出的那些子表的最大深度,stack1和stack2共用一个栈顶指针*/intstack2[M],depth=0,maxdep=0,top=-1;p=list->pointer;/*将p指针指向广义链表的第一个元素所在的链接点*/if(p!=NULL){do{while(p!=NULL){stack1[++top]=p;/*记录当前子表的起始位置*/stack2[top]=depth;/*记录当前所求子表的深度*/if(p->flag==1){/*当前链接点元素是子表*/depth++;/*当前层次数加1*/p=p->pointer;/*移动到下一层*/}elsep=NULL;}if(maxdep<depth){maxdep=depth;/*记录当前已求得的最大层次数*/}p=stack1[top];/*退回到上一层，移动到下一个元素，查看是否有子表*/depth=stack2[top--];p=p->link;}(p!=NULL&&top!=-1);}returnmaxdep+1;}2.#include<stdio.h>

#include<string.h>

main()

{

inta[100][100],m;

intn,i,j,k,max,flat=0,l;

scanf("%d,%d",&n,&l);

for(i=0;i<n;i++)

for(j=0;j<l;j++)

scanf("%d",&a[i][j]);

for(i=0;i<n;i++)

{

m=a[i][0];

for(j=0;j<l;j++)

if(a[i][j]>m)

{

m=a[i][j];

max=j;

}

for(k=0;k<n;k++)

if(a[k][max]<m)

{printf("No\n");

flat++;

break;

}

if(flat==0)

printf("%c\n",m);

}

}3.（1）#include<stdio.h>voidproc1(matrixA){ints=0,i,j;for(i=0;i<m;i++)/*第一列*/s=s+A[i][1];for(i=0;i<m;i++)/*最后一列*/s=s+A[i][n];for(j=0;j<n;j++)/*第一行*/s=s+A[1][j];for(j=0;j<m;j++)/*最后一行*/s=s+A[m][j];s=s-A[0][0]-A[0][n-1]-A[m-1][0]-A[m-1][n-1];/*减去4个角的重复元素值*/printf("s=%d\n",s);}（2）voidproc2(matrixA){ints=0,i,j;i=0;while(i<m){j=0;while(j<n){s=s+A[i][j];j=j+2;/*跳过一列*/}i=i+2;/*跳过一行*/}printf("s=%d\n",s);}（3）voidproc3(matrixA){inti,s;if(m!=n)printf("m!=n");else{s=0;for(i=0;i<m;i++)s=s+A[i][i];/*求第一列对角线之和*/for(i=0;i<n;i++)s=s+A[n-i-1][i];/*累加第二条对角线之和*/printf("s=%d\n",s);}}voidmain(){intm,n,i,j;matrixA;printf("m,n:");scanf("%d%d",&m,&n);printf("元素值:\n");for(i=0;i<m;i++)/*建立数组*/for(j=0;j<n;j++)scanf("%d",&A[i][j]);proc1(A);/*调用proc1()*/proc2(A);/*调用proc2()*/proc3(A);/*调用proc3()*/}树答案一选择题1-5ABBDC6-10CACBD11-15BCADB16-20BAAAA21-22CA二填空题n2+137单分支完全二叉树12764312+12-11多129P->lchild==null&&p->rchild==null哈夫曼树41601656316、6三综合应用题1（1）根节点：A叶子节点：CEFHIJKMN非终端节点：ABDGL（2）深度：5各节点层数A：1；B、C、D：2；E、F、G、H、I、J：3；K、L、M：4；N：5双亲：D祖先：AD孩子：KLM子孙：KLMN兄弟：HIJ堂兄弟：EF2先序遍历：ABCDEFGHIJ中序遍历：BCDAFEHJIG后序遍历：DCBFJIHGEA3对应的二叉树后序遍历为：bdeca456带权路径长度WPL=(2+3)*4+(6+7+8)*3+(10+14)*2=131树的结点总数137(1)哈夫曼树：给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffmantree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。(2)哈夫曼树为：哈弗曼编码：a:1110b:1111c:110d:00e:01f:10(4)长度：244四、算法设计题设计一个求结点x在二叉树中的双亲结点的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,charx){if(bt!=0&&flag==0)if(bt->data==x){flag=1;return;}else{r=(r+1)%20;q[r]=bt;preorder(bt->lchild,x);preorder(bt->rchild,x);}}voidparent(bitree*bt,charx){inti;preorder(bt,x);for(i=f+1;i<=r;i++)if(q[i]->lchild->data==x||q[i]->rchild->data)break;if(flag==0)printf("notfoundx\n");elseif(i<=r)printf("%c",bt->data);elseprintf("notparent");}

设计判断两个二叉树是否相同的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){if(bt1==0&&bt2==0)return(1);elseif(bt1==0||bt2==0||bt1->data!=bt2->data)return(0);elsereturn(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));}

设计计算二叉树中所有结点值之和的算法。voidsum(bitree*bt,int&s){if(bt!=0){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);} }4.设计求二叉树中值为x的结点所在的层号的算法。intlev=0;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidlevel(bitree*bt,intx){if(bt!=0){lev++;if(bt->key==x)return;elseif(bt->key>x)level(bt->lchild,x);elselevel(bt->rchild,x);}}树答案一选择题1-5ABBDC6-10CACBD11-15BCADB16-20BAAAA21-22CA二填空题n2+137单分支完全二叉树12764312+12-11多129P->lchild==null&&p->rchild==null哈夫曼树41601656316、6三综合应用题1（1）根节点：A叶子节点：CEFHIJKMN非终端节点：ABDGL（2）深度：5各节点层数A：1；B、C、D：2；E、F、G、H、I、J：3；K、L、M：4；N：5双亲：D祖先：AD孩子：KLM子孙：KLMN兄弟：HIJ堂兄弟：EF2先序遍历：ABCDEFGHIJ中序遍历：BCDAFEHJIG后序遍历：DCBFJIHGEA3对应的二叉树后序遍历为：bdeca456带权路径长度WPL=(2+3)*4+(6+7+8)*3+(10+14)*2=131树的结点总数137(1)哈夫曼树：给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffmantree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。(2)哈夫曼树为：哈弗曼编码：a:1110b:1111c:110d:00e:01f:10(4)长度：244四、算法设计题设计一个求结点x在二叉树中的双亲结点的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,charx){if(bt!=0&&flag==0)if(bt->data==x){flag=1;return;}else{r=(r+1)%20;q[r]=bt;preorder(bt->lchild,x);preorder(bt->rchild,x);}}voidparent(bitree*bt,charx){inti;preorder(bt,x);for(i=f+1;i<=r;i++)if(q[i]->lchild->data==x||q[i]->rchild->data)break;if(flag==0)printf("notfoundx\n");elseif(i<=r)printf("%c",bt->data);elseprintf("notparent");}

设计判断两个二叉树是否相同的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){if(bt1==0&&bt2==0)return(1);elseif(bt1==0||bt2==0||bt1->data!=bt2->data)return(0);elsereturn(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));}

设计计算二叉树中所有结点值之和的算法。voidsum(bitree*bt,int&s){if(bt!=0){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);} }4.设计求二叉树中值为x的结点所在的层号的算法。intlev=0;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidlevel(bitree*bt,intx){if(bt!=0){lev++;if(bt->key==x)return;elseif(bt->key>x)level(bt->lchild,x);elselevel(bt->rchild,x);}}第八章答案选择题1~5CCCCD6~10BACBD11~15BAAAA16~20CBCBB21~25CB⑧①③④DB26~31CBDBCA二、选择题1~9对对错对对对错三、填空题（1）2.9（2）2.1（3）1、2（4）7（5）1、2、4、8、5、3.7（6）O(n)、O(log2n)（7）3（8）增高一层（9）h（10）递增数列、后缀表达式（11）┌m/2┐-1、m-1、O(n)、O(nlog2n)、O(n)（12）减少一层（13）如何构造哈希函数、如何处理冲突（14）发生冲突的可能性越大、发生冲突的可能性越小（15）开放定址法、拉链法四、简答题1.静态查找表：如果一个查找表的操作只涉及查询和检索某个特定的数据元素的操作，无需动态的修改查找表，此类查找表称之为静态查找表。动态查找表：需要动态的插入或删除操作的查找表称之为动态查找表。适合静态查找的存储结构有：顺序存储，散列存储。适合动态查找的存储结构有：顺序存储，散列存储。2.平均查找长度：在查找过程中，一次查找的长度是指需要比较的关键字的次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值。其数学定义为ASL=∑PiCi(i=1,2,3,…,n),其中：Pi为查找表中第i个数据元素的概率，Ci为找到第i个数据元素时已经比较过的次数。3.（1）53/\1766/\/\12255870/\\566087（2）中序遍历二叉排序树可得到一个从小到大的有序序列。4.5.（1）（2）ASL=(4+2*3+3*2+4)/9=20/96.7.8.H(25)=25mod7=4H(31)=31mod7=3H(8)=8mod7=1H(27)=27mod7=6H(13)=13mod7=6H(68)=68mod7=5线性探测法：ASL=(5*1+2)/6=7/6链地址法：ASL=(5*1+1*2)/6=7/69.H(105)=105mod13=1H(97)=97mod13=6H(28)=28mod13=2H(52)=52mod13=0H(37)=37mod13=11H(22)=22mod13=9H(16)=16mod13=3H(90)=90mod13=12H(45)=45mod13=6H(76)=76mod13=11H(59)=59mod13=7H(74)=74mod13=9（1）散列地址0123456789101112131415关键字5210528169745592274379076冲突次数111112212113（2）散列地址0123456789101112131415关键字5210528169745592276379074冲突次数11111221311510.H(11)=(5*11)