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

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

1、数据结构与算法及答案解析(总分：90.00，做题时间：90 分钟)一、B选择题/B(总题数：31，分数：62.00)1.对于长度为 8的顺序存储结构的有序表，若采用二分查找法查找，在等概率的情况下，平均查找长度为_的值除以 8。（分数：2.00）A.17B.19C.21D.202.把算法工作量大小和实现算法所需存储单元多少分别称为算法的_和空间复杂度（分数：2.00）A.可实现性B.时间复杂度C.困难度D.计算有效性3.在一个顺序存储的循环队列中，队头指针指向队头元素的_。（分数：2.00）A.当前位置B.任意位置C.前一个位置D.后一个位置4.在循环双链表的 p结点之后插入 s结点的操作是_

2、。（分数：2.00）A.pnext=s； pnextprior=s； Sprior=p； Snext=pnext；B.snext=p； snext=pnext； pnext=s； pnextprior=s；C.pnext=s； sprior=p； pnextprior=s； snext=pnext；D.sprior=p； snext=pnext； pnextprior=s； pnext=S；5.数据的_包括集合结构、线性结构、树型结构和图状结构四种基本类型。（分数：2.00）A.算法描述B.基本运算C.逻辑结构D.存储结构6.在待排序的元素序列基本有序的前提下，效率最高的排序方法是_。（分数：

3、2.00）A.冒泡排序B.选择排序C.快速排序D.归并排序7.假设一个栈的输入序列为 A，B，C，D，E，则下列序列中不可能是栈的输出序列的是_。（分数：2.00）A.B，C，D，A， EB.E， D，A，C，BC.B，C，A，D， ED.A， E， D， C， B8.计算机算法指的是_。（分数：2.00）A.计算方法B.调度方法C.排序方法D.解决某一问题的有限运算序列9.一些重要的程序语言(如 C语言和 Pascal语言)允许过程的递归调用，而实现递归调用中的存储分配通常用_。（分数：2.00）A.栈B.堆C.数组D.链表10.单链表要求内存中可用存储单元的地址_。（分数：2.00）A.必

4、须是连续的B.一定是不连续的C.部分地址必须是连续的D.可以是连续的，也可以是不连续的11.树是结点的集合，它的根结点数目是_。（分数：2.00）A.有且只有 1B.1或多于 lC.0或 1D.至少 212.以下四种排序方法中，需要附加的内存空间最大的是_。（分数：2.00）A.插入排序B.选择排序C.快速排序D.归并排序13.数据结构中，与所使用的计算机无关的是数据的_。（分数：2.00）A.存储结构B.物理结构C.逻辑结构D.物理和存储结构14.若对 n个元素进行直接插入排序，则进行第 i趟排序过程前，有序表中的元素个数为 _。（分数：2.00）A.1B.i-1C.iD.i+115.若某二

5、叉树的前序遍历访问顺序是 ABDGCEFH，中序遍历访问顺序是 DGBAECFH，则其后序遍历的结点访问顺序是_。（分数：2.00）A.BDGCEFHAB.GDBECFHAC.BDGAECHFD.GDBEHFCA16.采用链接方式存储线性表的优点是_。（分数：2.00）A.便于随机存取B.花费的存储空间较顺序存储方式少C.便于插入和删除操作D.数据元素的物理顺序和逻辑顺序相同17.在计算机中，算法是指_。（分数：2.00）A.加工方法B.解题方案准确而完整的描述C.排序方法D.查询方法18.若某链表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用_存储方式最节省时间。（分

6、数：2.00）A.单链表B.双链表C.单循环链表D.带头结点的双循环链表19.数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及_。（分数：2.00）A.数据的存储结构B.计算方法C.数据映像D.逻辑存储20.如果进栈序列为 e1，e2，e3，e4，则可能的出栈序列是_。（分数：2.00）A.e3，e1，e4，e2B.e2，e4，e3，e1C.e3，e4，e1，e2D.任意顺序21.串的长度是_。（分数：2.00）A.串中不同字符的个数B.串中不同字母的个数C.串中所含字符的个数且字符个数大于零D.串中所含字符的个数22.线性表进行二分法查找，其前提条件是_。

