for（intj=i+1;j<=n;j++）
S;
An（n-1）/2Bn2/2Cn（n+1）/2Dn
11、研究数据结构就是研究（）。
A、数据的逻辑结构B、数据的存储结构
C、数据的逻辑结构和存储结构D、数据的逻辑结构、存储结构及其数据在运算上的实现
12、以下属于逻辑结构的是（）。
A、顺序表B、哈希表C、线性表D、单链表
13、具有线性结构的数据结构是（）。
A、图B、树C、广义表D、栈
14、数据的（）包括集合、栈、树和图结构４种基本类型
A、存储结构B、逻辑结构C、基本运算D、算法描述
15、以下说法正确的是（）。
A、数据元素是数据的最小单位
B、数据项是数据的基本单位
C、数据结构是带有结构的各数据项的集合
D、一些表面上很不相同的数据可以有相同的逻辑结构.
16.有如下函数fact（n），其时间复杂度为（）。
intfac（intn）
{if（n＜＝1）reurn1;
elsereturn（n*fac（n-1））;
}
AO（n2）BO（logn）CO（n）DO（n1/2）
17.下面说法错误的是（）。
（1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O（n）的算法在时间上总是优于复杂度O（2n）的算法
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
（4）同一个算法，实现语言的级别越高，执行效率就越低
A．
（1）B.
（1）,
（2）C.
（1）,（4）D.（3）
二、填空题
1、从一维数组a[n]中顺序查找出一个最大值元素的平均时间复杂性为，读取一个二维数组b[m,n]中任一元素的时间复杂性为。
2、线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素存在关系，而集合结构中元素之间不存在关系。
3、数据结构是研究数据的和以及它们之间的相互关系，并对这种结构定义相应的并设计出相应的。
4、通常从_____、_____、_____、_____等4个方面评价算法（包括程序）的质量。
5、数据的_____结构与数据元素本身的内容和形式无关。
6、程序段“i=1;while（i<=n）i=i*2;”的时间复杂性为_____。
三、简答题
1.试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
2.有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑结构图，并指出它们分别以属于何种结构。
（1）A=（K,R）,其中
K={a,b,c,d,e,f,g,h}
R={r}
r={,,,,,,}
（2）B=（K,R）,其中
K＝{a,b,c,d,e,f,g,h}
R={r}
r={,,,,,,}
（3）B=（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）}
3.设n为正整数。
利用大"O"记号，将下列程序段的执行时间表示为n的函数。
（1）i=1;k=0;
while（i<=n-1）
{
k+=10*i;
i++;
}
（2）i=1;j=0;
while（i+j<=n）
{
if（i>j）j++;
elsei++;
}
（3）x=n;y=0;//n是不小于1的常数
while（x>=（y+1）*（y+1））
y++;
（4）x=91;y=100;
while（y>0）
{if（x>100）{x-=10;y--;}
elsex++;
}
（5）i=1;
while（i<=n）
i=i*3;
第二章线性表
一、选择题
1.在一个长度为n的顺序表中，向第i个元素（1≤i≤n+1）位置插入一个新元素时，需要从后向前依次后移（）个元素。
An-iBn-i+1Cn-i-1Di
2在一个顺序表的表尾插入一个元素的时间复度的量级为（）。
AO（n）BO
（1）CO（n2）DO（logn）
3表长为n的顺序存储的线性表，当在任意位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（），删除一个元素需要移动元素的平均个数为（）。
A（n-1）/2BnC（n+1）/2Dn/2
4设单链表中指针p指向结点a，若要删除p之后的结点（若存在），则需修改指针的操作为（）。
Ap->next=p->next->nextBp=p->next
Cp=p->next->nextDnext=p
5单链表的存储密度为（）。
A大于1B等于5C小于1D不能确定
6.在n个结点的顺序表中，算法的时间复杂度是O
（1）的操作是（）。
（A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
（B）在第i个结点后插入一个新结点（1≤i≤n）
（C）删除第i个结点（1≤i≤n）
（D）将n个结点从小到大排序
7.在双向循环链表中，已知指针P指向ai，则寻找其前驱指针的时间复杂度为____。
（A）O
（1）（B）O（n）（C）O（nlogn）（D）O（n2）
8.下述哪一条是顺序存储结构的优点？
（）。
A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示
9.下面关于线性表的叙述中，错误的是哪一个？
（）
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
10.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表
11.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表
12.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。
则采用（）存储方式最节省运算时间。
A．单链表B．双链表C．单循环链表D．带头结点的双循环链表
13.链表不具有的特点是（）
A．插入、删除不需要移动元素B．可随机访问任一元素
C．不必事先估计存储空间D．所需空间与线性长度成正比
14.在非空双向循环链表中，在q所指的结点前插入一个由p所指结点的过程依次为:
p->next=q;p->prior=q->prior;（）;q->prior=p
A、q->next=pB、q->prior->next=p
C、p->next=pD、p->next->prior=p
二、简答题
1、在链表的设计中，为什么通常采用带头结点的链表结构？
2、对比顺序表与单链表，说明顺序表与单链表的主要优点和主要缺点。
三、编程题
1.在顺序表和单链表上分别实现：
已知线性表L中的元素按值非递减有序排列，编写一个函数删除表中多余的值相同的元素。
2.在顺序表和单链表上分别实现：
线性表L中存放一组整数（值都非0），要求编写一个函数将L拆分成两个表L1和L2，使L中大于0的元素存放在L1中，小于0的元素存放在L2中。
3.在顺序表和单链表上分别实现：
假设有两个按元素值递增次序排列的线性表，请编写一个高效算法将这两个表归并为一个按元素值递减次序排列的单链表。
4.在顺序表和单链表上分别实现：
线性表L中存放一组整数（值都非0），编写算法实现表L中负数放在正数的前面。
5.在顺序表和单链表上分别实现：
线性表L中存放一组整数，删除所有值等于x的元素。
6.在顺序表和单链表上分别实现：
删除表L中从第i个元素开始的连续j个元素。
7.在顺序表和单链表上分别实现：
在表L1的第i个元素前面插入表L2，若第i个元素不存在将表L2插入到表尾。
8.已知由单链表表示的线性表L中，含有三类字符的数据元素（如：
字母字符、数字字符和其它字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。
第三章栈和队列
一、选择题
1.栈和队列的共同点是（）。
A.都是先进先出B.都是先进后出
C.只允许在端点处插入和删除元素D.没有共同点
2.栈和队都是（）。
A．顺序存储的线性结构B.链式存储的非线性结构
C.限制存取点的线性结构D.限制存取点的非线性结构
3.输入序列为ABC，可以变为CBA时，经过的栈操作为（）.
A.push,pop,push,pop,push,popB.push,push,push,pop,pop,pop
C.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop
4.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（）。
A.23415B.54132C.23145D.15432
5.设一个栈的输入序列是1，2，3，4，5，已知它的一个输出序列是2，3，1，4，5，则该栈的容量至少应该是（）。
A.2B.3C.4D.5
6.一个栈的输入序列为P1,P2,P3…Pn，若输出序列的第一个元素是Pn，输出第i（1<=i<=n）个元素是（）。
A.不确定B.Pn-i+1C.PiD.Pn-i
7.一个递归算法必须包括（）。
A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分
8.一个队列的入队序列是1，2，3，4，则队列的出队序列是（）。
A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,1
9.设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。
A．线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈
10.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时（）。
A．仅修改队头指针B.仅修改队尾指针
C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改
11.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。
A．（rear-front+m）%mB．rear-front+1
C．（front-rear+m）%mD．（rear-front）%m
12.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？
（）
A.1和5B.2和4C.4和2D.5和1
13.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。
A.（rear+1）MODn=frontB.rear=front
C．rear+1=frontD.（rear-l）MODn=front
14.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是（）。
A．6B.4C.3D.2
15.在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。
该缓冲区应该是一个（）结构。
A.栈B.队列C.数组D.线性表
二、填空题
1．栈是_______的线性表，其运算遵循_______的原则。
2.一个栈的输入序列是：
1，2，3则不可能的栈输出序列是_______。
3.设有一个空栈，栈顶指针为1000H（十六进制），现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_______，而栈顶指针值是_______H。
设栈为顺序栈，每个元素占4个字节。
4.当两个栈共享一存储区时，栈利用一维数组stack（1,n）表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为_______，栈2空时，top[2]为_______，栈满时为_______。
5.用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_______。
6.循环队列的引入，目的是为了克服__假溢出时大量移动数据元素_____。
7.区分循环队列的满与空，有两种方法，它们是_____
和_____。
三、算法设计题
1、利用栈实现判断一个字符串是不是回文。
2、利用栈将一个十进制整数转换成八进制整数。
第四章串
一、选择题
1．下面关于串的叙述中，哪一个是不正确的？
（）
A．串是字符的有限序列B．空串是由空格构成的串
C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储
2若串S1=‘ABCDEFG’,S2=‘9898’,S3=‘###’,S4=‘’,执行
concat（replace（S1,substr（S1,length（S2）,length（S3））,S3）,substr（S4,index（S2,‘8’）,length（S2）））其结果为（）。
A．ABC###G0123B．ABCD###2345C．ABC###G2345D．ABC###2345
E．ABC###G1234F．ABCD###1234G．ABC###01234
3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）
A．求子串B．串联接C．串的模式匹配D．求串长
二、填空题
1．空格串是指__
（1）__，其长度等于___
（2）__。
2．组成串的数据元素只能是________。
3．一个字符串中________称为该串的子串。
4．INDEX（‘DATASTRUCTURE’，‘STR’）=________
5.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为__
（1）__，又称P为__
（2）__。
6.串是一种特殊的线性表，其特殊性表现在__
（1）__；串的两种最基本的存储方式是__
（2）__、__（3）__；两个串相等的充分必要条件是__（4）__。
第五章数组和广义表
一、选择题
1.常对数组进行的两种基本操作是（）
（A）建立与删除（B）索引和修改
（C）查找和修改（D）查找与索引
2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a35的地址为（）。
A.13B.33C.18D.40
3.设有数组A[1..8,1..10]，数组的每个元素长度为3字节，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（）。
A.BA+141B.BA+180C.BA+222D.BA+225
4.将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A66,65（即该元素下标i=66，j=65），在B数组中的位置K为（）。
A.198B.195C.197
5.A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，下标从0开始则对任一上三角元素a[i][j]对应T[k]的下标k是（）。
A.i（i-1）/2+jB.j（j-1）/2+i
C.i（j-i）/2+1D.j（i-1）/2+1
6.设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n（n+1）/2]中，对上述任一元素aij（1≤i，j≤n，且i≤j）在B中的位置为（）。
A.i（i-l）/2+jB.j（j-l）/2+i
C.j（j-l）/2+i-1D.i（i-l）/2+j-1
7、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。
A.60B.66C.18000D.33
8、对稀疏矩阵进行压缩存储目的是（）。
A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度
9、已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（）。
A.head（tail（tail（L）））B.tail（head（head（tail（L））））
C.head（tail（head（tail（L））））D.head（tail（head（tail（tail（L）））））
10、已知广义表LS＝（（a,b,c）,（d,e,f））,运用head和tail函数取出LS中原子e的运算是（）。
A.head（tail（LS））B.tail（head（LS））
C.head（tail（head（tail（LS）））D.head（tail（tail（head（LS））））
11、广义表A=（a,b,（c,d）,（e,（f,g）））,则下面式子的值为（）。
Head（Tail（Head（Tail（Tail（A）））））
A.（g）B.（d）C.cD.d
12、广义表（（a,b,c,d））的表头是（①），表尾是（②）。
A.aB.（）C.（a,b,c,d）D.（b,c,d）
13、下面说法不正确的是（）。
A.广义表的表头总是一个广义表B.广义表的表尾总是一个广义表
C.广义表难以用顺序存储结构D.广义表可以是一个多层次的结构
14.下列广义表是线性表的是（）
（A）E（a,（b,c））（B）E（a,E）（C）E（a,b）（D）E（a,L（））
二、填空题
1.数组的存储结构采用_______存储方式。
2.当广义表中的每个元素都是原子时，广义表便成了_______。
3.广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于
（1）____。
为了区分原子和表，一般用
（2）____表示表，用（3）_____表示原子。
一个表的长度是指（4）__，而表的深度是指__（5）__
4.已知广义表A=（9,7,（8,10,（99））,12），试用求表头和表尾的操作Head（）和Tail（）将原子元素99从A中取出来。
5.广义表（a,（a,b）,d,e,（（i,j）,k））的长度是
（1）_，深度是
（2）_。
第六章树
一、选择题
1.在下述结论中，正确的是（）。
①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A．①②③B．②③④C．②④D．①④
2.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）
A．9B．11C．15D．不确定
3.一棵完全二叉树上有731个结点，其中叶子结点的个数是（）。
A．320B．325C．326D．327
4.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）
A．5B．6C．7D．8
5.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）
A．m-nB．m-n-1C．n+1D．条件不足，无法确定
6.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。
与森林F对应的二叉树根结点的右子树上的结点个数是（）。
A．M1B．M1+M2C．M3D．M2+M3
7.一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有（）结点
A．2hB．2h-1C．2h+1D．h+1
8.深度为h的满m叉树的第k层有（）个结点。
（1=A．mk-1B．mk-1C．mh-1D．mh-1
9.利用二叉链表存储树，则根结点的右指针是（）。
A．指向最左孩子B．指向最右孩子C．空D．非空
10.树的后根遍历序列等同于该树对应的二叉树的（）.
A.先序序列B.中序序列C.后序序列
11．若二叉树采用二叉链表存储结构
升级会员 