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

《《数据结构》考试题型及说明(西华大学)(补考试卷闭卷)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、〈数据结构〉考试题型及说明（补考试卷闭卷）一、单项选择题：（每题2分，共30分）1、设根结点的高度为0，则高度为k的二叉树的最大结点数为（）。A)kB)2k-1C)2k+1-1D)2k-1+12、任何一棵二叉树上都有（）空链域。A).不确定B).2n+1C).n+1D).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).自己GB).G的极大连通子图C).G的

2、极小连通子图D).G的每一个连通子图5、对于任何一棵二叉树T，如果其终端结点树为n0，度为2的结点数为n2，则（）A)n0=n2+1B)n2=n0+1C)n0=2n2+1D)n2=2n0+16、设有一足够的的栈，入栈元素顺序为W，X，Y，Z，判断下列哪一个出栈序列是不可能的序列（）A)Z，W，Y，XB)X，Y，Z，WC)Z，Y，X，WD)Y，Z，X，W7、对于队列只能在（）插入元素A）队尾B)队首C)队中D)队中任意位置8、无向图的邻接矩阵的第i行元素之和是顶点i的().A).出度与入度之和B).出度C).入度D).度9、下列关于赫夫曼树的叙述错误的是

3、（）a)赫夫曼树的根结点的权值等于所有叶结点的权值之和b)具有n个叶结点的赫夫曼树共有2n－1个结点c)赫夫曼树是带权外路径长度最短的二叉树d)赫夫曼树一个结点的度可以是0、1或210、二叉树中不存在（）的结点。A）度为0B)度为1C)度为2D)度大于211、线形表、栈、队列都是（）结构。A）数组B)线形C)图D)树12、循环链表中最后一个结点的指针域将指向（）。A）表中任意结点B)空结点C)头结点D)尾结点13、设有向图G有n个顶点m条边，则其邻接表中表结点数是（）A)nB)2nC)mD)2m14、通常以“和给定值进行比较的关键字个数的期望值”称为（

4、）。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"比较的关键字。

5、(10分)六、对于A,B,C,D,E,F,G,H给定权值序列为W={5，30，7，6，14，25，3,9}，求出其赫夫曼树(可以图示)（15分）七、用类C（或标准C）语言写出写出将串中的非小写字母从串中删除，串用单链表表示，且每个结点只存一个字符。（15分）