2019.2.191.考虑以下二分查找的代码：#include <stdio.h>
int bsearch(int array[], int n, int v)
{
int left, right, middle;
left = 0, right = n - 1;
while (left <= right) {
middle = left + (right - left) / 2;
if (array[middle] > v ) {
right = middle;
} else if (array[middle] < v) {
left = middle;
} else {
return middle;
}
}
return -1;
}
对于输入array为：{2, 6, 8, 10, 13, 25, 36, 45, 53, 76, 88, 100, 127}， n = 13, v = 127时,运行bsearch函数，while循环调用的次数为____。 1 3 4 5 6 无数次
m的取值为6,9,10,11,11,11,11所以会无限次循环。下面是正确的二分查找
public static int Method(int[] nums, int low, int high, int target)
{
while (low <= high)
{
int middle = (low + high) / 2;
if (target == nums[middle])
{
return middle;
}
else if (target > nums[middle])
{
low = middle + 1;
}
else if (target < nums[middle])
{
high = middle - 1;
}
}
return -1;
}
2.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) （N+1）/2 N/2 N [（1+N）*N ]/2
第一个数的比较次数为1，第二个数的比较次数为2。。。以此类推第N个数的比较次数为N，所以总的比较次数为1+2+…+N=N(N+1)/2,平均比较次数为(N+1)/2,也即平均查找长度。
3.对有18个元素的有序表r[0…17],进行二分查找，则查找r[3]的比较序列下标为（） 0、1、2 8、4、1、2 8、3 8、3、1、2
第一次,下标范围0–17 比较序列r[8]第二次,下标范围0–7 比较序列r[3]
4.对于关键字序列（16,10,20,12,18,7,14,13,5,19），不可能构成其二叉排序树中一条查找路径的序列是（ ） 16,10,7,5 16,20,18,19 16,10,7,12,14 16,10,12,14
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；（3）左、右子树也分别为二叉排序树；
5.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找并且索引表和块内均采用顺序查找，则其平均查找长度为( )。 6 11 5 6.5
分块查找会分两部分进行,第一步先进行索引表查找判断其在那个字表中,第二步然后进行在字表中的查找索引表有5个元素 所以平均查找长度为:(1+5)/2=3字表中有6个元素,所以平均查找长度为:(1+6)/2=3.5所以总的平均查找长度为3+3.5=6.5
6.执行()操作时,需要使用队列做辅助存储空间 查找哈希(Hash)表 广度优先搜索网 前序(根)遍历二叉树 深度优先搜索网
深度优先搜索要借助栈；广度优先搜索要借助队列；
7.具有12个关键字的有序表,折半查找的平均查找长度() 3.1 4 2.5 5
具体查找如下图所示：查找一次：6.查找两次：3、10查找三次：1、4、8、11查找四次：2、5、7、9、12
8.顺序表查找指的是在顺序存储结构上进行查找。（ ） 正确 错误
折半查找最坏的情况下查找log(n)+1次，而二叉查找树最坏的情况是查找n次。(退化为单链表)
9.请问对一个排好序的数组进行查找，用平均时间复杂度最小的算法，时间复杂度为（） O(n) O(lgn) O(nlgn) O(1)10.折半查找与二元查找树的时间性能在最坏的情况下是相同的() 对 错
二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树二叉查找树数最坏的情况下是链表的形式。折半查找最坏的情况是logN+1
11.KMP算法下，长为n的字符串中匹配长度为m的子串的复杂度为（） O（N） O（M+N） O（M+LOGM） O（N+LOGM）
未解决！！！！！！
12.在一个有8个int数据的数组中，随机给出数组的数据，找出最大和第二大元素一定需要进行（）次比较： 8 9 10 1113. 既希望较快的查找又便于线性表动态变化的查找方法是() 顺序查找 折半查找 分块查找 哈希法查找
索引顺序查找又称为分块查找顺序查找，算法简单，时间复杂度O(n);折半查找，要求有序，O(log n);二叉搜索树，动态，查找性能取决于二叉树的形状，——》二叉平衡树，越平衡，时间复杂度越接近于O(log n); 哈希表：特殊的应用，查找一步到位
2019.2.201.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。 log2n+1 log2n-1 log2n log2(n+1)
平衡二叉树:一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树,查找时间的时间复杂度为O(log2n)。二叉查找树（Binary Search Tree），或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。
设散列表的长度为10，散列函数H(n)=n mod 7，初始关键字序列为 (33，24，8，17，21，10)，用链地址法作为解决冲突的方法，平均查找长度是（） 1 1.5 2 2.5
链地址法，将所有具有相同哈希地址的而不同关键字的数据元素连接到同一个单链表中33%7=5 24%7=3 8%7=1 17%7=3 放在24后面（24->17）21%7=0 10%7=3放在17后面（24->17->10）（1+1+1+2+1+3）/6=1.5
从n个数里面找最大的两个数理论最少需要比较 2logn 2 logn -1 n+ logn -2 2n-3
所有次数控制着，最终冠军，每一层的控制着亚军。类似比赛晋级，两两配对比较，赢的再两两配对，最后得到冠军(最大的数)，可以看成是一棵二叉树，以4人为例：00 20 1 2 3可以看出，找出最大的数比较次数是n-1。然后第二大的数肯定是跟冠军比较过的数字，那么很明显每一层都有一个，所以有logn-1次比较。
所以总共是n+logn-2次比较4.下面哪一方法可以判断出一个有向图是否有环(回路)( ) 深度优先遍历 拓扑排序 Dijkstra求最短路径 求关键路径
绝对能判断有向图是否有环的是：1.DFS2.拓扑排序3.最短路径是允许有环的！C肯定不选。4.D可选可不选。关键路径能不能判断一个图有环还存在一些争议。关键路径本身虽然不允许有环，但求关键路径的算法本身无法判断是否有环，判断是否有环的是关键路径的第一步——拓扑排序。所以这个问题的答案主要是看你从哪个角度出发看问题。
若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为()(1<=i<=n+1) O(0) O(1) O(n) O(n2)6.有 1000 个无序的整数，希望使用最快的方式找出前 50 个最大的，最佳的选择是（ ） 冒泡排序 基数排序 堆排序 快速排序T(n)=O(f(n))中，函数O（）的正确含义为（） T(n)为f（n）的函数 T（n）为n的函数 存在足够大的正整数M，使得T（n）≤M×f（n）8.线性表(a1,a2,…,an)以链接方式存储时,访问第i位置元素的时间复杂性为() O(i) O(1) O(n) O(i-1)void recursive(int n, int m, int o)
{
if (n <= 0)
{
printf("%d,%d\n", m, o);
}
else
{
recursive(n - 1, m + 1, o);
recursive(n - 1, m, o + 1);
}
}
以上函数的时间复杂度（） O(nmo) O(n2*m2) O(2^n) O(n!)下面是一段求最大值的程序，其中 datalist 是数据表， n 是 datalist 的长度int GetMax(int n,int datalist[])
{
int k=0;
for(int j=1;j<n;j++)
if(datalist[j]>datalist[k])
k=j;
return k;
}
请问该程序段的 McCabe 环路复杂性为多少？（） 2 3 4 5以下描述错误的是： KMP算法的时间复杂度是O(n) 最长路径问题有多项式时间解 最大流问题和最小割问题是等价的 PageRank算法总是会收敛算法的时间复杂度取决于（） 待处理数据的状态 处理器的速度 问题的规模 程序所占空间}

