南京航空航天大学2001年数据结构与程序设计试题
考试科目：数据结构与程序设计 说明：下列每道题10分，编程题可用任何一种编程语言编写
一、根据下图所示广义表的存储结构，写出此图表示的广义表。
二、试找出分别满足下列条件的所有二叉树
（1）先序序列和中序序列相同
（2）中序序列和后序序列相同
（3）先序序列和后序序列相同
三、根据下图所示的一棵3阶B树（有些教材中称为B-树）
（）分别给出插入关键字2，12，16，17和18之后的结果。
（）分别给出在原图上删除8和9之后的结果。
四、对下图所示的有向图
（1）画出它的邻接表示意图
（2）根据邻接表写出其拓扑排序序列
五、用栈实现将中缀表达式8-（3+5）*（5-6/2）转换成后缀表达式，画出栈的变化过程。
六、已知两个链表A和B分别表示两个集合，其元素递增排列。编一函数，求A与B的交集，并存放于A链表中。
七、已知一棵二叉树用二叉链表存储，编写递归函数，判断其是否是平衡二叉树。
八、编写程序将一整数序列中所有负数移到所有正数之前，要求时间复杂度为O（n）
九、已知n个顶点的有向图用邻接矩阵表示，编写函数，计算每对顶点之间的最短路径。
十、编程，判断一棵用二叉链表表示的二叉树是否是完全二叉树。