北京交通大学1993年数据结构考研试题

来源：时间：2007-06-06 13:36:15

1993年硕士学位研究生入学考试试题
一．有向图G=(V,E),其中={V1,V2,V3,V4}; E={<V3,V1>,<V3,V2>,<V4,V3>,<V4,V2>,<V1,V4>}试画出G的三种存贮结构图
二．设G=(V,E)是一个带有权的连通图,则
1．请回答什么是G的最小生成树；
2．设G为
请找出的所有最小生成树。
三.试证明折半查找算法的比较次数C≤∟log2x」+1.其中N 为有序表的元素个数
四.假设以数组sq[0..7]存放循环队列元素,变量F指向对头元素的前一位置,变量指向对尾元素，如用和分别表示入队和出队操作，请给出
1. 队空的初始条件;
2. 执行操作序列A3D1A5D2A1D2A4时的状态,并作必要的说明.
五.试构造一棵二叉树,包含权为1,4,9,16,25,36,49,64,81,100等10个终端结点,且具有最小的加权路径长度WPL.
六.广义表的接点结构如下:
其中LINK为指向表中下一元素的指针;TAG为标志域,具体含义如下:
0 表示该结点为原子结点.DATA为其数据
1 表示该结点为一个字表，DATA为指向该子表的指针
1.说明下列算法A的功能(注:P,T,M,N,R,Q为指针;算法中的NIL对应图中的^)
PROCEDURE  A(P,T)
  BEGIN
       Q:=NIL;
     WHILE  P<>NIL DO
      BEGIN
       IF P^.TAG<> 0 THEN
          BEGIN
             M:=P^.DATA;
            A(M,N);
           P^.DATA:=N
          END;
  R:=P^.LINK;
  P^.LINK:=Q;
  Q:=P;
  P:=R
END;
T:=Q
END.
3. 对于P所指的广义表,画出执行算法A后的表结构以及P为:

七.已知二叉树T,试写出复制该二叉树的算法(t→T)
1. 递归算法
2. 非递归算法

结束

特别声明：①凡本网注明稿件来源为"原创"的，转载必须注明"稿件来源：育路网"，违者将依法追究责任；

②部分稿件来源于网络，如有侵权，请亚洲2019AV无码网站在线_波多野结衣免费一区视频_国产IGAO视频网在线观看_国产人妖乱国产精品人妖沟通解决。