安徽农业大学《数据结构》2024 - 2025 学年第一学期期末试卷

第1页学院：专业班级：姓名：学院：专业班级：姓名：学号：装订线内不要答题学院/专业：__________姓名：__________学号：__________注意事项：1、本试卷满分100分。2、考试时间120分钟。题号一二三四五六七得分得分评阅人一、单项选择题（总共10题，每题3分，从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分）1.以下关于数据结构的说法，正确的是（）A.数据结构只研究数据的逻辑结构B.数据结构只研究数据的存储结构C.数据结构研究数据的逻辑结构、存储结构及其操作D.数据结构与程序设计语言有关2.线性表的顺序存储结构是一种（）的存储结构。A.随机存取B.顺序存取C.索引存取D.散列存取3.栈的特点是（）A.先进先出B.先进后出C.任意进出D.进出无序4.队列的操作原则是（）A.先进先出B.先进后出C.任意进出D.进出无序5.若一棵二叉树中度为2的结点数为15，则该二叉树的叶结点数为（）A.16B.15C.17D.不确定6.深度为5的完全二叉树的结点数最多为（）A.16B.31C.32D.647.对于排序算法，以下哪种算法平均时间复杂度最低（）A.冒泡排序B.选择排序C.插入排序D.快速排序8.哈希表的平均查找长度与（）有关。A.哈希函数B.装填因子C.哈希表的大小D.以上都有关9.数据结构中，与所使用的计算机无关的是数据的（）A.存储结构B.物理结构C.逻辑结构D.物理和存储结构10.设有一个二维数组A[10][20]，其元素按行存放，每个元素占一个存储单元，且A[0][0]的存储地址为2000，则A[6][12]的存储地址为（）A.2112B.2240C.2242D.2244二、多项选择题（总共5题，每题4分，下列各题有多个正确答案，请将所有正确答案的代号填在答题纸相应位置处，答案选错或未选全者，该题不得分）1.以下属于数据的逻辑结构的有（）A.线性结构B.树形结构C.图状结构D.顺序结构2.栈可以用来实现（）A.函数调用B.表达式求值C.递归D.缓冲区3.以下关于二叉排序树的说法正确的是（）A.左子树上所有结点的值均小于根结点的值B.右子树上所有结点的值均大于根结点的值C.中序遍历二叉排序树可以得到一个有序序列D.插入和删除操作不会破坏二叉排序树的性质4.以下排序算法中，属于稳定排序的有（）A.冒泡排序B.选择排序C.插入排序D.归并排序5.对于哈希表，以下说法正确的是（）A.哈希表的查找效率取决于哈希函数的好坏B.装填因子越大，哈希表的查找效率越低C.哈希表可以减少查找时间D.哈希表的平均查找长度与哈希函数无关三、判断题（总共10题，每题2分，请将判断结果填在答题纸相应位置处，正确的填“√”，错误的填“×”）1.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。（）2.线性表采用顺序存储时，对表中元素的存取是随机的。（）3.栈和队列都是特殊的线性表，它们的操作原则不同。（）4.二叉树中每个结点的度都小于等于2。（）5.完全二叉树一定是满二叉树。（）6.快速排序在最坏情况下的时间复杂度为O(n)。（）7.哈希表中的冲突是指不同关键字通过哈希函数得到相同的哈希地址。（）8.数据的逻辑结构决定了数据的存储结构。（）9.顺序存储结构比链式存储结构更节省存储空间。（）10.对二叉排序树进行中序遍历可以得到一个递增的序列。（）四、简答题（总共3题，每题10分，请简要回答下列问题）1.简述线性表的顺序存储结构和链式存储结构的优缺点。2.简述栈和队列的区别与联系。3.简述排序算法的稳定性，并举例说明稳定排序算法和不稳定