当前位置：文档之家 › 数据结构李春葆习题与解析

数据结构李春葆习题与解析

  • 格式：doc
  • 大小：127.11 KB
  • 文档页数：40

下载文档原格式

  / 40

合集下载

数据结构教程李春葆课后答案第5章递归

数据结构教程李春葆课后答案第5章递归

9. 设有一个不带表头结点的单链表 L，设计两个递归算法，maxnode(L)返回单链表 L
4
数据结构教程学习指导
中最大结点值，minnodel(L)返回单链表 L 中最小结点值。 解：对应的递归算法如下：
ElemType maxnode(LinkNode *L) { ElemType max; if (L->next==NULL) return L->data; max=maxnode(L->next); if (max>L->data) return max; else return L->data; } ElemType minnode(LinkNode *L) { ElemType min; if (L->next==NULL) return L->data; min=minnode(L->next); if (min>L->data) return L->data; else return min; }
b:5 b:4 b:3 b:2 a:1 c:2 c:3 c:4 c:5
2. 已知 A[0..n-1]为整数数组，设计一个递归算法求这 n 个元素的平均值。 解：设avg(A，i)返回A[0..i]共i+1个元素的平均值，则递归模型如下：
avg(A，i)=A[0] avg(A，i)=(avg(A，i-1)*i+A[i])/(i+1) 当i=0 其他情况
第 5 章 递归 return i-1; else return -1; }
5
#include "sqstring.cpp" //顺序串的基本运算算法 findpat(SqString s,SqString t) { int i=0,j=0,k; while (i<s.length && j<t.length) { if (t.data[j]=='*') { k=findpat(SubStr(s,i+2,s.length-i-1),SubStr(t,j+2,t.length-j-1)); j++; if (k>-1) return i-1; else return -1; } else if (s.data[i]==t.data[j]) { i++; j++; } else { i=i-j+1; j=0; } } if (j>=t.length)

数据结构教程李春葆第4版知识点习题答案

数据结构教程李春葆第4版知识点习题答案

第1章绪论知识点归纳一、数据结构概述1.数据结构的定义（1）基本概念数据是描述客观事物的数和字符的集合，是计算机能操作的对象的总称，也是计算机处理信息的某种特定的符号表示形式。

（2）相关术语① 数据元素数据元素又称元素、节点、顶点、记录等。

数据元素是数据的基本单位。

有时候，一个数据元素可以由若干个数据项组成。

② 数据项数据项又称字段或域，它是具有独立含义的最小数据单位。

③ 数据对象数据对象是性质相同的数据元素的集合，它是数据的子集。

（3）数据结构的内容① 数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。

② 数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，又称数据的物理结构。

③ 施加在数据上的操作，即数据的运算。

（4）逻辑结构数据的逻辑结构是从逻辑关系（主要是指数据元素的相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

（5）存储结构数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（又称映像），也就是逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。

一般只在高级语言（例如C／C++语言）的层次上讨论存储结构。

数据的运算最终需在对应的存储结构上用算法实现。

总之，数据结构是一门讨论“描述现实世界实体的数学模型（通常为非数值计算）及其之上的运算在计算机中如何表示和实现”的学科。

（6）数据结构的表示对于一种数据结构，其逻辑结构总是惟一的，但它可能对应多种存储结构，并且在不同的存储结构中，同一运算的实现过程可能不同。

描述数据结构通常采用二元组表示：B=（D，R）其中，B是一种数据结构，它由数据元素的集合D和D上二元关系的集合R组成，即：D={d i | 1≤i≤n，n≥0}R={r j | 1≤j≤m，m≥0}其中d i表示集合D中的第i个数据元素（或节点），n为D中数据元素的个数，特别地，若n=0，则D 是一个空集。

数据结构（李春葆）习题与解析

数据结构（李春葆）习题与解析

数据结构（李春葆）习题与解析一、绪论选择题1.数据结构是一门研究非数值计算的程序设计问题计算机的以及它们之间的和运算等的学科。

1A.数据元素B.计算方法C.逻辑存储D.数据映像2A.结构B.关系C.运算D.算法2.数据结构被形式地定义为(K,R)，其中K是的有限集，R是K上的有限集。

1A.算法B.数据元素C.数据操作D.逻辑结构2A.操作B.映像C.存储D.关系3.在数据结构中，从逻辑上可以把数据结构分成。

