南京航天航空大学2001年数据结构与程序设计专业课考研真题试卷 一、根据下图所示广义表的存储结构，写出此图表示的广义表。 二、试找出分别满足下列条件的所有二叉树 （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个顶点的有向图用邻接矩阵表示，编写函数，计算每对顶点之间的最短路径。 十、编程，判断一棵用二叉链表表示的二叉树是否是完全二叉树。 本文来源：https://www.wddqw.com/doc/054344ed12a6f524ccbff121dd36a32d7275c7cf.html