南京航空航天96考研题
说明：算法可以用任一种高级语言编写。
六、是非题（对者打对号，错者打错号）（10分）
1． 循环队列通常用指针来实现队列的头，尾相接。
2． 广义表的取表尾运算，其结果通常是个表，但有时也可是单元素值。
3． 完全二叉树的存储结构通常采用顺序存储结构。 n
4． 对有n个顶点的无向图，其边数e与各顶点度数间满足下列等式e=ΣTD（Vi）；
i=1
5． 完全二叉树肯定是平衡二叉树。
6． 堆是满二叉树。
7． 带权无向图的最小生成树必是唯一的。
8． 需要借助于一个队列来实现DFS算法。
9． 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。
10 Hash表与hash文件的唯一区别是hash文件引入了‘桶‘的概念。
七 对如下的树，画出三种不同的存储结够图。（6分）
八、 对下图分别按prim算法和
kruskal算法求出最小生成树。（请画
出构造步骤）(6分)
九、 简要回答下列问题。
1. 设要求从大到小排序。问在
什么情况下冒泡排序算法关
键字交换的次数
为最大。（4分）
2．如何衡量hash函数的优劣？简要叙述hash表技术中的冲突概念，并指出
三种解决冲突的方法。（6分）
十 、 如下的算法分别是后序线索二叉树求给定的结点的超前结点与后继结点的
1 left 指向其右孩子
rfalg= 0 right 指向其右孩子
1 right 指向其后继
该算法分别用类pascal语言和类C语实现，该生只要选做其中之一即可。
（8分）
用类 pascal 实现的算法
procedure prior (node,x)
begin
if node ≠ ∧ then
if
then
else end;
procedure next(bt, node, x)
begin （bt 是二叉树的树根）
if if node^.rfalg=1
then
else [repeat
T=x;
until x=node;
x=T;
]
end;
类C语言实现的算法
prior (node,x)
{
if (node !=null)
if ( * x=node else
*x=node left
}
next (bt, node, x) ( bt是二叉树的树根)
{ if (node rfalg)
else do
t = * x ;
While * x=T;
}
}
十一、 （统考生作）
设有两个从小到大排序的带头结点的有序链表。试编写求这两个链表交运算的 算法（即L1∩L2）。要求结果链表仍是从小到大排序，但无重复元素。 （10分）
十二 （单独命题考生做）
设无向图G有n个顶点，m条边。试遍写用邻接表存储该图的算发。（10分） （设顶点值用1～n或0～n-1编号）
南京航空航天96考研题
说明：算法可以用任一种高级语言编写。
六、是非题（对者打对号，错者打错号）（10分）
1． 循环队列通常用指针来实现队列的头，尾相接。
2． 广义表的取表尾运算，其结果通常是个表，但有时也可是单元素值。
3． 完全二叉树的存储结构通常采用顺序存储结构。 n
4． 对有n个顶点的无向图，其边数e与各顶点度数间满足下列等式e=ΣTD（Vi）；
i=1
5． 完全二叉树肯定是平衡二叉树。
6． 堆是满二叉树。
7． 带权无向图的最小生成树必是唯一的。
8． 需要借助于一个队列来实现DFS算法。
9． 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。
10 Hash表与hash文件的唯一区别是hash文件引入了‘桶‘的概念。
七 对如下的树，画出三种不同的存储结够图。（6分）
八、 对下图分别按prim算法和
kruskal算法求出最小生成树。（请画
出构造步骤）(6分)
九、 简要回答下列问题。
1. 设要求从大到小排序。问在
什么情况下冒泡排序算法关
键字交换的次数
为最大。（4分）
2．如何衡量hash函数的优劣？简要叙述hash表技术中的冲突概念，并指出
三种解决冲突的方法。（6分）
十 、 如下的算法分别是后序线索二叉树求给定的结点的超前结点与后继结点的
1 left 指向其右孩子
rfalg= 0 right 指向其右孩子
1 right 指向其后继
该算法分别用类pascal语言和类C语实现，该生只要选做其中之一即可。
（8分）
用类 pascal 实现的算法
procedure prior (node,x)
begin
if node ≠ ∧ then
if
then
else end;
procedure next(bt, node, x)
begin （bt 是二叉树的树根）
if if node^.rfalg=1
then
else [repeat
T=x;
until x=node;
x=T;
]
end;
类C语言实现的算法
prior (node,x)
{
if (node !=null)
if ( * x=node else
*x=node left
}
next (bt, node, x) ( bt是二叉树的树根)
{ if (node rfalg)
else do
t = * x ;
While * x=T;
}
}
十一、 （统考生作）
设有两个从小到大排序的带头结点的有序链表。试编写求这两个链表交运算的 算法（即L1∩L2）。要求结果链表仍是从小到大排序，但无重复元素。 （10分）
十二 （单独命题考生做）
设无向图G有n个顶点，m条边。试遍写用邻接表存储该图的算发。（10分） （设顶点值用1～n或0～n-1编号）