A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4.线性结构的顺序存储结构是一种的存储结构，线性表的链式存储结构是一种的存储结构。

A.随机存取B.顺序存取C.索引存取D.散列存取5.算法分析的目的是，算法分析的两个主要方面是。

1A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2A.空间复杂度和时间复杂度B.正确性和简单性C.可读性和文档性D.数据复杂性和程序复杂性6.计算机算法指的是，它必须具备输入、输出和等5个特性。

1A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法2A.可执行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。

A.正确B.不正确8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。

A.必须连续的B.部分地址必须连续的C.一定是不续的D连续不连续都可以9.以下的叙述中，正确的是。

A.线性表的存储结构优于链式存储结构B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。

A.正确B.不正确填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。

部分习题参考答案(数据结构 李春葆)PPT课件

部分习题参考答案(数据结构 李春葆)PPT课件

//对应的队列为空队时
{
QH[x]=s;
QT[x]=s;
}
else
{
QT[x]->next=s; //将*s节点链到QT[x]所指节点之后
QT[x]=s;
//让QT[x]仍指向尾节点
}
}
16
void Create(QNode *QH[],QNode *QT[]) //根据用户输入创建队列
{
int n,x,i;
L->data[j+1]=L->data[j]; L->data[i]=x; L->length++; }
1
2.3 设计一个算法，将一个带头结点的数据域依次为a1，a2，…， an（n≥3）的单链表的所有结点逆置，即第一个结点的数据域变 为an，…，最后一个结点的数据域为a1。
void Reverse(LinkList *&L) { LinkList *p=L->next,*q;
}
printf("\n");
}
18
void main()
{
int i;
QNode *QH[MAXQNode],*QT[MAXQNode];
//各队列的队头QH和队尾指针QT
for (i=0;i<MAXQNode;i++)
QH[i]=QT[i]=NULL;
解：（1）A、D均合法，而B、C不合法。因为在B中，先 进栈一次，立即出栈三次，这会造成栈下溢。在C中共进 栈五次，出栈三次，栈的终态不为空。
10
（2）本题使用一个链栈来判断操作序列是否合法，其中A为存
放操作序列的字符数组，n为该数组的元素个数（这里的

李春葆大数据结构习题与解析汇报(修订版)

李春葆大数据结构习题与解析汇报(修订版)

春葆编著：数据结构（C语言篇）――习题与解析（修订版）清华大学一、绪论选择题1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。

1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像2 A.结构 B.关系 C.运算 D.算法2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。

1 A.算法 B.数据元素 C.数据操作 D.逻辑结构2 A.操作 B.映像 C.存储 D.关系3.在数据结构中，从逻辑上可以把数据结构分成。

A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.部结构和外部结构4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。

A.随机存取B.顺序存取C.索引存取D.散列存取5.算法分析的目的是1，算法分析的两个主要方面是2。

1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2 A.空间复杂度和时间复杂度 B.正确性和简单性C.可读性和文档性D.数据复杂性和程序复杂性6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。

1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。

A.正确B.不正确8线性表若采用链式存储结构时，要求存中可用存储单元的地址。

A.必须连续的B.部分地址必须连续的C.一定是不续的D连续不连续都可以9.以下的叙述中，正确的是。

A.线性表的存储结构优于链式存储结构B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。

数据结构简明教程(李春葆版)课后习题答案

数据结构简明教程(李春葆版)课后习题答案

数据结构简明教程（第2版）配套练习题参考答案———————数据结构简明教程———————1.练习题1参考答案1.单项选择题（1）D （2）C （3）C （4）A （5）C （6）B （7）C （8）A （9）C （10）B 2.填空题（1）①逻辑结构 ②存储结构 ③运算（不限制顺序）（2）①线性结构 ②非线性结构（不限制顺序）（3）①数据元素 ②关系（4）①没有 ②没有（5）①前驱 ②一 ③后继 ④任意多个（6）任意多个（7）①顺序 ②链式 ③索引 ④哈希（不限制顺序）（8）①时间 ②空间（不限制顺序）（9）问题规模（通常用n 表示）。

（10）辅助或临时空间3.简答题（1）答：运算描述是指逻辑结构施加的操作，而运算实现是指一个完成该运算功能的算法。

它们的相同点是，运算描述和运算实现都能完成对数据的“处理”或某种特定的操作。

不同点是，运算描述只是描述处理功能，不包括处理步骤和方法，而运算实现的核心则是处理步骤。

（2）答：T 1(n )=O(n log 2n )，T 2(n )=O( )，T 3(n )=O(n 2)，T 4(n )=O(n log 2n )。

（3）答：j =0，第1次循环：j =1，s =10。

第2次循环：j =2，s =30。

第3次循环：j =3，s =60。

第4次循环：j =4，s =100。

while 条件不再满足。

所以，其中循环语句的执行次数为4。

（4）答：语句s ++的执行次数2)2)(3(3)1()1(12121-+=++-+=+-=∑∑∑-=-==n n n n i n n i n i i nj。

（5）答：其中x ++语句为基本运算语句，∑∑∑=+==-=-==n i n i j ni n n i n n T 1112)1()(1)(=O(n 2)。

（6） 答：由于内循环j 的取值范围，所以i ≤n /2，则，该程序段的时间复杂度为O(n 2)。

∑∑∑-===--==2/122/124/))12((n i nij n i n i n m 3log 2n2.练习题2参考答案1.单项选择题（1）A （2）C （3）A （4）B （5）C（6）D （7）C （8）B （9）A （10）C（11）B （12）A （13）C （14）D （15）D（16）D （17）A （18）C （19）A （20）D2.填空题（1）L.length=0（2）O(1)（3）O(n)（4）n-i（5）①物理存储位置②指针域（6）①前驱　②O(n)（7）q=p->next; p->next=q->next; free(q);（8）s->next= p->next; p->next=s;（9）O(1)（10）L->next==L3.简答题（1）答：顺序存储结构中，逻辑上相邻元素的存储空间也是相邻的，无需额外空间表示逻辑关系，所以存储密度大，同时具有随机存取特性。

数据结构教程李春葆课后答案第10章内排序


2 else d=d/3; } }
数据结构教程学习指导
（1）指出fun(a，n)算法的功能。 （2）当a[]={5，1，3，6，2，7，4，8}时，问fun(a，8)共执行几趟排序，各趟的排序 结果是什么？ 答：（1）fun(a，n)算法的功能是采用增量递减为1/3的希尔排序方法对a数组中元素进 行递增排序。 （2）当a[]={5，1，3，6，2，7，4，8}时，执行fun(a，8)的过程如下： d=2：2 1 3 6 4 7 5 8 d=1：1 2 3 4 5 6 7 8 共有两趟排序。 4. 在实现快速排序的非递归算法时，可根据基准元素，将待排序序列划分为两个子 序列。若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需要的栈 的深度为 O(log2n)。 答：由快速排序的算法可知，所需递归工作栈的深度取决于所需划分的最大次数。在 排序过程中每次划分都把整个待排序序列根据基准元素划分为左、右两个子序列，然后对 这两个子序列进行类似的处理。 设S(n)为对n个记录进行快速排序时平均所需栈的深度， 则： S(n)=
KeyType QuickSelect(RecType R[],int s,int t,int k) //在 R[s..t]序列中找第 k 小的元素 { int i=s,j=t; RecType tmp; if (s<t) //区间内至少存在 2 个元素的情况 { tmp=R[s]; //用区间的第 1 个记录作为基准 while (i!=j) //从区间两端交替向中间扫描,直至 i=j 为止 { while (j>i && R[j].key>=tmp.key) j--; //从右向左扫描,找第 1 个关键字小于 tmp 的 R[j] R[i]=R[j]; //将 R[j]前移到 R[i]的位置 while (i<j && R[i].key<=tmp.key) i++; //从左向右扫描,找第 1 个关键字大于 tmp 的 R[i] R[j]=R[i]; //将 R[i]后移到 R[j]的位置 } R[i]=tmp; if (k-1==i) return R[i].key; else if (k-1<i) return QuickSelect(R,s,i-1,k); //在左区间中递归查找 else return QuickSelect(R,i+1,t,k); //在右区间中递&& s==k-1) return R[k-1].key; else return -1; }

