数据结构习题及答案(3)

有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D ，变量T的值是 E 。 供选择的答案：

A： ① 先进先出 ②后进先出 ③进优于出

④出优于进 ⑤ 随机进出

B，C： ① 加1 ②减1 ③不变 ④清0 ⑤ 加2 ⑥减2 D：① a,b ②b,c ③c,a

④b,a ⑤ c,b ⑥ a,c

④ n-1 ⑤ n-2

E：① n+1 ②n+2 ③ n 答案：ABCDE=2, 2, 1, 6, 4

注意，向地址的高端生长，称为向上生成堆栈；向地址低端生长叫向下生成堆栈，本题中底部为n，向地址的低端递减生成，称为向下生成堆栈。

8. 【91初程P77】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

在做进栈运算时，应先判别栈是否 A ；在做退栈运算时，应先判别栈是否 B 。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为 C 。

为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 D 分别设在这片内存空间的两端，这样，只有当 E 时，才产生上溢。 供选择的答案：

A，B：①空 ② 满 ③ 上溢 ④ 下溢 C： ①n-1 ② n ③ n+1 ④ n/2 D： ① 长度 ②深度 ③ 栈顶 ④ 栈底

E：①两个栈的栈顶同时到达 栈空间的中心点 ②其中一个栈的栈顶到达栈空间的中心点 ③两个栈的栈顶在达栈空间的某一位置相遇 ④两个栈均不空，且一个栈的栈顶到达另一个栈的栈底

答案：ABCDE＝2, 1, 2, 4, 3 四、简答题（每小题4分，共20分） 1.说明线性表、栈与队的异同点。

刘答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。

不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，

因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。

② 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。

2.设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。 刘答：至少有14种。

① 全进之后再出情况，只有1种：4，3，2，1

② 进3个之后再出的情况，有3种，3,4,2,1 3,2,4,1 3,2,1,4

③ 进2个之后再出的情况，有5种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 ④ 进1个之后再出的情况，有5种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3

3. 【刘自编】假设正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’ 和‘ababab’则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？

答：线性表是随机存储，可以实现，靠循环变量（j--）从表尾开始打印输出；

堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可； 队列是先进先出，不易实现。

哪种方式最好，要具体情况具体分析。若正文在机内已是顺序存储，则直接用线性表从后往前读取即可，或将堆栈栈顶开到数组末尾，然后直接用POP动作实现。（但堆栈是先减后压还是??）

若正文是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全部压入后再依次输出。

4. 【统考书P60 4-13】顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？ 答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。 采用循环队列是解决假溢出的途径。 另外，解决队满队空的办法有三：

① 设置一个布尔变量以区别队满还是队空； ② 浪费一个元素的空间，用于区别队满还是队空。

③ 使用一个计数器记录队列中元素个数（即队列长度）。

我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。 判断循环队列队空标志是： f=rear 队满标志是：f=(r+1)%N

5. 【统考书P60 4-14】设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有

① front=11，rear=19; ② front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？

答：用队列长度计算公式： (N＋r－f)% N

① L=（40＋19－11）% 40=8 ② L=（40＋11－19）% 40=32 五、阅读理解（每小题5分，共20分）

1. 按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，并仿照教材例3-2的格式，画出对下

列算术表达式求值时操作数栈和运算符栈的变化过程：

A－B×C/D+E↑F

2. 写出下列程序段的输出结果（栈的元素类型SElem Type为char）。 void main( ){

Pop(S,x); Push(S,’t’); Push(S,x); Stack S;

Pop(S,x); Push(S,’s’); Char x,y;

while(!StackEmpty(S)){ Pop(S,y);printf(y); }; InitStack(S);

Printf(x); X=’c’;y=’k’;

} Push(S,x); Push(S,’a’); Push(S,y);

3. 写出下列程序段的输出结果（队列中的元素

类型QElem Type为char）。 void main( ){

Queue Q; Init Queue (Q); Char x=’e’; y=’c’;

EnQueue (Q,’h’); EnQueue (Q,’r’); EnQueue (Q,’y’); DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,’a’);

while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y); }; Printf(x); }

