算法设计试卷模式A答案.doc

南阳理工学院2010－2011学年第一学期试卷参考答案 课程： 算法设计与分析 （A） 评卷人（签名）： 复核人（签名）： 题号 一 二 三 四 五 总分 得分 一、选择题（每小题1分，共10分） 1．算法分析是（ C ）。 A． 将算法用某种程序设计语言恰当地表示出来 B． 在抽象数据集合上执行程序，以确定是否会产生错误的结果 C． 对算法需要多少计算时间和存储空间作定量分析 D． 证明算法对所有可能的合法输入都能算出正确的答案 2. 下列( A )不是描述算法的工具。 A．数据流图 B．伪代码 C．自然语言 D．程序语言 3. 如果某一算法的执行时间不超过输入规模的两倍，那么算法渐进时间复杂度为（B）。 A． O(n2) B． O(n) C． D． 4．下列程序段的S执行的次数为( D )。 for(int i=0;in;i++） for(int j=0;ji;j++) S;//S是基本操作，耗时常数时间 A．n2 B． n2／2 C．n(n+1) /2 D．n(n-1)/2 5．使用F(n)＝n*F(n)递归求F(4)，其中边界条件为F(0)=1，则递归调用子函数的次数为( B )。 A． 3次 B．4次 C．5次 D．8次 6．Fibonacci数列的第1项为0，第2项为1，那么它的第10项为( D )。 A． 3 B． 13 C． 21 D．34 7．下列排序算法不是基于交换的是( C )。 A冒泡排序 B． 快速排序 C 合并排序 D． 堆排序 8．4个结点的二叉查找树可能的形态有( C )种。 A 4种 B． 5种 C．14种 D． 15种 9．如果背包的容量为100，而物品共有10个，则使用动态规划来解0-1背包问题数组大小为( C ) A． 10 B． 100 C. 1000 D 10000 10．对线性表执行折半有哪些信誉好的足球投注网站时，要求线性表必须( C)。 A 以数组方式存储 B以单链表形式存储 C 以数组方式存储且关键字有序 D． 以单链表形式存储且关健字有序 二、填空题（每空2分，共30分） 1. 请将合并排序的分治算法补充完整。 数组a存放待排序元素，left:为待排序元素最小下标，right:为待排元素最大下标。 void MergeSort(Type a[],int left,int right){?? Type *b=new int[right-left+1];?? if(leftright)?? {? ? ? int i= (left+right}/2 ;? ? ? MergeSort(a,left,i);? ? ? MergeSort(a,i+1,right);? ? ? Merge(a,b,left,i,right);? ? ? Copy(a,b,left,right);?? }?} templateclass Typevoid Merge(Type a[],Type b[],int left,int mid,int right){?int i=1eft,j=mid+1,k=left;? ? while((i=mid)(j=right)) ?{? if(a[i]=a[j]) b[k++]=a[i++];? else b[k++]=a[j++];?}?if(imid) for(int q=j;q=right;q++)? b[k++]=a[q]; ?else for(int q=i;q=mid;q++) ? b[k++]=a[q];} template class Typevoid Copy(Type a[],Type b[],int left,int right){?? for(int i=left;i=right;i++)?? {?? ? ? a[i]=b[i];?? }} 2.动态规划的基本要素包括重叠子问题、自底向上的解决方法、 最优子结构性质。 3.矩阵连乘问题算法借助于 二维数组 存放各子问题的最优值。 4.给定序列X={ S R E A B E D B W D }, Y={R B A E F E A}的最长公共子序列的长度为 3 。 5.活动安排问题的贪心策略是 选择结束时间