北京工业大学考研真题数据结构1999

1、1 北京工业大学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 的树有

2、- 种不同形态，- 种不同的树。5 分块检索中， 若索引表和各块内存均用顺序查找，则有 900 各元素的线性表分成- 块最好：若分成 25 块；其平均查找长度为- 。6 下面的程序段中，对的赋值语句的频度为- （表示为n 的函数） ： ： ： ：；（分）设有字符序列 要求按字符升列排序：采用初是长为的希尔（）排序，一趟扫描的结果是 采用以元素为分界元素的快速排序，一躺扫描的结果是- 。8（6 分）已知广义表：a-（0） ，b-（） ， c-（a，b，c，d） ，d-（a，b，c）它们的存储结构图为（接两种结构种的任一种即可）：二（ 6 分）编写递归程序将二叉树逆时针旋转90 度打印出来。如右图

3、： （要求用类pascal 语言，并描述结构） 。2 三 （8 分）用依次输入的关键字13，29，41，19，5，1，7 和 6 建一棵三阶b-树，画出建该树的变化过程示意图（每插入一个结点至少用一张图）。四（共 20 分）已知顶点1 6 和输入边与权值的序列（如右框中）：2 4 6 每行三个数表示一条边的两个端点和其权值，共11 行。2 3 2 请你：1（8 分）采用邻接多重表表示该无向网，用类pascal 语言描述该数据结构，画出存储结构示意图，要求符和在边结点链表头部插入的算法和输入序列的次序。3 4 4 3 6 10 2（4 分）分别写出从顶点1 出发的深度优先和广度优先遍历顶点序列，

4、以及相应的生成树。4 5 7 3（8 分）按 prim 算法列表计算，从顶点1 始求最小生成树，并图示该树。5 6 151 2 5 1 3 8 1 4 3 3 5 1 4 6 11 五（ 12 分）下面函数的功能是在一个按访问频度不增有序的，带头结点的双向链环上检索关键值为x 的结点，对该结点访问频度计数，并维护该链环有序。若为找到，则插入该结点。所有结点的频度域初值在建表时都为零。请将程序中四处空缺补写完整。type link=node node=record key:char; freq:integer; pre,next:link; end; var l:link; function l

5、oc(l:link;x:char):link; var p,q:link; begin p:=l.next; while p.keyx do p:=p.next; if p=1 then new(q);q.key:=x;q.freq:=0 else p.freq:=p.freq+1;q:=p; while q.freqp.pre.freq do p:=p.pre; if pq then if then q.next:=p,q.pre;=p.pre;p.pre.next:=q; p.pre:=q retuen(q); end; 六（ 8 分）置换选择排序得到初始归并段长（k 个节数）为37，34，300，41，70，120， 35，3 4 43 该图示这些磁盘文件进行归并所用的4 阶最佳归并树，算出归并的总读写字节段，每读写1 字节计为1。七（ 10 分）树形选择排序通常采用顺序存储结构（1）试指出n 个元素的原始序列一般如何在该存储结构中存数（起始存储位置，次序），请说明理由。 （2）讨论树形选择排序的稳定性。若稳定，须说明理由；不稳定，须举反例，并尝试找出使它稳定的方法。八（ 10 分）已知一棵以线索链表为存储结构的中序全线索二叉树t，试在该二叉树上求任意结点 x 的前序前趋。叙述思路并编写算法