北京工业大学 北工大 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的树有------种不同形态，------种不同的树。

若索引表和各块内存均用顺序查找，则有900各元素的线性表分成-----块最好：5分块检索中，

若分成25块；其平均查找长度为--------。

6下面的程序段中，对ｘ的赋值语句的频度为------------（表示为n的函数） ＦＯＲ Ｉ：＝ １ＴＯ Ｎ ＤＯ ＦＯＲ Ｊ：＝１ ＴＯＩ ＤＯ

ＦＯＲ Ｋ：＝Ｉ ＴＯ Ｊ ＤＯ ｘ：＝ｘ＋ＤＥＬＴＡ； ７（８分）设有字符序列Ｑ Ｈ Ｃ Ｙ Ｐ Ａ Ｍ Ｓ Ｒ Ｄ Ｆ Ｘ要求按字符升列排序：

采用初是长为４的希尔（３ｂｅｌｌ）排序，一趟扫描的结果是――――――――― 采用以元素为分界元素的快速排序，一躺扫描的结果是------------。

，B-（），C-（a，b，c，d），D-（A，B，C）它们的存储结构8（6分）已知广义表：A-（0）图为（接两种结构种的任一种即可）：

1

布丁考研网，在读学长提供高参考价值的复习资料 www.ibudding.cn

（要求用类PASCAL语二（6分）编写递归程序将二叉树逆时针旋转90度打印出来。如右图：言，并描述结构）。

三 （8分）用依次输入的关键字13，29，41，19，5，1，7和6建一棵三阶B-树，画出建该树的变化过程示意图（每插入一个结点至少用一张图）。

1 2 5 1 3 8 1 4 3

： 2 4 6 四（共20分）已知顶点1——6和输入边与权值的序列（如右框中）

每行三个数表示一条边的两个端点和其权值，共11行。 2 3 2 请你： 3 4 4 1（8分）采用邻接多重表表示该无向网，用类PASCAL 语言描述该数据结构，画出

3 5 1

存储结构示意图，要求符和在边结点链表头部插入的算法和输入序列的次序。 3 6 10 2（4分）分别写出从顶点1出发的深度优先和广度优先遍历顶点 序列，以及相 4 5 7 应的生成树。

4 6 11

3（8分）按PRIM算法列表计算，从顶点1始求最小生成树，并图示该树。 5 6 15

五（12分）下面函数的功能是在一个按访问频度不增有序的，带头结点的双向链 环上检索关键值为x的结点，对该结点访问频度计数，并维护该链环有序。若为找到，则插入该结点。所有结点的频度域初值在建表时都为零。请将程序中四处空缺补写完整。 TYPE

Link=node

2

布丁考研网，在读学长提供高参考价值的复习资料 www.ibudding.cnNode=record Key:char; Freq:integer; Pre,next:link; End; VAR l:link;

Function loc(l:link;x:char):link; VAR p,q:link; Begin

p:=l^.next;

While p^.key<>x 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^.freq>p^.pre^.freq do p:=p^.pre; if p<>q 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

布丁考研网，在读学长提供高参考价值的复习资料 www.ibudding.cn43该图示这些磁盘文件进行归并所用的4阶最佳归并树，算出归并的总读写字节段，每读写1字节计为1。

七（10分）树形选择排序通常采用顺序存储结构（1）试指出n个元素的原始序列一般如何在该存储结构中存数（起始存储位置，次序），请说明理由。（2）讨论树形选择排序的稳定性。若稳定，须说明理由；不稳定，须举反例，并尝试找出使它稳定的方法。

八（10分）已知一棵以线索链表为存储结构的中序全线索二叉树t，试在该二叉树上求任意结

点X的前序前趋。叙述思路并编写算法，所用数据解构描述如下： TYPE

Link=^node; Node =record Key:elemty; L,r:link; Ltag,rgag:0..1 End; VAR t:link

4