测试用例如下:
例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)，请按表中元素的顺序构造一棵平衡二叉树，并求其在等概率树情况下查找成功的平均长度。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