数据结构教程李春葆课后答案第6章数组和广义表

答：对于上三角部分或者主对角中的元素 A[i][j（] i≤j），按列为主序存储时，前面有 0～ j-1 共 j 列，第 0 列有 1 个元素，第 1 列有 2 个元素，…，第 j-1 列有 j 个元素，所以这 j 列的元素个数=1+2+…+j=j(j+1)/2；在第 j 列中，A[i][j]元素前有 A[0..i-1，j]共 i 个元素。所 以 A[i][j]元素前有 j(j+1)/2+i 个元素，而 B 的下标从 0 开始，所以 A[i][j]在 B 中的位置 k=j(j+1)/2+i。
int length; }
//元素值 //重复元素的个数
如数组 A[]={1，1，1，5，5，5，5，3，3，3，3，4，4，4，4，4，4}，共有 17 个元 素，对应的压缩存储 B 为：{1，3}，{5，4}，{3，4}，{4，6}}。从中看出，如果重复元素 越多，采用这种压缩存储方式越节省存储空间。
6. 利用三元组存储任意稀疏数组 A 时，假设其中一个元素和一个整数占用的存储空间 相同，问在什么条件下才能节省存储空间。
答：设稀疏矩阵 A 有 t 个非零元素，加上行数 rows、列数 cols 和非零元素个数 nums （也算一个三元组），那么三元组顺序表的存储空间总数为 3(t+1)，若用二维数组存储时占 用存储空间总数为 m×n，只有当 3(t+1)<m×n 即 t<m×n/3-1 时，采用三元组存储才能节省存 储空间。
解：对于稀疏矩阵三元组表 a，从 a.data[0]开始查看，若其行号等于列号，表示是一
个对角线上的元素，则进行累加，最后返回累加值。算法如下：
bool diagonal(TSMatrix a,ElemType &sum)

