2017华科软件专业课分享

P灰灰 · 发表于 2017-7-9 20:50

本帖最后由 as3652553 于 2017-11-30 21:13 编辑

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

一．名词解释（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。
关于2018华科软院887复习八套卷
本套试题针对2018华科软件887数据结构与算法分析而制，内容与往年大纲一致，鉴于15-17年题型难度趋于稳定，本套卷将严格按照往年出题风格，希望各位考生能考到理想的成绩。

附2015-2017考研真题题型。
1名词解释（25分，1个5分）
5个名词留一大段空白给出解释。
例：完全图（2017）

答：若一个图的每一对不同顶点恰有一条边相连，则称为完全图。完全图是每对顶点之间都恰连有一条边的简单图。n个端点的完全图有n个端点及n(n − 1) / 2条边。

范围：数据结构的概念，时间复杂度，线性表，栈队列，树，图，排序算法，查找。
将总结出的算法解释背诵即可。

2.选择题（25分，1个5分）
选择题中经常出现关于时间复杂度的分析。（17年考了3道）
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. 循环执行的次数
堆栈的概念，树图中的计算题。

3.简答题（60分）

5道题
树的二道。（前中得后，中后得前，后序表达式，最优二叉树）
图的一道。（给出图，写出过程）普里姆，克鲁斯卡尔，迪杰斯特拉
排序一道。近几年经常考关于堆排序得知识。
给出代码，写出运行结果。（一道）

4.算法设计（40分）（编码困难可以写伪代码，会适当扣分）

基本上每年2道，一道线性表，一道树的，图的代码没考过。
例：求出链表L的倒数第N个结点的data。
先别急的写代码
首先用注释的形式写出代码的大概过程

/*输入：链表L，结点K
定义两个结点指针p1，p2指向该链表的头结点，利用p1遍历整个链表，记下长度n
然后再利用p2往后遍历n-k个结点
输出：结点K的data
异常：没有第K个结点，输入为空指针*/

之后再是代码

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
｛
。。。。
｝
写代码需要充分考虑所有的测试用例