文档介绍：《数据结构简明教程》练****题及参考答案练****题 1 1. 单项选择题(1) 线性结构中数据元素之间是( )关系。 A. 一对多 B. 多对多 C. 多对一 D. 一对一答: D(2) 数据结构中与所使用的计算机无关的是数据的() 结构。 A. 存储 B. 物理 C. 逻辑 D. 物理和存储答: C(3) 算法分析的目的是()。 A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性答: C(4) 算法分析的两个主要方面是()。 A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性答: A(5) 计算机算法指的是()。 A. 计算方法 B. 排序方法 D. 调度方法答: C(6) 计算机算法必须具备输入、输出和()等5 个特性。 A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性答: B 2. 填空题(1) 数据结构包括数据的①、数据的②和数据的③这三个方面的内容。答: ①逻辑结构②存储结构③运算(2) 数据结构按逻辑结构可分为两大类,它们分别是①和②。答: ①线性结构②非线性结构(3) 数据结构被形式地定义为( D,R ), 其中 D是①的有限集合,R是D 上的②有限集合。答: ①数据元素②关系数据结构简明教程(4) 在线性结构中, 第一个结点①前驱结点, 其余每个结点有且只有 1 个前驱结点; 最后一个结点②后继结点,其余每个结点有且只有 1 个后继结点。答: ①没有②没有(5) 在树形结构中, 树根结点没有①结点, 其余每个结点有且只有②个前驱结点; 叶子结点没有③结点,其余每个结点的后继结点数可以是④。答: ①前驱②1③后继④任意多个(6) 在图形结构中,每个结点的前驱结点数和后继结点数可以是( )。答: 任意多个(7) 数据的存储结构主要有四种,它们分别是①、②、③和④存储结构。答: ①顺序②链式③索引④哈希(8) 一个算法的效率可分为①效率和②效率。答: ①时间②空间 3. 简答题(1) 数据结构和数据类型两个概念之间有区别吗? 答: 简单地说,数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素,而且还在其上定义了一组操作。(2) 简述线性结构、树形结构和图形结构的不同点。答: 线性结构反映结点间的逻辑关系是一对一的,树形线性结构反映结点间的逻辑关系是一对多的,图在结构反映结点间的逻辑关系是多对多的。(3) 设有采用二元组表示的数据逻辑结构 S= ( D,R ), 其中 D={ a,b,…,i}, R={( a,b) ,(a,c) ,(c,d) ,(c,f ),(f,h ),(d,e ),(f,g ),(h,i )} ,问相对于关系 R ,哪些结点是开始结点,哪些结点是终端结点? 答: 该逻辑结构为树形结构,其中 a 结点没有前驱结点,称为根结点,b、e、g、i结点没有后继结点, 是终端结点,也称为叶子结点。(4) 以下各函数是算法中语句的执行频度, n 为问题规模,给出对应的时间复杂度: T 1(n )=n log 2n- 1000log 2nT 2(n )=3 logn - 1000log 2nT 3(n )=n 2- 1000log 2nT 4(n )=2 n log 2n- 1000log 2n答:T 1(n )=O( n log 2n),T 2(n )=O( ),T 3(n )=O( n 2),T 4(n )=O( n log 2n)。(5) 分析下面程序段中循环语句的执行次数。 int j=0 ,s=0 ,n=100; do {j=j+1; s=s+10*j; }while (j<n && s<n); 答: j =0 ,第 1 次循环: j =1 ,s =10 。第 2 次循环: j =2 ,s =30 。第 3 次循环: j =3 ,s =60 。第4 次循环: j =4 ,s =100 。 while 条件不再满足。所以,其中循环语句的执行次数为 4。 3 logn3 练****题及参考答案(6) 执行下面的语句时,语句 s++ 的执行次数为多少? int s=0; for (i=1;i<n-1;i++) fo r(j=n;j>= i;j--) s++; 答: 语句 s 的执行次数 2 )2 )(3(3)1()1(1 21 21???????????????????nnnnin ni ni inj?。(7)设n 为问题规模,求以下算法的时间复杂度。 void fun1(int n) {int x=0 ,i ;for (i=1;i<=n;i++) for (j=