Question

200分 找数据结构高手 计算机 加分

四、算法阅读题

1 阅读下列函数algo,并回答问题：
(1)假设队列q中的元素为(2,4,5,7,8),其中“2”为队头元素。写出执行函数调用algo(&q)后的队列q；
(2)简述算法algo的功能。
void algo(Queue *Q)
{
Stack S;
InitStack(&S);
while (!QueueEmpty(Q))
Push(&S, DeQueue(Q));
while (! StackEmpty(&S))
EnQueue(Q,Pop(&S));
}
(1)

（2)

2 .阅读下列函数F，并回答问题：
(1)已知如图所示的二叉树以二叉链表作存储结构，rt为指向根结点的指针。写出执行函数调用F(rt)的输出结果。
(2)说明函数F的功能。
void F(BinTree T)
{
Stack S;
if(T)
{
InitStack(&S);
Push(&S,NULL);
while(T)
{
printf("%c", T->data);
if(T->rchild) Push(&S,T->rchild);
if(T->lchild)T=T->lchild;
else T=Pop(&S);
}
}
}
(1)
(2)

vertex firstedge
3 .已知邻接表的顶点表结点结构为

adjvex next
边表结点EdgeNode的结构为

下列算法计算有向图G中顶点vi的入度。请在空缺处填入合适的内容，使其成为一个完整的算法。
int FindDegree(ALGraph *G,int i)//ALGraph为图的邻接表类型
{
int dgree, j;
EdgeNode *p;
degree= (1) ;
for(j=0;j<G->n;j++)
{
p=G->adjlist〔j〕. firstedge;
while ( (2) )
{
if( (3) )
{
degree++;
break;
}
p=p->next;
}
}
return degree;
}
(1)
(2)
(3)

data next
3 .已知单链表的结点结构为

下列算法对带头结点的单链表L进行简单选择排序，使得L中的元素按值从小到大排列。
请在空缺处填入合适的内容，使其成为完整的算法。
void SelectSort(LinkedList L)
{
LinkedList p,q,min;
DataType rcd;
p= (1) ;
while(p!=NULL) {
min=p;
q=p->next;
while(q!=NULL){
if( (2) )min=q;
q=q->next;
}
if( (3) ){
rcd=p->data;
p->data=min->data;
min->data=rcd;
}
(4) ;
}
}
(1)
(2)
(3)
(4)

五 算法设计题
.设线性表A=(a1,a2,a3,…,an)以带头结点的单链表作为存储结构。编写一个函数，对A进行调整，使得当n为奇数时A=(a2,a4,…,an-1,a1,a3,…,an)，当n为偶数时A=(a2,a4,…,an,a1,a3,…,an-1)。

Answer 1

四、算法阅读题
1.(1) 答：q=(8,7,5,4,2) 。
(2) 答：算法利用栈S辅助实现队列Q的逆置。

2.(1) 答：输出结果： a b d e g c f h。
(2) 答：算法功能：前序遍历二叉树。
3.(1) 答：0
(2) 答：p
(3) 答：p->adjvex==i
4.(1) 答：L ->next
(2) 答：q->data<min->data
(3) 答：min!=p
(4) 答：p=p->next

五.算法设计题
答： void f(LinkList L)
{
linkList p,q,r;
p=L;
q=L->next;
while(q&&q->next)
{
r=q->next;
q->next=r->next;
r->next=p->next;
p->next=r;
p=p->next;
q=q->next;
}
}

Answer 2

先把分加上去再说

Answer 3

比较难！！！