1、计算机专业基础综合数据结构（排序）历年真题试卷汇编 8 及答案与解析一、单项选择题0 设要将序列(q，h，c ， y，p，a ，m，s，r，d，f ，x，)中的关键码按字母升序重新排序，从下面供选择的答案中选出正确答案填入括号内。Af， h，c，d,p，m，q， r，s ，y，xBp， a，c ，s，q，d，x ，rh，m，yCa，d，c ，r，f，q，m，s，y，p，h，x Dh，c，q， p，a ，m， s，r ，d，x，yEh，q，c ，y，a ，p，m ，s，d，r,f，x【厦门大学 2000 六、3(163 分)】1 ( )是初始步长为 4 的 Shell 排序一趟扫描的结果；2 (
2、 )是对排序初始建堆的结果；3 ( )是以第一个元素为分界元素的快速一趟扫描的结果。4 n 个英文单词，每个单词长度基本相等，为 m。当 n50、mAk)k=j； 选第 i 个最大元素if(k!=i)AiAk； 选出第 i 个最大元素k=ni； k 记最小元素下标for(j=ni ; jAk； 选出第 i 个最小元素高层 for23 【正确答案】 选择排序一趟找出一个关键字最小的结点，其数据和当前结点进行交换；若要交换指针，则须记下当前结点和最小结点的前驱指针。核心语句段如下：p=head-next；while(p)(q=p-next； r=p； 设 r 是指向关键字最小的结点的指针while
3、(q!=null)(if(q 一datadata)r=q；q=q 一next；if(r!=p)r 一datap 一data；p=p 一next；24 【正确答案】 上题是按“交换结点值” 进行选择排序，本题要求交换结点。因此必须知道“值最小的元素 ”和“未排好的那些元素的第一个元素”前驱的指针。设“ 值最小的元素” 的前驱的指针是 start，待排序的第一个元素的指针是 P，其前驱的指针是 pre。则结点交换的核心语句段是： pre 一link=start 一link；start 一link 一link=p 一link；pre=pre 一link；前驱后移 P 一link=start 一lin
4、k 一link；start 一link=p ；25 【正确答案】 (2)核心语句段如下： for(i=0 ； i n； i+) 对每一个元素 for(j=0，cnt=0 ； jn； j+) if(aj keyai key)cnt+; 比当前元素的关键字小的元素个数 bcnt=ai; (3)对于有 n 个记录的表，关键码比较， 12 次。 (4)简单选择排序算法比本算法好。简单选择排序比较次数是 n(n 一 1)2，且只用一个交换记录的空间；而这种方法比较次数是 n2，且需要另一数组空间。因题目要求“针对表中的每个记录，扫描待排序的表一趟” ，所以比较次数是 n2 次。若限制“对任意两个记录之间
5、应该只进行一次比较”，则可把以上算法中的比较语句改为： for(i=0; in； i+)aicount=0 ； 各元素再增加一个计数域，初始化为 0 for(i=0；in ；i+) for(j=i+1 ；jn；j+) if(ai keyaj key)ajcount+； else aicount+；26 【正确答案】 值为 i(1in)的元素就是数组下标为 n 一 i 的元素。核心语句是：for(i=0； i=x) j 一一；Ri=Rj； 将比枢轴小的元素移到低端 (不交换)while(ij &Ri key=x) i+；Rj=Ri； 将比枢轴大的元素移到高端 (不交换) whileRi=R0； 枢轴元素到位return i； 返回枢轴位置 partitionvoid QuickSort(RecType R，int s ，int t) 对元素序列 Rst进行快速排序 if(st)k=partiti。 n(R，s ，t) ； 一趟划分QuickSort(R，s，ki)； 对枢轴左边部分快速排序QuickSort(R，k+1，t)； 对枢轴右边部分快速排序 if QuickSort29 【正确答案】 首先求出平均值作“虚” 枢轴，去进行划分。 “虚”枢轴的含义是可能没有该元素。30 【正确答案】 第一个元素为枢轴，但比较时小于零的数前移，大于等于零的数后移。
