单元练习3
一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ）
）（1）栈是运算受限制的线性表。
）（2）在栈空的情况下，不能作出栈操作，否则产生下溢出。
）（3）栈一定是顺序存储的线性结构。
）（4）栈的特点是“后进先出”。
）（5）空栈就是所有元素都为0的栈。
）（6）在c或c++语言中设顺序栈的长度为maxlen，则top=maxlen时表示队满。
）（7）链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。
）（8）一个栈的输入序列为：a，b，c，d，可以得到输出序列：c，a，b，d。
二．填空题。
1）在栈结构中，允许插入、删除的一端称为 。
2）在顺序栈中，当栈顶指针top=-1时，表示 。
3）在有n个元素的栈中，进栈操作的时间复杂度为 。
4）在栈中，出栈操作的时间复杂度为。
5）在一个链栈中，若栈顶指针等于null，则表示 。
6）向一个栈顶指针为top的链栈插入一个新结点*p时，应执行和top=p； 操作。
7）顺序栈s存储在数组 s->data[0..maxlen-1]中，进栈操作时要执行的语句有：
s->top
8）链栈ls，指向栈顶元素的指针是。
9）从一个栈删除元素时，首先取出然后再移动栈顶指针。
10）由于链栈的操作只在链表的头部进行，所以没有必要设置结点。
11）已知顺序栈s，在对s进行进栈操作之前首先要判断。
12）已知顺序栈s，在对s进行出栈操作之前首先要判断。
13）若内存空间充足， 栈可以不定义栈满运算。
14）链栈ls是空的条件是 。
15）链栈ls的栈顶元素是链表的元素。
16）同一栈的各元素的类型。
17）若进栈的次序是a、b、c、d、e，执行三次出栈操作以后，栈顶元素为。
18）四个元素按a、b、c、d顺序进s栈，执行两次pop（s，x）运算后，x的值是 。
三．选择题。
1）插入和删除只能在一端进行的线性表，称为( )
a．队列 b．循环队列 c．栈 d．循环栈
2）设有编号为1，2，3，4的四辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为 (
a．1234 b．1243 c．1324 d．1423
3）如果以链表作为栈的存储结构，则出栈操作时（ ）
a．必须判别栈是否满 b．必须判别栈是否空。
c．必须判别栈元素类型 d．队栈可不做任何判别。
4）元素a,b,c,d依次进栈以后，栈顶元素是（ ）
a．a b．bc．cd．d
5）顺序栈存储空间的实现使用（ ）存储栈元素。
a．链表 b．数组 c．循环链表 d．变量。
6）在c或c++语言中，一个顺序栈一旦被声明，其占用空间的大小（ ）
a．已固定 b．不固定 c．可以改变 d．动态变化。
7）带头结点的链栈ls的示意图如下，栈顶元素是（ ）
lsa．a b．bc．cd．d
8）链栈与顺序栈相比，有一个比较明显的优点是（ ）
a．插入操作更加方便b．通常不会出现栈满的情况。
c．不会出现栈空的情况 d．删除操作根加方便。
9）从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列 ( 命令。
a．x=top;top=top->next; b．top=top->next;x=top->data;
c．x=top->datad．x=top->data;top=top->next;
10）在一个栈顶指针为hs的链栈中，将一个s指针所指的结点入栈，应执行下列 ( 命令。
a．hs->next=sb．s->next=hs->next;hs->next=s;
c．s->next=hs->next;hs=s; d．s->next=hs;hs=hs->next;
11）四个元素按a、b、c、d顺序进s栈，执行两次pop（s，x）运算后，栈顶元素的值是（ ）
a．ab．bc．cd．d
12）元素a,b,c,d依次进栈以后，栈底元素是（ ）
a．ab．bc．cd．d
13）经过下列栈的运算后，再执行readtop(s)的值是（ ）
initstack(s) （初始化栈）;push(s,a);push(s,b); pop(s)
a．ab．bc．1d．0
14）经过下列栈的运算后，x的值是（ ）
initstack(s) （初始化栈）;push(s,a);push(s,b); readtop(s);pop(s,x);
a．ab．bc．1d．0
15）经过下列栈的运算后，x的值是（ ）
initstack(s) （初始化栈）;push(s,a);pop(s,x);push(s,b);pop(s,x);
a．ab．bc．1d．0
16）经过下列栈的运算后，sempty(s)的值是（ ）
initstack(s) （初始化栈）; push(s,a); push(s,b);pop(s,x); pop(s,x);
a．ab．bc．1d．0
17）向顺序栈中压入元素时，（
a． 先存入元素，后移动栈顶指针 b．先移动栈顶指针，后存入元素。
c．谁先谁后无关紧要d．同时进行。
18）初始化一个空间大小为5的顺序栈s后，s->top的值是（ ）
a．0b．-1 c．不再改变 d．动态变化。
19）一个栈的入栈次序abcde，则栈的不可能的输出序列是 (
a．edcba b．decbac．dceabd．abcde
20）设有一个顺序栈s，元素a,b,c,d,e,f,依次进栈，如果六个元素出栈的顺序是b，d，c，f，e，a，则栈的容量至少应是 (
a．3b．4c．5d． 6
四．设有一个栈，元素进栈的次序为：a，b，c，d，e，用i表示进栈操作，o表示出栈操作，写出下列出栈的操作序列。
1）c，b，a，d，e
2）a，c，b，e，d
五．算法设计题。
1．设用一维数组stack[n]表示一个堆栈，若堆栈中每个元素需占用m个数组单元（m>1），（1）试写出其入栈操作的算法。
2）试写出其出栈操作的算法。
2．设计一个算法，要求判别一个算术表达式中的圆括号配对是否正确。
《数据结构练习题》栈和队列
栈和队列。1 简述栈和线性表的区别。2 简述栈和队列这两种数据结构的相同点和不同点。3 如果进栈的元素序列为a，b，c，d，则可能得到的出栈序列有多少种？写出全部的可能序列。4 如果进栈的元素序列为1，2，3，4，5，6，能否得到4，3，5，6，1，2和1，3，5，4，2，6的出栈序列？并说明为什么...
数据结构实验数组
crosslist ma int z 主函数 void main creatmatrix ma out m ma main 十字链表的输出 void out m crosslist m printf printf 打回车键，返回。ch getchar void creatmatrix crossli...
数据结构,二维指针和数组 还有数据结构
自己建立头文件格式 include 指针 指针变量 是用来存放变量的存储地址的。p null int a 3 例如 p a 结论 p a p 3 指针变量定义的格式 类型名 指针名。最好采用int p 取值符号 后面加 地址 表示取这个地址里的值。地址符号 后面加 变量 表示取这个变量的地址。voi...
数据结构实验六图
1 掌握图的邻接矩阵和邻接表表示。2 掌握图的深度优先和广度优先搜索方法 3 理解图的应用方法。1 阅读并运行下面程序，根据输入写出运行结果。include define n 20 define true 1 define false 0 int visited n typedef struct 队...
数据结构 习题集
基础篇。习题1 一 选择题。1 计算机算法必须具备输入 输出 b 等5个特性。a 可行性 可移植性和可扩展性b 可行性 确定性和有穷性。c 确定性 有穷性和稳定性d 易读性 安全性和稳定性。2 在数据结构中，从逻辑上可以把数据结构分为 d a 动态结构和静态结构b 紧凑结构和非紧凑结构。c 内容结构...
数据结构实验队列 附程序
实验三队列。一 实验目的。1.了解队列的特性。2.掌握队列的顺序表示和实现。3.掌握队列的链式表示和实现。二 实验内容。实验3.3队列的顺序表示和实现。编写一个程序实现顺序队列的各种基本运算 采用循环队列 并在此基础上设计一个主程序，完成如下功能 1 初始化队列。2 建立顺序队列。3 入队。4 出队...
数据结构作业 线性表
1简述以下算法的功能 1 statusa linkedlistl p next q p q q p next 当相邻元素相等时删除多余元素。else while delete equal void reverse sqlist a 顺序表的就地逆置。for i 1,j reverse void li...