上海交通大学2004年硕士研究生入学考试数据结构试题

2004年研究生数据结构试题(70分)
一、            已知一棵中序线索二叉树的结点结构为：
 
  left     ltag          data           rtag            right
     

 
其中：data 域的类型为int。
ltag=0,那么left域中存放的是该结点的左儿子结点的地址。
ltag=1,那么left域中存放的是该结点的按中序周游次序的前驱结点的地址。
rtag=0,那么right域中存放的是该结点的右儿子结点的地址。
rtag=1,那么right域中存放的是该结点的按中序周游次序的后继结点地址。
现已知该中序线索树中，按照中序遍历次序的第一个结点的地址为first，以及某一整数值为key。请写一个函数，输出结点的data之值为key 的结点，并仍保持中序线索树的性质不变。注意：不准使用递归，额外空间不得大于O(1)。(本题 25 分)
 
二、已知一棵二叉树是以二叉链表的形式存储的，且结点的数据场的类型为int。现已知该二叉树的根结点的地址为root。请写一个非递归的函数(使用的额外空间不得大于O(1))，给出按后序遍历次序的第一个结点的数据场之值。(本题10分)
 
三、已知一棵二叉树是以二叉链表的形式存储的，其结点结构说明如下：（本题10 分。）
struct node {        int data;   // 结点的数据场。
struct node *left;    // 给出结点的左儿子的地址。
       struct node * right;   // 给出结点的右儿子的地址。
  }；
请在1、2二题的 [      ]  处进行填空，完成题目要求的功能。注意，每空只能填一个语句，多填为 0 分。
1、  求出以T 为根的二叉树或子树的结点个数。
int size (struct node * T ) {
               if (  [        ]  ) return 0;
               else [                           ];
       }
       2、 求出以T为根的二叉树或子树的高度。注：高度定义为树的总的层次数。
int height(struct node * T ) {
               if ( T == NULL ) [    ];
               else [                                  ];
       }
 
 
 
 
 
 
四、设结点个数为n，请问采用堆排序法进行排序，其时间复杂性是多少？请以大O形式给出，并给出证明。(本题10分)
 
五、填空：(本题15分)
1、在二叉排序树上成功地找到一个结点，在平均情况下的时间复杂性是 [     ], 在最坏情况下的时间复杂性是 [     ]。
设结点个数为 n，以大O形式给出时间复杂性。
2、在二叉平衡排序树上成功地找到一个结点，在平均情况下的时间复杂性是 [     ], 在最坏情况下的时间复杂性是 [       ]。
设结点个数为 n，以大O形式给出时间复杂性。
3、设工作区的容量为W，则置换选择排序法所得到的初始归并段长度的期望值为[    ]。
4、设主串和模式的字符个数分别为m和 n，则在最坏情况下，KMP 算法的时间复杂性为 [           ]。