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

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

1、数据结构与算法(四)及答案解析(总分：64.00，做题时间：90 分钟)一、选择题(总题数：22，分数：44.00)1.栈底至栈顶依次存放元素 A、B、C、D，在第 5 个元素 E 入栈前，栈中元素可以出栈，则出栈序列可能是( )。（分数：2.00）A.ABCEDB.DBCEAC.CDABED.DCBEA2.已知数据表 A 中每个元素距其最终位置都不远，为节省时间，应采用的算法是( )。（分数：2.00）A.堆排序B.直接插入排序C.快速排序D.直接选择排序3.下列关于栈的叙述中正确的是( )。（分数：2.00）A.在栈中只能插入数据B.在栈中只能删除数据C.栈是先进先出的线性表D.栈是先进后

2、出的线性表4.在计算机中，算法是指( )。（分数：2.00）A.查询方法B.加工方法C.解题方案准确而完整的描述D.排序方法5.下列描述中，不是线性表顺序存储结构特征的是( )。（分数：2.00）A.不便于插入和删除B.需要连续的存储空间C.可随机访问D.需另开辟空间来保存元素之间的关系6.设有下列二叉树：（分数：2.00）A.B.C.D.7.在深度为 5 的满二叉树中，叶子结点的个数为( )。（分数：2.00）A.32B.31C.16D.158.下列叙述中正确的是( )。（分数：2.00）A.线性表是线性结构B.栈与队列是非线性结构C.线性链表是非线性结构D.二叉树是线性结构9.在单链表中，

3、增加头结点的目的是( )。（分数：2.00）A.方便运算的实现B.使单链表至少有一个结点C.标识表结点中首结点的位置D.说明单链表是线性表的链式存储实现10.已知二叉树后序遍历序列是 dabec，中序遍历序列是 debac，它的前序遍历序列是( )。（分数：2.00）A.cedbaB.acbedC.decabD.deabc11.最简单的交换排序方法是( )。（分数：2.00）A.快速排序B.选择排序C.堆排序D.冒泡排序12.设一棵完全二叉树共有 699 个结点，则在该二叉树中的叶子结点数为( )个。（分数：2.00）A.349B.350C.255D.35113.用链表表示线性表的优点是( )

4、。（分数：2.00）A.便于插入和删除操作B.数据元素的物理顺序与逻辑顺序相同C.花费的存储空间比顺序存储少D.便于随机存取14.下列叙述中正确的是( )。（分数：2.00）A.一个算法的空间复杂度大，则其时间复杂度必定大B.一个算法的空间复杂度大，则其时间复杂度必定小C.一个算法的时间复杂度大，则其空间复杂度必定小D.上述 3 种说法都不对15.算法的时间复杂度是指( )。（分数：2.00）A.执行算法程序所需要的时间B.算法程序的长度C.算法执行过程中所需要的基本运算次数D.算法程序中的指令条数16.在数据结构中，与所使用计算机无关的是数据的( )。（分数：2.00）A.存储结构B.物理结

5、构C.逻辑结构D.物理和存储结构17.在下列选项中，哪个不是一个算法一般应该具有的基本特征?( )（分数：2.00）A.确定性B.可行性C.无穷性D.拥有足够的情报18.希尔排序法属于哪一种类型的排序法( )。（分数：2.00）A.交换类排序法B.插入类排序法C.选择类排序法D.建堆排序法19.线性表的顺序存储结构和线性表的链式存储结构分别是( )。（分数：2.00）A.顺序存取的存储结构、顺序存取的存储结构B.随机存取的存储结构、顺序存取的存储结构C.随机存取的存储结构、随机存取的存储结构D.任意存取的存储结构、任意存取的存储结构20.在下列几种排序方法中，要求内存量最大的是( )。（分数：

