A.45312B42531C.45213D42315 14.AVL树是一种平衡的二叉排序树,树中任一结点的( A.左右子树的高度均相同 B左右子树高度差的绝对值不超过1 C左子树的高度均大于右子树的高度D左子树的高度均小于右子树的高度 15.在ⅤSAM文件的控制区间中,记录的存储方式为() A.无序顺序B有序顺序C.无序链接D.有序链接 第二部分非选择题(共70分) 二填空题(本大题共10小题,每小题2分,若有两个空格,每个空格1分,共20分)不写解答过程, 将正确的答案写在每小题的空格内。错填或不填均无分。 16.若一个算法中的语句频度之和为T(n)=3720n+4 nlogn,则算法的时间复杂度为 17.。在如图所示的链表中,若在指针p所指的结点之后插入数据域值相继为a和b的两个结点,则可用下 列两个语句实现该操作,它们依次是 b 题17图 18.假设以S和X分别表示进栈和退栈操作,则对输入序列ab,cd,e进行一系列栈操作 SSXSXSSXXX之 得到的输出序列为 19.串S=“ I am a worker”的长度是 20.假设一个10阶的下三角矩阵A按列优先顺序压缩存储在一维数组C中,则C数组的大小应 为 21.在n个结点的线索二叉链表中,有 个线索指针 22.若采用邻接矩阵结构存储具有n个顶点的图,则对该图进行广度优先遍历的算法时间复杂度 为 23.对关键字序列(52,80,63,44,48,91)进行一趟快速排序之后得到的结果为 24.由10000个结点构成的二叉排序树,在等概率查找的假设下,查找成功时的平均查找长度的最大值可 能达到 25.若要找出所有工资低于1500元,职称是副教授,及所有工资低于2000元,职称是教授的记录,则查 询条件是 三解答题(本大题共4小题,每小题5分,共20分) 26.已知一个6行5列的稀疏矩阵中非零元的值分别为:-90,41,-76,28,-54,65和-8,它们在矩阵中 的列号依次为:1,4,5,1,2,4和5。当以带行表的三元组表作存储结构时,其行表 RowTab中的值依 次为0,0,2,2,3和5。请写出该稀疏矩阵(注:矩阵元素的行列下标均从1开始) 27.已知树T的先序遍历序列为 ABCDEFGHUKL后序遍历序列为 CBEFDJIKLHGA。请画出树T。 28.对关键字序列(72,87,61,23,94,16,05,58)进行堆排序,使之按关键字递减次序排列。请写 出排序过程中得到的初始堆和前三趟的序列状态 初始堆 第1趟: 第2趟: 第3趟A.4 5 3 1 2 B.4 2 5 3 1 C.4 5 2 1 3 D.4 2 3 1 5 14. AVL 树是一种平衡的二叉排序树，树中任一结点的（ ） A.左.右子树的高度均相同 B.左.右子树高度差的绝对值不超过 1 C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度 15. 在 VSAM 文件的控制区间中，记录的存储方式为（ ） A.无序顺序 B.有序顺序 C.无序链接 D.有序链接 第二部分 非选择题（共 70 分） 二.填空题（本大题共 10 小题，每小题 2 分，若有两个空格，每个空格 1 分，共 20 分）不写解答过程， 将正确的答案写在每小题的空格内。错填或不填均无分。 16. 若一个算法中的语句频度之和为 T(n)=3720n+4nlogn，则算法的时间复杂度为 。 17. 在如图所示的链表中，若在指针 p 所指的结点之后插入数据域值相继为 a 和 b 的两个结点，则可用下 列两个语句实现该操作，它们依次是 和 。 题 17 图 18. 假设以 S 和 X 分别表示进栈和退栈操作，则对输入序列 a,b,c,d,e 进行一系列栈操作 SSXSXSSXXX 之 后，得到的输出序列为 。 19. 串 S=“I am a worker”的长度是 。 20. 假设一个 10 阶的下三角矩阵 A 按列优先顺序压缩存储在一维数组 C 中，则 C 数组的大小应 为 。 21. 在 n 个结点的线索二叉链表中，有 个线索指针。 22. 若采用邻接矩阵结构存储具有 n 个顶点的图，则对该图进行广度优先遍历的算法时间复杂度 为 。 23. 对关键字序列（52，80，63，44，48，91）进行一趟快速排序之后得到的结果为 。 24. 由 10000 个结点构成的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度的最大值可 能达到 。 25. 若要找出所有工资低于 1500 元，职称是副教授，及所有工资低于 2000 元，职称是教授的记录，则查 询条件是 。 三.解答题（本大题共 4 小题，每小题 5 分，共 20 分） 26. 已知一个 6 行 5 列的稀疏矩阵中非零元的值分别为：-90，41，-76，28，-54，65 和-8，它们在矩阵中 的列号依次为：1，4，5，1，2，4 和 5。当以带行表的三元组表作存储结构时，其行表 RowTab 中的值依 次为 0，0，2，2，3 和 5。请写出该稀疏矩阵（注：矩阵元素的行列下标均从 1 开始）。 27. 已知树 T 的先序遍历序列为 ABCDEFGHIJKL 后序遍历序列为 CBEFDJIKLHGA。请画出树 T。 28. 对关键字序列（72，87，61，23，94，16，05，58）进行堆排序，使之按关键字递减次序排列。请写 出排序过程中得到的初始堆和前三趟的序列状态。 初始堆： 第 1 趟： 第 2 趟： 第 3 趟： a b p s Λ