数据结构第3章作业参考答案.pdf

《数据结构第3章作业参考答案.pdf》由会员分享，可在线阅读，更多相关《数据结构第3章作业参考答案.pdf（8页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、 第三章 特殊线性表 一、栈 一、单项选择题 1.六个元素按 6、5、4、3、2、1 的顺序进栈，则（B）不是合法的出栈序列。A.4 5 3 1 2 6 B.3 4 6 5 2 1 C.5 4 3 6 1 2 D.2 3 4 1 5 6 2.一个栈的入栈序列是 a、b、c、d、e，则栈的输出序列不可能是（A）。A.dceab B.decba C.edcba D.abcde 3.若进栈序列为 1,2,3,4，则不可能得到的出栈序列是（D）。A.3,2,1,4 B.3,2,4,1 C.2,3,4,1 D.4,2,3,1 4.设 n 个元素进栈序列是 1，2，3，n，其输出序列是 P1，P2，Pn，

2、若 P1=3，则P2 可能的值是（A ）。A.可能是 2 B.一定是 2 C.可能是 1 D.一定是 1 5.设有一顺序栈，元素 a、b、c、d、e、f 依次进栈，若 6 个元素出栈的顺序是 b、d、c、f、e、a，则栈的容量至少应该是（B）。A.2 B.3 C.5 D.6 6.设已将元素 a1、a2、a3依次入栈，元素 a4正等待入栈。那么下列 4 个序列中不可能出现的出栈序列是（A）。A.a3、a1、a4、a2 B.a3、a2、a4、a1 C.a3、a4、a2、a1 D.a4、a3、a2、a1 7.设计一个判别表达式中左、右括号是否配对出现的算法，采用（B）数据结构最佳。A.线性表的顺序存

3、储结构 B.栈 C.线性表的链式存储结构 D.队列 8.一个栈的输入序列为 1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（A）。A.5 4 1 3 2 B.2 3 4 1 5 C.2 3 1 4 5 D.1 5 4 3 2 9.设输入序列为 1，2，3，4，5，6，借助于一个栈若得到的输出序列为 2，3，4，6，5，1，则栈的最小深度为（B ）A.6 B.3 C.5 D.4 二、判断题 1.栈是限定仅在表尾进行插入和删除操作的线性表。对 2.若一个栈的输入序列为 1,2,3，则 3,1,2 是不可能的栈输出序列。对 3.栈是可以在表尾和表头进行插入和删除操作的线性表。错 4.任何一

4、个递归过程都可以转换为非递归过程。错 三、程序填空题 1.以下程序是顺序栈的求栈长、取栈顶、判栈空算法，请填空。/*顺序栈存储结构*/#define INITSIZE 100 /*存储空间的初始分配量*/typedef int ElemType;typedef struct int top;ElemType*base;int stacksize;sqstack;/*求栈长操作*/int getlen(sqstack*S)return();/*取栈顶元素操作*/int gettop(sqstack*S,e)if()return 0;*e=S-base ;return 1;/*取栈顶元素*/*判栈

5、空操作*/emptystack(sqstack*S)return();参考答案：S-top ElemType*S-top=0 S-top-1 S-top=0？1:0 2.以下程序分别是顺序栈的入栈和出栈操作，请填空。#define INITSIZE 100 /*存储空间的初始分配量*/typedef int ElemType;/*数据元素类型*/typedef struct int top;/*栈顶指针，初始 top=0*/ElemType*base;/*存储空间基地址*/int stacksize;/*栈总存储空间大小*/sqstack;int push(sqstack*S,ElemType

