数据结构期末复习 第一章 绪论一、选择题1、把数据存储到计算机中并具体体现数据元素间的逻辑结构称为B。A. 给相关变量分配存储单元B. 物理结构C. 算法的具体实现D. 逻辑结构2、下列说法中不正确的是D。A. 数据项是数据中不可分割的最小可标识单位B. 数据元素是数据的基本单位C. 数据可有若干个数据元素构成D. 数据项可由若干个数据元素构成3、一个存储结点存储一个A。A. 数据元素B. 数据结构C. 数据项D. 数据类型4、数据结构中与所使用的计算机无关的是数据的D。A. 存储结构B. 物理和存储结构C. 物理结构D. 逻辑结构5、下列的叙述中不属于算法特性的是C。A. 可行性B. 输入性C. 可读性D. 有穷性6、算法的时间复杂度与B有关。A. 计算机的操作系统B. 算法本身C. 数据结构D. 所使用的计算机。7、下面程序段的时间复杂度是B。is0;while (sn){i;si;}A.O(n0.5) B. O(log2n) C. O(n) D.O(1)8、下面程序段的时间复杂度是B。int f(unsigned int n){if (n0||n1) return 1;else return n*f(n-1);}A.O(1) B. O(log2n) C. O(n!) D. O(n)9、在数据结构中从逻辑上可以把数据结构分为D。A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.内部结构和外部结构 D.线性结构和非线性结构10、执行下面程序段时执行S语句的次数为D。for (int i1;in;i)for (int j1;ij;j)S;A.n2 B.n2/2 C.n(n1) D.n(n1)/211、数据的存储结构包括数据元素的表示和A。A. 数据元素间的关系的表示B. 数据处理的方法C. 数据元素的类型D. 相关算法12、树状结构中数据元素的位置之间存在D的关系。A. 一对一B. 多对多C. 每一个元素都有一个直接前驱和一个直接后继D. 一对多13、一种逻辑结构C。A. 与存储该逻辑结构的计算机相关B. 只能有唯一的存储结构C. 可以有不同的存储结构D. 是指某一种数据元素的性质14、把数据存储到计算机中并具体体现数据元素间的逻辑结构称为C。A. 逻辑结构B. 数据元素的存储C. 存储结构D. 给数据元素分配存储空间二、判断题1. 数据元素是数据的最小单位。×2. 数据的逻辑结构是指各数据元素之间的逻辑关系是用户根据应用需要建立的。√3. 算法和程序原则上没有区别在讨论数据结构时二者是通用的。×4. 数据的逻辑结构与数据元素本身的内容和形式无关。√5. 算法和程序都应具有下面一些特征有输入有输出确定性有穷性有效性。×6. 只有用面向对象的计算机语言才能描述数据结构算法。×7. 数据元素可以有一个或多个数据项组成。√8. 数据元素之间的抽象关系称为物理结构。×9. 数据的逻辑结构在计算机中的表示称为逻辑结构。×10. 数据的逻辑结构是与存储该结构的计算机相关的。×11数据结构中,元素之间存在多对多的关系称为树状结构。×12. 通常可以把某城市中各公交站点间的线路图抽象成树型结构。×13. 通常可以把一本含有不同章节的书的目录结构抽象成线性结构。×14. 结构中的数据元素存在多对多的关系称为图形结构。√15数据结构中数据可以由一个或多个数据项组成。×三、程序题指出下列各算法的时间复杂度。1、int prime(int n){int i1;int x(int) sqrt(n);while (ix)if (n %i 0) break;if (ix) return 1;else return 0;}答案O(log2n)2、int suml(int n){int p1,s0;for (int i1; in; i) {p*i;sp;}return s;}答案O(log2n)3、 int sum2(int n){int s0;for (int I1; In; I) {int p1;for (int j1; jI; j)p*j;sp;}return s;}答案O(n!)4、 int fun (int n){int I1, s1;while (sn)sI;return I;}答案O(n)