1、数据结构练习试卷 3及答案与解析 1 二叉树 (1)。在完全的二叉树中，若一个结点没有 (2)，则它必定是叶结点。 每棵树都能唯一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子结点是 N在原树里对应结点的 (3)，而 N的右子结点是它在原树里对应结点的 (4)。 （ A）是特殊的树 （ B）不是树的特殊形式 （ C）是两棵树的总称 （ D）是只有两个根结点的树形结构 （ A）左子结点 （ B）右子结点 （ C）左子结点或者没有右子结点 （ D）兄弟 （ A）最左子结点 （ B）最右子结点 （ C）最邻近的右兄弟 （ D）最邻近的左兄弟 （ A）最左子结点 （ B）最右子结点
2、（ C）最邻近的右兄弟 （ D）最邻近的左兄弟 5 在一棵非空二叉树中，叶子节点的总数比度为 2的节点总数多 (43)个。 （ A） -1 （ B） 0 （ C） 1 （ D） 2 6 某二叉树中度为 2的结点有 18个，则该二叉树中有 _个叶子结点。 （ A） 18 （ B） 19 （ C） 8 （ D） 20 7 设一棵二叉树的中序遍历结果为 DBEAFC，前序遍历结果为 ABDECF，则后序遍历结果为 _。 （ A） ACBEGFD （ B） ABCDEFG （ C） ACBEDFG （ D） ABCEDFG 8 假设一棵二叉树的后序遍历序列为 DGJHEBIFCA，中序遍历序列为DBG
3、EHJACIF，则其前序遍历序列为 _。 （ A） ABCDEFGHIJ （ B） ABDEGHJCFI （ C） ABDEGHJFIC （ D） ABDEGJHCFI 9 在深度为 5的满二叉树中，结点的个数为 _。 （ A） 32 （ B） 31 （ C） 16 （ D） 15 10 一棵二叉树中共有 70个叶子结点与 80个度为 1的结点 ，则该二叉树中的总结点数为 _。 （ A） 219 （ B） 221 （ C） 229 （ D） 231 11 对图 8-30所示的二叉树进行后序遍历 (左子树，右子树，根 )的结果是 _。（ A） 5 2 3 4 6 1 （ B） 5 2 3 4 1
4、 6 （ C） 2 6 4 1 3 5 （ D） 2 5 6 4 3 1 12 二叉树的查找有深度优先和广度优先二类，深度优先包括 _。 （ A）前序遍历、后序遍历、中序遍历 （ B）前序遍历、后序遍历、层次遍历 （ C）前序遍历、中序遍历、层次 遍历 （ D）中序遍历、后序遍历、层次遍历 13 无向图的邻接矩阵一定是 _。 （ A）对角矩阵 （ B）稀疏矩阵 （ C）三角矩阵 （ D）对称矩阵 14 为了描述 n个人之间的同学关系，可用 _结构表示。 （ A）线性表 （ B）树 （ C）图 （ D）队列 15 采用邻接表表示一有向图，若图中某顶点的入度和出度分别为 d1和 d2，则该顶点对应
5、的单链表的结点数为 _。 （ A） d1 （ B） d2 （ C） d1-d2 （ D） d1+d2 16 广度优先遍历的含义是：从图中 某个顶点 v出发，在访问了 v之后依次访问 v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，且 “先被访问的顶点的邻接点 ”先于 “后被访问的顶点的邻接点 ”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。 _是图 8-32的广度优先遍历序列。（ A） 1 2 6 3 4 5 （ B） 1 2 3 4 5 6 （ C） 1 6 5 2 3 4 （ D） 1 6 4 5 2 3 17 对于长度为 11的顺序存储的有序表，若采用折
6、半查找 (向下取整 )，则找到第 5个元素需要与表中的 _个元素进行比较操作 (包括与第 5个元素的比较 )。 （ A） 5 （ B） 4 （ C） 3 （ D） 2 18 用二分法来检索数据，最确切的说法是 _。 （ A）仅当数据随机排列时，才能正确地检索数据 （ B）仅当数据有序排列时，才能正确地检索数据 （ C）仅当数据量较大时，才能有效地检索数据 （ D）仅当数据量较小时，才能有效地检索数据 19 若线性表采用链式存储结构，则适用的查找方法为 _。 （ A）随机查找 （ B）散列查找 （ C）二分查找 （ D）顺序查找 20 下列数据结构中， 能用二分法进行查找的是 _ （ A）顺序存
7、储的有序线性表 （ B）线性链表 （ C）二叉链表 （ D）有序线性链表 21 以下各图用树结构描述了 7个元素之间的逻辑关系，其中， _适合采用二分法查找元素。22 对具有 n个元素的有序序列进行二分查找时， _。 （ A）查找元素所需的比较次数与元素的位置无关 （ B）查找序列中任何一个元素所需要的比较次数不超过 1og2(n+1) （ C）元素位置越靠近序列后端，查找该元素所需的比较次数越少 （ D）元素位置越靠近序列前端，查找该元 素所需的比较次数越少 23 采用哈希 (或散列 )技术构造查找表时，需要考虑冲突 (碰撞 )的处理，冲突是指_。 （ A）关键字相同的记录被映射到不同的哈希
8、地址 （ B）关键字依次被映射到编号连续的哈希地址 （ C）关键字不同的记录被映射到同一个哈希地址 （ D）关键字的数目超过哈希地址的数目 24 若线性表 (23,14,45,12,8,19,7)采用散列法进行存储和查找。设散列函数为 H(Key)=Key mod 7并采用线性探查法 (顺序地探查可用存储单元 )解决冲突，则构造的散列表为 _，其中， mod表示整除取余运算。 （ A）哈希地址 0 1 2 3 4 5 6 关键字 14 8 23 45 7 12 19 （ B）哈希地址 0 1 2 3 4 5 6 关键字 7 8 12 14 19 23 45 （ C）哈希地址 0 1 2 3 4
9、 5 6 关键字 7 8 23 45 12 19 14 （ D）哈希地址 0 1 2 3 4 5 6 关键字 14 7 12 8 45 23 19 25 在长度为 64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为_。 （ A） 63 （ B） 64 （ C） 6 （ D） 7 26 前序遍历序列与中序遍历序列相同的二叉树为 (1)，前序遍历序列与后序遍历序列相同的二叉树为 (2)。 （ A）根结点无左子树的二叉树 （ B）根结点无右子树的二 叉树 （ C）只有根结点的二叉树或非叶子结点只有左子树的二叉树 （ D）只有根结点的二叉树或非叶子结点只有右子树的二叉树 （ A）非叶子结点只有
10、左子树的二叉树 （ B）只有根结点的二叉树 （ C）根结点无右子树的二叉树 （ D）非叶子结点只有右子树的二叉树 28 若将图 8-31所示的无向图改为完全图，还需要增加 (1)条边。图 8-32所示的邻接矩阵表示为 (2)(行列均以 A、 B、 C、 D、 E为序 )。 （ A） 1 （ B） 2 （ C） 5 （ D） 15 （ A） （ B） （ C） （ D） 30 图 的存储结构主要有邻接表和 (1)，若用邻接表来存储一个图，则需要保存一个(2)存储的结点表和若干个 (3)存储的关系表 (又称边表 )。 （ A）转移矩阵 （ B）邻接矩阵 （ C）状态矩阵 （ D）优先矩阵 （ A）
11、顺序 （ B）链接 （ C）散列 （ D）分块 （ A）顺序 （ B）链接 （ C）散列 （ D）分块 数据结构练习试卷 3答案与解析 1 【正确答案】 B 【知识模块】 数据结构 2 【正确答案】 A 【知识模块】 数据结构 3 【正确答案】 A 【知识模块】 数据结构 4 【正确答案】 C 【试题解析】 树是结点的有限集合，它有且仅有 1个根结点。二叉树有 0个或 1个根结点，二者是两个不同的概念。所以，第 1空的正确答案为选项 B。 在完全二叉树中，如果一个结点没有左子结点，那么必然没有右子结点，所以就一定是叶结点。第 2空的正确答案为选项 A。 树中每个结点最多只有一个最左边的孩子 (
12、长子 )和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树： 在所有兄弟结点之间加一连线； 对每个结点，除了保留与其长子的连线外，去掉该结点与其他孩子 的连线。 因为树根没有兄弟，所以，树转换为二叉树之后，二叉树的根结点的右子树必然为空。在由树转换成的二叉树中，一个结点 N的左一个结点 N的左子结点是 N在原树里对应结点的最左子结点，而 N的右子结点是它在原树里对应结点的最邻近的右兄弟。所以，第 3空的正确答案为选项 A，第 4空的正确答案为选项 C。 【知识模块】 数据结构 5 【正确答案】 C 【试题解析】 根据二叉树的第 3条性质 “对于任意一棵二叉树，如果其叶结点数为 N
13、0，而度数为 2的结点总数为 N2，则 N0=N2+1”，所以本题应该选择 C。如果对 二叉树的性质不熟悉，也可以用特例来解答此类题目。因为从题目的意思不难理解，这种情况对任何一颗非空二叉树都存在。所以，可以例举一棵最简单的二叉树 只有 3个结点的满二叉树，它只有 1个根， 2个叶子。则度为 2的结点只有 1个根结点，所以叶子结点的总数比度为 2的结点总数多 1个。 【知识模块】 数据结构 6 【正确答案】 B 【试题解析】 二叉树具有如下性质：在任意一棵二叉树中，度为 0的结点 (即叶子结点 )总是比度为 2的结点多一个。根据题意，度为 2的结点为 18个，那么，叶子结点就应当是 19个。因
14、此，本题的 正确答案为选项 B。 【知识模块】 数据结构 7 【正确答案】 A 【试题解析】 基本思路如下： 确定根结点。在前序遍历中，首先访问根结点，因此可以确定前序序列 DBACFEG中的第一个结点 D为二叉树的根结点。 划分左子树和右子树。在中序遍历中，访问根结点的次序为居中，首先访问访问左子树上的结点，最后访问右子树上的结点，可知，在中序序列 ABCDEFG中，以根结点 D为分界线，子序列 ABC在左子树中，子序列 EFG在右子树中。如图 8-22所示。 确定左子树的结构。对于左子树 ABC，位于前序序列 最前面的一个结点为子树的根结点，根据前序遍历结果， B为该子树的根结点，中序序列
15、中位于该根结点前面的结点构成左子树上的结点子序列，位于该根结点后面的结点构成右子树上的结点子序列，所以 A为该左子树的左结点， C为右结点。现在可确定左子树结构如图 8-23所示。 确定右子树的结构。同理，可知右子树的结构。 本二叉树恢复的结果如图 8-24所示。 根据后序遍历的原则，该二叉树后序遍历的结果为ACBEGFD。 【知识模块】 数据结构 8 【正确答案】 B 【试题解析】 这类题目，可以根据所给条件，还原二叉 树，然后再进行前序遍历。还原二叉树的要点是首先确定根结点，再确定左子树的组成结点和右子树的组成结点。然后再针对每个左子树和右子树，继续确定其根结点以及左右子树。重点是，根据后
16、序遍历的特点是，最后一个结点必然为根。中序遍历中，根结点的左边，是左子树的结点，右边是右子树的结点。 分析过程如下： 首先，根据后序遍历为 DGJHEBIFCA，说明这棵二 叉树的根为 A。再根据中序遍历的结果：DBGEHJACIF，说明 DBGEHJ在根结点 A的左边，为左子树上的结点。 CIF在根结点 A的右边，是右子树上的结点。如图 8-25所示。 根据后序遍历结果， DGJHEBIFCA，说明 CIF这棵子树上， C是根结点。再根据 IF在中序遍历中的位置，可知 FI都是其右子树。再根据后序遍历结果，可知， F为根，I是其右结点。如图 8-26所示。 对于 DBGEHJ这棵左子树，根据
17、后序遍历结果可知， B是其根结点。再根据中序遍历结果可知， D是其左子树， GEHJ是其右子树。如图 8-27所 示。 对于 GEHJ这个二叉树，根据后序遍历结果， E为根结点。再根据中序遍历结果， HJ为其右子树。 G为其左子树。如图 8-28所示。 对于 HJ，根据后序遍历结果， H是根，再根据中序遍历结果， J是 H的右子树。构成二叉树如图 8-29所示。 对此二叉树进行前序遍历的结果是：ABDEGHJCFI。选项 B为本题正确答案。 【知识模块】 数据结构 9 【正确答案】 B 【试题解析】 二叉树有如下性质：深度为 m的二叉树最多有 2的 m次方再减 1个结点，也就是 2m-1=25
18、-1=32-1=31。由此可知答案为 B。 【知识模块】 数据结构 10 【正确答案】 A 【试题解析】 二叉树满足如下一条性质，即：对任意一棵二叉树，若终端结点(即叶子结点 )数为 n0，而其度数为 2的结点数为 n2，则 n0=n2+1。根据这条性质可知，若二叉树中有 70个叶子结点，则其度为 2的结点数为 70-1，即 69个。二叉树的总结点数是度为 2、度为 1和叶子结点的总和，因此，题目中的二叉树总结点数为 69+80+70，即 219。因此，本题的正确答案是选项 A。 【知识模块】 数据结构 11 【正确答案】 C 【试题解析】 二 叉树后序遍历的简单描述如下：若二叉树为空，则结束
19、返回。否则： 后序遍历左子树。 后序遍历右子树。 访问根结点。 也就是说，后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。 根据后序遍历的算法，结果是 2 6 4 1 3 5。本题正确答案为选项 C。 【知识模块】 数据结构 12 【正确答案】 A 【试题解析】 二叉树的查找有深度 优先和广度优先两种。深度优先包括：前序遍历、中序遍历和后序遍历。广度优先包括层次遍历。所以，本题正确答案为选项A。 【知识模块】 数据结构 13 【正确答案】 D 【试题解析】 设
20、G=(V,E)是具有 n个顶点的无向图，则 G的邻接矩阵是具有如下性质的 n阶方阵： 显然，在无向图中，如果存在边 (Vi,Vj)，那么，必定存在边 (Vj,Vi)，所以，无向图的邻接矩阵一定是对称矩阵。本题正确答案为选项 D。 【知识模块】 数据结构 14 【正确答案】 C 【试题解析】 n个人之间的同学关系是多 对多的关系，即在这 n个人中的任何 1人都可能存在多个同学。这种关系只有用图来表示最适合，故本题应该选择 C。 【知识模块】 数据结构 15 【正确答案】 B 【试题解析】 图的邻接表表示是由顶点表和边表组成的。对图中每个顶点都建立一个依附于该顶点的单链表，该单链表是以该顶点为弧尾
21、组成，单链表中结点的个数就是该顶点的出度。所以本题应该选择 B。 【知识模块】 数据结构 16 【正确答案】 A 【试题解析】 根据广度优先遍历的定义，首先访问顶点 1，然后访问顶点的邻接点 2或 6。如果先访问 2，则此时的访问序列是 1 2 6，如果先访问 6，则访问序列是 1 6 2。不用再考虑后续遍历，现在就可以看出，只有选项 A符合题意，为正确答案。 【知识模块】 数据结构 17 【正确答案】 B 【试题解析】 对于长度为 11的顺序存储的有序表，若采用折半查找，过程如下： 首先与中间元素也就是第 6个元素进行比较，如果相等，则找到；如果大于此元素，则在第 7个元素与第 11个元素之
22、间进行查找；如果小于此元素，则在第 1个元素和第 5个元素之间进行查找。 在第 1个元素和第 5个元素之间进行查找，需要与第 3个元素进 行比较。 然后在第 4个元素和第 4个元素之间进行查找。需要与第 4个元素进行比较，最后与第 5个元素进行比较。通过上述过程，可以看出，要找到第 5个元素，需要与第 6、 3、 4、 5个元素进行比较，共比较 4次。选项 B为本题正确答案。 【知识模块】 数据结构 18 【正确答案】 B 【试题解析】 二分法检索需要数据已有序排列。它首先取出序列中部的数据进行比较，若相等，则检索成功，否则可排除一半的数据，而从另一半序列中再一次进行二分法检索。故本题应该选择
23、 B。 【知识模块】 数据结构 19 【正确答案 】 D 【试题解析】 对于选项 A，随机查找方式中，在查找元素时，访问表中任意元素所需要的时间，与元素的位置和排列元素没有关系。对于选项 B，使用散列方式时，元素的存储位置与关键字相关。对于选项 C，二分查找适用于有序顺序表。对于选项 D，链式存储结构的特点是，通过指针链接，通常，设置一个指针指向链表中的某个结点，并从该结点出发，开始访问链表中的元素。它只能顺序查找表中的元素。本题正确答案为选项 D。 【知识模块】 数据结构 20 【正确答案】 A 【试题解析】 二分查找只适用于顺序存储的有序表 。在此所说的有序表是指线性表中的元素按值非递减排
24、列 (即从小到大，但允许相邻元素值相等 )的。选项 A正确。 【知识模块】 数据结构 21 【正确答案】 C 【试题解析】 二分查找又称折半查找，它是一种效率较高的查找方法。二分查找要求线性表是有序表，即表中结点按关键字有序。二分查找的基本思想是：首先确定区间的中点位置，然后将待查的值与中点值比较，若相等，则查找成功并返回此位置，若小于中点值，则在左子树 (前半区间 )进行查找，若大于中点值，则在右子树 (后半区间 )进行查找。符合二分查找要求的树，只有选项 C，所以它为正确答案。 【知识模块】 数据结构 22 【正确答案】 B 【试题解析】 二分查找是充分利用了元素间的次序关系，采用分治策略
25、。它的基本思想是，将 n个元素分成个数大致相同的两半，取 an/2与欲查找的 x作比较，如果 x=an/2则找到 x，算法终止。如果 x an/2，则我们只要在数组 a的左半部继续搜索 x(这里假设数组元素呈升序排列 )。如果 x an/2则我们只要在数组 a的右半部继续搜索 x。在二分查找中，查找元素所需的比较次数与元素的位置有关，选项 A的说法错误。元素位置越靠 近序列后端或前端，查找该元素所需的比较次数越多，选项 C和选项 D的说法错误。选项 B的说法正确，本题正确答案为选项B。 【知识模块】 数据结构 23 【正确答案】 C 【试题解析】 哈希 (或散列 )技术是指将数据元素存入查找表
26、时，根据元素的关键字值使用一个提前设定的散列函数计算出元素的存储位置进行查找。通常情况下，散列函数无法实现绝对均匀的散列处理，即可能将关键字不同的数据元素散列到同一个存储单元，这种情况称为冲突，发生冲突的关键字称为同义词。本题正确答案为选项 C。 【知识模块】 数据结构 24 【正确答案】 A 【试题解析】 一开始哈希表为空，首先存储 23，因为 23 mod 7=2，所以， 23存入地址 2的单元格；然后是 14， 14 mod 7=0，所以 14存入 0号单元格； 45 mod 7=3， 45存入 3号； 12 mod 7=5， 12存入 5号； 8 mod 7=1， 8存入 1号； 19
27、 mod 7=5，这时，因为 5号已被 12占据了，根据题意顺序地探查可用存储单元，所以19应该存入 6号；最后一个数 7 mod 7=0，而 0、 1、 2、 3号都已被占据，所以 7被存入 4号。故本题应该选择 A。 【 知识模块】 数据结构 25 【正确答案】 B 【试题解析】 在长度为 64的有序线性表中，其中的 64个数据元素是按照从大到小或从小到大的顺序排列有序的。在这样的线性表中进行顺序查找，最坏的情况就是查找的数据元素不在线性表中或位于线性表的最后。按照线性表的顺序查找算法，首先用被查找的数据和线性表的第一个数据元素进行比较，若相等，则查找成功，否则，继续进行比较，即和线性表的
28、第二个数据元素进行比较。同样，若相等，则查找成功，否则，继续进行比较。依次类推，直到在线性表中查找到该数据或查找到线性表的最后一个元 素，算法才结束。因此，在长度为 64的有序线性表中进行顺序查找，最坏的情况下需要比较 64次。本题正确答案为选项 B。 【知识模块】 数据结构 26 【正确答案】 D 【知识模块】 数据结构 27 【正确答案】 B 【试题解析】 前序遍历的顺序是：根，左子树，右子树。中序遍历的顺序是：左子树，根，右子树。后序遍历的顺序是：左子树，右子树，根。如果前序遍历与中序遍历相同，那么，中序遍历访问的所有左子树访问为空。所以，如果只有根结点，满足此条件。另外，非叶子结点只有
29、右子树，也满足此条件。所以 ，第 1问的正确答案为选项 D。如果前序遍历与后序遍历相同，那么，左右子树必然为空，所以，只有根结点。第 2问的正确答案为选项 B。 【知识模块】 数据结构 28 【正确答案】 C 【知识模块】 数据结构 29 【正确答案】 D 【试题解析】 对于完全无向图，其中任何 2个不同的结点都有一条邻接边；如果结点个数为 m，则完全无向图的边数为： m(m-1)/2 对于本题，结点有 5个，那么，完全无向图的边数应当是： 5(5-1)/2=10 而根据图，已经有了 5条边，所以，还需要增加 10-5=5条边 。本题第 1空的正确答案为选项 C。 邻接矩阵表示顶点间相邻关系的
30、矩阵。若 G是一个具有 n个顶点的图，则 G的邻接矩阵是如下定义的 nn矩阵： Ai,j=1，若 (Vi,Vj)(或 Vi,Vj )是图 G的边； Ai,j=0，若 (Vi,Vj)(或Vi,Vj )不是图 G的边。 根据邻接矩阵的定义，以及本题的条件，矩阵的第一个元素表示 A结点到 A结点的边，显然没有，所以，应当为 0。因此可以排除选项B和选项 C。 另外，因为此图为有向图，所以不是对称的，因而排除选项 A。本题第 2空的正确答案为选项 D。 【知识模块】 数据结构 30 【正确答案】 B 【知识模块】 数据结构 31 【正确答案】 A 【知识模块】 数据结构 32 【正确答案】 B 【试题解析】 常用的图存储结构有邻接表和邻接矩阵。第 1空的正确答案为选项B。若用邻接表来存储一个图，则需要保存一个顺序存储的结点表和若干个链接存储的关系表 (又称边表 )。所以，本题第 2空的正确答案为选项 A，第 2空的正确答案为选项 B。 【知识模块】 数据结构
