[计算机类试卷]数据结构与算法练习试卷5及答案与解析.doc

1、数据结构与算法练习试卷 5及答案与解析 1 二维数组 A08 ， 09 中的每个元素占 2个字节，从首地址 300开始，按行优先顺序存放，则元素 A4， 5的存储地址为 ( )。 （ A） 390 （ B） 326 （ C） 230 （ D） 310 2 设有关键码序列 (16， 9， 4， 25， 15， 2， 13， 18， 17， 5， 8， 24)，要按关键码值递增的次序排列，采用直接选择排序法，一趟排序后的结果为 ( )。 （ A） 2， 9， 4， 25， 15， 16， 13， 18， 17， 5， 8， 24 （ B） 15， 4， 18， 2， 16， 5， 8， 24， 1

2、7， 9， 13， 25 （ C） 9， 4， 16， 15， 2， 13， 18， 17， 5， 8， 24， 25 （ D） 9， 16， 4， 25， 2， 15， 13， 18， 5， 17， 8， 24 3 已知 12个数据元素为 34， 76， 45， 18， 26， 54， 92， 60， 25， 37， 03， 78，对该数据按从小到大排序，若采用希尔排序方法排序，设第一趟排序的增量为 6，第二趟排序的增量为 3，则第二趟排序后的序列为 ( )。 （ A） 60， 34， 25， 18， 03， 54， 92， 76， 45， 37， 26， 78 （ B） 18， 25， 0

3、3， 26， 34， 37， 54， 60， 45， 76， 78， 92 （ C） 18， 03， 25， 34， 26， 45， 37， 60， 54， 92， 76， 78 （ D）以上都不正确 4 对于初始关键字 (49， 38， 65， 97， 76， 13， 27)，使用二路归并排序，第一趟归并之后其序列变为 ( )。 （ A） 38， 49， 65， 97， 13， 27， 76 （ B） 38， 49， 65， 97， 13， 76， 27 （ C） 13， 27， 38， 49， 65， 76， 97 （ D） 49， 38， 65， 76， 97， 13， 27 5 对队列

4、的基本 运算，哪个说法是错误的 ? ( ) （ A）将队列初始化为空队列 （ B）求队列的元素个数 （ C）对队尾元素的删除 （ D）取出队头元素 6 对于一维数组与线性表的叙述正确的是 ( )。 （ A）前者长度固定，后者长度可变 （ B）两者长度都固定 （ C）两者长度都可变 （ D）后者长度固定，前者长度可变 7 对下列关键字序列用快速排序法进行排序时，速度最快的情形是 ( )。 （ A） 21， 25， 5， 17， 9， 23， 30 （ B） 5， 9， 17， 21， 23， 25， 30 （ C） 25， 23， 30， 17， 21， 5， 9 （ D） 21， 9， 17，

5、 30， 25， 23， 5 8 以下关于串的叙述中，哪一条是不正确的 ? ( ) （ A）空串是由空格组成的串 （ B）串是字符的有限序列 （ C）模式匹配是串的一种重要运算 （ D）串既可采用顺序存储，也可采用链接存储 9 设栈 S和队列 Q的初始状态均为空，元素 e1， e2， e3， e4， e5， e6依次通过栈S，一个元素出栈后即进入队列 Q，若 6个元素出队的顺序是 e2， e4， e3， e6，e5， e1，则栈 S的容量至少应是 ( )。 （ A） 2 （ B） 3 （ C） 4 （ D） 6 10 一棵二叉树的前根遍历、后根遍历和中根遍历所产生的序列中，所有叶结点的先后顺序

6、是 ( ) 。 （ A）不相同 （ B）完全相同 （ C）前根遍历与后根遍历相同 （ D）后根遍历与中根遍历相同 11 以下关于广义表的叙述中，正确的是 ( )。 （ A）广义表是 0个或多个单元素或子表组成的有限序列 （ B）广义表至少有一个元素是子表 （ C）广义表不可以是自身的子表 （ D）广义表不能为空表 12 可以将一个堆序列看成是一棵完全二叉树结点的层次序列，下面 关键序列 ( )就是一个堆。 （ A） 5， 72， 23， 16， 68， 94 （ B） 68， 94， 23， 72， 5， 16 （ C） 5， 94， 16， 68， 23， 72 （ D） 5， 23， 16

7、， 68， 94， 72 13 二叉树 ( )个根结点，按一定的规则，任意一棵树均可转换成惟一对应的二叉树。 （ A）有且只有 1 （ B）有 1或多于 1 （ C）有 0或 1 （ D）有至少 2 14 若对一个已经排好了序的序列进行排序，在下列四种排序方法中；哪种方法比较好 ?( ) （ A）冒泡法 （ B）直接选择法 （ C）直接插入法 （ D）归并法 15 在下列存储形式中，哪一个不是树的存储形式 ? ( ) （ A）孩子兄弟表示法 （ B）双亲表示法 （ C）顺序存储表示法 （ D）孩子链表表示法 16 设散列函数为 H(k)=k mod 7，现欲将关键码 23， 14， 9， 6，

