北京科技大学计算机研究生入学考试2002-2007真题答案

2002年，北京科技大学招收硕士研究生入学考试。

考试科目:数据结构

适用专业:计算机应用技术、计算机软件与理论系统工程、计算机系统结构

注意:所有考生做1-7题，单人考生做1、2、3、5、6、8、9题。请务必在答题卡上写下所有问题的答案。

一、(20分)回答下列问题:

1.计算机内存中映射(或表示)数据逻辑结构的常用方法有哪些？

2.请简述算法的确定性的含义。

3.线性结构和树形结构各有什么特点？

4.设单链表中节点的数据字段为data，指针字段为next，指针p为表中节点的地址。请写出在P节点前插入一个S节点的C语言描述语句。

5.请简要描述两个在你的算法设计中使用堆栈和队列的例子。

6.设一棵三叉树的叶节点数为n0，度为2和3的节点数分别为n2和n3，试给出n0与n2和n3的关系。

7.构造无向连通网络最小生成树的两种典型算法是什么？

8.在存在n (n >: =0)的情况下，当使用关键字在M阶B树上搜索时，搜索路径中涉及多少个节点？

9.请指出三种稳定和三种不稳定的内部排序方法。

10.哪个三级索引顺序用于检索ISAM文件？VSAM档案由哪三部分组成？

二、(10分)算法填空:

求霍夫曼树的加权路径长度(WPL)的算法如下，其中ht是根节点的指针，S是工作栈，Clearstack(S)，Push(S，P)，Pos(S)和Emptystack(S)分别是stack empty，指针P进入、退出和判断stack empty的函数。请填写算法中带下划线的空格以完成其功能。

三。(10分)

我们假设某单位员工的工资总额ST由“工资”、“扣款”、“实缴额”三项组成，其中工资项包括“基本工资”、“津贴”、“奖金”，扣款项包括“水”、“电”、“气”费用。

1.请使用以概化表形式描述的工资表ST，使用GetHead(ST)和GetTail(ST)函数提取表中的奖金项目；

2.用C语言描述广义表中的元素结构，并画出工资表的存储结构。

四。(10分给考生)

如下设置二叉树BT:

1.请画出这个二叉树BT的“顺序”和“二叉链表”存储结构；

2.用“前序”、“中序”、“后序”的方法写出遍历二叉树BT得到的结果序列，画出BT的后序线索二叉树。

五、(15分)

设无向网络G的邻接矩阵A如下:

1.请根据给定的邻接矩阵A画出网G的逻辑结构(G中的顶点用v1~v8表示)；

2.根据“深度优先”和“广度优先”的搜索方法，写出从顶点v1开始遍历网G得到的顶点序列；

3.从顶点v1开始，根据求最小生成树的Prim算法，画出网G的最小生成树。

六、(15分)

设关键记录集为k = {26，36，41，44，15，68，12，6，51，25}。

1.构建以K为权重集的霍夫曼树；依次取k中的值，构造二叉排序树；

2.设哈希表的表长为m=16，选择哈希函数的方法为H(key)=key%13，处理冲突的方法为“二次探查再哈希”。请依次取k中的值，构造满足给定条件的哈希表结构；

3.以K中的第一个关键字(26)为支点，用“快速排序”法对K进行排序时，将结果写在第一次排序的末尾，将K调整为顶部元素最大值的堆。

七、(此题20分)

算法设计:

1.设L为单向循环链表第一个节点的指针(无前导节点)，节点号为1，2，...，n，链表中的数字是K (1

2.有n个顶点的有向图G已经存储在邻接表结构中，顶点表指针为G，图中每个顶点的渗透度已经记录在该顶点的id字段中(即G->；数据[ i ]。id=第一个I (1

八、(本问卷10分)

设森林F={T1，T2，T3}如下:

1.如果这个森林F是用“孩子的兄弟表示法”存储的，请画出它的存储结构；

2.用“前序”和“中序”的方法写出遍历森林F得到的结果序列。

九、(本问卷20分)