数据结构模拟试卷1

1、数据结构模拟试卷1( 总分： 44.00 ，做题时间： 90 分钟)一、 单项选择题 ( 总题数： 12，分数： 24.00)1.( 江苏大学 ) 下面关于串的叙述中， ( ) 是不正确的。A. 串是字符的有限序列B. 空串是由空格构成的串C. 模式匹配是串的一种重要运算D. 串既可以采用顺序存储，也可以采用链式存储选项 A：串是零个或多个字符组成的有限序列，一般记为：S=''a1 a2 a n " ， S 称为串名，双引号括起来的字符序列是串值，将串值括起来的双引号本身不属于串，它的作用是避免串与常数或标识符混淆，故A 选项正确。 选项 B：窒皇是指长度为零的串，它

2、不包括任何字符。但是考生要注意与空白串进行区分，空白串是指由一个或者多个空格组成的串，故B 选项错误。 选项 C：模式匹配是一个比较复杂的串操作， 是子串在主串中的定位操作。常用的模式匹配算法有朴素的原始匹配算法和经过优化改进的无回溯算法，故 C 选项正确。 选项 D：串是特殊的线性表，所以串的存储结构与线性表的存储结构类似。串的顺序存储结构简称顺序串，顺序串又可按存储分配的不同分为静态存储分配的顺序串和动态存储分配的顺序串。串 的链式存储就是用单链表的方式存储串值，故D选项正确。2.( 华中科技大学 ) 若串 S="bioinformatics'' ，其子串的个数是

3、 ( ) 。A.15 B.95 C.35D.106 对于长度为 n 的字符串来说，其子串的个数为n(n+1) 2+1( 最后+1 是因为空串是任何串的子串) ，记住即可。此题 n=14，所以其子串的个数是106。3.( 中国科学院 ) 串是一种特殊的线性表，其特殊性体现在( ) 。A. 数据元素是一个字符B. 可以顺序存储C. 数据元素可以是多个字符D. 可以链式存储选择这道题的原因是它被多所学校( 武汉大学、中科院、大连理工、江苏大学等) 原题考查，考生只需记住一句话：串是一种特殊的线性表，其特殊性体现在数据元素是一个字符。4.( 中南大学 ) 求字符串 T 在字符串 S 中首次出现的位置的

4、操作称为( ) 。A. 求串的长度B. 求子串C. 串的模式匹配D. 串的连接第一题已经讲过，子串在主串中的定位操作称为模式匹配。例如A 和 B 分别为： A="This is a string'B=''is 则 B 是 A 的子串， B在 A 中出现了两次。其中首次出现对应的主串位置是3。因此称 B 在 A 中的序号( 或位置 ) 是 3。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，1C.

5、-1 ， 0，0，1，2， 3，1，1，2， 3，4，5D.-1 ， 0，1，2，-1 ，0， 1，2，1， 1， 2，3，4做出模式串以及对应字符下标， 如下表所示。S串长度为 0 时，next0=-1；S 串长度为 1 时，next1=0； S 串长度为 2 时， S 串为“ ab”next2=0； S 串长度为 3 时， S 串为“ aaba”next3=1； (S 串中下画线标出了其串首位置以及末尾位置的最长匹配串对，由此可求得当前 next 值) S 串长度为 4 时，S串为“abab”next4=2; S 串长度为 5 时，S 串为“ ababa”next5=3 ； S 串长度为

6、6 时，S 串为“，ababaa”next6=1 ；S 串长度为 7 时， S 串为“ a_babaaa” next7=1 ； S 串长度为 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.( 湖南大学 ) 稀疏矩阵一般的压缩存储方法有两种，即(

7、 ) 。A. 二维数组和三维数组B. 三元组和散列C. 三元组和十字链表D. 散列和十字链表稀疏矩阵进行压缩存储通常有两种方法：顺序存储( 三元组 ) 和链式存储 ( 十字链表 ) 。7.( 中山大学 ) 用十字链表表示一个稀疏矩阵，每个非零元一般用一个含有( ) 个域的结点表示。A.2B.3C.4D.5存储稀疏矩阵的十字链表结点包含5 个域：该非零元的行下标、该非零元的列下标、该非零元的值、该非零元所在行表的后继链域以及该非零元所在列表的后继链域。8.( 南京林业大学 ) 设广义表 L=(a)，则该广义表的长度是 ( ) ，深度是 ( )。A.1 ，1B.3 ，3C.3 ，1D.1 ，3广义

