完整word版,N2-数据结构答案

1、合肥学院2010至2011学年第2学期算法与数据结构课程阶段测试试卷学号：姓名：成绩：一、选择题（共30分。每小题2分。）01、假定在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶子结点数为 B个。A. 15B. 16 C . 17 D . 4702、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序A。A.不发生改变B.发生改变C. 不能确定 D.以上都不对03、设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是B。A. a在b的右方B. a在b的左方C. a是b的祖先 D. a是b的子孙04、若用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树

2、的C。A 、层次遍历算法 B 、前序遍历算法C 、中序遍历算法 D 、后序遍历算法05、如果二叉树中结点的先序序列是a.b.，中序序列是.b.a.,_则D。A .结点a和结点b分别在某结点的左子树和右子树中B .结点b在结点a的右子树中C .结点a和结点b分别在某结点的两棵非空子树中D .结点b在结点a的左子树中06、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是B的二叉树。A 空或只有一个结点B 高度等于其节点数C 任一结点无左孩子D 任一结点无右孩子07、具有n（n0）个结点的完全二叉树的深度为C。A . log 2（n） B . log 2（n） C . log 2（n） +1

3、D . log 2（n）+108、由带树为9,2,5,7的四个叶子结点树造一棵哈夫曼树，该树的带权路径长度为D。A . 29 B . 37 C . 46 D . 4409、根据使用频率为五个字符设计的哈夫曼编码不可能是CA. 111， 110， 10， 01， 00B.000， 001，010,011，1C. 100，11，10，1，0D.001， 000，01,11，1010、无向图的邻接矩阵是一个 A矩阵。A.对称B.零C .上三角D.对角11、 若用邻接矩阵表示一个有向图，则其中每一列包含的T的个数为A。A 、图中每个顶点的入度B、图中每个顶点的出度C 、图中弧的条数D、图中连通分量的数

4、目12、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点岀度的 时间复杂度为A 。A . O（n） B . 0（e） C . O（n+e） D . O（n2）13、 采用邻接表存储的图的广度优先遍历算法类似于二叉树的D。A .先序遍历B .中序遍历C.后序遍历D .层次遍历14、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中B。A .第i行非的元素之和B .第i列非的元素之和C .第i行非a且非0的元素个数 D .第i列非a且非0的元素个数15、 在图中求某个源点到其余各顶点的的最短路径的是A算法。A .迪杰斯特拉 B .哈夫曼 C .普里姆 D . K

5、MP算法二、填空题（共12分。每空2分。）16、 一棵哈夫曼树有21个结点，则其叶子结点的个数11。17、树的后根遍历序列等同于该树对应的二叉树的中序遍历。18、 连通图的生成树是一个极小的连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边19、 具有10个顶点的无向图，边的总数最多为45。20、 拓扑排序算法是通过重复选择具有0个前驱顶点的过程来完成的。21、 Dijkstra 算法求某一顶点到其余各顶点间的最短路径是按路径长度递增的次序来得到最短路径的。三、简答题（共28分）22、 已知遍历二叉树时得到的中序序列为CBGDAEF后序序列为CGDBFEA请写出先序序列。（4分）

6、答案：ABCDGEF23、若以数据集5,4,7,2,9 为结点的权值构造huffman树，按要求完成下列任务：（6分）1）按课本中huffman算法的求解顺序画出 huffman树；WPL=（2+4）*3+（5+7+9）*2=18+42=60abcde。若从顶点岀发按广24、下图若从顶点a岀发按深度优先搜索法进行遍历，则得到的顶点序列是度优先搜索法进行遍历，则得到的顶点序列是abced。（要示按字母顺序进行遍历）（6分）4fh25、请在右侧画出左图的一棵最小生成树。（6 分）71）写岀所有可能的拓扑排序序列；2）在图中添加什么边之后仅可能有惟一的拓扑序列。答案:ABCDEABDCE 或 四、算

7、法填空（每空3分，共18分。）27、下面算法实现按层次遍历二叉链树，请填空。void LevelOrderTraverse(BiTree T) LinkQueue Q; BiTree p;lnitQueue(&Q);if 仃)EnQueue(&Q, T);while (!QueueEmpty(Q)DeQueue(&Q, &p);printf(%c,p-data);if ( p-lchild) EnQueue(&Q, p-lchild);if (/*此处略 */) EnQueue(&Q, p-rchild); DestroyQueue(&Q);五、算法设计题(本题 12分)29、编写递归算法，计

8、算二叉树的深度。int BiTreeDepth(BiTree T) int h1,h2;if (T=NULL)return 0;else h仁 BiTreeDepth(T-lchild);h2=BiTreeDepth(T-rchild);if (h1h2)return h1+1;elsereturn h2+1; 28、下面算法实现图的深度优先搜索遍历，请填空。Boolean visitedMAX_VERTEX_NUM;void Dfs(MGraph G, int v) visitedv= TRUEprintf(%s,G.vexsv);for(w=FirstAdjVex(G,v); w=0; w=NextAdjVex(G,v,w) if(!visit