1、数据结构与算法练习试卷 2 及答案解析(总分：46.00，做题时间：90 分钟)一、选择题(总题数：23，分数：46.00)1.选择题（）下列各题 A、B、C、D 四个选项中，只有一个选项是正确的，请将正确选项涂写在答题卡相应位置上。（分数：2.00）_2.二维数组 A08，09中的每个元素占 2 个字节，从首地址 300 开始，按行优先顺序存放，则元素A4，5的存储地址为( )。（分数：2.00）A.390B.326C.230D.3103.设有关键码序列(16，9，4，25，15，2，13，18，17，5，8，24)，要按关键码值递增的次序排列，采用直接选择排序法，一趟排序后的结果为( )。
2、（分数：2.00）A.2，9，4，25，15，16，13，18，17，5，8，24B.15，4，18，2，16，5，8，24，17，9，13，25C.9，4，16，15，2，13，18，17，5，8，24，25D.9，16，4，25，2，15，13，18，5，17，8，244.已知 12 个数据元素为 34，76，45，18，26，54，92，60，25，37，03，78，对该数据按从小到大排序，若采用希尔排序方法排序，设第一趟排序的增量为 6，第二趟排序的增量为 3，则第二趟排序后的序列为( )。（分数：2.00）A.60，34，25，18，03，54，92，76，45，37，26，78B.
3、18，25，03，26，34，37，54，60，45，76，78，92C.18，03，25，34，26，45，37，60，54，92，76，78D.以上都不正确5.对于初始关键字(49，38，65，97，76，13，27)，使用二路归并排序，第一趟归并之后其序列变为( )。（分数：2.00）A.38，49，65，97，13，27，76B.38，49，65，97，13，76，27C.13，27，38，49，65，76，97D.49，38，65，76，97，13，276.对队列的基本运算，哪个说法是错误的? ( )（分数：2.00）A.将队列初始化为空队列B.求队列的元素个数C.对队尾元素的删除D
4、.取出队头元素7.对于一维数组与线性表的叙述正确的是( )。（分数：2.00）A.前者长度固定，后者长度可变B.两者长度都固定C.两者长度都可变D.后者长度固定，前者长度可变8.对下列关键字序列用快速排序法进行排序时，速度最快的情形是( )。（分数：2.00）A.21，25，5，17，9，23，30B.5，9，17，21，23，25，30C.25，23，30，17，21，5，9D.21，9，17，30，25，23，59.以下关于串的叙述中，哪一条是不正确的? ( )（分数：2.00）A.空串是由空格组成的串B.串是字符的有限序列C.模式匹配是串的一种重要运算D.串既可采用顺序存储，也可采用链接
5、存储10.设栈 S 和队列 Q 的初始状态均为空，元素 e1，e2，e3，e4，e5，e6 依次通过栈 S，一个元素出栈后即进入队列 Q，若 6 个元素出队的顺序是 e2，e4，e3，e6，e5，e1，则栈 S 的容量至少应是( )。（分数：2.00）A.2B.3C.4D.611.一棵二叉树的前根遍历、后根遍历和中根遍历所产生的序列中，所有叶结点的先后顺序是 ( ) 。（分数：2.00）A.不相同B.完全相同C.前根遍历与后根遍历相同D.后根遍历与中根遍历相同12.以下关于广义表的叙述中，正确的是( )。（分数：2.00）A.广义表是 0 个或多个单元素或子表组成的有限序列B.广义表至少有一个
6、元素是子表C.广义表不可以是自身的子表D.广义表不能为空表13.可以将一个堆序列看成是一棵完全二叉树结点的层次序列，下面关键序列( )就是一个堆。（分数：2.00）A.5，72，23，16，68，94B.68，94，23，72，5，16C.5，94，16，68，23，72D.5，23，16，68，94，7214.二叉树( )个根结点，按一定的规则，任意一棵树均可转换成惟一对应的二叉树。（分数：2.00）A.有且只有 1B.有 1 或多于 1C.有 0 或 1D.有至少 215.若对一个已经排好了序的序列进行排序，在下列四种排序方法中；哪种方法比较好?( )（分数：2.00）A.冒泡法B.直接选
7、择法C.直接插入法D.归并法16.在下列存储形式中，哪一个不是树的存储形式? ( )（分数：2.00）A.孩子兄弟表示法B.双亲表示法C.顺序存储表示法D.孩子链表表示法17.设散列函数为 H(k)=k mod 7，现欲将关键码 23，14，9，6，30，12，18 依次散列于地址 O6 中，用线性探测法解决冲突，则在地址空间 06 中，得到的散列表是( )。（分数：2.00）A.14，6，23，9，18，30，12B.14，18，23，9，30；12，6C.14，12，9，23，30，18，6D.6，23，30，14，18，12，918.一棵 4 层的满二叉树中，结点总数是( )。（分数：2
8、.00）A.31B.15C.7D.1319.对排序文件的初始状态不做任何要求的排序方法是( )。（分数：2.00）A.直接插入排序和快速排序B.直接插入和归并排序C.归并排序与快速排序D.归并排序与直接排序20.以下关于顺序存储结构的叙述中，哪一条是不正确的? ( )（分数：2.00）A.存储密度大B.逻辑上相邻的结点物理上不必邻接C.可以通过计算直接确定任意结点的存储地址D.插入、删除运算操作不方便21.下列程序的时间复杂度为( )。 for (i=l；i2n；i+) y+； for(j=0；ja3n；j+) x+； （分数：2.00）A.0(n-1)B.O(2 n )C.0(n 2 )D.
9、O(log 2 n)22.对于一个栈，给出输入项 A，B，C。如果输入项序列由 A，B，C 所组成，则不可能产生的输出序列是( )。（分数：2.00）A.BACB.ABCC.CABD.CBA23.在长度为 n 的顺序表中，删除第 i 个元素(0in+1)时，需向前移动的元素个数为( )。（分数：2.00）A.n-iB.n-i-1C.n-i+lD.i数据结构与算法练习试卷 2 答案解析(总分：46.00，做题时间：90 分钟)一、选择题(总题数：23，分数：46.00)1.选择题（）下列各题 A、B、C、D 四个选项中，只有一个选项是正确的，请将正确选项涂写在答题卡相应位置上。（分数：2.00）
10、_解析：2.二维数组 A08，09中的每个元素占 2 个字节，从首地址 300 开始，按行优先顺序存放，则元素A4，5的存储地址为( )。（分数：2.00）A.390 B.326C.230D.310解析：3.设有关键码序列(16，9，4，25，15，2，13，18，17，5，8，24)，要按关键码值递增的次序排列，采用直接选择排序法，一趟排序后的结果为( )。（分数：2.00）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，25C.9，4，16，15，2，13，18，17，5，8，24，25D.9，16，4，25，2
11、，15，13，18，5，17，8，24解析：4.已知 12 个数据元素为 34，76，45，18，26，54，92，60，25，37，03，78，对该数据按从小到大排序，若采用希尔排序方法排序，设第一趟排序的增量为 6，第二趟排序的增量为 3，则第二趟排序后的序列为( )。（分数：2.00）A.60，34，25，18，03，54，92，76，45，37，26，78B.18，25，03，26，34，37，54，60，45，76，78，92C.18，03，25，34，26，45，37，60，54，92，76，78 D.以上都不正确解析：5.对于初始关键字(49，38，65，97，76，13，27)
12、，使用二路归并排序，第一趟归并之后其序列变为( )。（分数：2.00）A.38，49，65，97，13，27，76B.38，49，65，97，13，76，27 C.13，27，38，49，65，76，97D.49，38，65，76，97，13，27解析：6.对队列的基本运算，哪个说法是错误的? ( )（分数：2.00）A.将队列初始化为空队列B.求队列的元素个数C.对队尾元素的删除 D.取出队头元素解析：7.对于一维数组与线性表的叙述正确的是( )。（分数：2.00）A.前者长度固定，后者长度可变 B.两者长度都固定C.两者长度都可变D.后者长度固定，前者长度可变解析：8.对下列关键字序列用快
13、速排序法进行排序时，速度最快的情形是( )。（分数：2.00）A.21，25，5，17，9，23，30 B.5，9，17，21，23，25，30C.25，23，30，17，21，5，9D.21，9，17，30，25，23，5解析：解析：选项 A 已经以 5 为基数分成了大于 5 和小于 5 的两部分，这是快速排序的基本思想，其他选项则没有这个特点，因此用快速排序方法对 A 排序最快。9.以下关于串的叙述中，哪一条是不正确的? ( )（分数：2.00）A.空串是由空格组成的串 B.串是字符的有限序列C.模式匹配是串的一种重要运算D.串既可采用顺序存储，也可采用链接存储解析：10.设栈 S 和队列
14、 Q 的初始状态均为空，元素 e1，e2，e3，e4，e5，e6 依次通过栈 S，一个元素出栈后即进入队列 Q，若 6 个元素出队的顺序是 e2，e4，e3，e6，e5，e1，则栈 S 的容量至少应是( )。（分数：2.00）A.2B.3 C.4D.6解析：11.一棵二叉树的前根遍历、后根遍历和中根遍历所产生的序列中，所有叶结点的先后顺序是 ( ) 。（分数：2.00）A.不相同B.完全相同 C.前根遍历与后根遍历相同D.后根遍历与中根遍历相同解析：解析：对二叉树的前根、后根、中根遍历，在遍历右子树的叶子结点前一定会先遍历左子树的叶子结点，因此叶子结点的顺序始终是一样的。12.以下关于广义表的
15、叙述中，正确的是( )。（分数：2.00）A.广义表是 0 个或多个单元素或子表组成的有限序列 B.广义表至少有一个元素是子表C.广义表不可以是自身的子表D.广义表不能为空表解析：13.可以将一个堆序列看成是一棵完全二叉树结点的层次序列，下面关键序列( )就是一个堆。（分数：2.00）A.5，72，23，16，68，94B.68，94，23，72，5，16C.5，94，16，68，23，72D.5，23，16，68，94，72 解析：14.二叉树( )个根结点，按一定的规则，任意一棵树均可转换成惟一对应的二叉树。（分数：2.00）A.有且只有 1B.有 1 或多于 1C.有 0 或 1 D.有
16、至少 2解析：15.若对一个已经排好了序的序列进行排序，在下列四种排序方法中；哪种方法比较好?( )（分数：2.00）A.冒泡法B.直接选择法C.直接插入法 D.归并法解析：16.在下列存储形式中，哪一个不是树的存储形式? ( )（分数：2.00）A.孩子兄弟表示法B.双亲表示法C.顺序存储表示法 D.孩子链表表示法解析：17.设散列函数为 H(k)=k mod 7，现欲将关键码 23，14，9，6，30，12，18 依次散列于地址 O6 中，用线性探测法解决冲突，则在地址空间 06 中，得到的散列表是( )。（分数：2.00）A.14，6，23，9，18，30，12B.14，18，23，9，
17、30；12，6 C.14，12，9，23，30，18，6D.6，23，30，14，18，12，9解析：18.一棵 4 层的满二叉树中，结点总数是( )。（分数：2.00）A.31B.15 C.7D.13解析：19.对排序文件的初始状态不做任何要求的排序方法是( )。（分数：2.00）A.直接插入排序和快速排序 B.直接插入和归并排序C.归并排序与快速排序D.归并排序与直接排序解析：20.以下关于顺序存储结构的叙述中，哪一条是不正确的? ( )（分数：2.00）A.存储密度大B.逻辑上相邻的结点物理上不必邻接 C.可以通过计算直接确定任意结点的存储地址D.插入、删除运算操作不方便解析：21.下列
18、程序的时间复杂度为( )。 for (i=l；i2n；i+) y+； for(j=0；ja3n；j+) x+； （分数：2.00）A.0(n-1)B.O(2 n )C.0(n 2 ) D.O(log 2 n)解析：解析：一个算法中所有语句重复执行的次数之和构成了该算法的运算时间。题中语句 y+执行了2n-1 次，语句 x+执行了(2n-1)(3n+1)=6n 2 -n-1 次，则该算法的时间复杂度 T(n) =6n 2 -n-1=O(n 2 )，22.对于一个栈，给出输入项 A，B，C。如果输入项序列由 A，B，C 所组成，则不可能产生的输出序列是( )。（分数：2.00）A.BACB.ABCC.CAB D.CBA解析：解析：此题主要考查栈的后进先出结构特点，输入项序列为 A，B，C，显然可能输出序列可以为CBA，若 A，B，C 都进栈后立即出栈，则输出序列为 ABC，A，B 相继进栈，B 出栈，A 再出栈，最后 C 入栈后出栈，则输出序列为 BAC。因此选项 A，B，D 组合都可能，对选项 C，C 是进栈的最后一个元素，却是最先出栈元素，则必然是 A，B，C 进栈完了之后再出栈，这样 A 不可能先于 B 出栈。23.在长度为 n 的顺序表中，删除第 i 个元素(0in+1)时，需向前移动的元素个数为( )。（分数：2.00）A.n-i B.n-i-1C.n-i+lD.i解析：
