牛客网专项练习总结（二）

1.对任何数据结构链式存储结构一定优于顺序存储结构()

A   对                             B错

  选B              分析：

顺序表

• 优点：查找和修改（首先要查找到）效率高，空间占用比链表小，时间复杂度 O(1)
• 缺点：插入和删除元素时，后面的元素都需要进行移动，编译时确定大小，时间复杂度 O(n)

链表

• 优点：插入和删除元素比较方便，只需要修改指针，空间大小不必指定，时间复杂度 O(n)
• 缺点：查询和修改（首先要查找到）效率并不高，而且因为添加了指针等中间数据结构，所以空间占用比顺序表大，时间复杂度 O(1)

 2.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。

选C                     分析：

没有循环，正常读取数组下标是常数，O（1）

3.使用二分搜索算法在 1000 个有序元素表中搜索一个特定元素，在最坏情况下，搜索总共需要比较的次数为（ ）。

A.10                                          B.11

C.500                                         D.1000

选A                      分析：

二分搜索的时间复杂度是：

O(log2 n)如果是整数，则就是这个数，如果不是整数，那么就取下线然后再加1

至多比较次数是⌊log2(n)⌋+1,其中⌊ ⌋表示向下取整

4.广告系统为了做地理位置定向，将IPV4分割为627672个区间，并标识了地理位置信息，区间之间无重叠，用二分查找将IP地址映射到地理位置信息，请问在最坏的情况下，需要查找多少次?

A.17                                                     B.18

C.19                                                     D.20

选D                分析：

log(627672)/log(2) = 19.26

5.假定对有序表: (3,4,5,7,24, 30,42,54,63, 72, 87, 95)进行折半查找，假定每个元素的查找概率相等，则查找成功时的平均查找长度是( ）
(要求画出描述折半查找过程的判定树）

 

选A

6.稀疏矩阵压缩存储后,必会失去随机存取功能()

A.对        B.错

选A                        分析：

稀疏矩阵在采用压缩存储后将会失去随机存储的功能。因为在这种矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。

7.已知字符串S 为“abaabaabacacaabaabcc”，模式串 t 为“abaabc”。采用 KMP 算法进行匹配，第一 次出现“失配”(s[i]≠t[j])  时，i=j=5，则下次开始匹配时，i 和 j 的值分别是 （） 。

选C                             分析：

先计算模式串abaabc的next数组

abaabc

011223

当匹配到i=5时，a！=c，

abaabaabacacaabaabcc

abaabc

123456789

然后 next[5]=3，移动模式串t往后3个位置，

abaabaabacacaabaabcc

xxxabaabc

12345678

i=5，j=2，继续比较

8.以下二维数组声明中，正确的是（ ）。

 

选B                          分析：

A:照此声明去定义的话，数组的一维会越界，因为b[2][3]中的2表示一维只能有两个字符或字符串，而由花括号中初始化的值可知，此时有三个一维字符，已经越界了

B,D:根据二维数组声明的规则，只能省去一维的大小，既不能仅仅舍去二维的大小，也不能两个都舍去。

9.以下多维数组声明语句中，不正确的有（  ）。

答案应该是CD吧，C不能指定数组大小；D前面一个已经定为3长度了所以赋值时也应该有3个

10.对于静态表的顺序查找法，若在表头设置监视哨，则正确的查找方式为（）。

查找过程从表中的第一个（或最后一个）记录开始，逐个进行比较

监视哨就是用来判定是否查找成功

选C