在顺序线性表中存放n个整数 n的值由用户输入确定 线性表可以是有序表或无序表。比较各查找算法在
已帮助 人
在顺序线性表中存放n个整数，n的值由用户输入确定，线性表可以是有序表或无序表。比较各查找算法在不同情况下的时间性能。 各查找算法的实测时间性能包括两个指标：算法执行的绝对时间和关键字的平均比较次数。 各查找算法要求评测查找成功与不成功的两种情形。 为了能比较出各种查找算法执行的绝对时间，需要对表中的数据进行较大量的查找，设为m次，m的值也由用户输入确定。当输入m为1000000时，则对线性表作1000000次查找。 （1）比较在有序表和无序表中进行顺序查找时，查找成功和查找失败时的算法执行的绝对时间和关键字的平均比较次数。 （2）比较在同一有序表中进行顺序查找和二分查找时的时间性能。 （3）比较在同一有序表中进行非递归二分查找和递归二分查找的时间性能。
回答
共1条回复-
A 解析：本题考查线性表的插入。线性表是最简单和最常用的一种数据结构，是由相同类型的结点组成的有限序列。线性表常用的存储方式有顺序存储和链接存储。线性表的顺序存储是将线性表的结点依次存储在数组中，用数组元素的顺序存储来体现线性表中结点的先后次序关系。在对顺序存储的线性表进行插入时，完成插入主要有以下步骤：(1)检测插入要求的有关参数的合理性；(2)把原来的第n-1个结点至第i个结点依次往后移一个数组元素位置；(3)把新结点放在第i个位置上，修改线性表的结点个数。在具有N个结点的线性表上插入新结点时，其时间主要花费在移动结点的循环上。若插入任一位置的概率相等，从后往前依次需要移动的次数为0，1，2，…，n，所以，平均移动次数为n/2。