《数据结构练习第四章 串》由会员分享，可在线阅读，更多相关《数据结构练习第四章 串（11页珍藏版）》请在金锄头文库上搜索。
1、1数据结构练习第四章数据结构练习第四章 串串一、选择题1函数 substr(“DATASTRUCTURE” ，5，9)的返回值为（ ） 。 A. “STRUCTURE”B.“DATA” C. “ASTRUCTUR” D. “DATASTRUCTURE” 2字符串的长度是指（ ） 。 A. 串中不同字符的个数B. 串中不同字母的个数 C. 串中所含字符的个数 D. 串中不同数字的个数 3两个字符串相等的充要条件是（ ） 。 A. 两个字符串的长度相等B. 两个字符串中对应位置上的字符相等 C. 同时具备(A)和(B)两个条件 D. 以上答案都不对 4关于串的叙述中，正确的是（ ） A空串是只含有
2、零个字符的串 B.空串是只含有空格字符的串 C.空串是含有零个字符或含有空格字符的串 D.串是含有一个或多个字符的有穷序列 5下面关于串的的叙述中，哪一个是不正确的？（ ） A串是字符的有限序列 B空串是由空格构成的串 C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链 式存储 6设有两个串 S1 和 S2，求 S2 在 S1 中首次出现的位置的运算称作( ) A求子串 B.判断是否相等 C模型匹配 D.连接 7若串 S=software,其子串的数目是( )。 A8 B37 C36 D9 8串的长度是指（ ） A串中所含不同字母的个数 B串中所含字符的个数 C串中所含不同字符
3、的个数 D串中所含非空格字符的个数 9串是一种特殊的线性表，其特殊性体现在( )。 A数据元素是一个字符 B. 可以顺序存储 C. 数据元素可以是多个字符 D. 可以链接存储 10下面关于串的的叙述中，哪一个是不正确的（B ） A. 串是字符的有限序列 B. 空串是由空格构成的串 C. 模式匹配是串的一种重要运算 D. 串既可以采用顺序存储，也可以采用链式存储 11若串software，其非平凡子串（非空且不同于串本身）的数目是（C ） A. 8 B. 37 C. 35 D. 9 12串是一种特殊的线性表，其特殊性体现在（ B ） A. 可以顺序存储 B. 数组元素是一个字符 C. 可以连续存
4、储 D. 数据元素可以是多个字符213. 下面关于串的的叙述中，哪一个是不正确的？（ B B ） A串是字符的有限序列 B空串是由空格构成的串 C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储 二、填空题 1两个串是相等的，当且仅当两个串的长度相等且_对应位置_的字符都 相同。 2串是一种特殊的线性表，串常见的存储结构有顺序存储和_链式存储_两 种方式。 3空格串是指_，其长度等于_。 (1) 由空格字符（ASCII 值 32）所组成的字符串 (2)空格个数 4一个字符串中_称为该串的子串 。任意个连续的字符组成的子序列 5字符串ababaaab的 nextval 函数
5、值为_。01010421 6串是一种特殊的线性表，其特殊性表现在_(1)_；串的两种最基本的存储 方式是_(2)_、_(3)_；两个串相等的充分必要条件是_(4)_。(1)其数据 元素都是字符 (2)顺序存储 (3)和链式存储 (4)串的长度相等且两串中对应位置的字符也相等 7下列程序读入无符号 16 进制数（出现的字母为小写），将其转换为十进制 数输出。请将程序空缺部分补全。 int f(char *s) int n=0, i; for(i=0;si!=0; i+) n=n*16+ (1) ; return n; main() char s10; scanf(“%s”,s); printf(
6、“%dn”, (2) ); (1)(si=97?si-87:si-48) a到f的 ASCII 码是 97 到 102 (2)f(s) 8下列算法实现求采用顺序结构存储的串 s 和串 t 的一个最长公共子串。 void maxcomstr(orderstring *s,*t, int index, length) int i,j,k,length1,con;index=0;length=0;i=1;while (ilength) index=i; length=length1; (3)_; else (4) _;(5) _ 题目分析题目分析 本题算法采用顺序存储结构求串 s 和串 t 的最大公
7、共子串。串 s 用 i 指针（1length) printf(“The copy position is wrong“);else if (start+count-1length) printf(“Too characters to be copied“); else for(i=start-1,j=0; in-1），返回子串在主串的位置（i-j）。 否则，当 im-n 则为匹配失败。 intint index(charchar s,t,intint m,n) 字符串 s 和 t 用一维数组存储，其长度分别为 m 和 n 本算法求字符串 t 在字符串 s 中的第一次出现,匹配成功输出 t 串在
8、 s 中的位 置,否则输出 0 intint i=0,j=0;whilewhile(i=0p=x.str; q=y.str;whilewhile(p q+; 对应字符相等，指针后移ifif(!p elseelse returnreturn(0); 8设计一个程序，使输入的句子按如下方式改造之后输出: (1) 单词之间只留一个空格做间隔； (2) 句子结束后必须紧跟句号； (3) 如果把句子的单词从左到右依次编号为 1，2，3，则对于第奇数个单 词，只要直接复制就行了，而对于第偶数个单词，应按反序打印。例如： 输入句子是: this is a silly program ; 改造后的输出是:th
9、is si a yllis program. 【中国科学技术大学 1995 十六.2(15 分)】 #includeinclude voidvoid transf(charchar *s)本算法将串 s 按要求改造 charchar *s,sk; sk 是栈，存储第偶数个单词intint i,j,k,flag,finished=0;flag 是单词开始与结束的标记scanf(“%s”,s);i=j=k=flag=0; k 是单词个数，用于标记奇数或偶数单词 whilewhile(*s!=0 滤去前导空格 ifif(flag=1) 单词结束11if(k%2=0) 第偶数个单词逆置 whilewh
10、ile(i0) s+j=ski-;s+j= ; 用一个空格分割单词 ； flag=0; s+; breakbreak;casecase ;:whilewhile(sj= )j-; 分号为句子结束标志 s+j=.; finished=1; breakbreak; 句子结束后要紧跟句号defaultdefault: ifif(flag=0) flag=1; k+; 开始新单词 ifif(k%2=1) s+j=*s+; 奇数单词直接复制elseelse sk+i=*s+; 偶数单词进栈switch main()charchar s;scanf(“%s”,s); transf(s); 9试设计一个 C
11、 算法（或 C 程序）：用单链表作存储结构，以回车为结束标志， 输入一个任意长度的字符串；然后判断该字符串是否为“回文”（正向读和反 向读时，串值相同的字符串称为“回文”），输出信息“Yes”或“No”；最后 删除字符串并释放全部空间。例如： 若输入“ABCD12321DCBA”是回文，则输出“Yes”; 若输入“ABCD123DCBA”，不是回文，则输出“No”。 要求：定义相关数据类型，不得使用数组（顺序表）作字符串的存诸结构和辅 助存储空间。假定字符串的长度为 n ,试分析上述算法的时间复杂度。【华中 科技大学 2004 五(10 分)】 题目分析题目分析 利用栈存放字符串的前半部分，将
12、后半部分与栈中弹出元素比较。 intint Symmetry(Linkedlist head,int n)本算法判断数据域为字符且长为 n 的单链表是否是“回文”，返回 1 或 0 表示成功或失败charchar s; 字符栈，容量足够大p=head-next 设链表带头结点int i=0; whilewhile(idata; p=p-next; i+; ifif(n%2=1) p=p-next;若链表有奇数个结点，则跳过中间结点whilewhile(p)ifif(p-data=si) p=p-next; i-;elseelse break; 不是回文ifif(!p elseelse returnreturn(0);
