东北大学2000年数据结构试题
1 （20分）
简要回答下列问题
（注意：请将答案写在答题纸上，并注明题号）
① （3分）
内存中一片连续空间（不妨假设地址从1到m），提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。
②（5分）
假设字符a,b,c,d,e,f的使用频度分别是0.07,0.09,0.12,0.22,0.23,0.27，写出a,b,c,d,e,f的Huffman（哈夫曼）编码。
③（4分）
一棵共有n个结点的树，其中所有分枝结点的度均为k，求该树中叶子结点的子数。
④（4分）
图1表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。
⑤（4分）
在起泡（汽泡）排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，试举例说明之。快速排序过程中有没有这种现象？
2 （15分）
设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法,
① 找出最小值结点，且打印该数值；
② 若该数值是奇数，则将其与直接后继结点的数值交换；
③若该数值是偶数，则将其直接后继结点删除；
3 （14分）
解答下列问题,
① (4分）
将算术表达式 ((a+b)+c*(d+e)+f)*(g+h) 转化为二叉树；
② (10分）
假设一个仅包含二元运算符的算术表达式以二叉链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。
4（21）
解答下列问题,
① （5分）
画出有向图的十字链表存储结构中头结点和表结点的结点结构。
② (4分）
下面哪一个方法可以判断出一个有向图中是否有环（回路）？
(1)深度优先遍历 (2)拓朴排序 (3)求最短路径 (4)求关键路径
③(12分）
假设一个有向图g已经以十字链表形式存储在内中，试写一个判断该有向图中是否有环（回路）的算法。
5（15分）
写出删除二叉排序树bt中值为x的结点的算法（二叉排序树以二叉链表形式存储，删除后仍然保持二叉排序性质）。
6（15分）
设有大小不等的n个数据组（n个数据组中数据的总数为m），顺序存放在空间区D内，每个数据占一个存储单元，数据组的首地址由数组s给出（如下图所示），试编写将新数据x插入到第i个数据组的末尾且属于第i个数据组的算法，插入后，空间区D和数组S的相互关系仍保持正确。
1 （20分）
简要回答下列问题
（注意：请将答案写在答题纸上，并注明题号）
① （3分）
内存中一片连续空间（不妨假设地址从1到m），提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。
②（5分）
假设字符a,b,c,d,e,f的使用频度分别是0.07,0.09,0.12,0.22,0.23,0.27，写出a,b,c,d,e,f的Huffman（哈夫曼）编码。
③（4分）
一棵共有n个结点的树，其中所有分枝结点的度均为k，求该树中叶子结点的子数。
④（4分）
图1表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。
⑤（4分）
在起泡（汽泡）排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，试举例说明之。快速排序过程中有没有这种现象？
2 （15分）
设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法,
① 找出最小值结点，且打印该数值；
② 若该数值是奇数，则将其与直接后继结点的数值交换；
③若该数值是偶数，则将其直接后继结点删除；
3 （14分）
解答下列问题,
① (4分）
将算术表达式 ((a+b)+c*(d+e)+f)*(g+h) 转化为二叉树；
② (10分）
假设一个仅包含二元运算符的算术表达式以二叉链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。
4（21）
解答下列问题,
① （5分）
画出有向图的十字链表存储结构中头结点和表结点的结点结构。
② (4分）
下面哪一个方法可以判断出一个有向图中是否有环（回路）？
(1)深度优先遍历 (2)拓朴排序 (3)求最短路径 (4)求关键路径
③(12分）
假设一个有向图g已经以十字链表形式存储在内中，试写一个判断该有向图中是否有环（回路）的算法。
5（15分）
写出删除二叉排序树bt中值为x的结点的算法（二叉排序树以二叉链表形式存储，删除后仍然保持二叉排序性质）。
6（15分）
设有大小不等的n个数据组（n个数据组中数据的总数为m），顺序存放在空间区D内，每个数据占一个存储单元，数据组的首地址由数组s给出（如下图所示），试编写将新数据x插入到第i个数据组的末尾且属于第i个数据组的算法，插入后，空间区D和数组S的相互关系仍保持正确。
