数据结构答案打印版new

《数据结构答案打印版new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1试卷参考答案1.填空题(1)N2+1(2)2N–1(3)2(4)队空条件：front==rear队满条件：(rear+1)%(m+1)==front　　注：假设牺牲数组一个单元，只存放m个元素(6)广度优先搜索(8)14(9)避免在插入和删除操作中将第一个结点看作是特殊结点，使程序编写简单。2.基本思想如下：(1)存储结构：两个栈使用同一段内存空间，图示如下。栈1只做PUSH操作，对应队列的进队；栈2只做POP操作，对应队列出队操作。　　　　　　　(2)队列定义：typedefstruct{　　　　　intdata[M];　　　　　intTop1;//栈1指针　　　　　intTop2;

2、//栈2指针}SqQueue;　队列初始化：　SqQueueq;　q.Top1=－1;　q.Top2=0;(3)进队操作：　if（q.Top1==M-1）　printf(“队满！”);　elseq.data[++q.top1]=e;(4)出队操作：　if(q.Top2==q.Top1+1)printf(“队空！”);　elsee=q.data[q.top2++];4.拓扑排序算法如下所示：voidTopologicalSort(Graphg){　　//有向图g采用邻接表存储结构　　int　indegree[MAX_VER];//定义各顶点入度数组indegree[]　　int　i,k,c

3、ount;　　SqQueue　q;　　node　　*p;　　FindIndegree(indegree,g);//求出所有顶点的入度　　q=InitQueue();//建0入度顶点队列q　　for(i=0;i

4、　　　　for(p=g.adjlist[k].firstarc;p;p=p->next)　　　　　　　{　　　　　　　　　　　　　--indegree[p->no];//对k号顶点的每个邻接点的入度减1　　　　　　　　　　　　　if(!indegree[p->no])　　　　　　　　　　　　　　　　q=EnQueue(q,p->no);//若入度为0则进队列　　　　　　　}//for　　　}//while　　if(count

5、有向图的拓扑排序算法的时间复杂性为O(n+e)5.由于学号已经排好序，要求按学生成绩（总分）排名次，若总分相同，则学号在前的，仍排在前面，即要求选择的排序算法具有稳定性，分析具有稳定性的排序算法有如下4种：　　　　　再从时间与空间去综合考虑，选择改进的冒泡排序好。算法如下：　voidbubble_sort(inta[],intn){　　　　　intt=0,done=0;　　　　　inti,j;　　　　　for(i=1;i<=n-1&&!done;i++)　　　　　{　　　　　　　　　　done=1;　　　　　　　　　　for(j=0;j<=n-i-1;j++)　　　　　　　　　　　　　　

6、if(a[j]>a[j+1])　　　　　　　　　　　　　　{done=0;t=a[j];a[j]=a[j+1];a[j+1]=t;}　　　　　}　}6.归并排序算法如下：voidMerge(intb[],inta[],inti,intm,intn){　　//将有序的b[i..m]和b[m+1..n]归并为有序的a[i..n]　　intj,k;　　for(j=m+1,k=i;(i<=m)&&(j<=n);++k)　　{　　　　　　cmp++;　　　　　　if(b[i]

7、ge++;}　　}　　while(i<=m)　　{a[k++]=b[i++];change++;}//将剩于的b[i..m]复制到a　　while(j<=n)　　{a[k++]=b[j++];change++;}//将剩余的b[j..n]复制到a}//MergevoidMSort(inta[],intc[],ints,intt){　　//将a[s..t]归并排序为c[s..t]　　intm;　　intb[MAX];　　if(s==t