南京航空航天大学1995数据结构考研题
数据结构部分
五、是否题(判断下面命题是否正确) (10分)
1. 深度为K的二叉树中结点总数≤2 -1。
2. 数组不适合作为任何二叉树的存储结构。
3. 对一棵二叉树进行层次遍历时，应借助于一个栈。
4. 对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。
5. 邻接多重表是无向图和有向图的链式存储结构。
6. 当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffmen树且二叉树的形状必是唯一的。
7. AOV网的含义是以边表示活动的网。
8. 拓扑排序算法把一个无向图中的顶点排成一个有序序列。
9. 对一个AOV网，从源点到终点的路径最长的路径称作关键路径。
10. 排文件的优点是维护简单。
六、出所有的二叉树，其结点在下列两种遍历下，恰好都是以同样的顺序出现：(5分)
(a) 前序遍历和中序遍历。
(b) 前序遍历和后序遍历。
七、要叙述循环队列的数据结构，并写出其初始状态、队列空、队列满是的队首指针与队尾指针的值 (5分)
八、对如下关键字序列，按快速排序算法思想对其排序。要求给出每趟的排序结果。(12，23，18，14，3，21，16) (6分)
九、简要叙述Hash表与Hash文件的不同之处。 (5分)
十、设Pa，Pb分别指向两个带头结点的有序(从小倒大)单链表。仔细阅读如下的程序，并回答问题： (9分)
(1) 程序的功能。
(2) s1，s2中值得含义。
(3) Pa，Pb中值得含义。
procedure exam(Pa, Pb)
begin
P1:=Pa↑.next;
P2:=Pb↑.next;
Pa↑.next:=∧;
s1:=0;
s2:=0;
while P1≠∧ and P2≠∧ do
[ case
P1.↑data
[ P:=P1;
P1:=P1↑.next;
s2:=s2+1;
dispose(P)];
P1↑.data>P2↑.data:
P2:=P2↑.next;
P1↑.data=P2↑.data:
[ P:=P1;
P1:=P1↑.next;
P↑.next:= Pa↑.next;
Pa↑.next:= P;
P2:= P2↑.next;
s1:=s1+1 ];
end
];
while P1≠∧ do
[ P:=P1;
P1:=P1↑.next;
dispose(P);
s2:=s2+1
]
end;↑
十一、(统考生做) 试编写求无向图G的连通分量的算法。要求输入每一连通分量的顶点值。设图G已用邻接表存储)(10分)
十二、(单独命题考生做)试编写求倒排循环链表元素的算法。 (10分) | 
