第一部分 数据结构概论及算法分析一、选择题1数据结构是一门研究计算机中_ _对象及其关系的学科。（1）数值运算 （2）非数值运算 （3）集合 （4）非集合2数据结构的定义为(K，R)，其中K是_ _的集合。（1）算法 （2）数据元素（3）数据操作 （4）逻辑结构3算法分析的目的是_。（1） 找出数据结构的合理性 （2） 研究算法中输入和输出的关系（3） 分析算法的效率以求改进 （4） 分析算法的易懂性和文档性4. 数据的不可分割的基本单位是_ _。 A.元素 B.结点 C.数据类型 D.数据项5下列算法suanfa2的时间复杂度为_。int suanfa2(int n) int t=1； while(t=n) t=t*2；return t； A.O(log2n) B.O(2n) C.O(n2) D.O(n)6.（ ）是具有相同特性数据元素的集合，是数据的子集。A 数据符号 B 数据对象 C 数据 D 数据结构7与数据元素本身的形式、内容、相对位置、个数无关的是数据的 ( )。A. 存储结构B. 逻辑结构 C. 算法D. 操作8数据结构是研究数据的（ ）及它们之间的相互联系。A、理想结构，物理结构 b、理想结构，逻辑结构C、物理结构，逻辑结构 d、抽象结构，逻辑结构9组成数据的基本单位是 （ ） 。a、数据项 b、数据类型 c、数据元素 d、数据变量10数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为： （A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构11算法指的是（ ）A计算机程序 B解决问题的计算方法C排序算法 D解决问题的有限运算序列12下列算法suanfa1中语句x=x*2；的执行次数是（ ）。 void suanfa1(int n) int i,j,x=1； for(i=1；i=n；i+) for(j=i；j=n；j+) x=x*2； printf(%d,x)； A.n(n-1)/2 B.n(n+1)/2 C.n2 D.nlog2n 13. 由_组成的集合是一个数据对象。 A.不同类型的数据项 B.不同类型的数据元素C.相同类型的数据项 D.相同类型的数据元素14在下列选项中，哪个不是一个算法一般应该具有的基本特征_。A. 确定性B. 可行性C. 无穷性D. 拥有足够的情报15在计算机中，算法是指_。A. 查询方法B. 加工方法C. 解题方案准确而完整的描述D. 排序方法16算法的时间复杂度是指_。A. 执行算法程序所需要的时间B. 算法程序的长度C. 算法执行过程中所需要的基本运算次数D. 算法程序中的指令条数17算法的空间复杂度是指_。A. 算法程序的长度B. 算法程序中的指令条数C. 算法程序所占的存储空间D. 算法执行过程中所需要的存储空间18下面叙述正确的是_。A. 算法的执行效率与数据的存储结构无关B. 算法的空间复杂度是指算法程序中指令（或语句）的条数C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止D. 以上三种描述都不对19数据的存储结构是指_。A. 数据所占的存储空间量B. 数据的逻辑结构在计算机中的表示C. 数据在计算机中的顺序存储方式D. 存储在外存中的数据20算法分析的目的是_。A. 找出数据结构的合理性B. 找出算法中输入和输出之间的关系C. 分析算法的易懂性和可靠性D. 分析算法的效率以求改进21_不是算法的基本特征。A. 正确性B. 长度有限C. 在规定的时间内完成D. 确定性二、填空1 一个数据结构在计算机中的表示(映象)称为 数据的存储结构。2 数据结构被形式地定义为（ D, R ），其中 D 是 数据元素 的有限集合， R 是 D 上的 关系 有限集合。 3一个算法的效率可分为 时间 效率和 空间 效率。4设问题规模为n，分析下列算法的时间复杂度为 O(n1/2) 。 for (i = 1; i * i =n; i+) +x ; s += x5设问题规模为n，分析下列算法的时间复杂度为 O(n3) 。 for ( i =1 ; i = n ; i+ )for ( j = 1 ; j = i ; j+ )for ( k=1 ; k = j ; k+) +x ; s += x ; 6数据的逻辑结构是从逻辑关系上描述数据，它与数据的 存储结构 无关，是独立于计算机的。7一个算法具有5个特性: 有穷性、确定性、可行性、有零个或多个输入、有一个或多个输出。8算法的复杂度主要包括 时间 复杂度和空间复杂度。9数据结构包括数据的逻辑结构、数据的_物理结构_以及对数据的操作运算。10数据的逻辑结构被分为_线性结构_、_树_、_图_和_集合_四种。11在图形结构中，每个结点的前驱结点和后续结点数可以_不为零_。12一种抽象数据类型包括 数据 和 操作 两个部分。三、判断1程序就是算法，但算法不一定是程序。( )2数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。( )3非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。( )4数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。()5算法一定要有输入和输出。()6算法分析的目的旨在分析算法的效率以求改进算法。（)精美排版