8、表的长度就是元素的个数，该广义表最外层括号里面只有一个元素(a)，故该广义表的长度为1；而括号最多层次为3，故该广义表的深度为3。9.( 北京师范大学 ) 已知广义表 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)第一步： tail(A)=(d，e， f)第二步： head(tail(A)=(d，e， f)第三步： tail(haead(tail(A)=(e，f) 第四步： head(tai

9、l(head(tail(A)=e10.( 重庆大学 ) 对于广义表，通常采用的存储结构是( )。A. 数组B. 链表C. Hash 表D. 三元组广义表通常采用链表作为存储结构，只是数据域有的时候是数据，有的时候是指向新表的指针；三元组一般用于存储稀疏矩阵结构；Hash 表一般用于存储针对查找操作的数据结构。11.( 南京林业大学 ) 一个非空广义表的表头( )。A. 不可能是子表B. 只能是子表C. 只能是原子D. 可以是子表或原子根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表；而其表尾必定是子表。12.( 华中科技大学 ) 广义表 (a,b)

10、，c，(d ，(e)的表尾是 ( ) 。A.(d ， (e)B.(d ，(e)C.eD.(c ， (d ， (e)二、 填空题 ( 总题数： 7，分数： 14.00)13.( 哈尔滨工程大学 ) 两个字符串相等的充要条件是：两个串的相等，且的字符相等。正确答案： ( 正确答案：长度，对应位置)14.( 重庆大学 ) 操作 StrDelete(&s,pos,len)从串 s( 其长度为 L) 中删除第 pos 个字符起长度为 len 的子串， 要求 pos 满足。正确答案： ( 正确答案： 1 posL-len+1)pos 必须满足被删除子串的起始位置不能少于s 的第一个字符，子串的最后

11、一个位置不能大于s 的最后一个字符，所以 1posL-len+1 。15.( 哈尔滨工程大学 ) 在字符串 S=“structure”中，以 t 为首的子串有个。正确答案： ( 正确答案： 11)11 个子串分别为： t 、tr 、tru 、truc 、truct、tructu、tructur、tructure、tu 、tur 、ture 。16.( 山东大学 ) 广义表 (a ，(a,b) ，d， e， (i,j)， k) 的长度是，深度是。正确答案： ( 正确答案： 5， 3)最外层的括号有五项，分别是 a、(a,b) 、d、e、(i，j) ，k) ，故该广义表的长度为5；i 和 j 的层

12、次最深， 都是 3，所以该广义表的深度为3。17.( 青岛大学 ) 广义表 Glist=(a)，则表尾为。正确答案： ( 正确答案： (a)18.( 青岛大学 ) 已知广义表 Glist=(a)，(b ，c， d) ， (e)，使用 head() 和 tail()函数取出 Glist中原子 b 的运算是。正确答案： ( 正确答案： head(1aead(tail(Glist)tail(Glist)=(b,c,d)，(e)； head(tail(Glist)=(b,c,d)； head(head(tail(G1ist)=b。19.( 武汉大学 ) 与普通的线性表不同的是，广义表的元素既可以是，也

13、可以是。正确答案： ( 正确答案：数据元素、子表)广义表是线性表的推广，即广义表中放松对表元素的原子限制，允许它们具有其自身结构，广义表的元素既可以是数据元素，也可以是子表。三、 设计题 ( 总题数： 3，分数： 6.00)20.( 北京理工大学 ) 抽象数据类型可以用三元组 (D ，S，P)，其中的 D，S，P 分别表示什么 ?你认为定义抽象数据类型的主要目的是什么?正确答案： ( 正确答案：抽象数据类型的三元组(D ，S，P) 中的 D表示数据， S表示关系， P 表示操作。抽象数据类型的定义可以由一种数据类型和定义在其上的一组操作组成，抽象数据类型的特征是使得使用与实现相分离，实现封装与

14、数据隐藏。)21. 用类 C 语言写出求广义表深度以及复制广义表的算法。正确答案： ( 正确答案：定义一个广义表类型如下： typedef Struct node int flag； union elemType data ； struct node *pointer ； ； struct node *1ink ； BSNode ， *BSLinkList ； 求广义表深度 int genlistDepth(BSLinkList 1ist)*1ist 存放广义链表的首地址，该算法返回广义链 表的深度* BSLinkList stacklM， p， *stackl用来记录子表的起始位置 * *s

15、tack2用来记录子表当前的深度， depth 用来表示当前所求子表的深度，maxdep用来记录当前已求出的那些子表的最大深度，stack1 和 stack2共用一个栈顶指针 * int stack2M，depth=0 ，maxdep=0， top=-1; p=list-pointer； *将 p 指针指向广义链表的第一个元素所在的链接点*if(p!=NULL) do while(p!=NULL) stack1+top=p； * 记录当前子表的起始位置* stack2top=depth； * 记录当前所求子表的深度 * if(p- flag=1) * 当前链接点元素是子表 * depth+ ；

16、 * 当前层次数加1* p=p- pointer； * 移动到下一层 * else p=NULL； if(maxdepdepth) maxdep=depth； * 记录当前已求得的最大层次数* p=stackltop； * 退回到上一层， 移动到下一个元素， 查看是否有子表 * depth=stack2top-； p=p- link ； (p!=NULL top!=-1)； returnmaxdep+1; 复制广义表 BSLinkListcopyBSList(BSLinkList1ista)BSLinkLiSt1istb=NULL ； if(1ista!=NULL) 1istb=(BSLink

17、List)malloc(sizeof(BSNode)； 1istb- flag=1ista- flag ；if(1ista-flag=0) 1istb- data=lista-data ； else listb- pointer=copyBSList(1ista-pointer)； listb-link=copyBSList(1ista-1ink) ， return 1istb； )22. 试写出连接两个顺序串以及判断两个顺序串是否相等的算法。正确答案： ( 正确答案： (1) 连接两个顺序串的算法。已知顺序串St1 和 St2 ，把 St2 连接到 St1 的末尾， 得到一个新的顺序串 St

18、3 。算法名为 Concat_St() ，参数为 St1 、St2 。 Concat st(St1，St2) char St3maxsize； * 创建一个新的顺序串为空* St3_1en=0 ， if(St1_1en+St2_1en maxsize+1) * 新串放不下两个串 * printf(''两串长度之和超长 !'')； return(NULL)； else for(i=ni =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)判断两个顺序串是否相等的算法。 已知顺序串 S