7、（分数：2.00）A.线性表以顺序方式存储，并且按关键码值排好序B.线性表以链式方式存储，并且按关键码值排好序C.线性表以顺序方式存储，并且按关键码的检索频率排好序D.线性表以链式方式存储，并 a按关键码的检索频率排好序23.算法的时间复杂度是指_。（分数：2.00）A.执行算法程序所需要的时间B.算法程序的长度C.算法执行过程中所需要的基本运算次数D.算法程序中的指令条数24.对长度为 4的顺序表进行查找，若第一个元素的概率为 1/8，第二个元素的概率为 1/4，第三个元素的概率 3/8，第四个元素的概率为 1/4，则查找任一元素的平均查找长度为_。（分数：2.00）A.11/8B.7/4C

8、.9/4D.11/425.在深度为 5的满二叉树中，叶子结点的个数为_。（分数：2.00）A.32B.31C.16D.1526.数据的存储结构包括顺序、_、索引和散列四种基本类型。（分数：2.00）A.向量B.数组C.集合D.链式27.在顺序栈中进行退栈操作时，_。（分数：2.00）A.谁先谁后都可以B.先移动栈顶指针，后取出元素C.不分先后，同时进行D.先取出元素，后移动栈顶指针28.已知一棵二叉树前序遍历和中序遍历分别为 ABDEGCFH和 DBGEACHF，则该二叉树的后序遍历为_。（分数：2.00）A.GEDHFBCAB.DGEBHFCAC.ABCDEFGHD.ACBFEDHG29.树

9、最适合于表示_。（分数：2.00）A.有序数据元素B.无序数据元素C.元素之间无联系的数据D.元素之间具有分支层次关系的数据30.在下列栈的基本运算中，不是加工型运算的是_。（分数：2.00）A.初始化B.进栈C.退栈D.判栈空31.实现递归调用属于_的应用。（分数：2.00）A.栈B.数组C.队列D.二叉树二、B填空题/B(总题数：14，分数：28.00)32.数据元素之间 1 的整体称为逻辑结构。（分数：2.00）填空项 1:_33.一个算法的时间复杂性是 1 的函数。（分数：2.00）填空项 1:_34.在单链表中，NULL 称为 1，它不指向任何结点，只起 2 作用。（分数：2.00）

10、填空项 1:_填空项 1:_35.对长度为 n顺序表的删除算法，它最坏情况的时间复杂性及其量级分别是 1 和 2，平均时间复杂性及其量级分别为 3 和 4。（分数：2.00）填空项 1:_36.存储结点中数据域占用的存储量与整个结点占用的存储量之比称为 1。（分数：2.00）填空项 1:_37.一般地，二叉树可以有 1 种基本形态。（分数：2.00）填空项 1:_38.按照排序过程涉及的存储设备的不同，排序可分为 1 和 2。（分数：2.00）填空项 1:_填空项 1:_39.评价排序算法优劣的主要标准是 1 和 2。（分数：2.00）填空项 1:_填空项 1:_40.稳定的排序算法有 1、

11、2 和 3。（分数：2.00）填空项 1:_41.第一趟排序后序列中关键字最大的记录交换到最后的排序方法是 1。（分数：2.00）填空项 1:_42.数据结构分为逻辑结构与存储结构，线性链表属于 1。（分数：2.00）填空项 1:_43.在树形结构中，树根结点没有 1。（分数：2.00）填空项 1:_44.数据的逻辑结构有线性结构和 1 两大类。（分数：2.00）填空项 1:_45.顺序存储方法是把逻辑上相邻的结点存储在物理位置 1 的存储单元中。（分数：2.00）填空项 1:_数据结构与算法答案解析(总分：90.00，做题时间：90 分钟)一、B选择题/B(总题数：31，分数：62.00)1

12、.对于长度为 8的顺序存储结构的有序表，若采用二分查找法查找，在等概率的情况下，平均查找长度为_的值除以 8。（分数：2.00）A.17B.19 C.21D.20解析：2.把算法工作量大小和实现算法所需存储单元多少分别称为算法的_和空间复杂度（分数：2.00）A.可实现性B.时间复杂度 C.困难度D.计算有效性解析：3.在一个顺序存储的循环队列中，队头指针指向队头元素的_。（分数：2.00）A.当前位置B.任意位置C.前一个位置 D.后一个位置解析：4.在循环双链表的 p结点之后插入 s结点的操作是_。（分数：2.00）A.pnext=s； pnextprior=s； Sprior=p； Sn

