考试科目：数据结构与程序设计 说明：下列每道题10分，编程题可用任何一种编程语言编写
1、 叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。
179，208，93，306，55，859，984，9，271，33
2、 什么是哈夫曼树？试证明有n个叶子的哈夫曼树共有2n-1个结点。
3、 推导并求解n阶Hanoi塔问题至少执行move操作次数。
4、设有三对角矩阵（Aij）n×n，将其三对角线上元素逐行存于数组B［1..m］中，使B[k]=Aij
求： （1）用 i,j 表示k的下标变换公式
（2）用k表示i,j 的下标变换公式
5、输入下列整数序列，画出建立的二叉排序树，最后分别图示将其中50，86删除后的二叉排序树
86，50，78，59，90，64，55，23，100，40，80，45
6、设整数序列a1，a2，… ，an，给出求解最大值的递归程序。
7、编程求解无向图G的所有连通分量。
8、设有带头结点的单链表L，编程对表中任一值只保留一个结点，删除其余值相同的结点。
9、设T是一棵n元树，Tb是T的孩子兄弟表示（二叉链表）的二叉树，试编程由Tb计算T的高度。（要求用非递归方法实现）
10、设以整数序列a1，a2，a3，a4作为栈S的输入，利用push，pop操作，写出所有可能的输出，并编程实现算法。 |
