数据结构 线性表 课后答案

1第 2 章线性表1．选择题(1)顺序表中第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是()。A．110B．108C．100D．120答案：B解释：顺序表中的数据连续存储，所以第 5 个元素的地址为：100+2*4=108。(2)在 n 个结点的顺序表中，算法的时间复杂度是 0(1)的操作是()。A.访问第 i 个结点(1WiWn)和求第 i 个结点的直接前驱(2WiWn)B.在第 i 个结点后插入一个新结点(1WiWn)C.删除第 i 个结点(1WiWn)D.将 n 个结点从小到大排序答案：A解释：在顺序表中插入一个结点的时间复杂度都是 O(n2),排序的时间复杂度为 O(n2)或O(nlog2n)。顺序表是一种随机存取结构，访问第 i 个结点和求第 i 个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是 0(1)。(3)向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动—的元素个数为()。A.8B.63.5C.63D.7答案：B 解释：平均要移动的元素个数为：n/2。(4)链接存储的存储结构所占存储空间()。A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B.只有一部分，存放结点值C.只有一部分，存储表示结点间关系的指针D.分两部分，一部分存放结点值，另一部分存放结点所占单元数答案：A(5)线性表若采用链式存储结构时，要求内存中可用存储单元的地址()。A.必须是连续的 B.部分地址必须是连续的C.一定是不连续的 D.连续或不连续都可以答案：D(6)线性表 L 在()情况下适用于使用链式结构实现。A.需经常修改 L 中的结点值 B.需不断对 L 进行删除插入C.L 中含有大量的结点 D.L 中结点结构复杂答案：B2解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。(7)单链表的存储密度()。A.大于 1B.等于 1C.小于 1D.不能确定答案：C解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比，假设单链表一个结点本身所占的空间为 D,指针域所占的空间为 N,则存储密度为：D/(D+N),—定小于 1。(8) 将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是()。A.nB.2n-1C.2nD.n-1答案：A解释：当第一个有序表中所有的元素都小于(或大于)第二个表中的元素，只需要用第二个表中的第一个元素依次与第一个表的元素比较，总计比较 n 次。(9) 在一个长度为 n 的顺序表中，在第 i 个元素(1WiWn+1)之前插入一个新元素时须向后移动()个元素。A.n-iB.n-i+1C.n-i-1D....