1、综合模拟试卷 22 及答案与解析一、单项选择题1 下面关于串的叙述中，( )是不正确的。（A）串是字符的有限序列（B）空串是由空格构成的串（C）模式匹配是串的一种重要运算（D）串既可以采用顺序存储，也可以采用链式存储2 若串 S=“bioinformatics“，其子串的个数是( )。（A）1 5（B） 95（C） 35（D）1 063 串是一种特殊的线性表，其特殊性体现在( )。（A）数据元素是一个字符（B）可以顺序存储（C）数据元素可以是多个字符（D）可以链式存储4 求字符串 T 在字符串 S 中首次出现的位置的操作称为( )。（A）求串的长度（B）求子串（C）串的模式匹配（D）串的连接5
2、 串“ababaaababaa”的 Rext 数组为( )。（A）一 1，0，1，2，3，4，5，6，7，8，8，8（B）一 1，0， 1，0， 1，0，0， 0，0， 1，0， 1（C）一 1，0，0， 1，2， 3， 1， 1，2，3，4，5（D）一 1，0， 1，2，一 1，0， 1，2， 1，1，2 ，3，46 稀疏矩阵一般的压缩存储方法有两种，即( )。（A）二维数组和三维数组（B）三元组和散列（C）三元组和十字链表（D）散列和十字链表7 用十字链表表示一个稀疏矩阵，每个非零元一般用一个含有( )个域的结点表示。（A）2（B） 3（C） 4（D）58 设广义表 L=(a)，则该广义表
3、的长度是( )，深度是( )。（A）1，1（B） 3，3（C） 3，1（D）1，39 已知广义表 A=(a，b,c)，(d，e ，f)，试问从 A 中取出原子 e 的操作运算是( )。（A）tail(head(A)（B） head(tail(A)（C） head(tail(tail(head(A)（D）head(tail(1lead(tail(A)10 对于广义表，通常采用的存储结构是( )。（A）数组（B）链表（C） Hash 表（D）三元组11 一个非空广义表的表头( )。（A）不可能是子表（B）只能是子表（C）只能是原子（D）可以是子表或原子12 广义表(a，b)，c，(d，(e)的表尾
4、是( )。（A）(d ，(e)（B） (d，(e)（C） e（D）(c，(d，(e)二、填空题13 两个字符串相等的充要条件是：两个串的_相等，且_的字符相等。14 操作 StrDelete(if(lista!=NULL)listb=(BSLinkList)malloc(sizeof(BSNode)listb-flag=lista-flag；if(lista 一flag=0)listb 一data=lista-data；elselistb 一pointer=copyBSList(lista 一pointer)；liStb 一link=copyBSList(lista 一link) ；retur
5、n listb；22 【正确答案】 (1)连接两个顺序串的算法。已知顺序串 St1 和 St2，把 St2 连接到 St1 的末尾，得到一个新的顺序串 St3。算法名为 Concat_St()，参数为 St1、St2。Concat_St(St1，St2)char St3maxsize； *创建一个新的顺序串为空*St3_len=0；if(St1_len+St2_lenmaxsize+1) *新串放不下两个串 *printf(“两串长度之和超长!“)；return(NULL)；elsefor(i=1；i=stl_len；i+) *把串 St1 传送给串 St3*St3i=St1i；for(j=1
6、；j=st2_len；j+) *接着把 St2 传送给串 St3*St3j+Stl_len=st2j；St3_Len=St1_len+St2_len； *修改串 St3 的长度*/St3St3_len+1=“0“； *为 st3 安放串结束符*return(St3)； *返回 St3*(2)判断两个顺序串是否相等的算法。已知顺序串 St1 和 St2，如果相等则返回 1，否则返回 0。算法名为 Equal_st()，参数为 St1、St2。Equal_St(St1，St2)if(St1 len!=St2_len) *两个串长度不相等*return(0)；else *两个串长度相等*for(i=l，i=St1_len；i+)if(St1i!=St2i) *有字符不同*return(0)；return(1)，
