(D)对TSP问题而言，遍历算法和贪心算法求得的解是不一样的，贪心算法是求精确解，执行更快一些，而遍历算法是求近似解，执行更慢一些；
答案：C 解释：
本题考查对贪心算法与遍历算法的简单理解
贪心算法：一定要做当前情况下的最好选择，否则将来可能会后悔，故名“贪心”。如果以A城市为起点，选择最近的下一点，为B城市。以B城市为起点，选择最近的下一个城市，可以选择C或D，以选择D为例。以D为起点，选择最近的下一点，为C城市。最后回到A。整个过程的花费为：14。于是，该贪心算法的解为14。而通过遍历可知，该问题的最优解为A-B-C-D-A，花费为13。可见，贪心算法与遍历算法的解不会总是完全相同。而贪心
3
算法只会做当前情况下最优选择，其时间复杂度为n级别。而遍历则会将各种情况考虑在内，其时间复杂度为（n-1）！级别当城市的数量变多时，遍历算法将会出现组合爆炸。故，相比之下，贪心算法的计算速度更快。所以(C)选项是正确的。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(2)关于TSP，下列说法不正确的是_____。
(A)TSP问题的一个可能解就是n个城市的一个组合
都对应不同的城市。若要求得最优解，则必须对所有的组合，即所有可能解进行比较。
(B)TSP问题的难点是当n值很大时，组合数目非常庞大(组合数目为n!)，以致于计算机不能在有限时间内完成所有的组合；
(C)TSP问题的难点是当n值很大时，组合数目非常庞大(组合数目为n!)，虽如此，计算机仍然能够在有限时间内完成所有的组合；
(D)上述思想--对所有组合进行比较的思想，即是所谓的遍历算法策略，它仅仅对n值很小的TSP问题是能行的。
答案：C 解释：
本题考查对TSP组合优化问题的理解
对所有组合进行比较的思想，即所谓的遍历算法策略，其组合数目为n!。2001年解决了德国15112个城市的TSP问题，使用了美国Rice大学和普林斯顿大学之间互连的、速度为500MHz 的Compaq EV6 Alpha 处理器组成的110台计算机，所有计算机花费的时间之和为22.6年。由此可见，当n巨大时，用遍历算法解决TSP问题是不现实的。所以(C)选项错误。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(3)关于TSP的贪心算法的求解思想，下列说法不正确的是_____。
(A)无需对所有组合(所有可能解)进行比较，而仅需依照某种办法确定其中的一个组合即可，该组合不一定是最优解，但却是一个较优解或次优解；
(B)在确定一个组合
(C)贪心算法确定的路径，是由局部最优(即tk+1在tk看来是最优的)组合起来的路径，该
路径从全局角度也一定是最优的；
(D)对一个具体的TSP问题，每次执行贪心算法，所求得的最终解可能是不同的。
答案：C 解释：
本题考查对TSP贪心算法的理解
（A）(B)选项都是对贪心算法的描述，贪心算法的核心就是：只考虑当前情况下得最优解。故（A）（B）正确。贪心算法得到的解释可行解，但不一定是最优解，故(C)错误。在执行贪心算法的过程中，会遇到下一步有两个最优选项的情况，所以每次执行贪心算法的最终解的结果可能是不同的。故(D)正确。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(4)下列哪些问题可应用求解TSP的算法，正确的是_____。
(A)电路板上需要钻n个孔，选择一条最短路径使机器移动并完成所有孔的钻孔工作的问题(机器在电路板上钻孔的调度问题)；
(B) n个盘子在三个柱子上的移动问题(梵天塔问题或者说汉诺塔问题)； (C) n座桥， 走过每座桥且仅走过一次的问题(图的遍历问题)； (D)上述(A)(B)(C)都可以。
答案：A 解释：
本题考查对TSP问题抽象的理解
求解TSP问题采用的是贪心算法。(A)选项所描述的问题其实就是TSP问题。（B）选项所描述的问题是梵天塔问题，应该采用的是递归的思想。（C）选项所描述的图的遍历问题，主要有深度优先搜索，和广度优先搜索两种解决方法，不是贪心算法。综上，（A）选项正确。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(5)关于下列四个数学抽象，说法正确的是_____。
(数学抽象I)城市记为：V={v1,v2,…,vn}，任意两个城市vi,vj∈V之间的距离记为：dvivj，问题的解是寻找所有城市的一个访问顺序T={t1,t2,…,tn}，其中ti∈V，使得min ni=1dtiti+1，这里假定除tn+1=t1外，ti ? tj(i?j时)。
(数学抽象II)电路元件记为：V={v1,v2,…,vn}，任意两个元件vi,vj∈V之间的距离记为：dvivj，问题的解是寻找所有元件之间的一个访问顺序T={t1,t2,…,tn}，其中ti∈V，使得min ni=1dtiti+1，这里假定除tn+1=t1外，ti ? tj(i?j时)。
(数学抽象III)图的结点记为：V={v1,v2,…,vn}，任意两个结点vi,vj∈V的边的权值记为：dvivj，问题的解是寻找所有结点之间的一个访问顺序T={t1,t2,…,tn}，其中ti∈V，使得min ni=1dtiti+1，这里假定除tn+1=t1外，ti ? tj(i?j时)。
(数学抽象IV)图的结点记为：N = {1,2，…，n}，任意两个结点i，j的边的权值记为：dij，问题的解是寻找所有结点之间的一个访问顺序t={t1,t2,…,tn}，其中ti?V，使得min min ni=1dtiti+1，这里假定除tn+1=t1外，ti ? tj(i?j时)。
(A)只有数学抽象I是TSP问题，数学抽象II和III不是；
(B)数学抽象I和III可以被认为是TSP问题，数学抽象II和IV不是； (C)数学抽象I、II、III和IV都可以被认为是TSP问题；
(D)上述说法都不正确。
答案：C 解释：
本题考查对TSP问题抽象的理解
I就是对最原始的TSP问题的抽象描述。II也是对TSP问题的描述，只是将城市换成了电子元件。III和IV是对同一问题的不同表述罢了，都是TSP问题，只是将城市换为了图。四个数学抽象都可以被认为是TSP问题。故选项（C）正确。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
5、数据结构是算法设计的重要步骤，针对不同问题的算法设计应该选择适当的数据结构，不同的数据结构会使得解决问题的算法的性能有所不同。回答下列问题。 (1)关于数据结构，下列说法不正确的是_____。
(A)数据结构是问题域数学模型中各种数据的存储结构； (B)数据结构是将逻辑上有一定语义关系的数据，转换成计算机可以存储和处理的变量，便于算法和程序进行处理； (C)数据结构是将具有一定语义关系的变量进行命名，以便隐藏数据结构内部的操作细节，便于算法按逻辑语义通过操控该名字来操控该数据结构； (D)数据结构包含了数据的逻辑结构、存储结构及其操作； (E)上述说法有不正确的。
答案：E 解释：
本题考查对数据结构的理解
数据结构是数据的逻辑结构、存储结构及其操作的总称，它提供了问题求解/算法的数据操纵机制。(A) (B) (C)(D)的说法都没有问题。所以（E）是不正确的。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(2)关于数据结构，下列说法不正确的是______________？
(A) 数据结构由逻辑结构、存储结构及运算3部分组成； (B) 存储结构定义了数据在存储器中的存储方式； (C) 向量使用顺序存储结构，并借助元素在存储器中的相对位置来表示数据元素的逻辑关系；
(D) 在树结构中，指针用于表达元素之间的逻辑关系——父子关系，每个元素的指针指向其父节点，因此一个元素可以有一个或多个指针。
答案：D 解释：
本题考查对数据结构的理解 数据结构是数据的逻辑结构、存储结构及其操作的总称。（A）正确。数据的存储结构
也就是在反映数据逻辑关系的原则下，数据在存储器中的存储方式。（B）正确。向量确实是使用顺序存储结构，并且借助元素在存储器中的相对位置来表示数据元素的逻辑关系的，（C）正确。在树结构中，如果每个元素的指针都指向其父节点，那么每个元素只能有一个指针。因为每个元素只有一个父亲。故（D）错误。 详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
6. 数据通常要存储在存储器中，存储器是按地址访问的存储单元的集合，因此存储器可被认为是按线性方式组织数据。数组是高级语言中经常使用的一种数据结构，其按照不同的下标可访问数组的不同的元素。如下图所示：
(1)关于数组和存储器，下列说法不正确的是_____。
(A)和存储器一样，数组是按线性方式组织数据； (B)和存储器一样，一维数组是按线性方式组织数据，一个数据元素需要一个存储单元来存储，一个下标即相当于一个存储单元的地址； (C)和存储器一样，一维数组是按线性方式组织数据，一个数据元素需要一个或多个存储单元来存储，一个下标即相当于一个存储单元的地址；
(D)和存储器一样，一维数组是按线性方式组织数据，一个数据元素需要一个或多个存储单元来存储，一个下标即相当于一个或多个存储单元的地址；
答案：C 解释：
本题考查对存储器和数组的理解。 数组是按照线性方式组织数据的。当一个数据元素需要多个存储单元存储时，一个下标代表的就是多个存储单元的地址，所以(C)的说法不准确。其余说法都对。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(2)请对照上图的左子图和右子图来观察，右子图的二维数组是按左图的形式存储在存储器中。则D[4][2]元素所对应的存储单元的存储地址为_____。
(A)00000000 00000101； (B)00000000 00001000； (C)00000000 00001010；
(D)上述都不正确；
答案：B 解释：
本题考查对存储器和数组的理解。 图中，二维数组中，D[4][2]对应的元素是80，而且是第二个80.在存储器中，找到第二个80的位置，其所对应的地址为：00000000 00001000；（B）正确。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(3)请参照上图的左子图和右子图来观察，右子图的二维数组是按左图的形式存储在存储器中。则D[i][j]元素，与对应存储单元的存储地址的转换关系正确的为_____。
(A)D[i][j]元素的存储地址=数组的起始地址+((i-1)*每行的列数+j-1)*单一元素占用存储单元的数目； (B)D[i][j]元素的存储地址=数组的起始地址+(i-1)*每行的列数+j-1；此公式在任何情况下都正确； (C)D[i][j]元素的存储地址=数组的起始地址+((j-1)*每行的列数+i-1)*单一元素占用存储单元的数目；
(D)D[i][j]元素的存储地址=数组的起始地址+(j-1)*每行的列数+i-1；此公式在任何情况下都正确；
答案：A 解释：
本题考查对存储器和二维数组的理解。 记住数组的下标是从0开始编号的。((i-1)*每行的列数+j-1)得到二维数组中，所求的元素的下标偏移量。((i-1)*每行的列数+j-1) *单一元素占用存储单元的数目得到地址的偏移量。再加上数组的起始地址，便可得到所求元素的地址。（A）正确。 详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
7.“树”是一种典型的数据结构，在很多算法中都应用树来组织相关的数据。树是组织层次型数据的一种存储结构，它将每一个数据称为一个数据元素。见下图I.示意，采用三个数组来存储树型数据，一个数组TreeElement[]存放数据元素本身，一个数组LeftPointer[]存放该数据元素的左侧子元素的存放地址(简称为左指针)，另一个数组RightPointer[]存放该数据元素的右侧子元素的存放地址(简称为右指针)。参照图I.，回答下列问题。