13、ext=pnext；B.snext=p； snext=pnext； pnext=s； pnextprior=s；C.pnext=s； sprior=p； pnextprior=s； snext=pnext；D.sprior=p； snext=pnext； pnextprior=s； pnext=S； 解析：5.数据的_包括集合结构、线性结构、树型结构和图状结构四种基本类型。（分数：2.00）A.算法描述B.基本运算C.逻辑结构 D.存储结构解析：6.在待排序的元素序列基本有序的前提下，效率最高的排序方法是_。（分数：2.00）A.冒泡排序 B.选择排序C.快速排序D.归并排序解析：7.假设一个

14、栈的输入序列为 A，B，C，D，E，则下列序列中不可能是栈的输出序列的是_。（分数：2.00）A.B，C，D，A， EB.E， D，A，C，B C.B，C，A，D， ED.A， E， D， C， B解析：8.计算机算法指的是_。（分数：2.00）A.计算方法B.调度方法C.排序方法D.解决某一问题的有限运算序列 解析：9.一些重要的程序语言(如 C语言和 Pascal语言)允许过程的递归调用，而实现递归调用中的存储分配通常用_。（分数：2.00）A.栈 B.堆C.数组D.链表解析：10.单链表要求内存中可用存储单元的地址_。（分数：2.00）A.必须是连续的B.一定是不连续的C.部分地址必须是

15、连续的D.可以是连续的，也可以是不连续的 解析：11.树是结点的集合，它的根结点数目是_。（分数：2.00）A.有且只有 1 B.1或多于 lC.0或 1D.至少 2解析：12.以下四种排序方法中，需要附加的内存空间最大的是_。（分数：2.00）A.插入排序B.选择排序C.快速排序D.归并排序 解析：13.数据结构中，与所使用的计算机无关的是数据的_。（分数：2.00）A.存储结构B.物理结构C.逻辑结构 D.物理和存储结构解析：14.若对 n个元素进行直接插入排序，则进行第 i趟排序过程前，有序表中的元素个数为 _。（分数：2.00）A.1B.i-1C.i D.i+1解析：15.若某二叉树的

16、前序遍历访问顺序是 ABDGCEFH，中序遍历访问顺序是 DGBAECFH，则其后序遍历的结点访问顺序是_。（分数：2.00）A.BDGCEFHAB.GDBECFHAC.BDGAECHFD.GDBEHFCA 解析：16.采用链接方式存储线性表的优点是_。（分数：2.00）A.便于随机存取B.花费的存储空间较顺序存储方式少C.便于插入和删除操作 D.数据元素的物理顺序和逻辑顺序相同解析：17.在计算机中，算法是指_。（分数：2.00）A.加工方法B.解题方案准确而完整的描述 C.排序方法D.查询方法解析：18.若某链表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用_存储方

17、式最节省时间。（分数：2.00）A.单链表B.双链表C.单循环链表D.带头结点的双循环链表 解析：19.数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及_。（分数：2.00）A.数据的存储结构 B.计算方法C.数据映像D.逻辑存储解析：20.如果进栈序列为 e1，e2，e3，e4，则可能的出栈序列是_。（分数：2.00）A.e3，e1，e4，e2B.e2，e4，e3，e1 C.e3，e4，e1，e2D.任意顺序解析：21.串的长度是_。（分数：2.00）A.串中不同字符的个数B.串中不同字母的个数C.串中所含字符的个数且字符个数大于零D.串中所含字符的个数

