全国自考数据结构导论（串、外部排序）模拟试卷1

29． 归并排序中使用的选择树和堆排序中的堆有什么差别?

30． 以10个长度为L的归并段为例，用2路平衡归并法进行排序，写出归并过程中各磁带内容的变化情况。

31． 以55个长度为L的归并段为例，用2路多阶段归并法进行排序，写出归并过程中各磁带内容的变化情况。

28． 以定长顺序存储结构表示串，设计算法，将s复制给t，当遇到空格序列时，只复制 一个空格，已知s昀最后一个字符不是空格。

27． 已知一个字符串，内有数字和非数字字符，例如akl23x456? 302ge1463，将其中连续的数字作为一个整体，依次存放到一维数组a中，例如a[0]=123，a[11=456，…，设计算法实现上述要求。

26． 函数void Insert(char*s，char*t，int pos)将字符串t插入到字符串s中，插入位置为pos。请用C语言实现该函数。假设分配给字符串s的空间足够让字符串t插入(说明：不得使用任何库函数)。

24． 分别在顺序串上和链串上实现判等运算StrEqual(S，T)

25． 若x和Y是两个单链表存储的串，编写一个函数找出x中第一个不在y中出现的字符。

23． 已知s=“(xyz)*”，T=“(x+z)*Y”。试利用连接、求子串和置换等基本运算，将S转换为T。

22． 设有A=“#”，B===“mule”，C=“old”，D=“my”，试计算下列运算的结果(注：A+B是CONCAT(A，B)的简写)。

(1)A+B；

(2)B+A；

(3)D+C+B；

(4)SubStr(B，3，2)；

(5)SubStr(C，1，0)；

(6)StrLen(A)；

(7)StrLen(D)；

(8)Index(B，D)；

(9)Index(C，“d”)；

(10)Insert(D，2，C)；

(11)Insert(B，1，A)；

(12)StrDel(B，2，2)；

(13)StrDel(B，2，O)；

(14)StrReplace(C，2，2，“k”)。