数据结构概论

1、数据结构概论一、 单项选择题（共32题）1. 下列叙述中正确的是（ ）。A. 算法的效率只与问题的规模有关，而与数据的存储结构无关B. 算法的时间复杂度是指执行算法所需要的计算工作量C. 数据的逻辑结构与存储结构是一一对应的D. 算法的时间复杂度与空间复杂度一定相关答案：B2. 下列数据结构中，属于非线性结构的是（ ）。A. 循环队列B. 带链队列C. 二叉树D. 带链栈答案：C3. 算法分析的两个主要方面是（ ）。A. 空间复杂性和时间复杂性B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性答案：A4. 决定选取何种存储结构时，一般不需要考虑（ ）A. 各结点的值如何B.

2、结点的个数C. 对数据有哪些运算D. 所用编程语言实现这种结构是否方便答案：A5. 数据的存储结构是指（ ）。A. 存储在外存中的数据B. 数据所占的存储空间量C. 数据在计算机中的顺序存储方式D. 数据的逻辑结构中计算机中的表示答案：D6. 数据的存储结构包括顺序、链接、散列和（ ）4种基本类型。A. 索引B. 数组C. 集合D. 向量答案：A7. 在算法中，对需要执行的每一步操作，必须给出清楚、严格的规定，这属于算法的（ ）。A. 正当性B. 可行性C. 确定性D. 有穷性答案：C8. 算法指的是（ ）A. 计算机程序B. 解决问题的计算方法C. 排序方法D. 解决问题的有限运算序列答案：

