《数据结构 练习 答案》由会员分享,可在线阅读,更多相关《数据结构 练习 答案(3页珍藏版)》请在金锄头文库上搜索。
1、1数据结构测验数据结构测验一、一、 填空题填空题1、数据结构一般包括数据结构一般包括 逻辑结构逻辑结构 、 物理结构物理结构 和数据操作三个方和数据操作三个方面的内容。面的内容。2、无向图的三种常存储表示方法无向图的三种常存储表示方法 邻接矩阵邻接矩阵、 邻接表邻接表 、 邻接多邻接多重表重表 。3、广义表广义表(a),(b),j,(d)的表头是的表头是 (a) ,表尾是,表尾是 (b),j,(d) 。4、由一棵二叉树的前序序列和由一棵二叉树的前序序列和 中序序列中序序列 可唯一确定这棵二叉树。可唯一确定这棵二叉树。5、栈顶的位置是随着栈顶的位置是随着 入栈入栈 和和 出栈出栈 操作而变化的。
2、操作而变化的。6、用用 7,5,2,4 作为四个叶结点作为四个叶结点 a,b,c,d 的权值,构造赫夫曼树,的权值,构造赫夫曼树,其带权路径长度为其带权路径长度为 35 。7、对称矩阵的下三角元素对称矩阵的下三角元素 ai,j的值存放在一维数组的值存放在一维数组 V 的元素的元素 Vk中,中,k 与与 i,j 的关系是的关系是 k=i (i-1)/2+j1,ij;j (j-1)/2+i1,i next=sb)s-next=top-next;top-next=s2c)s-next=top;top=sd)s-next=top;top=top-next2、在非空的线性表中,有且只有一个直接前驱和一个
3、直接后继的结点在非空的线性表中,有且只有一个直接前驱和一个直接后继的结点是(是( B )a)开始结点开始结点 b) 内部结点内部结点c)终端结点终端结点 d) 所有结点所有结点3、有有 m 个叶结点的赫夫曼树所具有的结点数为(个叶结点的赫夫曼树所具有的结点数为( C )a) m b) m+1 c)2m-1 d) 2m4、某二叉树的前序遍历序列为某二叉树的前序遍历序列为 ABDGCEFH,中序遍历序列为,中序遍历序列为DGBAECHF,则后序遍历序列为(,则后序遍历序列为( D )a) BDGCEFHA b) GDBECFHAc) BDGAECHF d) GDBEHFCA5、二维数组二维数组 A
4、44,数组起始地址,数组起始地址 loc00=1000,数组元素的长度,数组元素的长度为为 2,则,则 loc22是(是( D )a) 1002 b)1010 c)1008 d) 10206、对于一个具有对于一个具有 n 个节点的无向图,若采用邻接矩阵表示,则该矩阵个节点的无向图,若采用邻接矩阵表示,则该矩阵的大小是(的大小是( D )a) n b) (n+1)2 c) n-1 d) n27、二叉树和度为二叉树和度为 2 的树的相同之处是(的树的相同之处是( D )a)每个结点都有一个或两个孩子结点每个结点都有一个或两个孩子结点b)至少有一个根结点至少有一个根结点c)至少有一个度为至少有一个度
5、为 2 的结点的结点d)每个结点至多只有一个双亲结点每个结点至多只有一个双亲结点8、某个图的邻接表中有奇数个链表结点,则该图(某个图的邻接表中有奇数个链表结点,则该图( C )3a)一定有奇数个顶点一定有奇数个顶点b)一定有偶数个顶点一定有偶数个顶点c)一定是有向图一定是有向图d)可能是无向图可能是无向图三、分析题三、分析题1、从顶点从顶点 V3 开始利用普里姆算法构造无向网络的最小生成树。画出最小开始利用普里姆算法构造无向网络的最小生成树。画出最小生成树的构造过程并写出算法执行过程中生成树的构造过程并写出算法执行过程中 closedge 数组状态和最终状数组状态和最终状态。态。2、写出下列二
6、叉树的前序、中序和后序遍历的顺序。写出下列二叉树的前序、中序和后序遍历的顺序。前序序列:前序序列:ABDEHCFI中序序列:中序序列:DBHEACIF后序序列:后序序列:DHEBIFCA四、四、 设有链式存储结构的二叉树,写一算法计算其中树叶结点的数目。设有链式存储结构的二叉树,写一算法计算其中树叶结点的数目。假设二叉树以二叉链表方式存储。假设二叉树以二叉链表方式存储。count=0;int CountLeaf(BiTree T)if (T) if (T-lchild=NULL return OK;CountLeaf(T-lchild);CountLeaf(T-rchild); BCDEHFIA1V1V4V2V5V6V351535213841V1V4V2V5V6V35153521384V1V4V2V5V6V35153521384