【计算机类职业资格】数据结构与算法练习试卷1及答案解析.doc

1、数据结构与算法练习试卷 1 及答案解析(总分：48.00，做题时间：90 分钟)一、选择题(总题数：24，分数：48.00)1.选择题（）下列各题 A、B、C、D 四个选项中，只有一个选项是正确的，请将正确选项涂写在答题卡相应位置上。（分数：2.00）_2.一棵具有 5 层的完全二叉树中，结点总数最少是( )。（分数：2.00）A.15B.5C.16D.313.设 n、m 为一棵二叉树上的两个结点，在中序遍历时，若 n 在 m 的前面，则( )。（分数：2.00）A.n 为树的左子树上的结点，m 为右子树上的结点B.n 是 m 的祖先结点C.n 的层次比 m 层次高D.n 在 m 的左方4.对

2、于深度为 n，结点数为 k，有 m 个叶子结点的满二叉树，下列关系正确的是( )。（分数：2.00）A.k=m+nB.k=-2“-1C.n+m=2kD.re=k-15.快速排序方法在( )条件下最不利于发挥其长处。（分数：2.00）A.待排序序列中含有多个相同关键字B.待排序序列数据基本有序C.待排序序列数据量很大D.待排序序列元素个数为奇数6.在每一趟排序时，都将待排序序列中最大关键字选出来，并将此关键字从待排序序列中删除，继续对剩余元素进行同样操作的排序方法称之为( )。（分数：2.00）A.快速排序B.堆排序C.起泡捧序D.选择排序7.设有 1000 个无序的元素，希望用最快的方式挑选出

3、其中前 10 个最大元素，效率最高的排序方法是( )。（分数：2.00）A.堆排序B.快速排序C.基数排序D.起泡排序8.设哈希表长 m=14，哈希函数 H(key)=key%ll，表中已经有 4 个结点： addr(13)=4； addr(28)=5 addr(51)=6； addr(77)=7 如果用线性探测再与散列法处理冲突，关键字为 49 的结点地址为( )。（分数：2.00）A.8B.5C.9D.39.对于一个序列中的若干元素，若想得到某个元素之前的部分排序，最好采用什么排序方法? ( )（分数：2.00）A.快速排序B.堆排序C.基数排序D.希尔排序10.采用顺序查找法查找长度为

4、n 的线性表时，每个元素的平均查找长度为( )，（分数：2.00）A.(n+1)/2B.(n-1)/2C.n/2D.n11.一个有序表2，4，7，12，23，45，62，76，77，89，93，95，100，若采用二分查找法查找值为 93的关键字，需要( )次比较才能查找成功。（分数：2.00）A.1B.8C.2D.412.一棵二叉树的前序遍历结点顺序为 EACBDGF，中序遍历结点顺序为 ABCDEFG，则其后序遍历结点顺序为( )。（分数：2.00）A.EGFACDBB.EGACDFBC.BDCAFGED.BDCFAGE13.对以下关键字序列用快速排序方法排序速度最慢的是( )。（分数：2

5、00）A.15，21，5，12，9，20，31B.5，9，12，15，20，21，31)C.15，9，12，31，21，20，5D.21，20，31，12，15，5，9)14.用堆排序方法，在最坏情况下的时间复杂度为( )。（分数：2.00）A.O(n+1)B.O(n 2 )C.O(log 2 n)D.O(n log 2 n)15.给定如下一组关键字序列49，38，65，97，76，13，27，49，55，04，采用希尔排序，则第二趟排序后的结果为( )。（分数：2.00）A.13，04，49，38，27，49，55，65，97，76B.13，27，49，55，04，49，38，65，97，

6、76C.04，13，27，49，49，38，55，65，76，97D.04，13，27，38，49，49，55，65，76，9716.关于二叉树，下列说法不正确的是( )。（分数：2.00）A.在第 i 层上最多有 2 i-1 个结点B.深度为 k 的二叉树最多有 2 k -1 个结点C.相同层次的满二叉树结点数比完全二叉树结点多D.深度为 k 的满二叉树结点数一定为 2k-1 个17.元素 ABCDEF 按序进入队列，则队列的出队顺序为( )。（分数：2.00）A.FEDCBAB.ABCDEFC.DCBAEFD.ABFEDC18.在判断表达式中括号是否匹配的算法中，采用( )数据结构最佳。（

