数据结构校本教程课后习题.docx

1.4 总结与提高
1.4.1 主要知识点
（1）数据类型、数据结构等基本概念。
（2）几种基本数据结构的逻辑结构及常用的几种存储结构。
（3）算法的概念、算法的表示、算法的时间性能和空间性能评价方法。
练习题目
一、选择题
1.从逻辑上可以把数据结构分为（ ）两大类。
A. 线性结构、非线性结构 B .初等结构、构造型结构
C. 顺结构、链式结构 D.动态结构、静态结构
2.采用顺序存储结构表示数据时，相邻的数据元素的存储地址（ ）。
A. 一定不连续 B . 一定连续
C. 不一定连续 D. 部分连续，部分不连续
3.在发生非法操作时，算法能够做出适当处理的特性称为（ ）。
A. 健壮性 B . 可读性 C. 正确性 D. 可移植性
4.执行下面程序段的时间复杂度为（ ）。
For(int i=0;i<m;i++)
For(int j=0;j<n;j++) A[i][j]=i*j;
A. O(m2) B . O(n2) C. O(m*n) D. O(m+n)
5.执行下面程序段时，语句S的执行次数为（ ）。
For(int i=0i<=n;i++)
For(int j=0;j<=i;j++) S;
A. n2 B . n2/2 C. n(n+1) D. n(n+1)/2
二、判断题
1.算法就是程序。（ ）
2.算法必须有输入，但可以没有输出。（ ）
3.线性结构只能用顺序结构存储，非线性结构只能用非顺序结构存储。（ ）
4.顺序存储结构的特点是对于插入和删除操作的效率非常高。（ ）
5.算法的优劣与所用计算机的性能有关，与描述算法的语言无关。（ ）
三、简答题
1.简述数据结构的含义。
2.简述算法的时间复杂度。
3.简述数据类型的概念。
4.简述算法和程序的区别
5.常见的逻辑结构有哪些？存储结构有哪些？各自的特点是什么？
实验题目
1．试着写一算法，自大至小依次输出读入的三个整数X,Y和Z的值。

2.5 总结与提高
2.5.1 主要知识点
（1）顺序表和链表存储结构的描述方法。
（2）顺序表的查找、插入和删除算法。
（3）各种链表的查找、插入和删除算法。
2.5.2 典型例题
1．链表不具备的特点是（ ）
A．可随机访问任一结点 B． 插入删除不需要移动元素
C．不必事先估计存储空间 D．所需空间与其长度成正比
2．带头结点的单链表head为空的判定条件是（ ）
A．head= =NULL B．head->next= =NULL
C．head->next= =head D．head!=NULL
3．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（ ）存储方式最节省运算时间。
A．单链表 B．给出表头指针的单循环链表
C．双链表 D．带头结点的双循环链表
4．需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是（ ）
A．单链表 B ．静态链表 C．线性链表 D．顺序存储结构
5．与单链表相比，双链表的优点之一是（ ）
A．插入、删除操作更简单 B． 可以进行随机访问
C．可以省略表头指针或表尾指针 D．顺序访问相邻结点更灵活
6．在一个单链表中的p所指结点之前插入结点s，可执行如下的操作：
s->next= ① ;
p->next=s;
t=p->data;
p->data= ② ;
s->data= ③ ;
练习题目
1.下面是将不带头结点的链表L逆置的程序，请将程序补充完整：
void invert(Node *L)
{Node *p,*q,*r;
p=L;
q=p->next;
while(q!=NULL)
{

p=q; q=r;}
L->next=NULL;
L=p;
}
2.线性表中有n个元素，以下算法中，（ ）在顺序表上实现比在链表上实现效率更高。
A．输出第i(0≤i≤n-1)个元素
B．交换第0个元素与第1个元素的值
C．顺序输出这n个元素的值
D．输出与给定值x相等的元素在线性表中的序号
3.单链表中，增加一个头结点的目的是为了( )。
A．使单链表至少有一个结点 B．标识表结点中首结点的位置
C．方便运算的实现 D．说明单链表是线性表的链式存储
4.在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行（ ）。
A．q->next = p->next ; p->next = q;
B．p->next = q->next; q = p;
C．q->next = p->next; p->next = q;
D．p->next = q->next ; q->next = p;
5.不带头结点的单链表head为空的判定条件是（ ）
A．head= =NULL B．head->next= =NULL
C．head->next= =head D．head!=NULL
6.设p结点是带表头结点的双循环链表中的结点，则在p结点前插入s结点的语句序列中正确的是（ ）
A．p->prior=s;p->prior->next=s;s->prior=p->prior;s->next=p
B．p->prior->next=s;p->prior=s; s->prior=p->prior;s->next=p
C．s->prior=p->prior;p->prior->next; p->prior=s;s->next=p
D．p->prior=s;s->next=p; p->prior->next=s;s->prior=p->prior
7.在一个单链表中删除p所指的结点时，应执行以下操作：
q=p->next;

