当前位置：问答库＞考研试题

南京航空航天大学 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 个顶点的有向图用邻接矩阵表示，编写函数，计算每对顶点之间的最短路径。 十、编程，判断一棵用二叉链表表示的二叉树是否是完全二叉树。