《东南大学研究生入学考试数据结构试题》由会员分享，可在线阅读，更多相关《东南大学研究生入学考试数据结构试题（12页珍藏版）》请在金锄头文库上搜索。
1、东南大学一九九四年攻读硕士学位研究生入学考试试题试题编号:451 试题名称:数据结构一: 回答下列问题(共 32 分) 1.最近最少使用(Least-Recently-Used)页替换是虚拟存储系统中常用的策略,试说 明如何利用一页链接表时刻跟踪最近最少使用页?(8 分) 2.已知无向图 G,V(G)=1,2,3,4,E(G)=(1,2),(1,3),(2,3),(2,4),(3,4),试画出 G 的邻 接多表(Adjacency Multilists),并说明,若已知点 i,如何根据邻接多表找到与 i 相邻 的点 j?(8 分) 3.欲求前 k 个最大元素,用什么分类(sorting)方法好
2、?为什么?什么是稳定分类?分 别指出下列算法是否稳定分类算法,或易于改成稳定分类算法? (a) 插入分类 (b) 快速分类 (c) 合并分类 (d) 堆(heap)分类 (e) 基数分类(radix sort) (8 分) 4.构造最佳二叉检索树的前提条件是什么?在动态情况下,一般 AVL 树的查询性 能不如完全二叉检索树的,为什么人们却采用 AVL 树呢?(8 分) 二:下列算法对一 n 位二进制数加 1,假设无溢出,该算法的最坏时间复杂度是什 么?并分析它的平均时间复杂性.(15 分) type Num=array1.n of 0.1; procedure Inc(var A:Num);
3、var j: integer; begin i:=n;while Ai=1 doAi:=0;i:=i-1;end; Ai:=1; end Inc; 三:给定 n*m 矩阵 Aa.b,c.d,并设 Ai,j=k; 10 repeat j:=j-1 until listj.key=j; 13 interchange(listm,listj); 14 if n-j=j-m 15 then begin qsort1(list,m,j-1);m:=j+1;end 16 else begin qsort1(list,j+1,n);n:=j-1;end 17 end;(of while) 18 end; 问
4、: (共 20 分) 1.将第 9,10 行中的=,q do p:=p.next;p.next:=s;end; (of B) beginB(h,g);B(g,h); end; (of A) 三:已知无向图采用邻接表存储方式,试写出删除边(i,j)的算法.(10 分) 四:线性表中有 n 个元素,每个元素是一个字符,存在向量 R1.n中,试写一个 算法,使 R 中的字符按字母字符,数字字符和其它字符的顺序排列.要求利用原空 间,且元素移动次数最少.(15 分) 五:四阶 B 树中(如图所示),插入关键字 87,试画出插入调整后树的形状.(10 分)|30 60 80|/ / |20 25| |3
5、5 50| |60 70 75| |82 85 90| 六:试编写一算法对二叉树按前序线索化.(15 分)_东南大学二年攻读硕士学位研究生入学考试试题科目编号:451 科目名称:数据结构 一:简要回答下列问题(共 40 分) 1.假设一棵二叉树的层序序列是 ABCDEFGHIJ 和中序序列是 DBGEHJACIF,请画出 该树.(6 分) 2.简单比较文件的多重表和倒排表组织方式各自的特点.(6 分) 3.画出对算术表达式 A-B*C/D+EF 求值时操作数栈和运算符栈的变化过程.(6 分) 4.找出所有满足下列条件的二叉树 6 分) a)它们在先序遍历和中序遍历时,得到的结点访问序列相同;
6、b)它们在后序遍历和中序遍历时,得到的结点访问序列相同; c)它们在先序遍历和后序遍历时,得到的结点访问序列相同. 5.对一个由 n 个关键字不同的记录构成的序列,能否用比 2n-3 少的次数选出该 序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏情况 下至少进行多少次比较?(8 分) 6.已知某文件经过置换选择排序后,得到长度分别为 47,9,31,18,4,12,23,7 的 8 个初始归并段.试为 3 路平衡归并设计读写外存次数最少的归并方案,并求出 读写外存的次数.(8 分) 二:已知 L 是无表头结点的单链表,其中 P 结点既不是首元结点,也不是尾元结 点,(10
7、分) a)在 P 结点后插入 S 结点的语句序列是_ b)在 P 结点前插入 S 结点的语句序列是_ c)在表首插入 S 结点的语句序列是_ d)在表尾插入 S 结点的语句序列是_ (1) P.next:=S; (2) P.next:=P.next.next; (3) P.next:=S.next; (4) S.next:=P.next; (5) S.next:=L; (6) S.next:=NIL; (7) Q:=P; (8) WHILE P.nextNIL DO P:=P.next; (10) P:=Q; (11) P:=L; (12) L:=S; (13) L:=P; 三:设计一个符号表
8、的表示方法,编写算法使得在该表中进行查询,插入和删除 任何一个标识符 X 的操作在 O(1)的时间内.假设 1=k;repeat j:=j-1 until listj.key=j;interchange(listm,listj);if n-j=j-mthen begin qsort1(list,m,_);_;endelse begin qsort1(list,_,n);_;endend;(of while) end; 六:给定 n*m 矩阵 Aa.b,c.d,并设 Ai,j=Ai,j+1(a=i=b,c=j=d-1)和 Ai,j=Ai+1,j(a=i=b-1,c=j=d),设计一算法以 O(n+m)的时间复杂度判 定值 x 是否在 A 中.
