上海交通大学一九九八年硕士研究生入学考试试题 试题名称:数据结构和程序设计技术 试题编号:19 题一(20分)判断题:若认为下列命题正确,打“ˇ“,反之打“ 1、数据元素是数据的最小单位() 2、队列逻辑上是一个下端口和上端能增加又能减少的线性表 3、任何一个递归过程都可以转换成非递归过程。( 4、只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈() 5、数组可看成线性结构的一种推广,因此与线性表一样,可以对它进行插入、删除等操 作。() 6、两叉树是树的一种特殊情况() 7、在树中,如果从结点K出发,存在两条分别到达K,K”的长度相等的路径,由结点 K和k互为兄弟() 8、线索两叉树的优点是便于在中序遍历下,查找前趋和后继结点() 9、n个结点的两叉树有多种,其中树高最小的两叉树排序树是最佳的 10、最佳两叉排序树的任何子树都是最佳的() 11、设T为一棵平衡树,在其中插入一个结点N,然后立即删除该结点得到T1,T与T1 必定相同() 12、一个有向图的邻接表和逆邻接表中结点的个数可能不等。( 13、任何有向图的结点都可以排成拓扑排序,而且拓扑排序不唯一() 14、当改变网上某一关键路上任一关键活动后,必将产生不同的关键路径( 15、两分法插入排序所需比较次数与待排序记录的初始排列状态相关() 16、当待排序记录已经从小到大排序或者已经从大到小排序时,快速排序的执行时间最省 17、在索引顺序表中,实现分块查找,在等概率查找情况下,其平均查找长度不仅与表中 元素个数有关,而且与每块中元素个数有关() 18、在执行某个排序算法过程中,出现了排序码朝着最终排序序列相反方向移动,则该算
上海交通大学一九九八年硕士研究生入学考试试题 试题名称：数据结构和程序设计技术 试题编号：１９ 题一（２０分）判断题：若认为下列命题正确，打““，反之打““ １、 数据元素是数据的最小单位（ ） ２、 队列逻辑上是一个下端口和上端能增加又能减少的线性表（ ） ３、 任何一个递归过程都可以转换成非递归过程。（ ） ４、 只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈（ ） ５、 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入、删除等操 作。（ ） ６、 两叉树是树的一种特殊情况（ ） ７、 在树中，如果从结点 K 出发，存在两条分别到达 K’，K”的长度相等的路径，由结点 K’和 k”互为兄弟（ ） ８、 线索两叉树的优点是便于在中序遍历下，查找前趋和后继结点（ ） ９、 n 个结点的两叉树有多种，其中树高最小的两叉树排序树是最佳的（ ） １０、最佳两叉排序树的任何子树都是最佳的（ ） １１、设 T 为一棵平衡树，在其中插入一个结点 N，然后立即删除该结点得到 T1，T 与 T1 必定相同（ ） １２、一个有向图的邻接表和逆邻接表中结点的个数可能不等。（ ） １３、任何有向图的结点都可以排成拓扑排序，而且拓扑排序不唯一（ ） １４、当改变网上某一关键路上任一关键活动后，必将产生不同的关键路径（ ） １５、两分法插入排序所需比较次数与待排序记录的初始排列状态相关（ ） １６、当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省 ( ) １７、在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中 元素个数有关，而且与每块中元素个数有关（ ） １８、在执行某个排序算法过程中，出现了排序码朝着最终排序序列相反方向移动，则该算
法是不稳定的() 19、堆排序是稳定的排序方法 20、在分配排序时,最高位优先分配法比最低位优先分配法简单 题二、(15分)试证明:若借助栈由输入序列1,2…n得到输出序列为pl-p2,,pn(它是输 入序列的一个排序),则在输出序列中不可能出现这样的情形:存在着I(1<=ij<=3)
法是不稳定的（ ） １９、堆排序是稳定的排序方法（ ） ２０、在分配排序时，最高位优先分配法比最低位优先分配法简单（ ） 题二、（１５分）试证明：若借助栈由输入序列 1,2,…n 得到输出序列为 p1,p2,…pn,（它是输 入序列的一个排序），则在输出序列中不可能出现这样的情形：存在着 I (1<=i,j<=3)
11 题七(12分)已知a数组元素共5个,依次为12,10,5,3,1,b数组元素共4个,依次为 46.8,15,则执行如下所示的过15,12,10,8,65,4,3,1,数组abc的长度分别为l=5,m=4,n=9, 请在程序中方框内填入正确的成份,以完成上述要求 Procedure Sort j, k, x: integer d: array l.m of integer egin for 1: =I to m do d[i while(idi] en begin
6 4 2 3 11 题七(12 分)已知 a 数组元素共５个，依次为 12,10,5,3,1;b 数组元素共４个，依次为 4,6,8,15，则执行如下所示的过15,12,10,8,6,5,4,3,1，数组a,b,c的长度分别为l=5,m=4,n=9， 请在程序中方框内填入正确的成份，以完成上述要求。 Procedure Sort Var i,j,k,x:integer: d:array[1..m] of integer; begin for i:=1 to m do d[i]:= i:=1;j:=1;k:=1; while(id[i] then begin end; else begin
[k}=x end c[k]:=a[;k:=+1;1=i+1 end c[k]:=d]:k:=k+1j=+1 end; i sort; 题八(8分)已知如下一棵三阶B_树,试画出插入关键字B,LPQR以后的树形。 E J K n O
end; c[k]:=x; end; while do begin c[k]:=a[i]; k:=k+1;i:=i+1 end; while do begin c[k]:=d[j]; k:=k+1;j:=j+1 end; end;{sort} 题八（８分）已知如下一棵三阶Ｂ＿树，试画出插入关键字 B,L,P,Q,R 以后的树形。 A G C I M D E H J K N O
