第一章 绪论 

1.1 【答案】 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

1.2 【答案】试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。　　　　　

1.3 【答案】常用的存储表示方法有哪几种?

1.4 【答案】设三个函数f,g,h分别为 f(n)=100n³+n²+1000 , g(n)=25n³+5000n² , h(n)=n^1.5+5000nlgn 请判断下列关系是否成立：
　　(1) f(n)=O(g(n)) 
　　(2) g(n)=O(f(n)) 
　　(3) h(n)=O(n^1.5)
　　(4) h(n)=O(nlgn)

1.5 【答案】设有两个算法在同一机器上运行，其执行时间分别为100n²和2ⁿ,要使前者快于后者，n至少要多大?

1.6 【答案】设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。
(1) i=1; k=0; 
　　 while(i<n)
　　　 { k=k+10*i;i++;
　　　 }
(2) i=0; k=0;
　　 do{
　　　　k=k+10*i; i++; 
　　　 }
　　 while(i<n); 

(3) i=1; j=0; 
　　 while(i+j<=n) 
　　　 {
　　　　 if (i>j) j++;
　　　　 else i++;
　　　 }

(4)x=n; // n>1 
　 while (x>=(y+1)*(y+1))
　　 y++;

(5) x=91; y=100; 
    while(y>0)
　　　　 if(x>100)
　　　　　 {x=x-10;y--;}
　　　　 else x++;

1.7 【答案】算法的时间复杂度仅与问题的规模相关吗?

1.8 【答案】按增长率由小至大的顺序排列下列各函数：
 　　2¹⁰⁰, (3/2)ⁿ，(2/3)ⁿ， nⁿ ,n^0.5 , n! ，2ⁿ ，lgn ,n^lgn, n^(3/2)

1.9 【答案】有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大"O"记号表示。例如，设T₁(n)=1.39nlgn+100n+256=1.39nlgn+O(n), T₂(n)=2.0nlgn-2n=2.0lgn+O(n), 这两个式子表示，当n足够大时T₁(n)优于T₂(n)，因为前者的常数因子小于后者。请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣?
　　(1) T₁(n)=5n²-3n+60lgn 　 
　　(2) T₂(n)=3n²+1000n+3lgn  
　　(3) T₃(n)=8n²+3lgn 　　　 
　　(4) T₄(n)=1.5n²+6000nlgn