1、数据结构模拟试卷 1 及答案解析(总分：44.00，做题时间：90 分钟)一、单项选择题(总题数：12，分数：24.00)1.(江苏大学)下面关于串的叙述中，( )是不正确的。（分数：2.00）A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储2.(华中科技大学)若串 S=“bioinformatics，其子串的个数是( )。（分数：2.00）A.15B.95C.35D.1063.(中国科学院)串是一种特殊的线性表，其特殊性体现在( )。（分数：2.00）A.数据元素是一个字符B.可以顺序存储C.数据元素可以是多个字符D.可
2、以链式存储4.(中南大学)求字符串 T 在字符串 S 中首次出现的位置的操作称为( )。（分数：2.00）A.求串的长度B.求子串C.串的模式匹配D.串的连接5.(江苏大学)串“ababaaababaa的 next 数组为( )。（分数：2.00）A.-1，0，1，2，3，4，5，6，7，8，8，8B.-1，0，1，0，1，0，0，0，0，1，0，1C.-1，0，0，1，2，3，1，1，2，3，4，5D.-1，0，1，2，-1，0，1，2，1，1，2，3，46.(湖南大学)稀疏矩阵一般的压缩存储方法有两种，即( )。（分数：2.00）A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D
3、.散列和十字链表7.(中山大学)用十字链表表示一个稀疏矩阵，每个非零元一般用一个含有( )个域的结点表示。（分数：2.00）A.2B.3C.4D.58.(南京林业大学)设广义表 L=(a)，则该广义表的长度是( )，深度是( )。（分数：2.00）A.1，1B.3，3C.3，1D.1，39.(北京师范大学)已知广义表 A=(a,b,c)，(d，e，f)，试问从 A 中取出原子 e 的操作运算是( )。（分数：2.00）A.tail(head(A)B.head(tail(A)C.head(tail(tail(head(A)D.head(tail(haead(tail(A)10.(重庆大学)对于广
4、义表，通常采用的存储结构是( )。（分数：2.00）A.数组B.链表C.Hash 表D.三元组11.(南京林业大学)一个非空广义表的表头( )。（分数：2.00）A.不可能是子表B.只能是子表C.只能是原子D.可以是子表或原子12.(华中科技大学)广义表(a,b)，c，(d，(e)的表尾是( )。（分数：2.00）A.(d，(e)B.(d，(e)C.eD.(c，(d，(e)二、填空题(总题数：7，分数：14.00)13.(哈尔滨工程大学)两个字符串相等的充要条件是：两个串的_相等，且_的字符相等。（分数：2.00）_14.(重庆大学)操作 StrDelete( p=list-pointer；
5、*将 p 指针指向广义链表的第一个元素所在的链接点* if(p!=NULL) do while(p!=NULL) stack1+top=p； *记录当前子表的起始位置* stack2top=depth； *记录当前所求子表的深度* if(p-flag=1) *当前链接点元素是子表* depth+； *当前层次数加1* p=p-pointer； *移动到下一层* else p=NULL； if(maxdepdepth) maxdep=depth； *记录当前已求得的最大层次数* p=stackltop； *退回到上一层，移动到下一个元素，查看是否有子表* depth=stack2top-； p=
6、p-link； (p!=NULLtop!=-1)； return maxdep+1; 复制广义表 BSLinkList copyBSList(BSLinkList 1ista) BSLinkLiSt 1istb=NULL； if(1ista!=NULL) 1istb=(BSLinkList)malloc(sizeof(BSNode)； 1istb-flag=1ista-flag； if(1ista-flag=0) 1istb-data=lista-data； else listb-pointer=copyBSList(1ista-pointer)； listb-link=copyBSList(
7、1ista-1ink)， return 1istb； )解析：22.试写出连接两个顺序串以及判断两个顺序串是否相等的算法。（分数：2.00）_正确答案：(正确答案：(1)连接两个顺序串的算法。 已知顺序串 St1 和 St2，把 St2 连接到 St1 的末尾，得到一个新的顺序串 St3。算法名为 Concat_St()，参数为 St1、St2。 Concat st(St1，St2) char St3maxsize； *创建一个新的顺序串为空* St3_1en=0， if(St1_1en+St2_1enmaxsize+1) *新串放不下两个串* printf(两串长度之和超长!)； retur
8、n(NULL)； else for(i=n i=St1_1en；i+) *把串 St1 传送给串 St3* St3i=St1 i； for(j=1; j=St2_1en；j+) *接着把 St2 传送给串 St3* St3j+St1_1en=St2j; St3_Len=St1_1en+St2_1en； *修改串 St3 的长度* St3St3_1en+1=0； *为 St3 安放串结束符* return(St3)； *返回 St3* (2)判断两个顺序串是否相等的算法。 已知顺序串 St1 和 St2，如果相等则返回 1，否则返回 0。算法名为Equal_St()，参数为 St1、St2。 Equa1_St(St1，St2) if(St1_1en!=St2_1en) *两个串长度不相等* return(0)； else *两个串长度相等* for(i=1；i=St1_1en；i+) if(St1i!=St2i) *有字符不同* return(0)， return(1)； (2)判断两个顺序串是否相等的算法。 已知顺序串St1 和 St2，如果相等则返回 1，否则返回 0。算法名为 Equal_St()，参数为 St1、St2。)解析：