4. 简述以下算法的功能（栈和队列的元素类型均为int）。 void algo3(Queue &Q){ Stack S; int d; InitStack(S);

while(!QueueEmpty(Q)){ DeQueue (Q,d); Push(S,d); };

while(!StackEmpty(S)){ Pop(S,d); EnQueue (Q,d); } }

六、算法设计（每小题5分，共15分。至少要写出思路）

1. 假设一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧，编写一个判别表达式中括弧是

否正确配对的函数correct(exp,tag)；其中：exp为字符串类型的变量（可理解为每个字符占用一个数组元素），表示被判别的表达式，tag为布尔型变量。

#define m0 100 /*m0为算术表达式中最多字符个数*/ correct(exp,tag) char exp[m0]; int tag;

{char st[m0]; int top=0, i=1; tag=1;

while (i<=m0 && tag)

{if (exp[i]= = ?(?||exp[i]= =?[?||exp[i]= =?{?） /*遇到?(?、?[?或?{?，则将其入栈*/ {top++;

st[top]=exp[i]; }

if (exp[i]= =?)? ) /*遇到?)? ，若栈顶是?(?，则继续处理，否则以不配对返回*/ if(st[top]= =?(? ) top--; else tag=0;

if (exp[i]= =? )? ) /*遇到? ]? ，若栈顶是?[?，则继续处理，否则以不配对返回*/ if(st[top]= =?[ ?] top--; else tag=0;

if (exp[i]= =?)? ) /*遇到? }? ，若栈顶是?{?，则继续处理，否则以不配对返回*/ if(st[top]= =?{? top--; else tag=0; i++; }

if(top>0)tag=0; /*若栈不空，则不配对*/ }

2. 假设一个数组squ[m]存放循环队列的元素。若要使这m个分量都得到利用，则需另一个标志tag，以tag为0或1来区分尾指针和头指针值相同时队列的状态是“空”还是“满”。试编写相应的入队和出队的算法。

3. 试写一个算法，判别读入的一个以‘@’为结束符的字符序列是否是“回文”。

第4～5章 串和数组

一、填空题（每空1分，共20分）

1. 不包含任何字符（长度为0）的串 称为空串； 由一个或多个空格（仅由空格符）组成的串 称为空白串。（对应严题集4.1①，简答题：简述空串和空格串的区别） 2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 , “/”的字符定位的位置为 3 。

4. 子串的定位运算称为串的模式匹配； 被匹配的主串 称为目标串， 子串 称为模式。

5. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6 次匹配成功。

6. 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为 (n-m+1)*m 。

7. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 288 B ；末尾元素A57的第一个字节地址为 1282 ；若按行存储时，元素A14的第一个字节地址为 (8+4)×6+1000=1072 ；若按列存储时，元素A47的第一个字节地址为 (6×7＋4)×6＋1000）＝1276 。

(注：数组是从0行0列还是从1行1列计算起呢？由末单元为A57可知，是从0行0列开始！) 8. 〖00年计算机系考研题〗设数组a[1?60, 1?70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为 8950 。

答：不考虑0行0列，利用列优先公式： LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L 得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝8950

9. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素

的 行下标 、 列下标 和 元素值 。 10.求下列广义表操作的结果：

（1） GetHead【((a,b),(c,d))】=== (a, b) ; //头元素不必加括号 （2） GetHead【GetTail【((a,b),(c,d))】】=== (c,d) ; （3） GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== b ; （4） GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== （d） ; 二、单选题（每小题1分，共15分）

（ B ）1. 〖李〗串是一种特殊的线性表，其特殊性体现在：

Ａ．可以顺序存储 Ｂ．数据元素是一个字符 Ｃ．可以链式存储 Ｄ．数据元素可以是多个字符

（ B ）2. 〖李〗设有两个串p和q，求q在p中首次出现的位置的运算称作：

Ａ．连接 Ｂ．模式匹配 Ｃ．求子串 Ｄ．求串长

（ D ）3. 〖李〗设串s1=?ABCDEFG?，s2=?PQRST?，函数con(x,y)返回x和y串的连接串，

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