数据结构考研习题集

第1章 绪论一、选择题1.算法的计算量的大小称为计算的()。【北京邮电大学2 0 0 0 二、3 (2 0/8分】A.效率 B.复杂性 C.现实性 D.难度2.算法的时间复杂度取决于()【中科院计算所1 9 9 8二、1 (2 分)】A.问题的规模 B.待处理数据的初态 C.A和 B3.计算机算法指的是(1),它必须具备(2)(1)A.计算方法 B.排序方法(2)A.可执行性、可移植性、可扩充性C.确定性、有穷性、稳定性这三个特性。C.解决问题的步骤序列 D.调度方法B.可执行性、确定性、有穷性D.易读性、稳定性、安全性【南京理工大学1 9 9 9 一、1 (2 分)【武汉交通科技大学1 9 9 6 一、1 (4分】4 .一个算法应该是()。【中山 大 学 1 9 9 8二、1 (2 分】A.程序 B.问题求解步骤的描述 C.要满足五个基本特性 D.A和 C.5 .下面关于算法说法错误的是()【南京理工大学2 0 0 0 一、1 (1.5 分】A.算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性 D.以上几个都是错误的6 .下面说法错误的是()【南京理工大学2 0 0 0 一、2 (1.5 分】(1)算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度0(2”)的算法(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界(4)同一个算法，实现语言的级别越高，执行效率就越低A.(1)B.(1),(2)C.(1),(4)D.(3)7 .从逻辑上可以把数据结构分为()两大类。【武汉交通科技大学1 9 9 6 一、4 (2 分】A.动态结构、静态结构 B.顺序结构、链式结构C.线性结构、非线性结构 D.初等结构、构造型结构8.以下与数据的存储结构无关的术语是()。【北方交通大学2 0 0 0 二、1 (2 分】A.循环队列 B.链表 C.哈希表 D.栈9 .以下数据结构中，哪一个是线性结构()？【北方交通大学2 0 0 1 一、1 (2 分】A.广义表 B.二叉树 C.稀疏矩阵 D.串1 0 .以下那一个术语与数据的存储结构无关？()【北方交通大学2 0 0 1 一、2 (2 分】A.栈 B.哈希表 C.线索树 D.双向链表1 1 .在下面的程序段中，对 x的赋值语句的频度为()【北京工商大学2 0 0 1 一、1 0 (3 分】F O R i:=l T O n D OF O R j:=l T O n D Ox:=x+l;A.0(2 n)B.0(n)C.0(n2)D.0(l o g2n)1 2 .程序段 F O R i:=n-l D O W N T O 1 D OF O R j:=l T O i D OI F A j A j+l T H E N A j 与 A j+1 对换；其 中 n为正整数，则最后一行的语句频度在最坏情况下是()A.0(n)B.0(n l o g n)C.0(n3)D.0(n2)【南京理工大学 1 998、1(2 分)】1 3 .以下哪个数据结构不是多型数据类型()【中山 大 学 1 999 一、3 (1 分)】A.栈 B.广义表 C.有向图 D.字符串1 4 .以下数据结构中，()是非线性数据结构【中山 大 学 1 999 一、4 A.树 B.字符串 C.队 D.栈1 5 .下列数据中，()是非线性数据结构。【北京理工大学2 001 六、1 (2 分)】A.栈 B.队列 C.完全二叉树 D.堆1 6 .连续存储设计时，存储单元的地址（）。【中山 大 学 1 999 一、1 （1 分】A.一 定 连 续 B.一 定 不 连 续 C.不 一 定 连 续 D.部分连续，部分不连续1 7 .以下属于逻辑结构的是（）。【西安电子科技大学应用2 001 一、1】A.顺序表 B.哈希表 C.有序表 D.单链表二、判断题1 .数据元素是数据的最小单位。（）【北京邮电大学1 998 一、1 （2分）】【青岛 大 学 2 000、1 （1 分】【上海交通大学1 998 一、1】【山东师范大学2 001 一、1 （2分）】2 .记录是数据处理的最小单位。（）【上海海运学院1 998 一、5 （1 分】3 .数据的逻辑结构是指数据的各数据项之间的逻辑关系；（）【北京邮电大学2 002 、1 （1 分】4 .算法的优劣与算法描述语言无关，但与所用计算机有关。（）【大连海事大学2 001 一、1 0（1 分】5 .健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（）【大连海事大学2 001 一、1 1 （1 分】6 .算法可以用不同的语言描述，如果用C语言或P A SC A L 语言等高级语言来描述，则算法实际上就是程序了。（）【西安交通大学1 996 二、7 （3 分）】7 .程序一定是算法。（）【燕山大学1 998二、2 （2分）并改错】8.数据的物理结构是指数据在计算机内的实际存储形式。（）【山东师范大学2 001 、2 （2分）】9.数据结构的抽象操作的定义与具体实现有关。（）【华南理工大学2 002 一、1 （1 分】1 0.在顺序存储结构中，有时也存储数据结构中元素之间的关系。（）【华南理工大学2 002 一、2 （1 分】1L顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）【上海海运学院1 999 一、1 （1 分】1 2 .数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。（）【华南理工大学2 002 一、5 （1 分】1 3 .数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的储存结构.（）【上海海运学院1 998 一、1 （1 分】三、填空1 .数据的物理结构包括 的表示和 的表示。【燕 山 大 学 1 998 一、1 （2 分】2 .对于给定的n个元素，可以构造出的逻辑结构有（1）,，（4）四种。【中科院计算所1 9 9 9 二、1 （4分）】3 .数 据 的 逻 辑 结 构 是 指。【北京邮电大学2 001 二、1 （2分】4 .一个数据结构在计算机中 称为存储结构。【华中理工大学2 000 一、1 （1 分】5 .抽象数据类型的定义仅取决于它的一组（1）,而 与（2）无关,即不论其内部结构如何变化，只 要 它 的（3）不变，都不影响其外部使用。【山东 大 学 2 001 三、3 （2分】6 .数 据 结 构 中 评 价 算 法 的 两 个 重 要 指 标 是【北京理工大学2 001 七、1 （2分）】7 .数据结构是研讨数据的（1）和（2）,以及它们之间的相互关系，并对与这种结构定义相应的（3）,设计出相应的（4）。【西安电子科技大学1 9 9 8 二、2 （3 分】8 .一个算法具有5个特性：（1）、（3）,有零个或多个输入、有一个或多个输出。【华中理工大学2 000 一、2 （5分）】【燕山 大 学 1 9 9 8 一、2 （5分】9 .已知如下程序段FOR i:=n DOWNTO 1 DO 语句 1BEGINx:=x+l；语句2 FORj:=n DOWNTO i DO 语句 3 y：=y+l;语句4 END；语 句 1 执 行 的 频 度 为（1）；语句2执 行 的 频 度 为（2）；语句3执 行 的 频 度 为（3）；语句4执行的频度为（4）。【北方交通大学1 9 9 9 二、4 （5分】1 0.在下面的程序段中，对 x的赋值语句的频度为_ _ _ _（表示为n的函数）F O R i：=1 T O n D OF O R j：=1 T O i D OF O R k：=1 T O j D Ox ：=x +d e l t a；【北京工业大学1 9 9 9 一、6 (2 分】1 1 .下面程序段中带下划线的语句的执行次数的数量级是：【合肥工业大学1 9 9 9 三、1 (2 分】i：=1；W H I L E i n D O i：=i*2;1 2 .下面程序段中带下划线的语句的执行次数的数量级是(【合肥工业大学2 000三、1 (2 分】i:=l;W H I L E i n B E G I N F O R j:=l T O n D O x:=x+l;i:=i*2 E N D；1 3 .下面程序段中带有下划线的语句的执行次数的数量级是()【合肥工业大学2 001 三、1 (2 分】i：=n*n W H I L E i O l D O i:=i d i v 2;1 4 .计算机执行下面的语句时，语句s的执行次数为。【南京理工大学2 000二、1 (L 5 分】F O R(i=l；i =i;j)s .1 5 .下面通序段的时间复杂度为 o (n l)s u m=l；f o r (i=0;s u m n;i+)s u m+=l;【南京理工大学 2 001 二、1 (2 分】1 6 .设 m.n 均为自然数，m可表示为一些不超过n的自然数之和，f (m,n)为这种表示方式的数目。例 f(5,3)=5,有 5种表示方式：3+2,3+1+1,2+2+1,2+1+1+1,l+1+l+l+l o以下是该函数的程序段，请将未完成的部分填入，使之完整i n t f (m,n)i n t m,n;i f(m=l)r e t u r n (1);i f(n=l)r e t u r n (2);)i f(m n)r e t u r n f (m,m);i f (m=n)r e t u r n 1+(3);r e t u r n f (m.n-1)+f (m-n,(4);)执行程序，f (6,4)=。【中科院软件所1 9 9 7 二、1 (9 分】1 7 .在有n个选手参加的单循环赛中，总共将进行_ _ _ _ 场比赛。【合肥工业大学1 9 9 9 三、8 (2 分】四、应用题1 .数据结构是一门研究什么内容的学科？【燕山 大 学 1 9 9 9 二、1 (4 分】2 .数据元素之间的关系在计算机中有几种表示方法？各有什么特点？【燕山大学1 9 9 9 二、2 (4 分】3 .数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？【北京邮电大学1 9 9 4 一(8 分】4 .回答问题(每题2分)【山东工业大学1 9 9 7 一(8 分】(1)在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？(2)若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。(3)在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。(4)评价各种不同数据结构的标准是什么？5 .评价一个好的算法，您是从哪几方面来考虑的？【大连海事大学1 9 9 6 二、3 (2 分)】【中山 大 学 1 9 9 8 三、1 (5 分】6 .解释和比较以下各组概念【华南师范大学2 0 0 0 一(1 0 分)】(1)抽象数据类型及数据类型(2)数据结构、逻辑结构、存储结构(3)抽象数据类型【哈尔滨工业大学2 0 0 0 一、1 (3 分】(4)算法的时间复杂性【河海 大 学 1 9 9 8 一、2 (3 分)】(5)算 法【吉林工业大学1 9 9 9 一、1 (2 分】(6)频 度【吉林工业大学1 9 9 9 一、2 (2 分】7 .根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？【北京科技大学1 9 9 8 一、1】【同济大学1 9 9 8 8 .对于一个数据结构，一般包括哪三个方面的讨论？【北京科技大学1 9 9 9 一、1 (2 分)】9 .当你为解决某一问题而选择数据结构时，应从哪些方面考虑？【西安电子北京科技大学2 0 0 0 1 0 .若将数据结构定义为一个二元组(D,R),说明符号D,R应分别表示什么？【北京科技大学2 0 0 1 一、1 (2 分】1 1 .数据结构与数据类型有什么区别？【哈尔