2017年华中科技大学887数据结构与算法分析考研试题

本站小编 免费考研网/2020-02-27

一.名词解释(25分,1个5分)

1.1堆分配存储表示

1.2完全图

1.3树的结点层次

1.4拓扑排序

1.5时间复杂度

二.选择题(25分,1个5分)

2.1 折半查找的平均时间复杂度是(B)

A. 1

B.logn

C. n

D. n

2.2

int frog{

if(n==0)

return 1;

else

return (n+frog(n-1)/2);



上述算法时间复杂度是多少(B)

A.logn

B.n

C. nlogn

D. (n)`2

2.3一个算法的时间复杂度与什么有关(D)

A. 存储器的大小

B. 编程语言

C. 计算机的主频

D. 循环执行的次数

2.4具有20个树叶的二叉树中只有1个孩子的结点个数是11,则这个二叉树总的结点个数是多少(A)

A. 50

B.49

C. 51

D.52

2.5下列关于队列说话不正确的是(B)

A. 先进先出

B.后进先出

C. 插入删除只能在端点

D. 插入删除在不同点进行

三.简答题(60分)

3.1{1,2,3,4,5,6,7,8}利用数组建成一个最大堆并使用堆排序将其排序唯一个升序数组。要求画出所有中间过程。

3.2 先序为ABDFGHCE 中序BFDHGACE 画出该树

3.3给出一个邻接矩阵画出克鲁斯卡尔算法具体过程

00 4 4 2 1

4 00 1 00 2

4 1 00

5 3

2 00 5 00 4

1 2 3 4 00

3.4 13个权值为5,18,12,13,4,6,7,9,28,16,20,30,2

给出哈夫曼树并设计编码

3.5给出输出结果并说明函数功能。

void Print(int w)

{

int i;

if (w!=0)

{

Print(w-1);

for(i=1:i<=w;i++)

printf(“%d, ”,w);

printf(“/n”);

}

}

四.算法设计(40分)(编码困难可以写伪代码,会适当扣分)

4.1求二叉树所有具有两个子女的结点个数,如果根节点为空,则返回0。

typedef struct Bintreenode{

int data;

struct Bintreenode *right;

struct Bintreenode *left;

} *Bintreenode;

4.2 一个长度为n数组由负数0 正数组成,编写函数,将其重新排序为前面都是负数,中间都是0 .后面都是正数的结构。要求时间复杂度为n。


相关话题/华中科技大学 数据