数据结构c语言版期末考试试题及答案

数据结构c语言版期末考试试题及答案

单项选择题（每题2分，共10题）1.线性表采用顺序存储结构，访问第i个元素的时间复杂度为（）A.O(1)B.O(n)C.O(logn)D.O(n^2)2.栈的操作特性是（）A.先进先出B.先进后出C.随机进出D.以上都不对3.队列的插入操作在（）进行。A.队头B.队尾C.任意位置D.中间位置4.一棵完全二叉树共有360个结点，则在该二叉树中度为1的结点个数为（）A.0B.1C.180D.1815.对n个记录的文件进行快速排序，所需要的辅助存储空间为（）A.O(1)B.O(n)C.O(logn)D.O(n^2)6.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方式最节省运算时间。A.单链表B.双链表C.带头结点的双循环链表D.单循环链表7.哈希表的平均查找长度与（）有关。A.哈希函数B.装填因子C.处理冲突的方法D.以上都是8.已知一个图的邻接矩阵如下，则该图有（）条边。\[\begin{bmatrix}0&1&0&0\\1&0&1&0\\0&1&0&1\\0&0&1&0\end{bmatrix}\]A.3B.4C.5D.69.对于顺序存储的线性表，访问某个元素的时间复杂度为（）A.O(n)B.O(1)C.O(n^2)D.O(logn)10.数据结构中，与所使用的计算机无关的是数据的（）结构。A.存储B.物理C.逻辑D.物理和存储答案：1.A2.B3.B4.B5.C6.C7.D8.B9.B10.C多项选择题（每题2分，共10题）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.广义表6.栈和队列的共同点有（）A.都是线性结构B.都有特定的操作规则C.都可以用数组实现D.都可以用链表实现7.以下哪些操作会改变栈的状态（）A.入栈B.出栈C.取栈顶元素D.初始化栈8.影响哈希表查找效率的因素有（）A.哈希函数的选择B.哈希表的装填因子C.处理冲突的方法D.哈希表的大小9.对于一棵二叉排序树，以下说法正确的是（）A.左子树的所有结点值小于根结点值B.右子树的所有结点值大于根结点值C.中序遍历得到的序列是有序的D.前序遍历可以找到树中的最小值10.以下哪些算法可以用于图的遍历（）A.深度优先搜索B.广度优先搜索C.迪杰斯特拉算法D.克鲁斯卡尔算法答案：1.AB2.AB3.ACD4.ABD5.ABC6.ABCD7.ABD8.ABC9.ABC10.AB判断题（每题2分，共10题）1.线性表的顺序存储结构比链式存储结构更节省存储空间。（）2.栈和队列都是特殊的线性表。（）3.完全二叉树一定是满二叉树。（）4.快速排序在任何情况下的时间复杂度都是O(nlogn)。（）5.哈希表的查找效率只与哈希函数有关。（）6.图的邻接矩阵表示法只能用于有向图。（）7.中序遍历二叉排序树可以得到一个有序序列。（）8.顺序存储的线性表，插入和删除操作的时间复杂度都是O(n)。（）9.拓扑排序适用于有向无环图。（）10.归并排序是一种不稳定的排序算法。（）答案：1.×2.√3.×4.×5.×6.×7.√8.√9.√10.×简答题（每题5分，共4题）1.简述栈和队列的区别。答案：栈是先进后出，操作在栈顶进行；队列是先进先出，插入在队尾，删除在队头。二者操作特性不同，应用场景也不同，栈常用于表达式求值等，队列用于广度优先遍历等。2.简述二叉排序树的定义。答案：二叉排序树要么为空，要么满足：左子树所有结点的值小于根结点的值，右子树所有结点的值大于根结点的值，且左右子树也都是二叉排序树。3.简述选择排序的基本思想。答案：在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。4.简述图的深度优先搜索遍历的基本过程。答案：从图中某一顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程。讨论题（每题5分，共4题）1.讨论顺序存储结构和链式存储结构在不同场景下的优缺点。答案：顺序存储结构优点是存储密度大、可随机访问；缺点是插入删除操作效率低，需连续存储空间。链式存储结构优点是插入删除效率高，无需连续空间；缺点是存储密度小，不可随机访问。顺序结构适用于频繁访问元素场景，链式结构适用于频繁插入删除场景。2.讨论哈希表中处理冲突的方法及各自特点。答案：开放定址法，简单直观，但容易产生聚集现象；链地址法，处理冲突简单，不会产生聚集，且哈希表装填因子可大于1，但指针会占用额外空间。再哈希法计算复杂但效果较好，建立公共溢出区实现简单但效率较低。3.讨论不同排序算法在实际应用中的选择依据。答案：数据量小且基本有序选插入排序；数据量小但无序选冒泡排序或选择排序；数据量大时，稳定要求高可选归并排