2003年数据结构考试重点：填空与判断题解析

"该资源是一份2003年的数据结构期末考试试题，包含了填空题、判断题和选择题，涵盖了数据结构的基础知识，如二叉树的遍历、排序算法、栈与队列的操作、数据结构的概念、以及图和编码的相关知识。" 详细知识点解析： 1. 二叉树高度与节点数的关系： - 高度为k的二叉树的最大结点数是2^(k+1) - 1，最小结点数是k+1。 - 填空题中，最大结点数为2^(k+1) - 1，最小结点数为k+1。 2. 二叉树的遍历： - 给定中序遍历和后序遍历，可以唯一确定一棵二叉树。根据中序和后序遍历，可以推导出前序遍历。 - 在这个问题中，前序遍历序列为E, A, B, D, C, F, G。 - 对应的树林包含两棵树，因为后序遍历中，最后一个元素E是整个二叉树的根，而A到D在后序中在一起，形成一棵树，F到G形成另一棵树。 3. 希尔排序和快速排序： - 希尔排序是一种插入排序的改进版，通过设置初始步长进行分组，减少元素的交换次数。 - 初始步长为4的希尔排序，一趟扫描后，关键码序列可能变为(H, Q, A, M, S, R, D, F, X, Y, C, Q)。 - 快速排序是通过分治策略实现的，以第一个元素为分界元素，一趟扫描后，序列可能变为(A, F, G, C, H, Q, D, S, M, R, X, Y)。 4. 栈的溢出与下溢： - 栈的上溢发生在压入新元素时，栈已满，没有空间容纳新元素。 - 栈的下溢通常不会发生，因为栈为空时，不再执行弹出操作。 5. 起泡排序的比较与移动次数： - 起泡排序在最好情况下（已排序），只需做n-1次比较和0次移动。 - 在最坏情况下（逆序），需要做n*(n-1)/2次比较。 判断题部分涉及的知识点： - 数据结构包括逻辑结构、存储结构和运算三个方面。 - 线性结构可以顺序存储或链式存储，非线性结构也有多种存储方式。 - 栈和队列是特殊的线性表，分别遵循后进先出和先进先出原则。 - 单链表无法从中间结点访问所有结点，需要从头结点开始。 - 将一棵树转换成二叉树，根结点可能有左右子树。 - 哈夫曼树是最优二叉树，权值较大的结点离根较远。 - 邻接矩阵存储图，所需空间与图的边数有关。 - 哈夫曼编码中，相同频率的字符编码可以不同，以便保持编码唯一性。 - 顺序存储的线性表需要连续存储单元。 - 快速排序是不稳定的排序算法，因为相等元素的相对位置可能会改变。 单项选择题涉及的内容涵盖更广泛，包括数据结构的各个方面，如链表、树、图、排序算法等，每个题目都需要对相应的概念有深入理解才能解答。