数据结构习题集（自编）
第一章 绪论
一、选择题
1．数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（）和运算的学科。
A．结构 B．关系 C．运算 D．算法 2．在数据结构中，从逻辑上可以把数据结构分成（）。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．逻辑结构和存储结构 3．线性表的逻辑顺序和存储顺序总是一致的，这种说法（）。
A．正确 B．不正确 C．无法确定 D．以上答案都不对 4．算法分析的目的是（）。
A．找出算法的合理性 B．研究算法的输人与输出关系 C．分析算法的有效性以求改进 D．分析算法的易懂性 5. 算法的时间复杂度取决于（ ）
A．问题的规模 B. 待处理数据的初态 C. A和B 6．一个算法应该是（ ）。
A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 7. 下面关于算法说法错误的是（ ）
A．算法最终必须由计算机程序实现
B.为解决某问题的算法与为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的
8．以下与数据的存储结构无关的术语是（ ）。
A．循环队列 B. 链表 C. 哈希表 D. 栈 9．在下面的程序段中，对x的赋值语句的频度为（ ）
for（i=0;i A． 2n B．n C．n2 D．log2n 10．以下数据结构中，（ ）是非线性数据结构 A．树 B．字符串 C．队列 D．栈 11. 下列数据中，（ ）是线性数据结构。 A．哈夫曼树 B.有向无环图 C. 二叉排序树 D. 栈 12．以下属于逻辑结构的是（ ）。 A．顺序表 B. 哈希表 C.有序表 D. 单链表 二、填空题 1、_______是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，________是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。（数据、数据） 2、数据元素是数据的______，有些情况下也称为元素、结点、顶点、记录等。（基本单位） 3、________是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为________。（数据项、数据项） 4、数据的逻辑结构是指数据之间的________。逻辑结构是从________上描述数据，它与具体存储无关，是独立于计算机的。因此逻辑结构可以看作是从具体问题抽象出来的______________。（逻辑关系、逻辑关系、数学模型） 5、数据的________指数据元素及其关系在计算机存储器内的表示。_________是逻辑结构在计算机里的实现，也称之为映像。（存储结构、存储结构） 6、数据逻辑结构可以分为四种基本的类型，_______结构中的元素除了仅仅只是同属于一个_________________，不存在什么关系。（集合、集合） 7、数据逻辑结构的四种基本类型中，________中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。（线性结构） 8、数据逻辑结构的四种基本类型中，____________中的元素是一种一对多的关系。（树形结构） 9、图型结构或图状结构是一种________的关系。在这种逻辑结构中，所有结点均可以有多个前驱和多个后继。（多对多） 10、有时也可将树型结构、集合和图型结构称为__________，这样数据的逻辑结构就可以分为__________和________两大类。（非线性结构、线性结构、非线性机构） 11、____________方式是指逻辑上相邻的结点被存储到物理上也相邻的存储单元中。这种存储结构只存储结点的数值，不存储结点之间的关系，结点之间的关系是通过存储单元的相邻关系隐含的表示出来的。（顺序存储） 12、_______方式是种存储方法，不要求逻辑上相邻的结点在物理上也相邻，即数据元素可以存储在任意的位置上。（链式存储） 13、_________方式是利用结点关键字的值直接计算出该结点存储单元地址，然后将结点按某种方式存人该地址的一种方法。（散列存储或哈希存储） 14、所谓算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的其中每个指令表示一个或多个操作。算法的五个重要特性是__________、__________、__________、__________和__________。（有限序列、有穷性、确定性、可行性、输入、输出） 15、算法的_______性是指算法必须能够在执行有限个步骤之后结束，并且每个步骤都必须在有穷的时间内完成。（有穷性） 16、算法的________性是指算法中的每一个步骤必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。并且，在任何条件下，算法只能有惟一的一条执行路径，即只要输人是相同的就只能得到____________的输出结果。（确定性、相同） 17、算法的____________性又称为算法的能行性，是指算法中描述的操作是可以通过已经实现的基本运算执行有限次来实现。（可行性） 18、判断一个算法的好坏主要以下几个标准：________、________、________、_________。（正确性、可读性、健壮性、时间效率和空间效率） 19、算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机_________的长短和___________________的大小。（运行时间、所占据空间） 20、空间复杂度（SPace ComPlexity）也是度量一个算法好坏的标准，它所描述的是算法在运行过程中所占用_____________的大小。（存储空间） 三、判断题 1．顺序存储方式只能用于存储线性结构。（×） 2．数据元素是数据的最小单位。（×） 3．算法的优劣与算法描述语言无关，但与所用计算机有关。(×) 4．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。() 5．数据的逻辑结构是指各元素之间的逻辑关系，是根据用户需要而建立的。（） 6．数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。（） 7．数据的物理结构是指数据在计算机中实际的存储形式。（） 8．具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构。（） 9．算法实际上就是程序，程序也一定是算法。(×) 10. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。(×) 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×) 12. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。() 13. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。 (×) 14. 判断一个算法的好坏主要以下几个标准：正确性、有穷性、健壮性和可行性。(×) 15．算法的时间复杂度T（n）=O(f(n))表示随问题规模n的增大，算法执行时间的增长率与函数f(n)的增长率相同。（） 四、综合题 1．用大O形式表示下面算法的时间复杂度： for（i=0；i＜m；i十十） for（j=0；j＜n；j＋＋） A[i][j]=i*j； 2．写出下面算法的时间复杂度： i＝0； s=0； while(s＜n） ｛ i++; s+=i; ｝ 3．写出以下算法的时间复杂度： for（i＝0; i＜m; i＋＋） for（j＝0 ; j＜t; j＋＋） c[i][j]=0； for（i=0；i＜m；i＋＋） for（j=o; j for（k=0；k＜n；k＋＋） c［i］［j］＋＝a［i］［k］*b[k][j]; 4．写出下面算法的时间复杂度： i=1; while（i＜＝n） i=i*3; 5．求下面函数中各条语句的频度和算法的时间复杂度： prime（int n） ｛ int i＝2； while ((n％i）！=0＆＆i＜sqrt(n) ) i++; if（i＞sqrt(n) ) printf（”％d is a prime number.＼n”，n）； else printf（”％d is not a prime number.＼n”，n）；｝ 1. 该算法的时间复杂度为：O(m×n)。 2. 该算法的时间复杂度为：O(n) 3. 该算法的时间复杂度为：O(m×n×t)。 4. 该算法的时间复杂度为：log3(n)。 5. 该算法的时间复杂度为：O(n)。 6．将下列函数，按它们在n→∝时的无穷大阶数，从小到大排序。 n, n-n3+7n5, nlogn, 2n/2, n3, logn, n1/2+logn, (3/2)n, ,n!, n2 +logn 从小到大排列为：logn, n1/2+logn, n, nlogn, n2+logn，n3, n-n3+7n5, 2 n/2, (3/2)n, n!,