2006年电信研究院数据结构(殷仁昆教授讲授).doc

《数据结构》试题（开卷） 学号 姓名 一、单项选择题（每空1分，共10分） 从A, B, C, D四个选项中选择一个正确的答案，将其标号与题号对应起来。 若线性表使用频率最高的运算是查找第i个元素及其前驱的值，则采用（ ）方法存储最节省时间。 A. 单链表 B. 双向链表C. 单向循环链表 D. 顺序表 对于用一维数组element[n]顺序存储的线性表，其算法的时间复杂度为O(1)的运算应是（ ）。 A. 将n个元素从小到大排序 B. 从线性表中删除第i个元素(1≤i≤n) C. 查找第i个元素(1≤i≤n) D. 在第i个元素(1≤i≤n)后插入一个新元素 假设一个栈的输入序列是1、2、3、4，则不可能得到的输出序列是（ ）。 A. 1、2、3、4 B. 4、1、2、3 C. 4、3、2、1 D. 1、3、4、2 将递归算法转换成对应的非递归算法时，除了单向递归和尾递归的情况外，通常需要使用（ ）保存中间结果。 A. 链表 B. 栈C. 队列 D. 顺序表 假设一个循环队列Q[maxSize] 的队头指针为front，队尾指针为rear，队列的最大容量为maxSize，除此之外，该队列再没有其他数据成员，则该队列的队满条件是（ ）。 A. Q.front == Q. rear B. Q.front+Q.rear = maxSize C. Q.front == (Q.rear+1) % maxSize C. Q.rear == (Q.front+1) % maxSize 在一个二维数组A中，假设每个数组的长度为3个存储单元，行下标i从0到8，列下标j从0到9，从首地址SA开始按行连续存放。在这种情况下，元素A[8][5]的起始地址为（ ）。 A. SA+141 B. SA+144 C. SA+222 D. SA+255 树最适合用来表示（ ）的数据。 A. 有序 B. 无序 C. 任意元素之间具有多种联系 D. 元素之间具有分支层次关系 在一棵非空二叉树的中序遍历序列中，树根结点的右边（ ）。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的所有结点 D. 只有左子树上的部分结点 设n和m分别是一棵二叉树上的两个结点，在中序遍历时，n在m前面访问的条件是（ ）。A. n在m右侧分支B. n是m祖先C. n在m左侧分支 D. n是m子孙 设森林中有三棵树，第一、第二和第三棵树中的结点个数分别为m1，m2和m3。那么在由该森林转化成的二叉树中树根结点的右子树上有（ ）个结点。 A. m1+m2 B. m2+m3 C. m3+m1 D. m1+m2+m3 二、简作题（每题10分，共50分） 如果一棵二叉树的前序遍历序列是A B C D E F G H，中序遍历序列为B C A E D G H F，试根据这两个序列的特点，恢复这棵二叉树，并给出它的后序遍历序列。已知如图所示的AOE网络，试求： 每项活动的最早可能开始时间Ae和最迟允许开始时间Al； 完成此工程最少需要多少单位时间； 关键活动和关键路径。 设散列(Hash)函数为Hash(key) = key % p，散列表地址空间为0～12，若采用线性探查法解决冲突，则对于如下给定的关键码序列 { 19, 14, 23, 01, 68, 21, 84, 38 }， 构造相应的散列表，并指出对每一个关键码进行查找时的关键码比较次数； 对于插入结束后的散列表，计算成功的和不成功的平均查找长度。 给定权值集合{15, 03, 14, 02, 06, 09, 16, 17}, 构造相应的Huffman树, 并计算它的带权路径长度WPL。要求在构造过程中每次构造新的二叉树时选择权值最小的结点作为左子女，权值次小的结点作为右子女。 (1) 下图是一棵3阶B树，试分别画出在插入65、15、40、30之后B树的变化。 (2) 下图是一个3阶B树。试分别画出在删除50、40之后B树的变化。（2分） 20分） 已知二叉树中的结点类型用BinTreeNode表示，被定义为 struct BinTreeNode { ElemType data; BinTreeNode *leftChild, *rightChild; }; 其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树的根结点。void BTC ( BinTreeNod