【计算机类职业资格】数据结构与算法(一)及答案解析.doc

《【计算机类职业资格】数据结构与算法(一)及答案解析.doc》由会员分享，可在线阅读，更多相关《【计算机类职业资格】数据结构与算法(一)及答案解析.doc（9页珍藏版）》请在麦多课文档分享上搜索。

1、数据结构与算法(一)及答案解析(总分：78.00，做题时间：90 分钟)一、B选择题/B(总题数：28，分数：56.00)1.计算机算法指的是 _，它必须具备输入、输出，可执行性、确定性和有穷性。（分数：2.00）A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法2.设计一个“判别在表达式中左、右括号是否配对出现”的算法，采用 _ 数据结构最佳。（分数：2.00）A.线性表的顺序存储结构B.栈C.队列D.线性表的链式存储结构3.若对一棵二叉树进行中序遍历得到的结果是(B，D，A，G，H，E，C，F)，进行后序遍历的结果是DBHGEFCA，那么这棵二叉树进行前序遍历得到的结果是 _。

2、（分数：2.00）A.(A， B， D， C， E， G， H，B.(A， B， D， C， E， H， G，C.(D，B，A，C，E，G，H，D.无法确定4.一个队列的入列序号是 1，2，3，4，则队列的输出系列是 _。（分数：2.00）A.4，3，2，1B.1，2，3，4C.1，4，3，2D.3，2，4，15.对关键字序列(11，12，13，14，15)采用对半查找算法查找关键字 11，则关键字之间比较次数为 _。（分数：2.00）A.1B.2C.3D.46.如果以链表为栈的存储结构，则出栈操作是 _。（分数：2.00）A.必须判别栈是否为满B.必须判别栈是否为空C.判别栈元素的类型D.对

3、栈不作任何判别7.在算法设计基本方法中， _ 是从初始条件出发，逐次推出所需求的结果。（分数：2.00）A.递推B.递归C.列举法D.归纳法8.分析算法的目的是 _。（分数：2.00）A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档9.若完全二叉树共有 n 个结点，且从根结点开始，按层序(每层从左到右)用正整数 0，1，2，n-1，从小到大对结点编号，则对于编号为 k 的结点，错误的是 _。（分数：2.00）A.若 k0，则该结点的父结点编号为k/2(表示取整)B.若 2kn-1，则编号为 k 的结点无右子树，但可能有左子树C.若 2

4、k+1=n-1，则编号为 k 的结点的右子结点编号为 2k+1D.若 k=0，则该结点肯定没有父结点10.用数组 A0m-1存放循环队列的元素值，若其头尾指针分别为 front 和 rear，则循环队列中当前元素的个数为 _。（分数：2.00）A.(rear-front+rmod mB.(rear-front+m+1)mod mC.(rear-front+m-1)mod mD.(rear-front-m-1)mod m11.采用顺序查找方法查找长度为 n 的线性表时，每个元素的平均查找长度为 _。（分数：2.00）A.nB.n/2C.(n+1)/2D.(n-1)/212.设有 1000 个无序

5、的元素，希望用最快的速度挑选出其中前 10 个最大的元素，最好选用 _ 排序法。（分数：2.00）A.希尔排序B.冒泡排序C.堆排序D.快速排序13.链栈与顺序栈相比，有一个比较明显的优点是 _。（分数：2.00）A.插入操作更加方便B.通常不会出现栈满情况C.不会出现栈空的情况D.删除操作更加方便14.对线性表进行二分法检索。其前提条件是 _ 。（分数：2.00）A.线性表以顺序方式存储，并且按关键码值排好序B.线性表以顺序方式存储，并且按关键码的检索频率排好序C.线性表以链接方式存储，并且按关键码值排好序D.线性表以链接方式存储，并且按关键码的检索频率排好序15.下列关于数据结构的叙述中，

6、正确的是 _。（分数：2.00）A.实际应用中，队列的顺序存储结构一般采用循环队列的形式B.递推算法结构程序一般比递归算法结构程序更精练C.树是一种线性结构D.用一维数组存储二叉树，总是以先序遍历的顺序存储各结点16.完全二叉树中，若一个结点是叶结点，则它没有 _。（分数：2.00）A.左子结点B.右子结点C.左子结点和左子结点D.左子结点、右子结点和兄弟结点17.下面关于数据结构的叙述中，正确的是 _。（分数：2.00）A.顺序存储方式的优点是存储密度大，且插入、删除运算效率高B.链表中的每一个结点都包含恰好一个指针C.包含 n 个结点的二叉排序树的最大检索长度为 log2nD.将一棵树转换

7、为二叉树后，根结点没有右子树18.一组记录的排序码为(46，79，56，38，40，84)，则利用堆排序的方法建立的初始堆为 _。（分数：2.00）A.79，46，56，38，40，84B.84，79，56，38，40，46C.84，79，56，46，40，38D.84，56，79，40，46，3819.下述几种排序方法中， _ 是最简单的交换类排序方法。（分数：2.00）A.冒泡排序B.插入排序C.快速排序D.选择排序20.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 _。（分数：2.00）A.希尔排序B.冒泡排序C.插入排序D.选择排序21.二分法查找 _ 存储结构。（分

8、数：2.00）A.只适合于链式B.只适合于顺序C.既适合于顺序也适合于链式D.既不适合于顺序也不适合于链式22.对含有 n 个关键词的序列进行冒泡法排序，最少的比较次数是 _ 。（分数：2.00）A.nB.n-1C.n/2D.n-223.下面关于二叉树的叙述中正确的是 _。（分数：2.00）A.度为 2 的树称为二叉树B.二叉树的度肯定是 2C.二叉树中所有结点的度都是 2D.由 3 个结点可以构造出 5 种不同的二叉树24.对给定的整数序列(541，132，984，746，518，181，946，314，205，827)进行从小到大的排序时，采用快速排序(以中间元素 518 为基准)的第一趟

9、扫描结果是 _ 。（分数：2.00）A.(181，132，314，205，541，518，946，827，746，984)B.(541，132，827，746，518，181，946，314，205，984)C.(205，132，314，181，518，746，946，984，541，827)D.(541，132，984，746，827，181，946，314，205，518)25.设栈 S 和队列 Q 的初始状态为空，元素 e1，e 2，e 3，e 4，e 5，e 6依次通过栈 S，一个元素出栈后即进入栈队列 Q，若 6 个元素出队的顺序是 e2，e 4，e 3，e 6，e 5，e 1，则栈

10、 S 的容量至少应该是 _。（分数：2.00）A.6B.4C.3D.226.按照二叉树的定义，深度为 5 的二叉树至多有 _ 个结点。（分数：2.00）A.16B.32C.10D.3127.采用二分查找方法查找长度为 n 的线性表时，每个元素的平均查找长度为 _。（分数：2.00）A.O(log2B.O(C.O(nlog2D.O(n2)28.以下叙述正确的是 _。（分数：2.00）A.线性表的线性存储结构优于链表存储结构B.在树形结构中，树根结点没有前驱结点C.栈的操作方式是先进先出D.队列的操作方式是先进后出二、B填空题/B(总题数：11，分数：22.00)29.一个算法通常由对数据对象的运

11、算和操作以及算法的U 【1】 /U两种基本要素组成。（分数：2.00）填空项 1:_30.算法复杂度包括时间复杂度和空间复杂度。对空间复杂度一般可以用平均态和最坏情况复杂性来衡量：而对于空间复杂度，一般指执行该算法所需要的U 【2】 /U。（分数：2.00）填空项 1:_31.在数据结构的图形结构中，每个结点的前驱结点数和后续结点数可以U 【3】 /U个。（分数：2.00）填空项 1:_32.在树中，一个结点的直接子结点的个数称为该结点的U 【4】 /U。（分数：2.00）填空项 1:_33.设只包含根结点的二叉树的高度为 0，则高度为 k 的二叉树的最小结点数为U 【5】 /U。（分数：2.

12、00）填空项 1:_34.已知一棵二叉树前序序列和中序序列分别为 A，B，D，E，G，C，F，H 和 D，B， G，E，A，C，H，F，则该二叉树的后序序列为U 【6】 /U。（分数：2.00）填空项 1:_35.从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较，将其放入已排序序列正确位置上的方法，称为U 【7】 /U。（分数：2.00）填空项 1:_36.从未排序序列中挑选元素，将其依次放入已排序序列(初始时为空)的一端，这种排序方法称为U 【8】 /U。（分数：2.00）填空项 1:_37.在表为 n 的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为U 【

13、9】 /U。（分数：2.00）填空项 1:_38.在插入排序、希尔排序、选择排序、堆排序和快速排序中，平均比较次数最少的排序是U 【10】 /U。（分数：2.00）填空项 1:_39.在堆排序和快速排序中，若只从最坏情况下排序最快并且要节省内存考虑，则应选择U 【11】 /U方法。（分数：2.00）填空项 1:_数据结构与算法(一)答案解析(总分：78.00，做题时间：90 分钟)一、B选择题/B(总题数：28，分数：56.00)1.计算机算法指的是 _，它必须具备输入、输出，可执行性、确定性和有穷性。（分数：2.00）A.计算方法B.排序方法C.解决问题的有限运算序列 D.调度方法解析：2.

14、设计一个“判别在表达式中左、右括号是否配对出现”的算法，采用 _ 数据结构最佳。（分数：2.00）A.线性表的顺序存储结构B.栈 C.队列D.线性表的链式存储结构解析：3.若对一棵二叉树进行中序遍历得到的结果是(B，D，A，G，H，E，C，F)，进行后序遍历的结果是DBHGEFCA，那么这棵二叉树进行前序遍历得到的结果是 _。（分数：2.00）A.(A， B， D， C， E， G， H， B.(A， B， D， C， E， H， G，C.(D，B，A，C，E，G，H，D.无法确定解析：4.一个队列的入列序号是 1，2，3，4，则队列的输出系列是 _。（分数：2.00）A.4，3，2，1B.1

15、，2，3，4 C.1，4，3，2D.3，2，4，1解析：5.对关键字序列(11，12，13，14，15)采用对半查找算法查找关键字 11，则关键字之间比较次数为 _。（分数：2.00）A.1B.2 C.3D.4解析：6.如果以链表为栈的存储结构，则出栈操作是 _。（分数：2.00）A.必须判别栈是否为满B.必须判别栈是否为空 C.判别栈元素的类型D.对栈不作任何判别解析：7.在算法设计基本方法中， _ 是从初始条件出发，逐次推出所需求的结果。（分数：2.00）A.递推 B.递归C.列举法D.归纳法解析：8.分析算法的目的是 _。（分数：2.00）A.找出数据结构的合理性B.研究算法中的输入和输

16、出的关系C.分析算法的效率以求改进 D.分析算法的易懂性和文档解析：9.若完全二叉树共有 n 个结点，且从根结点开始，按层序(每层从左到右)用正整数 0，1，2，n-1，从小到大对结点编号，则对于编号为 k 的结点，错误的是 _。（分数：2.00）A.若 k0，则该结点的父结点编号为k/2(表示取整)B.若 2kn-1，则编号为 k 的结点无右子树，但可能有左子树 C.若 2k+1=n-1，则编号为 k 的结点的右子结点编号为 2k+1D.若 k=0，则该结点肯定没有父结点解析：10.用数组 A0m-1存放循环队列的元素值，若其头尾指针分别为 front 和 rear，则循环队列中当前元素的个

17、数为 _。（分数：2.00）A.(rear-front+rmod m B.(rear-front+m+1)mod mC.(rear-front+m-1)mod mD.(rear-front-m-1)mod m解析：11.采用顺序查找方法查找长度为 n 的线性表时，每个元素的平均查找长度为 _。（分数：2.00）A.nB.n/2C.(n+1)/2 D.(n-1)/2解析：12.设有 1000 个无序的元素，希望用最快的速度挑选出其中前 10 个最大的元素，最好选用 _ 排序法。（分数：2.00）A.希尔排序B.冒泡排序C.堆排序 D.快速排序解析：13.链栈与顺序栈相比，有一个比较明显的优点是

18、_。（分数：2.00）A.插入操作更加方便B.通常不会出现栈满情况 C.不会出现栈空的情况D.删除操作更加方便解析：14.对线性表进行二分法检索。其前提条件是 _ 。（分数：2.00）A.线性表以顺序方式存储，并且按关键码值排好序 B.线性表以顺序方式存储，并且按关键码的检索频率排好序C.线性表以链接方式存储，并且按关键码值排好序D.线性表以链接方式存储，并且按关键码的检索频率排好序解析：15.下列关于数据结构的叙述中，正确的是 _。（分数：2.00）A.实际应用中，队列的顺序存储结构一般采用循环队列的形式 B.递推算法结构程序一般比递归算法结构程序更精练C.树是一种线性结构D.用一维数组存储

19、二叉树，总是以先序遍历的顺序存储各结点解析：16.完全二叉树中，若一个结点是叶结点，则它没有 _。（分数：2.00）A.左子结点B.右子结点C.左子结点和左子结点 D.左子结点、右子结点和兄弟结点解析：17.下面关于数据结构的叙述中，正确的是 _。（分数：2.00）A.顺序存储方式的优点是存储密度大，且插入、删除运算效率高B.链表中的每一个结点都包含恰好一个指针C.包含 n 个结点的二叉排序树的最大检索长度为 log2nD.将一棵树转换为二叉树后，根结点没有右子树 解析：18.一组记录的排序码为(46，79，56，38，40，84)，则利用堆排序的方法建立的初始堆为 _。（分数：2.00）A.

20、79，46，56，38，40，84B.84，79，56，38，40，46 C.84，79，56，46，40，38D.84，56，79，40，46，38解析：19.下述几种排序方法中， _ 是最简单的交换类排序方法。（分数：2.00）A.冒泡排序 B.插入排序C.快速排序D.选择排序解析：20.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 _。（分数：2.00）A.希尔排序B.冒泡排序C.插入排序D.选择排序 解析：21.二分法查找 _ 存储结构。（分数：2.00）A.只适合于链式B.只适合于顺序 C.既适合于顺序也适合于链式D.既不适合于顺序也不适合于链式解析：22.对含有

21、n 个关键词的序列进行冒泡法排序，最少的比较次数是 _ 。（分数：2.00）A.nB.n-1 C.n/2D.n-2解析：23.下面关于二叉树的叙述中正确的是 _。（分数：2.00）A.度为 2 的树称为二叉树B.二叉树的度肯定是 2C.二叉树中所有结点的度都是 2D.由 3 个结点可以构造出 5 种不同的二叉树 解析：24.对给定的整数序列(541，132，984，746，518，181，946，314，205，827)进行从小到大的排序时，采用快速排序(以中间元素 518 为基准)的第一趟扫描结果是 _ 。（分数：2.00）A.(181，132，314，205，541，518，946，827

22、，746，984)B.(541，132，827，746，518，181，946，314，205，984)C.(205，132，314，181，518，746，946，984，541，827) D.(541，132，984，746，827，181，946，314，205，518)解析：25.设栈 S 和队列 Q 的初始状态为空，元素 e1，e 2，e 3，e 4，e 5，e 6依次通过栈 S，一个元素出栈后即进入栈队列 Q，若 6 个元素出队的顺序是 e2，e 4，e 3，e 6，e 5，e 1，则栈 S 的容量至少应该是 _。（分数：2.00）A.6B.4C.3 D.2解析：26.按照二叉树的

23、定义，深度为 5 的二叉树至多有 _ 个结点。（分数：2.00）A.16B.32C.10D.31 解析：27.采用二分查找方法查找长度为 n 的线性表时，每个元素的平均查找长度为 _。（分数：2.00）A.O(log2 B.O(C.O(nlog2D.O(n2)解析：28.以下叙述正确的是 _。（分数：2.00）A.线性表的线性存储结构优于链表存储结构B.在树形结构中，树根结点没有前驱结点 C.栈的操作方式是先进先出D.队列的操作方式是先进后出解析：二、B填空题/B(总题数：11，分数：22.00)29.一个算法通常由对数据对象的运算和操作以及算法的U 【1】 /U两种基本要素组成。（分数：2.

24、00）填空项 1:_ （正确答案：控制结构）解析：30.算法复杂度包括时间复杂度和空间复杂度。对空间复杂度一般可以用平均态和最坏情况复杂性来衡量：而对于空间复杂度，一般指执行该算法所需要的U 【2】 /U。（分数：2.00）填空项 1:_ （正确答案：内存空间）解析：31.在数据结构的图形结构中，每个结点的前驱结点数和后续结点数可以U 【3】 /U个。（分数：2.00）填空项 1:_ （正确答案：任意多）解析：32.在树中，一个结点的直接子结点的个数称为该结点的U 【4】 /U。（分数：2.00）填空项 1:_ （正确答案：一次数/度）解析：33.设只包含根结点的二叉树的高度为 0，则高度为

25、k 的二叉树的最小结点数为U 【5】 /U。（分数：2.00）填空项 1:_ （正确答案：k+1）解析：34.已知一棵二叉树前序序列和中序序列分别为 A，B，D，E，G，C，F，H 和 D，B， G，E，A，C，H，F，则该二叉树的后序序列为U 【6】 /U。（分数：2.00）填空项 1:_ （正确答案：D，G，E，B，H，P，C，A）解析：35.从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较，将其放入已排序序列正确位置上的方法，称为U 【7】 /U。（分数：2.00）填空项 1:_ （正确答案：希尔排序）解析：36.从未排序序列中挑选元素，将其依次放入已排序序列(初始时为空)的一端，这种排序方法称为U 【8】 /U。（分数：2.00）填空项 1:_ （正确答案：选择排序）解析：37.在表为 n 的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为U 【9】 /U。（分数：2.00）填空项 1:_ （正确答案：n+1）解析：38.在插入排序、希尔排序、选择排序、堆排序和快速排序中，平均比较次数最少的排序是U 【10】 /U。（分数：2.00）填空项 1:_ （正确答案：快速排序）解析：39.在堆排序和快速排序中，若只从最坏情况下排序最快并且要节省内存考虑，则应选择U 【11】 /U方法。（分数：2.00）填空项 1:_ （正确答案：堆排序）解析：