数据结构考研真题与其答案.docx
- 文档编号:9974695
- 上传时间:2023-05-22
- 格式:DOCX
- 页数:35
- 大小:39.30KB
数据结构考研真题与其答案.docx
《数据结构考研真题与其答案.docx》由会员分享,可在线阅读,更多相关《数据结构考研真题与其答案.docx(35页珍藏版)》请在冰点文库上搜索。
数据结构考研真题与其答案
.
一、选择题
1.算法的计算量的大小称为计算的(
B)。
【北京邮电大学
2000二、3
(20/8分)】
A.效率B.复杂性C.现实性D.难度
2.算法的时间复杂度取决于(C)【中科院计算所1998二、1(2分)】
A.问题的规模B.待处理数据的初态C.A和B
3.计算机算法指的是(C),它必须具备(B)这三个特性。
(1)A.计算方法B.排序方法C.解决问题的步骤序列
D.调度方法
(2)A.可执行性、可移植性、可扩充性B.可执行性、确定性、
有穷性
C.确定性、有穷性、稳定性D.易读性、稳定性、安
全性
【南京理工大学1999一、1(2分)【武汉交通科技大学1996一、
1(4分)】
4.一个算法应该是(B)。
【中山大学1998二、1(2分)】
A.程序B.问题求解步骤的描述C.要满足五个基本特性
D.A和C.
5.下面关于算法说法错误的是(D)【南京理工大学2000一、1(1.5
分)】
A.算法最终必须由计算机程序实现
B.为解决某问题的算法同为该问题编写的程序含义是相同的
C.算法的可行性是指指令不能有二义性D.以上几个都是
错误的
6.下面说法错误的是(C)【南京理工大学2000一、2(1.5分)】
(1)算法原地工作的含义是指不需要任何额外的辅助空间
(2)在相同的规模n下,复杂度O(n)的算法在时间上总是优于复杂度
n
O
(2)的算法
(3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界
(4)同一个算法,实现语言的级别越高,执行效率就越低4
A.
(1)B.
(1),
(2)C.
(1),(4)D.(3)
7.从逻辑上可以把数据结构分为(C)两大类。
【武汉交通科技大学1996
一、4(2分)】
A.动态结构、静态结构B.顺序结构、链式结构
C.线性结构、非线性结构D.初等结构、构造型结构
8.以下与数据的存储结构无关的术语是(D)【。
北方交通大学2000二、
1(2分)】
.
.
A.循环队列B.链表C.哈希表D.栈
9.以下数据结构中,哪一个是线性结构(D)?
【北方交通大学2001
一、1(2分)】
A.广义表B.二叉树C.稀疏矩阵D.串
10.以下那一个术语与数据的存储结构无关?
(A【)北方交通大学2001一、2(2分)】
A.栈B.哈希表C.线索树D.双向
链表
11.在下面的程序段中,对x的赋值语句的频度为(C)【北京工商大
学2001一、10(3分)】FORi:
=1TOnDOFORj:
=1TOnDO
x:
=x+1;
A.O(2n)
B
.O(n)C
2
D
n
.O(n)
.O(log2)
12.程序段FORi:
=n-1DOWNTO1DO
FORj:
=1TOiDO
IFA[j]>A[j+1]
THENA[j]
与A[j+1]对换;
其中n为正整数,则最后一行的语句频度在最坏情况下是(
D
)
A.O(n)
B.O(nlogn)
C.O(n
3)
D.
O(n2)
【南京理
工大学1998一、1(2分)】
13.以下哪个数据结构不是多型数据类型(D
)【中山大学
1999
一、3
(1分)】
A.栈
B
.广义表
C
.有向图
D
.字符串
14.以下数据结构中,(A
)是非线性数据结构
【中山大学
1999
一、4】
A.树
B
.字符串
C
.队
D
.栈
15.下列数据中,(C)是非线性数据结构。
【北京理工大学2001六、
1(2分)】
A.栈B.队列C.完全二叉树D.堆
16.连续存储设计时,存储单元的地址(A)。
【中山大学1999一、1(1分)】
A.一定连续B.一定不连续C.不一定连续D.部分连续,部分不连续
17.以下属于逻辑结构的是(C)。
【西安电子科技大学应用2001一、
1】
A.顺序表B.哈希表C.有序表D.单链表
.
.
二、判断题
1.数据元素是数据的最小单位。
(X)
【北京邮电大学
1998
一、1(2分)】【青岛大学
2000
一、1
(1
分)】
【上海交通大学
1998
一、1】
【山东师范大学
2001
一、1
(2
分)】
2.记录是数据处理的最小单位。
(
X)【上海海运学院1998一、5(1分)】
3.数据的逻辑结构是指数据的各数据项之间的逻辑关系;(X)【北京邮电大学2002一、1(1分)】
4.算法的优劣与算法描述语言无关,但与所用计算机有关。
(
X)
【大连海事大学
2001
一、10(1分)】
5.健壮的算法不会因非法的输入数据而出现莫名其妙的状态。
(
O)
【大连海事大学
2001
一、11(1分)】
6.算法可以用不同的语言描述,
如果用C语言或PASCAL语言等高级语言
来描述,则算法实际上就是程序了。
(X)【西安交通大学
1996二、7
(3分)】
7.程序一定是算法。
(
X)【燕山大学1998
二、2(2分)并改错】
8.数据的物理结构是指数据在计算机内的实际存储形式。
(
O)【山东师
范大学2001一、2(2分)】
9.
数据结构的抽象操作的定义与具体实现有关。
(X)
【华南理工大学
2002
一、1(1分)】
10.
在顺序存储结构中,有时也存储数据结构中元素之间的关系。
(X
)
【华南理工大学
2002
一、2(1分)】
11.
顺序存储方式的优点是存储密度大,且插入、删除运算效率高。
(
X)
【上海海运学院
1999
一、1(1分)】
12.
数据结构的基本操作的设置的最重要的准则是,
实现应用程序与存储结构的独立。
(
O)
【华南理工大学
2002
一、5(1分)】
13.
数据的逻辑结构说明数据元素之间的顺序关系
它依赖于计算机的储存结构
.(
X
)
【上海海运学院
1998
一、1(1分)】
三、填空
1.数据的物理结构包括数据元素的表示和数据元素间关系的表示。
【燕山大学1998一、1(2分)】
2.对于给定的n个元素,可以构造出的逻辑结构有集合线性结构树
形结构图状结构(或网状结构)四种。
【中科院计算所1999二、1(4分)】
3.数据的逻辑结构是指数据的组织形式,即数据元素之间逻辑关系的总体。
.
.
而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。
【北京邮电大
学2001二、1(2分)】
4.一个数据结构在计算机中表示(又称映像)称为存储结构。
【华中理工大学2000一、1(1分)】
5.抽象数据类型的定义仅取决于它的一组逻辑特性,而与在计算机内部如
何表示和实现无关,即不论其内部结构如何变化,只要它的数学特性不变,都不影响其外部使用。
【山东大学2001三、3(2分)】
6.数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度
【北京理工大学2001七、1(2分)】
7.数据结构是研讨数据的_逻辑结构和物理结构,以及它们之间的相
互关系,并对与这种结构定义相应的
操作(运算),设计出相应的算法。
【西
安电子科技大学1998
二、2(3分)】
8.一个算法具有5个特性:
(1)有穷性
(2)确定性(3)可行性,
有零个或多个输入、有一个或多个输出
。
【华中理工大学
2000一、2(5分)】【燕山大学1998
一、2(5
分)】
9.已知如下程序段
FORi:
=n
DOWNTO
1
DO
{语句1}
BEGIN
x:
=x+1;
{语句2}
FORj:
=n
DOWNTO
i
DO
{语句3}
y:
=y+1;
{语句4}
END;
语句1执行的频度为
n+1;语句2执行的频度为
n;语句
3执行的频
度为n(n+3)/2;语句4执行的频度为
n(n+1)/2。
【北方交通大学
1999二、
4(5分)】
10.在下面的程序段中,对x的赋值语句的频度为
1+(1+2++(1+2+3)
+⋯+(1+2+⋯+n)=n(n+1)(n+2)/6
3
O(n
)
(表示为n的函数)
FOR
i:
=1TOn
DO
FOR
j:
=1
TOi
DO
FOR
k:
=1TO
j
DO
x:
=x+delta
;
【北京工业大学
1999
一、6(2分)】
11.下面程序段中带下划线的语句的执行次数的数量级是:
log2n【合肥工业大学
1999三、1(
分)】
i:
=1;WHILEi : =i*2; . . 12. 下面程序段中带下划线的语句的执行次数的数量级是 ( nlog2n)。 【合肥工业大学 2000 三、1(2分)】 i: =1; WHILEi =1TOnDOx: =x+1;i: =i*2END ; 13. 下面程序段中带有下划线的语句的执行次数的数量级是 (log2n2 ) 【合肥工业大学 2001 三、1(2分)】 i: =n*n WHILEi<>1 DOi: =idiv2; 14. 计算机执行下面的语句时,语句 s的执行次数为 (n+3)(n-2)/2 。 【南京理工大学 2000二、1(1.5分)】 FOR(i=l ;i ;i++) FOR(j=n;j>=i;j--) s; 15. 下面程序段的时间复杂度为___O(n)_____。 (n>1) sum=1 ; for(i=0;sum 【南京理工大学 2001 二、1 (2分)】 16.设m.n均为自然数,m可表示为一些不超过n的自然数之和,f(m,n)为这种表示方式的数目。 例f(5,3)=5,有5种表示方式: 3+2,3+1+1,2+2+1,2+1+1+1,1+1+1+1+1。 ①以下是该函数的程序段,请将未完成的部分填入,使之完整 intf(m,n) intm,n; {if(m==1) return1; if(n==1){ return1;} if(m {returnf(m,m);} if(m==n) {return1+f(m,n-1);} returnf(m.n-1)+f(m-n,n); } ②执行程序,f(6,4)=9。 【中科院软件所1997二、1(9分)】 17.在有n个选手参加的单循环赛中,总共将进行n(n-1)/2 场比赛。 【合肥工业大学1999三、8(2分)】四、应用题 1.数据结构是一门研究什么内容的学科? 【燕山大学1999二、1(4分)】 . . 数据结构是一门研究在非数值计算的程序设计问题中,计算机的操作对象及对象间的关系和施加于对象的操作等的学科。 2.数据元素之间的关系在计算机中有几种表示方法? 各有什么特点? 【燕山大学1999二、2(4分)】 四种表示方法 (1)顺序存储方式。 数据元素顺序存放,每个存储结点只含一个元素。 存储位置反映数据元素间的逻辑关系。 存储密度大,但有些操作(如插入、 删除)效率较差。 (2)链式存储方式。 每个存储结点除包含数据元素信息外还包含一组(至 少一个)指针。 指针反映数据元素间的逻辑关系。 这种方式不要求存储空 间连续,便于动态操作(如插入、删除等),但存储空间开销大(用于指针),另外不能折半查找等。 (3)索引存储方式。 除数据元素存储在一地址连续的内存空间外,尚需建立一个索引表,索引表中索引指示存储结点的存储位置(下标)或存储 区间端点(下标),兼有静态和动态特性。 (4)散列存储方式。 通过散列函数和解决冲突的方法,将关键字散列在连续的有限的地址空间内,并将散列函数的值解释成关键字所在元素的存 储地址,这种存储方式称为散列存储。 其特点是存取速度快,只能按关键字随机存取,不能顺序存取,也不能折半存取。 2.数据类型和抽象数据类型是如何定义的。 二者有何相同和不同之处,抽象数据类型的主要特点是什么? 使用抽象数据类型的主要好处是什么? 【北京邮电大学1994一(8分)】 数据类型是程序设计语言中的一个概念,它是一个值的集合和操作的 集合。 如C语言中的整型、实型、字符型等。 整型值的范围(对具体机器都应有整数范围),其操作有加、减、乘、除、求余等。 实际上数据类型是 厂家提供给用户的已实现了的数据结构。 “抽象数据类型(ADT)”指一个数学模型及定义在该模型上的一组操作。 “抽象”的意义在于数据类型的数学抽象特性。 抽象数据类型的定义仅取决于它的逻辑特性,而与其在计算 机内部如何表示和实现无关。 无论其内部结构如何变化,只要它的数学特性不变就不影响它的外部使用。 抽象数据类型和数据类型实质上是一个概念。 此外,抽象数据类型的范围更广,它已不再局限于机器已定义和实现的数据类型,还包括用户在设计软件系统时自行定义的数据类型。 使用抽象数据类型定义的软件模块含定义、表示和实现三部分,封装在一起,对 用户透明(提供接口),而不必了解实现细节。 抽象数据类型的出现使程序设计不再是“艺术”,而是向“科学”迈进了一步。 4.回答问题(每题2分)【山东工业大学1997一(8分)】 . . (1)在数据结构课程中,数据的逻辑结构,数据的存储结构及数据的运算之间存在着怎样的关系? 数据的逻辑结构反映数据元素之间的逻辑关系(即数据元素之间的关 联方式或“邻接关系”),数据的存储结构是数据结构在计算机中的表示,包括数据元素的表示及其关系的表示。 数据的运算是对数据定义的一组操作,运算是定义在逻辑结构上的,和存储结构无关,而运算的实现则是依赖于存储结构。 (2)若逻辑结构相同但存储结构不同,则为不同的数据结构。 这样的说法对吗? 举例说明之。 逻辑结构相同但存储不同,可以是不同的数据结构。 例如,线性表的逻辑结构属于线性结构,采用顺序存储结构为顺序表,而采用链式存储结构称为线性链表。 (3)在给定的逻辑结构及其存储表示上可以定义不同的运算集合,从 而得到不同的数据结构。 这样说法对吗? 举例说明之。 栈和队列的逻辑结构相同,其存储表示也可相同(顺序存储和链式存储),但由于其运算集合不同而成为不同的数据结构。 (4)评价各种不同数据结构的标准是什么? 数据结构的评价非常复杂,可以考虑两个方面,一是所选数据结构是否准确、完整的刻划了问题的基本特征;二是是否容易实现(如对数据分解是 否恰当;逻辑结构的选择是否适合于运算的功能,是否有利于运算的实现; 基本运算的选择是否恰当。 ) 5.评价一个好的算法,您是从哪几方面来考虑的? 评价好的算法有四个方面。 一是算法的正确性;二是算法的易读性;三是 算法的健壮性;四是算法的时空效率(运行)。 【大连海事大学1996二、3(2分)】【中山大学1998三、1(5分)】 6.解释和比较以下各组概念【华南师范大学2000一(10分)】 (1)抽象数据类型及数据类型 (2)数据结构、逻辑结构、存储结构 (3)抽象数据类型【哈尔滨工业大学2000一、1(3分)】 (4)算法的时间复杂性【河海大学1998一、2(3分)】 (5)算法【吉林工业大学1999一、1(2分)】 (6)频度【吉林工业大学1999一、2(2分)】 (1)见上面题3 (2)见上面题4(3)见上面题3 (4)算法的时间复杂性是算法输入规模的函数。 算法的输入规模或问题的规模是作为该算法输入的数据所含数据元素的数目,或与此数目有关的 其它参数。 有时考虑算法在最坏情况下的时间复杂度或平均时间复杂度。 (5)算法是对特定问题求解步骤的描述,是指令的有限序列,其中每一 . . 条指令表示一个或多个操作。 算法具有五个重要特性: 有穷性、确定性、可行性、输入和输出。 (6)频度。 在分析算法时间复杂度时,有时需要估算基本操作的原操作,它是执行次数最多的一个操作,该操作重复执行的次数称为频度。 6.根据数据元素之间的逻辑关系,一般有哪几类基本的数据结构? 集合、线性结构、树形结构、图形或网状结构。 【北京科技大学1998一、1】【同济大学1998】 8.对于一个数据结构,一般包括哪三个方面的讨论? 【北京科技大学1999 一、1(2分)】 逻辑结构、存储结构、操作(运算)。 9.当你为解决某一问题而选择数据结构时,应从哪些方面考虑? 【西安电子北京科技大学2000】 通常考虑算法所需要的存储空间量和算法所需要的时间量。 后者又涉及 到四方面: 程序运行时所需输入的数据总量,对源程序进行编译所需时间, 计算机执行每条指令所需时间和程序中指令重复执行的次数。 10.若将数据结构定义为一个二元组(D,R),说明符号D,R应分别表示 什么? 【北京科技大学2001一、1(2分)】 D是数据元素的有限集合,S是D上数据元素之间关系的有限集合。 11.数据结构与数据类型有什么区别? 【哈尔滨工业大学2001三、1(3 分)】 “数据结构”这一术语有两种含义,一是作为一门课程的名称;二是作为 一个科学的概念。 作为科学概念,目前尚无公认定义,一般认为,讨论数 据结构要包括三个方面,一是数据的逻辑结构,二是数据的存储结构,三 是对数据进行的操作(运算)。 而数据类型是值的集合和操作的集合,可以看作是已实现了的数据结构,后者是前者的一种简化情况。 12.数据的存储结构由哪四种基本的存储方法实现? 【山东科技大学2001一、1(4分)】 12.见上面题2。 13.若有100个学生,每个学生有学号,姓名,平均成绩,采用什么样的 数据结构最方便,写出这些结构? 【山东师范大学1996二、2(2分)】 将学号、姓名、平均成绩看成一个记录(元素,含三个数据项),将 100个这样的记录存于数组中。 因一般无增删操作,故宜采用顺序存储。 typedefstruct {intnum;//学号 charname[8];//姓名 . . floatscore;/平均成绩 }node; nodestudent[100]; 14.运算是数据结构的一个重要方面。 试举一例,说明两个数据结构的逻辑结构和存储方式完全相同,只是对于运算的定义不同。 因而两个结构具有显著不同的特性,是两个不同的结构。 【北京大学1998一、1(5分)】见上面题4(3)。 15.在编制管理通讯录的程序时,什么样的数据结构合适? 为什么? 【长沙铁道学院1998四、3(6分)】 应从两方面进行讨论: 如通讯录较少变动(如城市私人电话号码),主要用于查询,以顺序存储较方便,既能顺序查找也可随机查找;若通讯录 经常有增删操作,用链式存储结构较为合适,将每个人的情况作为一个元 素(即一个结点存放一个人),设姓名作关键字,链表安排成有序表,这样可提高查询速度。 16.试举一例,说明对相同的逻辑结构,同一种运算在不同的存储方式下实现,其运算效率不同。 【北京理工大学2000三、1(4.5分)】 线性表中的插入、删除操作,在顺序存储方式下平均移动近一半的元素,时间复杂度为O(n);而在链式存储方式下,插入和删除时间复杂度都是O (1)。 17.有实现同一功能的两个算法A1和A2,其中A1的时间复杂度为 Tl=O(2n),A2的时间复杂度为T2=O(n2),仅就时间复杂度而言,请具体分析这两个算法哪一个好。 【北京航空航天大学2000二(10分)】 对算法A1和A2的时间复杂度T1和T2取对数,得nlog2和2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 考研 与其 答案