西安石油大学：《数据结构》精品课程资源（章节习题）第1章 绪论

基本概念习题 1-1什么叫数据?什么叫数据元素?什么叫数据项? 1-2什么叫数据的物理结构?什么叫数据的存储结构?什么叫数据的操作? 1-3数据结构课程主要讨论哪三个方面的问题? 1-4分别画出线性结构、树结构和图结构的逻辑示意图。 1-5什么叫类型?什么叫数据类型?什么叫抽象数据类型? 1-6怎样利用抽象数据类型设计大型软件? 1-7什么叫算法?算法的5个性质是什么? 1-8根据算法的性质解释算法和程序的区别? 1-9评判算法的优劣有哪几种方法? 1-10什么叫算法的时间复杂度?怎样表示算法的时间复杂度? 1-11设n为已在算法前边定义的整数类型,并已知n为正整数,分析下列各算法中加下 划线语句的执行次数,并给出各算法的时间复杂度T(n) (1)inti=1,k=0; while(i1 inty=O while(x>=(y+1)*(y+1) (5)int i,, k, x=0 for(i=0,1<n;i++) for(k=0; k<j; k++) 1-12设求解同一个问题有三种算法,三种算法各自的时间复杂度分别为Om),O(2) 和Omng),哪种算法最可取?为什么 1-13按增长率从小到大的顺序排列下列各组函数: (3/2),(2/3)",(4/3) (2)n, (3)lbn, nlb n, n/b",n *1-14下面是几个典型的时间复杂度函数估值问题

基本概念习题： 1-1 什么叫数据？什么叫数据元素？什么叫数据项？ 1-2 什么叫数据的物理结构？什么叫数据的存储结构？什么叫数据的操作？ 1-3 数据结构课程主要讨论哪三个方面的问题？ 1-4 分别画出线性结构、树结构和图结构的逻辑示意图。 1-5 什么叫类型？什么叫数据类型？什么叫抽象数据类型？ 1-6 怎样利用抽象数据类型设计大型软件？ 1-7 什么叫算法？算法的 5 个性质是什么？ 1-8 根据算法的性质解释算法和程序的区别？ 1-9 评判算法的优劣有哪几种方法？ 1-10 什么叫算法的时间复杂度？怎样表示算法的时间复杂度？ 1-11 设 n 为已在算法前边定义的整数类型，并已知 n 为正整数，分析下列各算法中加下 划线语句的执行次数，并给出各算法的时间复杂度 T(n)。 (1) int i = 1, k = 0; while (i 1 */ int y = 0; while(x >= (y+1)*(y+1)) y++; (5) int i, j, k, x = 0; for (i = 0; i < n; i++) for (j = 0; j < i; j++) for (k = 0; k < j; k++) x = x + 2; 1-12 设求解同一个问题有三种算法，三种算法各自的时间复杂度分别为 O(n2 )，O(2n ) 和 O(nlg n)，哪种算法最可取？为什么？ 1-13 按增长率从小到大的顺序排列下列各组函数： （1）2 100 ，（3/2）n，（2/3）n，（4/3）n （2）n，n 3/2，n 2/3，n!，n n （3）lb n，n×lb n，n lb n，n *1-14 下面是几个典型的时间复杂度函数估值问题：

(1)当n为正整数时,n取何值能使2>n3 (2)说明2+n3是O(2) (3)给出5(n2+6)/(n+3)+7lgn的O值估计

（1）当 n 为正整数时，n 取何值能使 2 n > n 3 ； （2）说明 2 n + n 3 是 O(2n )； （3）给出 5(n2 + 6) / (n + 3) + 7lg n 的 O 值估计