考试科目:数据结构与程序设计 说明:下列每道题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操作,写出所有可能的输出,并编程实现算法。