大学课件--上海交大计算机电子-数据结构九七.docxVIP

本文档由标准美女（标准王国）整

理，仅作学习交流使用。如文档存在缺

页、字迹模糊、乱码等情况，请大家通过论坛消息与我联系。

上海交通大学一九九七年硕士研究生入学考试试题试题名称：数据结构及程序设计技术

试题编号：19

题一(6分）有五个数依次进栈：1,2,3,4,5.在各种出栈的序列中，以3,4先出的序列有哪几个。(3在4之前出栈）

题二(4分）试写出进栈操作，出栈操作算法的时间复杂性。

题三(4分）已知KMP串匹配算法的模式串是AABBAAB,试写出改进后的NEXT信息帧。

题四(4分）设某通信电文由A、B、C、D、E、F六个字符组成，它们在电文中出现的次数分别是16,5,9,3,20,1。试画出编码用的哈夫曼树。

题五(5分）已知某排序平衡二叉树T具有下列特点：(1)结点的关键字均在1到9范围内；(2)在T中存在一个关键字为n1的叶结点，若删去该结点，立即插入一个关键字为n1的结点，得到的平衡树与原T不相同；(3)在T中存在另一个关键字为n2的非叶结点，删去它，并立即插入n2结点，得到与原T相同的平衡树；(4)在T中插入某n3结点后立即删除它，得到的平衡树与原T不相同。试画出具有上述特点的最简单（结点个数最少）的平衡树T,并写明n1,n2,n3分别等于几？

题六(9分）某整型数组A的10个元素值依次为6,2,9,7,3,8,4,5,0,1,用下列各排序方法，将A中元素由小到大排序。

（1）取第一个元素值6作为分割数，（2）试写出快速排序第一次分隔后A中的结果。

（3）用堆排序，（4）试写出将第一个选出的数据放在A的最后位置上，（5）将A调整成堆后的A中结果。

（6）用基数为3的基数排序法，（7）试写出第一次分配和收集后A中的结果。题七(14分）某赋权有向图及它的单邻接表如下：

（1）试写出深度优先有哪些信誉好的足球投注网站顺序。

（2）画出深度优先生成树。

（3）将该图作为AOE网络图，（4）试写出C的最早发生时间及活动FC的最晚开始时间。

（5）用Dijkstra算法计算源点A到各顶点的最短路径，（6）试写出当计算出AD及AG的最短路径时，（7）A到其它各点路径（中间结点）的值。

始点

123

32

1213

15

终点

请在下列各题的（N）处，填写适当的Pascal语句（或其它成份），完成各题

的程序。

题八(10分）下列程序输入一个正整数N(0n10)，打印1,2,….,n各数字的全排列，例如输入n=3,打印123,132,213,231,312,321

programexam8(input,output);constmaxn=9;

vara:array[1..maxn]ofinteger;{放全排序一个值}s:setof1..maxn;{放1到9各数字的集合}

n:integer

procedureload(j:integer);{将S中数字装入到a中}varj,kinteger;

begin

forj:=1tondoifjins

thenbegins:=(1)a[i]:=j;

ifin

then(2)

elsefork:=1tondowriten(a[k]);

(3)end

end{load};begin{main}

readln(n);s:=[1..n];load(1)

end.

题九(10分）下面的过程对二叉树进行后序遍历（非递归）。假设已有栈的一些操作过程说明。并说明树的结点类型：

typepointer=node;node=record

data:integer;

left,right:pointerend;

procedurepost(p:pointer);varq:pointer;

begin

ifpthen

begincreate_stack(s);建{立一个S栈，并初始化为空栈}while(Pnil)ornote