数据结构教程李春葆课后答案 图

（3）对于邻接矩阵表示的无向图，顶点i的度等于第i行中元素为1的个数；对于邻接矩 阵表示的有向图，顶点i的出度等于第i行中元素为1的个数，入度等于第i列中元素为1的个 数，顶点i度等于它们之和。
对于邻接表G表示的无向图，顶点i的度等于G->adjlist[i]为头结点的单链表中边表结点 个数。
对于邻接表G表示的有向图，顶点i的出度等于G->adjlist[i]为头结点的单链表中边表结 点的个数；入度需要遍历所有的边结点，若G->adjlist[j]为头结点的单链表中存在编号为i 的边结点，则顶点i的入度增1，顶点i的度等于入度和出度之和。
4
数据结构教程学习指导
中。因为在采用Kruskal算法构造最小生成树时，选择这3条权最小的边加入时，有可能出 现回路。例如，如图8.5所示的带权无向图，有3条边的权均为1，它们一定不会同时都出现 在其任何最小生成树中。
1 1
1 0
1
3
3 2
图 8.5 一个带权无向图
8. 对于如图8.6所示的带权有向图，采用Dijkstra算法求出从顶点0到其他各顶点的最短 路径及其长度，要求给出求解过程。
0
0
1
2
4
5
1
2
4
5
6
3
6
(a) 一个有向图
3 (b) 3 个强连通分量
图 8.2 一个有向图及其强连通分量
3. 对于稠密图和稀疏图，采用邻接矩阵和邻接表哪个更好些？ 答：邻接矩阵适合于稠密图，因为邻接矩阵占用的存储空间与边数无关。邻接表适合 于稀疏图，因为邻接表占用的存储空间与边数有关。
4. 对 n 个顶点的无向图和有向图（均为不带权图），采用邻接矩阵和邻接表表示时， 如何求解以下问题：

李春葆数据结构教程第4版习题答案

1章答案1.简述数据与数据元素的关系与区别。

解：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。

数据元素是数据的基本单位，是数据的个体。

数据与元素之间的关系是元素与集合之间的关系。

2.数据结构和数据类型有什么区别？解：数据结构是互相之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。

而数据类型是一个值的集合和定义在这个集合上的一组运算的总称，如C语言中的int数据类型是由-32768~32767（16位机）的整数和+、-、*、/、%等运算符组成。

3.设3个表示算法频度的函数f、g和h分别为：f（n）=100n3+n2+1000 g（n）=25n3+5000n2 h（n）=n1.5+5000nlog2n求它们对应的时间复杂度。

