二级MS Office高级应用

1

1. 在长度为n的有序线性表中进行二分查找，最坏的情况下需要比较的次数是：O（log2n）(以2为底n对数)

解析：当有序线性表为顺序存储时才可以用二分查找，可以证明的是对于长度为n的有序线性表，最坏的情况下，二分查找只需要比较O（log2n）次，而顺序查找需要比较n次。

补充：二分折半查找
二分折半查找需要要求待查找表中的元素必须是有序的。基本思想：将n个元素分层大至相等的两部分。取中间元素a[n/2]和待查找元素x比较，如果：（这里假设表中的元素从小到大排序）

• x = a[n/2]:则找到了目标元素，算法终止
• x < a[n/2]:则表示需要从表中的左半部分继续查找
• x > a[a/2]:ze表示需要从表中的右半部分继续查找
• 同理遍历下次，直到找到目标元素，或者超出查找的范围则终止算法

代码

class Search{
    int binarySearch(Integer[] srcArray,int des){
        int low = 0;
        int high = srcArray.length - 1;
        int number = 1;
        while(low<=high&&(low<=srcArray.length -1)&&(high<=srcArray.length -1)){
            System.out.println("循环的次数"+number++);
            int middle = (low+high)/2;
            int test = srcArray[middle];
            if(test == des){
                System.out.println("找到了目标元素，所在的数组的下标是："+middle);
                return test;
            }else if(des > test){
                low = middle +1;
            }else{
                high = middle -1;
            }
        }
        return -1;
    }
}
public class binarySearch {
    public static void main(String[] args){
        Integer[] srcArray = {4,5,6,8,9,10};
        Search search = new Search();
        int result = search.binarySearch(srcArray, 7);
        if(result == -1){
            System.out.println("找不到元素");
        }

    }
}

1. 数据流图中带有箭头的线段表示的是（数据流）
2. 在软件开发中，需求阶段可以使用的工具有（数据流图DFD，数据字典DD，判定树和判定表）