对序列（50，72，28，39，81，15）中的元素按值从小到大

对具有n个元素的有序序列进行二分查找时，(61)。

A．元素位置越靠近序列前端，查找该元素所需的比较次数越少

B．查找序列中任何一个元素所需要的比较次数不超过[log2(n+1)]

C．查找元素所需的比较次数与元素的位置无关

D．元素位置越靠近序列后端，查找该元素所需的比较次数越少

对一棵二叉排序树进行()遍历，可以得到该二叉树的多有结点按值从小到大排列的序列。

A、前序

B、中序

C、后序

D、按层次

此题为判断题(对，错)。

阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 下面的程序利用快速排序中划分的思想在整数序列中找出第k小的元素（即将元素从小到大排序后，取第k个元素）。 对一个整数序列进行快速排序的方法是：在待排序的整数序列中取第一个数作为基准值，然后根据基准值进行划分，从而将待排序的序列划分为不大于基准值者（称为左子序列）和大于基准值者（称为右子序列），然后再对左子序列和右子序列分别进行快速排序，最终得到非递减的有序序列。 例如，整数序列“19, 12, 30, 11,7,53, 78, 25"的第3小元素为12。整数序列“19,12,7,30,11,11,7,53,78,25,7"的第3小元素为7。 函数partition（int a[ ], int low,int high）以a[low]的值为基准，对a[low]、a[low+1]、…、 a[high]进行划分，最后将该基准值放入a[i] (low≤i≤high)，并使得a[low]、a[low+1]、，．．、 A[i-1]都小于或等于a[i]，而a[i+1]、a[i+2]、．．、a[high]都大于a[i]。 函教findkthElem(int a[],int startIdx,int endIdx,inr k)在a[startIdx]、a[startIdx+1]、...、a[endIdx]中找出第k小的元素。

【代码】 include <stdio.h> include <stdlib.h> Int partition（int a [ ]，int low, int high） {//对 a[low..high]进行划分，使得a[low..i]中的元素都不大于a[i+1..high]中的元素。 int pivot=a[low]； //pivot表示基准元素 Int i=low,j=high; while(（ 1） ){ While(i<j&&a[j]>pivot)--j; a[i]=a[j] While(i<j&&a[i]<=pivot)++i; a[j]=a[i] } （2） ； //基准元素定位 return i； } Int findkthElem（int a[ ]，int startIdx，int endIdx, int k） {//整数序列存储在a[startldx..endldx]中，查找并返回第k小的元素。 if (startldx<0 ||endIdx<0 || startIdx>endIdx || k<1 ||k-1>endIdx ||k-1<startIdx) Return-1; //参数错误 if(startIdx<endldx){ int loc=partition(a, startIdx, endldx)； ∥进行划分，确定基准元素的位置 if (loc==k-1) ∥找到第k小的元素 return （3） ； if(k-1 <loc) //继续在基准元素之前查找 return findkthElem(a, （4） ,k）； else ／／继续在基准元素之后查找 return findkthElem(a， （5） ，k); } return a[startIdx]； } int main() { int i, k; int n; int a[] = {19, 12, 7, 30, 11, 11, 7, 53, 78, 25, 7}; n= sizeof(a)／sizeof(int) //计算序列中的元素个数 for (k=1;k＜n+1；k++){ for(i=0;i＜n;i++){ printf(“%d/t”,a[i]); } printf(“\n”); printf(“elem %d=%d\n,k,findkthElem(a,0,n-1,k));//输出序列中第k小的元素 } return 0； }

若在线性表中采用折半查找法查找元素，该线性表应该()

A.元素按值有序

B.构采用顺序存储结

C.元素按值有序且采用顺序存储结构

D.元素按值有序且采用链式存储结构

阅读以下说明和流程图，填补流程图中的空缺(1)～(9)，将解答填入对应栏内。

【说明】

假设数组A中的各元素A(1)，A(2)，…，A(M)已经按从小到大排序(M≥1)；数组B中的各元素B(1)，B(2)，…，B(N)也已经按从小到大排序(N≥1)。执行下面的流程图后，可以将数组A与数组B中所有的元素全都存入数组C中，且按从小到大排序 (注意：序列中相同的数全部保留并不计排列顺序)。例如，设数组A中有元素：2，5， 6，7，9；数组B中有元素2，3，4，7：则数组C中将有元素：2，2，3，4，5，6，7， 7， 9。

【流程图】

A.值为n的元素

B.值为1的元素

C.值为n-k的元素

D.不确定的

试题一（共 15 分）

阅读以下说明和流程图，填补流程图中的空缺（1）～（9） ，将解答填入答题纸的对应栏内。

[说明]

假设数组 A 中的各元素 A(1)，A(2) ，…，A(M)已经按从小到大排序（M≥1） ；数组 B 中的各元素 B(1)，B(2)，…，B(N)也已经按从小到大排序（N≥1） 。执行下面的流程图后， 可以将数组 A 与数组 B 中所有的元素全都存入数组 C 中， 且按从小到大排序 （注意：序列中相同的数全部保留并不计排列顺序） 。例如，设数组 A 中有元素：2，5，6，7，9；数组B 中有元素：2，3，4，7；则数组 C 中将有元素：2，2，3，4，5，6，7，7，9。

[流程图]