数据结构复习15201210数据结构考研复习5201210章节幻灯片.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 3 算法设计 3 算法设计 3 算法设计 3 算法设计 3 算法设计 3 算法设计 3 算法设计 3 算法设计 数据结构考研复习5 * * * * * * * * * * * * * * * * * * * * * * * 1 单选题 1 单选题 1 单选题 1 单选题 1 单选题 19、已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多是 A. 4? ? B. 5?? C. 6??? D. 7 1 单选题 1 单选题 1 单选题 21、对一组数据（2，12，16，88，5，10）进行排序，若前三趟排序结果如下 第一趟：2，12，16，5，10，88 第二趟：2，12，5，10，16，88 第三趟：2，5，10，12，16，88 则采用的排序方法可能是： A. 起泡排序? B. 希尔排序? C. 归并排序? D. 基数排序 1 单选题 20、采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是 A. 递归次数与初始数据的排列次序无关 B. 每次划分后，先处理较长的分区可以减少递归次数 C. 每次划分后，先处理较短的分区可以减少递归次数 D. 递归次数与每次划分后得到的分区处理顺序无关 1 单选题 1 单选题 1 单选题 1 单选题 1 单选题 11、对一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是 A．排序的总趟数 B. 元素的移动次数 C. 使用辅助空间的数量 D. 元素之间的比较次数 1 单选题 2 算法应用 2 算法应用 2 算法应用 2 算法应用 2 算法应用 41.（10分）将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中，散列表的存储空间是一个下标从0开始的一个一维数组，散列函数为：H（key）=（key×3）MOD 7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。 （1）请画出所构造的散列表。 （2）分别计算等概率情况下，查找成功和查找不成功的平均查找长度。 2 算法应用 解答： （1）由装载因子0.7，数据总数7个，存储空间长度为10。所以，构造的散列表为： 下标 0 1 2 3 4 5 6 7 8 9 关键字 7 14 8 11 30 18 9 探测次数 1 2 1 1 1 3 3 2 算法应用 （2）查找成功的平均查找长度ASL=(1+1+1+1+2+3+3)/7=12/7 查找不成功的平均查找长度 ASL=(3+2+1+2+1+5+4)/7=18/7 下标 0 1 2 3 4 5 6 探测次数 3 2 1 2 1 5 4 2 算法应用 2 算法应用 3 算法设计 3 算法设计 3 算法设计 42.（13分）设将n(n1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移P（0﹤P﹤n）个位置，即将R中的数据由（X0 ,X1 ,……Xn-1）变换为（Xp, Xp+1 , ……Xn-1 , X0 , X1 , ……Xp-1）要求： （1）给出算法的基本设计思想。 （2）根据设计思想，采用C或C++或JAVA语言表述算法，关键之处给出注释。 （3）说明你所设计算法的时间复杂度和空间复杂度。 3 算法设计 解答： （1）算法思想：三次置逆。 1次 （X0 ,X1 ,……Xn-1）变换为 （Xn-1 ,Xn-2 ,……X0） 2次 （Xn-1, Xn-2 , ……Xp ）变换为 （Xp ,Xp+1 ,……Xn-1） 3次 （Xp-1, Xp-2 , ……X0 ）变换为 （X0 ,X1 ,……Xp-1） 最终结果 （Xp ,Xp+1 ,……Xn-1 , X0 ,X1 ,……Xp-1） 3 算法设计 （2）算法实现：置逆函数、调用函数。 void invert1( int r[], int s, int t ) {// 本算法将数组r中下标自s到t的元素逆置 for ( k=s; k=(s+t)/2; k++ ){ w = r[k];　　　r[k] = r[t-k+s];　　　r[t-k+s] = w;　　} // for} // invert1 3 算法设计 void invert2( int r[], int s, int