数据结构考研分类复习真题 第五章 数组和广义表[28]

指出下列算法中错误低效之处并将其改成一个正确且高效的算法

PROCEDURE delk(A m lasti k) ;

｛从数组A[１last]中删除第i个元素起的 k个元素m为A上限｝

BEGIN

IF(i<) OR (i>last) OR(k<) OR(last>m)

THEN write (error)

ELSE FOR count: = TO k TO

[FOR j:=last DOWNTO i+ DO

A[j]:=A[j];

last:=last]

ENDP;{delk} 【北方交通大学 一 （分）】

设输入为整数数组A[n]其中<=A[i]<=k(<=i<=n)输出数组为b[n]c[k]是临时工作空间阅读下述算法后回答下列问题

PROC Demo(ABk){

()FOR i:= TO k DO C[i]:=;

()FOR j:= TO n DO C[A[j]]:= C[A[j]]+;

()FOR i:= TO k DO C[i]:= C[i]+ C[i]

()FOR j:=n DOWNTO DO {

() B[C[A[j]]]:=A[j];

()C[A[j]]:=C[A[j]] } }

(a)当标号（）行的循环执行完后C[i](<=i<=n)的值有何意义？

(b)当标号（）行的循环执行完后C[i](<=i<=n)的值有何意义？

(c)算法执行后B的内容有何特点？

(d)当k=O(n)时算法的时间复杂度是多少？ 【中科院软件所 二（分）】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []