数据结构计算机科学与技术专业期末考试试题无答案

数据结构计算机科学与技术专业期末考试试题无答案 本试卷共有四大部分：单项选择题、填空题、判断题和解答题。下面是对每个部分的知识点解释： 一、单项选择题（共15题，每题2分，共30分） 1. 算法的特性：有穷性、确切性、高效性和可行性。题目中选项D、可行性不是算法所必须具备的特性。 知识点：算法的特性、有穷性、确切性、高效性、可行性 2. 线性表的存储方式：顺序表和链表。题目中选项C、一定是不连续的，正确答案是线性表采用链接存储时，其地址不一定是连续的。 知识点：线性表、顺序表、链表、存储方式 3. 线性表的常用操作：取第i个元素及其前趋元素。题目中选项C、双链表，正确答案是采用的存储方式最节省时间。 知识点：线性表、常用操作、存储方式 4. 打印缓冲区：解决计算机主机与打印机之间速度不匹配问题。题目中选项B、队列，正确答案是设置一个打印缓冲区，应该是一个队列结构。 知识点：打印缓冲区、队列、计算机主机、打印机、速度不匹配问题 5. 栈的出栈序列：题目中选项D、2 3 4 1 5 6，不是合法的出栈序列。 知识点：栈、出栈序列 6. 数组的基本操作：存取、修改、检索和排序等。题目中选项D、数组的基本操作没有插入与删除操作，正确答案是除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等。 知识点：数组、基本操作、存取、修改、检索、排序 7. 串的定义：任意有限个符号构成的序列。题目中选项A、符号构成的序列，正确答案是串是任意有限个符号构成的序列。 知识点：串、符号构成的序列 8. 二叉树的前序序列和后序序列：题目中选项A、空或只有一个结点，正确答案是二叉树的前序序列和后序序列正好相反，则该二叉树一定是空或只有一个结点的二叉树。 知识点：二叉树、前序序列、后序序列 9. 树、森林和二叉树的关系：题目中选项B、将树、森林按照二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题，正确答案是讨论树、森林和二叉树的关系，目的是为了借助二叉树上的操作方法去实现对树的的一些操作。 知识点：树、森林、 二叉树、关系 10. 连通图的边的数量：题目中选项C、n+1，正确答案是要连通具有n个顶点的有向图，至少需要n+1条边。 知识点：连通图、边的数量 11. 拓扑排序序列：题目中选项B、1，3，2，4，5，正确答案是该图的正确的拓扑排序序列。 知识点：拓扑排序序列 12. 静态查找与动态查找的根本区别：题目中选项B、施加在其上的操作不同，正确答案是静态查找与动态查找的根本区别在于施加在其上的操作不同。 知识点：静态查找、动态查找、根本区别 13. 哈希查找中k个关键字具有相同哈希值：题目中选项C、k+1，正确答案是哈希查找中k个关键字具有相同哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少需要进行k+1次探测。 知识点：哈希查找、关键字、哈希值、探测 14. 稳定的排序方法：题目中选项A、直接插入排序，正确答案是直接插入排序是稳定的排序方法。 知识点：稳定的排序方法、直接插入排序 15.最佳的内部排序方法：题目中选项A、直接插入排序，正确答案是当待排序序列基本有序或个数较小的情况下，最佳的内部排序方法是直接插入排序。 知识点：内部排序方法、直接插入排序 二、填空题（共8题，每题2分，共16分） 1. 数据的存储结构主要有顺序存储结构和链式存储结构。 知识点：数据的存储结构、顺序存储结构、链式存储结构 2. 顺序表中第一个元素的存储地址是1000，每个元素的长度为2，则第15个元素的存储地址是2008。 知识点：顺序表、存储地址、元素的长度 3. 单链表中插入新结点的时间复杂度为O(n)。 知识点：单链表、插入新结点、时间复杂度 4. 循环队列中，队满时共有n-1个元素。 知识点：循环队列、队满、元素个数 5. 广义表的表头是a。 知识点：广义表、表头 6. 深度为k的二叉树中，所含叶子的个数最多为2^k。 知识点：二叉树、深度、叶子个数 7. 利用简单选择排序对n个记录进行排序，最好情况下，记录交换的次数为0。 知识点：简单选择排序、记录交换、次数 8. 无向图的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于1。 知识点：无向图、邻接矩阵 三、判断题（共8题，每题1分，共8分） 1. 基于某种逻辑结构之上的基本操作，其实现是唯一的。 知识点：逻辑结构、基本操作、实现 2. 线性表的顺序存储结构优于链接存储结构。 知识点：线性表、顺序存储结构、链接存储结构 3. 在单链表中，要取得某个元素，只要知道该元素所在结点的地址即可，因此单链表是随机存取结构。 知识点：单链表、随机存取结构 4. 二叉排序树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值。 知识点：二叉排序树、充要条件 5. 当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂性的主要因素。 知识点：排序、元素、时间复杂性 6. 二分查找法必需在有序表上进行。 知识点：二分查找法、有序表 7. 键值序列{A,C,D,B,E,E,F}不是一个堆。 知识点：键值序列、堆 8. 一个有向图的邻接表和逆邻接表中的结点个数一定相等。 知识点：有向图、邻接表、逆邻接表 四、解答题（共4题） （以下省略）