《数据结构》(C语言版)习题答案.doc 14页

'习题1一、选择题1.B2.D3.D4.A5.C6.A7.B8.D9.C10.A二、简答题1.答：数据的逻辑结构通常有四种，即集合、线性结构、树形结构和图状结构。存储结构主要有顺序存储结构和链式存储结构。2.答：比如一分通讯录，记录了相关人员的电话号码，将其按姓名一人占一行构成表，这个表就是一个数据结构。每一行是一个记录，对于整个表来说，只有一个开始结点和一个终端结点，其它结点也只有一个前驱和一个后继。这几个关系就确定了表的逻辑结构。3.答：算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有有穷性、确定性、可行性、输入和输出5个特性。4.答：它是一种树型结构，可以用二元组描述为：A={K,R}K={a,b,c,d,e,f,g,h,i}R={(a,b),(a,c),(c,d),(c,e),(d,f),(d,g),(e,h),(f,i)}5.答：(1)A对应的逻辑图形如下图左，它是一种线性结构。abcdefghabcdefgh(2)B对应的逻辑图形如上图右所示，它是一种树型结构。(3)C对应的逻辑图形如下图所示，它是一种图型结构。123465三、计算题解：(1)O(n)；(2)O(n)；(3)O(n1/2)；（4）略。 习题2一、选择题1.A2.B3.B4.D5.A6.C7.B8.A9.C10.C二、简答题1.答：线性表是具有n个数据元素的一个有限序列。线性表的特点是：数据元素之间是一对一的关系。除第一个元素外，每个元素有且只有一个直接前驱；除最后一个元素外，每个元素有且只有一个直接后继。2.答：头指针是链表的一个标识，它用来指向带头结点的链表中的头结点。头结点是在链表的第一个数据元素之前附加的一个结点，它的作用是使对第一个结点的操作和其它结点一致，表空与非空时处理一致，不需要特殊处理，简化了操作。3.答：顺序表的特点是逻辑位置相邻的数据元素其物理位置也相邻，因此可以进行随机存储，是一种随机存储结构。其插入和删除操作的时间复杂度均为O(n)。链表中的数据元素使用一组任意的存储单元存储，不要求逻辑位置相邻的数据元素物理位置也相邻，而是采用附加的指针表示元素之间的逻辑关系。链表的插入和删除结点均不需要移动其他结点，但是，其查找运算必须从头指针开始顺序查找，其时间复杂度为O(n)。4.答：算法如下voidConvert(SqList&L){inti,j,temp;j=L.length-1;i=0;while(iLb.elem[j])j++;elseListDelete_Sq(La,i+1,k);}}6.答：算法如下voidInvertList(LinkList&L){LinkListp,q,r;p=L->next; q=p->next;p->next=NULL;while(q!=NULL){r=q->next;q->next=p;p=q;q=r;}L->next=p;}7.答：算法如下voidMergeOrder(LinkListLa,LinkListLb){LinkListpa,pb,Lc,pc;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}if(!pa)pc->next=pb;elsepc->next=pa;}8.答略。9.答：算法如下intLength(LinkListL){inti=0;LinkListp;p=L->next;while(p){p=p->next;i++;}returni;} 习题3一、选择题1.C2.B3.A4.D5.B6.A7.C8.A9.B10.B二、简答题1.答：栈是限定在表的一端进行插入和删除操作的线性表。队列是只允许在表的一端进行插入，而在另一端进行删除元素的线性表。栈的操作是按照后进先出原则进行的，因此又称作后进先出的线性表。队列的操作是按照先进先出原则进行的，因此又称作先进先出的线性表。2.答：当front¹0，rear=M时，再有元素入队发生溢出，称之为“假溢出”，存储空间还有剩余。为了改进这种状况，可以将顺序队列想象为一个首尾相接的环状空间，称之为循环队列。3.答：(1)相应入队列操作StatusEnQueue_L(LinkQueue&Q,ElemTypee){p=(QLink)malloc(sizeof(QNode));p->data=e;p->next=Q->next;Q->next=p;Q=p;returnOK;}(2)相应出队列的操作StatusDeQueue_L(LinkQueue&Q,ElemType&e){if(Q->next==Q)returnERROR;p=Q.next->next;e=p->data;Q->next->next=p->next;free(p);returnOK;}4.答：intpush(ElemTypex,inti){if(top1==top2-1)return0;elseif(i==1){top1++;C[top1]=x;}else{top2--;C[top2]=x;}return1;}intpop(inti,ElemType&e){ if(i=1){if(top1==0)return0;else{x=C[top1];top1--;}}else{if(top2==n+1)return0;else{x=C[top2];top2++;}}return1;}5.答：算法如下voidPrint(intn){inti;if(n==0)return;for(i=1;i<=n;i++)printf("%3d",n);printf("n");Print(n-1);}6．答：算法如下ElemTypeBottom(StackS){ElemTypex,y;StackT;InitStack(T);while(!StackEmpty(S)){pop(S,x);push(T,x);}while(!StackEmpty(T)){pop(T,y);push(S,y);}returnx;} 习题4一、选择题1.B2.D3.B4.D5.A二、简答题1.答：长度为零的串称为空串，记作""。空格也是串的字符集合中的一个元素，由一个或多个空格组成的串称为空格串。例如""，其长度为串中空格的个数。2.答：虽然串是由字符组成的，但串和字符是两个不同的概念。串是长度不确定的字符序列，而字符只是一个字符。即使是长度为1的串也与字符不同。例如，串"a"和字符"a"就是两个不同的概念，因为在存储时串的结尾通常加上串结束标志""。3.答：在串的顺序存储结构是用一维数组存放串中的字符。一种方法是用静态内存分配的方法定义的数组，数组元素的个数是在编译时确定的，在运行时是不可改变的，称之为静态顺序存储。另一种方法是用动态内存分配的方法定义的数组，数组元素的个数是在程序运行时用户申请确定的，称之为动态顺序存储。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中从下标从pos+len开始的元素前移len位S[0]=S[0]-len;//串长的处理returnOK;}5.答：StatusSubString(StringS1,StringS2){inti,j,k,flag=0;i=1;while(ilchild);Release(T->rchild);free(T);}}6.解：intDepth(BiTreeT){if(!T)return0;//如果T为空，则其深度为0else{//若T不空返回其子树中深度较大值加1if(Depth(T->lchild)>=Depth(T->rchild))returnDepth(T->lchild)+1;elsereturnDepth(T->rchild)+1;}}7.解：voidLevel(BiTreeb,BiTreep,int*h,intlh){if(b==NULL)*h=0; elseif(p==b)*h=lh;else{Level(p,b->lchild,h,lh+1);if(*h==-1)Level(p,b->rchild,h,lh+1);}}习题7一、选择题1.C2.D3.A4.B5.B6.D7.A8.D9.C10.C11.D12.C二、简答题1.对于无向图，如果在深度优先遍历中遇到回边，则必定存在环。对于有向图，如果从有向图的某个顶点v出发的遍历，在DFS(v)结束之前出现了一条从顶点u指向v的回边，则此有向图必定存在环。因为u在深度优先生成树上是v的子树，即存在u到v的路径，现在又出现一条从u指向v的弧，则它们必然构成一条回路。2.用邻接矩阵表示图时，矩阵元素的个数与顶点个数无关；但和边数有关。三、设计题1．解：图(a)和图(b)的入度和出度为：入度出席A13B30C21D32E13F12入度出席A21B11C30D12E02F122.解：(1)按普里姆算法求得的最小生成树：ADBEFC(a)(b)GH3454532ABCDEFG234414①②④⑤⑥③⑦①②③④⑤⑥(2)按克鲁斯卡尔算法求得的最小生成树 ADBEFC(a)(b)GH3454532ABCDEFG234414①②④⑤⑥③⑦①②③④⑤⑥(a)(b)ABCEFGD48281523933AEBCDFG125158433.解：4.解：intvisited[MAXSIZE];intExist_Path_DFS(GraphG,inti,intj){intk;ArcNode*p;if(i==j)return1;else{visted[i]=1;for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;if(!visited[k]&&Exist_Path_DFS(k,j))return1;}}}5．答案略。6．答案略。 习题8一、选择题1.C3.D4.B5.A6.B7.D8.C9.C10.C二、简答题1.答：静态查找是指只在数据元素集合中查找是否存在关键字等于某个给定关键字的数据元素。动态查找除包括静态查找的要求外，还包括在查找过程中同时插入数据元素集合中不存在的数据元素，或者从数据元素集合中删除已存在的某个数据元素的要求。2.答：为了确定要查找的记录位置，与给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度ASL(AverageSearchLength)。对于含有n个记录的表，平均查找长度的计算公式为：其中，Pi为查找第i个元素的概率。3.答：与二叉排序树相比，B-树是一种平衡多叉排序树。这里说的平衡是指所有叶结点都在同一层上，从而可避免出现像二叉排序树那样的分支退化现象；多叉是指多于二叉。因此B-树是一种动态查找效率较二叉排序树更高的树。DecAugAprFebNovJuneOctJulyJanMaySeptMar三、设计题1．解：523020506860702.解：3.解：(1)m的取值为13(2)地址0123456789101112key807588901021131264735231151探测次数656571011 习题9一、选择题1.B2.D3.B4.C5.D6.C二、设计题1.解：intQuickSort(SeqListR,intj,intlow,inthigh){//对R[low..high]快速排序intpivotpos;//划分后的基准记录的位置if(lowj)return(R,j,low,pivotpos-1);elsereturnquicksort(R,j,pivotpos+1,high);}}//QuickSort2.解：voidselectsort(linklisthead){RecNode*p,*q,*s;if(head->next)&&(head->next->next){p=head->next;//p指向当前已排好序最大元素的前趋while(p->next){q=p->next;s=p;while(q){if(q->keykey)s=q;q=q->next;}//endwhile交换s结点和p结点的数据;p=p->next;}//endwhile}//endif}//endsort3.解：voidQuickSort(SeqListR,intlow,inthigh){//对R[low..high]快速排序intpivotpos;if(high-low<=2){//若当前区内元素少于3个//则进行直接插入排序InsertSort(R,low,high);}else{pivotpos=midPartion(R,low,high);QuickSort(R,low,pivotpos-1);QuickSort(R,pivotpos+1，high); }}//QuickSortintmidPartion(SeqListR,inti,intj){//三者取中规则定基准if(R[(i+j)/2].key>R[i].key){交换R[(i+j)/2]和R[i];}if(R[i].key>R[j].key){交换R[i]和R[j];}if(R[i].key)R->length)　Error("havenosuchnode");R->data[i].key=R->data[R->length].key;R->length--;R->data[R->length].key=key;//插入新的记录for(j=i/2;j>0;j--){//建堆low=j;high=R->length;R->data[0].key=R->data[low].key;//R->data[low]是当前调整的结点for(large=2*low;large<=high;large*=2){if(largedata[large].keydata[large+1].key)large++;if(R->data[0].keydata[large].key){R->data[low].key=R->data[large].key;low=large;//令low指向新的调整结点}elsebreak;}R->data[low].key=R->data[0].key;}}～～～～THEEND～～～～'