作者: duck0135 时间: 2011-2-14 16:34
标题: 华中科技大学软件学院2011年研究生入学考试试题
华中科技大学软件学院2011年研究生入学考试试题
数据结构与算法
一.术语解释:(25')
1 线性表
2 树的结点的层次
3 排序
4 完全图
5 最小生成树
二.单项选择:(25')
1 在数组{1,2,3,4,5,6,7,8,9,10}中折半查找5,需要的比较次数是()
A 1 B 2 C 3 D 4
2 假定问题规模为N时,某递归算法的时间复杂度记为T(N),已知T(1)=1,
T(N)=2T(N/2)+N/2,用O表示的时间复杂度为()
A O(N) B O(NlogN) C O(N²) D O(N²logN)
3 一棵二叉树的先序遍历输出为ABCDEFGH,中序遍历为CBEDAFHG,则其先序遍历输出为()【此题的确问的是先序遍历】
A CBDEAFGH B CBEDAFHG
C BCEDFAHG D 以上都不对
4 栈和队列的共同点是()
A 先进先出 B 后进先出
C 插入删除只能在端点进行 D 没有共同点
5 起泡排序的时间复杂度是(C)【此题原试卷将答案附上了】
A O(N) B O(NlogN) C O(N²) D O(N²logN)
三.简答(60')
1 用一个数组实现两个栈,尽可能利用存储空间,写出两个栈的插入、删除操作算法。
2 已知一组关键字为{27、25、23、37、35、33、77、75、73、97、95、93、103},按哈希函数H(key)=key Mod 11(表长11),用连地址法处理冲突,画出哈希表。
3 一个递归函数具有如下形式
Void func(int n)
{
if(n>0)
{
func(n/2);
printf("d%",n*n);
func(n/2);
}
return;
}
请依次写出fun(1),fun(2),fun(3),fun(5)执行的结果,其时间复杂度为多少?
4 一个通信网络中共有九中字符,其概率分别为0.14、0.23、0.15、0.03、0.18、0.1、0.02、0.11、0.04,画出相应的赫夫曼树来设计其赫夫曼编码。
5 V₁→V₂→V₃→∧; V₂→V₄→V5→∧ ; V3→V5→V6→∧ ; V4→∧;
V5 →V7 →V8 →∧ ; V6→V8→∧; V7 →∧ ; V8→V9→∧ ; V9→∧,
画出这个逻辑结构的图示,分别写出从V₁出发的深度优先和广度优先搜索序列。
四.应用编程题:(40')
1 在一个整形数组a中既有负数又有正数,编写一个算法将a中所有负数移到整数之前, 要求其时间复杂度为O(n),n为数组长度,并且只使用常数个辅助空间。
例如:a[ ]={1,2,3,4,-1,1,-2,-1,-4}执行算法后的输出为a[ ]={-4,-1,-2,-1,1,4,3,2,1}
2 编写一个C函数,输入一个二叉树的根节点,返回这棵树中所有值大于0的节点值之和,如果根为空,返回0。
二叉树的链式存储结构对应的C语言的结点类型定义如下:
typedef struct node{
ElemType data;
struct node *lchild;
struct node *rchild;
}BTree;
说明:1.本试题为回忆版试题,某些题目的数值或者语言表述可能与原版不一致;
2.本试题仅供大家学习交流使用,严禁用于各类商业用途。
作者: hotsummer86 时间: 2011-2-14 21:57
专业课比中科大简单。。。最起码知识点少很多很多。。
作者: magicyang112 时间: 2011-2-14 22:24
编程题出题点和北航的好像啊。。。我囧 不过这题量最多只有北航的70%吧。。。。3小时?。。。。
中科的数据结构确实很难 很多很生的出题点。。。
作者: zzfxjk 时间: 2011-2-15 22:37
LZ.计算机不是全国统考啊!是不是有些院校还是自主考试啊?这是怎么回事啊?12年的求教....
作者: ffwwd456 时间: 2011-2-16 18:02
虽然我不是这个专业的........这个很像二级里的公共基础
作者: ewlwl 时间: 2011-2-16 18:14
想了解华科软院的同学可以论坛短信我,愿意回答各种有关问题
作者: duck0135 时间: 2011-2-18 17:24
回复 zzfxjk 的帖子
计算机是统考,软件学院一般自主命题!
作者: 291947537 时间: 2011-3-23 12:17
回复 ewlwl 的帖子
呵呵,你好!
请问你知道华科软件学院软件工程的总共学费、学习时间吗?
顺便请教一句:复试难吗?全部都是上机,还是有笔试啊?有相关题吗?
感激不尽!
作者: rocdevil 时间: 2011-4-6 14:42
谢谢
作者: 沫小蜗 时间: 2011-9-22 23:21
分享哈皮