3.对于顺序存储的线性表，其算法的时间复杂度为O(1)的运算应该是（）。A.将n个元素从小到大排序B.删除第i(1<=i<=n)个元素C.改变第i(1<=i<=n)个元素D在第i(1<=i<=n)个元素后插入一个新元素顺序存储即顺序表，链式存储即链表首先排除B和D，因为第i个元素不是最后一个元素，如果在表尾插入和删除元素，时间复杂度是为O(1)删除第i个元素需要把i后面的元素都往前移插入第i个元素需要把i后面的元素都往后移所以BD排除对于A选项，对n个元素排序最小也要O(n)，相关的排序算法类似冒泡算法等这里不做叙述对于顺序表，是随机存取的，所以找第i个元素可以直接找，修改的时间复杂度为O(1)，故选C作者在做这题的时候看成链式表了…5.设线性表中有2n个元素，（）在单链表上实现要比在顺序表上实现效率更高。A.删除所有值为x的元素B.在最后一个元素的后面插入一个新元素C.顺序输出前k个元素D.交换第i个元素和第2n-i-1个元素的值（i=0,…,n-1）选A，单链表是链式存储，删除只需要修改前结点的指针，顺序表删除的话需要移动大量的数据，所有对于本题来说单链表实现的效率更高B选项需要先遍历单链表找到最后一个元素，顺序表可以直接读取最后一个元素C选项单链表和顺序表效率相同D选项在找到第2n-i-1的值时，单链表需要遍历，顺序表可以直接读取，所以单链表效率更低7.给定有n个元素的一维数组，建立一个有序单链表的最低时间复杂度是（）A.O(1)B.O(n)C.O(n2)D.O(nlog2n)本题的关键字是有序，即这个单链表的元素是有序的本题可以有两个方向进行：①直接插入排序，时间复杂度是O(n2)②先排序数组，在插入单链表，排序数组的时间复杂度最好是O(nlog2n)故选D8.将长度为n的单链表链接在长度为m的单链表后面，其算法的时间复杂度采用大O形式表示应该是()A.O(1)B.O(n)C.O(m)D.O(n+m)思路是，遍历m，找到m的尾结点，把指针域指向n链表的首结点，故算法的时间复杂度是O(m)可以联想的是，如果m链表有尾指针的话，那么算法时间复杂度就是O(1)10.在一个长度为n的带头结点的单链表h上，设有尾指针r，则执行（）操作与链表的表长有关。A.删除单链表中的第一个元素B.删除单链表中的最后一个元素C.在单链表第一个元素前插入一个新元素D.在单链表最后一个元素后插入一个新元素首先排除A、C，因为第一个元素跟表长没有关系，D选项因为有尾指针，所以不用遍历单链表B选项需要遍历单链表，所以跟表长有关注意：尾指针是指向尾结点的，不是尾结点的指针域19.一个链表最常用的操作是在末尾插入结点和删除结点，则选用（）最节省时间A.带头结点的双循环链表B.单循环链表C.带尾指针的单循环链表D.单链表插入和删除都要改变相邻结点的指针域，肯定是双循环链表最节省时间BCD都要遍历20.设对n（n>1）个元素的线性表运算只有4种：删除第一个元素；删除最后一个元素；在第一个元素之前插入新元素；在最后一个元素之后插入新元素，则最好使用（）A.只有尾结点指针没有头结点指针的循环单链表B.只有尾结点指针没有头结点指针的非循环双链表C.只有头结点指针没有尾结点指针的循环双链表D.既有头结点指针又有尾结点指针的循环单链表对于A，删除最后一个元素时需要遍历单链表，所以时间复杂度是O(n)对于B，因为没有头指针，所以需要遍历到最后一个元素，尾结点的指针指向头结点，时间复杂度是O(n)C最四个运算的时间复杂度都尾O(1)对于D，删除最后一个的时候还是需要遍历错题的原因主要是对概念还比较模糊，其实答案都比较简单…
11
点赞
踩
43
收藏
觉得还不错?
一键收藏
打赏
第二章线性表选择题有关问题王道考研第二章线性表选择题有关问题复制链接
前端小王hs
CSDN认证博客专家
CSDN认证企业博客
分类专栏
您愿意向朋友推荐“博客详情页”吗？
强烈不推荐
不推荐
一般般
推荐
强烈推荐
提交
成就一亿技术人!
hope_wisdom 发出的红包
实付元使用余额支付
点击重新获取
钱包余额
0
抵扣说明： 1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。余额充值
}