《数据结构》-第四章

习题41选择题1、空串与空格串是（B）。A、相同B、不相同、不能确定2、串是一种特殊的线性表，其特殊性体现在（B）。A、可以顺序存储B、数据元素是一个字符C、可以链式存储D、数据元素可以是多个字符3、设有两个串P和Q，求Q在P中首次出现的位置的操作是（B）。A、连接B、模式匹配C、求子串D、求串长4、设串S1“ABCDEFG”，S2“PQRST”函数STRCONCAT（S，T）返回S和T串的连接串，STRSUB（S，I，J）返回串S中从第I个字符开始的、由连续J个字符组成的子串。STRLENGTHS返回串S的长度。则STRCONCAT（STRSUB（S1，2，STRLENGTH（S2），STRSUB（S1，STRLENGTH（S2），2）的结果串是（D）。A、BCDEFB、BCDEFGC、BCPQRSTD、BCDEFEF5、若串S“SOFTWARE”，其子串个数是（B）。A、8B、37C、36D、942简答题1、简述空串与空格串、主串与子串、串名与串值每对术语的区别答空串是指长度为0的串，即没有任何字符的串。空格串是指由一个或多个空格组成的串，长度不为0。子串是指由串中任意个连续字符组成的子序列，包含子串的串称为主串。串名是串的一个名称，不指组成串的字符序列。串值是指组成串的若干个字符序列，即双引号中的内容。2、两个字符串相等的充要条件是什么答条件一是两个串的长度必须相等条件二是串中各个对应位置上的字符都相等。3、串有哪几种存储结构答有三种存储结构，分别为顺序存储、链式存储和索引存储。4、已知两个串S1”FGCDBCABCADR”,S2”ABC”,试求两个串的长度，判断串S2是否是串S1的子串，并指出串S2在串S1中的位置。答（1）串S1的长度为14，串S2的长度为3。（2）串S2是串S1的子串，在串S2中的位置为9。5、已知S1IMASTUDENT，S2STUDENT，S3TEACHER，试求下列各操作的结果STRLENGTHS1；答13STRCONCATS2,S3；答”STUDENTTEACHAR”STRDELSUBS1,4,10；答IM6、设S1”AB”，S2”ABCD”，S3”EFGHIJK，试画出它们在各种存储结构下的结构图。答顺序存储方式下AB0S1ABCD0S2EFGHIJK0S3链式存储方式ABS10ABS2CD0EFS3K043算法题1、试写出将字符串S2中的全部字符拷贝到字符串S1中的算法，不允许用库函数STRCPY。（可作为上机实践题目）INCLUDEDEFINEMAXLEN100STRUCTSTRINGCHARCHMAXLEN/MAXLEN为数组中存储空间的最大数量INTLENVOIDSTRCOPYSTRINGFORI0IINCLUDETYPEDEFCHARELEMTYPESTRUCTLNODEELEMTYPEDATASTRUCTLNODENEXTL/单链表的后插入创建算法VOIDRCREATELNODEL,ELEMTYPEAINTILNODEP,SPLFORI0AI0ISLNODEMALLOCSIZEOFLNODESDATAAISNEXTNULLPNEXTSPS/单链表的输出算法VOIDPRINTLISTLNODELLNODEPIFLNEXTNULLPRINTF“单链表为空N“ELSEPLNEXTWHILEPNEXTNULLPRINTF“C“,PDATAPPNEXTPRINTF“CN“,PDATACHARLOCATEELEMLNODES1,LNODES2LNODEP,QIFS2NEXTNULLPRINTF“串S2为空串N“ELSEIFS1NEXTNULLPRINTF“串S1为空串N“RETURNS2NEXTDATAELSEPS2NEXTWHILEPNULLQS1NEXTWHILEQDATAPDATAIFQDATAPDATARETURNPDATAPPNEXTRETURN0/主函数VOIDMAINLNODES1,S2CHARA40,B40CHARXINTI0,J0PRINTF“输入S1串（以输入为结束标志）N“SCANF“C“,WHILEXAIXSCANF“C“,AI0S1LNODEMALLOCSIZEOFLNODES1NEXTNULLRCREATES1,APRINTF“输入S2串（以输入为结束标志）N“SCANF“C“,WHILEXBJXSCANF“C“,BJ0S2LNODEMALLOCSIZEOFLNODES2NEXTNULLRCREATES2,BPRINTF“S1串为“PRINTLISTS1PRINTF“S2串为“PRINTLISTS2PRINTF“S2中第一个不在S1中出现的字符为“PRINTF“C“,LOCATEELEMS1,S23、设字符串采用块链存储结构，块链中每个结点存放M（M4）个字符，试写出实现字符串删除的算法。INCLUDEINCLUDEDEFINEN30DEFINEM4TYPEDEFSTRUCTLNODECHARDATA4STRUCTLNODENEXTLINKSTRINGINTR0VOIDCREATELINKSTRINGS,CHARCHMLNODEP,QQSFORINTK0KDATAICHKIPNEXTNULLQNEXTPQPPLNODEMALLOCSIZEOFLNODEPDATA00PNEXTNULLQNEXTPVOIDDELSTRINGLINKSTRINGS,INTI,INTJINTKLINKSTRINGPSNEXT,Q,TIFIR|JRPRINTF“给定的范围不合法N“FORK0KNEXTTPNEXTQTNEXTFORK0KNEXTPNEXTTVOIDPRINTSTRINGLINKSTRINGS,INTRLNODEPSNEXTIFSNEXTNULLPRINTF“是空串N“ELSEFORINTI0IDATAJPRINTF“N“PPNEXTVOIDMAINLINKSTRINGSINTI0,J0,X,YCHARANM,CHSLNODEMALLOCSIZEOFLNODESNEXTNULLPRINTF“请输入相应的字符串以作为结束标志N“SCANF“C“,WHILECHAIJCHJIFJMIJ0RSCANF“C“,IFJDEFINEMAXLEN100STRUCTSTRINGCHARCHMAXLENINTLEN/顺序串的创建算法VOIDCREATE_SQSTRINGFORI0INISCHIAISLENN/顺序串输出算法VOIDPRINTLISTSTRINGSPRINTF“当前顺序串为“FORINTI0ISLENIPRINTF“C“,SCHIPRINTF“N“/删除顺序串中值与X相等的元素VOIDDELSTRINGWHILEISLENIFSCHIXFORINTKI1KSLENKSCHK1SCHKSLENELSEI/主函数VOIDMAINSTRINGSCHARAMAXLEN,CHINTJ0PRINTF“输入删除字符“SCANF“C“,PRINTF“请输入顺序串的元素（以作为结束标志）