1、数据结构练习试卷 2及答案与解析 1 下列对于线性链表的描述中正确的是 _。 （ A）存储空间不一定连续，且各元素的存储顺序是任意的 （ B）存储空间不一定连续，且前件元素一定存储在后件元素的前面 （ C）存储空间必须连续，且前件元素一定存储在后件元素的前面 （ D）存储空间必须连续，且各元素的存储顺序是任意的 2 在程序的执行过程中，用 _结构可以实现嵌套调用函数的正确返回。 （ A）队列 （ B）栈 （ C）树 （ D）图 3 堆栈操作中， _保持不变。 （ A）堆栈的 顶 （ B）堆栈中的数据 （ C）堆栈指针 （ D）堆栈的底 4 判断一个表达式中左右括号是否匹配，采用 _实现较为方便
2、。 （ A）线性表的顺序存储 （ B）队列 （ C）线性表的链式存储 （ D）栈 5 在执行递归过程时，通常使用的数据结构是 _。 （ A）堆栈 (stack) （ B）队列 (queue) （ C）图 (graph) （ D）树 (tree) 6 若需将一个栈 S中的元素逆置，则以下处理方式中正确的是 _。 （ A）将栈 S中元素依次出栈并入栈 T，然后栈 T中元素依 次出栈并进入栈 S （ B）将栈 S中元素依次出栈并入队，然后使该队列元素依次出队并进入栈 S （ C）直接交换栈顶元素和栈底元素 （ D）直接交换栈顶指针和栈底指针 7 字符串是一种线性表，其特殊性表现在 _。 （ A）它的
3、数据元素是一个字符 （ B）它可以链式存储 （ C）它可以顺序存储 （ D）它的数据元素可以是多个字符 8 数组 A-55,08按列存储。若第一个元素的首地址为 100，且每个元素占用 4个存储单元，则元素 A2,3的存储地址为 _。 （ A） 244 （ B） 260 （ C） 364 （ D） 300 9 若二维数组 P15,08的首地址为 base，数组元素按行存储，且每个元素占用 1个存储单元，则元素 P3,3在该数组空间的地址为 _。 （ A） base+13 （ B） base+16 （ C） base+18 （ D） base+21 10 已知有一维数组 T0m*n-1，其中 m
4、 n。从数组 T的第一个元素 (T0)开始，每隔 n个元素取出一个元素依次存入数组 B1m中，即 B1=T0， D2=Tn，依此类推，那么放入 Bk(1kn)的元素是 _。 （ A） T(k-1)*n （ B） T(k*n) （ C） T(k-1)*m （ D） Tk*m 11 已知 N个数已存入数组 A1M的前 N个元素中 (N M)，为在 Ai(1iN)之前插入一个新数，应先 _，以挪出一个空闲位置插入该数。 （ A）从 Ai开始直到 A1，每个数向后移动一个位置 （ B）从 A1开始直到 Ai，每个数向后移动一个位置 （ C）从 Ai开始直到 AN，每个数向前移动一个位置 （ D）从 A
5、N开始 直到 Ai，每个数向后移动一个位置 12 设数组 a13,14中的元素以列为主序存放，每个元素占用 1个存储单元，则数组元素 a2,3相对于数组空间首地址的偏移量为 _。 （ A） 6 （ B） 7 （ C） 8 （ D） 9 13 设 W为一个二维数组，其每个数据元素 Wij占用 6个字节，行下标 i从 0到 8，列下标 j从 2到 5，则二维数组 W的数据元素共占用 (1)个字节。 W中第 6行的元素和第 4列的元素共占用 (2)个字节。 若按行顺序存放二维数组 W，其起始地址的字节号为 100，则二维数组 W的最 后一个数据元素的起始地址的字节号为 (3)，数据元素 w34的起始
6、地址号为 (4)。 （ A） 480 （ B） 192 （ C） 216 （ D） 144 （ A） 78 （ B） 72 （ C） 66 （ D） 84 （ A） 310 （ B） 311 （ C） 315 （ D） 314 （ A） 179 （ B） 178 （ C） 184 （ D） 185 17 对矩阵压缩存储的主要目的是 _。 （ A）方便运算 （ B）节省存储空间 （ C）降低计算复杂度 （ D）提高运算效率 18 数据结构中的树最适合用来表示 _的情况。 （ A）数据元素有序 （ B）数据元素之间具有多对多关系 （ C）数据元素无序 （ D）数据元素之间具有一对多关系 19 对于
7、 n个元素的关键字序列 k1,k2,k n，若将其按次序对应到一棵具有 n个结点的完全二叉树上，使得任意结点都不大于其孩子结点 (若存在孩子结点 )，则称其为小顶堆。根据以上定义， _是小顶堆。20 设有二叉树如图 8-15所示。 对此二叉树先序遍历的结果为_。 （ A） ABCDEF （ B） BDAECF （ C） ABDCEF （ D） DBEFCA 21 二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值；其左、右子树本身就是两棵二叉排序树。根据该定义，对一棵非空的二叉排序
8、树进行 _遍历，可得到一个结点元素的递增序列。 （ A）先序 (根、左、右 ) （ B）中序 (左、根、右 ) （ C）后序 (左、右、根 ) （ D）层序 (从树根开始，按层次 ) 22 对图 8-16所示的二叉树进行中序遍历 (左子树，根，右子树 )的结果是 _。（ A） 2 5 3 4 6 1 （ B） 2 5 3 4 1 6 （ C） 2 6 5 4 1 3 （ D） 2 6 4 5 3 1 23 考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值，并小于等于其右子树上的一切结点的值。 现把 9个数1,2,3,48,9 填入图 8-18所示的二叉树的 9
9、个结点中，并使之具有上述性质，此时N1的值是 (1)， N2的值是 (2)， N9的值是 (3)。现欲把 放入此树并使该树保持前述性质，增加的一个结点可以放在 (4)。（ A） 1 （ B） 2 （ C） 3 （ D） 4 （ E） 7 （ A） 1 （ B） 2 （ C） 3 （ D） 4 （ E） 5 （ A） 1 （ B） 2 （ C） 3 （ D） 6 （ E） 5 （ A） N1下面 （ B） N8下面 （ C） N9下面 （ D） N6下面 27 在深度为 7的满二叉树中，叶子结点的个数为 _。 （ A） 32 （ B） 31 （ C） 64 （ D） 63 28 在具有 100个
10、结点的树中，其边的数目为 _。 （ A） 101 （ B） 100 （ C） 99 （ D） 98 29 设某种二叉树有如下特点：结点的子树数 目不是 2个，则是 0个。这样的一棵二叉树中有 m(m 0)个子树为 0的结点时，该二叉树上的结点总数为 _。 （ A） 2m+1 （ B） 2m-1 （ C） 2(m-1) （ D） 2(m+1) 30 对于二维数组 a14,36，设每个元素占两个存储单元，若分别以行和列为主序存储，则元素 a3,4相对于数组空间起始地址的偏移量分别是 (1)和 (2)。 （ A） 12 （ B） 14 （ C） 16 （ D） 18 （ A） 12 （ B） 14
11、（ C） 16 （ D） 18 32 满二叉树的特点是每层上的结点 数都达到最大值，因此对于高度为 h(h 1)的满二叉树，其结点总数为 (1)。对非空满二叉树，由根结点开始，按照先根后子树、先左子树后右子树的次序，从 1、 2、 3、 依次编号，则对于树中编号为 i的非叶子结点，其右子树的编号为 (2)(高度为 3的满二叉树如图 8-17所示 )。（ A） 2h （ B） 2h-1 （ C） 2h-1 （ D） 2h-1+1 （ A） 2i （ B） 2i-1 （ C） 2i+1 （ D） 2i+2 数据结构练习试卷 2答案与解析 1 【正确答案】 A 【试题解析】 在链式存储结构中，存储数
12、据 的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，数据元素之间的逻辑关系，是由指针域来确定的。由此可见，选项 A的描述正确。因此，本题的正确答案为A。 【知识模块】 数据结构 2 【正确答案】 B 【试题解析】 每当程序要调用一个函数时，系统会将调用前的状态保存起来，等到调用返回时再恢复到调用前的状态。所以，当函数嵌套调用时，最先被调用的函数肯定要等到它嵌套调用的其他函数都返回了，才会最后一个返回。即先保存的状态需要最后才能被恢复，这正好符合栈的先进后出的特点。所以 ，用栈结构可以实现嵌套调用函数的正确返回。选项 B为本题正确答案。 【知识模块】 数据结构 3
13、【正确答案】 D 【试题解析】 堆栈是只能通过访问它的一端 (栈顶 )来实现数据存储和检索的一种线性数据结构。由此可见，在对堆栈操作的过程中，栈顶会发生变化，堆栈中的数据肯定会变，堆栈指针通常指向下一个出栈数据的位置，故也会发生变化。唯一不变的只有堆栈的底，所以应该选择 D。 【知识模块】 数据结构 4 【正确答案】 D 【试题解析】 判断一个表达式中的左右括号是否匹配，一般使用的算法是从 左至右扫描表达式，碰到左括号，就将其压入一个堆栈，碰到右括号，就到堆栈中弹出一个左括号，并判断两个括号类型是否一致。就这样，如果碰到要弹出左括号时堆栈为空，或者两个括号类型不一致，或者扫描完整个表达式堆栈不
14、为空，则均可断定表达式中存在括号不匹配的情况。所以，本题应采用的数据结构是栈，选项 D为正确答案。 【知识模块】 数据结构 5 【正确答案】 A 【试题解析】 当过程被调用时，通常会先将现场保存起来，等到过程返回时，再恢复现场。当一个过程直接或间接地调用了自身，则该过程就被称为递归过程。当过 程递归地调用时，会连续地保存现场，而回溯时则会连续地恢复现场。现场的保存和恢复是先进后出的，这跟数据结构中的堆栈的工作方式很相似。故在执行递归过程时，通常使用的数据结构是堆栈。 【知识模块】 数据结构 6 【正确答案】 B 【试题解析】 栈的特点是先进后出。队列的特点是先进先出。对于选项 A，首先，将栈
15、S中元素依次出栈并入栈 T，那么，现在栈 T中的元素是栈 S中的元素的逆序。然后，栈 T中元素依次出栈并进入栈 S，那么，栈 S中的元素又是栈 S中的元素的逆序，实际上，就以原来的顺序放置。所以，本选项不满足 题目要求。对于选项 A，首先，将栈 S中元素依次出栈并入队，那么，现在队头的元素是栈 S中的栈顶元素，队尾元素是栈 S的栈底元素。然后，该队列元素依次出队并进入栈 S，因为队是先进先出，所以，队头元素 (也就是原来的栈顶元素 )成为栈S的栈底元素，队尾元素 (也就是原来的栈底元素 )成为栈 S中的栈顶元素。实现了逆序放置。所以，本选项为正确答案。选项 C和选项 D不符合栈结构的操作要求。
16、 【知识模块】 数据结构 7 【正确答案】 A 【试题解析】 任何线性表即可以链式存储也可以顺序存储，所以选项 B和选项 C都不能表 现字符串的特殊性。字符串是由某字符集上的字符所组成的任何有限字符序列。所以其每个数据元素都只能是 1个字符，而不能为多个字符，故本题应该选择 A。 【知识模块】 数据结构 8 【正确答案】 B 【试题解析】 数组 A-55,08)如果按列存储的话，在内存中的顺序就是： A-5,0， A-4,0， A-3,0， ， A4,8， A5,8。我们把 A-5,0 A5,0称为第 0列；A-5,1) A5, 1称为第 1列 ，则元素 A2,3之前共有 0 2，三个整列，每
17、列有 -5 5共 11个元素。并且，在第 3列中，元素 A2,3之前还有 A-5,3 A1,3这 7个元素。所以，元素 A2,3之前共有 113+7=40个元素。首地址为 100，且每个元素占用 4个存储单元，则元素 A2,3的存储地址为 100+404=260。 【知识模块】 数据结构 9 【正确答案】 D 【试题解析】 根据定义，二维数组 P15,08中的元素可表示如下： P1,0P1,1P1,2P1,3P1,4P1,5P1,6P1,7P1,8 P2,0P2,1P2,2P2,3P2,4P2,5P2,6P2,7P2,8 P3,0P3,1P3,2P3,3P3,4P3,5P3,6P3,7P3,8
18、 P4,0P4,1P4,2P4,3P4,4P4,5P4,6P4,7P4,8 P5,0P5,1P5,2P5,3P5,4P5,5P5,6P5,7P5,8 数组空间首地址为 base，也就是说元素 P1,0的存储地址为 base，按行存储时，P3,3之前存储了 29+3个元素，因此 P3,3在该数组安间的地址为 base+21。 【知识模块】 数据结构 10 【正确答案】 A 【试题解析】 根据题意，每隔 n个元素取出一个元素依次存入数组 B(1m中。所以，不难推导出 B1=T0， B2=Tn， B3=T2n， ， Bk=T(k-1)n 故本题应该选择 A。 【知识 模块】 数据结构 11 【正确答
19、案】 D 【试题解析】 根据题干内容，数组 A1M元素的结构如图 8-10所示。 对于选项 A，从Ai开始直到 A1，每个数向后移动一个位置，那么，首先移动 Ai到 Ai+1的位置时，会覆盖 Ai+1的内容。而且，最后挪出的空闲位置为 A1，如图 8-11所示。显然，不符合题意。 对于选项 B，首先A1内容向后移动到 A2内容，那么， A2的内容被 A1的内容所覆盖， A2内容再继续向后移，实际上是将 A1内容又覆盖了 A3内容。依此类 推。最后，A2 Ai的值都变成了 A1的值。空闲位置是 A1。如图 8-12所示。也不符合题意。 对于选项C，从 Ai开始直到 AN，每个数向前移动一个位置，
20、那么，首先移动 Ai到 Ai-1的位置时，会覆盖 Ai-1的内容， Ai的内容变成 Ai+1，依此类推， AN-1的内容成为 AN的内容。而且，最后挪出的空闲位置为 AN，如图 8-13所示。显然，不符合题意。 对于选项 D，从AN开始直到 Ai，每个数向后移动一个位置，那么，首先移动 AN到 AN+1的位 置时，会覆盖 AN+1的内容， AN-1的内容移入 AN，依此类推， Ai的内容移入 Ai+1。而且，最后挪出的空闲位置为 Ai，如图 8-14所示。显然符合题意。本题正确答案为选项 D。【知识模块】 数据结构 12 【正确答案】 B 【试题解析】 当数组元素以列为主序存储时，首先存储第
21、1列的所有元素，然后存储第 2列的所有元素，再存储第 3列的所有元素，以此类推，最后存储最后一列的所有元素。数组元素 a2,3表示是在第 3行的第 2个元素。所以，根据以列为主序存储元素的方式，它的位置 前有 2列元素，再加上两个元素，所以，它的位置为 2*3+2=8，相对第一个元素的偏移量为 8-1=7。本题正确答案为选项 B。 【知识模块】 数据结构 13 【正确答案】 C 【知识模块】 数据结构 14 【正确答案】 B 【知识模块】 数据结构 15 【正确答案】 A 【知识模块】 数据结构 16 【正确答案】 C 【试题解析】 行下标为 0 8，说明有 8-0+1=9行；列下标 2 5，
22、说明有 5-2+1=4列。所以共有 94=36个元素。因为每个元素占 6个字节，所以，该数组 共占636=216个字节。所以，第 1空的正确答案为选项 C。 每个元素占 6个字节，每行有 4个元素，则每行占 64=24个字节。每列有 9个元素，所以，每列占69=54个字节。对于第 6行和第 4列的元素，因为有 W64既属于第 6行，又属于第 4列，所以，不应当重复计算。因此，第 6行和第 4列的元素应当占 24+54-6=72个字节。第 2空的标准答案为选项 B。 第一个元素的起始地址为 100，前面已经计算过，该数组所有元素共占用 216个字节。那么，最后一个元素的起始地址就是 100+21
23、6-6=310。最后一个元素要占用 6个 字节，所以要在计算中减去 6。第 3个空的正确答案为选项 A。 如果按行存放数组，那么，存放顺序为，首先是第 0行的 4个元素，然后是第 1行的 4个元素，以此类推。 W34即第 3行第 4列，前面已有存储了 3行又两个元素，也就是 34+2=14个元素。所以， W34的起始地址为 100+614=184。第 4个空的正确答案为选项 C。 【知识模块】 数据结构 17 【正确答案】 B 【试题解析】 多个相同的非零元素只分配一个存储空间，对零元素分配存储空间的方法，就是矩阵压缩存储，这样可以节省存储空间，所以，选项 B正 确。 【知识模块】 数据结构
24、18 【正确答案】 D 【试题解析】 树结构中一个数据元素可以有两个或两个以上的直接后继元素，可以用来描述客观世界中广泛存在的层次关系。树是 n(n0)个结点的有限集合。当n=0时称为空树。在任一非空树 (n 0)中，有且仅有一个称为根的结点；其余结点可分为 m(m0)个互不相交的有限集 T1,T2,Tm ，其中每个集合又都是一棵树，并且称为根结点的子树。因此，树中数据元素之间具有一对多的逻辑关系。本题正确答案为选项 D。 【知识模块】 数据结构 19 【 正确答案】 D 【试题解析】 对于 n个元素的关键字序列 k1,k2,k n，当且仅当满足下列关系时称其为堆： KiK2i且 KiK2i+
25、1 或者 KiK2iK2i+1 其中， 1in/2，满足 式称为小顶堆，满足 式称为大顶堆。 显然，题目中选项 A中 25与 23和 51之间的关系不满足小顶堆的定义；选项 B中 51与 63和 25之间、 55与 23之间的关系不满足小顶堆的定义；选项 C的情况与 B类似。选项 D是小顶堆，为本题正确答案。 【知识模块】 数据结构 20 【正确答案】 C 【 试题解析】 二叉树的遍历分为先序、中序、后序三种不同方式。本题要求先序遍历，其遍历顺序应该为：访问根结点 -先序遍历左子树 -先序遍历右子树。按照定义，先序遍历序列是 ABDCEF，故答案为 C。 【知识模块】 数据结构 21 【正确答
26、案】 B 【试题解析】 中序遍历二叉树的操作定义为：若二叉树为空，则进行空操作；否则： 中序遍历根的左子树； 访问根结点； 中序遍历根的右子树。 显然，根据二叉排序树的定义，对一棵非空的二叉排序树进行中序遍历，可得到一个结点元素的递增 序列。本题正确答案为选项 B。 【知识模块】 数据结构 22 【正确答案】 D 【试题解析】 根据中序遍历的特点，先遍历左子树，然后是根，再遍历右子树，结果是 2 6 4 5 3 1。本题正确答案为选项 D。 【知识模块】 数据结构 23 【正确答案】 E 【知识模块】 数据结构 24 【正确答案】 D 【知识模块】 数据结构 25 【正确答案】 D 【知识模块
27、】 数据结构 26 【正确答案】 B 【试题解析】 要按照题目要求填结点，那么，左下角的结点 n7应当具有最小值，也就是 1，右下角的结点 n6，应当具有最大值，也就是 9。如图 8-19所示，现在考虑将 2、 3、 4、 5、 6、 7、 8放入其中。 现在，不考虑 n7和 n6，在要放入数值的树中，其左下角结点为 n4，放入剩余数字的最小值 2，根据题目对此树的要求， n8应当放入 3。右下角结点为 n3，放入剩余数字的最大值为 8，根据题目要求， n1应当放入 7。结果如图 8-20所示。 现在只剩下 4、 5、 6了，根据题目要求，显然应当在 n2放入 4， n5放入 5， n6放入
28、6。最终结果如图 8-21所示。所以，第 1空的正确答案为选项 G，第 2空的 正确答案为选项 D，第 3空的正确答案为选项 F。 要使此树保持题目要求的特点，放入 3.5，那么，可放到 n8下面，作为它的右子树。第 4空的正确答案为选项 B。 【知识模块】 数据结构 27 【正确答案】 C 【试题解析】 在二叉树的第 k层上，最多有 2k-1(k1)个结点。对于满二叉树来说，每一层上的结点数都达到最大值，即在满二叉树的第 k层上有 2k-1个结点。因此，在深度为 7的满二叉树中，所有叶子结点在第 7层上，即其结点数为 2k-1=27-1=64。因此，本题的正确答案为 C。 【知识模块】 数
29、据结构 28 【正确答案】 C 【试题解析】 在树中，所有的边必定连接了 1对父子结点，并且除根结点以外的其余结点都有且仅有 1个父结点。所以，边的个数等于除根结点以外的其余结点的个数。又因为 1，棵树只有 1个根结点，所以 1棵树的边数等于它的结点数减1。故本题应该选择 C。 【知识模块】 数据结构 29 【正确答案】 B 【试题解析】 在任意一棵二叉树中，若终端结点的个数为 n0，度为 2的结点数为 n2，则： n0=n2+1 根据题意， n0=m，则 n2=n0-1=m-1。 所 以，结点总数为： n0+n2=m+(m-1)=2m-1 本题正确答案为选项 B。 【知识模块】 数据结构 3
30、0 【正确答案】 D 【知识模块】 数据结构 31 【正确答案】 A 【试题解析】 每一个二维数组都可以被看作是一个矩阵。本题的二维数组a14,36的矩阵如下： 以行为主序存储，即以 a1,3、a1,4、 a1,5、 a1,6、 a2,3 这样的顺序连续存储，不难看出， a3,4是第 10个元素。第 1个元素的地址就是数组空间的起始地址，所以其 偏移量为 0，那么a3,4的偏移量难道为 9?千万不要忘记题目的要求 “每个元素占两个存储单元 ”，所以 a3,4的偏移量是 9*2=18。故第 1空应该选择 D。 以列为主序存储，即以a1,3、 a2,3、 a3,3、 a4,3， a1,4 这样的顺
31、序连续存储，所以 a3,4是第 7个元素。那么 a3,4的偏移量就是 6*2=12。故第 2空应该选择 A。 【知识模块】 数据结构 32 【正确答案】 C 【知识模块】 数据结构 33 【正确答案】 C 【试题解析】 满二叉树的第 1层 (树根 )有 1个结点，第二层有 2个结点，第三层有4个结点，依此类推，第 h层有 2h-1个结点。将所有层上的结点数相加就是树中的结点总数，即 20+21+22+2 h-1=2h-1。第 1空的正确答案为选项 C。显然对非空满二叉树中的结点按照题目中的方式进行编号，结点 i的左子树编号为 2i，右子树编号为 2i+1。第 2空的正确答案为选项 C。 【知识模块】 数据结构
