数据构造考试题库(含参考答案).docx

《数据构造考试题库(含参考答案).docx》由会员分享，可在线阅读，更多相关《数据构造考试题库(含参考答案).docx（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据构造考试题库(含参考答案)第1章绪论一、选择题1.算法的计算量的大小称为计算的。【北京邮电大学2000二、320/8分】A效率B.复杂性C.现实性D.难度2.算法的时间复杂度取决于【中科院计算所1998二、12分】A问题的规模B.待处理数据的初态C.A和B3.计算机算法指的是1，它必须具备2这三个特性。(1)A计算方法B.排序方法C.解决问题的步骤序列D.调度方法(2)A可执行性、可移植性、可扩大性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性【南京理工大学1999一、12分【武汉交通科技大学1996一、14分】4一个算法应该是。【中山大学1998二、12

2、分】A程序B问题求解步骤的描绘C要知足五个基本特性DA和C.5.下面关于算法讲法错误的是【南京理工大学2000一、11.5分】A算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是一样的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的6.下面讲法错误的是【南京理工大学2000一、21.5分】(1算法原地工作的含义是指不需要任何额外的辅助空间2在一样的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法3所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界4同一个算法，实现语言的级别越高，执行效率就越低A(1)B.(1),(2)C.(1),(

3、4)D.(3)7从逻辑上能够把数据构造分为两大类。【武汉交通科技大学1996一、42分】A动态构造、静态构造B顺序构造、链式构造C线性构造、非线性构造D初等构造、构造型构造8下面与数据的存储构造无关的术语是。【北方交通大学2000二、12分】A循环队列B.链表C.哈希表D.栈9下面数据构造中，哪一个是线性构造？【北方交通大学2001一、12分】A广义表B.二叉树C.稀疏矩阵D.串10下面那一个术语与数据的存储构造无关？【北方交通大学2001一、22分】A栈B.哈希表C.线索树D.双向链表11在下面的程序段中，对x的赋值语句的频度为【北京工商大学2001一、103分】FORi:=1TOnDOFO

4、Rj:=1TOnDOx:=x+1;AO(2n)BO(n)CO(n2)DO(log2n)12程序段FORi:=n-1DOWNTO1DOFORj:=1TOiDOIFAjAj+1THENAj与Aj+1对换；其中n为正整数，则最后一行的语句频度在最坏情况下是A.OnB.O(nlogn)C.O(n3)D.O(n2)【南京理工大学1998一、1(2分)】13下面哪个数据构造不是多型数据类型【中山大学1999一、31分】A栈B广义表C有向图D字符串14下面数据构造中，是非线性数据构造【中山大学1999一、4】A树B字符串C队D栈15.下列数据中，是非线性数据构造。【北京理工大学2001六、12分】A栈B.队

5、列C.完全二叉树D.堆16连续存储设计时，存储单元的地址。【中山大学1999一、11分】A一定连续B一定不连续C不一定连续D部分连续，部分不连续17下面属于逻辑构造的是。【西安电子科技大学应用2001一、1】A顺序表B.哈希表C.有序表D.单链表二、判定题1.数据元素是数据的最小单位。()【北京邮电大学1998一、12分】【青岛大学2000一、11分】【上海交通大学1998一、1】【山东师范大学2001一、12分】2.记录是数据处理的最小单位。()【上海海运学院1998一、51分】3.数据的逻辑构造是指数据的各数据项之间的逻辑关系；()【北京邮电大学2002一、11分】4算法的优劣与算法描绘语

6、言无关，但与所用计算机有关。()【大连海事大学2001一、101分】5强健的算法不会因非法的输入数据而出现莫名其妙的状态。()【大连海事大学2001一、111分】6算法能够用不同的语言描绘，假如用C语言或PASCAL语言等高级语言来描绘，则算法实际上就是程序了。()【西安交通大学1996二、73分】7程序一定是算法。()【燕山大学1998二、22分并改错】8数据的物理构造是指数据在计算机内的实际存储形式。()【山东师范大学2001一、22分】9.数据构造的抽象操作的定义与详细实现有关。()【华南理工大学2002一、11分】10.在顺序存储构造中，有时也存储数据构造中元素之间的关系。()【华南理

7、工大学2002一、21分】11.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()【上海海运学院1999一、11分】12.数据构造的基本操作的设置的最重要的准则是，实现应用程序与存储构造的独立。()【华南理工大学2002一、51分】13.数据的逻辑构造讲明数据元素之间的顺序关系,它依靠于计算机的储存构造.()【上海海运学院1998一、11分】三、填空1数据的物理构造包括数据元素的表示和数据元素关系的表示。【燕山大学1998一、12分】2.对于给定的n个元素,能够构造出的逻辑构造有集合，线性结构，树形构造，_图状构造或网状构造_四种。【中科院计算所1999二、14分】3数据的逻辑构造是

8、指数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系。【北京邮电大学2001二、12分】4一个数据构造在计算机中的表示或称映像称为存储构造又数据的物理构造。【华中理工大学2000一、11分】5抽象数据类型的定义仅取决于它的一组_逻辑特性_，而与_在计算机内部怎样表示和实现_无关，即不管其内部构造怎样变化，只要它的_数学特性_不变，都不影响其外部使用。【山东大学2001三、32分】6数据构造中评价算法的两个重要指标是算法的时间复杂度和空间复杂度【北京理工大学2001七、12分】7.数据构造是研讨数据的_逻辑构造_和_物理构造_，以及它们之间的互相关系

9、，并对与这种构造定义相应的_操作运算_，设计出相应的_算法。【西安电子科技大学1998二、23分】8一个算法具有5个特性:有穷性、确定性、可行性，有零个或多个输入、有一个或多个输出。【华中理工大学2000一、25分】【燕山大学1998一、25分】9已知如下程序段FORi:=nDOWNTO1DO语句1BEGINx:=x+1；语句2FORj:=nDOWNTOiDO语句3y:=y+1;语句4END；语句1执行的频度为n+1；语句2执行的频度为n；语句3执行的频度为n(n+3)/2；语句4执行的频度为n(n+1)/2。【北方交通大学1999二、45分】10在下面的程序段中，对的赋值语句的频度为_1+1

10、+2+1+2+3+1+2+n=n(n+1)(n+2)/6_表示为n的函数FORi：TOnDOFORj：TOiDOFORk：1TOjDO：delta；【北京工业大学1999一、62分】11.下面程序段中带下划线的语句的执行次数的数量级是：log2n【合肥工业大学1999三、12分i：=1；WHILEi1DOi:=idiv2;14.计算机执行下面的语句时，语句s的执行次数为_(n+3)(n-2)/2_。【南京理工大学2000二、11.5分】FOR(i=l；i=i;j-)s;15.下面程序段的时间复杂度为_On_。(n1)sum=1；for(i=0;sum执行程序，f(6,4)=9。【中科院软件所1

11、997二、19分】17.在有n个选手参加的单循环赛中，总共将进行_n(n-1)/2_场比赛。【合肥工业大学1999三、82分】四、应用题1.数据构造是一门研究什么内容的学科？【燕山大学1999二、14分】2.数据元素之间的关系在计算机中有几种表示方法？各有什么特点？【燕山大学1999二、24分】3.数据类型和抽象数据类型是怎样定义的。二者有何一样和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？【北京邮电大学1994一8分】4.回答问题每题2分【山东工业大学1997一8分】1在数据构造课程中，数据的逻辑构造，数据的存储构造及数据的运算之间存在着如何的关系？2若逻辑构造

12、一样但存储构造不同，则为不同的数据构造。这样的讲法对吗？举例讲明之。3在给定的逻辑构造及其存储表示上能够定义不同的运算集合，进而得到不同的数据构造。这样讲法对吗？举例讲明之。4评价各种不同数据构造的标准是什么？5评价一个好的算法，您是从哪几方面来考虑的？【大连海事大学1996二、32分】【中山大学1998三、15分】6解释和比拟下面各组概念【华南师范大学2000一10分】1抽象数据类型及数据类型2数据构造、逻辑构造、存储构造3抽象数据类型【哈尔滨工业大学2000一、13分】4算法的时间复杂性【河海大学1998一、23分】5算法【吉林工业大学1999一、12分】6频度【吉林工业大学1999一、2

13、2分】7.根据数据元素之间的逻辑关系，一般有哪几类基本的数据构造？【北京科技大学1998一、1】【同济大学1998】8对于一个数据构造，一般包括哪三个方面的讨论？【北京科技大学1999一、12分】9.当你为解决某一问题而选择数据构造时，应从哪些方面考虑？【西安电子北京科技大学2000】10.若将数据构造定义为一个二元组D，R,讲明符号D，R应分别表示什么？【北京科技大学2001一、12分】11数据构造与数据类型有什么区别？【哈尔滨工业大学2001三、13分】12数据的存储构造由哪四种基本的存储方法实现？【山东科技大学2001一、14分】13若有100个学生，每个学生有学号，姓名，平均成绩，采用

14、什么样的数据构造最方便，写出这些构造？【山东师范大学1996二、22分】14.运算是数据构造的一个重要方面。试举一例，讲明两个数据构造的逻辑构造和存储方式完全一样，只是对于运算的定义不同。因此两个构造具有显著不同的特性，是两个不同的构造。【北京大学1998一、15分】15.在编制管理通讯录的程序时,什么样的数据构造适宜?为什么?【长沙铁道学院1998四、3(6分)】16.试举一例，讲明对一样的逻辑构造,同一种运算在不同的存储方式下实现，其运算效率不同。【北京理工大学2000三、14.5分】17.有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2n)，A2的时间复杂度为T2=

15、O(n2)，仅就时间复杂度而言，请详细分析这两个算法哪一个好。【北京航空航天大学2000二10分】18设计一数据构造，用来表示某一银行储户的基本信息：账号、姓名、开户年月日、储蓄类型、存入累加数、利息、帐面总数。【浙江大学1994一、35分】19.写出下面算法中带标号语句的频度。TYPEar=ARRAY1.nOFdatatype;PROCEDUREperm(a:ar;k,n:integer);VARx:datatype;i:integer;BEGIN1IFk=nTHENBEGIN2FORi:=1TOnDO3write(ai);writeln;ENDELSEBEGIN4FORi:=kTOnDO5

16、ai:=ai+i*i;6perm(a,k+1,n);END;END;设k的初值等于1。【北京邮电大学1997二10分】20.分析下面程序段中循环语句的执行次数。i:=0;s:=0;n:=100;REPEATi:=i+1;s:=s+10*i;UNTILNOT(iENDInc；【东南大学1998三(8分)1994二15分】22.阅读下列算法，指出算法A的功能和时间复杂性PROCEDUREA(h,g:pointer);(h,g分别为单循环链表singlelinkedcircularlist中两个结点指针)PROCEDUREB(s,q:pointer)；VARp:pointer;BEGINp:=s;W

17、HILEp.nextqDOp:=p.next;p.next:=s;END;(ofB)BEGINB(h,g);B(g,h);END;ofA【东南大学1999二10分】23.调用下列C函数f(n)或PASACAL函数f(n)回答下列问题:1试指出f(n)值的大小，并写出f(n)值的推导经过;2假定n=5，试指出f(5)值的大小和执行f(5)时的输出结果。C函数：intf(intn)inti,j，k,sum=0;for(i=l;ii-1;j-)for(k=1;kforj1tondoxx+1endend【中科院自动化研究所1995二、26分】27.斐波那契数列Fn定义如下F0=0，Fl=1，Fn=Fn

18、-1+Fn-2,n=2,3.请就此斐波那契数列，回答下列问题。(1)(7分)在递归计算Fn的时候，需要对较小的Fn-1，Fn-2，,Fl,F0准确计算多少次?(2)(5分)假如用大O表示法，试给出递归计算Fn时递归函数的时间复杂度录多少?【清华大学2000二12分】28将下列函数，按它们在n时的无穷大阶数，从小到大排序。n,n-n3+7n5,nlogn,2n/2,n3,logn,n1/2+logn,(3/2)n,n!,n2+logn【中科院计算所1995】第1章绪论二、判定题三填空题1数据元素数据元素间关系2集合线性构造树形构造图状构造或网状构造。3数据的组织形式，即数据元素之间逻辑关系的总体

19、。而逻辑关系是指数据元素之间的关联方式或称“邻接关系。4表示又称映像。51逻辑特性2在计算机内部怎样表示和实现3数学特性。6算法的时间复杂度和空间复杂度。71逻辑构造2物理构造3操作运算4算法。81有穷性2确定性3可行性。91n+12n3n(n+3)/24n(n+1)/2。101+1+2+1+2+3+1+2+n=n(n+1)(n+2)/6O(n3)11.log2n12.nlog2n13.log2n214.(n+3)(n-2)/215.O(n)16.(1)1(2)1(3)f(m,n-1)(4)n917.n(n-1)/2四应用题1数据构造是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对

20、象间的关系和施加于对象的操作等的学科。2四种表示方法1顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作如插入、删除效率较差。2链式存储方式。每个存储结点除包含数据元素信息外还包含一组至少一个指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作如插入、删除等，但存储空间开销大用于指针，另外不能折半查找等。3索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置下标或存储区间端点下标，兼有静态和动态特性。4散列存储方式。通过散列函数和解决冲突的方法，将关键

21、字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。3数据类型是程序设计语言中的一个概念，它是一个值的集合和操作的集合。如C语言中的整型、实型、字符型等。整型值的范围对详细机器都应有整数范围，其操作有加、减、乘、除、求余等。实际上数据类型是厂家提供应用户的已实现了的数据构造。“抽象数据类型ADT指一个数学模型及定义在该模型上的一组操作。“抽象的意义在于数据类型的数学抽象特性。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部怎样表示和实现无关。无论其内部构造怎样

22、变化，只要它的数学特性不变就不影响它的外部使用。抽象数据类型和数据类型本质上是一个概念。此外，抽象数据类型的范围更广，它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。使用抽象数据类型定义的软件模块含定义、表示和实现三部分，封装在一起，对用户透明提供接口，而不必了解实现细节。抽象数据类型的出现使程序设计不再是“艺术，而是向“科学迈进了一步。41数据的逻辑构造反映数据元素之间的逻辑关系即数据元素之间的关联方式或“邻接关系，数据的存储构造是数据构造在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑构造上的，和

23、存储构造无关，而运算的实现则是依靠于存储构造。2逻辑构造一样但存储不同，能够是不同的数据构造。例如，线性表的逻辑构造属于线性构造，采用顺序存储构造为顺序表，而采用链式存储构造称为线性链表。3栈和队列的逻辑构造一样，其存储表示可以一样顺序存储和链式存储，但由于其运算集合不同而成为不同的数据构造。4数据构造的评价非常复杂，能够考虑两个方面，一是所选数据构造能否准确、完好的刻划了问题的基本特征；二是能否容易实现如对数据分解能否恰当；逻辑构造的选择能否合适于运算的功能，能否有利于运算的实现；基本运算的选择能否恰当。5评价好的算法有四个方面。一是算法的正确性；二是算法的易读性；三是算法的强健性；四是算法

24、的时空效率运行。61见上面题32见上面题43见上面题34算法的时间复杂性是算法输入规模的函数。算法的输入规模或问题的规模是作为该算法输入的数据所含数据元素的数目，或与此数目有关的其它参数。有时考虑算法在最坏情况下的时间复杂度或平均时间复杂度。5算法是对特定问题求解步骤的描绘，是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有五个重要特性：有穷性、确定性、可行性、输入和输出。6频度。在分析算法时间复杂度时，有时需要估算基本操作的原操作，它是执行次数最多的一个操作，该操作重复执行的次数称为频度。7集合、线性构造、树形构造、图形或网状构造。8逻辑构造、存储构造、操作运算。9通常考虑算法所需

25、要的存储空间量和算法所需要的时间量。后者又涉及到四方面：程序运行时所需输入的数据总量，对源程序进行编译所需时间，计算机执行每条指令所需时间和程序中指令重复执行的次数。10D是数据元素的有限集合，S是D上数据元素之间关系的有限集合。11“数据构造这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。作为科学概念，目前尚无公认定义，一般以为，讨论数据构造要包括三个方面，一是数据的逻辑构造，二是数据的存储构造，三是对数据进行的操作运算。而数据类型是值的集合和操作的集合，能够看作是已实现了的数据构造，后者是前者的一种简化情况。12见上面题2。13将学号、姓名、平均成绩看成一个记录元素，含

26、三个数据项，将100个这样的记录存于数组中。因一般无增删操作，故宜采用顺序存储。typedefstructintnum;/学号charname8;/姓名floatscore;/平均成绩node；nodestudent100;14.见上面题43。15应从两方面进行讨论：如通讯录较少变动如城市私人电话号码，主要用于查询，以顺序存储较方便，既能顺序查找可以随机查找；若通讯录经常有增删操作，用链式存储构造较为适宜，将每个人的情况作为一个元素即一个结点存放一个人，设姓名作关键字，链表安排成有序表，这样可提高查询速度。16线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为On；而

27、在链式存储方式下，插入和删除时间复杂度都是O1。17对算法A1和A2的时间复杂度T1和T2取对数，得nlog2和2logn。显然，算法A2好于A1。18.structnodeintyear,month,day;typedefstructintnum;/帐号charname8;/姓名structnodedate;/开户年月日inttag;/储蓄类型，如：0-零存，1-一年定期floatput;/存入累加数；floatinterest;/利息floattotal;/帐面总数count；19(1)n(2)n+1(3)n(4)(n+4)(n-1)/2(5)(n+2)(n-1)/2(6)n-1这是一个递

28、归调用，因k的初值为1，由语句6知，每次调用k增1，故第(1)语句执行n次。2是FOR循环语句，在知足(1)的条件下执行，该语句进入循环体(3)n次，加上最后一次判定出界，故执行了n+1次。(4)也是循环语句，当k=1时判定n+1次进入循环体(5)n次，k=2时判定n次，最后一次k=n-1时判定3次，故执行次数是n+1+n+3=(n+4)(n-1)/2次。语句(5)是(4)的循环体，每次比(4)少一次判定，故执行次数是n+(n-1)+2=(n+2)(n-1)/2次。注意分析时，不要把(2)分析成n次，更不是1次。204这时i=4，s=100REPEAT语句先执行循环体，后判定条件，直到条件为真

29、时退出循环。21算法在最好情况下，即二进制数的最后一位为零时，只作一次判定，未执行循环体，赋值语句Ai执行了一次；最坏情况出如今二进制数各位均为1最高位为零，因题目假设无溢出，这时循环体执行了n-1次，时间复杂度是O(n)，循环体平均执行n/2次，时间复杂度还是O(n)。22该算法功能是将原单循环链表分解成两个单循环链表：其一包括结点h到结点g的前驱结点；另一个包括结点g到结点h的前驱结点。时间复杂度是O(n)。23第一层FOR循环判定n+1次，往下执行n次，第二层FOR执行次数为(n+(n-1)+(n-2)+1)，第三层循环体受第一层循环和第二层循环的控制，其执行次数如下表：i=123nj=

30、nnnnnj=n-1n-1n-1n-1j=333j=222j=11执行次数为(1+2+n)+(2+3+n)+n=n*n(n+1)/2-n(n2-1)/6。在n=5时，f(5)=55，执行经过中，输出结果为：sum=15,sum=29,sum=41,sum=50,sum=55每个sum=占一行,为节省篇幅，这里省去换行。24O(n2),m的值等于赋值语句m:=m+125(1)O(1)(2)O(n2)(3)O(n3)26(1)O(n)(2)O(n2)27.1由斐波那契数列的定义可得：Fn=Fn-1+Fn-2=2Fn-2+Fn-3=3Fn-3+2Fn-4=5Fn-4+3Fn-5=8Fn-5+5Fn-6=pF1+qF0