1、计算机专业基础综合数据结构（概论）历年真题试卷汇编 3 及答案解析(总分：70.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。【2011 年全国硕士研究生入学计算机学科专业基础综合试题】简称【201 1 年全国试题 1(2 分)】 x=2； while(x *x；（分数：2.00）A.O(log 2 n)B.O(n)C.O(nlog 2 n)D.O(n 2 )2.求整数 n(n0)阶乘的算法如下，其时间复杂度是( )。【2012 年全国试题 1(2 分)】int fact(int n)if(n
2、=i) return i；return n*fact(n 一 1)；（分数：2.00）A.O(log 2 n)B.O(n)C.O(nlog 2 n)D.O(n 2 )3.已知两个长度分别为 m 和 n 的升序链表，若将它们合并为一个长度为 m+n 的降序链表，则最坏情况下的时间复杂度是( )。【2013 年全国试题 1(2)分】（分数：2.00）A.O(n)B.O(mn)C.O(min(m，n)D.O(max(m，n)4.下列程序段的时间复杂度是( )。【2014 年全国试题 1(2 分)】count=0;for(k=1；k=n；k*=2)for(j=1；j=n；j+)count+；（分数：2
3、.00）A.O(log 2 n)B.O(n)C.O(nlog 2 n)D.O(n 2 )5.在数据结构中，数据的最小单位是( )。【北京理工大学 2006 九、1(1 分)】（分数：2.00）A.数据元素B.字节C.数据项D.结点6.在数据结构中，数据的基本单位是( )。【北京理工大学 2004 五、1(1 分)】（分数：2.00）A.数据项B.数据类型C.数据元素D.数据变量7.数据对象是指( )。【北京工业大学 2005 一、1(2 分)】（分数：2.00）A.描述客观事物且由计算机处理的数值、字符等符号的总称B.数据的基本单位C.性质相同的数据元素的集合D.相互之间存在一种或多种特定关系
4、的数据元素的集合8.以下说法正确的是( )。【北京理工大学 2006 五、2(1 分)】（分数：2.00）A.数据元素是数据的最小单位B.数据项是数据的基本单位C.数据结构是带有结构的数据元素的集合D.数据结构是带有结构的各数据项集合9.数据结构研究的内容涉及( )。【武汉理工大学 2004 一、1(3 分)】（分数：2.00）A.数据如何组织B.数据如何存储C.数据的运算如何实现D.算法用什么语言来描述10.在定义 ADT 时，除数据对象和数据关系外，还需说明( )。【北京理工大学 2005 一、2(1 分)】（分数：2.00）A.数据元素B.算法C.基本操作D.数据项11.在数据结构中，从
5、逻辑上可以将之分为( )。【中南大学 2005 一、1(2 分)】（分数：2.00）A.动态结构和静态结构B.紧凑结构和非紧凑结构C.内部结构和外部结构D.线性结构和非线性结构12.从逻辑上可以把数据结构分为( )两大类。【电子科技大学 2013 二、1(2 分)】（分数：2.00）A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构13.数据结构中数据元素之间的逻辑关系被称为( )。【北京理工大学 2005 一、1(1 分)】（分数：2.00）A.数据的存储结构B.数据的基本操作C.程序的算法D.数据的逻辑结构14.以下与数据的存储结构无关的术语是(
6、)。【北方交通大学 2000 二、1(2 分)】（分数：2.00）A.循环队列B.链表C.哈希表D.栈15.以下数据结构中，哪一个是线性结构?( )【北方交通大学 2001 一、1(2 分)】（分数：2.00）A.广义表B.二叉树C.稀疏矩阵D.串二、填空题(总题数：10，分数：20.00)16.在数据结构中，数据的逻辑结构分(1)和(2)。【暨南大学 2011 二、1(2 分)】（分数：2.00）_17.链接存储的特点是利用_来表示数据元素之间的逻辑关系。【北京邮电大学 2006 一、1(2 分)】（分数：2.00）_18.数据的物理结构包括_的表示和_的表示。【燕山大学 1998 一、1(
7、2 分)】（分数：2.00）_19.对于给定的 n 个元素，可以构造出的逻辑结构有(1)，(2)，(3)，(4)四种。【中科院计算所 1999 二、1(4 分)】（分数：2.00）_20.数据结构由数据的_、_和_三部分组成。【北京邮电大学 2004 二、1(2分)】（分数：2.00）_21.一个数据结构在计算机中的_称为存储结构。【华中理工大学 2000 一、1(1 分)】（分数：2.00）_22.数据的逻辑结构是指_。【北京邮电大学 2001 二、l(2 分)】（分数：2.00）_23.数据结构是研讨数据的(1)和(2)，以及它们之间的相互关系，并对与这种结构定义相应的(3)，设计出相应的
8、(4)。【西安电子科技大学 1998 二、2(3 分)】（分数：2.00）_24.一个算法具有 5 个特性：(1)、(2)、(3)、有零个或多个输入、有一个或多个输出。【华中理工大学2000 一、2(5 分)】【燕山大学 1998 一、2(5 分)】（分数：2.00）_25.抽象数据类型的定义仅取决于它的一组(1)，而与(2)无关，即不论其内部结构如何变化，只要它的(3)不变，都不影响其外部使用。【山东大学 2001 三、3(2 分)】（分数：2.00）_三、判断题(总题数：10，分数：20.00)26.数据项是数据的最小单位。( )【北京邮电大学 2005 二、1(1 分)】（分数：2.00
9、）A.正确B.错误27.数据元素是数据的最小单位。( )【北京邮电大学 1998 一、1(2 分)】（分数：2.00）A.正确B.错误28.每种数据结构都应具备三种基本运算：插入、删除和查找。( )【吉林大学 2007 一、2(1 分)】（分数：2.00）A.正确B.错误29.顺序存储结构要求连续的存储区域，在存储管理上不够灵活，因此不常用。( )【哈尔滨工程大学2004】（分数：2.00）A.正确B.错误30.数据的逻辑结构是指数据的各数据项之间的逻辑关系。( )【北京邮电大学 2002 一、1(1 分)】（分数：2.00）A.正确B.错误31.数据结构概念包括数据之间的逻辑结构、数据在计算
10、机中的存储方式和数据的运算三个方面。( )【吉林大学 2006 一、4(1 分)】（分数：2.00）A.正确B.错误32.数据的逻辑结构与数据元素本身的内容和形式无关。( )【南京理工大学 2004 二、1(1 分)】（分数：2.00）A.正确B.错误33.算法和程序没有区别，在数据结构中二者是通用的。( )【暨南大学 2010 三、11(1 分)】（分数：2.00）A.正确B.错误34.构成数据的最小单位是数据元素。( )【武汉大学 2005 一、1(2 分)】（分数：2.00）A.正确B.错误35.数据元素可以由类型互不相同的数据项构成。( )【武汉大学 2004 一、1(2 分)】（分数
11、：2.00）A.正确B.错误计算机专业基础综合数据结构（概论）历年真题试卷汇编 3 答案解析(总分：70.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。【2011 年全国硕士研究生入学计算机学科专业基础综合试题】简称【201 1 年全国试题 1(2 分)】 x=2； while(x *x；（分数：2.00）A.O(log 2 n) B.O(n)C.O(nlog 2 n)D.O(n 2 )解析：2.求整数 n(n0)阶乘的算法如下，其时间复杂度是( )。【2012 年全国试题 1(2 分)】in
12、t fact(int n)if(n=i) return i；return n*fact(n 一 1)；（分数：2.00）A.O(log 2 n)B.O(n) C.O(nlog 2 n)D.O(n 2 )解析：3.已知两个长度分别为 m 和 n 的升序链表，若将它们合并为一个长度为 m+n 的降序链表，则最坏情况下的时间复杂度是( )。【2013 年全国试题 1(2)分】（分数：2.00）A.O(n)B.O(mn)C.O(min(m，n)D.O(max(m，n) 解析：4.下列程序段的时间复杂度是( )。【2014 年全国试题 1(2 分)】count=0;for(k=1；k=n；k*=2)fo
13、r(j=1；j=n；j+)count+；（分数：2.00）A.O(log 2 n)B.O(n)C.O(nlog 2 n) D.O(n 2 )解析：5.在数据结构中，数据的最小单位是( )。【北京理工大学 2006 九、1(1 分)】（分数：2.00）A.数据元素B.字节C.数据项 D.结点解析：6.在数据结构中，数据的基本单位是( )。【北京理工大学 2004 五、1(1 分)】（分数：2.00）A.数据项B.数据类型C.数据元素 D.数据变量解析：7.数据对象是指( )。【北京工业大学 2005 一、1(2 分)】（分数：2.00）A.描述客观事物且由计算机处理的数值、字符等符号的总称B.数
14、据的基本单位C.性质相同的数据元素的集合 D.相互之间存在一种或多种特定关系的数据元素的集合解析：8.以下说法正确的是( )。【北京理工大学 2006 五、2(1 分)】（分数：2.00）A.数据元素是数据的最小单位B.数据项是数据的基本单位C.数据结构是带有结构的数据元素的集合 D.数据结构是带有结构的各数据项集合解析：9.数据结构研究的内容涉及( )。【武汉理工大学 2004 一、1(3 分)】（分数：2.00）A.数据如何组织 B.数据如何存储 C.数据的运算如何实现 D.算法用什么语言来描述解析：10.在定义 ADT 时，除数据对象和数据关系外，还需说明( )。【北京理工大学 2005
15、 一、2(1 分)】（分数：2.00）A.数据元素B.算法C.基本操作 D.数据项解析：11.在数据结构中，从逻辑上可以将之分为( )。【中南大学 2005 一、1(2 分)】（分数：2.00）A.动态结构和静态结构B.紧凑结构和非紧凑结构C.内部结构和外部结构D.线性结构和非线性结构 解析：解析：数据的逻辑结构还可以分为：集合、线性结构、树形结构、图形或网状结构。12.从逻辑上可以把数据结构分为( )两大类。【电子科技大学 2013 二、1(2 分)】（分数：2.00）A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构 D.初等结构、构造型结构解析：13.数据结构中数据元素
16、之间的逻辑关系被称为( )。【北京理工大学 2005 一、1(1 分)】（分数：2.00）A.数据的存储结构B.数据的基本操作C.程序的算法D.数据的逻辑结构 解析：14.以下与数据的存储结构无关的术语是( )。【北方交通大学 2000 二、1(2 分)】（分数：2.00）A.循环队列B.链表C.哈希表D.栈 解析：15.以下数据结构中，哪一个是线性结构?( )【北方交通大学 2001 一、1(2 分)】（分数：2.00）A.广义表B.二叉树C.稀疏矩阵D.串 解析：二、填空题(总题数：10，分数：20.00)16.在数据结构中，数据的逻辑结构分(1)和(2)。【暨南大学 2011 二、1(2
17、 分)】（分数：2.00）_正确答案：(正确答案：(1)线性结构 (2)非线性结构)解析：17.链接存储的特点是利用_来表示数据元素之间的逻辑关系。【北京邮电大学 2006 一、1(2 分)】（分数：2.00）_正确答案：(正确答案：指针)解析：18.数据的物理结构包括_的表示和_的表示。【燕山大学 1998 一、1(2 分)】（分数：2.00）_正确答案：(正确答案：数据元素；数据元素间关系)解析：19.对于给定的 n 个元素，可以构造出的逻辑结构有(1)，(2)，(3)，(4)四种。【中科院计算所 1999 二、1(4 分)】（分数：2.00）_正确答案：(正确答案：(1)集合 (2)线性
18、结构 (3)树形结构 (4)图状结构或网状结构)解析：20.数据结构由数据的_、_和_三部分组成。【北京邮电大学 2004 二、1(2分)】（分数：2.00）_正确答案：(正确答案：逻辑结构；存储结构；运算)解析：21.一个数据结构在计算机中的_称为存储结构。【华中理工大学 2000 一、1(1 分)】（分数：2.00）_正确答案：(正确答案：表示(又称映像)解析：22.数据的逻辑结构是指_。【北京邮电大学 2001 二、l(2 分)】（分数：2.00）_正确答案：(正确答案：数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。)解析：23.数据
19、结构是研讨数据的(1)和(2)，以及它们之间的相互关系，并对与这种结构定义相应的(3)，设计出相应的(4)。【西安电子科技大学 1998 二、2(3 分)】（分数：2.00）_正确答案：(正确答案：(1)逻辑结构 (2)物理结构 (3)操作(运算) (4)算法)解析：24.一个算法具有 5 个特性：(1)、(2)、(3)、有零个或多个输入、有一个或多个输出。【华中理工大学2000 一、2(5 分)】【燕山大学 1998 一、2(5 分)】（分数：2.00）_正确答案：(正确答案：(1)有穷性 (2)确定性 (3)可行性)解析：25.抽象数据类型的定义仅取决于它的一组(1)，而与(2)无关，即不
20、论其内部结构如何变化，只要它的(3)不变，都不影响其外部使用。【山东大学 2001 三、3(2 分)】（分数：2.00）_正确答案：(正确答案：(1)逻辑特性 (2)在计算机内部如何表示和实现 (3)数学特性)解析：三、判断题(总题数：10，分数：20.00)26.数据项是数据的最小单位。( )【北京邮电大学 2005 二、1(1 分)】（分数：2.00）A.正确 B.错误解析：解析：数据有三个层次：数据，数据元素，数据项。数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数据元素是数据的基本单位，数据项是数据的最小不可分割单位。27.数
21、据元素是数据的最小单位。( )【北京邮电大学 1998 一、1(2 分)】（分数：2.00）A.正确B.错误 解析：28.每种数据结构都应具备三种基本运算：插入、删除和查找。( )【吉林大学 2007 一、2(1 分)】（分数：2.00）A.正确B.错误 解析：29.顺序存储结构要求连续的存储区域，在存储管理上不够灵活，因此不常用。( )【哈尔滨工程大学2004】（分数：2.00）A.正确B.错误 解析：30.数据的逻辑结构是指数据的各数据项之间的逻辑关系。( )【北京邮电大学 2002 一、1(1 分)】（分数：2.00）A.正确B.错误 解析：31.数据结构概念包括数据之间的逻辑结构、数据
22、在计算机中的存储方式和数据的运算三个方面。( )【吉林大学 2006 一、4(1 分)】（分数：2.00）A.正确 B.错误解析：32.数据的逻辑结构与数据元素本身的内容和形式无关。( )【南京理工大学 2004 二、1(1 分)】（分数：2.00）A.正确 B.错误解析：33.算法和程序没有区别，在数据结构中二者是通用的。( )【暨南大学 2010 三、11(1 分)】（分数：2.00）A.正确B.错误 解析：解析：算法不等于程序。算法具有“有穷性”，操作系统的监控程序总在运行，不具备有穷性的要求。算法用计算机语言实现时就是程序。34.构成数据的最小单位是数据元素。( )【武汉大学 2005 一、1(2 分)】（分数：2.00）A.正确B.错误 解析：35.数据元素可以由类型互不相同的数据项构成。( )【武汉大学 2004 一、1(2 分)】（分数：2.00）A.正确 B.错误解析：
