数据结构课程课后练习习题答案.docx

《数据结构简明教程》练习题及参考答案 练习题 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. 排序方法 C. 求解问题的有限运算序列 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）一个算法的效率可分 ① 效率和 ② 效率。答：① ②空 答 （ 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 模， 出 的 复 度： T1 ( n)= nlog 2n-1000log 2n T2 ( n)= nlog 2 3 -1000log 2n 3 2 2 n T ( n)= n -1000log T ( n )=2 log n -1000log n 4 2 2 答： T1( n)=O( nlog 2n) ，T2( n)=O(n log)2 3， T3( n)=O( n2) ， T4( n)=O( nlog 2n) 。 （ 5）分析下面程序段中循 句的 行次数。 int j=0,s=0,n=100; do {j=j+1; s=s+10*j; } while (jn sn); 答： j =0，第 1次循 ： j =1， s=10。第 2次循 ： j =2， s=30。第 3次循 ： j =3， s=60。 第4次循环： j =4， s=100。 while 条件不再满足。所以，其中循环语句的执行次数为 4。 （ 6）执行下面的语句时，语句 s++的执行次数为多少？ int s=0; for (i=1;in-1;i++) for (j=n;j=i;j--) s++; n 2 i n 2 (n 3)(n 2) 答：语句 s的执行次数 1 (n i 1) n (n 1) 3 。 i 1 j n