湖南大学866数据结构真题

1、画出对下列存储于数组中的值执行buildheap后得到的最大值堆： 10 5 12 3 2 1 8 7 9 4

先序遍历为12 10 4 1 2 9 5 8 3 7 中序遍历为1 4 2 10 5 9 12 3 8 7

2、假设某字母表各个字母的权如下：

Q Z F M T S O E 2 3 10 10 10 15 20 30

(a) 按照这个字母表，一个包含n个字母的字符串采用Huffman编码在最差情况下需要多少位？怎样的串会出现最差情况？

在最差的情况下需要5*n位，当所有的字母都是Q或者Z的时候。

（b）按照这个字母表，包含n个字母的字符串采用Huffman编码在最佳情况下需要多少位？怎样的串会出现最佳情况？

在最佳的情况下需要2*n位，当所有的字母都是E或者O的时候。 （c）按照一个字母表，一个字母平均需要多少位？

（2*30 + 2*20 + 3*15 + 3*10 + 3*10 + 4*10 + 5*3+ 5*2）/100 =2.7 ∴ 2.7

3、

北京师范大学08年考研程序设计与数据结构试题

考研_考试大 [ 2008/11/17 ] 来源：北京师范大学

一、简答题（20分）

1.数据类型和抽象数据类型的含义 2.算法的特性与算法的时间复杂度

3.快速排序方法最好和最坏的情况是什么？简要分析说明 4.栈、队列的共同点与不同点，说明其属于线形表的原因 二、方法选择（20分）

1.一棵二叉排序树中各结点不相同，欲得到一个由大到小的结点值递减序列，你认为采用什么方法能得到要求的结果？

2.设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序，基数排序，快速排序，堆排序，插入排序），那种方法最好，为什么？

三、（40分，每题8分）

1.已知一个循环单链表la，av是可利用栈的头指针，请用３个赋值语句，完成将整个循环链表释放的功能。（即将表整个归还到可用的栈空间） 2.给出求N阶hanoi塔的函数定义如下：Hanoi （ int n，char x，char y ，char z ）

{ if （ n= =1） move （ x ，1，z） Else{ hanoi（ n-1， x，z，

计算机——《数据结构》

第1页 共13页

1．简述栈的基本操作

2．给定权值组W={1，3，78，14，20，28}，建立哈夫曼树。 3．试求下面的网络的最小生成树

10 1?C10

69 ?B15?E5 613 6?A?D

84.对一组关键字49，7，50，5，94，16，90，29，71，使用希尔排序，写出对d1?3时的一趟排序的结果。 1-4题答案：

1、栈的基本操作有：

栈的建立，判栈满，判栈空，压栈，退栈和取栈顶元素等。 2、

144

66

7838

28 1820 414

3 13、 41 96 536 625 84、

4950594169029717

1649295090947175

5．写出队列的基本操作。

a 6．对下面的二叉树

（１） 其中序遍历序列为

b

c （２）其后序遍历序列为 d e

5

g

h 7．给定一组关键字序列12，7，51，32，23，试构造一棵查找树。

8．对一组关键字49，7，50，5，94，16，90，29，71，使用快速排序，试给出第一次划分过程。

5-8题答案：

5．队列的基本操作有：

队列的建立，判队空，

2012年全国硕士研究生统一入学考试自命题试题

********************************************************************************************

学科与专业名称：计算机技术，软件工程 考试科目代码与名称：830 数据结构 考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 一. 选择题(每题2分，共30分) 1．队列操作的原则是（ ）。 A. 先进先出 B. 后进先出 C. 只能进行插入 D. 只能进行删除 2. 一个栈的进栈序列是a, b, c, d, e, 则栈的不可能的输出序列是（ ）。 A. edcba B. decba C. dceab D. abcde 3. 采用顺序查找法查找长度为n的线性表时,每个元素的平均查找长度为 （ ）。 A. n B. n/2 C.(n+1)/2 D.(n-1)/2 4. 线性表的链接实现有利于(

第一章 概述 真题

16.下列程序段的时间复杂度为____________。 for(i=1；i<=n；i++)

for(j=1；j<=n；j++)

for(k=1；k<=n；k++)

s=i+j+k；

17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____________。

16.下列程序段的时间复杂度为________。

i=0；s=0；

while（i

17.数据的逻辑结构被分为集合结构、_____、树形结构和图状结构4种。

1.数据的不可分割的最小标识单位是（ ）

A.数据项 B.数据记录 C.数据元素 D.数据变量 2. for（i=0；i

for（j=0；j

c［i］［j］=0；

for（i=0；i

for（j=0；j

for（k=0；k

c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；

上列程序的时间复杂度为（ ）

A.O(m+n×t) B.O(m+n+t) C.O(m×n×t) D.O(m×t+n)

16.在数据结构中，数据的存储结构有顺序存储方式、链式存储方式、_____和散列存储方式等四种。 17.作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为______。

第一章 概述 真题

16.下列程序段的时间复杂度为____________。 for(i=1；i<=n；i++)

for(j=1；j<=n；j++)

for(k=1；k<=n；k++)

s=i+j+k；

17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____________。

16.下列程序段的时间复杂度为________。

i=0；s=0；

while（i

17.数据的逻辑结构被分为集合结构、_____、树形结构和图状结构4种。

1.数据的不可分割的最小标识单位是（ ）

A.数据项 B.数据记录 C.数据元素 D.数据变量 2. for（i=0；i

for（j=0；j

c［i］［j］=0；

for（i=0；i

for（j=0；j

for（k=0；k

c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；

上列程序的时间复杂度为（ ）

A.O(m+n×t) B.O(m+n+t) C.O(m×n×t) D.O(m×t+n)

16.在数据结构中，数据的存储结构有顺序存储方式、链式存储方式、_____和散列存储方式等四种。 17.作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为______。

第一章 概述 真题

16.下列程序段的时间复杂度为____________。 for(i=1；i<=n；i++)

for(j=1；j<=n；j++)

for(k=1；k<=n；k++)

s=i+j+k；

17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____________。

16.下列程序段的时间复杂度为________。

i=0；s=0；

while（i

17.数据的逻辑结构被分为集合结构、_____、树形结构和图状结构4种。

1.数据的不可分割的最小标识单位是（ ）

A.数据项 B.数据记录 C.数据元素 D.数据变量 2. for（i=0；i

for（j=0；j

c［i］［j］=0；

for（i=0；i

for（j=0；j

for（k=0；k

c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；

上列程序的时间复杂度为（ ）

A.O(m+n×t) B.O(m+n+t) C.O(m×n×t) D.O(m×t+n)

16.在数据结构中，数据的存储结构有顺序存储方式、链式存储方式、_____和散列存储方式等四种。 17.作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为______。

【付出多少，收获多少，加油！】

2012湖南大学经济学综合真题（回忆版）

一．名词解释

1. 需求的交叉弹性

2. 货币幻觉

3. 道德风险

4. 公开市场业务

5. 等产量曲线

6. 结构性失业

二．

1. 什么是边际报酬递减规律，它导致短期边际成本曲线出现什么形状，为什么

2. 如果决策者通过相关法律规定厂商对雇佣的工人增加3美元每小时的补贴，请跟据

供给曲线或需求曲线分析劳动的供给和厂商对劳动的需求，讨论其对就业的影响。

3. 丹尼尔森（E.F.Donision）的经济增长因素，并分析其对经济的作用。

4. 总供给曲线的原因及其分析

三． 计算题

1. 厂商的生产函数STC=Q-3Q+10Q+85，

1) 当价格为55时，厂商的最优产量是多少，最大利润是多少

2) 当价格为19时，厂商是否亏损，亏损多少

3) 在什么情况下，厂商停止生产。