7、分数：2.00）A.线性表的顺序存储结构B.线性表的链式存储结构C.广义表D.栈19.若待排序序列已基本有序，要使它完全有序，从关键码的比较次数和移动次数考虑，应当采用的排序方法是( )。（分数：2.00）A.直接插入排序B.快速排序C.直接选择排序D.归并排序20.对一棵二叉树的中序遍历序列中，根结点的左边包括( )。（分数：2.00）A.左子树上的叶子结点B.右子树上的所有结点C.左子树上的所有结点D.右子树上的叶子结点21.线索二叉树是一种( )结构。（分数：2.00）A.逻辑B.存储C.线性D.物理22.下图所示是一棵二叉树，其后序遍历序列是( )。 （分数：2.00）A.DEBGFC

8、AB.ABCDEFGC.DEBFGCAD.DBEACGF23.如下图所示，下列说法正确的是( )。 （分数：2.00）A.此树不是满二叉树也不是完全二叉树B.中序遍历序列是 HIDBEACFGC.此树是完全二叉树，也是满二叉树D.以上说法均不正确24.栈结构通常采用的两种存储结构是( )。（分数：2.00）A.顺序存储结构和链表存储结构B.散列方式和索引方式C.后进先出结构和顺序存储结构D.线性存储结构和非线性存储结构数据结构与算法练习试卷 1 答案解析(总分：48.00，做题时间：90 分钟)一、选择题(总题数：24，分数：48.00)1.选择题（）下列各题 A、B、C、D 四个选项中，只有

9、一个选项是正确的，请将正确选项涂写在答题卡相应位置上。（分数：2.00）_解析：2.一棵具有 5 层的完全二叉树中，结点总数最少是( )。（分数：2.00）A.15B.5C.16 D.31解析：解析：具有 5 层的树结点最少的是完全二叉树，第 5 层只有一个结点，其他 4 层是由满二叉树构成。3.设 n、m 为一棵二叉树上的两个结点，在中序遍历时，若 n 在 m 的前面，则( )。（分数：2.00）A.n 为树的左子树上的结点，m 为右子树上的结点B.n 是 m 的祖先结点C.n 的层次比 m 层次高D.n 在 m 的左方 解析：4.对于深度为 n，结点数为 k，有 m 个叶子结点的满二叉树，

10、下列关系正确的是( )。（分数：2.00）A.k=m+nB.k=-2“-1 C.n+m=2kD.re=k-1解析：5.快速排序方法在( )条件下最不利于发挥其长处。（分数：2.00）A.待排序序列中含有多个相同关键字B.待排序序列数据基本有序C.待排序序列数据量很大 D.待排序序列元素个数为奇数解析：6.在每一趟排序时，都将待排序序列中最大关键字选出来，并将此关键字从待排序序列中删除，继续对剩余元素进行同样操作的排序方法称之为( )。（分数：2.00）A.快速排序B.堆排序C.起泡捧序 D.选择排序解析：7.设有 1000 个无序的元素，希望用最快的方式挑选出其中前 10 个最大元素，效率最高

11、的排序方法是( )。（分数：2.00）A.堆排序 B.快速排序C.基数排序D.起泡排序解析：8.设哈希表长 m=14，哈希函数 H(key)=key%ll，表中已经有 4 个结点： addr(13)=4； addr(28)=5 addr(51)=6； addr(77)=7 如果用线性探测再与散列法处理冲突，关键字为 49 的结点地址为( )。（分数：2.00）A.8 B.5C.9D.3解析：9.对于一个序列中的若干元素，若想得到某个元素之前的部分排序，最好采用什么排序方法? ( )（分数：2.00）A.快速排序B.堆排序 C.基数排序D.希尔排序解析：10.采用顺序查找法查找长度为 n 的线性

