数据结构简明教程（第 2 版） 配套练习题参考答案———————数据结构简明教程———————1
练习题 1 参考答案1
单项选择题（1）D （2）C （3）C （4）A （5）C（6）B （7）C （8）A （9）C （10）B2
填空题（1）①逻辑结构 ②存储结构 ③运算（不限制顺序）（2）①线性结构 ②非线性结构（不限制顺序）（3）①数据元素 ②关系（4）①没有 ②没有（5）①前驱 ②一 ③后继 ④任意多个（6）任意多个（7）①顺序 ②链式 ③索引 ④哈希（不限制顺序）（8）①时间 ②空间（不限制顺序）（9）问题规模（通常用 n 表示）
（10）辅助或临时空间3
简答题（1）答：运算描述是指逻辑结构施加的操作，而运算实现是指一个完成该运算功能的算法
它们的相同点是，运算描述和运算实现都能完成对数据的“处理”或某种特定的操作
不同点是，运算描述只是描述处理功能，不包括处理步骤和方法，而运算实现的核心则是处理步骤
（2）答：T1(n)=O(nlog2n)，T2(n)=O( )，T3(n)=O(n2)，T4(n)=O(nlog2n)
（3）答：j=0，第 1 次循环：j=1，s=10
第 2 次循环：j=2，s=30
第 3 次循环：j=3，s=60
第 4 次循环：j=4，s=100
w hile 条件不再满足
所以，其中循环语句的执行次数为 4
（4）答：语句 s++的执行次数2)2)(3(3)1()1(12121 nnnninniniinj
（5）答：其中 x++语句为基本运算语句， ninijninninnT1112)1()(1)(=O(n2)
（6） 答：由于内循环 j 的取值范围，所以 i≤n/2，则，该程序段的时间复杂度为 O(n2)
2/122/124/))
