数据结构典型例题集

《数据结构典型例题集》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基本概念典型例题一、单项选择题[例6-1]数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是(①)的有穷集合，R是D上(②)的有限集合。①A.算法B.数据元素C.数据操作D.逻辑结构②A.操作B.映像C.存储D．关系解析：由数据结构的集合形式化定义可知，本题答案为：①B；②D。[例6-2]数据的常用存储结构中不包括()。A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储方法和散列存储方法。由此可知，本题

2、答案为：B。[例6-3]算法指的是(①)，它必须具备(②)这三个特性。①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性C．确定性、有穷性、稳定性D．易读性、稳定性、安全性解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本题答案为：①㈠②B。[例6-4]在下面的程序段中，对x的赋值语句的执行频度为()。for(i=0；i

3、+)for(j=0；j

4、简述数据结构的定义。解析：数据结构是指数据元素之间的相互关系，即数据的组织形式。数据结构通常包括三个方面的内容，分别是数据的逻辑结构、数据的存储结构(物理结构)和在这些数据上定义的运算。用集合的观点可以把数据结构表示为一个二元组DS＝(D，R)。其中，D是数据元素的有穷集合，R是D上关系的有限集合。[例6-7]分析以下程序段的时间复杂度。for(i=0；i

5、复执行的次数。一个算法中所有语句的执行频度之和构成了该算法的运行时间。在本例算法中，语句①的执行频度是n+l，语句②的执行频度是n，语句③的执行频度是n(2n+2)＝2n2-2n，语句④的执行频度是n(2n+1)＝2n2+n。该程序段的时间复杂度T(n)＝(n+1)+n+(2n2+2n)+(2n2+n)＝4n2+5n+1＝O(n2)。实际上，可以用算法中基本操作重复执行的频度作为度量标准，而被视为基本操作的一般是最深层循环内的语句。在上例中，语句④为基本操作，其执行频度为2n2+n，因此，该算法的时间复

6、杂度T(n)＝2n2+n＝O(n2)。[例6-8]分析以下程序段的时间复杂度。i=1；while(i<=m)i=i*2；解析：上述算法的基本操作语句是i＝i*2，设其执行频度为T(n)，则有：2T(n)≤n，即T(n)≤lbn＝O(lbn)。因此，该程序段的时间复杂度为O(lbn)。60线性结构典型例题一、单项选择题[例7-1]在数据结构中，与所使用计算机无关的数据叫(①)结构；链表是一种采用(②)存储结构存储的线性表；链表适用于(③)查找；在链表中进行(④)操作的效率比在线性表中进行该操作的效率高。①

7、A．存储B．物理C．逻辑D．物理和逻辑②A．顺序B．网状C．星式D．链式③A．顺序B．二分法C．顺序及二分法D．随机④A．二分法查找B．快速查找C．顺序查找D．插入解析：本题考查的是基本概念。本题答案为：①C；②D；③A；④D。[例7-2]链表不具备的特点是()。A．插入和删除不需要移动元素B．可随机访问任一结点C．不必预分配空间D．所需空间与其长度成正比解析：线性表可随机访问任一结点，而链表必须从第一个数据结点出发逐一查找每个结点。本题答案为：B。[例7-3]不带头结点的单链表head为空的判定条件是

8、()。A．head＝＝NULLB．head_>next＝＝NULLC．head_>next＝＝headD．head!＝NULL解析：在不带头结点的单链表head中，head指向第一个数据结点。空表即该表没有结点，head＝＝NULL表示该单链表为空。本题答案为：A。[例7-4]带头结点的单链表head为空的判定条件是()。A．head＝＝NULLB．head—>next＝＝NULLC．head—>next＝＝headD．head!＝NULL