2012 年 408 真题2012 年 408 数据结构 · 第 1 题选中文字高亮 · 下划线求整数 n(n≥0) 阶乘的算法如下,其时间复杂度是( )。 int fact(int n) { if (n <= 1) return 1; return n * fact(n - 1); } AO(log2n))BO(n)CO(nlog2n))DO(n2)←上一题设包含 4 个数据元素的集合 S = { “do”, “for”, “repeat”, “while” },各元素的查找概率依次为: p1=0.35 , p2=0.15 , p3=0.15 , p4=0.35 。将 S 保存在一个长度为 4 的顺序表中,采用折半查找法,查找成功时的平均查找长度为 2.2 。请回答: (1) 若采用顺序存储结构保存 S ,且要求平均查找长度更短,则元素应如何排列?应使用何种查找方法?查找成功时的平均查找长度是多少? (2) 若采用链式存储结构保存 S ,且要求平均查找长度更短,则元素应如何排列?应使用何种查找方法?查找成功时的平均查找长度是多少?下一题已知操作符包括 +、−、∗、/、( 和 )。将中缀表达式 a+b−a∗((c+d)/e−f)+g 转换为等价的后缀表达式 ab+acd+e/f−∗−g+ 时,用栈来存放暂时还不能确定运算次序的操作符,若栈初始为空,则转换过程中同时保存在栈中的操作符的最大个数是( )。→