《计算机算法设计与分析》习题及答案

{int q=Partition(a,p,r);

QuickSort (a,p,q-1); 回溯法解迷宫问题 迷宫用二维数组存储，用'H'表示墙,'O'表示通道

int x1,y1,success=0; 给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，返回其在数组中的位置，如果未找到返回-1。 写出二分搜索的算法，并分析其时间复杂度。

template

int BinarySearch(Type a[], const Type& x, int n) {利用分治算法写出合并排序的算法，并分析其时间复杂度 void MergeSort(Type a[], int left, int right) {

if (left

void Clique::Backtrack(int i) 顺序表存储表示如下： typedef struct

{RedType r[MAXSIZE+1]; high]的记录,枢轴记录到位,并返回其所在位置, int pivotkey;

[0]=[low]; ey; ey>=pivotkey) --high; [low]=[high]; ey<=pivotkey) ++low; [high]=[low]; high]作快速排序 int pivotloc;

if (low

QSort(L,low,pivotloc-1); //对低子表递归排序,pivotloc是枢轴

位置

QSort(L,pivotloc+1,high); //对高子表递归排序 } }

void QuickSort(SqList &L) {//对顺序表L作快速排序 QSort(L,1,; }