数据结构考试题库含答案(7)

（1）、abcde（1分）

（2）、不可能，因为：d是第一出栈字符，说明a,b已别压入栈内；并且压入栈的次序为abcde；由以上得出：ab出栈的顺序只能是b、a，而不是a、b。所以，出栈序列d,c,e,a,b是不可能的。（2分） （3）、（2分）

push (a)，pop (a) push (b)，pop (b) push (c)，pop (c) push (d)，pop (d) push (e)，pop (e)

4. 简述栈和队列的异同点。

相同点：栈和队列都是只允许在表的端点处进行插入、删除操作的线性表。（2分） 不同点：栈的特点是先进后出，队列的特点是后进先出。（3分）

5. 若依次读入数据元素序列1、2、3，进栈的过程中允许出栈，试写出各种可

能的出栈序列。

答:123、132、213、231、321（各1分）

6. 如果入栈序列有ＡＢＣ组成, 请问输出序列可能有哪些? (较难)

输出序列有5种：

C B A, B C A, B A C, A C B , A B C（各1分）

7. 如果有abcde五个数据依次全部存入，如果采用队列和栈来进行存储，依次

取出分别将获得什么内容。（简单）

队列：abcde （2.5分） 栈: edcba （2.5分）

8. 设将整数 1，2，3，4依次进栈，能否得到1423出栈序列和1432?并说明为什么不能得到或者如何得到。（中等）

不能得到1423，但可以得到1432（2分）

因为要得到4必须将所有数据入栈，这样将只能依次获取到1432不能获得1423。采用push、pop、push、push、push、pop、pop、pop可以获得1432。（3分）

9. 循环队列的优点是什么？如何判断它的空和满？(可不考)

循环队列的优点是可以克服顺序队列的\假上溢\现象，能够使存储队列的向量空间得到

充分的利用。（3分）采用牺牲一个元素空间的方法，循环队列队空的条件是front==rear，循环队列队满的条件是：(rear+1)%M==front。（2分）

第四章 串

1. 对于字符串S=’abcde’，请问：（简单）

（1）字符串S的长度是多少？

（2）字符串S的子串有几个，并列出所有子串？ 答： （1）、5 （1分） （2）、16，（1分）所有字串：’a’、’b’、’c’、’d’、’e’、 ’ab’、 ’ bc’、 ’ cd’ 、’de’、’abc’、

’ bcd’、 ’cde’、 ’abcd’、 ’bcde’、 ’abcde’、Φ。（3分）

2. 对于字符串S=’12345’，请问：（简单）

（1）字符串S的长度是多少？

（2）字符串S的子串有几个，并列出所有子串？ 答： （1）、5 （1分） （2）、16，（1分）所有字串：’1’、’2’、’3’、’4’、’5’、 ’12’、 ’ 23’、 ’ 34’ 、’45’、’123’、

’ 234’、 ’345’、 ’1234’、 ’2345’、 ’12345’、Φ。（3分）

3. 请问答：什么串的模式匹配？模式匹配算法有几种？（简单）

答：串的模式匹配是指子串的定位运算，即在主串中查找子串第一次出现的位置。 模式匹配算法有两种：简单匹配算法(Brute-Force)、KMP算法。

（该题共4个得分点，答对串匹配定义或大意基本相同，得 2 分；答对两种匹配算，得 2 分，答错或少答一个 扣 1分）

第五章 数组和广义表

1. 在数据结构中，数组是最基本的结构，请完成以下要求：

（1）、定义一个能容纳5个整型元素的数组iAry，且元素的值为10、20、30、40、50 。（2）、*画出数组iAry的顺序存储结构。（规定：整型长度为两个字节） （1）、int iAry[5]={ 10、20、30、40、50 } （2 分） （2）、如下图：（3分，根据情况，酌情扣分）

2. 简述数组的定义、特点和分类。（简单）

定义：数组是n个相同数据类型的数据元素a0,a1,a2,...,an-1构成的有限集合。（1个得分点） 特点：

1）数组中各元素具有统一的类型；（1个得分点）

2）数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。（1个得分点）

3数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。 （1个得分点）

分类：按维度可分为一维数组、二维数组、多维数组（1个得分点）

3. 已知一个二维数组A如下所示。（较难）

（1）请按照行优先、列优先的方式进行顺序存储，给出顺序存储的序列（2个得分点） 行优先：a11a12a13a21a22a23 列优先：a11a21a12a22a13a23

（2）若a11在内存中存储的地址为α，每个元素的存储空间大小为L，则按照行优先的方式和列优先的方式分别存储，其中a22的地址loc(a22)分别为多少（2个得分点）

行优先：loc(a22)=α+4L 列优先：loc(a22)=α+3L