《数据结构》考试题型及说明(西华大学)(补考试卷闭卷).doc

数据结构考试题型及说明 （补考试卷闭卷）一、 单项选择题：（每题2分，共30分）1、设根结点的高度为0，则高度为k的二叉树的最大结点数为（ ）。A) k B) 2k -1 C) 2k+1 -1 D) 2k-1 +12、任何一棵二叉树上都有（ ）空链域。A). 不确定 B). 2n+1 C). n+1 D). n3、判断下列序列中，哪个不是线性表（ ）。A) （18，23，54，55，6） B) （A，b，C，d，E） C） （1，2，3，x，Y） D) （MON，TUE，FRI，SUN）4、无向图G的连通分量是指（ ）.A).自己G B).G的极大连通子图 C).G的极小连通子图 D).G的每一个连通子图5、对于任何一棵二叉树T，如果其终端结点树为n0，度为2的结点数为n2，则（ ）A) n0=n2+1 B) n2=n0+1 C) n0=2n2+1 D) n2=2n0+16、设有一足够的的栈，入栈元素顺序为W，X，Y，Z，判断下列哪一个出栈序列是不可能的序列（ ）A) Z，W，Y，X B) X，Y，Z，W C ) Z，Y，X，W D) Y，Z，X，W7、对于队列只能在（ ）插入元素A）队尾 B)队首 C)队中 D)队中任意位置8、无向图的邻接矩阵的第i行元素之和是顶点i的( ).A). 出度与入度之和 B). 出度 C). 入度 D). 度9、下列关于赫夫曼树的叙述错误的是（ ）a) 赫夫曼树的根结点的权值等于所有叶结点的权值之和b) 具有n个叶结点的赫夫曼树共有2n1个结点c) 赫夫曼树是带权外路径长度最短的二叉树d) 赫夫曼树一个结点的度可以是0、1或210、二叉树中不存在（ ）的结点。A）度为0 B) 度为1 C) 度为2 D) 度大于211、线形表、栈、队列都是（ ）结构。A）数组 B) 线形 C)图 D)树12、循环链表中最后一个结点的指针域将指向（ ）。 A）表中任意结点 B) 空结点 C)头结点 D)尾结点13、设有向图G有n个顶点m条边，则其邻接表中表结点数是（ ）A) n B) 2n C) m D) 2m14、通常以“和给定值进行比较的关键字个数的期望值”称为（ ）。 A）长度 B) 查找长度 C)平均查找长度 D)查找15、若希望在插入排序过程中不移动记录，只有改变存储结构，进行（ ）。 A）链表插入排序 B) 线形表插入排序 C)队列插入排序 D)折半插入排序二、说明任意N个结点的二叉树中一定有N+1个空指针，为什么？（10分）三、说明线性表的顺序结构和链式结构各自的优缺点。(10分)四、已知第5层有3个叶子结点的完全二叉树，可以构造出多少种？各自有多少个结点？(10分)五、在关键字序列（07，12，15，18，27，32，41，92）中用二分查找法查找和给定值92相等的关键字，请写出查找过程中依次和给定值92比较的关键字。(10分)六、对于A,B,C,D,E,F,G,H给定权值序列为W=5，30，7，6，14，25，3 ,9，求出其赫夫曼树 (可