第一章绪论
一，选择题
1．组成数据的基本单位是（C ）
A ．数据项B ．数据类型C ．数据元素D ．数据变量
2．数据结构是研究数据的（C ）以及它们之间的相互关系。
A ．理想结构，物理结构B ．理想结构，抽象结构
C ．物理结构，逻辑结构D ．抽象结构，逻辑结构
3．算法分析的两个主要方面是（D ）
A ．正确性和简单性B ．可读性和文档性
C ．数据复杂性和程序复杂性D ．时间复杂度和空间复杂度
4．算法分析的目的是（C ）。
A ．找出数据结构的合理性B ．研究算法中的输入和输出的关系
C ．分析算法的效率以求改进D ．分析算法的易懂性和文档性
5. 算法的时间复杂度取决于（C ）
A．问题的规模B. 待处理数据的初态C. A 和B Ｄ．以上都不是
6．一个算法应该是（B ）。
A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.
7. 下面关于算法说法错误的是（D ）
A．算法最终必须由计算机程序实现
B.为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的
8．从逻辑上可以把数据结构分为（C ）两大类。
A．动态结构、静态结构B．顺序结构、链式结构
C．线性结构、非线性结构D．初等结构、构造型结构
9．程序段for (i=n-1;i>=1;i--)
for (j=1;j
if(A[j]>A[j+1])
A[j]与A[j+1]对换；
其中n 为正整数，则最后一行的语句频度在最坏情况下是（D ）
A ．O （n ）B ．O(nlogn)C. ．O(n3) D ．O(n2)
10．连续存储设计时，存储单元的地址（A ）。
A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续
二，判断题
1．数据结构的抽象操作的定义与具体实现有关。(×)
2．数据结构是数据对象与对象中数据元素之间关系的集合。（√）
3．在顺序存储结构中，有时也存储数据结构中元素之间的关系。(×)
4．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用的需要建立的。（√）
5．算法和程序原则上没有区别，在讨论数据结构是两者是通用的。(×)
6．同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。(×)
7．数据的逻辑结构与数据元素本身的内容和形式无关。（√）
8．算法的优劣与算法描述语言无关，但与所用计算机有关。(×)
9．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（√）
10．算法可以用不同的语言描述，如果用C 语言或PASCAL 语言等高级语言来描述，则算法实际上就是程序了。(×)
三，填空
1．数据的物理结构包括数据元素的表示和数据元素间关系的表示。
2. 对于给定的n 个元素,可以构造出的逻辑结构有，，__图状结构或网状结构_四种。
3．一个数据结构在计算机中称为存储结构。
4．抽象数据类型的定义仅取决于它的一组_实现_无关，即不论其内部结构如何变化，只要它的_数学特性_不变，都不影响其外部使用。
5．线性结构中元素之间存在关系, 树形结构中元素之间存在关系, 图形结构中元素之间存在6．一个算法有5个特性:，有零个或多个输入、有一个或多个输出。
7．已知如下程序段
for （i=n ；i
{
x:=x+1；
for(j=n;j
y:=y+1;
}
语句1执行的频度为；语句2执行的频度为3执行的频度为4执行的频度为。
8．在下面的程序段中，对ｘ的赋值语句的频度为__O(n3)___（表示为n 的函数）//1+（1+2++（1+2+3）+…+（1+2+…+n）=n(n+1)(n+2)/6
for(i＝1;i
for(j＝１;j
for(k＝1;k
ｘ＝ｘ＋delta；
9. 计算机执行下面的语句时，语句s 的执行次数为_(n+3)(n-2)/2______。
for(i=l；i
for(j=n;j>=i;j--)
s;
10. 下面程序段的时间复杂度为___O(n)_____。(n>1)
sum=1；
for (i=0;sum
四，应用题
1．1．什么是数据? 它与信息是什么关系?
信息就是消息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。
什么是数据？数据(data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。{语句2}{语句3}{语句4}
什么是数据结构? 数据结构是研究什么内容的学科？有关数据结构的讨论涉及哪三方面? 2．
数据结构是指数据以及相互之间的关系。记为：数据结构={D, R }。其中，D 是某一数据对象，R 是该对象中所有数据成员之间的关系的有限集合。
数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。
有关数据结构的讨论一般涉及以下三方面的内容：
（1）数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构；
（2）数据成员及其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构；
（3）施加于该数据结构上的操作。
数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。
3．评价一个好的算法，从哪几方面考虑？
评价好的算法有四个方面。一是算法的正确性；二是算法的易读性；三是算法的健壮性；四是算法的时空效率（运行）。
4．若将数据结构定义为一个二元组（D，R）,说明符号D，R应分别表示什么？
D 是数据元素的有限集合，R是D 上数据元素之间关系的有限集合。
5．解释算法与程序的区别？
算法是为了解决某类问题而规定的一个有限长的操作序列。
一个算法必须满足以下五个重要特性：
有穷性确定性可行性有输入有输出
算法与程序的联系和区别：
（1）算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。
一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止。因此，操作系统不是一个算法。
（2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。
（3）算法是面向功能的，通常用面向过程的方式描述；程序可以用面向对象方式搭建它的框架。
（4）算法与数据结构是相辅相承的：解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。
6．有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。
（1）A=（K ，R ），其中：
K={a，b ，c ，d ，e ，f ，g}
R={r}
r={〈a ，b 〉，〈b ，c 〉，〈c ，d 〉，〈d ，e 〉，〈e ，f 〉，〈f ，g 〉}
（2）B=（K ，R ），其中：
K={a，b ，c ，d ，e ，f ，g ，h}
R={r}
r={〈d ，b 〉，〈d ，g 〉，〈d ，a 〉，〈b ，c 〉，〈g ，e 〉，〈g ，h 〉，〈a ，f 〉}
（3）C=（K ，R ），其中：
K={1，2，3，4，5，6}
R={r}
r={(1,2) ，(2,3) ，（2，4），（3，4），（3，5），（3，6），（4，5），（4,6）}这里的圆括号对表示两结点是双向的。
（1）A
对应逻辑图形如下，它是一种线性结构。
（2）B
对应逻辑图形如下，它是一种树形结构。
（3）C
对应逻辑图形如下，它是一种图形结构。
7．分析以下程序段的时间复杂度。
（1）
a=0；b=1；①
for （i=2；i 〈=n；i++）②
{
s=a+b；③
b=a；④
a=S；⑤
}
（2）
inti ，j ，k ；
for （i=0；i 〈n ；i++〉①
for （j=0；j 〈n ；j++〉②
{
c[i][j]=0；③
for （k=0；k 〈n ；k++〉④
c[i][j]=c[i][j]+a[i][k]+b[k][j]；⑤
}
（1）解：
语句①的频度是2；
语句②的频度是n ；
语句③的频度是n-1；
语句④的频度是n-1；
语句⑤的频度是n-1；
故，该程序段的时间复杂度T （n ）=2+n+3*（n-1）=4n-1=O（n ）。
（2）解：
语句①的频度为n+1；
语句②作为语句①循环体内的语句应该执行n 次，但语句②本身要执行n+1次，故语句②的频度是n （n+1）；
同理可得语句③、④和⑤的频度分别是n2，n2（n+1）和n3。该程序段所有语句的频度之和为：
T （n ）=2n3+3n2+2n+1
其复杂度为O（n3）。
8．求下列算法段的语句频度及时间复杂度
（1）
for(i=1;i
for(j=1;j
x=x+1;
（2）
for （i=1;i
for (j=1;j
for (k=1;k
x=i+j-k;
（1）分析：该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固
2定，与外循环有关，因此，时间频度T(n)=1+2+3+…+n=n*(n+1)/2。有1/4≤T(n)/n≤1，
22故它的时间复杂度为Ｏ(n), 即Ｔ(n)与n 数量级相同。
（2）分析算法规律可知时间频度T(n)=1+(1+2)+(1+2+3)+...+(1+2+3+…+n)。由于有1/6≤
33T（n)/n ≤1，故时间复杂度为Ｏ(n)
第二章线性表
一，选择
1．在一个以h 为头的单循环链中，p指针指向链尾的条件是（A ）
A. p->next=hB. p->next=NILC. p->next->next=hD. p->data=-1
2．下面关于线性表的叙述中，错误的是哪一个？（B ）
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
3．线性表是具有n 个（C ）的有限序列（n>0）。
A．表元素B．字符C．数据元素D．数据项
4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A ）存储方式最节省时间。
A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表
5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D ）存储方式最节省运算时间。
A．单链表B．仅有头指针的单循环链表
C．双链表D．仅有尾指针的单循环链表
6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(D )最节省时间。
A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表
7．在带有头结点的单链中插入一个新结点时不可能修改（A ）。
A ．头指针B ．头结点指针域C ．开始结点指针域D ．其它结点指针域
8．双向链表中有两个指针域，llink和rlink，分别指向前驱及后继，设p 指向链表中的一个结点，q指向一待插入结点，现要求在p 前插入q，则正确的插入为（D ）。
A. p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=p->llink;
B. q->llink=p->llink;p->llink->rlink=q;q->rlink=p;p->llink=q->rlink;
C. q->rlink=p;p->rlink=q;p->llink->rlink=q;q->rlink=p;
D. p->llink->rlink=q;q->rlink=p;q->llink=p->llink;p->llink=q;
9．对于一个头指针为head 的带头结点的单链表，判定该表为空表的条件是（B ）。
A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL
10．在顺序表中查找第i 个元素的时间效率最高的算法时间复杂度是（A ）。
A ．O(1)B ．O() C ．O(log2n) D ．O(n)
11．最好的情况下，在顺序表中按值查找一个元素的算法时间复杂度是（D ）。
A ．O(n)B ．O(n ) C ．O(log2n) D ．O(1)
12. 若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为（C ）(1
2A. O(0)B. O(1)C. O(n)D. O(n)
13. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C ）。
A．O(n)O(n)B. O(n)O(1)C. O(1)O(n)D. O(1)O(1)
14．线性表（a1,a2,…,an）以链接方式存储时，访问第i 位置元素的时间复杂性为（C ）。
A．O（i）B．O（1）C．O（n）D．O（i-1）
15．非空的循环单链表head 的尾结点p 满足（A ）。
A．p->link=headB．p->link=NILC．p=NILD．p=head
二，判断
1. 链表中的头结点仅起到标识的作用。(×)
2．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。(√)
3．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。(×)
4．顺序存储方式只能用于存储线性结构。(×)
5．线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。(×)
6. 线性表的特点是每个元素都有一个前驱和一个后继。(×)
7. 取线性表的第i 个元素的时间同i 的大小有关。(×)
8. 循环链表不是线性表。(×)
9. 线性表就是顺序存储的表。(×)
10. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×)
三，填空
1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。
2．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（n-1）/2。
3．在一个长度为n 的顺序表中第i 个元素（1
4．对于一个具有n 个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为___O(1)_____,在给定值为x 的结点后插入一个新结点的时间复杂度为__O(n)__。
5．在双向循环链表中, 向p 所指的结点之后插入指针f 所指的结点，其操作是6. 在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句：
s->next=p；s->prior==s；
7.顺序存储结构通过物理上相邻表示元素之间的关系;链式存储结构通过指针表示元素之间的关系。
8. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共4个，单链表为2个。
9. 已知指针p 指向单链表L 中的某结点，则删除其后继结点的语句是：,时间复杂度是O(1); 。
10. 带头结点的双循环链表L 中只有一个元素结点的条件是L->next->next==L。四，算法设计
1LNode*Locate(LinkListL,int x)//链表上的元素查找, 返回指针
{
for(p=l->next;p&&p->data!=x;p=p->next);
return p;
}//Locate
int Length(LinkListL)//求链表的长度
{
for(k=0,p=L;p->next;p=p->next,k++);
return k;
}//Length
为（a void reverse(SqList&A)//顺序表的就地逆置
{
for(i=0,j=A.length-1;i
A.elem[i]A.elem[j];
}//reverse
void LinkList_reverse(Linklist&L)//链表的就地逆置; 为简化算法, 假设表长大于2
{
p=L->next;q=p->next;s=q->next;p->next=NULL;
while(s->next)
{
q->next=p;p=q;
q=s;s=s->next;//把L 的元素逐个插入新表表头
}
q->next=p;s->next=q;L->next=s;
}//LinkList_reverse
分析:本算法的思想是, 逐个地把L 的当前元素q 插入新的链表头部,p 为新表表头.
性表C 的算法，即使得
线性表A ，B 和C 均以单链表作存储结构，且C 表利用A 表和B 表中的结点空间构成。void merge1(LinkList&A,LinkList&B,LinkList&C)
//把链表A 和B 合并为C,A 和B 的元素间隔排列, 且使用原存储空间
{
p=A->next;q=B->next;C=A;
while(p&&q)
{
s=p->next;p->next=q;//将B 的元素插入
if(s)
{
t=q->next;q->next=s;//如A 非空, 将A 的元素插入
}
p=s;q=t;
}//while
}//merge1
第三章栈和队列
一，选择
1. 对于栈操作数据的原则是（B ）。
A. 先进先出B. 后进先出C. 后进后出D. 不分顺序
2. 已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有（B ）。
A. dacb B. cadb C. dbca D. badc
3. 最大容量为n 的循环队列，队尾指针是rear，队头是front，则队空的条件是（B ）。
A. (rear+1)MOD n=frontB. rear=front
C．rear+1=frontD. (rear-l)MOD n=front
4当利用大小为n 的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时首先应执行语句修改top 指针。（B ）
A ．top++B ．top--C ．top=0D ．top
5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p 1,p 2,p 3，…，pN ,若p N 是n，则p i 是(D )。
A. i B. n-i C. n-i+1D. 不确定
6. 一个递归算法必须包括（B ）。
A. 递归部分B. 终止条件和递归部分C. 迭代部分D.终止条件和迭代部分
7. 执行完下列语句段后，i值为：（B ）
int f(intx)
{return ((x>0)? x*f(x-1):2);}
int i ;
i =f(f(1));
A．2B. 4C. 8D. 无限递归
8. 设栈S 和队列Q 的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S 的容量至少应该是(C )。
A．6B. 4C. 3D. 2
9. 栈和队列的共同点是（C ）。
A. 都是先进先出B. 都是先进后出
C. 只允许在端点处插入和删除元素D. 没有共同点
10. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（D ）数据结构最佳。
A．线性表的顺序存储结构B. 队列C. 线性表的链式存储结构D. 栈
11. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时(D )。
A．仅修改队头指针B. 仅修改队尾指针
C. 队头、队尾指针都要修改D. 队头,队尾指针都可能要修改
12. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（C ）的数据结构。
A．队列B．多维数组C．栈D. 线性表
13. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front 和rear，则当前队列中的元素个数为（A ）。
A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m
14. 循环队列存储在数组A[0..m]中，则入队时的操作为（D ）。
A. rear=rear+1B. rear=(rear+1)mod (m-1)
C. rear=(rear+1)mod m D. rear=(rear+1)mod(m+1)
15. 若用一个大小为6的数组来实现循环队列，且当前rear 和front 的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front 的值分别为多少？(B )
A. 1和5B. 2和4C. 4和2D. 5和1
二，判断
1.
2.
3.
4. 任何一个递归过程都可以转换成非递归过程。（√）只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。（×）队列逻辑上是一个下端和上端既能增加又能减少的线性表。（√）循环队列也存在空间溢出问题。（√）循环队列只是一个大小为maxsize 的数组空间有限自然存在溢出问题
5. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（√）
三，填空
1．栈是限定仅在表尾进行插入或删除操作的线性表。
3．中缀表达式3*（x+2）-5所对应的后缀表达式为；后缀表达式“45*32+-”的值为15。
4. 顺序栈用data[1..n]存储数据，栈顶指针是top, 则值为x 的元素入栈的操作是data[++top]=x；。
5．向一个循环队列中插入一元素时，需首先移动，然后再向所指位置6．用下标0开始的N 元数组实现循环队列时，为实现下标变量M 加1后在数组有效下标范围内循环，可采用的表达式是：M=7．用长度为n 的数组顺序存储一个栈时，若用top==n表示栈空，则表示栈满的条件为四，应用题
1．链栈中为何不设置头结点?
链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。
2．指出下列程序段的功能
(1)void Demo1(SeqStack*S){
int i; arr[64]; n=0;
while (StackEmpty(S))arr[n++]=Pop(S);
for (i=0,i
}//Demo1
(1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。
(2)SeqStack S1, S2, tmp;
DataType x;
...//假设栈tmp 和S2已做过初始化
while (! StackEmpty (&S1))
{
x=Pop(&S1);
Push(&tmp,x);
}
while (! StackEmpty (&tmp))
{
x=Pop(&tmp);
Push(&S1,x);Push(&S2,x); }
(2)程序段的功能是利用tmp 栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。3. 试证明：若借助栈由输入序列1,2,…,n得到输出序列为P 1,P 2,…,Pn （它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着i
如果i p j 的情况，则说明要将p j 压到p i 之上，也就是在p j 出栈之后p i 才能出栈。这就说明，对于i
具体解答(提示：用反证法) ：
因为借助栈由输入序列1, 2, 3, …, n ，可得到输出序列p 1, p 2, p 3, …, p n ，如果存在下标i, j, k ，满足i
①i 进栈，i 出栈，j 进栈，j 出栈，k 进栈，k 出栈。此时具有最小值的排在最前面p i
位置，具有中间值的排在其后p j 位置，具有最大值的排在p k 位置，有p i
②i 进栈，i 出栈，j 进栈，k 进栈，k 出栈，j 出栈。此时具有最小值的排在最前面p i
位置，具有最大值的排在p j 位置，具有中间值的排在最后p k 位置，有p i
③i 进栈，j 进栈，j 出栈，i 出栈，k 进栈，k 出栈。此时具有中间值的排在最前面p i
位置，具有最小值的排在其后p j 位置，有p j
④i 进栈，j 进栈，j 出栈，k 进栈，k 出栈，i 出栈。此时具有中间值的排在最前面p i 位置，具有最大值的排在其后p j 位置，具有最小值的排在p k 位置，有p k
⑤i 进栈，j 进栈，k 进栈，k 出栈，j 出栈，i 出栈。此时具有最大值的排在最前面p i 位置，具有中间值的排在其后p j 位置，具有最小值的排在p k 位置，有p k
4．举例说明顺序队的“假溢出”现象，并给出解决方案。
设顺序存储队列用一维数组q[m]表示，其中m 为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front 指向队头元素的前一位置，rear指向队尾元素。当front 等于-1时队空，rear等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear 等于m-1时，若front 不等于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾相连，即循环队列（0..m-1）。在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1）%m=front，m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。
五，算法设计题
1．回文是指正读反读均相同的字符序列，如"abba" 和"abdba" 均是回文，但"good" 不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈) 根据提示，算法可设计为：//以下为顺序栈的存储结构定义
#defineStackSize 100//假定预分配的栈空间最多为100个元素typedef char DataType;//假定栈元素的数据类型为字符typedef struct{
DataType data[StackSize];int top; }SeqStack;
int IsHuiwen(char *t)
{//判断t 字符向量是否为回文，若是，返回1，否则返回0
SeqStack s; int i , len; char temp;
InitStack(&s);
len=strlen(t);//求向量长度
for (i=0;i
Push(&s,t[i]);
while(!EmptyStack(&s))
{//每弹出一个字符与相应字符比较
temp=Pop(&s);if(temp!=S[i])return 0;//不等则返回0else i++;}
return 1; //比较完毕均相等则返回1}
2．一个双向栈S 是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化InitStack (S ) 、入栈Push(S , i , x) 和出栈Pop(S , i ) 等算法，其中i 为0或1，用以表示栈号。
双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空间可以充分利用。双向栈的算法设计如下：//双向栈的栈结构类型与以前定义略有不同
#defineStackSize 100//假定分配了100个元素的向量空间#definechar DataType typedef struct{
DataType Data[StackSize]int top0; //需设两个指针int top1; }DblStack
void InitStack(DblStack *S) {//初始化双向栈
S->top0=-1;
S->top1=StackSize; //top2也指出了向量空间，但由于是作为栈底，因此不会出错}
int EmptyStack(DblStack *S,int i ) {//判栈空(栈号i)
return (i==0&&S->top0==-1||i ==1&&S->top1==StackSize) ; }
int FullStack(DblStack *S){//判栈满,满时两头相遇
return (S->top0==S-top1-1); }
void Push(DblStack*S,int i, DataType x) {//进栈(栈号i)
if (FullStack(S ))
Error("Stackoverflow");//上溢、退出运行
if (i ==0) S->Data[++S->top0]=x; //栈0入栈if (i ==1) S->Data[--S->top1]=x; //栈1入栈}
DataType Pop(DblStack*S,int i) {//出栈(栈号i)
if (EmptyStack(S,i) )
Error("Stackunderflow");//下溢退出if(i==0)
return (S->Data[S->top0--]);//返回栈顶元素，指针值减1if(i==1)
return (S->Data[S->top1++]); //因这个栈以另一端为底，所以指针值加1。
}
第四章
一，选择
串
1．下面关于串的的叙述中，哪一个是不正确的？（B ）
A．串是字符的有限序列B．空串是由空格构成的串
C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．设有两个串p 和q，其中q 是p 的子串，求q 在p 中首次出现的位置的算法称为（C ）
A．求子串B．联接C．匹配D．求串长3．串的长度是指（B ）
A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数4．若串S=’software’,其子串的数目是（B ）。
A．8B．37C．36D．9二，填空
1．空格串是指由空格字符（ASCII值32）所组成的字符串，其长度等于空格个数。2．组成串的数据元素只能是_。
3．一个字符串中任意个连续的字符组成的子序列称为该串的子串。
4．INDEX（‘DATASTRUCTURE’，‘STR’）=5。
5．设正文串长度为n，模式串长度为m，则串匹配的KMP 算法的时间复杂度为6．模式串P=‘abaabcac’的next 函数值序列为7．设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为模式匹配，又称P 为模第五章数组和广义表
一，选择
1. 已知广义表L=（（x,y,z），a，（u，t，w）），从L 表中取出原子项t 的运算是（D ）。
A. head（tail（tail（L）））B. tail（head（head（tail（L））））C. head （tail（head（tail（L））））D. head （tail(head（tail（tail（L）））)）2. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（D ）。
Head(Tail(Head(Tail(Tail(A)))))A. (g)B. (d)C. c D. d 3.稀疏矩阵一般的压缩存储方法有两种,即（C ）
A．二维数组和三维数组B．三元组和散列C．三元组和十字链表D．散列和十字链表
4. 二维数组A 的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A 按行先存储，元素A[8,5]的起始地址与当A 按列先存储时的元素（B ）的起始地址相同。设每个字符占一个字节。
A. A[8,5]B. A[3,10]C. A[5,8]D. A[0,9]5. 对稀疏矩阵进行压缩存储目的是（C ）。
A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度
6. 设A 是n*n的对称矩阵，将A 的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素a ij (1≤i，j≤n，且i≤j)在B 中的位置为(B )。
A. i(i-l)/2+jB. j(j-l)/2+iC. j(j-l)/2+i-1D. i(i-l)/2+j-17. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k 是（B ）。
A．i（i-1）/2+jB．j（j-1）/2+iC．i（j-i）/2+1D．j（i-1）/2+18. 设广义表L=（（a,b,c）），则L 的长度和深度分别为（C ）。
A. 1和1B. 1和3C. 1和2D. 2和39. 数组A[0..4,-1..-3,5..7]中含有元素的个数（B ）。
A．55B．45C．36D．1610. 下面说法不正确的是(A )。
A. 广义表的表头总是一个广义表B. 广义表的表尾总是一个广义表C. 广义表难以用顺序存储结构D. 广义表可以是一个多层次的结构二，判断
1．一个稀疏矩阵A m*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m 和n 的值互换，则就完成了A m*n的转置运算。（×）
2. 从逻辑结构上看，n维数组的每个元素均属于n 个向量。（√）3. 稀疏矩阵压缩存储后，必会失去随机存取功能。（√）
4. 对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（√）5. 数组可看成线性结构的一种推广，因此与线性表一样可对它进行插入，删除操作。（×）
6. 所谓取广义表的表尾就是返回广义表中最后一个元素。（×）7. 二维以上的数组其实是一种特殊的广义表。（√）
8. 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（×）9. 若一个广义表的表头为空表，则此广义表亦为空表。（×）
10. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（×四应用题
1. 画出下列广义表的两种存储结构图((),A,(B,(C,D)),(E,F))。2. 设某表H 如下：
A
a1
a2
B b1
c1
C
c2
X
）
其中A,B,C 为子表名，a1,a2,b1,c1,c2,x为其元素。
试用广义表形式表示H,并写出运算HEAD(H)和TAIL(H)函数从H 中取出单元素a2的运算；（1）H(A(a1,a 2）,B(b1）,C(c1，c2）,x）
HEAD(TAIL(HEAD(H)))=a2五，算法设计
1．设任意n 个整数存放于数组A(1:n)中，试编写程序，将所有正数排在所有负数前面
本题属于排序问题，只是排出正负，不排出大小。可在数组首尾设两个指针i 和j，i自小至大搜索到负数停止，j自大至小搜索到正数停止。然后i 和j 所指数据交换，继续以上过程，直到i=j为止。
void Arrange(intA[],intn)
//n个整数存于数组A 中，本算法将数组中所有正数排在所有负数的前面{inti=0,j=n-1,x;//用类C 编写，数组下标从0开始while(i
{while(i0)i++;while(i
if(i
}//算法Arrange 结束.
[算法讨论]对数组中元素各比较一次，比较次数为n。最佳情况(已排好,正数在前,负数在后)不发生交换，最差情况(负数均在正数前面)发生n/2次交换。用类c 编写，数组界偶是0..n-1。空间复杂度为O(1).
2.设二维数组a[1..m,1..n]含有m*n个整数。判断a 中所有元素是否互不相同?输出相关信息(yes/no)。
判断二维数组中元素是否互不相同，只有逐个比较,找到一对相等的元素，就可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次？在当前行，每个元素要同本行后面的元素比较一次（下面第一个循环控制变量p 的for 循环），然后同第i+1行及以后各行元素比较一次，这就是循环控制变量k 和p 的二层for 循环。
int JudgEqual(inga[m][n],intm,n)
//判断二维数组中所有元素是否互不相同，如是，返回1；否则，返回0。{for(i=0;i
{for(p=j+1;p
if(a[i][j]==a[i][p]){printf(“no”);return(0);}
//只要有一个相同的，就结论不是互不相同
for(k=i+1;k
if(a[i][j]==a[k][p]){printf(“no”);return(0);}
}//for(j=0;j
printf(yes”);return(1);//元素互不相同}//算法JudgEqual 结束
第6章树和二叉树
一选择
1．算术表达式a+b*（c+d/e）转为后缀表达式后为（B ）
A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++2. 在下述结论中，正确的是（D ）
①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换;
④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④3．具有10个叶结点的二叉树中有（B ）个度为2的结点，
A．8B．9C．10D．ll4. 有n 个叶子的哈夫曼树的结点总数为（D ）。
A．不确定B．2nC．2n+1D．2n-15．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（A ）。
A．CBEFDAB．FEDCBA C．CBEDFA D．不定
6．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（D ）。
A．acbedB．decabC．deabcD．cedba
7．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（B ）
A．都不相同B．完全相同C．先序和中序相同，而与后序不同D．中序和后序相同，而与先序不同
8．n个结点的线索二叉树上含有的线索数为（C ）
A．2nB．n－lC．n＋lD．n9．深度为k 的二叉树，结点数最多有（B ）A ．2k B ．2k -1C ．2k-1
D ．2k-1-1
10．判断线索二叉树中某结点p 有左孩子的条件是（C ）A ．p!=NULLB ．p->lchild!=NULLC ．p->ltag=0D ．p->ltag=1二、基础知识题
1．列出右图所示二叉树的叶结点、分支结点和每个结点的层次。
二叉树的叶结点有⑥、⑧、⑨。分支结点有①、②、③、④、⑤、⑦。
结点①的层次为1；结点②、③的层次为2；结点④、⑤、⑥的层次为3；结点⑦、⑧的层次为4；结点⑨的层次为5。
2．使用（1）顺序表示和（2）二叉链表表示法，
分别画出右图所示二叉树的存储表示。
（1）顺序表示
01
①
②
2③10
3④11
45⑤12⑧
6⑥
13
78⑦
9
14151617⑨
（2）二叉链表表示
试画出3个结点的二叉树的所有不同形态。
3.设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的
编码最短。
字符A，B，C，D出现的次数为9,1,5,3。其哈夫曼编码如下A:1，B:000，C:01，D:001
第七章图
一，选择
1．图中有关路径的定义是（A ）。
A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是2．设无向图的顶点个数为n，则该图最多有（B ）条边。
A．n-1B．n(n-1)/2C．n(n+1)/2D．03．一个n 个顶点的连通无向图，其边的个数至少为（A ）。
A．n-1B．nC．n+1D．nlogn；4．要连通具有n 个顶点的有向图，至少需要（B ）条边。
A．n-lB．nC．n+lD．2n5．n个结点的完全有向图含有边的数目（D ）。
A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）6. 求解最短路径的Floyd 算法的时间复杂度为(D )。
A．O（n）B. O（n+c）C. O（n*n）D. O（n*n*n）7．已知有向图G=(V,E)，其中V={V1,V 2,V 3,V 4,V 5,V 6,V 7}，
E={,,,,,,,,},G的拓扑序列是（A ）。
A．V1,V 3,V 4,V 6,V 2,V 5,V 7B．V1,V 3,V 2,V 6,V 4,V 5,V 7C．V1,V 3,V 4,V 5,V 2,V 6,V 7D．V1,V 2,V 5,V 3,V 4,V 6,V 7
8. 在用邻接表表示图时，拓扑排序算法时间复杂度为(B )。
A. O(n)B. O(n＋e)C. O(n*n)D. O(n*n*n)9．有n 个结点的有向完全图的边数是（C ）A ．n 2B ．2n C ．n （n-1）D ．2n （n+1）10．下列哪一种图的邻接矩阵是对称矩阵？（B ）
A．有向图B．无向图C．AOV网D．AOE网11．当一个有N 个顶点的图用邻接矩阵A 表示时，顶点Vi 的度是（B ）。
A．
∑A [i , j ]
i =1
n
B．
∑A [i , j ]
j =1
n
C．
∑A [j , i ]
i =1
n
D．
A [j , i ]∑A [i , j ]∑j =1
i =1
n
n
+
12．对图做宽度优先遍历时会使用何种数据结构(A )
A ．队列B ．树C ．栈D ．集合
13．无向图G=(V,E),其中：V={a,b,c,d,e,f},
E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（D ）。
A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b14．下列关于AOE 网的叙述中，不正确的是（B ）。
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成C．所有的关键活动提前完成，那么整个工程将会提前完成D．某些关键活动提前完成，那么整个工程将会提前完成15．下面哪一方法可以判断出一个有向图是否有环（B ）：
A．深度优先遍历B. 拓扑排序C. 求最短路径D. 求关键路径二，判断
1.树中的结点和图中的顶点就是指数据结构中的数据元素。（√）
2．一个图G 有n 个顶点，n -1条边，则该图可以看成是G 的一棵生成树。(×)
3．如果AOE 网中某一个关键活动延迟一天，则整个工程将延期一天。反之，如果缩短该关键活动的持续时间，则一定可使整个工程提前完工。(×) 4. 有e 条边的无向图，在邻接表中有e 个结点。（×）
5. 有向图中顶点V 的度等于其邻接矩阵中第V 行中的1的个数。（×）6．强连通图的各顶点间均可达。（√）
7．强连通分量是无向图的极大强连通子图。（×）8．连通分量指的是有向图中的极大连通子图。（×）
9．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（×）10. 在图G 的最小生成树G1中，可能会有某条边的权值超过未选边的权值。（√）四，应用题
1．画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。2
．给出右图的邻接矩阵、领接表表示。
3．对下图所示的连通图，请分别用普里姆（Prim ）和克鲁斯卡尔（Kruskal ）算法构造其最
小生成树。
4．已知某图的邻接表为
（1）．写出此邻接表对应的邻接矩阵；
（2）．写出由v1开始的深度优先遍历的序列；时间复杂度是多少？（4）．写出由v1开始的广度优先遍历的序列；时间复杂度是多少？
（2）V1V2V5V3V4V6(4)V1V2V3V4V5V6
5．画出下图所示的AOV
网的所有拓扑有序序列。
共有8种：
ADBECF DABECF
ADBEFC DABEFC ADEBCF DAEBCF ADEBFC DAEBFC
6．对图所示的有向图，试利用Dijkstra 算法求出从源点1
到其他各顶点的最短路径，
从顶点1到其他各顶点的最短路径及距离如下：
1→3（15）1→3→2（19）1→3→6→4（29）1→3→2→5（29）1→3→6（25）
第九、十章
1. 基于比较方法的n 个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是（A ）。
A. O(nlogn)B. O(logn)C. O(n)D. O(n*n)
2．快速排序法在下列哪种情况下最不利于发挥其长处（C ）
A ．被排序的数据量太大
B ．被排序的数据中含有多个相同的关键字C ．被排序的数据已基本有序D ．被排序的数据完全无序
3．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（A ）排序为宜。
A．直接插入B．直接选择C．堆D．快速
4．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（C ）。
A. 快速排序B. 堆排序C. 归并排序D. 直接插入排序5. 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为（C ）
A．-1，4，8，9，20，7，15，7B．-1，7，15，7，4，8，20，9C．-1，4，7，8，20，15，7，9D．A，B，C均不对。6．归并排序的时间复杂度是（B ）
A ．O （n 2）B ．O （nlog 2n ）
C ．O （n ）
D ．O （log 2n ）
7．折半查找排序的时间复杂度是（A ）
A ．O （n 2）B ．O （nlog 2n ）C ．O （n ）D ．O （log 2n ）
8．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（D ）。
A．直接插入排序B. 气泡排序C. 快速排序D. 直接选择排序
9．将两个各有N 个元素的有序表归并成一个有序表,其最少的比较次数是(A )
A．NB．2N-1C．2ND．N-1
10．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（C ）。
A．(38,40,46,56,79,84)B. (40,38,46,79,56,84)
C．(40,38,46,56,79,84)D. (40,38,46,84,56,79)
11. 采用简单选择排序，比较次数与移动次数分别为(C )。
A. O（n）,O(logn)B. O(logn),0(n*n)C. 0(n*n),0(n)D. 0(nlogn),0(n)
12. 对序列{15，9，7，8，20，-1，4，}用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是(B )
A. l B. 4C. 3D. 2
13．对下列关键字序列用快速排序法进行排序时，速度最快的情形是（A ）。
A．{21,25,5,17,9,23,30}B．{25,23,30,17,21,5,9}
C．{21,9,17,30,25,23,5}Ｄ．{5,9,17,21,23,25,30}
14. 快速排序方法在（D ）情况下最不利于发挥其长处。
A. 要排序的数据量太大B. 要排序的数据中含有多个相同值
C. 要排序的数据个数为奇数D. 要排序的数据已基本有序
15．某顺序存储的表格中有90000个元素，已按关键字值额定升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字的值皆不相同。用顺序查找法查找时，平均比较次数约为（C ）
A ．25000B ．30000C ．45000D ．90000
二、判断
1．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（√）
2．内排序要求数据一定要以顺序方式存储。（×）
3．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（×）
4．直接选择排序算法在最好情况下的时间复杂度为O（N）。（×）
5．两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（×）
6．在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n )。（×）
7．利用关键字比较进行排序的算法，最好情况下时间复杂性为O (n log n ) 。(×)
8．堆肯定是一棵平衡二叉树。（×）
9．堆是满二叉树。（×）
10.简单选择排序是一种稳定的排序方法。(√)
三、应用
1. 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：
(1)归并排序每归并一次书写一个次序。
(2)快速排序每划分一次书写一个次序。
(3)堆排序先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。
2．对关键字{45,24, 53, 45, 12, 24, 90}，给出二叉排序树的构造过程。假设这6个记录的查
找概率相同，求查找成功时的ASL 。
3．已知一组关键字为(19,14,23,01,68,20,84,27,55,11,10,79)，哈希函数为：H(key)=keyMOD 13，用线性探测再散列法处理冲突，构造哈希表a[0..15]。计算等概率情况下查找成功时的平均查找长度ASL 。
4．关键码集合如下：｛[1**********]3
排序，画出堆排序的初态、建堆和重建堆的过程。27｝，用堆排序方法从小到大
第一章绪论
一，选择题
1．组成数据的基本单位是（C ）
A ．数据项B ．数据类型C ．数据元素D ．数据变量
2．数据结构是研究数据的（C ）以及它们之间的相互关系。
A ．理想结构，物理结构B ．理想结构，抽象结构
C ．物理结构，逻辑结构D ．抽象结构，逻辑结构
3．算法分析的两个主要方面是（D ）
A ．正确性和简单性B ．可读性和文档性
C ．数据复杂性和程序复杂性D ．时间复杂度和空间复杂度
4．算法分析的目的是（C ）。
A ．找出数据结构的合理性B ．研究算法中的输入和输出的关系
C ．分析算法的效率以求改进D ．分析算法的易懂性和文档性
5. 算法的时间复杂度取决于（C ）
A．问题的规模B. 待处理数据的初态C. A 和B Ｄ．以上都不是
6．一个算法应该是（B ）。
A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.
7. 下面关于算法说法错误的是（D ）
A．算法最终必须由计算机程序实现
B.为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的
8．从逻辑上可以把数据结构分为（C ）两大类。
A．动态结构、静态结构B．顺序结构、链式结构
C．线性结构、非线性结构D．初等结构、构造型结构
9．程序段for (i=n-1;i>=1;i--)
for (j=1;j
if(A[j]>A[j+1])
A[j]与A[j+1]对换；
其中n 为正整数，则最后一行的语句频度在最坏情况下是（D ）
A ．O （n ）B ．O(nlogn)C. ．O(n3) D ．O(n2)
10．连续存储设计时，存储单元的地址（A ）。
A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续
二，判断题
1．数据结构的抽象操作的定义与具体实现有关。(×)
2．数据结构是数据对象与对象中数据元素之间关系的集合。（√）
3．在顺序存储结构中，有时也存储数据结构中元素之间的关系。(×)
4．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用的需要建立的。（√）
5．算法和程序原则上没有区别，在讨论数据结构是两者是通用的。(×)
6．同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。(×)
7．数据的逻辑结构与数据元素本身的内容和形式无关。（√）
8．算法的优劣与算法描述语言无关，但与所用计算机有关。(×)
9．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（√）
10．算法可以用不同的语言描述，如果用C 语言或PASCAL 语言等高级语言来描述，则算法实际上就是程序了。(×)
三，填空
1．数据的物理结构包括数据元素的表示和数据元素间关系的表示。
2. 对于给定的n 个元素,可以构造出的逻辑结构有，，__图状结构或网状结构_四种。
3．一个数据结构在计算机中称为存储结构。
4．抽象数据类型的定义仅取决于它的一组_实现_无关，即不论其内部结构如何变化，只要它的_数学特性_不变，都不影响其外部使用。
5．线性结构中元素之间存在关系, 树形结构中元素之间存在关系, 图形结构中元素之间存在6．一个算法有5个特性:，有零个或多个输入、有一个或多个输出。
7．已知如下程序段
for （i=n ；i
{
x:=x+1；
for(j=n;j
y:=y+1;
}
语句1执行的频度为；语句2执行的频度为3执行的频度为4执行的频度为。
8．在下面的程序段中，对ｘ的赋值语句的频度为__O(n3)___（表示为n 的函数）//1+（1+2++（1+2+3）+…+（1+2+…+n）=n(n+1)(n+2)/6
for(i＝1;i
for(j＝１;j
for(k＝1;k
ｘ＝ｘ＋delta；
9. 计算机执行下面的语句时，语句s 的执行次数为_(n+3)(n-2)/2______。
for(i=l；i
for(j=n;j>=i;j--)
s;
10. 下面程序段的时间复杂度为___O(n)_____。(n>1)
sum=1；
for (i=0;sum
四，应用题
1．1．什么是数据? 它与信息是什么关系?
信息就是消息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。
什么是数据？数据(data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。{语句2}{语句3}{语句4}
什么是数据结构? 数据结构是研究什么内容的学科？有关数据结构的讨论涉及哪三方面? 2．
数据结构是指数据以及相互之间的关系。记为：数据结构={D, R }。其中，D 是某一数据对象，R 是该对象中所有数据成员之间的关系的有限集合。
数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。
有关数据结构的讨论一般涉及以下三方面的内容：
（1）数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构；
（2）数据成员及其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构；
（3）施加于该数据结构上的操作。
数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。
3．评价一个好的算法，从哪几方面考虑？
评价好的算法有四个方面。一是算法的正确性；二是算法的易读性；三是算法的健壮性；四是算法的时空效率（运行）。
4．若将数据结构定义为一个二元组（D，R）,说明符号D，R应分别表示什么？
D 是数据元素的有限集合，R是D 上数据元素之间关系的有限集合。
5．解释算法与程序的区别？
算法是为了解决某类问题而规定的一个有限长的操作序列。
一个算法必须满足以下五个重要特性：
有穷性确定性可行性有输入有输出
算法与程序的联系和区别：
（1）算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。
一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止。因此，操作系统不是一个算法。
（2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。
（3）算法是面向功能的，通常用面向过程的方式描述；程序可以用面向对象方式搭建它的框架。
（4）算法与数据结构是相辅相承的：解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。
6．有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。
（1）A=（K ，R ），其中：
K={a，b ，c ，d ，e ，f ，g}
R={r}
r={〈a ，b 〉，〈b ，c 〉，〈c ，d 〉，〈d ，e 〉，〈e ，f 〉，〈f ，g 〉}
（2）B=（K ，R ），其中：
K={a，b ，c ，d ，e ，f ，g ，h}
R={r}
r={〈d ，b 〉，〈d ，g 〉，〈d ，a 〉，〈b ，c 〉，〈g ，e 〉，〈g ，h 〉，〈a ，f 〉}
（3）C=（K ，R ），其中：
K={1，2，3，4，5，6}
R={r}
r={(1,2) ，(2,3) ，（2，4），（3，4），（3，5），（3，6），（4，5），（4,6）}这里的圆括号对表示两结点是双向的。
（1）A
对应逻辑图形如下，它是一种线性结构。
（2）B
对应逻辑图形如下，它是一种树形结构。
（3）C
对应逻辑图形如下，它是一种图形结构。
7．分析以下程序段的时间复杂度。
（1）
a=0；b=1；①
for （i=2；i 〈=n；i++）②
{
s=a+b；③
b=a；④
a=S；⑤
}
（2）
inti ，j ，k ；
for （i=0；i 〈n ；i++〉①
for （j=0；j 〈n ；j++〉②
{
c[i][j]=0；③
for （k=0；k 〈n ；k++〉④
c[i][j]=c[i][j]+a[i][k]+b[k][j]；⑤
}
（1）解：
语句①的频度是2；
语句②的频度是n ；
语句③的频度是n-1；
语句④的频度是n-1；
语句⑤的频度是n-1；
故，该程序段的时间复杂度T （n ）=2+n+3*（n-1）=4n-1=O（n ）。
（2）解：
语句①的频度为n+1；
语句②作为语句①循环体内的语句应该执行n 次，但语句②本身要执行n+1次，故语句②的频度是n （n+1）；
同理可得语句③、④和⑤的频度分别是n2，n2（n+1）和n3。该程序段所有语句的频度之和为：
T （n ）=2n3+3n2+2n+1
其复杂度为O（n3）。
8．求下列算法段的语句频度及时间复杂度
（1）
for(i=1;i
for(j=1;j
x=x+1;
（2）
for （i=1;i
for (j=1;j
for (k=1;k
x=i+j-k;
（1）分析：该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固
2定，与外循环有关，因此，时间频度T(n)=1+2+3+…+n=n*(n+1)/2。有1/4≤T(n)/n≤1，
22故它的时间复杂度为Ｏ(n), 即Ｔ(n)与n 数量级相同。
（2）分析算法规律可知时间频度T(n)=1+(1+2)+(1+2+3)+...+(1+2+3+…+n)。由于有1/6≤
33T（n)/n ≤1，故时间复杂度为Ｏ(n)
第二章线性表
一，选择
1．在一个以h 为头的单循环链中，p指针指向链尾的条件是（A ）
A. p->next=hB. p->next=NILC. p->next->next=hD. p->data=-1
2．下面关于线性表的叙述中，错误的是哪一个？（B ）
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
3．线性表是具有n 个（C ）的有限序列（n>0）。
A．表元素B．字符C．数据元素D．数据项
4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A ）存储方式最节省时间。
A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表
5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D ）存储方式最节省运算时间。
A．单链表B．仅有头指针的单循环链表
C．双链表D．仅有尾指针的单循环链表
6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(D )最节省时间。
A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表
7．在带有头结点的单链中插入一个新结点时不可能修改（A ）。
A ．头指针B ．头结点指针域C ．开始结点指针域D ．其它结点指针域
8．双向链表中有两个指针域，llink和rlink，分别指向前驱及后继，设p 指向链表中的一个结点，q指向一待插入结点，现要求在p 前插入q，则正确的插入为（D ）。
A. p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=p->llink;
B. q->llink=p->llink;p->llink->rlink=q;q->rlink=p;p->llink=q->rlink;
C. q->rlink=p;p->rlink=q;p->llink->rlink=q;q->rlink=p;
D. p->llink->rlink=q;q->rlink=p;q->llink=p->llink;p->llink=q;
9．对于一个头指针为head 的带头结点的单链表，判定该表为空表的条件是（B ）。
A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL
10．在顺序表中查找第i 个元素的时间效率最高的算法时间复杂度是（A ）。
A ．O(1)B ．O() C ．O(log2n) D ．O(n)
11．最好的情况下，在顺序表中按值查找一个元素的算法时间复杂度是（D ）。
A ．O(n)B ．O(n ) C ．O(log2n) D ．O(1)
12. 若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为（C ）(1
2A. O(0)B. O(1)C. O(n)D. O(n)
13. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C ）。
A．O(n)O(n)B. O(n)O(1)C. O(1)O(n)D. O(1)O(1)
14．线性表（a1,a2,…,an）以链接方式存储时，访问第i 位置元素的时间复杂性为（C ）。
A．O（i）B．O（1）C．O（n）D．O（i-1）
15．非空的循环单链表head 的尾结点p 满足（A ）。
A．p->link=headB．p->link=NILC．p=NILD．p=head
二，判断
1. 链表中的头结点仅起到标识的作用。(×)
2．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。(√)
3．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。(×)
4．顺序存储方式只能用于存储线性结构。(×)
5．线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。(×)
6. 线性表的特点是每个元素都有一个前驱和一个后继。(×)
7. 取线性表的第i 个元素的时间同i 的大小有关。(×)
8. 循环链表不是线性表。(×)
9. 线性表就是顺序存储的表。(×)
10. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×)
三，填空
1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。
2．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（n-1）/2。
3．在一个长度为n 的顺序表中第i 个元素（1
4．对于一个具有n 个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为___O(1)_____,在给定值为x 的结点后插入一个新结点的时间复杂度为__O(n)__。
5．在双向循环链表中, 向p 所指的结点之后插入指针f 所指的结点，其操作是6. 在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句：
s->next=p；s->prior==s；
7.顺序存储结构通过物理上相邻表示元素之间的关系;链式存储结构通过指针表示元素之间的关系。
8. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共4个，单链表为2个。
9. 已知指针p 指向单链表L 中的某结点，则删除其后继结点的语句是：,时间复杂度是O(1); 。
10. 带头结点的双循环链表L 中只有一个元素结点的条件是L->next->next==L。四，算法设计
1LNode*Locate(LinkListL,int x)//链表上的元素查找, 返回指针
{
for(p=l->next;p&&p->data!=x;p=p->next);
return p;
}//Locate
int Length(LinkListL)//求链表的长度
{
for(k=0,p=L;p->next;p=p->next,k++);
return k;
}//Length
为（a void reverse(SqList&A)//顺序表的就地逆置
{
for(i=0,j=A.length-1;i
A.elem[i]A.elem[j];
}//reverse
void LinkList_reverse(Linklist&L)//链表的就地逆置; 为简化算法, 假设表长大于2
{
p=L->next;q=p->next;s=q->next;p->next=NULL;
while(s->next)
{
q->next=p;p=q;
q=s;s=s->next;//把L 的元素逐个插入新表表头
}
q->next=p;s->next=q;L->next=s;
}//LinkList_reverse
分析:本算法的思想是, 逐个地把L 的当前元素q 插入新的链表头部,p 为新表表头.
性表C 的算法，即使得
线性表A ，B 和C 均以单链表作存储结构，且C 表利用A 表和B 表中的结点空间构成。void merge1(LinkList&A,LinkList&B,LinkList&C)
//把链表A 和B 合并为C,A 和B 的元素间隔排列, 且使用原存储空间
{
p=A->next;q=B->next;C=A;
while(p&&q)
{
s=p->next;p->next=q;//将B 的元素插入
if(s)
{
t=q->next;q->next=s;//如A 非空, 将A 的元素插入
}
p=s;q=t;
}//while
}//merge1
第三章栈和队列
一，选择
1. 对于栈操作数据的原则是（B ）。
A. 先进先出B. 后进先出C. 后进后出D. 不分顺序
2. 已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有（B ）。
A. dacb B. cadb C. dbca D. badc
3. 最大容量为n 的循环队列，队尾指针是rear，队头是front，则队空的条件是（B ）。
A. (rear+1)MOD n=frontB. rear=front
C．rear+1=frontD. (rear-l)MOD n=front
4当利用大小为n 的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时首先应执行语句修改top 指针。（B ）
A ．top++B ．top--C ．top=0D ．top
5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p 1,p 2,p 3，…，pN ,若p N 是n，则p i 是(D )。
A. i B. n-i C. n-i+1D. 不确定
6. 一个递归算法必须包括（B ）。
A. 递归部分B. 终止条件和递归部分C. 迭代部分D.终止条件和迭代部分
7. 执行完下列语句段后，i值为：（B ）
int f(intx)
{return ((x>0)? x*f(x-1):2);}
int i ;
i =f(f(1));
A．2B. 4C. 8D. 无限递归
8. 设栈S 和队列Q 的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S 的容量至少应该是(C )。
A．6B. 4C. 3D. 2
9. 栈和队列的共同点是（C ）。
A. 都是先进先出B. 都是先进后出
C. 只允许在端点处插入和删除元素D. 没有共同点
10. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（D ）数据结构最佳。
A．线性表的顺序存储结构B. 队列C. 线性表的链式存储结构D. 栈
11. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时(D )。
A．仅修改队头指针B. 仅修改队尾指针
C. 队头、队尾指针都要修改D. 队头,队尾指针都可能要修改
12. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（C ）的数据结构。
A．队列B．多维数组C．栈D. 线性表
13. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front 和rear，则当前队列中的元素个数为（A ）。
A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m
14. 循环队列存储在数组A[0..m]中，则入队时的操作为（D ）。
A. rear=rear+1B. rear=(rear+1)mod (m-1)
C. rear=(rear+1)mod m D. rear=(rear+1)mod(m+1)
15. 若用一个大小为6的数组来实现循环队列，且当前rear 和front 的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front 的值分别为多少？(B )
A. 1和5B. 2和4C. 4和2D. 5和1
二，判断
1.
2.
3.
4. 任何一个递归过程都可以转换成非递归过程。（√）只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。（×）队列逻辑上是一个下端和上端既能增加又能减少的线性表。（√）循环队列也存在空间溢出问题。（√）循环队列只是一个大小为maxsize 的数组空间有限自然存在溢出问题
5. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（√）
三，填空
1．栈是限定仅在表尾进行插入或删除操作的线性表。
3．中缀表达式3*（x+2）-5所对应的后缀表达式为；后缀表达式“45*32+-”的值为15。
4. 顺序栈用data[1..n]存储数据，栈顶指针是top, 则值为x 的元素入栈的操作是data[++top]=x；。
5．向一个循环队列中插入一元素时，需首先移动，然后再向所指位置6．用下标0开始的N 元数组实现循环队列时，为实现下标变量M 加1后在数组有效下标范围内循环，可采用的表达式是：M=7．用长度为n 的数组顺序存储一个栈时，若用top==n表示栈空，则表示栈满的条件为四，应用题
1．链栈中为何不设置头结点?
链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。
2．指出下列程序段的功能
(1)void Demo1(SeqStack*S){
int i; arr[64]; n=0;
while (StackEmpty(S))arr[n++]=Pop(S);
for (i=0,i
}//Demo1
(1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。
(2)SeqStack S1, S2, tmp;
DataType x;
...//假设栈tmp 和S2已做过初始化
while (! StackEmpty (&S1))
{
x=Pop(&S1);
Push(&tmp,x);
}
while (! StackEmpty (&tmp))
{
x=Pop(&tmp);
Push(&S1,x);Push(&S2,x); }
(2)程序段的功能是利用tmp 栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。3. 试证明：若借助栈由输入序列1,2,…,n得到输出序列为P 1,P 2,…,Pn （它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着i
如果i p j 的情况，则说明要将p j 压到p i 之上，也就是在p j 出栈之后p i 才能出栈。这就说明，对于i
具体解答(提示：用反证法) ：
因为借助栈由输入序列1, 2, 3, …, n ，可得到输出序列p 1, p 2, p 3, …, p n ，如果存在下标i, j, k ，满足i
①i 进栈，i 出栈，j 进栈，j 出栈，k 进栈，k 出栈。此时具有最小值的排在最前面p i
位置，具有中间值的排在其后p j 位置，具有最大值的排在p k 位置，有p i
②i 进栈，i 出栈，j 进栈，k 进栈，k 出栈，j 出栈。此时具有最小值的排在最前面p i
位置，具有最大值的排在p j 位置，具有中间值的排在最后p k 位置，有p i
③i 进栈，j 进栈，j 出栈，i 出栈，k 进栈，k 出栈。此时具有中间值的排在最前面p i
位置，具有最小值的排在其后p j 位置，有p j
④i 进栈，j 进栈，j 出栈，k 进栈，k 出栈，i 出栈。此时具有中间值的排在最前面p i 位置，具有最大值的排在其后p j 位置，具有最小值的排在p k 位置，有p k
⑤i 进栈，j 进栈，k 进栈，k 出栈，j 出栈，i 出栈。此时具有最大值的排在最前面p i 位置，具有中间值的排在其后p j 位置，具有最小值的排在p k 位置，有p k
4．举例说明顺序队的“假溢出”现象，并给出解决方案。
设顺序存储队列用一维数组q[m]表示，其中m 为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front 指向队头元素的前一位置，rear指向队尾元素。当front 等于-1时队空，rear等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear 等于m-1时，若front 不等于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾相连，即循环队列（0..m-1）。在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1）%m=front，m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。
五，算法设计题
1．回文是指正读反读均相同的字符序列，如"abba" 和"abdba" 均是回文，但"good" 不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈) 根据提示，算法可设计为：//以下为顺序栈的存储结构定义
#defineStackSize 100//假定预分配的栈空间最多为100个元素typedef char DataType;//假定栈元素的数据类型为字符typedef struct{
DataType data[StackSize];int top; }SeqStack;
int IsHuiwen(char *t)
{//判断t 字符向量是否为回文，若是，返回1，否则返回0
SeqStack s; int i , len; char temp;
InitStack(&s);
len=strlen(t);//求向量长度
for (i=0;i
Push(&s,t[i]);
while(!EmptyStack(&s))
{//每弹出一个字符与相应字符比较
temp=Pop(&s);if(temp!=S[i])return 0;//不等则返回0else i++;}
return 1; //比较完毕均相等则返回1}
2．一个双向栈S 是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化InitStack (S ) 、入栈Push(S , i , x) 和出栈Pop(S , i ) 等算法，其中i 为0或1，用以表示栈号。
双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空间可以充分利用。双向栈的算法设计如下：//双向栈的栈结构类型与以前定义略有不同
#defineStackSize 100//假定分配了100个元素的向量空间#definechar DataType typedef struct{
DataType Data[StackSize]int top0; //需设两个指针int top1; }DblStack
void InitStack(DblStack *S) {//初始化双向栈
S->top0=-1;
S->top1=StackSize; //top2也指出了向量空间，但由于是作为栈底，因此不会出错}
int EmptyStack(DblStack *S,int i ) {//判栈空(栈号i)
return (i==0&&S->top0==-1||i ==1&&S->top1==StackSize) ; }
int FullStack(DblStack *S){//判栈满,满时两头相遇
return (S->top0==S-top1-1); }
void Push(DblStack*S,int i, DataType x) {//进栈(栈号i)
if (FullStack(S ))
Error("Stackoverflow");//上溢、退出运行
if (i ==0) S->Data[++S->top0]=x; //栈0入栈if (i ==1) S->Data[--S->top1]=x; //栈1入栈}
DataType Pop(DblStack*S,int i) {//出栈(栈号i)
if (EmptyStack(S,i) )
Error("Stackunderflow");//下溢退出if(i==0)
return (S->Data[S->top0--]);//返回栈顶元素，指针值减1if(i==1)
return (S->Data[S->top1++]); //因这个栈以另一端为底，所以指针值加1。
}
第四章
一，选择
串
1．下面关于串的的叙述中，哪一个是不正确的？（B ）
A．串是字符的有限序列B．空串是由空格构成的串
C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．设有两个串p 和q，其中q 是p 的子串，求q 在p 中首次出现的位置的算法称为（C ）
A．求子串B．联接C．匹配D．求串长3．串的长度是指（B ）
A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数4．若串S=’software’,其子串的数目是（B ）。
A．8B．37C．36D．9二，填空
1．空格串是指由空格字符（ASCII值32）所组成的字符串，其长度等于空格个数。2．组成串的数据元素只能是_。
3．一个字符串中任意个连续的字符组成的子序列称为该串的子串。
4．INDEX（‘DATASTRUCTURE’，‘STR’）=5。
5．设正文串长度为n，模式串长度为m，则串匹配的KMP 算法的时间复杂度为6．模式串P=‘abaabcac’的next 函数值序列为7．设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为模式匹配，又称P 为模第五章数组和广义表
一，选择
1. 已知广义表L=（（x,y,z），a，（u，t，w）），从L 表中取出原子项t 的运算是（D ）。
A. head（tail（tail（L）））B. tail（head（head（tail（L））））C. head （tail（head（tail（L））））D. head （tail(head（tail（tail（L）））)）2. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（D ）。
Head(Tail(Head(Tail(Tail(A)))))A. (g)B. (d)C. c D. d 3.稀疏矩阵一般的压缩存储方法有两种,即（C ）
A．二维数组和三维数组B．三元组和散列C．三元组和十字链表D．散列和十字链表
4. 二维数组A 的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A 按行先存储，元素A[8,5]的起始地址与当A 按列先存储时的元素（B ）的起始地址相同。设每个字符占一个字节。
A. A[8,5]B. A[3,10]C. A[5,8]D. A[0,9]5. 对稀疏矩阵进行压缩存储目的是（C ）。
A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度
6. 设A 是n*n的对称矩阵，将A 的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素a ij (1≤i，j≤n，且i≤j)在B 中的位置为(B )。
A. i(i-l)/2+jB. j(j-l)/2+iC. j(j-l)/2+i-1D. i(i-l)/2+j-17. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k 是（B ）。
A．i（i-1）/2+jB．j（j-1）/2+iC．i（j-i）/2+1D．j（i-1）/2+18. 设广义表L=（（a,b,c）），则L 的长度和深度分别为（C ）。
A. 1和1B. 1和3C. 1和2D. 2和39. 数组A[0..4,-1..-3,5..7]中含有元素的个数（B ）。
A．55B．45C．36D．1610. 下面说法不正确的是(A )。
A. 广义表的表头总是一个广义表B. 广义表的表尾总是一个广义表C. 广义表难以用顺序存储结构D. 广义表可以是一个多层次的结构二，判断
1．一个稀疏矩阵A m*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m 和n 的值互换，则就完成了A m*n的转置运算。（×）
2. 从逻辑结构上看，n维数组的每个元素均属于n 个向量。（√）3. 稀疏矩阵压缩存储后，必会失去随机存取功能。（√）
4. 对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（√）5. 数组可看成线性结构的一种推广，因此与线性表一样可对它进行插入，删除操作。（×）
6. 所谓取广义表的表尾就是返回广义表中最后一个元素。（×）7. 二维以上的数组其实是一种特殊的广义表。（√）
8. 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（×）9. 若一个广义表的表头为空表，则此广义表亦为空表。（×）
10. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（×四应用题
1. 画出下列广义表的两种存储结构图((),A,(B,(C,D)),(E,F))。2. 设某表H 如下：
A
a1
a2
B b1
c1
C
c2
X
）
其中A,B,C 为子表名，a1,a2,b1,c1,c2,x为其元素。
试用广义表形式表示H,并写出运算HEAD(H)和TAIL(H)函数从H 中取出单元素a2的运算；（1）H(A(a1,a 2）,B(b1）,C(c1，c2）,x）
HEAD(TAIL(HEAD(H)))=a2五，算法设计
1．设任意n 个整数存放于数组A(1:n)中，试编写程序，将所有正数排在所有负数前面
本题属于排序问题，只是排出正负，不排出大小。可在数组首尾设两个指针i 和j，i自小至大搜索到负数停止，j自大至小搜索到正数停止。然后i 和j 所指数据交换，继续以上过程，直到i=j为止。
void Arrange(intA[],intn)
//n个整数存于数组A 中，本算法将数组中所有正数排在所有负数的前面{inti=0,j=n-1,x;//用类C 编写，数组下标从0开始while(i
{while(i0)i++;while(i
if(i
}//算法Arrange 结束.
[算法讨论]对数组中元素各比较一次，比较次数为n。最佳情况(已排好,正数在前,负数在后)不发生交换，最差情况(负数均在正数前面)发生n/2次交换。用类c 编写，数组界偶是0..n-1。空间复杂度为O(1).
2.设二维数组a[1..m,1..n]含有m*n个整数。判断a 中所有元素是否互不相同?输出相关信息(yes/no)。
判断二维数组中元素是否互不相同，只有逐个比较,找到一对相等的元素，就可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次？在当前行，每个元素要同本行后面的元素比较一次（下面第一个循环控制变量p 的for 循环），然后同第i+1行及以后各行元素比较一次，这就是循环控制变量k 和p 的二层for 循环。
int JudgEqual(inga[m][n],intm,n)
//判断二维数组中所有元素是否互不相同，如是，返回1；否则，返回0。{for(i=0;i
{for(p=j+1;p
if(a[i][j]==a[i][p]){printf(“no”);return(0);}
//只要有一个相同的，就结论不是互不相同
for(k=i+1;k
if(a[i][j]==a[k][p]){printf(“no”);return(0);}
}//for(j=0;j
printf(yes”);return(1);//元素互不相同}//算法JudgEqual 结束
第6章树和二叉树
一选择
1．算术表达式a+b*（c+d/e）转为后缀表达式后为（B ）
A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++2. 在下述结论中，正确的是（D ）
①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换;
④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④3．具有10个叶结点的二叉树中有（B ）个度为2的结点，
A．8B．9C．10D．ll4. 有n 个叶子的哈夫曼树的结点总数为（D ）。
A．不确定B．2nC．2n+1D．2n-15．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（A ）。
A．CBEFDAB．FEDCBA C．CBEDFA D．不定
6．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（D ）。
A．acbedB．decabC．deabcD．cedba
7．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（B ）
A．都不相同B．完全相同C．先序和中序相同，而与后序不同D．中序和后序相同，而与先序不同
8．n个结点的线索二叉树上含有的线索数为（C ）
A．2nB．n－lC．n＋lD．n9．深度为k 的二叉树，结点数最多有（B ）A ．2k B ．2k -1C ．2k-1
D ．2k-1-1
10．判断线索二叉树中某结点p 有左孩子的条件是（C ）A ．p!=NULLB ．p->lchild!=NULLC ．p->ltag=0D ．p->ltag=1二、基础知识题
1．列出右图所示二叉树的叶结点、分支结点和每个结点的层次。
二叉树的叶结点有⑥、⑧、⑨。分支结点有①、②、③、④、⑤、⑦。
结点①的层次为1；结点②、③的层次为2；结点④、⑤、⑥的层次为3；结点⑦、⑧的层次为4；结点⑨的层次为5。
2．使用（1）顺序表示和（2）二叉链表表示法，
分别画出右图所示二叉树的存储表示。
（1）顺序表示
01
①
②
2③10
3④11
45⑤12⑧
6⑥
13
78⑦
9
14151617⑨
（2）二叉链表表示
试画出3个结点的二叉树的所有不同形态。
3.设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的
编码最短。
字符A，B，C，D出现的次数为9,1,5,3。其哈夫曼编码如下A:1，B:000，C:01，D:001
第七章图
一，选择
1．图中有关路径的定义是（A ）。
A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是2．设无向图的顶点个数为n，则该图最多有（B ）条边。
A．n-1B．n(n-1)/2C．n(n+1)/2D．03．一个n 个顶点的连通无向图，其边的个数至少为（A ）。
A．n-1B．nC．n+1D．nlogn；4．要连通具有n 个顶点的有向图，至少需要（B ）条边。
A．n-lB．nC．n+lD．2n5．n个结点的完全有向图含有边的数目（D ）。
A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）6. 求解最短路径的Floyd 算法的时间复杂度为(D )。
A．O（n）B. O（n+c）C. O（n*n）D. O（n*n*n）7．已知有向图G=(V,E)，其中V={V1,V 2,V 3,V 4,V 5,V 6,V 7}，
E={,,,,,,,,},G的拓扑序列是（A ）。
A．V1,V 3,V 4,V 6,V 2,V 5,V 7B．V1,V 3,V 2,V 6,V 4,V 5,V 7C．V1,V 3,V 4,V 5,V 2,V 6,V 7D．V1,V 2,V 5,V 3,V 4,V 6,V 7
8. 在用邻接表表示图时，拓扑排序算法时间复杂度为(B )。
A. O(n)B. O(n＋e)C. O(n*n)D. O(n*n*n)9．有n 个结点的有向完全图的边数是（C ）A ．n 2B ．2n C ．n （n-1）D ．2n （n+1）10．下列哪一种图的邻接矩阵是对称矩阵？（B ）
A．有向图B．无向图C．AOV网D．AOE网11．当一个有N 个顶点的图用邻接矩阵A 表示时，顶点Vi 的度是（B ）。
A．
∑A [i , j ]
i =1
n
B．
∑A [i , j ]
j =1
n
C．
∑A [j , i ]
i =1
n
D．
A [j , i ]∑A [i , j ]∑j =1
i =1
n
n
+
12．对图做宽度优先遍历时会使用何种数据结构(A )
A ．队列B ．树C ．栈D ．集合
13．无向图G=(V,E),其中：V={a,b,c,d,e,f},
E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（D ）。
A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b14．下列关于AOE 网的叙述中，不正确的是（B ）。
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成C．所有的关键活动提前完成，那么整个工程将会提前完成D．某些关键活动提前完成，那么整个工程将会提前完成15．下面哪一方法可以判断出一个有向图是否有环（B ）：
A．深度优先遍历B. 拓扑排序C. 求最短路径D. 求关键路径二，判断
1.树中的结点和图中的顶点就是指数据结构中的数据元素。（√）
2．一个图G 有n 个顶点，n -1条边，则该图可以看成是G 的一棵生成树。(×)
3．如果AOE 网中某一个关键活动延迟一天，则整个工程将延期一天。反之，如果缩短该关键活动的持续时间，则一定可使整个工程提前完工。(×) 4. 有e 条边的无向图，在邻接表中有e 个结点。（×）
5. 有向图中顶点V 的度等于其邻接矩阵中第V 行中的1的个数。（×）6．强连通图的各顶点间均可达。（√）
7．强连通分量是无向图的极大强连通子图。（×）8．连通分量指的是有向图中的极大连通子图。（×）
9．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（×）10. 在图G 的最小生成树G1中，可能会有某条边的权值超过未选边的权值。（√）四，应用题
1．画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。2
．给出右图的邻接矩阵、领接表表示。
3．对下图所示的连通图，请分别用普里姆（Prim ）和克鲁斯卡尔（Kruskal ）算法构造其最
小生成树。
4．已知某图的邻接表为
（1）．写出此邻接表对应的邻接矩阵；
（2）．写出由v1开始的深度优先遍历的序列；时间复杂度是多少？（4）．写出由v1开始的广度优先遍历的序列；时间复杂度是多少？
（2）V1V2V5V3V4V6(4)V1V2V3V4V5V6
5．画出下图所示的AOV
网的所有拓扑有序序列。
共有8种：
ADBECF DABECF
ADBEFC DABEFC ADEBCF DAEBCF ADEBFC DAEBFC
6．对图所示的有向图，试利用Dijkstra 算法求出从源点1
到其他各顶点的最短路径，
从顶点1到其他各顶点的最短路径及距离如下：
1→3（15）1→3→2（19）1→3→6→4（29）1→3→2→5（29）1→3→6（25）
第九、十章
1. 基于比较方法的n 个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是（A ）。
A. O(nlogn)B. O(logn)C. O(n)D. O(n*n)
2．快速排序法在下列哪种情况下最不利于发挥其长处（C ）
A ．被排序的数据量太大
B ．被排序的数据中含有多个相同的关键字C ．被排序的数据已基本有序D ．被排序的数据完全无序
3．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（A ）排序为宜。
A．直接插入B．直接选择C．堆D．快速
4．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（C ）。
A. 快速排序B. 堆排序C. 归并排序D. 直接插入排序5. 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为（C ）
A．-1，4，8，9，20，7，15，7B．-1，7，15，7，4，8，20，9C．-1，4，7，8，20，15，7，9D．A，B，C均不对。6．归并排序的时间复杂度是（B ）
A ．O （n 2）B ．O （nlog 2n ）
C ．O （n ）
D ．O （log 2n ）
7．折半查找排序的时间复杂度是（A ）
A ．O （n 2）B ．O （nlog 2n ）C ．O （n ）D ．O （log 2n ）
8．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（D ）。
A．直接插入排序B. 气泡排序C. 快速排序D. 直接选择排序
9．将两个各有N 个元素的有序表归并成一个有序表,其最少的比较次数是(A )
A．NB．2N-1C．2ND．N-1
10．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（C ）。
A．(38,40,46,56,79,84)B. (40,38,46,79,56,84)
C．(40,38,46,56,79,84)D. (40,38,46,84,56,79)
11. 采用简单选择排序，比较次数与移动次数分别为(C )。
A. O（n）,O(logn)B. O(logn),0(n*n)C. 0(n*n),0(n)D. 0(nlogn),0(n)
12. 对序列{15，9，7，8，20，-1，4，}用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是(B )
A. l B. 4C. 3D. 2
13．对下列关键字序列用快速排序法进行排序时，速度最快的情形是（A ）。
A．{21,25,5,17,9,23,30}B．{25,23,30,17,21,5,9}
C．{21,9,17,30,25,23,5}Ｄ．{5,9,17,21,23,25,30}
14. 快速排序方法在（D ）情况下最不利于发挥其长处。
A. 要排序的数据量太大B. 要排序的数据中含有多个相同值
C. 要排序的数据个数为奇数D. 要排序的数据已基本有序
15．某顺序存储的表格中有90000个元素，已按关键字值额定升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字的值皆不相同。用顺序查找法查找时，平均比较次数约为（C ）
A ．25000B ．30000C ．45000D ．90000
二、判断
1．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（√）
2．内排序要求数据一定要以顺序方式存储。（×）
3．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（×）
4．直接选择排序算法在最好情况下的时间复杂度为O（N）。（×）
5．两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（×）
6．在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n )。（×）
7．利用关键字比较进行排序的算法，最好情况下时间复杂性为O (n log n ) 。(×)
8．堆肯定是一棵平衡二叉树。（×）
9．堆是满二叉树。（×）
10.简单选择排序是一种稳定的排序方法。(√)
三、应用
1. 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：
(1)归并排序每归并一次书写一个次序。
(2)快速排序每划分一次书写一个次序。
(3)堆排序先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。
2．对关键字{45,24, 53, 45, 12, 24, 90}，给出二叉排序树的构造过程。假设这6个记录的查
找概率相同，求查找成功时的ASL 。
3．已知一组关键字为(19,14,23,01,68,20,84,27,55,11,10,79)，哈希函数为：H(key)=keyMOD 13，用线性探测再散列法处理冲突，构造哈希表a[0..15]。计算等概率情况下查找成功时的平均查找长度ASL 。
4．关键码集合如下：｛[1**********]3
排序，画出堆排序的初态、建堆和重建堆的过程。27｝，用堆排序方法从小到大