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