6、2.00）A.插入排序B.选择排序C.快速排序D.归并排序21.下列关于队列的叙述中正确的是( )。（分数：2.00）A.在队列中只能插入数据B.在队列中只能删除数据C.队列是先进先出的线性表D.队列是先进后出的线性表22.在一棵二叉树上第 5 层的结点数最多有( )个。（分数：2.00）A.8B.16C.32D.15二、填空题(总题数：10，分数：20.00)23.队列是限定在表的一端进行插入和在另一端进行删除操作的线性表。允许插入的一端称作 1。（分数：2.00）填空项 1:_24.在先左后右的原则下，根据访问根结点的次序，二又树的遍历可以分为 3 种：前序遍历、 1 遍历和后序遍历。（分

7、数：2.00）填空项 1:_25.设一棵完全二叉树共有 500 个结点，则在该二叉树中有 1 个叶子结点。（分数：2.00）填空项 1:_26.在最坏情况下，冒泡排序的时间复杂度为 1。（分数：2.00）填空项 1:_27.某二叉树中度为 2 的结点有 18 个，则该二叉树中有 1 个叶子结点。（分数：2.00）填空项 1:_28.栈的基本运算有 3 种：入栈、退栈和 1。（分数：2.00）填空项 1:_29.实现算法所需的存储单元多少和算法的工作量大小分别称为算法的 1。（分数：2.00）填空项 1:_30.数据结构包括数据的逻辑结构、数据的 1，以及对数据的操作运算。（分数：2.00）填空

8、项 1:_31.算法的基本特征是可行性、确定性、 1 和拥有足够的情报。（分数：2.00）填空项 1:_32.在最坏情况下，堆排序需要比较的次数为 1。（分数：2.00）填空项 1:_数据结构与算法(四)答案解析(总分：64.00，做题时间：90 分钟)一、选择题(总题数：22，分数：44.00)1.栈底至栈顶依次存放元素 A、B、C、D，在第 5 个元素 E 入栈前，栈中元素可以出栈，则出栈序列可能是( )。（分数：2.00）A.ABCEDB.DBCEAC.CDABED.DCBEA 解析：2.已知数据表 A 中每个元素距其最终位置都不远，为节省时间，应采用的算法是( )。（分数：2.00）A

9、.堆排序B.直接插入排序 C.快速排序D.直接选择排序解析：3.下列关于栈的叙述中正确的是( )。（分数：2.00）A.在栈中只能插入数据B.在栈中只能删除数据C.栈是先进先出的线性表D.栈是先进后出的线性表 解析：4.在计算机中，算法是指( )。（分数：2.00）A.查询方法B.加工方法C.解题方案准确而完整的描述 D.排序方法解析：5.下列描述中，不是线性表顺序存储结构特征的是( )。（分数：2.00）A.不便于插入和删除B.需要连续的存储空间C.可随机访问D.需另开辟空间来保存元素之间的关系 解析：6.设有下列二叉树：（分数：2.00）A.B. C.D.解析：7.在深度为 5 的满二叉树

10、中，叶子结点的个数为( )。（分数：2.00）A.32B.31C.16 D.15解析：8.下列叙述中正确的是( )。（分数：2.00）A.线性表是线性结构 B.栈与队列是非线性结构C.线性链表是非线性结构D.二叉树是线性结构解析：9.在单链表中，增加头结点的目的是( )。（分数：2.00）A.方便运算的实现 B.使单链表至少有一个结点C.标识表结点中首结点的位置D.说明单链表是线性表的链式存储实现解析：10.已知二叉树后序遍历序列是 dabec，中序遍历序列是 debac，它的前序遍历序列是( )。（分数：2.00）A.cedba B.acbedC.decabD.deabc解析：11.最简单的

