华南师范大学数据结构期末考试试卷

华南师范大学--数据结构-期末题含答案.pdf 本资源是华南师范大学计算机科学系2003-2004学年第（一）学期期末考试试卷，主要考察学生对数据结构的理解和应用。试卷共分为三部分：判断题、单项选择题和填空题。 一、判断题（正确的划“√”，错误的划“×”。每小题1分，共5分） 1. 顺序存储方式只能用于存储线性结构。（√） 顺序存储方式可以用于存储线性结构，如数组、链表等，但也可以用于存储非线性结构，如树、图等。 2. 用邻接矩阵表示图所用的存储空间大小与图的边数成正比。（×） 邻接矩阵表示图所用的存储空间大小与图的顶点数成正比，而不是边数。因为邻接矩阵的大小是顶点数的平方。 3. 哈夫曼树一定是满二叉树。（×） 哈夫曼树不一定是满二叉树，哈夫曼树是一种特殊的二叉树，它的叶子节点的路径长度之和最小。 4. 中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（√） 中序遍历一棵二叉排序树的结点可以得到排好序的结点序列，因为二叉排序树的中序遍历结果是排好序的。 5. 栈和队列都是限制存取点的线性结构。（√） 栈和队列都是限制存取点的线性结构，栈限制从顶部存取，队列限制从头部或尾部存取。 二、单项选择题（每小题2分，共10分） 1. 算法的时间复杂度取决于（a）问题的规模 算法的时间复杂度取决于问题的规模、待处理数据的初态和算法的设计等因素。 2. 若需要在O(nlog2(n))的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是：（c）归并排序 归并排序的时间复杂度是O(nlog2(n))，且是稳定的排序方法。 3. 具有n个顶点的有向图最多有（b）n(n-1)条边。 具有n个顶点的有向图最多有n(n-1)条边，因为每个顶点可以与其他n-1个顶点相连。 4. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（a）插入排序法。 插入排序法是从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置。 5. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除一个元素，则采用（c）带表头结点的双向循环链表存储方式最节省时间。 带表头结点的双向循环链表存储方式可以快速实现插入和删除操作。 三、填空题（每空1分，共20分） 1. 在单链表中经常设置一个头结点，那么头结点的作用是：简化链表的操作和管理。 头结点可以简化链表的操作和管理，使得链表的操作更加方便和高效。 2. 设广义表L＝(（a，b），（c，d）)，则head(L)是a；tail(L)是(b，c，d)；L的长度是3；深度是2。 广义表是一种复杂的数据结构，它可以表示多种类型的数据，head(L)是广义表的头结点，tail(L)是广义表的尾结点，L的长度是广义表中的元素个数，深度是广义表的层数。 3. 设W为一个二维数组，其每个数据元素Wij占用6个字节，行下标i从0到8，列下标j从2到5，则二维数组W的数据元素共占用1440个字节。W中第6行的元素和第4列的元素共占用36个字节。若按行顺序存放二维数组W，其起始地址的字节号为100，则二维数组W的最后一个数组元素的起始地址的字节号为1136，数组元素W34的起始地址号为1084，而数组元素W22的起始地址与当W按列顺序存放时数据元素的起始地址相同。 二维数组W的数据元素占用空间的计算是根据行下标和列下标来计算的，W中第6行的元素和第4列的元素占用空间的计算也是一样。 4. 用循环链表表示的队列长度为n，若只设头指针，则可以快速实现队列的操作。 循环链表可以快速实现队列的操作，因为循环链表可以快速地插入和删除元素。