pop(s2, x); return ok;
else //栈s1和s2都为空。
return error;
二、（本题15分）用孩子兄弟链表作为树的存储结构，设计算法求出树的深度。
解：算法思路：一棵树的深度可以递归定义为：若树为空，则深度为0，否则树的深度为根结点的所有子树深度的最大值加1。
数据结构为：
typedef struct csnode
return m+1;
三、（本题15分）已知在某并发处理系统的petri网基础上建立的可达图如下图所示。图中每个顶点表示系统运行中的一种状态，有向边(弧)表示事件(用t表示)，例如有向边(vi，vj)表示系统在状态vi时出现该事件将引发系统由状态vi到状态vj。
1）请分别给出该可达图的邻接表、邻接矩阵以及邻接矩阵的三元组3种存储表示的形式说明和存储结果示意图，要求每种存储结构能够表达出该可达图的全部信息，并分别对这三种形式中每个部分的含义予以简要说明。
2）若假设每个域（包括指针域）的长度为2个字节，请分别计算出这三种结构所占用的空间大小。
四、（本题15分）设计一个算法，判断无向图g（图中有n个顶点）是否是一棵树。
解：算法思路：从第v个顶点出发，对图进行深度优先搜索。
若在算法结束之前，又访问了某一已访问过的顶点，则图g中必定存在环，g不是一棵以v为根的树。若在算法结束之后，所访问的顶点数小于图的顶点个数n，则图g不是连通图，g也不是一棵以v为根的树。
boolean visited[max用于标识结点是否已被访问过。
status ( visitfunc) (int v); 函数变量。
void dfstr**erse( graph g, status ( visitfunc) (int v));
status dfs( graph g, int v );
2）基本操作是关键字比较操作和记录移动操作。其中关键字比较操作为o(n2)，记录移动操作为o(n)。因此，总的时间复杂性为o(n2)。
2019《数据结构》期末试卷B卷
一 本题10分 1 线性表和广义表的主要区别点是什么？已知广义表 c a,b,a,b a,b a,b 则tail head tail c 2 满足什么条件可以实施二分查找？二分查找的时间复杂度是多少？二 本题10分 证明 一棵二叉树的先序序列和中序序列可惟一确定这棵二叉树。三 本题15分 某带权有向...
数据结构 试卷b答案
中南财经政法大学2005 2006 学年第 2 学期期末考试试卷答案。课程名称 数据结构 b 卷课程代号 09091051 考试形式 闭卷 笔试使用对象 电子政务专业。一 单选题 共25题，每题1分，共25分 二 多选题 共5题，每题2分，共10分 三 填空题 共6题，每空1分，共10分 1.线性结...
杭师A 试卷 数据结构期末试卷答案
杭州师范大学国际服务工程学院2008 2009学年第二学期期末考试。数据结构与算法分析 试卷 a 注意 请将答案填写在答题纸上。一 选择 共30分，每小题3分，把最恰当的答案题号填到答题卷上 1.对于具有n个顶点的连通图 连通的无向图 其最少的边数目为。a.nb.n n 1 2 c.n 1d.n 1...