算法设计题 B .doc

-上-装-订-线-咸阳师范学院2006 2007 学年度第 1 学期 算法分析与设计 课程试题（B卷）课程代码 100173 任课教师 赵娟 适用专业 计算机科学与技术 层次 本科 年级 2003级 班级 学号 姓名 考试日期 试场 -下-装-订-线-咸阳师范学院试题（B卷）首页题 号一二三四五六七八总计得 分评 卷 人注意： （1）本试卷不允许另附其它答题纸。（2）请在指定位置做答，否则不得分。-一 选择题（将答案填在下面表格中的空白处，每题2分，共40分，阴影处学生不得填写答案。）总分题号12345678910答案得分题号11121314151617181920答案得分1 选出不是算法所必须具备的特征（ ）。A 有穷性 B 确切性 C 高效性 D 可行性2 下列（ ）不是描述算法的工具。A 数据流图 B 伪代码 C 自然语言 D 程序语言3 下列（ ）不是衡量算法的标准。A 时间效率 B 空间效率 C 问题的难度 D 适应能力4 从排序过程是否完全在内存中进行，排序问题可以分为（ ）。A 稳定排序与不稳定排序 B 内排序与外排序C 直接排序与间接排序 D 主排序与辅助排序5 在数据结构中，从逻辑上可以把数据结构分成（ ）。A 动态结构和静态结构 B 紧凑结构和非紧凑结构C 线性结构和非线性结构 D 内部结构和外部结构 6 N个结点的完全图的边条数为（ ）。A n(n-1)/2 B n! C n(n-1) D 2n7 下列不便于进行查入删除操作的数据结构为（ ）。 A 静态链表 B 单链表 C 顺序表 D 双向链表8 如果某一算法的执行时间不超过输入规模的两倍，那么算法渐进时间复杂度为（ ）。A (2n) B (n) C (n) D (n)9 空树的高度为（ ）。A 0 B 1 C 1 D 无定义10 下列函数关系随着输入量增大增加最快的是（ ）。A log2N B N3 C 2N D N!11 如果待排序的序列基本有序，下列算法效率最高的是（ ）。A 插入排序 B 选择排序 C 快速排序 D 归并排序12 在排序算法中，从待排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ ）。A 希尔排序 B 冒泡排序 C 插入排序 D 选择排序13 下列情况不适合使用快速排序的是（ ）。A 要排序的数据表数量很大 B 要排序的数据表中有相同的关键字C 要排序的数据表基本有序 D 要排序的数据表对象个数为奇数14 执行顺序搜索，成功搜索时执行比较的次数为（ ）。A n B n/2 C (n+1)/2 D (n-1)/215 对线性表执行折半搜索，要求线性表必须（ ）A 以数组方式存储 B 以链表形式存储C 以数组方式存储且关键字有序 D 以链表形式存储且关键字有序16 如果需要设计一个算法判别左右括号是否配对出现，采用（ ）数据结构最好。A 数组 B 链表 C 栈 D 队列17 对有序表 3 , 14 , 27 , 30 , 38, 41, 56 , 70, 74, 81, 85, 93执行Fibonacci搜索算法，搜索关键字为70的结点时，经过第（ ）次后搜索成功。A 1 B 2 C 4 D 5 第 1 页（共 4 页）-上-装-订-线-咸阳师范学院2006 2007 学年度第 1 学期 算法分析与设计 课程试题（B卷）课程代码 100173 任课教师 赵娟 适用专业 计算机科学与技术 层次 本科 年级 2003级 班级 学号 姓名 考试日期 试场 -下-装-订-线-18 Johnson-Trotter算法的渐进时间复杂度为（ ）。A O(1) B O(n) C O(2n) D O(n!)19 下列字符串序列不符合字典排序的是（ ）。A abc acb bca B abc acb cbaC bac bca abc D bca bac bca20 如果背包的容量为100，而物体共有10件，则使用动态规划求解背包问题数组大小为（ ）。A 10 B 100 C 1000 D 10000得分二 简答题（每题5分，共25分）1 衡量一个排序算法效率需要考虑哪些因素？2 写出2, 14, 27, 30, 40, 41, 56, 70, 74, 81, 88, 93, 98搜索表上执行折半搜索时的搜索树。3 试简要描述字符匹配算法BM算法执行过程（使用流程图）。4对于集合A= a, b, c,写出A的幂集。5 已知二叉树的前序序列和中序序列，构造出该二叉树。先序序列：ABCDEFG中序序列： CDBAFEG 第 2 页（共 4 页）-上-装-订-线-咸阳师范学院2006 2007 学年度第 1 学期 算法分析与设计 课程试题（B卷）课程代码 100173 任课教师 赵娟 适用专业 计算机科学与技术 层次 本科 年级 2003级 班级 学号 姓名 考试日期 试场 -下-装-订-线-得分三 计算题（每题5分，共20分。要求写出解题过程） 1 使用Horner法则求解多项式p(x)=x4 +x3+2x2+3x+5 在2处的值。 2 给出递推公式x(n)=x(n-1)+2n，对于任意的n0；x(0)=0对应的通项公式的计算过程。3 计算下列程序段中的基本操作S被执行的的次数For i:=0 to n do For j:=i to n do S /S为某种基本操作4 假设散列函数为Hash(key) = mod(key,13)，如果散列表中已有的四项为：Hash(14)、Hash(15)、Hash(16)、Hash(18),假设散列地址空间为13；如果使用的是线性探查法处理冲突，则计算关键字为28的结点的散列地址。第 3 页（共 4 页）-上-装-订-线-咸阳师范学院2006 2007 学年度第 1 学期 算法分析与设计 课程试题（B卷）课程代码 100173 任课教师 赵娟 适用专业 计算机科学与技术 层次 本科 年级 2003级 班级 学号 姓名 考试日期 试场 -下-装-订-线-得分 四 编写算法题（第1题5分，第2题10分，共15分）1 编写两条直线L1和L2相交的判定算法。2 编写输出图的某一层结点的算法 第 4 页（共 4 页）咸阳师范学院 2006 200 7 学年度第 一 学期 专业（本） 2003 级 算法分析与设计（B） 课程试题参考答案及评分标准一 选择题（每道题2分，总计40分）1 C 2 C 3 C 4 B 5 C 6 C 7 A 8 BA9 B 10 C 11 D 12 C 13 C 14 B 15 C 16 C 17 A 18 B 19 DA20 C 二 简答题（每道题5分，总计25分）1 要考虑 a 排序过程所需要的算法步数 2分 b 当执行一次键的比较需要较长时间，则要考虑排序过程中所执行的键的比较次数 2分 c 当排序时需要移动记录，且记录都很大时，还需要考虑记录的移动次数。 1分2 （5分） 索引 0 1 2 3 4 5 6 7 8 9 10 11 12214 2730404156707481889398 56278121440304170749388898 ABCDEFG三 计算题（每题5分，总计20分）1 p(x)=x3(x+1)+2x2+3x+5 1分=x2(x(x+1)+2)+3x+5 1分=x(x(x(x+1)+2)+3)+5 1分把x=2代入上式，得 p(x)=43 2分2 x(n)=x(n-1)+2n =x(n-2)+2(n-1)+2n 1分 =x(n-3)+2(n-2)+2(n-1)+2n 1分 = =x(0)+2+4+2n 1分 =2=(n+1)n 2分3 12345.+n 3分=(n+1)n/2 2分4 根据求模运算得知，14的散列地址为1，15的散列地址为2，16的散列地址为3，18的散列地址为5，1分同样28的散列地址就应该为2，但是地址为2的空间已经被占用了， 2分根据线性探查法处理冲突，可知，28的散列地址为6。 2分 i+; j=k; 1分 If(Q-front= = Q-rear) printf(“ not N level/n”); 1分 If(i=N) While (Q-front! = Q-rear) 2分 p =Q-front-next; Q-front-next=p-next; Printf(“%d”&p-data); 3流程图： YYN开 始构造失配移位表 构造匹配移位表模式串与文本串左对齐发生失配 模式串右移d位结 束模式串右端开始比较匹配成功到达文本末端N1分1分1分1分1分 4 A的幂集为, a, b , c, a, b, b, c, c, a, a, b, c5分 5四 编写算法题 1 ALGORITHM LineInteraction(L1, L2)判断两条直线是否相交的算法输入：直线L1（P1，P2），直线L2（P3，P4）输出：如果两条直线是相交的，那么返回True，否则返回Falsed x=L2.p4.x L2.p3.x ; d y=L2.p4.y L2.p3.y ; 1分m = dy/dx; 1分F1=L1.p1.y-m*(L1.p1.x L2.p3.x)-L2.p3.y; 1分F2=L1.p2.y-m*(L1.p2.x L2.p3.x)-L2.p3.y; 1分If F1 * F2 data=v0; p-next=null; p-firstarc=visitedv0-firstarc; /处理将要入队列的结点 Q-rear-next=p; /v0入队列 1分 j=j+1; /j在这表示队列中的元素个数 while ( Q-front! = Q-rear) ! (i !=N) 1分 while( j!=0) 1分 p =Q-front-next; Q-front-next=p-next; /队头元素p出队 j-; q=p-firstarc; visitedq-data=true; k=0; k表示的是下一层入队列