11、交换排序方法是( )。（分数：2.00）A.快速排序B.选择排序C.堆排序D.冒泡排序 解析：12.设一棵完全二叉树共有 699 个结点，则在该二叉树中的叶子结点数为( )个。（分数：2.00）A.349B.350 C.255D.351解析：13.用链表表示线性表的优点是( )。（分数：2.00）A.便于插入和删除操作 B.数据元素的物理顺序与逻辑顺序相同C.花费的存储空间比顺序存储少D.便于随机存取解析：14.下列叙述中正确的是( )。（分数：2.00）A.一个算法的空间复杂度大，则其时间复杂度必定大B.一个算法的空间复杂度大，则其时间复杂度必定小C.一个算法的时间复杂度大，则其空间复杂度必

12、定小D.上述 3 种说法都不对 解析：15.算法的时间复杂度是指( )。（分数：2.00）A.执行算法程序所需要的时间B.算法程序的长度C.算法执行过程中所需要的基本运算次数 D.算法程序中的指令条数解析：16.在数据结构中，与所使用计算机无关的是数据的( )。（分数：2.00）A.存储结构B.物理结构C.逻辑结构 D.物理和存储结构解析：17.在下列选项中，哪个不是一个算法一般应该具有的基本特征?( )（分数：2.00）A.确定性B.可行性C.无穷性 D.拥有足够的情报解析：18.希尔排序法属于哪一种类型的排序法( )。（分数：2.00）A.交换类排序法B.插入类排序法 C.选择类排序法D.

13、建堆排序法解析：19.线性表的顺序存储结构和线性表的链式存储结构分别是( )。（分数：2.00）A.顺序存取的存储结构、顺序存取的存储结构B.随机存取的存储结构、顺序存取的存储结构 C.随机存取的存储结构、随机存取的存储结构D.任意存取的存储结构、任意存取的存储结构解析：20.在下列几种排序方法中，要求内存量最大的是( )。（分数：2.00）A.插入排序B.选择排序C.快速排序D.归并排序 解析：21.下列关于队列的叙述中正确的是( )。（分数：2.00）A.在队列中只能插入数据B.在队列中只能删除数据C.队列是先进先出的线性表 D.队列是先进后出的线性表解析：22.在一棵二叉树上第 5 层的

14、结点数最多有( )个。（分数：2.00）A.8B.16 C.32D.15解析：二、填空题(总题数：10，分数：20.00)23.队列是限定在表的一端进行插入和在另一端进行删除操作的线性表。允许插入的一端称作 1。（分数：2.00）填空项 1:_ （正确答案：队尾）解析：24.在先左后右的原则下，根据访问根结点的次序，二又树的遍历可以分为 3 种：前序遍历、 1 遍历和后序遍历。（分数：2.00）填空项 1:_ （正确答案：中序）解析：25.设一棵完全二叉树共有 500 个结点，则在该二叉树中有 1 个叶子结点。（分数：2.00）填空项 1:_ （正确答案：250）解析：26.在最坏情况下，冒泡

15、排序的时间复杂度为 1。（分数：2.00）填空项 1:_ （正确答案：n(n-1)/2#n *(n-1)/2#O(n(n-1)/2)#0(n*(n-1)/2)）解析：27.某二叉树中度为 2 的结点有 18 个，则该二叉树中有 1 个叶子结点。（分数：2.00）填空项 1:_ （正确答案：19）解析：28.栈的基本运算有 3 种：入栈、退栈和 1。（分数：2.00）填空项 1:_ （正确答案：读栈顶元素#读栈顶的元素#读出栈顶元素）解析：29.实现算法所需的存储单元多少和算法的工作量大小分别称为算法的 1。（分数：2.00）填空项 1:_ （正确答案：空间复杂度和时间复杂度）解析：30.数据结构包括数据的逻辑结构、数据的 1，以及对数据的操作运算。（分数：2.00）填空项 1:_ （正确答案：存储结构）解析：31.算法的基本特征是可行性、确定性、 1 和拥有足够的情报。（分数：2.00）填空项 1:_ （正确答案：有穷性）解析：32.在最坏情况下，堆排序需要比较的次数为 1。（分数：2.00）填空项 1:_ （正确答案：O(nlog 2n)）解析：