2011年浙江工业大学数据结构一、简答题1、简要阐述下列5个术语的基本含义：数据、数据元素、数据结构、存储结构、抽象数据类型。（本题10分）2、数据存储结构和链式存储结构是数据结构中常用的存储方式，试比较这两种存储方式的优缺点并写出在什么情况下采用顺序表比链式表更合适？（本题10分）3、阅读下列函数，回答相关问题：I
tarra
gei
tai
tLi
tHi
txL和H分别为数据区的上届和下届I
ti，j，t；iLJHwhilijwhileijajxjwhileijaixiifijtajajaiaitIfaixretur
iElseretur
i1；（1）写出该函数的功能；（2）写一个调用上述函数实现下列功能的算法：对一整型数组b
中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。（本题10分）4、假设有一个适当大小的栈S，输入栈的序列为A、B、C、D、E。回答下列问题：（1）下列三种输入序列是否都能得到？①B，C，E，A；②E，A，B，C，D；③E，D，C，B，A；（2）对可能的输入序列给出产生该输出序列，所必要的运算序列（用栈的基本运算符给出）。5、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分为别007，019，002，006，032，003，021，010。试为这8个字母设计哈弗曼编码（左结点值小于右结点值，左分支编码0，右分支编码1）。使用07的二进制表形式是另一种编码方案。试比较两种方案的优缺点。（本题10分）6、已知一颗二叉树的中序遍历结果为：DBFEAGHCI后序遍历结果为：DEFBHGICA。回答下列问题：（1）画出这棵二叉树，并写出它的前序遍历结果；（2）将这颗二叉树转换成等价的森林。（10分）7、一个深度为H的满M叉树有以下性质：第H层上的结点都是叶子节点，其余各层上每个节点都有M棵非空子树，如果按层次顺序从1开始对全部节点进行编号，求：（1）各层的结点数的数目是多少？（2）编号为
的结点的双亲结点（若存在）的编号是什么？（3）编号为
的结点的第i个孩子结点（若存在）的编号是多少？（4）编号为
的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是什么？（本题10分）8、8、用弗洛伊德算法（Flory算法）计算图1中任意两点之间的最短路径，要求写出该计算过程的主要步骤。（本题10分）
9、设一组关键字为（7152031485364768299），Hash函数Hkeykey11，Hash表表长m11，用线性探测法解决冲突，试构造Hashr