解：f（n）=100n3+n2+1000=O（n3），g（n）=25n3+5000n2=O（n3），当n→∞时，√n>log2n，所以h（n）=n1.5+5000nlog2n= O（n1.5）。

4.用C／C++语言描述下列算法，并给出算法的时间复杂度。

（1）求一个n阶方阵的所有元素之和。

（2）对于输入的任意三个整数，将它们按从小到大的顺序输出。

（3）对于输入的任意n个整数，输出其中的最大和最小元素。

解：（1）算法如下：本算法的时间复杂度为O（n2）。

（2）算法如下：本算法的时间复杂度为O（1）。

（3）算法如下：本算法的时间复杂度为O（n）。

5.设n为正整数，给出下列各种算法关于n的时间复杂度。

（1）（2）（3）解：（1）设while循环语句执行次数为T（n），则：（2）算法中的基本运算语句是if（b[k]>b[j]）k=j，其执行次数T（n）为：（3）设while循环语句执行次数为T（n），则：则6.有以下递归算法用于对数组a[i．．j]的元素进行归并排序：求mergesort（a，0，n－1）的时间复杂度。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

数据结构（C语言篇）―习题与解析（修订版）清华大学出版社一、绪论选择题1.数据结构是一门研究非数值计算的程序设计问题计算机的以及它们之间的和运算等的学科。

1A.数据元素 B.计算方法 C.逻辑存储 D.数据映像2A.结构 B.关系 C.运算 D.算法2.数据结构被形式地定义为(K, R)，其中K是的有限集，R是K上的有限集。

1A.算法 B.数据元素 C.数据操作 D.逻辑结构2A.操作 B.映像 C.存储 D.关系3.在数据结构中，从逻辑上可以把数据结构分成。

A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4.线性结构的顺序存储结构是一种A的存储结构，线性表的链式存储结构是一种B的存储结构。

A.随机存取B.顺序存取C.索引存取D.散列存取5.算法分析的目的是C，算法分析的两个主要方面是AB。

1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2 A.空间复杂度和时间复杂度 B.正确性和简单性C.可读性和文档性D.数据复杂性和程序复杂性6.计算机算法指的是C，它必须具备输入、输出和B等5个特性。

1 A.计算方法 B.排序方法 C.解决问题的有限运算序列D.调度方法2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法B。

A.正确B.不正确8线性表若采用链式存储结构时，要求内存中可用存储单元的地址D。

A.必须连续的B.部分地址必须连续的C.一定是不续的D连续不连续都可以9.以下的叙述中，正确的是B。

A.线性表的存储结构优于链式存储结构B.二维数组是其数据元素为线性表的线性表队列的操作方式是D. 先进后出栈的操作方式是C.先进先出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法B。

A.正确B.不正确填空题1.数据逻辑结构包括三种类型线性结构、树形结构和图形结构，树形结构和图形结构合称为非线性结构。

2.在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。

3.在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续可以任意多个。

4.在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。

5.线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。

6.算法的五个重要特性是有穷性、确定性、可行性、输入、输出。

7.下面程序段的时间复杂度是O（m*n）。

for( i = 0; i < n; i++)for( j = 0; j < m; j++)A[i][j] = 0;8.下面程序段的时间复杂度是O（n）。

i = s = 0;while ( s < n){i ++; /* i = i +1*/s += i; /* s = s + i*/}9.下面程序段的时间复杂度是O（n2）。

s = 0;for( i = 0; i < n; i++)for( j = 0; j < n; j++)s += B[i][j];sum = s;10.下面程序段的时间复杂度是O（log3n）。

i = 1;while ( i <= n )i = i * 3;二、线性表单项选择题．，则2100，每个元素的长度为1.一个向量第一个元素的存储地址是。

B第5个元素的地址是D.120C.100 A.110 B.108，则栈的不可能输出序列是e c、d、2.一个栈的入栈序列是a、b、。

C D.abcdeC.dceabA.edcba B.decba、、pn，其输出序列为p、12、3、…、3.若一个栈的入栈序列是21。

C，则p为、…p 、p，若p=n in31不确定 D. C. n - i +1 B. n = i A. i。

A 4.栈结构通常采用的两种存储结构是散列方式和索引方式 B.线性存储结构和链表存储结构 A.线性存储结构和非线D. C.链表存储结构和数组性存储结构5.判断一个栈ST (最多元素为m) 为空的条件是B。

