数据结构练习题及答案

A.必须一致 B.不能一致 C.可以不一致 D.不限制 4. 队列是一个（C）线性表结构。

A.不加限制的 B.推广了的 C.加了限制的 D.非 5. 当利用大小为n的数组顺序存储一个队列时，该队列的最后一个元素的下标为（B）。

A.n-2 B.n-1 C.n D.n+1 6. 一个循环队列一旦说明，其占用空间的大小（A）。

A.已固定 B.可以变动 C.不能固定 D.动态变化 7. 循环队列占用的空间（A）。

A.必须连续 B.不必连续 C.不能连续 D.可以不连续 8. 存放循环队列元素的数组data有10个元素，则data数组的下标范围是（B）。

A.0～10 B.0～9 C.1～9 D.1～10 9. 若进队的序列为A、B、C、D，则出队的序列是（C）。

A.B、C、D、A B.A、C、B、D C.A、B、C、D D.C、B、D、A 10. 4个元素按A、B、C、D顺序连续进队Q，则队尾元素是（D）

A．A B．B C．C D．D

11. 4个元素按A、B、C、D顺序连续进队Q，执行一次QutQueue(Q)操作后，队头元素是（B）。 A.A B.B C.C D.D

12. 4个元素按A、B、C、D顺序连续进队Q，执行4次QutQueue(Q)操作后，再执行QEmpty(Q)；后的值

是（B）。 A.0 B.1 C.2 D.3 13. 队列Q，经过下列运算后，x的值是（B）。InitQueue(Q)(初始化队列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)；ReadFront(Q,x)；

A.a B.b C.0 D.1 14. 循环队列SQ队满的条件是（B）。

A.SQ->rear= =SQ->front B.(SQ->rear+1)%MAXLEN= =SQ->front

C.SQ->rear= =0 D.SQ->front= =0

15. 设链栈中结点的结构：data为数据域，next为指针域，且top是栈顶指针，若想在链栈的栈顶插入

一个由指针s所指的结点，则应执行下列（A）操作。

A.s->next=top->next;top->next=s; B.top->next=s;

C.s->next=top;top->next; D.s->next=top;top=s; 16. 带头结点的链队LQ示意图如下，链队列的队头元素是（A）。

LQ->front H A B C D ∧ LQ->rear A．A B．B C．C D．D 17. 带头结点的链队列LQ示意图如下，指向链队列的队头指针是（C）。 LQ->front H A B C D ∧ 9

LQ->rear

A.LQ->front B.LQ->rear C.LQ->front->next D.LQ->rear->next 18. 带头结点的链队列LQ示意图如下,在进行进队的运算时指针LQ->frnot(A). LQ->front H A B C D ∧ LQ->rear

A.始终不改变 B.有时改变 C.进队时改变 D.出队时改变 19.队列Q，经过下列运算后，再执行QEmpty(Q)的值是（C）。

InitQueue(Q)(初始化队列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)；ReadQueue(Q,x)； A.a B.b C.0 D.1

20.若用一个大小为6数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为（B）。

A.5和1 B.4和2 C.2和4 D.1和5

10

第5章 串

一、判断题

1. 串是n个字母的有限序列。 （×） 2. 串的数据元素是一个字符。 （√） 3. 串的长度是指串中不同字符的个数。 （×） 4. 如果两个串含有相同的字符，则说明它们相等。 （×） 5. 如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。 （×） 6. 串的堆分配存储是一种动态存储结构。 （√） 7. “DT”是“DATA”的子串。 （×） 8. 串中任意个字符组成的子序列称为该串的子串。 （×） 9. 子串的定位运算称为模式匹配。 （√） 10. 在链串中为了提高存储密度，应该增大结点的大小。 （√） 二、填空题

1. 由零个或多个字符组成的有限序列称为 字符串（或串） 。 2. 字符串按存储方式可以分为顺序存储、链接存储和 堆分配存储 。 3. 串的顺序存储结构简称为 顺序串 。

4. 串顺序存储非紧凑格式的缺点是 空间利用率低 。

5. 串顺序存储紧凑格式的缺点是对串的字符处理 效率低 。

6. 串链接存储的优点是插入、删除方便，缺点是 空间利用率 。 7. 在C或C++语言中，以字符 \\0 表示串值的终结。 8. 空格串的长度等于 空格的个数 。

9. 在空串和空格串中，长度不为0的是 空格串 。

