软件技术基础试题库(3)

71．对有3600个记录的索引顺序表(分块表)进行查找,最理想的块长为___。( A.1800 B.60 C.1200

D. log2 3600

答案：B

72. 折半查找20个记录的有序表,若查找失败,比较关键字的次数____。( ) A.最多为6 B.最多为5 C.最多为4 D.最多为3 答案：B

73. 中序遍历一棵二叉排序树所得到的结点序列是键值的( )

A.递增或递减 B.递减 C.递增 D.无序 答案：

74．散列表中的冲突是指____。( ) A.两个元素具有相同的序号

B.两个元素的键值相同，而其他属性相同 C.不同的键值对应相同的存储地址 D.数据元素的地址相同

)

答案：

75．用线形探测法查找散列表，可能要探测多个散列地址，这些位置上的键值____。( )

A.一定是同义词 B.不一定是同义词 C.一定不是同义词 D.都相同 答案：

76．在初始为空的杂凑表中依次插入关键字序列(MON，TUE，WED，THU，FRI，SAT，

SUN), 杂凑函数为H(k)=i MOD 7，其中，i为关键字k的第一个字母在英文字母表中的序号，地址值域为[0:6]，采用线性再散列法处理冲突。插入后的杂凑表应该如________________所示。( ) A. 0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MON B. 0 1 2 3 4 5 6 TUE THU WED FRI SUN SAT MON C. 0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MON D. 0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON

答案：

77．设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个

表项的平均探查次数不超过1.5，则散列存储空间应能够至少容纳 个表项。（设搜索成功的平均搜索长度为Snl=(1+1/(1-a))/2,其中a 为装填因子）( ) A.400 B.526 C.624 D.676 答案：

78．对长度为10的表作选择(简单选择)排序,共需比较____次关键字。( ) A.45 B.90 C.55 D.110

答案：

79. 设有100个数据元素，采用折半搜索时，最大比较次数为 ( )。

A. 6 B. 7

C. 8 D. 10 答案：

80. 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样

的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是____。( ) A. 选择排序 B. 直接插入排序 C. 快速排序 D. 起泡排序 答案：C

81. 对5个不同的数据元素进行直接插入排序，最多需要进行( )

A. 8 B. 10 C. 15 D. 25 答案：

82. 采用折半查找方法进行查找，数据文件应为，且限于( )

A.有序表 顺序存储结构 B.有序表 链式存储结构 C.随机表 顺序存储结构 D.随机表 链式存储结构 答案：

83. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其存放

在已排序序列的合适位置，该排序方法称为 排序法。( ) A.插入 B.选择 C.希尔 D.二路并归 答案：

84. 就平均查找速度而言，下列几种查找速度从慢至快的关系是( )

A.顺序 折半 哈西 分块 B.顺序 分块 折半 哈西 C.分块 折半 哈西 顺序 D.顺序 哈西 分块 折半