free(q);
实验题目
1．假设有两个集合 A 和 B 分别用两个线性表 La 和 LB 表示，即：线性表中的数据元素即为集合中的成员，现要求一个新的集合A＝A∪B ，例如A={1,2,3,4}，B ={1,5,6,4,8,9}，则A∪B ={1,2,3,4,5,6,8,9}。

3.3 总结与提高
3.3.1 主要知识点
1. 栈和队列这两种抽象数据类型的特点。
2. 栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算法，判断栈满和栈空的条件以及它们的描述方法。
3. 线性队列和循环队列的基本操作实现算法，判断队满和队空的条件以及它们的描述方法。
4. 递归算法执行过程中栈的状态变化过程。
3.3.2 典型例题
1. 如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和1 3 5 4 2 6，请说明为什么不能或如何才能得到。
输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。
得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。
2. 设从键盘输入一整数的序列：a1, a2, a3，…，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。
#define maxsize //栈空间容量
void InOutS(int s[maxsize]) //s是元素为整数的栈，本算法进行入栈和退栈操作。
{
int top=0; //top为栈顶指针，定义top=0时为栈空。
for(i=1; i<=n; i++) //n个整数序列作处理。
{
scanf(“%d”,&x); //从键盘读入整数序列。
if(x!=-1) // 读入的整数不等于-1时入栈。
if(top==maxsize-1) printf(“栈满\n”);
else s[++top]=x; //x入栈。
else //读入的整数等于-1时退栈。
{
if(top==0) printf(“栈空\n”);
else printf(“出栈元素是%d\n”,s[top--])；
}
}
}
练习题目
一 单选题
1. 对于栈操作数据的原则是（ ）。
A. 先进先出 B . 后进先出 C. 后进后出 D. 不分顺序
2. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）
A. 5 4 3 6 1 2 B . 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6
3. 输入序列为AB C，可以变为CB A时，经过的栈操作为（ ）。
A. push,pop,push,pop,push,pop B . push,push,push,pop,pop,pop
C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop
4. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
A．线性表的顺序存储结构 B . 队列 C. 线性表的链式存储结构 D. 栈
5. 用链接方式存储的队列，在进行删除运算时（ ）。
A. 仅修改头指针 B . 仅修改尾指针
C. 头、尾指针都要修改 D. 头、尾指针可能都要修改
6. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。
A．(rear-front+m)%m B ．rear-front+1
C．(front-rear+m)%m D．(rear-front)%m
7. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )
A. 1和 5 B . 2和4 C. 4和2 D. 5和1
8. 栈和队列的共同点是（ ）。
A. 都是先进先出 B . 都是先进后出
C. 只允许在端点处插入和删除元素 D. 没有共同点
9. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。
A． 6 B . 4 C. 3 D. 2
10. 栈和队列都是（ ）。
A．顺序存储的线性结构 B . 链式存储的非线性结构
C. 限制存取点的线性结构 D. 限制存取点的非线性结构
二、判断题
1. 若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。（ ）
2. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（ ）
3. 队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ）
4. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（ ）
5. 任何一个递归过程都可以转换成非递归过程。（　　）
三、填空题
1．栈是_______的线性表，其运算遵循_______的原则。
2．在作进栈运算时应先判别栈是否_ _;在作退栈运算时应先判别栈是否 _；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_ 。
3. 用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_______。
4. 顺序栈用data[0…n-1]存储数据，栈顶指针是top,则值为x的元素入栈的操作是_______。
5．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_______。
6. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_______。
7．表达式求值是_______应用的一个典型例子。
8．循环队列的引入，目的是为了克服_______。
9. 循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是_______。
实验题目
1、将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长，当向第0号栈插入一个新元素时，使top[0]增1得到新的栈顶位置，当向第1号栈插入一个新元素时，使top[1]减1得到新的栈顶位置。当top[0]+1 == top[1]时或top[0] = top[1]-1时，栈空间满，此时不能再向任一栈加入新的元素。试定义这种双栈结构的类型定义，并实现判栈空、判栈满、插入、删除算法。
2、假设以数组Q[m]存放循环队列中的元素，同时设置一个标志tag，以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入和删除算法。