中科院研究生院2010年专业课数据结构复习资料-例题.pdfVIP

1. 试利用栈的基本操作写出二叉树后序遍历的非递归算法。 参考答案： 除了记录每次递归根结点的栈之外，还需要一个记录当前结点遍历状态的栈，如 果处于左子树遍历，状态为0，否则状态变为1。 Status PostOrderTraverse(BiTree T, Status (*Visit)(ElemType e))  {    // 采用二叉链表存储结构，Visit 是对数据元素操作的应用函数    InitStack(Sroot);    InitStack(Stag);    p = T;    while (p || !StackEmpty(Sroot)) {  if (p) {    Push(Sroot, p);    Push(Stag, 0);    p = p‐lchild;  } else {    Pop(Stag, tag);    if (tag == 0) {      GetTop(Sroot, p);      Push(Stag, 1);      p = p‐rchild;    } else {      Pop(Sroot, p);      if (!Visit(p)) return ERROR;      p = NULL;    }  }    }    return OK;  }  2. 画出和下列已知访问序列对应的树： 树的先根次序访问序列为：KIMCBDNFHJEALG ； 树的后根次序访问序列为：MCIBNHFJDLAGEK 。 参考答案： K I B D E M C N F J A G H L 3. 画出和下列已知访问序列对应的森林： 森林的先序次序访问序列为：JHEFIABLGCKD ； 森林的中序次序访问序列为：HJIAFBLECDKG 。 参考答案： J E G H F B L C K I A D 4. 试写一算法，以判断用邻接表方式存储的有向图中是否存在由顶点v 到顶点 i v 的路径。 j 参考答案： int visited[]=0; int dfs(AdjList g, vi) { vistit[vi]=1; p=g[vi].firstarc; while(p!=NULL) { j=p-adjvex; if(vj==j) { flag=1; return 1; } if(vistited[j]==0) dfs(g, j); p=p-next; } if (!flag) return 0; } 5. 给出下图所示无向带权图，根据该图完成下列各题： (1) 写出它的邻接矩阵； (2) 按Prim 算法求其最小生成树，要求按步骤画出生成过程； (3) 利用Dijkstra 算法求顶点A 到其他各顶点的最短路径，写出算法执行过 程中各步的状态。 A 8 2 1 G 3 6 B 5 D 1 F 6 2