1-数据结构习题1.docVIP

第一章 选择: 1.数据结构研究数据的（ ）以及它们之间的相互关系。 A）存储结构，物理结构 B）理想结构，抽象结构 C）物理结构，逻辑结构 D）抽象结构，逻辑结构 2.在数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A）存储 B）物理 C）逻辑 D）物理与存储 3.数据结构课程主要研究以下三方面的内容，它们是（ ）。 A）数据、数据元素、数据类型 B）数据元素、数据类型、算法实现 C）数据元素、数据的逻辑结构、数据的存储结构 D）数据的逻辑结构、数据的存储结构、数据的运算 4.在以下的复杂度量级中，量级最低的是（　）。 A）O(n) B）O(log2n) C）O(nlog2n) D）O(n2) 5.在下列叙述中，正确的是（　）。 A）数据的逻辑结构要考虑数据元素本身的内容 B）不同类型的数据元素可以归类到同一的逻辑结构中 C）数据元素之间的关联关系在数据的逻辑结构中体现 D）数据元素是数据不可分割的最小标识单位 （数据项） A）可行性、可移植性和可扩充性 B）可行性、确定性和有穷性 C）确定性、稳定性和有穷性 D）易读性、稳定性和安全性 7.算法分析的目的是（　）。 A)找出数据结构的合理性 B)研究算法中的输入/输出关系 C)分析算法的易读性 D)分析算法的效率以求改进 8.设n=10，下面程序段的时间复杂度是（　）。 for(i=10; in; i++) { j=k=0; while(j+k=i) if　(jk)　k++; else j++; } A）O（log2n） B）O(n) C）O(nlog2n) D）O(n2) 9.计算机算法是指( )。 A)计算方法 B)排序方法 C)调度方法 D)解决问题的有限运算序列 10.数据的定义取决于数据的逻辑结构，而数据的实现取决于数据的物理结构( )。 A)正确 B) 不正确 11.下面说法错误的是（ ） A)算法原地工作的含义是指不需要任何额外的辅助空间 B)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 C)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 D)同一个算法，实现语言的级别越高，执行效率就越低 判断： 1. 数据元素是数据的最小单位。( N ) 数据项是数据的最小单位2. 记录是数据处理的最小单位。 ( N ) 3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( N ) 数据元素 4. 算法的优劣与算法描述语言无关，但与所用计算机有关。( N ) 5. 健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( Y ) 6. 算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。( N ) 7. 数据的物理结构是指数据在计算机内的实际存储形式。( Y ) 8. 数据结构的抽象操作的定义与具体实现有关。( N ) 9. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。( Y ) 10. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的存储结构. ( N ) 语句频度与时间复杂度 1.计算机执行下面的语句时,语句s的执行次数为: (n+3)(n-2)/2。 for(i=l；in-l；i++) for(j=n; j=i; j--) s; 2.下面程序段中带有下划线的语句执行次数的量级是( log2n2 ) i=n*n while (i!=1) i=i / 2; 3.下面程序段中带下划线的语句的执行次数的数量级是(nlog2n )。 i=1; while( in) { for j=1;j=n;j++ { x=x+1; i=i*2； } } 4. 在下面的程序段中，对ｘ的赋值语句的频度为: n(n+1)(n+2)/6 O(n3) for（i= 1；i=n; i++） for(j=1;j=i;j++) for (k＝1;k=j; k++) ｘ＝ｘ+1； 5. 已知如下程序段,则各语句的频度为: for（i= n；i=1; i- -） //语句1