8、 30， 12， 18依次散列于地址 O 6中，用线性探测法解决冲突，则在地址空间 0 6中，得到的散列表是 ( )。 （ A） 14， 6， 23， 9， 18， 30， 12 （ B） 14， 18， 23， 9， 30； 12， 6 （ C） 14， 12， 9， 23， 30， 18， 6 （ D） 6， 23， 30， 14， 18， 12， 9 17 一棵 4层的满二叉树中，结点总数是 ( )。 （ A） 31 （ B） 15 （ C） 7 （ D） 13 18 对排序文件的初始状态不做任何要求的排序方法是 ( )。 （ A）直接插入排序和快速排序 （ B）直接插入和归并排序 （

9、C）归并排序与快速排序 （ D）归并排序与直接排序 19 以下关于顺序存储结构的叙述中，哪一条是不正确的 ? ( ) （ A）存储密度大 （ B）逻辑上相邻的结点物理 上不必邻接 （ C）可以通过计算直接确定任意结点的存储地址 （ D）插入、删除运算操作不方便 20 下列程序的时间复杂度为 ( )。 for (i=l； i 2n； i+) y+； for(j=0； j a3n； j+) x+； （ A） 0(n-1) （ B） O(2n) （ C） 0(n2) （ D） O(log2n) 21 对于一个栈，给出输入项 A， B， C。如果输入项序列由 A， B， C所组成，则不可能产生的输出序

10、列是 ( )。 （ A） BAC （ B） ABC （ C） CAB （ D） CBA 22 在长度为 n的顺序表中，删除第 i个元素 (0 i n+1)时，需向前移动的元素个数为 ( )。 （ A） n-i （ B） n-i-1 （ C） n-i+l （ D） i 数据结构与算法练习试卷 5答案与解析 1 【正确答案】 A 【知识模块】 数据结构与算法 2 【正确答案】 A 【知识模块】 数据结构与算法 3 【正确答案】 C 【知识模块】 数据结构与算法 4 【正确答案】 B 【知识模块】 数据结构与算法 5 【正确答案】 C 【知识模块】 数据结构与算法 6 【正确答案】 A 【知识模块】

11、 数据结构与算法 7 【正确答案】 A 【试题解析】 选项 A已经以 5为基数分成了大于 5和小于 5的两部分，这是快速排序的基本思想，其他选项则没有这个特点，因此用快速排序方法对 A排序最快。 【知识模块】 数据结构与算法 8 【正确答案】 A 【知识模块】 数据结构与算法 9 【正确答案】 B 【知识模块】 数据结构与算法 10 【正确答案】 B 【试题解析】 对二叉树的前根、后根、中根遍历，在遍历右子树的叶子结点前一定会先遍历左子树的叶子结点，因此叶子结点的顺序始终是一样的。 【知识模块】 数据结构与算法 11 【正确答案】 A 【知识模块】 数据结构与算法 12 【正确答案】 D 【知

12、识模块】 数据结构与算法 13 【正确答案】 C 【知识模块】 数据结构与算法 14 【正确答案】 C 【知识模块】 数据结构与算法 15 【正确答案】 C 【知识模块】 数据结构与算法 16 【正确 答案】 B 【知识模块】 数据结构与算法 17 【正确答案】 B 【知识模块】 数据结构与算法 18 【正确答案】 A 【知识模块】 数据结构与算法 19 【正确答案】 B 【知识模块】 数据结构与算法 20 【正确答案】 C 【试题解析】 一个算法中所有语句重复执行的次数之和构成了该算法的运算时间。题中语句 y+执行了 2n-1次，语句 x+执行了 (2n-1)(3n+1)=6n2-n-1次，

13、则该算法的时间复杂度 T(n) =6n2-n-1=O(n2)， 【知 识模块】 数据结构与算法 21 【正确答案】 C 【试题解析】 此题主要考查栈的后进先出结构特点，输入项序列为 A， B， C，显然可能输出序列可以为 CBA，若 A， B， C都进栈后立即出栈，则输出序列为ABC， A， B相继进栈， B出栈， A再出栈，最后 C入栈后出栈，则输出序列为BAC。因此选项 A， B， D组合都可能，对选项 C， C是进栈的最后一个元素，却是最先出栈元素，则必然是 A， B， C进栈完了之后再出栈，这样 A不可能先于 B出栈。 【知识模块】 数据结构与算法 22 【正确答案】 A 【知识模块 】 数据结构与算法