数据结构与操作系统 Z 试卷 《数据结构》部分 （90 分） 一、简答题（20 分，每题 5 分） 1、请给出四种数据结构基本类型。 2、简述栈和队列的区别。 3、什么是关键路径？ 4、插入类排序有哪几种？其中，哪些是不稳定的排序算法？ 二、应用题（40 分） 1、如果进栈的序列是 12345，请给出所有 3、4 先出栈的序列（3 在 4 之前出栈）。（5 分） 2、给出先缀表达式“- + a * b – c d / e f”对应的后缀式，画出其相 应的二叉树，并画出该二叉树的中序线索树。（10 分） 3、某带权有向图及它的邻接表如下图所示，试写出它的广度优先 搜索序列，并根据克鲁斯卡尔算法，求它的最小生成树。（10 分） 4、请写出应填入下列叙述中（ ）内的正确答案。排序有各种方 法，如插入排序、快速排序、堆排序、冒泡排序等。设一数组中原有 数据如下：15，13，20，18，12，60。下面是一组由不同排序方法进 行一遍排序后的结果。（15 分） （①）排序的结果为：12，13，15，18，20，60 （②）排序的结果为：13，15，18，12，20，60 A B C ^ B C D E F G H D E ^ F ^ C F G ^ E H ^ G ^ H G ^ ^ B C E A G D F H 2 3 3 5 1 2 3 4 6 5 2 6
您现在的位置： 
