《数据结构 第4章 串答案》由会员分享，可在线阅读，更多相关《数据结构 第4章 串答案（12页珍藏版）》请在金锄头文库上搜索。
1、郑大考研网 祝您考研成功！ 可为你提供郑大各专业历年考研真题和相关笔记！郑大考研网论坛http:/ 郑大考研网热线：13633846090第四章 串 一、选择题 1.B2.E3.C4.A5.C6.A7.1D7.2F8.B 注9.D10.B注：子串的定义是：串中任意个连续的字符组成的子序列，并规定空串是任意串的子串， 任意串是其自身的子串。若字符串长度为 n（n0） ，长为 n 的子串有 1 个，长为 n-1 的子 串有 2 个，长为 n-2 的子串有 3 个，长为 1 的子串有 n 个。由于空串是任何串的子 串，所以本题的答案为：8*（8+1）/2+1=37。故选 B。但某些教科书上认为“空
2、串是任意 串的子串”无意义，所以认为选 C。为避免考试中的二意性，编者认为第 9 题出得好。 二、判断题1.2.3.三填空题 1(1) 由空格字符（ASCII 值 32）所组成的字符串 (2)空格个数 2字符 3任意个连续的字符组成的子序列 45 5.O(m+n) 601122312 701010421 8(1)模式匹配 (2)模式串 9(1)其数据元素都是字符(2)顺序存储(3)和链式存储(4)串的长度相等且两串中对应位置 的字符也相等 10两串的长度相等且两串中对应位置的字符也相等。 11 xyxyxywwy 12*s+=*t+ 或（*s+=*t+）!=0 13 （1）charchar s
3、 (2) j+ (3) i = j 14题目分析本题算法采用顺序存储结构求串 s 和串 t 的最大公共子串。串 s 用 i 指针 （1midch /当读入不是分隔符whilewhile (it.curlen，则向左移；若 jmaxlen)printf(“参数错误n”);exit(0); /检查参数及置换后的长度的合法性。ifif(j=i+j-1;k-) s.chk+t.curlen-j=s.chk;elseelse ifif (jt.curlen) /s 串中被替换子串的长度小于 t 串的长度。forfor(k=i-1+j;kt.curlen) s.curlen=s.curlen-(j-t.c
4、urlen);elseelse s.curlen=s.curlen+(t.curlen-j); /算法结束 算法讨论若允许使用另一数组，在检查合法性后，可将 s 的第 i 个（不包括 i）之 前的子串复制到另一子串如 s1 中，再将 t 串接到 s1 串后面,然后将 s 的第 i+j 直到尾的部 分加到 s1 之后。最后将 s1 串复制到 s。主要语句有： forfor(k=0;ki-1+j;k-);/将子串第 i+j-1 个字符以后的子串复制到 s1s1.chl-=s.chk forfor(k=0;k=pos ;j-)*(p+x)=*p; p-;/串 s 的 pos 后的子串右移，空出串 t
5、 的 位置。q-; /指针 q 回退到串 t 的最后一个字符forfor(j=1;j0) sj+=stki- /将第偶数个字符逆序填入原字符数组 14.题目分析本题是对字符串表达式的处理问题，首先定义 4 种数据结构：符号的类 码，符号的 TOKEN 表示，变量名表 NAMEL 和常量表 CONSL。这四种数据结构均定义成结构 体形式，数据部分用一维数组存储，同时用指针指出数据的个数。算法思想是从左到右扫 描表达式，对读出的字符，先查出其符号类码：若是变量或常量，就到变量名表和常量表 中去查是否已有，若无，则在相应表中增加之，并返回该字符在变量名表或常量表中的下 标；若是操作符，则去查其符号类
6、码。对读出的每个符号，均填写其 TOKEN 表。如此下去， 直到表达式处理完毕。先定义各数据结构如下。 structstruct / 定义符号类别数据结构charchar data7; /符号 charchar code7； /符号类码 TYPL； typedeftypedef structstruct /定义 TOKEN 的元素intint typ； /符号码 intint addr； /变量、常量在名字表中的地址 cmp； structstruct cmp data50；/定义 TOKEN 表长度NAMEL.last）NAMEL.datai=ch；NAMEL.last+；/变 量加入cas
7、ecase0: casecase1: casecase2: casecase3: casecase4: casecase5:/处 理常量 casecase6: casecase 7:casecase8: casecase9: TY=1；/常量类码为 1forfor（i=1；iCONSL.last） CONSL.datai=ch；CONSL.last+；/将 新常量加入defaultdefault: /处理运算符TYoperator（ch） ；/类码序号i=0 ； /填入 TOKEN 的 addr 域（期望输出空白） /结束 switchswitch，下面将 ch 填入 TOKEN 表 TOKE
8、N.data+TOKEN.last.typ=TY；TOKEN.dataTOKEN.last.addr=i； scanf（“c” ，&ch） ； /读入表达式的下一符号。/whilewhile /算法结束 程序讨论为便于讨论，各一维数组下标均以 1 开始，在字符为变量或常量的情况下， 将其类码用 TY 记下，用 i 记下其 NAMEL 表或 CONSL 表中的位置，以便在填 TOKEN 表时用。 在运算符（+ ， * ， （ ， ） ）填入 TOKEN 表时，TOKEN 表的 addr 域没意义，为了程 序统一，这里填入了0 。本题是表达式处理的简化情况（只有 3 个单字母变量，常量只 有 0.9，操作符只 4 个） ，若是真实情况，所用数据结构要相应变化。
