数据结构简明教程（第 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/))12((ninijnininm3log 2n32.练习题2 参考答案1. 单项选择题（1）A （2）C （3）A （4）B （5）C（6）D （7）C （8）B （9）A （10）C（11）B （12）A （13）C （14）D （15）D（16）D （17）A （18）C （19）A （20）D2. 填空题（1）L.length=0（2）O(1)（3）O(n)（4）n-i（5）①物理存储位置 ②指针域（6）①前驱 ②O(n)（7）q=p->nex t; p->nex t=q->nex t; free(q);（8）s->nex t= p->nex t; p->nex t=s;（9）O(1)（10）L->nex t==L3. 简答题（1）答：顺序存储结构中，逻辑上相邻元素的存储空间也是相邻的，无需额外空间表示逻辑关系，所以存储密度大，同时具有随机存取特性。缺点是插入或删除元素时平均需要移动一半的元素，同时顺序存储...