18、解析：22.线性表进行二分法查找，其前提条件是_。（分数：2.00）A.线性表以顺序方式存储，并且按关键码值排好序 B.线性表以链式方式存储，并且按关键码值排好序C.线性表以顺序方式存储，并且按关键码的检索频率排好序D.线性表以链式方式存储，并 a按关键码的检索频率排好序解析：23.算法的时间复杂度是指_。（分数：2.00）A.执行算法程序所需要的时间B.算法程序的长度C.算法执行过程中所需要的基本运算次数 D.算法程序中的指令条数解析：24.对长度为 4的顺序表进行查找，若第一个元素的概率为 1/8，第二个元素的概率为 1/4，第三个元素的概率 3/8，第四个元素的概率为 1/4，则查找任一

19、元素的平均查找长度为_。（分数：2.00）A.11/8B.7/4C.9/4 D.11/4解析：25.在深度为 5的满二叉树中，叶子结点的个数为_。（分数：2.00）A.32B.31C.16 D.15解析：26.数据的存储结构包括顺序、_、索引和散列四种基本类型。（分数：2.00）A.向量B.数组C.集合D.链式 解析：27.在顺序栈中进行退栈操作时，_。（分数：2.00）A.谁先谁后都可以B.先移动栈顶指针，后取出元素C.不分先后，同时进行D.先取出元素，后移动栈顶指针 解析：28.已知一棵二叉树前序遍历和中序遍历分别为 ABDEGCFH和 DBGEACHF，则该二叉树的后序遍历为_。（分数：

20、2.00）A.GEDHFBCAB.DGEBHFCA C.ABCDEFGHD.ACBFEDHG解析：29.树最适合于表示_。（分数：2.00）A.有序数据元素B.无序数据元素C.元素之间无联系的数据D.元素之间具有分支层次关系的数据 解析：30.在下列栈的基本运算中，不是加工型运算的是_。（分数：2.00）A.初始化B.进栈C.退栈D.判栈空 解析：31.实现递归调用属于_的应用。（分数：2.00）A.栈 B.数组C.队列D.二叉树解析：二、B填空题/B(总题数：14，分数：28.00)32.数据元素之间 1 的整体称为逻辑结构。（分数：2.00）填空项 1:_ （正确答案：逻辑关系）解析：33

21、.一个算法的时间复杂性是 1 的函数。（分数：2.00）填空项 1:_ （正确答案：算法输入规模）解析：34.在单链表中，NULL 称为 1，它不指向任何结点，只起 2 作用。（分数：2.00）填空项 1:_ （正确答案：空指针）填空项 1:_ （正确答案：标志）解析：35.对长度为 n顺序表的删除算法，它最坏情况的时间复杂性及其量级分别是 1 和 2，平均时间复杂性及其量级分别为 3 和 4。（分数：2.00）填空项 1:_ （正确答案：n-1；O(n)；(n-1)/2：O(n)）解析：36.存储结点中数据域占用的存储量与整个结点占用的存储量之比称为 1。（分数：2.00）填空项 1:_ （

22、正确答案：存储密度）解析：37.一般地，二叉树可以有 1 种基本形态。（分数：2.00）填空项 1:_ （正确答案：5）解析：38.按照排序过程涉及的存储设备的不同，排序可分为 1 和 2。（分数：2.00）填空项 1:_ （正确答案：内部排序）填空项 1:_ （正确答案：外部排序）解析：39.评价排序算法优劣的主要标准是 1 和 2。（分数：2.00）填空项 1:_ （正确答案：时间复杂性）填空项 1:_ （正确答案：算法需要的附加空间）解析：40.稳定的排序算法有 1、 2 和 3。（分数：2.00）填空项 1:_ （正确答案：直接插入排序：冒泡排序；归并排序）解析：41.第一趟排序后序列中关键字最大的记录交换到最后的排序方法是 1。（分数：2.00）填空项 1:_ （正确答案：冒泡排序）解析：42.数据结构分为逻辑结构与存储结构，线性链表属于 1。（分数：2.00）填空项 1:_ （正确答案：存储结构）解析：43.在树形结构中，树根结点没有 1。（分数：2.00）填空项 1:_ （正确答案：前件）解析：44.数据的逻辑结构有线性结构和 1 两大类。（分数：2.00）填空项 1:_ （正确答案：非线性结构）解析：45.顺序存储方法是把逻辑上相邻的结点存储在物理位置 1 的存储单元中。（分数：2.00）填空项 1:_ （正确答案：相邻）解析：