全国自考数据结构导论（串、外部排序）模拟试卷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”)。

19． 在选择树中，“败者”是指______。

20． 归并排序有两个基本阶段，第一阶段是______，第二阶段是______。

21． 简述下列每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字与串变量的值。

17． 串s1=‘abcdefg’，s2=‘hijkl’，则concat(substr(s1，2，strlen(s2))，substr(s1，strlen(s2)，2))=_________。

18． 寻找子串在主串中的位置，称为________。其中，主串又称为_______，子串又称为_______。

15． 空串是_________，其长度等于_______；空格串是________，其长度是______。

16． 若两个串的长度相等且对应位置上的字符也相等，则称两个串________。

12． 磁盘文件采用选择法实现k路归并时，占用CPU的时间与k_______。

14． 一个串的任意连续字符组成的子序列称为串的________，该串称为________。

13． 磁盘文件有m个初始归并段，采用k路归并时，所需的归并遍数是_______。

10． 串s1=‘ABCDEFG’，s2=‘PQRST’，函数concat(x，y)返回x和y串的连接串，substr(s，i，j)返回串s的从序号i的字符开始的j个字符组成的子串，strlen(s)返回串s的长度，则concat(slabstr(s1，2，strlen(s2))，substr(s1，strlen(s2)，2))=_________

11． 外排序是指_______。

9． 空串与空格串是相同的，这种说法_________。

7． 设s1=“Hello”，s2=“student”，函数StrDel(s2，strlen,(S1)，3)的值是________

8． 若字符串”abcdefg”采用链式存储，假设每个字符占用1个字节，每个指针占用2个字节，则改字符串的存储密度为__________。

6． 已知两个串s==“abcczym”和T=“abccyzm”，则StrEqual串判等操作的结果是________。

5． 设有两个串S和T，求T在s中首次出现的位置的运算是________运算。

4． 串是一种特殊的线性表，其特殊性体现在_______。

2． 串的长度是指_________。

3． 若串中字符经常发生变化，则采用_______存储方式最合适。

1． 以下有关串的描述中，_________是不正确的。