首页 理论教育 二分查找相关代码|C++语言

二分查找相关代码|C++语言

时间:2023-08-13 理论教育 版权反馈
【摘要】:()A.1 B.2 C.3 D.54.给定队列的入队顺序1、2、3,共有几种可能的出队序列?A.O B.O C.O D.O6.在具有n个节点的双键表中做插入、删除运算,平均时间复杂度为()。A.O B.O C.O D.O7.经过下列运算后,QueueFront的值是()。

二分查找相关代码|C++语言

测试用例如下:

例12-9 给定数组num[10] ={1,2,3,4,5,6,7,8,9,10};目标值target为3。

第一步:取数组中间的值,中间下标mid=(0+9)/2=4,num[mid]=5;因为3<5,取5的前半部分作为一个新的数组,即{1,2,3,4},该数组保留原来的下标值。

第二步:重复第一步,中间下标mid=(0+3)/2=1,num[1]=2;因为3>2,取2的后半部分作为一个新的数组,即{3,4},该数组保留原来的下标值。

第三步:重复第一步,中间下标mid=(2+3)/2=2,num[2]=3;因为3=3,所以返回值为2。

代码实现:

至此,完成了二分查找的一般情况下的解决方法,但是还要考虑另一种情况:当数组存在重复元素的时候就会导致答案可能出错,因为要查找的是第一次出现的位置。

例12-10 num[5]={1,2,2,2,3};target=2;采用上面的方法得出的是下标2,而现在需要的答案是下标1。

所以对上面的代码进行如下改进,若目标值小于或等于中间的值则继续对前一部分进行操作。

一、选择题

1.下列不属于线性数据结构的是( )。

A.线性表 B.队列 C.栈 D.树

2.下列描述正确的是( )。

A.栈的操作是先进先出 B.栈的操作是先进后出

C.队列的操作是先进先出 D.队列的操作是先进后出

3.给定栈的入栈序列1、2、3,共有几种可能的出栈序列?( )

A.1 B.2 C.3 D.5

4.给定队列的入队顺序1、2、3,共有几种可能的出队序列?( )

A.1 B.2 C.3 D.4

5.对于顺序表来说,访问任一节点的时间复杂度是( )。

A.O(1) B.O(n) C.O(log2n) D.O(n2)

6.在具有n个节点的双键表中做插入、删除运算,平均时间复杂度为( )。

A.O(1) B.O(n) C.O(log2n) D.O(n2)

7.经过下列运算后,QueueFront(Q)的值是( )。

IniQueue(Q);EnQueue(Q,a);EnQueue(Q,a);DeQueue(Q,x);(www.xing528.com)

A.a B.b C.l D.2

8.一个栈的入栈序列是a,b,c,则栈的不可能的输出序列是( )。

A.acb B.abc C.bca D.cab

9.循环队列是空队列的条件是( )。

A.Q->rear==Q->front

B.(Q->rear+l)%maxsize==Q->front

C.Q->rear==0

D.Q->front==0

10.设S3=“IAM”,S4=“A TERCHER”,则Strcmp(S3,S4)=( )。

A.0 B.小于0 C.大于0 D.不确定

二、填空题

1.数据元素是数据的______。

2.数据的逻辑结构是对数据之间________的描述。

3.对于一个具有n个节点的单链表,在已知p所指节点后插入一个新节点的时间复杂度是______;在给定值为X的节点后插入一个新节点的时间复杂度是________。

4.对于栈,只能在________插入和删除元素。

5.循环队列进行DeQuene(Q,x)运算时,要执行的语句序列中有________%Queqe Size。

6.串的两种最基本的存储方式是________和________。

7.对称矩阵的上三角元素a[i,j]的值存放在一维数组V的元素V[k]中,k与i,j的关系是k=________。

8.稀疏矩阵的三元组中,第2列存储的是稀疏数组中非零元素所在的________。

9.已知二叉树有50个叶子节点,则二叉树的总节点数至少是________。

10.设有一棵二叉树有4个节点a,b,c,d,分别带权7,5,2,4,其带权路径最短为________。

11.二叉树按某种顺序线索化后,任一节点均有指向其前驱和后继的线索,这种说法________。

12.若要求一个稠密图G的最小生成树,最好用________算法来求解。

13.用迪杰斯特拉(Dijkstra)算法求n个顶点e条边的图中的某一顶点到其余各顶点间的最短路径的时间复杂度为________。

14.对于n个记录的集合进行快速排序,在最坏情况下所需要的时间是______。

图12-16 习题三二叉

15.在堆排序和快速排序中,若初始记录接近正序或反序,则选用________。

三、给定一棵二叉树如图12-16所示,写出它的前序、中序、后序遍历

四、一棵树的中序遍历为BEDGFAC,后序遍历为EGFDBCA,画出这棵树。

五、给定表(119,14,22,l,66,21,83,27,56,13,10),请按表中元素的顺序构造一棵平衡二叉树,并求其在等概率树情况下查找成功的平均长度

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