数据结构考研真题

第 5 章 数组和广义表

一、选择题

1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。【燕山大学 2001 一、2 （2分）】

A. 13 B. 33 C. 18 D. 40

2. 有一个二维数组A[1:6，0:7] 每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（①）个字节。假设存储数组元素A[1，0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是（②）。若按行存储，则A[2，4]的第一个字节的地址是（③）。若按列存储，则A[5，7]的第一个字节的地址是（④）。就一般情况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。供选择的答案：【上海海运学院 1998 二、2 （5分）】

①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120 G. 156 H. 23

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. 线性表的链接实现有利于(

第1章 绪论

一、选择题

1. 算法的计算量的大小称为计算的（ ）。【北京邮电大学2000 二、3 （20/8分）】

A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（ ）【中科院计算所 1998 二、1 （2分）】

A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2） 这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法

(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性

C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安

全性

【南京理工大学 1999 一、1（2分） 【武汉交通科技大学 1996 一、1（ 4分）】

4．一个算法应该是（ ）。【中山大学 1998 二、1（2分）】

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C.

5. 下面关于算法说法错误的

北京师范大学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，

第一章 概述 真题

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.作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为______。

哈尔滨工业大学2000年数据结构考研试题

一． 名词解释：（12分） 1． 抽象数据类型； 2． 算法的时间复杂性； 3． 散列法(hashing)； 4． 索引文件。 二． 填空：(12分)

1． 在单链表中设置头结点的作用是_________________________________。 2． n个顶点的连通无向图，其边的条数至少为________________________。 3． 线索二元树的左线索指向其_______________，右线索指向其____________。 4． 树在计算机内的表示方式有___________，_____________，________________。

5． 排序（sorting）有哪几种方法_______________，_____________，____________，_____________，____________。

三．判断下列叙述是否正确，若你认为正确，请画“ “，否则画” “。 1． 存在这样的二元树，对它采用任何次序的遍历，结果相同。（ ） 2． 二元树就是结点度为2的树。（ ）

3． 若连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ） 4

天津大学数据结构和程序设计考研真题-考研资料-笔记讲义

许多学生在考研复习的时候，都会遇到重点不明确，不知道从何复习的情况。为此，天津考研网建议，考研复习中，专业的考研复习资料，是帮助考生能够快速掌握复习重点及方法必不可少的因素，然后就是真题和讲义，可以让同学了解历年考研的出题方向和大致范围。天津考研网推出了天津大学数据结构和程序设计的考研复习资料及真题解析班，以下为详细介绍:

天津大学数据结构和程序设计考研真题等资料由天津考研网签约的天津大学计算机科学与技术学院高分考研学生历时近一月所作，该考生在考研中取得了专业课129分的好成绩并在复试中更胜一筹，该资料包含该优秀本校考生的考研经验、考研试题解题思路分析、复试流程经验介绍以及针对官方指定参考书的重难要点并根据天津大学本科授课重点整理等，从漫漫初试长路到紧张复试亮剑为各位研友提供全程考研指导攻关。

特别说明：此科目06年以前科目名称为数据结构；自06年到08年科目名称改为计算机基础（包含数据结构、程序设计、计算机原理）；自09年开始全国统考，科目名称为计算机学科专业基础综合；自2013年开始由学校自主命题，科目名称改为901数据结构与程序设计。

第一部分 由天津考研网提供的核心复习资料

[注]：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释 一、 回答下列问题：[20分] 1、 算法的定义和性质

2、 为什么说数组与广义表是线性表的推广？ 3、 什么是结构化程序设计？

4、 哈希方法的基本思想

5、 给出一不稳定排序方法名称与实例

二、 构造结果：[24分]

（1） 确定x:=x+1语句在下面程序段中的频率，要求写出分析过程。 for i:=1 to n do

for j:=1 to I do

for k:=1 to j do x:=x+1

（2） 画出对长度为8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均查找长度。

（3） 已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列．

（4） 假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为{2，3，5，7，11，4，13，15}，试为这8个字母设计哈夫曼编码．

（5） 在地址空间为0~15的散列区中，对以下关键字序列构G造哈希表，关键字序列为（Jan,Feb,Mar, Apr,May,Jun,Jul Aug,Sep,Oct,Nov,Dec），H(x)=[i/2] ，其中i