数据结构习题及解答
第1章 概述
【例1-1】分析以下程序段的时间复杂度。
for(i=0;i<n;i++) for(j=0;j<m;j++) A[i][j]=0;
解:该程序段的时间复杂度为O(m*n)。 【例1-2】分析以下程序段的时间复杂度。
i=s=0; ① while(s<n) { 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 8n11
2n
224x=
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。
严蔚敏数据结构各章习题... 72页 免费 数据结构各章自测题答案 35页 免费... 数据结构期末复习题全集...
严蔚敏版 数据结构习题集答案_理学_高等教育_教育专区。第1章 绪论 1.1 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。...
严蔚敏版数据结构课后习题答案_高等教育_教育专区。数据结构复习资料第1章 绪论 1.1 简述下列术语:数据,数据元素、数据对象、数据结构、存储结 构、数据类型和...
严蔚敏 数据结构课后习题及答案解析_工学_高等教育_教育专区。第一章 绪论 ...带有头结点的循环链表,将两个循环链表的长度放在各并自的头结点的数据域中的 ...
数据结构各章自测题答案_工学_高等教育_教育专区。数据结构各章自测题目及答案...1. 【严蔚敏习题集 P7 1.3②】 D={d1,d2,d3,d4} R={(d1,d2)...
数据结构习题集答案(C语言版严蔚敏)_电脑基础知识_IT/计算机_专业资料。特别...80 . 第 1 章 绪论 1.1 简述下列术语:数据,数据元素、数据对象、数据结构...
严蔚敏版数据结构课后习题答案_理学_高等教育_教育专区。课后习题答案...113 第 1 章 绪论 1.1 简述下列术语:数据,数据元素、数据对象、数据结构、...
严蔚敏数据结构课本配套的习题集答案严蔚敏数据结构课本配套的习题集答案隐藏>> 严蔚敏《数据结构(C 语言版)习题集》答案 第一章 绪论 1.16 void print_...
严蔚敏版数据结构课后习题答案_理学_高等教育_教育专区。第 1 章 绪论 1.1 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数 据...
严蔚敏版数据结构习题完整答案严蔚敏 数据结构 C 语言版答案详解 第 1 章 绪论 1.1 简述下列术语:...
热门文档