《齐鲁工业大学2024年成人高等教育《数据结构》期末考试题及参考答案.docx》由会员分享，可在线阅读，更多相关《齐鲁工业大学2024年成人高等教育《数据结构》期末考试题及参考答案.docx（71页珍藏版）》请在课桌文档上搜索。
1、成人高等教育数据结构（一）一、单选题1.用链接方式存储的队列，在进行插入运算时（）。口仅修改头指针口头、尾指针都要修改a仅修改尾指针口头、尾指针可能都要修改正确答案C2.按排序过程中依据的原则分类，快速排序属于（）。口插入类的排序方法醺选择类的排序方法31交换类的排序方法口归并类的排序方法正确答案C3.设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为（）。正确答案C4.在数据结构的讨论中把数据结构从逻辑上分为（）。门内部结构与外部结构静态结构与动态结构a线性结构与非线性结构口紧凑结构与非紧凑结构正确答案C5.深度优先遍历类似于二叉树的（）分）门先序遍历口中序遍历日后序遍历S
2、l层次遍历正确答案D6.如下陈述中正确的是（2.5分）口串是一种特殊的线性表耳串的长度必须大于零日串中元素只能是字母口空串就是空格串正确答案A7.下面排序算法的时间复杂度最小的是（）。（2.5分）门直接插入排序目简单选择排序日冒泡排序口快速排序正确答案D8.衡量查找算法效率的主要标准是（）2.5分）a元素的个数修所需的存储量,平均查找长度口算法难易程度适合对动态查找表进行高效率查找的组织结构是（有序表可分块有序表日二叉排序树口快速排序正确答案C10.两个字符串相等的条件是（）。口串的长度相等口含有相同的字符集a都是非空串口串的长度相等且对应的字符相同正确答案D11.一棵具有5层满二叉树中节点总
3、数为（正确答案C12.串是任意有限个（）。口符号构成的序列,符号构成的集合,字符构成的序列口字符构成的集合正确答案C13.一棵深度为6的二叉树至多有（）个结点。（2.5分）加3正确答案D14.链表不具有的特点是（）。（2.5分）口插入、删除不需要移动元素修可随机访问任一元素不必事先估计存储空间口所需空间与线性长度成正比正确答案B15.算法分析的主要方法是（）。口空间复杂度和时间复杂度口正确性和简明性日可读性和文档性口数据复杂性和程序复杂性正确答案A16.一棵含18个结点的二叉树的高度至少为（）。正确答案C17.与数据元素本身的形式、内容、相对位置、个数无关的是数据的口存储结构逻辑结构日算法口操
4、作正确答案B18.从逻辑上可以把数据结构分为（）。门动态结构、静态结构顺序结构、链式结构日线性结构、非线性结构口初等结构、构造型结构正确答案C19.队列的删除操作是在（）。（2.5分）口队尾口队前日队首口队后正确答案C20.下列排序方法中，稳定的排序方法为（口希尔排序可堆排序a快速排序口直接插入排序正确答案D二、判断题1.在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=Tear。正确答案错误2.当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。正确答案正确3.单链表
5、可以实现随机存取。正确答案错误4.每种数据结构都应具备三种基本运算：插入、删除和搜索。（25分）正确答案错误5.完全二叉树就是满二叉树。正确答案错误6.栈的特点是先进后出，队列的特点是先进先出。正确答案正确7.空串是任意串的子串。（2.5分）正确答案正确8.存在这样的二叉树，对它采用任何次序的遍历，结果相同。（2.5分）正确答案正确在有向图中每个顶点的度等于各顶点的入度与出度之和。（2.5分）正确答案正确9.栈是一种线性结构。（2.5分）正确答案正确10.在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。正确答案错误11.栈和队列的存储方式，既可以顺序存储也可以链式存储。/
6、C1.八、3分）正确答案正确12.二叉树是一棵无序树。（2.5分）正确答案错误13.在任意一棵二叉树中，叶子结点的个数等于度为2结点的个数加Io正确答案正确14.“顺序查找法”是指在顺序表上进行查找的方法。正确答案错误15.堆排序是一种稳定的排序算法。正确答案错误16.对链表进行插入和删除操作时，不必移动结点。/C1.八、(2.07T)正确答案正确17.内部排序是指排序过程中在内存中进行排序。(2.5分)正确答案正确18.线性表的逻辑顺序与物理顺序总是一致的。（2.5分）正确答案正确19.满二叉树中存在度为1的结点。（2.5分）正确答案错误您的答案是未作答回答错误成人高等教育数据结构（二）一单
7、选题1.一棵具有5层满二叉树中节点总数为（）。（2.5分）JJ33日32三31由6噩正确答案C2.堆是一种（）排序。窜入日僻口归并正确答案B3.使用折半查找，线性表必须（）。（2.5分）自以顺序方式存储同以页序方式存储，且元素已按值排好序日以链式方式存储同|以链式方式存储，且元素已按值S的序正确答案B4.数据结构这门学科的研究内容下面选项最准确的是（）O（2.5分）研究数据对象和数据之间的关系研究数据对象W研究数据对象和数据的操作W研究数据对象、数据之间的关系和操作正确答案D5.与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。（2.5分）口逻辑结构靠法串作正确答案B6.队列的删除
8、操作是在（）。（2.5分）件艰日队前日队首正确答案C7.数据结构在计算机内存储器中的表示是指（）。（2.5分）口数据蹄：；雌元素之间的关系鬻数据的逻辑结构，数据的物理存储结构正确答案D8.在有n个叶子结点的哈夫曼树中，其结点总数为（）（2.5分）口襁定三2n+l三2n-l9.线性表采用链式存储结构时，要求内存中可用存储单元的地址（）。（2.5分）口必须是连续的I必须是部分连续的定是不连续的乖续和不连续都可以正确答案D10.排序算法中，不稳定的排序是（）。（2.5分）11三螭入排序冒泡排序己哪序期蝌排序正确答案C11.链表适用于（）查找。（2.5分）E砺日二分法3三序，也能二分法日随机正确答案A
9、12.下面排序算法的时间复杂度最小的是（）。（2.5分）口直接插入排序日简单选择排序日冒泡排序鬻快速排序正确答案D13.将6个不同的整数进行排序，至少需要比较（）次正确答案A14.队列的插入操作是在（）进行。（2.5分）11三队首日队前钵AS正确答案A15.算法指的是（）。（2.5分）口计算机程序。解决问题的计算方法鼬序算法解决问题的有限运算序列正确答案D16.算法分析的主要方法是（）。（2.5分）空间复杂度和时间复杂度正确性和简明性己可读性和文档性，辘复杂性和程序复杂性正确答案A17.从逻辑上可以把数据结构分为（）O（2.5分）日动态结构、静态结构日顺序结构、链式结构靠性结构、非线性结构1初
10、等结构、构造型结构正确答案C18.以下排序方法中，稳定的排序方法是（）。（2.5分）j直接插入排序和冒泡排序简单选择排序和归并排序。泡排序和快速排序口期E序和基数排序正确答案A19.设JI访表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为（）。（2.5分）20.衡量查找算法效率的主要标准是（）（2.5分）口元素的个数所需的存储量券均查找长度覆算法难易程度正确答案C二.判断题1.任何一棵二叉树的叶结点在三种遍历中的相对次序是不变的。（2.5分）正确答案正确2.串中任意个字符组成的子序列称为该串的子串。（2.5分）正确答案错误3.对链表进行插入和删除操作时，不必移动结点。（2.5分）
11、正确答案正确4.已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。（2.5分）正确答案正确5.数据项是数据处理的最小单位。（2.5分）正确答案正确6.栈和队列都是操作受限制的线性表。（2.5分）正确答案正确7.线性表的顺序存储结构优于链式存储结构。（2.5分）正确答案错误8.完全二叉树中每个结点或者没有孩子或者有2个孩子。（2.5分）正确答案错误9.二叉树是一棵无序树。（2.5分）正确答案错误10.当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。（2.5分）正确答案正确11.顺序存储的线性表可以随机访问，链式存储的线
12、性表只能JI质序访问。（2.5分）正确答案正确12.内部排序是指排序过程中在内存中进行排序。（2.5分）正确答案正确13.双链表中至多只有一个结点的后继指针为空。（2.5分）正确答案正确14.满二叉树中存在度为1的结点。（2.5分）正确答案错误15.选择排序过程中元素之间的比较次数与原始序列的状态无关。正确答案正确16一棵哈夫曼树有m个叶子结点，则其结点总数为2m-lo（2.5分）正确答案正确17.在任意一棵二叉树中，叶子结点的个数等于度为2结点的个数加I0（2.5分）正确答案正确18.一个算法具有五个特性：确定性、可行性、有穷性、输入和输出。（2.5分）正确答案错误19栈的特点是先进后出，队
13、列的特点是先进先出。（2.5分）正确答案正确20.每种数据结构都应具备三种基本运算：插入、删除和搜索。（2.5分）正确答案错误您的答案是未作答回答错误成人高等教育数据结构（三）一、单选题1.用链接方式存储的队列，在进行插入运算时（）。口仅修改头指针口头、尾指针都要修改a仅修改尾指针口头、尾指针可能都要修改正确答案C2.以下排序方法中，稳定的排序方法是（）。口直接插入排序和冒泡排序口简单选择排序和归并排序日泡排序和快速排序口堆排序和基数排序正确答案A3.堆是一种（）排序。口插入曰选择日交换口归并正确答案B4.串是任意有限个（）。（2.5分）口符号构成的序列口符号构成的集合,字符构成的序列口字符构
14、成的集合正确答案C5.链表不具有的特点是（）。（2.5分）口插入、删除不需要移动元素口可随机访问任一元素日不必事先估计存储空间口所需空间与线性长度成正比正确答案B6.对于栈操作数据的原则是（2.5分）口先进先出同后进先出日后进后出口不分顺序正确答案B7.适合对动态查找表进行高效率查找的组织结构是（）。（2.5分）有序表q分块有序表日二叉排序树口快速排序正确答案C8.线性表采用链式存储结构时，要求内存中可用存储单元的地址（）O（2.5分）口必须是连续的醺必须是部分连续的，一定是不连续的口连续和不连续都可以判断顺序栈（最多结点数为m）为栈满的条件是（IJtop=O圆top!=mJtopI=OJto
15、p=m正确答案D10.邻接矩阵为对称矩阵的图是（）。（/0j/口无向图可有向图日带权有向图口有向图或无向图正确答案A11.下列排序方法中，稳定的排序方法为（）。（乙t）/T）门希尔排序口堆排序a快速排序口直接插入排序正确答案D12.在一个非空二叉树的中序遍历序列中，根结点的右边（门只有右子树上的所有结点日只有右子树上的部分结点,只有左子树的上的部分结点口只有左子树上的所有结点正确答案A13.从逻辑上可以把数据结构分为（）。a动态结构、静态结构可顺序结构、链式结构,线性结构、非线性结构口初等结构、构造型结构正确答案C14.树最适合用来表示（）。（2.5分）口有序数据元素口无序数据元素,元素之间具
16、有分支层次关系的数据口元素之间无联系的数据正确答案C15.设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为（）。（2.5分）正确答案C16.与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）O口存储结构目逻辑结构日算法口操作正确答案B17.两个字符串相等的条件是（分）口串的长度相等口含有相同的字符集a都是非空串口串的长度相等且对应的字符相同正确答案D18.算法指的是（）。（2.5分）口计算机程序日解决问题的计算方法日排序算法口解决问题的有限运算序列正确答案D19.已知二叉树的先序遍历序列为ABCD,中序遍历序列为BCDA,则后序遍历序列为（）。（2.5分）0ABC
17、D邸CDAJcdbaEDCBA20.关于串的叙述，错误的是（）。（2.5分）口串是字符有限序列耳串是由空格组成的串,模式匹配是串的重要运算口串有用顺序、链式两种存储方式正确答案B二、判断题每题2.5分，共20道小题，总分值50分）1.栈和队列都是操作受限制的线性表。（2.5分）正确答案正确2.在二叉排序树中插入新结点时，新结点总是作为叶子结点插入。（2.5分）正确答案正确3.完全二叉树中每个结点或者没有孩子或者有2个孩子。（2.5分）4.一个算法具有五个特性：确定性、可行性、有穷性、输入和输出。（25分）正确答案错误5.双链表中至多只有一个结点的后继指针为空。正确答案正确6.空串是任意串的子串
18、。正确答案正确7.线性表的顺序存储结构优于链式存储结构。（2.5分）正确答案错误8.在线性链表中删除中间的结点时，只需将被删结点释放。（2.5分）正确答案错误9.栈可以作为实现程序设计语言过程调用时的一种数据结构。（2.5分）正确答案正确10.采用不同的遍历方法，所得到的无意向图生成树总是相同的。（2.5分）正确答案错误11.线性表的逻辑顺序总是与其物理顺序一致。正确答案错误12.完全二叉树就是满二叉树。（25分）正确答案错误13.选择排序过程中元素之间的比较次数与原始序列的状态无关。正确答案正确14.栈和队列的存储方式，既可以顺序存储也可以链式存储O分）正确答案正确15.快速排序在任何情况下
19、均可得到最快的排序效果。正确答案错误16.二叉树中每个结点的度最大为2,因此二叉树是一种特殊的树。（2.5分）正确答案错误17.在长度为n的顺序表中，求第i个元素的直接前驱算法的时间复杂度为O。正确答案正确18.任何一棵二叉树的叶结点在三种遍历中的相对次序是不变的。（2.5分）正确答案正确19.最小生成树是指边数最少的生成树。正确答案错误20.在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。纠错正确答案错误您的答案是未作答回答错误成人高等教育数据结构（四）一单选题1.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。（2.5分）
20、M链表国双链表事向循环砺表正确答案D2.在一个非空二叉树的中序遍历序列中，根结点的右边（）（2.5分）口只有右子树上的所有结点日只有右子树上的部分结点日只有左子树的上的部分结点0只有左子树上的所有结点正确答案A3.一棵具有5层满二叉树中节点总数为（）。（2.5分）正确答案C4.线性表采用链式存储结构时，要求内存中可用存储单元的地址（）。（2.5分）口必须是连续的:必须是部分连续的日定是不连续的口连续和不连续都可以正确答案D5.如下陈述中正确的是（）。（2.5分）串是一种特殊的线性表串的长度必须大于零串中元素只能是字母日空串就是空格串正确答案A6.堆是一种（）排序。（2.5分）窜入日蝌回归并正确
21、答案B7.对n个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多（）（2.5分）飘小到大排列好的日从大到小排列好的m元素无序口元素基本有序正确答案B8.数据结构在计算机内存储器中的表示是指（）。（2.5分）口数据结构昌翔S元素之间的关系修数据的逻辑结构数据的物理存储结构正确答案D9.使用折半查找，线性表必须（）O（2.5分）日以顺方式存储I以顺序方式存储，且元素已按值排好序m以链式方式存储口以链式方式存储，且元素已按值排好序正确答案B10广义表是线性表的推广，它们之间的区别在于（）。（2.5分）口是否能为空,能否使用子表。能否使用原子项表的长度正确答案B11.两个字符串相等的条件是（）
22、。（2.5分）串的长度相等口含有相同的字符集靠是非空串0串的长度相等且7寸应的字符相同正确答案D12.以下数据结构中哪一个是非线性结构？（）。（2.5分）日队列靠m辘表牛叉树正确答案D13.用链表表示线性表的优点是（）。（2.5分）嚼便于随机存取花费的存储空间比顺序表少a数据元素的物理顺序与逻辑顺序相同乖于插入与删除正确答案D14.对一个算法的评价，不包括如下（）方面的内容。（2.5分）口健壮性和可读性鹭正确性融行性口时空复杂度正确答案C15快速排序在下列哪种情况下最易发挥其长处（）O（2.5分）被排序的数据中含有多个相同排序码拗E序的数据已基本有序日被排序的数据完全无序了被排序的数据中的最大
23、值和最小值相差悬殊16.一个队列的入队序列是1,2,3,4,则队列的输出序列是（）。（2.5分）04,3,2,101,2,3,401,4,3,203.2,4,1正确答案B17.用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的。（2.5分）队列18.已知二叉树的先序遍历序列为ABCD,中序遍历序列为BCDA,则后序遍历序列为（2.5分）ABCDBCDACDBADCBA正确答案D19.在一个具有n个顶点的无向图中，要连通所有顶点则至少需要）条边。2.5分）Sn=I20.链表不具有的特点是（）。（2.5分）EJ插入、删除不需要移动元素胃可随机访问任一元素不必事先估计存储空间口所需空间与线
24、性长度成正比正确答案B二、判断题1.快速排序在任何情况下均可得到最快的排序效果。（2.5分）正确答案错误2.堆排序是一种稳定的排序算法。（2.5分）3.存在这样的二叉树，对它采用任何次序的遍历，结果相同。（2.5分）正确答案正确4.键值序歹1.IA,C,D,E,F,E,F是一个堆。（2.5分）正确答案正确5.在有向图中每个顶点的度等于各顶点的入度与出度之和。（2.5分）正确答案正确6.串中任意个字符组成的子序列称为该串的子串。（2.5分）正确答案错误7.进行折半查找的表必须是JI质序存储的有序表。（2.5分）正确答案正确8.一棵哈夫曼树有m个叶子结点，则其结点总数为2m-lo（2.5分）正确答
25、案正确9.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（2.5分）正确答案正确10.数据项是数据处理的最小单位。（2.5分）正确答案正确11.单链表可以实现随机存取。（2.5分）正确答案错误12.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。（2.5分）正确答案正确13.只有面向对象的计算机语言才能描述数据结构算法。（2.5分）正确答案错误14.当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。（2.5分）正确答案正确15.向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶
26、子结点。（2.5分）正确答案正确16.树的先根遍历序列等同于该树对应的二叉树中序遍历序列。（2.5分）正确答案错误17.在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。（2.5分）正确答案错误18.线性表的逻辑顺序总是与其物理三序一致。（2.5分）正确答案错误19.栈的特点是先进后出，队列的特点是先进先出。（2.5分）正确答案正确20非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。（2.5分）正确答案错误您的答案是未作答回答错误成人高等教育数据结构（五）一、单选题1.算法分析的主要方法是（）。口空间复杂度和时间复杂度目正确性和简明性日可读性和文档性口数据复杂性和程
27、序复杂性正确答案A2.堆是一种（）排序。口插入醺选择日交换口归并正确答案B3.树最适合用来表示（）。口有序数据元素,无序数据元素日元素之间具有分支层次关系的数据口元素之间无联系的数据正确答案C4.队列的删除操作是在（）。（2.5分）口队尾,队前日队首口队后正确答案C5.算法分析的目的是（）。（2.5分）辨别数据结构的合理性口研究算法中输入与输出的关系日评价算法的效率口鉴别算法的可读性正确答案C6.对一个算法的评价，不包括如下（）方面的内容。分）口健壮性和可读性口正确性a并行性口时空复杂度正确答案C7.将6个不同的整数进行排序，至少需要比较（）次3151121正确答案A8.下列排序方法中，稳定的
28、排序方法为（）。（2.5分）希尔排序口堆排序日快速排序口直接插入排序正确答案D在数据结构中，数据的基本单位是（口数据项口数据元素,数据对象口数据文件正确答案B10.下面排序算法的时间复杂度最小的是（）。（2.5分）门直接插入排序目简单选择排序，冒泡排序口快速排序正确答案D11.数据结构在计算机内存储器中的表示是指（）。2.5分)口数据结构数据元素之间的关系区数据的逻辑结构口数据的物理存储结构12.以下数据结构中哪一个是非线性结构？（）。/25分）口队列栈a线性表口二叉树正确答案D13.在顺序表中，只要知道（），就可在相同时间内求出任一结点的存储地址。（25分）门基地址口结点大小日向量大小口基地
29、址和结点大小正确答案D14.己知二叉树的先序遍历序列为ABCD,中序遍历序列为BCDA,则后序遍历序列为（）。（2.5分）Qabcd弗CDASCDBAEDCBA正确答案D15.线性表的顺序存储结构是一种（）的存储结构。（2.5分）门随机存取口顺序存取日索引存取口散列存取正确答案A16.从逻辑上可以把数据结构分为（）。门动态结构、静态结构可顺序结构、链式结构31线性结构、非线性结构口初等结构、构造型结构正确答案C17.在一个具有11个顶点的无向图中，要连通所有顶点则至少需要）条边。正确答案C18.链表适用于（）查找。（2.5分）口顺序口二分法日顺序，也能二分法口随机正确答案A19.对稀疏矩阵进行
30、压缩存储目的是（2.5分）口便于进行矩阵运算口便输入和输出,节约存储空间口降低运算的时间复杂度正确答案C20.算法的时间复杂度取决于（2.5分）口问题的规模口待处理数据的初始状态日问题的规模和待处理数据的初始状态口不确定正确答案C二、判断题共20道小题，总分值50分）1.“顺序查找法”是指在顺序表上进行查找的方法。正确答案错误2.向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。正确答案正确3.存在这样的二叉树，对它采用任何次序的遍历，结果相同。4.在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。正确答案错误5.图的广度优先搜索算法通常采用递归算法求解
31、。（2.5分）正确答案正确6.满二叉树中存在度为1的结点。（2.5分）正确答案错误7.完全二叉树就是满二叉树。（2.5分）正确答案错误8.线性表的逻辑顺序总是与其物理顺序一致。当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。正确答案正确10.在长度为n的顺序表中，求第i个元素的直接前驱算法的时间复杂度为。正确答案正确11.线性表的顺序存储和链式存储都必须占用内存中的连续存储单元。（2.5分）正确答案错误12.进行折半查找的表必须是顺序存储的有序表。正确答案正确13.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。分）正确答案正确14.每种数据结构都应具备三种基本运算：插入、删除和搜索。正确答案错误15.在线性链表中删除中间的结点时，只需将被删结点释放。（2.5分）正确答案错误16.线性表的顺序存储结构优于链式存储结构。（2.5分）正确答案错误17.在任意一棵二叉树中，叶子结点的个数等于度为2结点的个数加Io（2.5分）正确答案正确18.栈可以作为实现程序设计语言过程调用时的一种数据结构。正确答案正确19.图的深度优先搜索是一种典型的回溯搜素的例子，可以通过递归算法求解。（2.5分）正确答案正确20.在有向图中每个顶点的度等于各顶点的入度与出度之和。（2.5分）正确答案正确
