1.1：对有n个结点、e条边且采用数组表示法（即邻接矩阵存储）的无向图进行深度优先遍历，时间复杂度_____。
A O(n^2)
B O(e^2)
C O(n+e)
D O(n×e)
1.2：在12个互异元素构成的有序数组 a[1..12] 中进行二分查找(即折半查找，向下取 整)，若待查找的元素正好等于a[9]，则在此过程中，依次与数组中的（ ）比较后，查找成功结束。
A. a[6]、 a[7]、 a[8]、 a[9]
B. a[6]、a[9]
C.a[6]、 a[7]、 a[9]
D. a[6]、 a[8]、 a[9]
1.3：用哈希表存储元素时，需要进行冲突（碰撞）处理，冲突是指_____。
A 关键字被依次映射到地址编号连续的存储位置。
B 关键字不同的元素被映射到相同的存储位置。
C 关键字相同的元素被映射到不同的存储位置。
D 关键字被映射到哈希表之外的位置。
【试题分析：哈希表（hashtable）通过一个已记录的关键字为自变量的函数（哈希函数）得到该记录的存储地址，所以在哈希表中进行查找操作时，需用同一哈希函数计算得到待查记录的存储地址，然后到相应的存储单元去获得有关信息再判定查找是否成功。用哈希表存储元素时，需要进行冲突（碰撞）处理，这个冲突指的是关键字不同的元素被映射到相同的存储位置。 】
网友评论