12、表时，每个元素的平均查找长度为( )，（分数：2.00）A.(n+1)/2 B.(n-1)/2C.n/2D.n解析：11.一个有序表2，4，7，12，23，45，62，76，77，89，93，95，100，若采用二分查找法查找值为 93的关键字，需要( )次比较才能查找成功。（分数：2.00）A.1B.8C.2D.4 解析：12.一棵二叉树的前序遍历结点顺序为 EACBDGF，中序遍历结点顺序为 ABCDEFG，则其后序遍历结点顺序为( )。（分数：2.00）A.EGFACDBB.EGACDFBC.BDCAFGE D.BDCFAGE解析：解析：由前序遍历序列得知 E 是根结点，由中序序列可知：

13、A、B、C、D 在左子树上，且是左子树的中序序列，A 是左子树上的根，C 是 A 的右子结点，B、D 分别是 C 的左右结点， F、G 在右子树上，且是右子树上的中序序列，G 是右子树上的根，F 是 G 的左子结点。由此描绘一下该二叉树，就可得到答案A。13.对以下关键字序列用快速排序方法排序速度最慢的是( )。（分数：2.00）A.15，21，5，12，9，20，31B.5，9，12，15，20，21，31) C.15，9，12，31，21，20，5D.21，20，31，12，15，5，9)解析：14.用堆排序方法，在最坏情况下的时间复杂度为( )。（分数：2.00）A.O(n+1)B.O(

14、n 2 )C.O(log 2 n)D.O(n log 2 n) 解析：15.给定如下一组关键字序列49，38，65，97，76，13，27，49，55，04，采用希尔排序，则第二趟排序后的结果为( )。（分数：2.00）A.13，04，49，38，27，49，55，65，97，76 B.13，27，49，55，04，49，38，65，97，76C.04，13，27，49，49，38，55，65，76，97D.04，13，27，38，49，49，55，65，76，97解析：16.关于二叉树，下列说法不正确的是( )。（分数：2.00）A.在第 i 层上最多有 2 i-1 个结点B.深度为 k 的

15、二叉树最多有 2 k -1 个结点C.相同层次的满二叉树结点数比完全二叉树结点多 D.深度为 k 的满二叉树结点数一定为 2k-1 个解析：17.元素 ABCDEF 按序进入队列，则队列的出队顺序为( )。（分数：2.00）A.FEDCBAB.ABCDEF C.DCBAEFD.ABFEDC解析：18.在判断表达式中括号是否匹配的算法中，采用( )数据结构最佳。（分数：2.00）A.线性表的顺序存储结构B.线性表的链式存储结构C.广义表D.栈 解析：19.若待排序序列已基本有序，要使它完全有序，从关键码的比较次数和移动次数考虑，应当采用的排序方法是( )。（分数：2.00）A.直接插入排序 B.

16、快速排序C.直接选择排序D.归并排序解析：20.对一棵二叉树的中序遍历序列中，根结点的左边包括( )。（分数：2.00）A.左子树上的叶子结点B.右子树上的所有结点C.左子树上的所有结点 D.右子树上的叶子结点解析：21.线索二叉树是一种( )结构。（分数：2.00）A.逻辑B.存储C.线性D.物理 解析：22.下图所示是一棵二叉树，其后序遍历序列是( )。 （分数：2.00）A.DEBGFCA B.ABCDEFGC.DEBFGCAD.DBEACGF解析：23.如下图所示，下列说法正确的是( )。 （分数：2.00）A.此树不是满二叉树也不是完全二叉树B.中序遍历序列是 HIDBEACFGC.此树是完全二叉树，也是满二叉树D.以上说法均不正确 解析：24.栈结构通常采用的两种存储结构是( )。（分数：2.00）A.顺序存储结构和链表存储结构 B.散列方式和索引方式C.后进先出结构和顺序存储结构D.线性存储结构和非线性存储结构解析：