《数据结构》综合复习资料
一、填空题
1、数据结构是（）。
2、数据结构的四种基本形式为集合、（）、（）和（）。
3、线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接前驱外，其他结点有且仅有一个直接（）；除终端结点没有直接（）外，其它结点有且仅有一个直接（）。
4、堆栈的特点是（），队列的特点是（），字符串中的数据元素为（）。
5、字符串s1=“I am a student！”(单词与单词之间一个空格),s2=“student”,则字符串s1的长度为（），串s2是串s1的一个（）串，串s2在s1中的位置为（）。
6、KMP算法的特点：效率较（）；（）回溯，对主串仅需要从头到尾扫描（）遍，可以边读入边匹配。
7、广义表（（a），（（b），c），（（（d））））的长度为（），表头为（），表尾为（）。
8、ADT称为抽象数据类型，它是指（）。
9、求下列程序的时间复杂度，并用大O表示方法表示（）。
for( i=1 ; i<=n ; + + i)
for( j=1 ; j<=i; + + j )
{ ++x;
a[i][j] = x;
}
10、以下运算实现在链栈上的退栈操作，请在_____处用适当句子予以填充。
int Pop(LstackTp *ls,DataType *x)
{ LstackTp *p;
if(ls!=NULL)
{ p=ls;
*x= ;
ls= ;
;
return(1)；
}else return(0);
}
11、用堆栈求中缀表达式a+b*c/d+e*f的后缀表达式，求出的后缀表达式为（）。
12、C语言中存储数组是采用以（）为主序存储的，在C语言中定义二维数组float a[8][10],每个数据元素占4个字节，则数组共占用（）字节的内存。若第一个数据元素的存储地址为8000，则a[5][8]的存储地址为（）。
13、含零个字符的串称为（）串，用 表示。其他串称为（）串。任何串中所含字符的个数称为该串的（）。
14、数据的逻辑结构被分为（）、（）、（）和（）四种。
15、算法设计的评价标准为（）、（）、（）、（）。
16、在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为（），若假定p为一个数组a中的下标，则其后继结点的下标为（）。
17、堆栈的特点是（），所以又称（）表，队列的特点是（），所以又称（）表。
18、（）通常称作串的模式匹配。在一个主串中查找子串是否存在，存在返回（）；不存在返回( )。
19、在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的（）、（）和（）三项,同时存储稀疏矩阵行数、列数和非零数据元素的个数。
20、线性表的常见链式存储结构有（）、（）和（）。
21、队列简称（）表，在队列中，新插入的结点只能添加到（），被删除的只能是排在（）的结点。
二、单项选择题
1、一个堆栈的入栈序列为abcde，若出栈和入栈操作可间隔进行，则出栈序列不可能的为（）。
A、edcba
B、decba
C、decab
D、abcde
2、设A是一个m*n阶矩阵，A按列序存储在一组连续的存储单元中，每个元素占用w个存储单元，若A[1,1]的存储地址为base，则A[i,j]的存储地址为（）。
A、base+[(i-1)*m+(j-1)]*w
B、base+[(j-1)*m+(i-1)]*w
C、base+（j*m+i）*w
D、base+（j*m+i）*w
3、设定树根的层次为1，则有64个结点的完全二叉树的深度为（）。
A、8
B、7
C、6
D、5
4、在二叉树的先序遍历，中序遍历和后序遍历算法中，所有叶子结点的先后顺序（）。
A、都不相同
Ｂ、前序遍历和中序遍历相同，而与后序遍历不同