数据结构 练习 答案汇.docVIP

PAGE  PAGE 3 数据结构测验 填空题 数据结构一般包括　逻辑结构　、　物理结构　和数据操作三个方面的内容。 无向图的三种常存储表示方法　邻接矩阵、　邻接表　、　邻接多重表　。 广义表((a)，((b)，j，(((d))))的表头是　(a)　，表尾是　(((b)，j，(((d))))　。 由一棵二叉树的前序序列和　中序序列　可唯一确定这棵二叉树。 栈顶的位置是随着　入栈　和　出栈 操作而变化的。 用7，5，2，4作为四个叶结点a，b，c，d的权值，构造赫夫曼树，其带权路径长度为　　35　　。 对称矩阵的下三角元素a[i，j]的值存放在一维数组V的元素V[k]中，k与i，j的关系是k=i′(i-1)/2+j－1，i≥j；j′(j-1)/2+i－1，i j　。 顺序队列在实现的时候，通常将数组看成是一个首尾相连的环，这样做的目的是为避免产生　假溢出　现象。 在对二叉树进行层次遍历时，需要用　队列　来暂存所访问结点的地址。 高度为h的满二叉树中有　2h-1　个结点。 选择题 向一个栈顶指针top的链栈中插入一个s所指节点时，执行（ C ） top-next=s s-next=top-next；top-next=s s-next=top；top=s s-next=top；top=top-next 在非空的线性表中，有且只有一个直接前驱和一个直接后继的结点是（ B ） a)开始结点 b) 内部结点 c)终端结点 d) 所有结点 有m个叶结点的赫夫曼树所具有的结点数为（ C ） a) m b) m+1 c)2m-1 d) 2m 某二叉树的前序遍历序列为ABDGCEFH，中序遍历序列为DGBAECHF，则后序遍历序列为（ D ） a) BDGCEFHA b) GDBECFHA c) BDGAECHF d) GDBEHFCA 二维数组A[4][4]，数组起始地址loc[0][0]=1000，数组元素的长度为2，则loc[2][2]是（ D ） a) 1002 b)1010 c)1008 d) 1020 对于一个具有n个节点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ D ） a) n b) (n+1)2 c) n-1 d) n2 二叉树和度为2的树的相同之处是（ D ） 每个结点都有一个或两个孩子结点 至少有一个根结点 至少有一个度为2的结点 每个结点至多只有一个双亲结点 某个图的邻接表中有奇数个链表结点，则该图（ C ） 一定有奇数个顶点 一定有偶数个顶点 一定是??向图 可能是无向图 三、分析题 从顶点V3开始利用普里姆算法构造无向网络的最小生成树。画出最小生成树的构造过程并写出算法执行过程中closedge数组状态和最终状态。 B C D E H F I A 写出下列二叉树的前序、中序和后序遍历的顺序。 前序序列：ABDEHCFI 中序序列：DBHEACIF 后序序列：DHEBIFCA 设有链式存储结构的二叉树，写一算法计算其中树叶结点的数目。 假设二叉树以二叉链表方式存储。 count=0; int CountLeaf(BiTree T) { if (T) { if (T-lchild==NULL T-rchild==NULL) count++; 　return OK; CountLeaf(T-lchild); CountLeaf(T-rchild);　　　　　　　　　　　　　　　　　　　　　 } }