天津大学试卷专用纸 学院 专业 年级 学号 姓名 共4页第1页 2005~2006学年第2学期期末考试试卷 3.(10分、每小题5分)散列表的地址区间为0~16,散列函数为H(k)=k%17,采 《数据结构》(B卷共4页) 用线性探测法处理冲突,并将关键字序列26,25,72,38,8,18,59依次储存到 (考试时间:2006年6月21日) 了散列表中 (1)、元素59存放在散列表中的地址是多少? “下凹 、搜索元索素39需要比较的次数是多少? 实做题(共计65分) (10分、每小题5分)已知一个中缀算术表达式: 3+4/(25-(6+15)*8 (1)、写出对应的后缀算术表达式 (2)、画出在转换成后缀表达式的过程中运算符栈的变化 注意 4.(10分)设有一个关键码的输入序列{55,31,11,37,46,73,63,02 07},从空树开始构造平衡二叉搜索树,画出每加入一个新结点时二叉树的形态。 若发生不平衡,指明需做的平衡旋转的类型,并给出平衡旋转的结果 (10分)假定有四个元素A、B、C、D按所列次序进栈,试写出所有可能的出栈序列 注意:每一个元素进栈后都允许出栈,如ACDB就是一种出栈序列
天津大学试卷专用纸 学院 专业 班 年级 学号 姓名 共 4 页 第 1 页 2005 ～2006 学年第 2 学期期末考试试卷 《 数据结构 》（B 卷 共 4 页） （考试时间：2006 年 6 月 21 日） 题号 一 二 三 四 五 六 七 八 成绩 核分人签字 得分 一．实做题（共计 65 分） 1. （10 分、每小题 5 分）已知一个中缀算术表达式： 3+4/(25-(6+15))*8@ ⑴、写出对应的后缀算术表达式 ⑵、画出在转换成后缀表达式的过程中运算符栈的变化 注意： “@“为结束符 2. （10 分）假定有四个元素 A、B、C、D 按所列次序进栈，试写出所有可能的出栈序列。 注意：每一个元素进栈后都允许出栈，如 ACDB 就是一种出栈序列。 3. （10 分、每小题 5 分）散列表的地址区间为 0～16，散列函数为 H ( ) = %17 ，采 用线性探测法处理冲突，并将关键字序列 26，25，72，38，8，18，59 依次储存到 了散列表中。 ⑴、元素 59 存放在散列表中的地址是多少？ ⑵、搜索元素 39 需要比较的次数是多少？ 4. （10 分）设有一个关键码的输入序列{ 55， 31， 11， 37， 46， 73， 63， 02， 07} ，从空树开始构造平衡二叉搜索树，画出每加入一个新结点时二叉树的形态。 若发生不平衡，指明需做的平衡旋转的类型，并给出平衡旋转的结果
天津大学试卷专用纸 学院 专业 年级 学号 姓名 共4页第2页 (10分)已知一个无向图,要求用Pim算法生成最小生成树(假设以1为起点,画6.(10分、每小题5分)已知有向图的邻接矩阵如下所示,该有向图的顶点分别为 有向图的邻接矩阵为 A B CDE FG H I 0000000
天津大学试卷专用纸 学院 专业 班 年级 学号 姓名 共 4 页 第 2 页 5. （10 分）已知一个无向图，要求用 Prim 算法生成最小生成树（假设以 1 为起点，画 出构造过程）。 6. （10 分、每小题 5 分）已知有向图的邻接矩阵如下所示，该有向图的顶点分别为 A,B,C,D,E,F,G,H,I， (1) 根据邻接矩阵画出该图。 (2) 对该图进行拓扑排序，并给出三种排序结果。 有向图的邻接矩阵为 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 000000001 000000001 000000000 000000000 A B C D E F G H I A B C D E F G H I
天津大学试卷专用纸 学院 专业 年级 学号 姓名 共4页第3页 (5分)已知树的广义表表示如下T=(A(B(E(K,L)C(G,D(H(M)1,J)),画出该 广义表的链表存储结构。(给出一种方法) 2.(5分)试设计算法,统计一个采用邻接表存储、具有n个顶点的有向无权图所有顶 点的入度 、算法设计共计35分) (10分)试编写快速排序中一趟排序的算法
天津大学试卷专用纸 学院 专业 班 年级 学号 姓名 共 4 页 第 3 页 7. （5 分）已知树的广义表表示如下 T＝（A(B(E(K , L)), C(G), D(H(M), I, J ))）,画出该 广义表的链表存储结构。（给出一种方法） 二、算法设计(共计 35 分) 1. （10 分） 试编写快速排序中一趟排序的算法。 2. （5 分）试设计算法，统计一个采用邻接表存储、具有 n 个顶点的有向无权图所有顶 点的入度
天津大学试卷专用纸 学院 专业 年级 学号 姓名 共4页第4页 (10分)试给出中序遍历二叉树的算法(要求写出非递归的算法) 4.(10分、每小题5分)试设计算法,n为大于等于0的整数 (1)给出函数的递归算法 (2)用堆栈设计函数的非递归算法 m n*P(n2)n>0
天津大学试卷专用纸 学院 专业 班 年级 学号 姓名 共 4 页 第 4 页 3. （10 分）试给出中序遍历二叉树的算法（要求写出非递归的算法） 4. （10 分、每小题 5 分）试设计算法，n 为大于等于 0 的整数， （1）给出函数的递归算法 （2）用堆栈设计函数的非递归算法 1 n=0 P(n)= n * P(n/2) n>0