东南大学2008年计算机应用技术专业考研试题之数据机构

一、下列算法时间复杂性

void fun（int m，int n）

{

int i=0，j=0；

while（i<m）

if（j<n） j++；

else

{

j=0；

i++；

}

}

二、应用题

1 void String：：fail （ ） { // 计算模式p （ *this）的失败函数

2 int LengthP= Length（ ）； f[0]= -1；

3 for （int j = 1； j < LengthP； j++） { // 计算f[j]

4 int i = f[j-1]；

5 while （（*（str+j）！=*（str+i+1）） && （i>=0）） i=f；

6 if （ *（str+j） == *（str+i+1）） f[j] = i+1；

7 else f[j] = -1；

8 }

9 }

问：第5句的作用是什么？执行第6句时i可以小于0吗？执行第7句时i一定小于0吗？

三、 R0，R1，R2，R3，R4，R5，R6建败着树。

四、论述

论述在克鲁斯卡尔算法中，如何利用并查集判断所选边<u，v>是否会成环。

五、问答题

树的定义：一棵树是由一个或多个结点组成的有限集合，且其中

（1）存在一个称为根的特定结点；

（2）剩余结点被划分为n≥0个不相交集合T1， …， Tn，且Ti（1≤i≤n）也是一棵树。T1， …， Tn 称为根结点的子树。

问：为什么树不能为空啊？为什么二叉树可以？

六、快排序和堆排序都不稳定，举例说明。

七、给了一棵3阶B树，画图描述连续删除两个数，再在原图上连续插入两个数过程。

八、判断题

struct Element{int key；}；

struct TreeNode

{

TreeNode *LeftChild，*RightChild；

Element data；

}

利用上面两个结构给出判断一棵根为t的二叉树是否为AVL树的递归算法。

bool Tree：：IsAVL（）

{

return IsAVL（t）；

}

bool Tree：：IsAVL（TreeNode * cur）

{

if（！cur） return true；

//……

}

int Tree：：Height（TreeNode * cur）

{

//……

}

请点击查看更多东南大学考研相关信息>>>

相关链接：东南大学历年考研专业课试题汇总

【东南大学2008年计算机应用技术专业考研试题之数据机构】相关文章：

★ 山东师范大学05年考研专业课试题(区域经济学)

★ 山东师范大学06年考研专业课试题(电动力学)

★ 清华大学1996年硕士研究生入学考试生物化学试题

★ 南开大学2000年硕士研究生入学考试文艺理论试题

★ 西南财经大学2000年硕士研究生入学考试经济学说史试题

★ 山东师范大学05年考研专业课试题(美学基本原理)

★ 北京大学2000年硕士研究生考试实验心理学试题

★ 西安交通大学2000年硕士研究生入学考试微生物学试题

★ 山东师范大学06年考研专业课试题(环境学概论)

★ 山东师范大学05年考研专业课试题(文学艺术基本理论)