6、 x)if(S-top=S-stacksize)S-base=(ElemType*)realloc(,(S-stacksize+1)*sizeof(ElemType);if(!S-base)return 0;return 1;int pop(sqstack*S,e)if(S-top=0)/*栈空*/return 0;return 1;参考答案：S-base S-stacksize+S-baseS-top+=x ElemType*e=S-base-S-top 3.已知压栈函数 int push(sqstack*S,ElemType x)，弹栈函数 int pop(sqstack*S,ElemTy

7、pe*e)，初始化栈函数 void initstack(sqstack*S)，判栈空函数 int empty(sqstack*S)。以下算法是将任意一个十进制整数 m 转换为 n（92 n）进制数输出，请填空。converse(,int n)int e;sqstack S;while(m!=0);while(!empty(*S);printf(%d,e);参考答案：int m initstack(&S)push(&S,m%n)m=m/n pop(&S,&e)二、队列 一、单项选择题 1.在一个链队列中，假定 front 和 rear 分别为队首指针和队尾指针，则进行插入 s 所指向结点的操作是

8、（A）。A.rear-next=s;rear=s;B.front=front-next;C.front-next=s;front=s;D.front=rear-next;2.循环队列的长度计算公式为（B）。A.rear-front B.(rear-front+MAXSIZE)%M AXSIZE C.front-rear D.(front-rear+MAXSIZE)%M AXSIZE 3.设栈 S 和队列 Q 的初始状态为空，元素 e1，e2，e3，e4，e5 和 e6 依次通过栈 S，一个元素出栈后即进队列 Q，若 6 个元素出队的序列是 e2，e4，e3，e6，e5，e1，则栈 S的容量至少

9、应该是（B）。A.2 B.3 C.4 D.6 4.栈和队列都是（B）。A.顺序存储的线性结构 B.限制存取点的线性结构 C.链接存储的线性结构 D.限制存取点的非线性结构 5.栈和队列共同的特点是（D）。A.先进先出 B.先进后出 C.后进先出 D.仅在表的一端进行插入、删除操作 6.若用一个大小为 m 的数组来实现循环队列，用 front 和 rear 分别表示队头和队尾，则当前队列中的元素数是（C）。A.rear-front-1 B.rear-front+1 C.(rear-front+m)%m D.rear-front 7.若用一个大小为 6 的数组来实现循环队列，队头指针 front

10、指向队头元素，队尾指针rear 指向队尾元素的下一个位置。若当前 rear 和 front 的值分别为 0 和 3，当从队列中删除两个元素，再加入两个元素后，rear 和 front 的值分别为（B）。A.1 和 5 B.2 和 5 C.4 和 2 D.5 和 1 8.若循环队列的队头指针为 front，队尾指针为 rear，则队长的计算公式为（D）。A.rear-front B.front-rear C.rear-front+1 D.都不正确 9.某线性表中最常用的操作是在最后一个元素之后插入一个元素及删除第 1 个元素，则采用以下哪种存储方式最节省操作时间(B)。A.单链表 B.队列 C.

11、双链表 D.栈 二、判断题 1、顺序队列的“假溢出”现象是可以解决的。对 2、区分循环队列的满与空，有牺牲一个存储单元和设标记两种方法。对 3、引入循环队列的目的是为了克服假溢出时大量移动数据元素。对 4、循环队列也存在空间溢出的问题。对 5、队列的特点是先进不一定先出。错 三、程序填空题 1、以下是循环队列的出队和判队空操作，请填空。#define MAXCSIZE 100 /*队列存储空间大小*/typedef int ElemType;typedef struct ElemType*base;/*队列存储空间基地址*/int front;/*队头指针*/int rear;/*队尾指针*/

12、cqueue;int outqueue(cqueue*cq,x)/*出队列*/if()return(0);/*失败，返回 0*/*x=;cq-front=;return(1);/*成功，返回 1*/int empty(cqueue*cq)return()；参考答案：ElemType*cq-rear=cq-front cq-basecq-front (cq-front+1)%MAXCSIZE cq-front=cq-rear?1:0 2.下面是循环队列的判队空和取队头元素操作的算法，请填空。#define MAXCSIZE 100 typedef int ElemType;typedef str

13、uct ElemType*base;/*基址*/int front;/*队头指针,指示队头元素*/rear;/*队尾指针，指示队尾元素后一位置*/cqueue;int empty(cqueue*cq)/*队空返回 1，否则返回 0*/return ;int getfront(cqueue*cq,x)/*取队头操作，成功返回 1，失败返回 0*/if()return 0;else *x=;return 1;参考答案：int cq-front=cq-rear?1:0 ElemType*cq-front=cq-rear cq-basecq-front 3.以下是循环队列的类型定义及入队算法，请将空缺

14、补充完整。#define MAXCSIZE 100 typedef int ElemType;Typedef struct ElemType*base;/*基址*/int front;/*队头指针,指示队头元素*/int rear;/*队尾指针，指示队尾元素后一位置*/cqueue;int enqueue(cq,ElemType x)/*入队列*/if(cq-front=)return(0);cq-base =;cq-rear=;return(1);参考答案：cqueue*(cq-rear+1)%MAXCSIZE cq-rear x(cq-rear+1)%MAXCSIZE 4.如果希望循环队列

15、中的向量单元都能得到利用，则可设置一个标志域 tag，每当尾指针和头指针值相同时，以 tag 的值为 0 或 1 来区分队列状态是“空”还是“满”。请对下列函数填空，使其分别实现与此结构相应的入队和出队的算法。#define MAXCSIZE 100 typedef int ElemType;typedef struct ElemType*base;/*队列元素基地址*/int front;/*队头指针*/int rear;/*队尾指针*/cqueue;int tag;/*标志域*/int enqueue(cqueue*q,ElemType x)if()return 0;q-dataq-rea

16、r=x;q-rear=;if(q-rear=q-front);return 1;int dequeue(cqueue*q,ElemType*x)if(q-rear=q-front&tag=0)return 0;*x=q-dataq-front;q-front=;if(q-rear=q-front);return 1;参考答案：q-rear=q-front&tag=1 (q-rear+1)%MAXCSIZE tag=1(q-front+1)%MAXCSIZE tag=0 三、串 一、单项选择题 1.下面关于串的的叙述中，（D）是不正确的。A.串是字符的有限序列 B.串既可以采用顺序存储，也可以采

17、用链式存储 C.模式匹配是串的一种重要运算 D.空串是由空格构成的串 2.串是一种特殊的线性表，其特殊性体现在（D）。A.可以顺序存储 B.数据元素可以是一个字符 C.可以链式存储 D.数据元素可以是多个字符 3.串是（B ）。A.一些符号构成的序列 B.任意有限个字符构成的序列 C.一些字母构成的序列 D.一个以上的字符构成的序列 4.设有两个串 p 和 q，其中 q 是 p 的子串，求 q 在 p 中首次出现的位置的算法称为（C）。A.求子串 B.串联接 C.模式匹配 D.求串长 5.串的长度是指（B ）A串中所含不同字母的个数 B串中所含字符的个数 C串中所含不同字符的个数 D串中所含非空格字符的个数 二、判断题 1.串是一种特殊的线性结构，因此它的基本操作与线性表的基本操作相同。错 2.如果两个串中含有相同的字符，则这两个串相等。错 3.串是一种数据对象和操作都特殊的线性表。对