北京工业大学 北工大 1999年数据结构 考研真题及答案解析.pdf

布丁考研网，在读学长提供高参考价值的复习资料 北京工业大学 1999 年硕士研究生入学考试试题 考试科目：数据结构 一、（26 分）填空、选择（一个或多个）题，1-6 题每小题 2 分： 1 下面的叙述中，不正确的是（ ） A 关键活动不按期完成就会影响整个工程的完工时间。 B 任何一个关键工程提前完成，将使整个工程提前完成。 C 所有关键活动都提前完成，则使整个工程提前完成。 D 提些关键活动若提前完成，则将使整个工程提前完成。 2 下面的排序算法中，不稳定得是（ ） A 起泡排序 B 折半插入排序 C 简单选择排序 D 希尔排序 E 基数排序 F 堆排序。 3 包含结点 A ，B ，C 的二叉树有种不同的状态，种不同的二叉树。 4 包含结点 A ，B ，C 的树有种不同形态，种不同的树。 5 分块检索中，若索引表和各块内存均用顺序查找，则有 900 各元素的线性表分成块最好： 若分成 25 块；其平均查找长度为 。 6 下面的程序段中，对ｘ的赋值语句的频度为 （表示为n 的函数） ＦＯＲ Ｉ：＝ １ＴＯ Ｎ ＤＯ ＦＯＲ Ｊ：＝１ ＴＯＩ ＤＯ ＦＯＲ Ｋ：＝Ｉ ＴＯ Ｊ ＤＯ ｘ：＝ｘ＋ＤＥＬＴＡ； ７（８分）设有字符序列Ｑ Ｈ Ｃ Ｙ Ｐ Ａ Ｍ Ｓ Ｒ Ｄ Ｆ Ｘ要求按字符升 列排序： 采用初是长为４的希尔（３ｂｅｌｌ）排序，一趟扫描的结果是――――――――― 采用以元素为分界元素的快速排序，一躺扫描的结果是 。 6 分）已知广义表：A- （0 ），B- （），C- （a，b ，c，d ），D- （A ，B ，C ）它们的存储结构 8 （ 图为（接两种结构种的任一种即可）： 1 布丁考研网，在读学长提供高参考价值的复习资料 二（6 分）编写递归程序将二叉树逆时针旋转 90 度打印出来。如右图：（要求用类PASCAL 语 言，并描述结构）。 三 （8 分）用依次输入的关键字 13，29 ，41 ，19，5，1，7 和 6 建一棵三阶 B-树， 1 2 5 画出建该树的变化过程示意图（每插入一个结点至少用一张图）。 1 3 8 1 4 3 四（共20 分）已知顶点 1——6 和输入边与权值的序列（如右框中）： 2 4 6 每行三个数表示一条边的两个端点和其权值，共 11 行。 2 3 2 请你： 3 4 4 8 分）采用邻接多重表表示该无向网，用类 PASCAL 语言描述该数据结构，画出 1 （ 3 5 1 存储结构示意图，要求符和在边结点链表头部插入的算法和输入序列的次序。 3 6 10 4 分）分别写出从顶点 1 出发的深度优先和广度优先遍历顶点 序列，以及相 2 （ 4 5 7 应的生成树。