第一章 绪论
1.简述下列术语：数据、数据元素、逻辑结构、存储结构、数据结构、数据类型和抽象数据类型。
答：数据：是对客观事物的符号表示，在计算机科学中指能输入到计算机中并被计算机程序处理的符号总称。
数据元素：又叫节点，它是组成数据的基本单位，在程序中，通常作为一个整体进行考虑和处理的。一般情况下，一个数据元素包含若干个数据项。
逻辑结构：数据元素和数据元素之间的逻辑关系称为数据的逻辑结构。（1）线性结构（2)非线性结构
存储结构：数据的逻辑结构在计算机中的表示（又称映像）。它包括数据元素的表示和关系的表示。数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像。对应的两种不同的存储结构分别是顺序存储结构和链式存储结构。顺序映像是借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系；非顺序映像是借助指针（指向数据元素的存储地址）表示数据元素之间的关系。
数据结构：指相互之间存在某种关系的数据元素的集合。
数据结构是一个二元组，如数据结构Data_Structure=(D,R)其中，D是数据元素的有限集，R是D上的关系的有限集。
数据类型：是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作。ADT=（D,S,P)三元组表示其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。
2.填空题
1、数据结构是一门研究非数值计算的程序设计问题中计算机的（操作对象）以及它们之间（关系）和运算等的学科。
2、数据结构包括数据的（逻辑机构）、数据的（存储结构）和数据的（运算）这三个方面的内容。
3、数据结构按逻辑结构可分为两大类，他们是(线性结构）和（非线性结构）。
3.什么是算法？算法的主要特点是什么？
答：算法是解决某特定问题的有穷的有效地运算序列。
算法的主要特点是：有穷性、确定性、可行性、输入、输出。
4.分析一下程序时间复杂度：
（1）x=0;
for(i=1;i
x++;
f(n)=(n^2-n)/2;
(2)int s=0,i,j,k;
for(i=0;i<=n;i++)
for(j=0;j<=i;j++)
for(k=0;k
n^3
自测题
1、线性结构是数据元素之间存在一种：（D）
A)一对多关系 B)多对多关系
C）多对一关系 D）一对一关系
2.数据结构中，与所使用的计算机无关的是数据的（C）结构
A）存储 B）物理 C）逻辑 D）物理和存储
3.算法分析的目的是（C）
A）找出数据结构的合理性
B）研究算法中的输入和输出的关系
C）分析算法的效率
以求改进
D）分析算法的易懂性和文档性
4.在数据结构中，从逻辑上可以将之分为（D）。
A）动态结构和静态结构
B）紧凑结构和非紧凑结构
C）内部结构和外部结构
D）线性结构和非线性结构
5.计算算法的时间复杂度是属于一种（B）
A)事前统计的方法
B)事前分析估算的方法
C）事后统计的方法
D）事后分析估算的方法
6.可以用（D）定义一个完整的数据结构
A)数据元素
B）数据对象
C）数据关系
D）抽象数据类型
7.下面程序段时间复杂度是：
i=1；
while(i<=n)
i=i*3;
log3(n)
第二章
1．在顺序表中插入或删除一个元素，需要移动（n/2）元素，移动的元素个数与（表长和元素所在的位置）有关。
2.在双链表中，每个结点有两个指针域，一个指向（前驱结点）另一个指向（后继结点）。
3．线性表的顺序存储结构是通过（元素在存储器上的相对位置）来直接反映数据元素之间的逻辑关系，而链式存储结构是通过（指针）来间接反映数据元素之间的逻辑关系的。
4．在循环双向链表的p所指结点之后插入s所指结点的操作是（s->next=p->next）;(p->next->prior=s);(p->next=s);(s->prior=p);
5．试比较顺序存储结构和链式存储结构的优缺点。各在什么情况下用比较好？
答：顺序表的优点：1无须为表示节点间的逻辑关系而增加额外的空间；
2 可以实现随机存取；
缺点：1数据元素最大个数需预先确定，使得高级程序设计语言编译系统需预先分配相应的存储空间；
2插入和删除运算的效率较低；
3顺序结构的存储空间不便于扩充。
链表的优点：1.结点的空间可动态申请和释放；
2．数据元素的逻辑关系靠结点的指针指示，增减结点，非常方便。
缺点：1.不能进行随机访问，只能进行顺序访问。
2．每个结点上增加指针域，造成额外存储空间增大。
（1）若线性表需频繁找却很少进行插入和删除操作，或其操作和元素在表中的位置密切相关时，宜采用顺序表作为存储结构；若线性表需频繁 插入和删除时，则宜采用单链表做存储结构。
（2）当线性表中元素个数变化较大或者未知时，最好使用单链表实现；
而如果用户事先知道线性表的大致长度，使用顺序表的空间效率会更高。
6．描述以下三个概念的区别：头指针、头结点、首元素结点（第一个元素结点）。在链表设置头结点的作用是什么？
答：头指针是指向链表中第一个结点的指针。
头结点是在链表的首元结点之前附设的一个结点；数据域只存放空表信息或表长等信息。
首元素结点是指链表中存储线
性表中第一个元素a1的结点。
设置头结点的作用：
1． 对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一个结点的指针域，因为任何元素结点都有前驱结。
2． 对带头结点的链表，表头指针是指向头结点的非空指针，因此，空表和非空表的处理是一样的。
自测题：
（1） 一个顺序表所占用的存储空间大小与（B）无关。
A．表的长度 B.元素的存放顺序 C.元素的类型 D.元素中各字段的类型
（2）设存储分配是从低地址到高地址进行的。若每个元素占用4个存储单元，则某元素的地址是指它所占用的单元的（A）
A．第1个单元的地址 B.第2个单元的地址
C.第3个单元的地址 D.第4个单元的地址
(3)若线性表采用顺序存储结构，每个元素占用4个存储单元，第1个元素的存储地址为100，则第12个元素的存储地址是（B）。
A.112 B.144 C.148 D.412
(4)若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值应该是（D）。
A.i>0 B.i
A．i>0 B.i<=n C.1<=i<=n D.1<=i<=n+1
(6)若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，首先需要移动表中（A）个数据元素。
A．n-i B.n+i C.n-i+1 D.n-i-1
(7)若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，需要移动表中（C）个元素。
A．i B.n+I C.n-i+1 D.n-i-1
(8)若频繁地对线性表进行插入和删除操作，该线性表应该采用（C）存储结构。
A．散列 B。顺序 C.链式 D.索引
（9）聊表中所占用的存储单元地址一定是（）
A．无序的 B.连续的 C.不连续的 D.部分连续的
（10）链表中的每一个链结点所占用的存储单元（B）。
A．不必连续 B.一定连续 C.部分连续 D.连续与否无所谓
（11）与单链表相比，双向链表的优点之一是（D）
A．插入、删除操作更简单 B．可以进行随机访问
C．可以省略头结点指针 D．顺序访问相邻结点更灵活
(12)表达式中，符号p->next表示D。
A．p所指的链结点的指针域(位置)
B．p所指的链结点的指针域的内容
C．p所指的链结点的下一个链结点的值
D．p所指的链结点的下一个链结点的地址(出现在表达式中)
(13)在一个具有n个链结点的线性链表中查找某一个链结点，若查找成功，需要平均比较 （C）个链结点。
A．n B．n／2 C．(n+1)／2 D．(n-1)／Q
(14)从一个具有n个链结点的有序线性链表(即链结点按照
数据域值有序链接)中插入一个新的链结点，并且仍然保持链表有序的时间复杂度为――。
A．O(1) B．O(n) C．O( n(2) ) D．O( log2(n) )
(15)在非空线性链表中由p所指的链结点后面插入一个由q所指的链结点的过程是依次执行(B)。
A．q->next=p；p->next=q； B．q->next=p->next；p->next=q；
C．q->next=p->next；p=q； D．p->next=q；q->next=p；
(16)若删除非空线性链表中由p所指的链结点的直接后继链结点的过程是依次执行 ___B_____.
A．r=p->next；p->next=r；free(r)；
B．r=p->next；p->next=r->next；free(r)；
C．r=p->next；p->next=r->next；free(p)；
D．p->next=p->next->next；free(p)；
(17)在非空双向循环链表中由q所指的链结点后面插入一个由p所指的链结点的动作依次 为：p->prior=q；p->next=q->next；(B) q->next=p；。(空白处为一条赋值语句)
A．q->prior=p B．q->next->prior=p
C．p->next>prior=p D．p->prior->prior=p
(18)在非空双向循环链表中由q所指的那个链结点前面插入一个p所指的链结点的动作对 应的语句依次为：p->next=q；p->prior=q->prior；(B) q->prior=p；。(空白处为一条赋值语句)
A．q->next=p； B．q->prior->next=p；
C．p->next->next=p； D．p->prior->next=p；
(19)在包含有1000个数据元素的线性表中实现如下四个操作，所需要的执行时间最长的是(D)
A．线性表采用顺序存储结构，在第10个元素后面插入一个新的元素
B．线性表采用链式存储结构，在第10个元素后面插入一个新的元素
C．线性表采用顺序存储结构，删除第990个元素
D．线性表采用链式存储结构，删除p所指的链结点
第三章 栈与队列
1．假设CQ[0……11]是一个环形队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。
d,e,b,g,h入队； d,e出队； I,j,k,l,m入队； b出队； n,o,p,q入队
2．写出下列程序段的输出结果（栈的元素类型SElemType为char）。
Void main(){
Stack S;
Char x,y;
InitStack(S);
X=’c’;y=’k’;
Push(S,x);Push(S,’a’);Push(S,y);
Pop(S,x);push(S,’t’);Push(S,x);
Pop(S,x);Push(S,’s’);
While(!StackEmpty(S)){Pop(S,y);printf(y);};
Printf(x);
}
Cats
3.对于一个栈，给出输入项A,B,C,D。如果输出项序列由A,B,C,D所组成，试给出全部可能的输出序列。
ABCD ABDC ACBD ACDB ADCB
BADC BACD BCDA BCAD BDCA
CBDA CBAD CDBA
DCAB
4．在以下栈的基本运算中，不是加工型运算的是（D）
A．InitStack(S) B.Push(S，X) C.Pop(S) D.Stackempty(S)
2．以下说法正确的是（A）
A．因链栈本身没有容量
限制，故在用户内存空间的范围内不会出现栈满情况。
B.因顺序栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况
C．对于链栈而言，在栈满状态下，如果此时再作进栈运算，则会发生“上溢”。
D．对于顺序栈而言在栈满状态下如果此时再作进栈运算，则会发生“下溢”。
3．顺序队列的入队操作应为（B）
A．sq.rear=sq.rear+1; sq.data[sq.rear]=x
B.sq.data[sq.rear]=x; sq.rea=sq.rear+1
C.sq.rear=(sq.rear+1)%maxsize; sq.data[sq.rear]=x;
D.sq.data[sq.rear]=x; sq.rear=(sq.rear+1)%maxsize
4.循环队列的入队操作应为（D）
A.sq.rear=sq.rear+1 sq.data[sq.rear]=x
B.sq.data[sq.rear]=x; sq.rear=sq.rear+1
C.sq.rear=(sq.rear+1)%maxsize; sq.data[sq.rear]=x
D.sq.data[sq.rear]=x; sq.rear=(sq.rear+1)%maxsize
5.顺序队列得出队操作为（B）
A．sq.front=(sq.front+1)%maxsize
B.sq.front=sq.front+1
C.sq.rear=(sq.rear+1)%maxsize
D.sq.rear=sq.rear+1
6．循环队列的出队操作为（A）
A．sq.front=(sq.front+1)%maxsize
B.sq.front=sq.front+1
C.sq.rear=(sq.rear+1)%maxsize
D.sq.rear=sq.rear+1
7.循环队列的队满条件为（C）
A.(sq.rear+1)%maxsize==(sq.front+1)%maxsize;
B.(sq.rear+1)%maxsize==sq.front+1
C.(sq.rear+1)%maxsize==sq.front
D.sq.rear==sq.front
8．循环队列的队空条件为（D）
A．（sq.rear+1）%maxsize==(sq.front+1)%maxsize
B.(sq.rear+1)%maxsize==sq.front+1
C.(sq.rear+1)%maxsize==sq.front
D.sq.rear==sq.front
9.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s5,s1,则栈的容量至少应该是（B）
A.2 B.3 C.5 D.6
10．向一个栈顶指针为Top的链中插入一个s所指结点时，其操作步骤为（B）
A．Top->next=s
B.s->next=Top->next; Top->next=s
C.s->next=Top;Top=s
D.s->next=Top;Top=Top->next
11.从栈顶指针为Top的链栈中删除一个结点，并将被删结点的只保存在x中，其操作步骤为（B）
A.x=Top->data;Top=Top->next
B.Top=Top->next;x=Top->data;
C.x=Top;Top=Top->next
D.x=Top->data
12.在一个链队中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为（）
A.f->next=c;f=s
B.r->next=s;r=s
C.s->next=r;r=s
D.s->next=f;f=s
13.链栈与顺序栈相比，有一个比较明显的优点即（B）
A.插入操作更方便
B.通常不会出现栈满的情况
C.不会出现栈空的情况
D．删除操作更方便
14．一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（C）
A．edcba B.decba C.dceab D.abcde
15.若已知一个栈的输入序列为1,2,3，……n，其输出序列为P1、P2、……Pn.p1=n,则pi为（C）
A．i B.n=i C.n-i+1 D.不确定
16．若已知一个栈的输入序列为1,2,3，……n,其输出序列为P1、P2、……Pn.
若Pn=n,则pi为（D）
A.i B.n=i C.n-i+1 D.不确定
18．若已知一个栈的输入序列为p1,p2,p3,……,pn,其输
出序列为1,2,……n.p3=1,则p1为（A）
A.可能是2 B.一定是2 C.不可能是2 D.不可能是3
19．若已知一个栈的输入序列为p1,p2,p3,……，pn,其输出序列为1、2、……n。若pn=1,则pi为（A）
A.n-i+1 B.n-i C.i D.有多种可能
20．若用一个大小为6的一维数组来实现环形队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是（B）
A.1和5 B.2和4 C.4和2 D5和1
补充：线性表、栈与队的异同点：
相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链式存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）
不同点：
1、 运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先出的LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表。
2、 用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。
第六章
一、下面是有关二叉树的叙述，请判断正误。
1．若二叉树用二叉链表作存储结构，则在n个结点的二叉树链表中只有n-1个非空指针域。
2．二叉树中每个结点的两棵子树的高度差等于1。
3．二叉树中每个结点的两棵子树是有序的。对！
4．二叉树中每个结点有两棵非空子树或两棵空子树。
5．不存在这样的二叉树：它有n个度为0的结点，n-1个度为1的结点，n-2个度为2的结点。对！
6．二叉树中所有结点个数是2^(k-1)-1,其中k是树的深度。
7．二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
8．对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2^i-1个结点。
9．用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个位空指针。
10．具有12个结点的完全二叉树有5个度为2的结点。对！
二．练习
1、先序遍历序列为：abdgcefh,中序遍历为dgbaechf,给出该二叉树的后续遍历序列。
2、后序遍历序列为：cedbhjigfa,中序遍历为cbedahgijf，给出该二叉树的先序遍历序列。
三、填空。
1．一棵深度为6的满二叉树有（）个分支结点和（）个叶子结点。
2．一颗具有257个结点的完全二叉树，它的深度为（）
3．设一棵完全二叉树具有1000个结点，则此完全二叉树有（）个叶子结点，有（）个度为2的结点，有（）个结点只有非空左子树，有（）个结点只有非空右子树。
5．一棵含有n个结点的k叉树，可能达到的最大深度（），最小深度（）。
三、已知某二叉树的后续遍历是dabec,中
序遍历是debac，给出它的先序遍历序列。
四、某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，给出其后序遍历序列，并给出其后序线索二叉树和后续线索二叉链表。
补充：
1、二叉树具有下列重要特性：
性质1：在二叉树的第i层上之多有2^(i-1)个结点。
性质2：深度为k的二叉树至多有2^k-1个结点。
性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
性质4：具有n个结点的完全二叉树的深度为不大于log2n+1的最大整数
性质5：如果对一棵有n个结点的完全二叉树（其深度为【log2n+1】的结点按层序编号（从第1层到第【log2n+1】层，每层从左到右），则对任一结点i（1<=i<=n）,有：
（1） 如果i=1,则结点i是二叉树的根，无双亲；如果i>1,则其双亲PARENT(i)是结点【i/2】.
2、1）由二叉树的前序序列和中序序列可以唯一确定这棵二叉树。
2）由二叉树的中序序列和后序序列可以唯一确定这棵二叉树。
3）由二叉树的前序序列和后序序列不能唯一确定这棵二叉树。