数据结构习题集包含答案(3)

19．一个栈的输人序列是12345，则栈的输出序列为12345是_________（填是否可能）。 20．设sq[1．．maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，则作入栈操作的条件是______________。 21．设sq[1．．maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，如果把栈顶元素弹出并送到X中，则需执行语句______________。 22．栈的特性是__________________。

23．对栈进行退栈时的操作是先取出元素，后移动_________。 24．设s[1．．max]为一个顺序存储的栈，变量top指示栈顶位置，栈为满的条件是____。 25．设链栈的栈顶指针为top，则栈非空的条件是___________。

26．已知循环队列用数组data[1...n]存储元素值，用f，r分别作为头尾指针， 则当前元素个数为____________。

27．在一个循环队列中，队首指针指向队首元素的________位置。（前一个或后一个） 28．队列中允许进行删除的一端称为_______________。

29．链队列实际上是一个同时带有头指针和尾指针的单链表（1．．n），尾指针指向该单链表的第___________个元素。

30．设双向链表链列为lq，lq的头指针为lq.Front，尾指针为lq.Rear，则队列为空的条件是____________。

31．从循环队列中删除一个元素，其操作是先取出一个元素，后移动______________。 32．队列中允许进行插入的一端称为_________。

1. 表尾、栈顶、栈底、空栈 2. 进栈、入栈、退栈、出栈

3. 栈顶元素、栈顶元素、栈顶元素、最先出栈、后进先出、LIFO 4. 顺序、链式、顺序栈、链栈 5. 溢出、上溢、溢出、下溢 6. 链栈、特殊的单链表 7. 中缀表达式

8. 后缀表达式、波兰式

9. 特殊的线性表、队尾、队头 10. 先进先出、先进先出、FIFO 11. 顺序存储结构、顺序队列

12. 队头元素、队尾元素、队头指针、队尾指针 13. 循环队列、取模运算

14. 递归函数、自调用函数、直接递归调用、间接递归调用 15. 空、满 16. 链队列 17. n-1

18. 不可能的 19. 可能的

20. top!=maxsize

21. x=sq[top]; top=top-1 22. 先进后出 23. 栈顶指针 24. top==max 25. top!=nil

26. (n+r-f)mod n 27. 前一个 28. 队首 29. n

30. lq->front==lq->rear 31. 栈顶指针 32. 队尾

三、判断题

1．栈和队列都是限制存取点的线性结构。（ ） 2．不同的入栈和出栈组合可能得到相同输出序列。（ ） 3．消除递归一定要用栈。（ ） 4．循环队列是顺序存储结构。（ ） 5．循环队列不会产生溢出。（ ） 6．循环队列满的时候rear= =front。（ ）

7．在对链队列（带头结点）做出队操作时不会改变front指针的值。（）

1. 正确。

2. 错误：不同的入栈和出栈组合得到不同输出序列。 3. 错误：某些情况如尾递归可以转换为递推的形式。 4. 正确。

5. 错误：循环队列不会产生假溢出。 6. 错误。 7. 正确。

四、综合题

1．设有4个元素A、B、C和D进栈，给出它们所有可能的出栈秩序。 可能的出栈序列：（共14个）

ABCD ABDC ACBD ACDB ADCB BACD BADC BCAD BCDA BDCA CBAD CBDA CDBA DCBA

不可能的出栈序列：（共10个） ADBC BDAC

CABD CADB CDAB

DABC DACB DBAC DBCA DCAB

习题四

一、选择项

l．空串与空格串（ ）。

A．相同 B．不相同 C．可能相同 D．无法确定 2．设有两个申S1与S2，求串S2在S1中首次出现位置的运算称作（ ）。 A．连接 B．求子串 C．模式匹配 D．判子串 3．串与普通的线性表相比较，它的特殊性体现在（ ）。 A．顺序的存储结构 B．链接的存储结构 C．数据元素是一个字符 D．数据元素可以任意 4．设有串S=‘Computer’，则其子串的数目是（ ）。

A．36 B．37 C．8 D．9 1. B 2. C 3. C 4. B

二、境空题

1．串是由零个或多个字符组成的____________。通常记作：s＝“c1，c2，?，cn”(n=>0)，其中，S称为________；串中的Ci（1<=i<=n）可以是字母、数字 字格或其他字符。用双引号括起来的部分是_________．即串S的内容。

2．串中字符的个数称为串的________。

3．不含有任何字符的串称为_________，它的长度为___________。

4．由一个或多个空格构成的串称为____________，它的长度为___________。

5．串中任意多个连续字符组成的子序列称为该串的____________；包含___________的串称为主串。

6．字符在序列中的序号称为该字符在串中的________________。

7．两个字符串相等是指两个字符串的，也就是说这两个字符串不仅__________，而且对应位置上的字符也。

8．两个串的比较实际上是_________的比较。两个串从第一个位置上的字符开始进行比较，当第一次出现_____________大的串为大，若比较过程中出现一个字符串结束的情况，则另一个串为_________________。

9．串的_______________就是把串所包含的字符序列，依次存人连续的存储单元中去。 10．有些计算机系统中为了充分利用存储空间，允许一个存储单元可以存放多个字 符，串的这种存储方式是一种__________________。 11．串的______________是以存储单元为存储单位，一个存储单元中只存放__________。在这种情况下，即使一个存储单元能存放多个字符，这时候也只存放________________。

12．串在非紧缩方式下，串长度的存储是隐式的，__________即串的长度。

13．一些计算机是以字节为存取单位，恰好一个字符占用一个字节，自然形成了每个存储单元存放__________的分配方式，这种方式就是一种__________。这种方式一般不需要存放____________的存储单元，而需要以程序中各变量值所、的字符为结束符。

14．串的链式存储结构是将存储区域分成一系列大小相同的结点，每个结点有两个城：____________域和________域。其中___________域用于存放数据，___________域用于存放下一个结点的指针。

15．子串定位StrIndex (s，t)，也称为_______，是返回串t在s主串中的位置。 1. 有限序列、串名、串值 2. 长度

3. 空串、零

4. 空格串、空格的个数 5. 子串、子串 6. 位置

7. 值相等、长度相等、相等 8. ASCII码、ASCII码、较大者 9. 顺序存储结构 10. 紧缩式存储方式

11. 非紧缩存储方式、一个字符、一个字符 12. 串所占用的存储单元的个数

13. 一个字符、单字节存储方式、串长、不包含 14. 数据、指针、数据、指针 15. 模式匹配

三、判断回

1．子串是主串中字符构成的有限序列。（×）

2．KMP算法的最大特点是指示主串的指针不需要回溯。（ 3．串中的元素只能是字符。（ ） 4．串中的元素只可能是字母。（×） 5．串是一种特殊的线性表。（ ） 6．串中可以包含有空白字符。（ ） 7．串的长度不能为零。（×） 8．两个串相等必有串长度相同。（ ） 9．两个串相等则各位置上字符必须对应相等。（ ）

）

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构习题集包含答案(3)在线全文阅读。