测试用例如下:
例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。
所以对上面的代码进行如下改进,若目标值小于或等于中间的值则继续对前一部分进行操作。
一、选择题
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),请按表中元素的顺序构造一棵平衡二叉树,并求其在等概率树情况下查找成功的平均长度。
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。