数据结构答案打印版.doc

1试卷参考答案

(1) N2 + 1 (2) 2N – 1 (3) 2
(4) 队空条件:front == rear队满条件:(rear+1) % (m+1) == front
注:假设牺牲数组一个单元,只存放m个元素
(6) 广度优先搜索(8) 14
(9) 避免在插入和删除操作中将第一个结点看作是特殊结点,使程序编写简单。
:
(1) 存储结构:两个栈使用同一段内存空间,图示如下。栈1只做PUSH操作,对应队列的进队;栈2只做POP操作,对应队列出队操作。

(2) 队列定义:
typedef struct{
int data[M];
int Top1;//栈1指针
int Top2;//栈2指针
}SqQueue;
队列初始化:
SqQueue q;
= -1;
=0;
(3) 进队操作:
if(==M-1) printf(“队满!”);
else [++]=e;
(4) 出队操作:
if (==+1) printf(“队空!”);
else e=[q. top2++];
:
void TopologicalSort(Graph g){
//有向图g采用邻接表存储结构
int indegree[MAX_VER];//定义各顶点入度数组indegree[]
int i,k,count;
SqQueue q;
node *p;
FindIndegree(indegree,g);//求出所有顶点的入度
q=InitQueue();//建0入度顶点队列q
for(i=0;i<;i++)
if(!indegree[i]) q=EnQueue(q,i);//入度为0者进队列
count=0;//对输出顶点计数
while(!QueueEmpty(q))
{ q=DeQueue(q,&k);
printf("%3c",[k].vex);
count++;//输出k号顶点并计数
for(p=[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<)//该有向图有回路
printf("\nThere is a circuit.");
}// TopologicalSort
对于有n个顶点,e条边的有向图的拓扑排序算法的时间复杂性为O(n+e)
,要求按学生成绩(总分)排名次,若总分相同,则学号在前的,仍排在前面,即要求选择的排序算法具有稳定性,分析具有稳定性的排序算法有如下4种:

再从时间与空间去综合考虑,选择改进的冒泡排序好。算法如下:
void bubble_sort(int a[],int n){
int t=0,done=0;
int i,j;
for(i=1;i<=n-1&&!done;i++)
{
done=1;
for(j=0;j<=n-i-1;j++)
if(a[j]>a[j+1])
{done=0; t=a[j]; a[j]=a[j+1]; a[j+1]=t; }
}
}
:
void Merge(int b[],int a[],int i,int m,int n){
//将有序的b[i..m]和b[m+1..n]归并为有序的a[i..n]
int j,k;
for(j=m+1,k=i;(i<=m)&&(j<=n);++k)
{
cmp++;
if(b[i]<b[j])
{a[k]=b[i++];change++;}
else {a[k]=b[j++];change++;}
}
while(i<=m)
{a[k++]=b[i++];change++;}//将剩于的b[i..m]复制到a
while(j<=n)
{a[k++]=b[j++];change++;}//将剩余的b[j..n]复制到a
}// Merge
void MSort(int a[],int c[],int s,int t){
//将a[s..t]归并排序为c[