crazyphone

南京航空航天大学2002年数据结构与程序设计考研试题
一、将下列稀疏矩阵的非零元素表示成三元组的形式和十字链表的形式。


二、设一棵二叉树的层次遍历序列为ABDEGHJK，中序遍历序列为GDJHKBEA。
（1）画出这棵二叉树示意图
（2）说明建立这棵二叉树的原理
三、回答下列B树（有些教材中称为B-树）问题:
（1）一棵4阶4层（根为第一层，叶子为第二层）的B树，至少有多少关键字，至多有多少关键字
（2）在含有n个关键字的m阶B树中进行查找时，最多访问多少个结点。
四、哈希表中使用哈希函数H（key）=3 * key % 11,并采用开放定址法处理冲突，随机探测再散列的下一地址公式为:
   d1=H (key )
di=( di-1 +7 * key ) % 11 （I=2,3…..）
试在0到10的散列地址空间中对关键字序列（22，41，53，46，30，13，01，67）画出Hash表示意图，并求在等概率情况下查找成功的平均查找长度。
五、求出一棵滿k叉树的叶子结点数n和所有非叶子结点数m之间的关系，给出求解过程。
六、已知两个链表A和B，其元素值递增排列。编程，将A和B合并成一个递减有序（相同值只保留一个）的链表C，并要求利用原表结点。
七、已知一棵二叉树用二叉链表存储，root 指向根结点，p指向树中任一结点。编程，输出从root 到p 之间路径上的结点。
八、已知一棵树用孩子－兄弟链表存储。编程，计算该树的叶子数。
九、设有n 个整数组成的序列，每个整数为－1，0，1之一。编写一个时间复杂度为O（n）的算法，使该序列按负数、零、正数的次序排好。
十、已知n个顶点的带权图用邻接矩阵表示，编写函数，实现用Kruskal算法构造最小生成树，要求对函数中所使用的变量和内容做详细的注释说明。

南京航空航天大学2000年数据结构与程序设计考研试题
考试科目:数据结构与程序设计
说明:下列每道题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操作，写出所有可能的输出，并编程实现算法。