习题一参考答案一、概念题1. 试述下列各组概念：⑴ 数据、数据元素、数据项⑵ 数据结构、数据的逻辑结构、数据的存储结构⑶ 数据类型、数据操作⑷ 算法、算法的时间复杂度、算法的空间复杂度参考答案 : 略2．试述数据结构研究的3 个方面的内容。参考答案 : 数据结构研究的3 个方面分别是数据的逻辑结构、数据的存储结构和数据的运算（操作）。3．试述集合、线性结构、树型结构和图型结构四种常用数据结构的特性。参考答案 : 集合结构：集合中数据元素之间除了“同属于一个集合”的特性外，数据元素之间无其它关系，它们之间的关系是松散性的。线性结构：线性结构中数据元素之间存在“一对一”的关系。即若结构非空，则它有且仅有一个开始结点和终端结点， 开始结点没有前趋但有一个后继，终端结点没有后继但有一个前趋，其余结点有且仅有一个前驱和一个后继。树形结构：树形结构中数据元素之间存在“一对多”的关系。即若结构非空，则它有一个称为根的结点，此结点无前驱结点，其余结点有且仅有一个前驱，所有结点都可以有多个后继。图形结构：图形结构中数据元素之间存在“多对多”的关系。即若结构非空，则在这种数据结构中任何结点都可能有多个前驱和后继。4．设有数据的逻辑结构的二元组定义形式为B=(D,R)，其中 D={a1,a2,⋯,an}，R={
| i=1,2, ⋯， n-1}，请画出此逻辑结构对应的顺序存储结构和链式存储结构的示意图。参考答案 :顺序存储结构示意图如下：a1a2a3anan-10 1 2 ⋯ n-2 n-1⋯链式存储结构示意图如下：a1a2a3an^⋯5．设一个数据结构的逻辑结构如图所示，请写出它的二元组定义形式。 K 2 K 1 K 4 K 5 K 3 K 8 K 6 K 7 K9图 第 5 题的逻辑结构图参考答案 : 它的二元组定义形式为B=（ D，R），其中 D={k1,k2,k3,k4,k5,k6,k7,k8,k9}，R=,,,,,,,,, }。6．设有函数f (n)=3n 2-n+4，请证明 f (n)=O(n2)。证明： 因为存在 c=6，N=1，对所有的n≥N ，0 ≤3n2-n+4≤ 6×n2 都是恒成立的，所以由书P16 的定义可得f (n)=O(n2)。7．请比较下列函数的增长率，并按增长率递增的顺序排列下列函数：(1) 2100 (2) (3/2)n (3) (4/3)n (4) nn (5) n2/3 (6) n3/2 (7) n! (8)n(9) n (10) log 2n (11) 1/log 2n (12)log 2(log2n) (13)nlog 2n (14) nlog2n参考答案 : 按...
