华科软件学院2011年考研试题 数据结构与算法

一.术语解释

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;

【华科软件学院2011年考研试题 数据结构与算法】相关文章：

★ 山东师范大学05年考研专业课试题(世界政治经济与国际关系)

★ 上海交通大学1990年硕士研究生考试数据结构及程序设计技术试题

★ 华东师范大学1997年考研中共党史试题

★ 天津商学院2006年考研民法试题

★ 华南师范大学2003年考研发展与教育心理学试题

★ 清华大学法学院2006年法学硕士入学考试试题

★ 清华大学2000年硕士研究生入学考试数据结构与程序设计试题

★ 山东师范大学06年考研专业课试题(离散数学)

★ 山东师范大学05年考研专业课试题(艺术学与中外美术史)

★ 天津商学院2006年考研民商法试题