1、数据结构模拟试卷 1 及答案与解析一、单项选择题1 (江苏大学 )下面关于串的叙述中，( ) 是不正确的。（A）串是字符的有限序列（B）空串是由空格构成的串（C）模式匹配是串的一种重要运算（D）串既可以采用顺序存储，也可以采用链式存储2 (华中科技大学) 若串 S=“bioinformatics，其子串的个数是( )。（A）15（B） 95（C） 35（D）1063 (中国科学院) 串是一种特殊的线性表，其特殊性体现在( )。（A）数据元素是一个字符（B）可以顺序存储（C）数据元素可以是多个字符（D）可以链式存储4 (中南大学 )求字符串 T 在字符串 S 中首次出现的位置的操作称为( )。（
2、A）求串的长度（B）求子串（C）串的模式匹配（D）串的连接5 (江苏大学 )串“ababaaababaa的 next 数组为( )。（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 (中山大学 )用十字链表表示一个稀疏矩阵，每个非零元一般用一个含有( )个域的结点
3、表示。（A）2（B） 3（C） 4（D）58 (南京林业大学) 设广义表 L=(a)，则该广义表的长度是( )，深度是( )。（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(haead(tail(A)10 (重庆大学) 对于广义表，通常采用的存储结构是( )。（A）数组（B）链表（C） Hash 表（D）三元组11 (南京林业大学) 一
4、个非空广义表的表头( ) 。（A）不可能是子表（B）只能是子表（C）只能是原子（D）可以是子表或原子12 (华中科技大学) 广义表(a,b)，c，(d，(e) 的表尾是( )。（A）(d ，(e)（B） (d，(e)（C） e（D）(c，(d，(e)二、填空题13 (哈尔滨工程大学) 两个字符串相等的充要条件是：两个串的_相等，且_的字符相等。14 (重庆大学) 操作 StrDelete( S 串长度为 5 时，S 串为“ababa”next5=3； S 串长度为 6 时，S 串为“，ababaa”next6=1； S 串长度为 7 时，S 串为“a_babaaa”next7=1； S 串长度
5、为 8 时，S 串为“ababaaab”next8=2； S 串长度为 9 时，S串为“ababaaaba”next9=3 ； S 串长度为 10 时，S 串为“ababaaabab”next10=4； S 串长度为 11 时，S 串为 “ababaaababa”next11=5； 综上，next 数组值为：-1，0，0，1，2，3，1，1，2，3，4，56 【正确答案】 C【试题解析】 稀疏矩阵进行压缩存储通常有两种方法：顺序存储(三元组)和链式存储(十字链表) 。7 【正确答案】 D【试题解析】 存储稀疏矩阵的十字链表结点包含 5 个域：该非零元的行下标、该非零元的列下标、该非零元的值、该
6、非零元所在行表的后继链域以及该非零元所在列表的后继链域。8 【正确答案】 D【试题解析】 广义表的长度就是元素的个数，该广义表最外层括号里面只有一个元素(a)，故该广义表的长度为 1；而括号最多层次为 3，故该广义表的深度为3。9 【正确答案】 D【试题解析】 第一步：tail(A)=(d，e ，f)第二步：head(tail(A)=(d，e，f)第三步：tail(haead(tail(A)=(e，f)第四步：head(tail(head(tail(A)=e10 【正确答案】 B【试题解析】 广义表通常采用链表作为存储结构，只是数据域有的时候是数据，有的时候是指向新表的指针；三元组一般用于存储
7、稀疏矩阵结构；Hash 表一般用于存储针对查找操作的数据结构。11 【正确答案】 D【试题解析】 根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表；而其表尾必定是子表。12 【正确答案】 D二、填空题13 【正确答案】 长度，对应位置14 【正确答案】 1posL-len+1【试题解析】 pos 必须满足被删除子串的起始位置不能少于 s 的第一个字符，子串的最后一个位置不能大于 s 的最后一个字符，所以 1posL-len+1。15 【正确答案】 11【试题解析】 11 个子串分别为：t、tr、tru 、 truc、truct、 tructu、tr
8、uctur、tructure、tu、tur、ture。16 【正确答案】 5，3【试题解析】 最外层的括号有五项，分别是 a、(a,b) 、d、e、(i ，j)，k) ，故该广义表的长度为 5；i 和 j 的层次最深，都是 3，所以该广义表的深度为 3。17 【正确答案】 (a)18 【正确答案】 head(1aead(tail(Glist)【试题解析】 tail(Glist)=(b,c,d)，(e) ；head(tail(Glist)=(b,c,d)；head(head(tail(G1ist)=b。19 【正确答案】 数据元素、子表【试题解析】 广义表是线性表的推广，即广义表中放松对表元素的
9、原子限制，允许它们具有其自身结构，广义表的元素既可以是数据元素，也可以是子表。三、设计题20 【正确答案】 抽象数据类型的三元组(D，S，P)中的 D 表示数据，S 表示关系，P 表示操作。抽象数据类型的定义可以由一种数据类型和定义在其上的一组操作组成，抽象数据类型的特征是使得使用与实现相分离，实现封装与数据隐藏。21 【正确答案】 定义一个广义表类型如下：typedef Struct nodeint flag；union elemType data；struct node *pointer；struct node *1ink； BSNode，*BSLinkList；求广义表深度int gen
10、listDepth(BSLinkList 1ist) *1ist 存放广义链表的首地址，该算法返回广义链表的深度*BSLinkList stacklM，p， *stackl 用来记录子表的起始位置 *stack2 用来记录子表当前的深度，depth 用来表示当前所求子表的深度，maxdep 用来记录当前已求出的那些子表的最大深度，stack1 和 stack2 共用一个栈顶指针*int stack2M，depth=0，maxdep=0，top=-1;p=list-pointer； *将 p 指针指向广义链表的第一个元素所在的链接点*if(p!=NULL)dowhile(p!=NULL)stac
11、k1+top=p； *记录当前子表的起始位置*stack2top=depth； *记录当前所求子表的深度*if(p-flag=1) *当前链接点元素是子表*depth+； *当前层次数加 1*p=p-pointer； *移动到下一层*elsep=NULL；if(maxdepdepth)maxdep=depth； *记录当前已求得的最大层次数*p=stackltop； *退回到上一层，移动到下一个元素，查看是否有子表 *depth=stack2top-；p=p-link；(p!=NULLtop!=-1)；return maxdep+1;复制广义表BSLinkList copyBSList(BSL
12、inkList 1ista)BSLinkLiSt 1istb=NULL；if(1ista!=NULL)1istb=(BSLinkList)malloc(sizeof(BSNode)；1istb-flag=1ista-flag；if(1ista-flag=0)1istb-data=lista-data；elselistb-pointer=copyBSList(1ista-pointer) ；listb-link=copyBSList(1ista-1ink) ，return 1istb；22 【正确答案】 (1)连接两个顺序串的算法。已知顺序串 St1 和 St2，把 St2 连接到 St1 的末
13、尾，得到一个新的顺序串 St3。算法名为 Concat_St()，参数为 St1、St2。Concat st(St1，St2)char St3maxsize； *创建一个新的顺序串为空*St3_1en=0，if(St1_1en+St2_1enmaxsize+1) *新串放不下两个串 *printf(两串长度之和超长!) ；return(NULL)；elsefor(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=St
14、1_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。
