天津大学试卷专用纸 学院 专业 年级 学号 姓名 共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} ，从空树开始构造平衡二叉搜索树，画出每加入一个新结点时二叉树的形态。 若发生不平衡，指明需做的平衡旋转的类型，并给出平衡旋转的结果