2. 三部门经济，已知C=60+0.8Yd,I= 30-0.2r,G=100.M=200亿美元，L=0.2Y-10r.T=100亿

美元

1) 求IS和LM方程。均衡利率和均衡产出，投资

2) 若政府支出由100增加至110，求均衡利率，均衡产出，和投资

3) 是否有挤出效应。

四．论述题

1) 凯恩斯主义者为什么强调积极的财政政策。如果政府采用1.减

高等代数——2005年真题

一．（20分）证明：数域F上的一个n次多项式f?x?能被它的导数整除的充要条件是

f?x??a?x?b?，?其中a,b是F中的数?.

n二．（20分）设a1a2?an?0，计算下面的行列式：

1?a111?111?a21?111?1??1111111?1?an

1?a3?????2??2??????4?1三．（15分）已知矩阵A?PQ，其中P???，Q???，Q?，求矩阵A,A2和A100。

?3???2?????1????1?四．（20分）给定线性方程组

?x1?a1x2?a12x3?a13?23?x1?a2x2?a2x3?a2 ? （1） 23?x1?a3x2?a3x3?a323??x1?a4x2?a4x3?a4当a1,a2,a3,a4满足什么条件时，方程组（1）有惟一解？无穷多解？无解？ 五．（20分）设f?X???AX是一实二次型，若有实n维向量X1,X2使得Xf?X1????f?X2???，证明：必存在实n维向量X0?0使f?X0??0。

六．设W是齐次线性方程组

?2x1?x2?x3?x4?3x5?0

高等代数——2005年真题

一．（20分）证明：数域F上的一个n次多项式f?x?能被它的导数整除的充要条件是

f?x??a?x?b?，?其中a,b是F中的数?.

n二．（20分）设a1a2?an?0，计算下面的行列式：

1?a111?111?a21?111?1??1111111?1?an

1?a3?????2??2??????4?1三．（15分）已知矩阵A?PQ，其中P???，Q???，Q?，求矩阵A,A2和A100。

?3???2?????1????1?四．（20分）给定线性方程组

?x1?a1x2?a12x3?a13?23?x1?a2x2?a2x3?a2 ? （1） 23?x1?a3x2?a3x3?a323??x1?a4x2?a4x3?a4当a1,a2,a3,a4满足什么条件时，方程组（1）有惟一解？无穷多解？无解？ 五．（20分）设f?X???AX是一实二次型，若有实n维向量X1,X2使得Xf?X1????f?X2???，证明：必存在实n维向量X0?0使f?X0??0。

六．设W是齐次线性方程组

?2x1?x2?x3?x4?3x5?0