3、D9. k = 1;for(i = 0; i < n; i+) for(j = 0; j < n; j+） aij = k+;上述程序段的时间复杂度为（ ）。A. O(n)B. O(0)C. O(n2)D. O(1)答案：C10. 执行下面程序段时，S语句的执行次数为（ ）。for(int i = 1; i <= n; i+) for(int j = 1; j <= i; j+) S;A. n(n-1)/2B. n(n+1)/2C. n2/2D. n答案：B11. 下列叙述中正确的是（ ）。A. 顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B.

4、顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C. 顺序存储结构能存储有序表，链式存储结构不能存储有序表D. 链式存储结构比顺序存储结构节省存储空间答案：A12. 下列叙述中正确的是（ ）。A. 一个逻辑数据结构只能有一种存储结构B. 数据的逻辑结构属于线性结构，存储结构属于非线性结构C. 一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D. 一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率答案：D13. 数据结构中，与所使用的计算机无关的是数据的（ ）结构。A. 存储B. 物理C. 逻辑D. 物理和存储答案：C14. 计算机算法指的是（ ）

5、。A. 计算方法B. 排序方法C. 解决问题的有限运算序列D. 调度方法答案：C15. 算法的空间复杂度是指（ ）。A. 算法在执行过程中所需要的计算机存储空间B. 算法所处理的数据量C. 算法程序中的语句或指令条数D. 算法在执行过程中所需要的临时工作单元数答案：A16. 下面程序段的时间复杂性的量级为（ ）。int i = 0, s1 = 0, s2 = 0;while(i+ < n) if(i%2) s1 += i; else s2 += i;A. O(1)B. O(logn)C. O(n)D. O(n2)答案：C17. 下面程序段的时间复杂度为（ ）。for(int i = 0;

6、 i < m; i+) for(int j = 0; j < n; j+) aij = i * j;A. O(m2)B. O(n2)C. O(m + n)D. O(m * n)答案：D18. 在数据结构中，从逻辑上可以把数据结构分成（ ）。A. 动态结构和静态结构B. 紧凑结构和非紧凑结构C. 线性结构和非线性结构D. 内部结构和外部结构答案：C19. 非线性结构是数据元素之间存在一种（ ）。A. 一对多关系B. 多对多关系C. 多对一关系D. 一对一关系答案：B20. 下列叙述中正确的是（ ）。A. 一个算法的空间复杂度大，则其时间复杂度也必定大B. 一个算法的空间复杂度大，则其

7、时间复杂度必定小C. 一个算法的时间复杂度大，则其空间复杂度必定小D. 上述3种说法都不对答案：D21. 在数据结构中，数据的基本单位是（ ）。A. 数据项B. 数据元素C. 数据对象D. 数据文件答案：B22. 算法分析的目的是（ ）。A. 找出数据结构的合理性B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性答案：C23. 下列函数中，按它们在时的无穷大阶数，最大的是（ ）。A. lognB. nlognC. 2n/2D. n!答案：D24. （ ）是信息的载体，它能够被计算机识别、存储和加工处理。A. 数据B. 数据元素C. 结点D. 数据项答案

8、：A25. 下列程序段的时间复杂度为（ ）。for(i = 1;i < n; i+) y = y + 1; for(j=0; j <= (2 * n); j+) x+;A. O(n-1)B. O(2n)C. O(n2)D. O(2n+1)答案：C26. 下面程序段的时间复杂度为（ ）。i=1;while(i <= n) i=i*2;A. O(1)B. O(n)C. O(n2)D. O(log2n)答案：D27. 下面程序段的时间复杂度为（ ）。a=0; b=1;for(i = 2; i <= n; i+) s = a + b; b = a; a = s;A. O(1)B

9、. O(n)C. O(log2n)D. O(n2)答案：B28. 数据结构是一门研究非数值计算的程序设计问题中，计算机的（ ）以及它们之间的关系和运算等的学科。A.操作对象B. 计算方法C. 逻辑存储D. 数据映象答案：A29.在数据结构中，从逻辑上可以把数据结构分成（ ）。A. 动态结构和静态结构B. 紧凑结构和非紧凑结构C. 线性结构和非线性结构D. 内部结构和外部结构答案：C30. 算法分析的目的是（ ）。A. 找出数据结构的合理性B. 研究算法中输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性答案：D31. 算法分析的两个主要方面是（ ）。A. 空间复杂性和时

10、间复杂性B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性答案：A32. 计算机算法指的是 (1) ，计算机算法必须具备输入、输出和 (2) 等5个特性。算法分析的目的是 (3) ， 它的两个主要方面是 (4) 。数据结构中，与所使用的计算机无关的是数据的 (5) 结构。供选择的答案：(1)A. 计算方法B. 排序方法C. 调度方法 D. 解决问题的有限运算序列 (2)A. 可行性、可移植性和可扩充性B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性(3)A. 找出数据结构的合理性B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进

11、D. 分析算法的易懂性和文档性(4)A. 空间复杂性和时间复杂性B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性(5)A. 存储B. 物理C. 逻辑D. 物理和存储答案：DBCAC二、填空题（共5题）1. 数据结构按逻辑结构可分为两大类，它们分别是（ ）和（ ）。答案：线性结构 非线性结构2. 数据结构分为逻辑结构和存储结构，循环队列属于（ ）。答案：存储结构3. 问题处理方案的正确而完整的描述称为（ ）。答案：算法4. 一个算法的效率可分为（ ）效率和（ ）效率。答案：时间 空间5. 数据结构是一门研究非数值计算的程序设计问题中计算机的（ ）以及它们之间的（ ）和运算等的

12、学科。答案：操作对象 关系三、简答题（共12题）1. 设有两个算法在同一机器上运行，其执行时间分别为100n2和2n，要使前者快于后者，n至少要多大？答案：要使100n2快于2n时，必须满足100，可以算出n的值为15时，2n恰好大于100n2，所以至少应该是15。2. 按增长率由小至大的顺序排列下列各函数：(2/3)n、nn、n!、2n、lgn、nlgn,n3/2、（3/2）n。答案：3. 设有数据结构(D,R)，其中：D = 1，2，3，4，5，6，7，8R = （1，2），（1，7）（1，8)(2，3），(2，4)，（2，7)，(2，8)，（3，4)，（3，5)，（3，6)，(4，5），

13、（4，6）试画出其逻辑结构图，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点，并指出该图属于何种逻辑结构。答案：开始结点是指无前驱的结点，如图中满足该定义的开始结点为1;终端结点是指无后继的结点，如图中满足该定义的开始结点为5、6、7、8;该逻辑结构是非线性结构中的图结构。4. 计算下面程序段的时间复杂度。i=0; s=O;while(s < n) i+; s += i;答案：上述算法中的基本操作为while循环语句，设while循环执行T(n)次，则有表达式s=1+2+T(n)<n成立。即：，可得,显然有:所以该算法的时间复杂度为。5. 求下列算法的时间复杂度。cou

14、nt=0; x=1;while(x) x *= 2; count+;答案：O(log2n)6. 指出下面算法的功能并求出其时间复杂性。int suml（int n） int p=1, s=0; for(int i = 1; i <= n; i+) p *= i; s += p; return s;答案：计算的值。时间复杂性为O(n)。7. 指出下面算法的功能并求出其时间复杂性。void mtable(int n) for(int i = 1; i <= n; i+) for(int j = i; j <= n; j+) printf("i*j=%dt",

15、i*j); printf("n"); 答案： 打印出一个具有n行的乘法表，第i行中有n-i+l个乘法项，每个乘法项为i与的乘积。时间复杂性为O(n2）。8. 指出下面算法的功能并求出其时间复杂性。void cmatrix(int aMN, int d)/M和N为全局整型常量 for(int i = 0; i < M; i+） for(int j = 0; j < N; j+） aij *= d;答案：使数组aMN中的每一个元素均乘以d的值。时间复杂性为O(M*N）。9. 设n为正整数, 分析下面程序段中加下划线的语句的执行次数。for (int i = 1; i

16、 <= n; i+) for (int j = 1; j <= n; j+) cij = 0.0; for (int k = 1; k <= n; k+) cij = cij + aik * bkj; 答案： 10. 设n为正整数, 分析下面程序段中加下划线的语句的执行次数。x = 0; y = 0;for (int i = 1; i <= n; i+) for (int j = 1; j <= i; j+) for (int k = 1; k <= j; k+) x = x + y;答案：11. 设n为正整数, 分析下面程序段中加下划线的语句的执行次数。i

17、nt i = 1, j = 1; while (i<=n && j<=n) i = i + 1; j = j + i; 答案：i = 1时，i = 2，j = j + i = 1 + 2 = 2 + 1，i = 2时，i = 3，j = j + i = ( 2 + 1 ) + 3 = 3 + 1 + 2，i = 3时，i = 4，j = j + i = ( 3 + 1 + 2 ) + 4 = 4 + 1 + 2 + 3，i = 4时，i = 5，j = j + i = ( 4 + 1 + 2 + 3 ) + 5 = 5 + 1 + 2 + 3 + 4，i = k时，

18、i = k + 1，j = j + i = ( k + 1 ) + ( 1 + 2 + 3 + 4 + + k )，解出满足上述不等式的k值，即为语句i = i + 1的程序步数。解之得：(向上取整，即大于等于括号内数的最小整数)12. 设n为正整数, 分析下面程序段中加下划线的语句的执行次数。int i =1;do for(int j = 1; j <= n; j+) i = i + j;while(i < 100 + n);答案：for语句每执行一次，语句i=i+j将执行n次，而i的值会增加因此，当for语句执行k次后，i的值将变为故最终for语句的执行次数k为满足的最小整数k

19、，语句i = i + j的程序步数为n*k。即四、应用题（共5题）1. 试编写一个函数计算n!*2n的值，结果存放于数组AarraySize的第n个数组元素中，0 £ n £ arraySize。若设计算机中允许的整数的最大值为maxInt，则当n>arraySize或者对于某一个k (0 £ k £ n)，使得k!*2k > maxInt时，应按出错处理。可有如下三种不同的出错处理方式：(1) 用printf显示错误信息及exit(1)语句来终止执行并报告错误；(2) 用返回整数函数值0, 1来实现算法，以区别是正常返回还是错误返回；(3)

20、 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。【解答】#include <stdio.h>const int arraySize = 100;const int MaxInt = 0x7fffffff;int calc( int T , int n ) int i, value = 1;if ( n != 0 ) int edge = MaxInt / n / 2;for ( i = 1; i < n; i+ ) value *= i*2;if ( value > edge ) re

21、turn 0;value *= n * 2;Tn = value;printf("A %d = %dn", n, Tn);return 1;void main ( ) int AarraySize;int i;for ( i = 0; i < arraySize; i+ )if ( !calc ( A, i ) ) printf("failed at %d .n", i );break;2. 已知数组an中的元素为整型，设计算法将其划分为左右两部分，左边所有元素为偶数，右边所有元素为奇数，并要求算法的时间复杂度为O(n)。答案：从数组的两端向中间比

22、较，初始化两个变量i和j，其中i=0，j=n-1。对元素ai和aj执行如下循环：若ai为偶数，则i=i+l，循环执行直到ai为奇数转至;若aj为奇数，则j=j-1，循环执行直到aj为偶数转至;若i<j，交换ai和aj，i=i+l，j=j-1，继续循环。上述算法的C语言描述如下：void fu_jo(int a, int n) int i = 0, j = n-1, temp; while(i < j) while(ai%2 = 0) i+; while(aj%2 != 0) j-; if(i < j) temp =ai; ai = aj; aj = temp; i+; j-;

23、 上述算法使用两层循环完成了对数组的扫描过程，其中ai从前向后开始扫描，aj则从后向前开始扫描，当i>=j时扫描即停止，因此虽然是两层循环但只对数组扫描了一遍，所以，该算法的时间复杂度为O(n)。3. 算法设计：求整型数组an中的最大值和最小值，并分析该算法的时间复杂度。答案：算法的伪代码描述如下：将数组中前两个元素进行比较，较大的值存放在max变量中，较小的值存放在min变量中;从第三个元素开始依次取出数组中的每一个元素ai，执行下列操作，直到最后一个元素：a)如果ai>max，则max变量中的值被ai替换;b)如果ai<min，则min变量中的值被ai替换;输出最大值max，最小值min。算法的C语言描述如下：void fun_maxmin(int a, int n, int max, int min