A.ST->top!=0B. ST->top==0C. ST->top!= mD.ST->top== m6.判断一个栈ST (最多元素为m) 为满栈的条件是D。

A.ST->top!=0B. ST->top==0C. ST->top!= m-1D.ST->top== m-17.栈的特点是B，队列的特点是A。

A.先进先出，后进后出B.先进后出，后进先出8.一个队列的入队序列是1、2、3、4，则队列输出序列是B。

A.4、3、2、1B.1、2、3、4C.1、4、3、2D.3、2、4、19.判断一个队列QU (最多元素为m) 为空的条件是C。

A. QU->rear－QU->front == mB. QU->rear－QU->front－1 == mC. QU->front == QU->rearD. QU->front－QU->rear +110.判断一个队列QU (最多元素为m) 为满队列的条件是A。

A. QU->rear－QU->front == mB. QU->rear－QU->front－1 == mC. QU->front == QU->rearD. QU->front－QU->rear +111.判断一个循环队列QU (最多元素为m) 为空的条件是。

A. QU->front == QU->rearB. QU->front != QU->rearC. QU->front == (QU->rear + 1) %mD. QU->front != (QU->rear+ 1) %m12.判断一个循环队列QU (最多元素为m) 为满队列的条件是。

A. QU->front == QU->rearB. QU->front != QU->rearD. QU->front != (QU->rearC. QU->front == (QU->rear + 1) %m+ 1) %m13循环队列用数组A[0, m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是。

A.(rear－front + m) %mB. rear－front + 1C. rear－front－1D. rear－front14.栈和队列的共同点是。

A.都是先进后出B.都是先进先出C.只允许在端点处插入、删除元素D.没有共同点填空题1.向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈只能在插入和删除元素；对于队列只能在插入元素和删除元素。

2.在一个长度为n的向量中的第i个元素(1≤i≤n)之前插入一个元素时，需向后移动个元素。

3.在一个长度为n的向量中的删除第i个元素(1≤i≤n)时，需要向前移动个元素。

4.向栈中压入元素的操作是。

5.对栈进行退栈时的操作是。

6.在一个循环队列中，队首指针指向队首元素的。

7.从循环队列中删除一个元素时，其操作是。

8.在具有n个单元的循环队列中，队满时共有个元素的。

9.一个栈的输入序列是12345，则栈的输出序列43512是。

10.一个栈的输入序列是12345，则栈的输出序列12345是。

三、链表单项选择题1.不带头结点的单链表head为空的判定条件是。

A.head==NULLB.head->nxt==NULLC.head->next==headD.head!=NULL2.带头结点的单链表head为空的判定条件是。

A.head==NULLB.head->nxt==NULLC.head->next==headD.head!=NULL3.非空的循环单链表head的尾结点（由p所指向）满足。

A.p->next==NULLB.p==NULLC.p->next==headD.p==head4.在循环双链表的p所指结点之后插入s所指结点的操作是。

A. p->right=s;s->left=p;p->right->left=s;s->right=p->right;B. p->right=s;p->right->left=s;s->left=p;s->right=p->right;C. s->left=p;s->right=p->right;p->right=s;p->right->left=s;D. s->left=p;s->right=p->right; p->right->left=s;p->right=s;所指结点的前驱结点，若在p所指结点是q在一个单链表中，已知5.q和p之间插入s结点，则执行。

A. s->next = p->next; p->next=s;B. p->next = s->next; s->next =p;C. q->next = s; s->next = p;D. p->next = s; s->next = q;6.在一个单链表中，已知p所指结点不是最后结点，在p之后插入s 所指结点，则执行。

A. s->next = p; p->next=s;B. s->next = p->next; p->next =s;C. s->next = p->next; p = s;D. p->next = s; s->next = p;7.在一个单链表中，若删除p所指结点的后续结点，则执行。

A. p->next = p->next->next;p->next;= p B.p->next=p->next->next;D. p =p->next ->next;C. p->next = p->next;结点时，在查找成n个结点的单链表中查找其值等于x9.从一个具有个结点。

功的情况下，需平均比较D. (n+1)/2C. (n-1)/2 B. n/2 A. n个结点的有序单链表中插入一个新结点并仍然有序在一个具有n10. 。