10. 两个串相等是指两个串长度相等，且对应位置的 字符都相同 。 11. 设“S=My Music”，则LenStr(s)= 8 。 12. 两个字符串分别为；S1=”Today is”、S2=”30 July，2005”，ConcatStr(S1，S2)的结果是 Today is 30 July,2005 。

13. 求子串函数SubStr(“Today is 30 July，2005”，13，4)的结果是 July 。 14. 在串的运算中，EqualStr(aaa,aab)的返回值 <0 。 15. 在串的运算中，EqualStr(aaa,aaa)的返回值 0 。

16. 在子串的定位运算中，被匹配的主串称为目标串，子串称为 模式 。 17. 模式匹配成功的起始位置称为 有效位移 。

18. 设S=”abccdcdccbaa”，T=”cdcc”，则第 6 次匹配成功。

19. 设S=”c:/mydocument/text1.doc”，T=”mydont”，则字符定位的位置为 0 。

20. 若n为主串长度，m为子串长度，n>>m，则模式匹配算法最坏情况下的时间复杂度为 (n-m+1)*m 。 三、选择题

1. 串是和种特殊的线性表，其特殊体现在（B）。

A．可能顺序存储 B．数据元素是一个字符C．可以链接存储 D．数据元素可以是多个字符 2. 某串的长度小于一常数，则采用（B）存储方式最节省空间。

A．链式 B．顺序 C．堆结构 D．无法确定 3. 以下论述正确的是（C）。

A．空串与空格串是相同的B．”tel”是”Teleptone”的子串 C．空串是零个字符的串 D．空串的长度等于1 4. 以下论述正确的是（B）。

A．空串与空格串是相同的B．”ton”是”Teleptone”的子串

11

C．空格串是有空格的串 D．空串的长度等于1

5. 以下论断正确的是（A）。

A．全部由空格组成的串是空格串 B．”BEUIJING”是”BEI JING”的子串 C．”something”<”Something” D．”BIT”=”BITE” 6. 设有两个串S1和S2，则EqualStr（S1，S2）运算称作（D）。 A．串连接 B．模式匹配 C．求子串 D．串比较 7. 串的模式匹配是指（D）。

A．判断两个串是否相等 B．对两个串比较大小

C．找某字符在主串中第一次出现的位置D．找某子串在主串中第一次出现的第一个字符位置 8. 若字符串”ABCDEFG”采用链式存储，假设每个字符占用1个字节，每个指针占用2个字节。则该字

符串的存储密度为（D）。

A．20% B．40% C．50% D．33.3%

9. 若字符串”ABCDEFG”采用链式存储，假设每个指针占用2个字节，若希望存储密度为50%，则每个结点应存储（A）个字符。 A.2 B.3 C.4 D.5 10. 设串S1=”IAM”，S2=”A SDUDENT”，则ConcatStr(S1，S2)=（B）。

A．”I AM” B.”I AM A SDUDENT” C.”IAMASDUDENT” D.”A SDUDENT” 11. 设S=””，则LenStr(S)=（A）。

A.0 B.1 C.2 D.3 12. 设目标串T=”AABBCCDDE”，模式P=”ABCDE”，则该模式匹配的有效位移为（A）。

A.0 B.1 C.2 D.3

13. 设目标串T=”AABBCCDDEEFF”，模式P=”CCD”，则该模式匹配的有效位移为（D）。

A.2 B.3 C.4 D.5

14. 设目标串T=”aabaababaabaa”，模式P=”abab”，模式匹配算法的外层循环进行了（D）次。

A.1 B.9 C.4 D.5 15. 模式匹配算法在最坏情况下的时间复杂是（D）。

A.O(m) B.O(n) C.O(m+n) D.O(m×n)

16. S=”morning”,执行求子串函数SubSur(S,2,2)后结果为（B）。

A. ”mo” B. ”or” C. ”in” D. ”ng” 17. S1=”good”，S2”morning”，执行串连接函数ConcatStr(S1，S2)后结果为（A）。 A. ”goodmorning” B. ”good morning” C. ”GOODMORNING” D. ”GOODMORNING” 18. S1=”good”, S2=”morning”执行函数SubSur(S2,4,LenStr(S1))后的结果为（B）。 A.”good” B.”ning” C.”go” D.”morn” 19. 设串S1=”ABCDEFG”，S2=”PQRST”，则ConcatStr（SubStr(S1，2，LenStr（S2）），SubStr(S1，LenStr

（S2），2））的结果串为（D）。

A. BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF 20. 若串S=”SOFTWARE”，其子串的数目最多是（C）。

A．35 B.36 C.37 D.38

12