大学数据结构期末考试试题

大学数据结构期末考试试题考试时间：120分钟满分：100分注意事项：1.请在答题纸指定位置填写姓名、学号和班级。2.所有答案请书写在答题纸指定区域内，超出区域的答案无效。3.字迹工整，卷面整洁，否则酌情扣分。4.严禁作弊，一经发现，按学校相关规定处理。一、选择题(每题2分，共20分)1.以下关于数据结构的说法中，不正确的是（）A.数据结构是计算机中组织和存储数据的特定方式B.数据结构包括数据的逻辑结构和物理结构C.一种逻辑结构只能有一种对应的物理结构D.算法的设计与数据结构的选择密切相关2.在一个长度为n的顺序表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需向后移动（）个元素。A.n-iB.n-i+1C.n-i-1D.i3.栈和队列的共同点是（）A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点4.对于一棵深度为h的满二叉树，其节点总数为（）A.2^hB.2^h-1C.2^(h-1)D.h5.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则其前序遍历序列是（）A.cedbaB.acbedC.decabD.ceabd6.在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。A.1/2B.1C.2D.47.采用邻接表存储的图，其深度优先遍历类似于二叉树的（）A.先序遍历B.中序遍历C.后序遍历D.层次遍历8.下列排序方法中，不稳定的是（）A.直接插入排序B.冒泡排序C.快速排序D.归并排序9.对线性表进行折半查找时，要求线性表必须（）10.在哈希表中，解决冲突的方法不包括（）A.开放定址法B.链地址法C.除留余数法D.公共溢出区法二、填空题(每空2分，共20分)1.数据结构被定义为（）的集合以及定义在该集合上的（）的集合。2.链表中，逻辑上相邻的节点其物理位置（）相邻。3.队列的特点是（）。4.字符串“ababaab”的长度是（），其next数组（不考虑改进算法）的值为（）。（注：next数组下标从0或1开始均可，请在答题时注明）5.一棵二叉树的第k层最多有（）个节点。6.图的深度优先搜索遍历中，需要使用（）数据结构来保存待访问的节点。7.对于n个记录的集合进行冒泡排序，在最坏情况下的时间复杂度是（）。8.当待排序的序列基本有序时，（）排序方法的效率较低。9.索引顺序查找是一种介于（）查找和（）查找之间的查找方法。三、简答题(每题5分，共20分)1.简述时间复杂度和空间复杂度的概念，并说明在算法分析中为何通常更关注时间复杂度。2.试比较顺序存储结构和链式存储结构的优缺点。3.什么是平衡二叉树？为什么要引入平衡二叉树？4.简述Prim算法和Kruskal算法的基本思想，并说明它们的主要区别。四、算法设计与分析题(共40分)1.（10分）已知一个带头节点的单链表L，其节点结构为：`data|next`。请编写一个算法，删除链表中所有值为x的节点。要求：*给出算法的基本思路。*写出完整的C语言或Java语言函数实现。2.（10分）假设以数组S[0..m-1]作为两个栈的共享存储空间，两个栈的栈底分别设在数组的两端，栈顶指针分别为top0和top1（分别指向栈顶元素的下一个位置）。试编写算法实现这两个栈的入栈操作（push0和push1）和出栈操作（pop0和pop1）。要求：*说明栈空和栈满的条件。*写出完整的C语言或Java语言函数实现（至少实现push0和pop0）。3.（10分）已知一棵二叉树的根节点指针为root，每个节点包含数据域data和左右孩子指针left、right。请编写一个递归算法，计算该二叉树的深度（或高度）。要求：*给出算法的基本思路。*写出完整的C语言或Java语言函数实现。4.（10分）设有一组关键字序列为：{12,23,31,18,45,27,50,36}。请回答下列问题：*若采用直接插入排序，写出每一趟排序后的结果（按从小到大顺序）。*若采用快速排序，以第一个元素为基准元素，写出第一趟排序后的结果，并简要说明该趟排序的过程。--