数据结构各章习题及答案.pdf

数据结构习题及解答 第 1 章 概述 【例 1-1 】分析以下程序段的时间复杂度。 for(i=0;in;i++) for(j=0;jm;j++) A[i][j]=0; 解：该程序段的时间复杂度为 O(m*n) 。 【例 1-2 】分析以下程序段的时间复杂度。 i=s=0; ① while(sn) { i++; ② s+=i; ③ } 解：语句①为赋值语句，其执行次数为 1 次，所以其时间复杂度为 O(1) 。语句②和语 句③构成 while 循环语句的循环体， 它们的执行次数由循环控制条件中 s 与 n 的值确定。 假 定循环重复执行 x 次后结束， 则语句②和语句③各重复执行了 x 次。其时间复杂度按线性 累加规则为 O(x) 。此时 s 与 n 满足关系式： s ≥n ，而 s=1+2+3+ …+x 。所以有： 1+2+3+… +x ≥n ，可以推出： 1 1 8n 1 1 2n 2 2 4 x= x 与 n 之间满足 x=f( n ），所以循环体的时间复杂度为 O( n ) ，语句①与循环体由线 性累加规则得到该程序段的时间复杂度为 O( n ）。 【例 1-3 】分析以下程序段的时间复杂度。 i=1; ① while(i=n) i=2*i; ② 解：其中语句①的执行次数是 1，设语句②的执行次数为 f(n) ，则有： 2 f ( n) n 。 得： T （n）=O( log2 n ) 【例 1-4 】有如下递归函数 fact(n) ，分析其时间复杂度。 fact(int n) { if(n=1) return(1); ① else return(n*fact(n-1)); ② } 解：设 fact （n）的运行时间函数是 T(n) 。该函数中语句①的运行时间是 O(1) ，语句 ②的运行时间是 T(n-1)+ O(1) ，其中 O(1) 为常量运行时间。 由此可得 fact （n）的时间复杂度为 O(n) 。 习题 1 一、单项选择题 1. 数据结构是指（ 1. A ）。 A. 数据元素的组织形式 B. 数据类型 C.数据存储结构 D. 数据定义 2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ 2. C ）。 A. 存储结构 B. 逻辑结构 C.链式存储结构 D. 顺序存储结构 3. 树