上海交通大学1990年研究生考试数据结构及程序设计技术试题
一、回答下述问题（25分） 1、已知10万个无序的，且互不相等的正整数，现要求找出前10个最大的正整数。采用以下五种分类法：快速分类法，合并分类法，选择分类法，堆分类法，SHELL分类法。试问，那一种方法将能最快地找出这前十个最大的正整数？为什么？ 2、在外部分类时，常采用多阶段合并分类法。假定采用二路多阶段合并分类法。合并开始时，磁带T1分布有Fs-1个合并段，磁带T2分布有Fs-2个合并段，磁带T3为空白带，假定每个合并段都有M个记录。注意，Fs-1,Fs-2分别为fibonacci数列的第S－1及S－2项。试推导出在合并分类结束时，记录读写的总次数9（推导出和式即可） 3、求下列样品的失效函数： (1)P1=aaaaaa (2)P2=abcabdaaabc (3)P3=abcabdabeabc 4、已知字母a,b,c,d,e,f,g,h的使用频率分别为40%,20%,10%,8%,8%,5%,5%,4%；给出这8个字符的HUFFUMAN编码，要求给出求解步骤。 5、可否使用拓扑分类算法，确定所给有向图是否有回路？如何实现，为什么？ 6、求出下图的关键路径，结点的最早完成时间，结点的最晚完成时间及关键活动。 二、（15分） 设计一个程序，以一序列正整数，如：78，45，2，14，23，…作为输入，生成一棵中序穿线二叉树。 三、（10分） 已知一棵以标准形式存贮的三次有序树。设计一个程序，将该有序树转化成相应的二叉树（同样以标准形式存贮）。 四、（10分） 假定在平衡分类二叉树中，进行结点删除操作之后，出现了不平衡。试作图说明，如何针对各种不平衡的情况进行调整，使该数恢复为平衡分类二叉树。 五、（10分） 研制一程序，将十进制数N转换为R（2<=R>=16）进制数的数字串。 六、（15分） 回答问题 1、你认为评价程序质量的标准是什么？ 2、什么是函数的副作用？ 七、（15分） 研制一个求K个数的最大公约数的程序。页:
[1]