1、全国自考数据结构导论（串、外部排序）模拟试卷 1 及答案与解析一、单项选择题1 以下有关串的描述中，_是不正确的。（A）串是字符的有限序列（B）子串是串中任意连续字符组成的子序列（C）串可以采用顺序存储或链式存储（D）空串是由一个或多个空格组成的串2 串的长度是指_。（A）串中包含的字符个数（B）串中包含的不同字符个数（C）串中除空格以外的字符个数（D）串中包含的不同字母个数3 若串中字符经常发生变化，则采用_存储方式最合适。（A）定长顺序（B）堆（C）链式（D）散列4 串是一种特殊的线性表，其特殊性体现在_。（A）可顺序存储（B）数据元素是一个字符（C）可链接存储（D）数据元素可以是多个字符
2、。5 设有两个串 S 和 T，求 T 在 s 中首次出现的位置的运算是_运算。（A）求子串（B）串插入（C）串连接（D）模式匹配6 已知两个串 s=“abcczym”和 T=“abccyzm”，则 StrEqual 串判等操作的结果是_。（A）一 1（B） 0（C） 1（D）647 设 s1=“Hello”，s2=“student”，函数 StrDel(s2，strlen,(S1)，3)的值是_（A）空串（B） lo（C） stud（D）ent8 若字符串”abcdefg”采用链式存储，假设每个字符占用 1 个字节，每个指针占用2 个字节，则改字符串的存储密度为_。（A）20（B） 30（C）
3、 333（D）409 空串与空格串是相同的，这种说法_。（A）正确（B）不正确（C）可以说正确的（D）可以说不正确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)=_（A）BCDEF（B） BCDEFG（C） BCPQRST（D）BCDEFEF11 外排序是指_。（A）在外存上进行的排序方法（B）不需
4、要使用内存的排序方法（C）数据里很大，需要人工干预的排序方法（D）排序前后数据在外存，排序时数据调入内存的排序方法12 磁盘文件采用选择法实现 k 路归并时，占用 CPU 的时间与 k_。（A）有关（B）无关（C）可能有关（D）关系不大13 磁盘文件有 m 个初始归并段，采用 k 路归并时，所需的归并遍数是 _。（A）log 2k（B） log2m（C） logkm（D）log km二、填空题14 一个串的任意连续字符组成的子序列称为串的_，该串称为_。15 空串是_，其长度等于_；空格串是_，其长度是_。16 若两个串的长度相等且对应位置上的字符也相等，则称两个串_。17 串 s1=abcd
5、efg，s2=hijkl，则 concat(substr(s1，2，strlen(s2) ，substr(s1，strlen(s2)，2)=_。18 寻找子串在主串中的位置，称为_。其中，主串又称为_，子串又称为_。19 在选择树中，“ 败者” 是指 _。20 归并排序有两个基本阶段，第一阶段是_，第二阶段是_。三、应用题21 简述下列每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字与串变量的值。22 设有 A=“#”，B=“mule”，C=“old”，D=“my” ，试计算下列运算的结果(注：A+B 是 CONCAT(A，B)的简写)。(1)A+B；(2)B+A；(3)
6、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”)。23 已知 s=“(xyz)*”，T=“(x+z)*Y”。试利用连接、求子串和置换等基本运算，将 S转换为 T。24 分别在顺序串上和链串上实现判等运算 StrEqual(S，T)25 若 x 和 Y 是
7、两个单链表存储的串，编写一个函数找出 x 中第一个不在 y 中出现的字符。26 函数 void Insert(char*s，char*t ，int pos)将字符串 t 插入到字符串 s 中，插入位置为 pos。请用 C 语言实现该函数。假设分配给字符串 s 的空间足够让字符串 t 插入(说明：不得使用任何库函数)。27 已知一个字符串，内有数字和非数字字符，例如 akl23x456? 302ge1463，将其中连续的数字作为一个整体，依次存放到一维数组 a 中，例如 a0=123， a11=456，设计算法实现上述要求。28 以定长顺序存储结构表示串，设计算法，将 s 复制给 t，当遇到空格
8、序列时，只复制 一个空格，已知 s 昀最后一个字符不是空格。29 归并排序中使用的选择树和堆排序中的堆有什么差别?30 以 10 个长度为 L 的归并段为例，用 2 路平衡归并法进行排序，写出归并过程中各磁带内容的变化情况。31 以 55 个长度为 L 的归并段为例，用 2 路多阶段归并法进行排序，写出归并过程中各磁带内容的变化情况。全国自考数据结构导论（串、外部排序）模拟试卷 1 答案与解析一、单项选择题1 【正确答案】 D【知识模块】 串2 【正确答案】 A【知识模块】 串3 【正确答案】 C【知识模块】 串4 【正确答案】 B【试题解析】 串是以字符为数据元素，以线性结构为逻辑结构的数据
9、，因此把串看成是一种特殊的线性表，其特殊性就体现在所有的数据元素仅含有单个字符。【知识模块】 串5 【正确答案】 D【知识模块】 串6 【正确答案】 B【知识模块】 串7 【正确答案】 C【知识模块】 串8 【正确答案】 C【知识模块】 串9 【正确答案】 B【知识模块】 串10 【正确答案】 D【知识模块】 串11 【正确答案】 D【知识模块】 外部排序12 【正确答案】 B【知识模块】 外部排序13 【正确答案】 D【知识模块】 外部排序二、填空题14 【正确答案】 子串 主串【知识模块】 串15 【正确答案】 零个字符的串 零 由空格字符组成的串 所含空格的个数【知识模块】 串16 【正
10、确答案】 相等【知识模块】 串17 【正确答案】 bcdefef【试题解析】 concat(sLtbstr(s1，2，strlen(s2) ， substr(s1，strlen(s2) ，2)=concat(substr(s1，2，5)，substr(s1，5，2)=concat(bcdd，ef)=bcdefef【知识模块】 串18 【正确答案】 串的模式匹配目标串模式串【知识模块】 串19 【正确答案】 在一次比较中，没有上升进入其父结点的结点【知识模块】 外部排序20 【正确答案】 生成初始归并段 对这些初始归并段采用某种归并方法，进行多遍归并【知识模块】 外部排序三、应用题21 【正确答
11、案】 空串：指不含任何字符的串，记作 ，它的长度为 0。空格串：指由若干个空格组成的字符串，它的长度不为 0。串变量：可以取不同字符串值的变量。串常量：只能引用但不能改变值的串。主串与子串：一个串中由任意连续字符组成的子序列称为该串的子串，而该串称为它的所有子串的主串。串变量的名字：表示串的标识符。串变量值串变量：表示的字符序列。【知识模块】 串22 【正确答案】 (1)A+B=“#mule” (2)B+A=“mule”(3)D+C+B“myoldmule”(4)SubStr(B，3，2)=“le”(5)SubStr(C，1，0)=“”(6)StrLen(A)=1(7)StrLen(D)=2
12、(8)Index(B， D)=0(9)Index(C， “d”)=3 (10)Insert(D， 2，C)=“myldy”(11)Insert(B， 1，A)=“m#ule”(12)StrDel(B，2，2)“me”(13)StrDeI(B，2，0)=“mule”(14)StrReplace(C，2，2，“k”)=“ok”【知识模块】 串23 【正确答案】 substr(S，1，2)+“+”+substr(S，4 ，3)+substr(S ，3，1)【知识模块】 串24 【正确答案】 (1)int equall(string S，t)*串 s，t 为顺序存储结构*ifs curlen!=tcu
13、rlen) *判断串 s，T 长是否相等*return(0)； *两串不相同 *elsei=1;while(iS curlen);*若 is curlen 表示两串相同，返回 1，否则返回 0*(2)int equal2(strlist S，t)*串 S，t 为链式存储结构*p1=s;p2=t；while(p1!=NULL) *将串 S 中第 pos 起以后的字符后移* *(P+J)=*p；P 一一；P+;q=t; *将 P 移到第 pos 位置，q 指向串 t 的第一个字符 *for(k=1；k=0*P=0&*P=9)sum=sum*10+*p 一0；p+；ai+=sum；else p+；【
14、试题解析】 扫描输入的字符串，当串不结束时，若读的字符为数字字符，则该字符开始检查其后的若干字符，若是数字字符则累加，直到非数字字符为止，并将该数字放人数组 a 中，然后继续扫描，直到所有的字符全部检查完毕。算法描述如下。【知识模块】 串28 【正确答案】 viodCopyString(strings，stringot) *将串 s 中满足条件的字符赋给串 t*i=1； j=0；while(i=s0) t+j=si；if(si=)while(si+1=)*若后续字符是空格，则跳过*i+；i+：t0=j；【试题解析】 设两个变量 i 和 j 分别指向串 s 和串 t 的首位置，并将 si赋给t+
15、，若 si为空格，则跳过其后面连续的空格，直到将串 s 中满足条件的字符全部赋给串 t 为止。算法描述如下。【知识模块】 串29 【正确答案】 选择树是由参加比较的 n 个元素作为叶子结点而得到的完全二叉树；而堆是 n 个元素 R(i=1 ，2，n)的序列，它满足性质： RiR21 且RiR2i+1(1in2)，堆是一个含有 n 个结点的完全二又树。【知识模块】 外部排序30 【正确答案】 2 路平衡归并使用 4 台磁带机：T 1，T 2，T 2 和 T4，开始时初始归并段的分布如下： T 1：R 1(1L)，R 2(1L)，R 5(1L)， R7(1L)，R 0(1L) T2：R 2(1L)
16、，R4(1L)，R 6(1L)，R 8(1L)，R 10(1L) T3： T 4： 其中 Ri(1L)(1i10)表示归并段 Ri 的长度为 1L。 经过第一遍归并后，各磁带上的归并段的分布如下： T1： T 2： T3：R 1(2L)，R 3(2L)，R 5(2L) T4：R 2(2L)，R 4(2L) 经过第二遍归并后，各磁带上的归并段的分布如下： T 1：R 1(4L)，R 3(2L) T2：R 2(4L) T3： T 4： 经过第三遍归并后，各磁带上的归并段的分布如下： T 1： T 2： T 3：R 1(8L) T4：R 2(2L) 经过第四遍归并后，各磁带上的归并段的分布如下： T
17、 1：R 1(10L) T2： T 3： T 4：【知识模块】 外部排序31 【正确答案】 2 路多阶段归并使用 3 台磁带机：T 1、T 2 和 T3，假设开始时初始归并段的分布是 T1 中 20 段，T 2 中 35 段，其归并过程如下： i 遍后 T 1 T2 T3 开始 20(1L) 35(1L) 1 15(1L) 20(2L)(从 T1 和 T2 归并成 20 个 2L 长的段放到 T3) 2 15(3L) 5(2L) (从 T2 和 T3 归并成 15 个 3L 长的段放到 T1) 3 10(3L)5(5L) (从 T1 和 T3 归并成5 个 5L 长的段放到 T2) 4 5(3L) 5(8L) (从 T1 和 T2 归并成 5 个 8L 长的段放到 T3) 5 5(11L) (从 T1 和 T3 归并成 5 个 11L 长的段放到 T2)【知识模块】 外部排序
