数据结构与算法练习试卷5 (题后含答案及解析)
题型有：1. 选择题
选择题（每小题1分，共60分）下列各题A、B、C、D四个选项中，只有一个选项是正确的，请将正确选项涂写在答题卡相应位置上。
1． 二维数组A[0…8，0…9]中的每个元素占2个字节，从首地址300开始，按行优先顺序存放，则元素A[4，5]的存储地址为( )。
A．390 B．326 C．230 D．310
正确答案：A 涉及知识点：数据结构与算法
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，17，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
正确答案：A 涉及知识点：数据结构与算法
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，03，26，34，37，54，60，45，76，78，92 C．18，03，25，34，26，45，37，60，54，92，76，78 D．以上都不正确
正确答案：C 涉及知识点：数据结构与算法
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
正确答案：B 涉及知识点：数据结构与算法
5． 对队列的基本运算，哪个说法是错误的? ( ) A．将队列初始化为空队列 B．求队列的元素个数 C．对队尾元素的删除 D．取出队头元素
正确答案：C 涉及知识点：数据结构与算法
6． 对于一维数组与线性表的叙述正确的是( )。 A．前者长度固定，后者长度可变 B．两者长度都固定 C．两者长度都可变
D．后者长度固定，前者长度可变
正确答案：A 涉及知识点：数据结构与算法 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，30，25，23，5
正确答案：A
解析：选项A已经以5为基数分成了大于5和小于5的两部分，这是快速排序的基本思想，其他选项则没有这个特点，因此用快速排序方法对A排序最快。 知识模块：数据结构与算法
8． 以下关于串的叙述中，哪一条是不正确的? ( ) A．空串是由空格组成的串 B．串是字符的有限序列
C．模式匹配是串的一种重要运算
D．串既可采用顺序存储，也可采用链接存储
正确答案：A 涉及知识点：数据结构与算法
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
正确答案：B 涉及知识点：数据结构与算法
10． 一棵二叉树的前根遍历、后根遍历和中根遍历所产生的序列中，所有叶结点的先后顺序是 ( ) 。
A．不相同 B．完全相同
C．前根遍历与后根遍历相同 D．后根遍历与中根遍历相同
正确答案：B
解析：对二叉树的前根、后根、中根遍历，在遍历右子树的叶子结点前一定会先遍历左子树的叶子结点，因此叶子结点的顺序始终是一样的。 知识模块：数据结构与算法
11． 以下关于广义表的叙述中，正确的是( )。 A．广义表是0个或多个单元素或子表组成的有限序列 B．广义表至少有一个元素是子表 C．广义表不可以是自身的子表 D．广义表不能为空表
正确答案：A 涉及知识点：数据结构与算法
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，68，94，72
正确答案：D 涉及知识点：数据结构与算法
13． 二叉树( )个根结点，按一定的规则，任意一棵树均可转换成惟一对应的二叉树。
A．有且只有1 B．有1或多于1 C．有0或1 D．有至少2
正确答案：C 涉及知识点：数据结构与算法
14． 若对一个已经排好了序的序列进行排序，在下列四种排序方法中；哪种方法比较好?( )
A．冒泡法
B．直接选择法 C．直接插入法 D．归并法
正确答案：C 涉及知识点：数据结构与算法
15． 在下列存储形式中，哪一个不是树的存储形式? ( ) A．孩子兄弟表示法 B．双亲表示法 C．顺序存储表示法 D．孩子链表表示法
正确答案：C 涉及知识点：数据结构与算法
16． 设散列函数为H(k)=k mod 7，现欲将关键码23，14，9，6，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
正确答案：B 涉及知识点：数据结构与算法
17． 一棵4层的满二叉树中，结点总数是( )。 A．31 B．15 C．7 D．13
正确答案：B 涉及知识点：数据结构与算法
18． 对排序文件的初始状态不做任何要求的排序方法是( )。 A．直接插入排序和快速排序 B．直接插入和归并排序 C．归并排序与快速排序 D．归并排序与直接排序
正确答案：A 涉及知识点：数据结构与算法
19． 以下关于顺序存储结构的叙述中，哪一条是不正确的? ( ) A．存储密度大
B．逻辑上相邻的结点物理上不必邻接
C．可以通过计算直接确定任意结点的存储地址
D．插入、删除运算操作不方便
正确答案：B 涉及知识点：数据结构与算法
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)
正确答案：C
解析：一个算法中所有语句重复执行的次数之和构成了该算法的运算时间。题中语句 y++执行了2n-1次，语句x++执行了(2n-1)(3n+1)=6n2-n-1次，则该算法的时间复杂度T(n) =6n2-n-1=O(n2)， 知识模块：数据结构与算法
21． 对于一个栈，给出输入项A，B，C。如果输入项序列由A，B，C所组成，则不可能产生的输出序列是( )。
A．BAC B．ABC C．CAB D．CBA
正确答案：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． 在长度为n的顺序表中，删除第i个元素(0＜i＜n+1)时，需向前移动的元素个数为( )。
A．n-i B．n-i-1 C．n-i+l D．i
正确答案：A 涉及知识点：数据结构与算法
因篇幅问题不能全部显示，请点此查看更多更全内容