手机APP下载

您现在的位置: 首页 > 考研频道 > 考研专业课 > 上海交通大学 > 正文

上海交通大学2004年数据结构专业课考研真题试卷(回忆版)

来源:可可英语 编辑:max   可可英语APP下载 |  可可官方微信:ikekenet

一、已知一棵中序线索二叉树的结点结构为:

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 算法的时间复杂性为 [ ]。

附答案:

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 分)
要点:1、注意,题目给出的是按照中序遍历次序的第一个结点的地址first,因此必须从first开始查找data之值为key 的结点p及其父结点q,而不能从根结点开始进行寻找。
2、若结点p是q的右儿子,可分四种情况进行讨论:
A、 结点p是叶子。
B、结点p无左儿子,但有右儿子。
C、 结点p有左儿子,但无右儿子。
D、 结点p既有左儿子,同样也有右儿子。
在进行调整后,注意保持调整后的中序穿线树的结点的中序遍历次序不变。
3、若结点p是q的左儿子,同样有四种情况必须讨论,同2。

二、已知一棵二叉树是以二叉链表的形式存储的,且结点的数据场的类型为int。现已知该二叉树的根结点的地址为root。请写一个非递归的函数(使用的额外空间不得大于O(1)),给出按后序遍历次序的第一个结点的数据场之值。(本题10分)
要点:根据后序周游的定义:LRN 可知第一个被访问的结点将是二叉树中的最左方的叶子,设p=root,若p 为空,则无解返回,否则有三种情况。
1、若有左儿子,则p=p->left;
2、若无左儿子,但有右儿子,则p=p->right;
3、若既没有左儿子,也没有右儿子,则p即为所求

三、已知一棵二叉树是以二叉链表的形式存储的,其结点结构说明如下:(本题10分)
struct node { int data; // 结点的数据场。
struct node *left; // 给出结点的左儿子的地址。
struct node * right; // 给出结点的右儿子的地址。
};
请在1、2二题的 [ ] 处进行填空,完成题目要求的功能。注意,每空只能填一个语句,多填为 0 分。
1、求出以T 为根的二叉树或子树的结点个数。
int size (struct node * T ) {
if ( [ T == NULL ] ) return 0;
else [ return 1 +size(T->left) + size(T->right) ];
}
2、 求出以T为根的二叉树或子树的高度。注:高度定义为树的总的层次数。
int height(struct node * T ) {
if ( T == NULL ) [ return 0 ];
else [ return 1 +( ( height(T->left) > height(T->right))? height(T->left): height(T->right) ) ];
}

四、设结点个数为n,请问采用堆排序法进行排序,其时间复杂性是多少?请以大O形式给出,并给出证明。(本题10分)
要点:

1、建堆的时间代价:O(n)
2、 排序且进行调整的时间代价:log(n-1)+ log(n-2)+……+ log3+ log2 = O(nlogn)
证明的详细过程略。

五、填空:(本题15分)
1、在二叉排序树上成功地找到一个结点,在平均情况下的时间复杂性是 [ O(logn) ], 在最坏情况下的时间复杂性是 [ O(n) ]。设结点个数为 n,以大O形式给出时间复杂性。
2、在二叉平衡排序树上成功地找到一个结点,在平均情况下的时间复杂性是 [ O(logn) ], 在最坏情况下的时间复杂性是 [O(logn) ]。设结点个数为 n,以大O形式给出时间复杂性。
3、设工作区的容量为W,则置换选择排序法所得到的初始归并段长度的期望值为[ 2w ]。
4、设主串和模式的字符个数分别为m和 n,则在最坏情况下,KMP 算法的时间复杂性为 [ O( m+n) ]。


发布评论我来说2句

    最新文章

    可可英语官方微信(微信号:ikekenet)

    每天向大家推送短小精悍的英语学习资料.

    添加方式1.扫描上方可可官方微信二维码。
    添加方式2.搜索微信号ikekenet添加即可。