资源描述：
《数据结构期末试卷A》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构期末试卷A一、判断题：（共10分，每题1分）1、深度为h的非空二叉树的第i层最多有2i-1个结点。（）2、在完全二叉树中,若某结点无左孩子,则它必是叶结点。（）3、一组权值，可以唯一构造出一棵赫夫曼树。()4、在n个结点的无向图中,若边数多于n-1,则该图必是连通图。（）5、对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。（）6、无向图的邻接矩阵是对称的，有向图的邻接矩阵是不对称的。（）7、折半查找只适用于有序表，包括有序的顺序表和有序的链表。（）8、一个好的哈希函数应使函数值均匀的分布在存储空
2、间的有效地址范围内，以尽可能减少冲突。（）9、在初始数据为逆序时，冒泡排序所执行的比较次数最多。（）10、希尔排序在效率上较直接插入排序有较大的改进。但是不稳定的。（）二、填空题：（共20分，每空2分）1、在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个________,，且存在一条从根到该结点的___________。2、三个结点的二叉树，最多有__________种形状。3、任何一棵二叉树，若n0，n2分别是度为0，2的结点的个数，则n0和n2的关系为_______。4、设有10个值，构成赫夫曼树，则该赫夫曼树共有_______个结点。5、在一个无向图中，所有顶点
3、的度数之和等于所有边数的_______倍。6、一个连通图的生成树是该图的________连通子图。若这个连通图有n个顶点,则它的生成树有________条边。7、如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是____________。8、将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫_____。三、选择题：（共20分，每题2分）1、设x是一棵树，x’是对应于x的二叉树，则x的后根次序遍历和x’的____次序遍历相同A.先序B.中序C.后序D.都不是2、设有100个元素，用折半查找法进行查找时，在查找成功的情况下，最大比较次数是__
4、___。A.100B.50C.99D.73、设散列表长m=14,散列函数H（K）=K％11，已知表中已有4个结点：r(15)=4;r(38)=5;r(61)=6;r(84)=7，其他地址为空，如用二次探测再散列处理冲突，关键字为49的结点地址是________。A.8B.3C.5D.94、在含有n个项点有e条边的无向图的邻接矩阵中，零元素的个数为________。A.eB.2eC.n2-eD.n2-2e5、图的深度优先遍历类似于树的_______。A.先序遍历B.中序遍历C.后序遍历D.层次遍历6、下面关于图的存储的叙述中，哪一个是正确的。________A．用邻接矩阵法存储图,占用的
5、存储空间数只与图中结点个数有关,而与边数无关B．用邻接矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关C．用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关D．用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关7、从堆中删除一个元素的时间复杂度为________。A、O(1)B、O(n)C、O(log2n)D、O(nlog2n)8、用某种排序方法对关键字序列（23，72，21，47，15，27，59，35，20）进行排序时，前三趟的结果情况如下________：23，21，47，15，27，59，35，20，7221，23，15，27
6、，47，35，20，59，7221，15，23，27，35，20，47，59，72则所采用的排序方法是________A.选择排序B.起泡排序C.归并排序D.快速排序9、将一棵有40个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为15的结点的左孩子的编号为______。A.30B.31C.16D.3210、如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是_______A.有向完全图B.连通图C.强连通图D.有向无环图四、应用题：（共28分，每题4分）1、将下图转换为二叉树，对转换后的二叉树进行先序、中序、后序遍历序列。ABCDEFGJ2、什么
7、是赫夫曼（Huffman）树？有一组数值14、21、32、15、28，画出赫夫曼树，并计算其WPL。3、设一个有向图为G=(V,E),其中V={v1,v2,v3,v4}，E={,,,,},画出该有向图，画出相应邻接表，写出从顶点v1出发进行深度优先和广度优先搜索得到的顶点序列。4、用序列（46，88，45，39，70，58，101，10，66，34）建立一个平衡的二叉排序树，
