********************* 第 1 章 **************************************
1.(数据元素）是数据的基本单位，在程序中作为一个整体而加以处理。
2.（数据项）是数据的不可分割的最小标识单位，但是它通常不具有完整确定的实际意义，或不被当作一个整体对待。
3.数据元素之间逻辑关系的整体称为数据的（逻辑结构），它是数据的组织形式。 4.根据数据元素之间关系的不同特性，数据结构所分的四个基本逻辑结构分别是（集合）、（线性结构）、（树形结构）和（图状结构）。
5.在任何问题中，数据元素都不是孤立的，它们之间总存在某种关系，通常称这种关系为（逻辑结构）关系
6.存储结点之间通常有四种基本存储方式，即（顺序）存储方式、（链式）存储方式、（索引）存储方式和（散列）存储方式。
7.通常从四个方面来评价算法的质量，它们是（正确性）、（易读性）、（健壮性）和（高效性）。 8.一个算法的时空性能是指该算法的（时间性能）和（空间性能）。 9.最坏情况时间复杂性和平均时间复杂性统称为（时间复杂性）。
10.一个算法的（输入规模）或问题的（规模）是指作为该算法输入的数据所含数据元素的数目，或与此数目有关的其他参数。
11.一般情况下，一个算法的时间复杂度是算法（输入规模）的函数。
12.数据结构的基本任务可以简洁地概括为：数据结构的（设计）和（实线），它们也是数据结构课程的主要内容。
13. 数据结构中评价算法的两个重要指标是(算法的时间复杂性和空间复杂性)
n
14.下面程序段中带下划线的语句的执行次数的数量级是(log2) i=1; while(i 17.一个算法在不同输入下的计算量是不同的，因此，通常用(最坏情况时间复杂性)和(平均时间复杂性)来确定一个算法的计算量。 18.一般地，运算是指在任何逻辑结构上施加的操作，根据操作的效果，可将运算分成(加工型运算)和(引用型运算)两种基本类型。 ********************* 第 2 章 ************************************** 19.通常我们将顺序结构存储的线性表称为（顺序表），将链接方式结构存储的线性表称为（链表）。 20.若一个线性表至少有一个结点，那么它的第一个结点称为（起始结点），最后一个结点称为（终端结点）。 21.在顺序表中，等概率情况下，插入和删除一个元素平均需移动(表长的一半)个元素，具体移动元素的个数与(表的长度)和(数据元素所在的位置)有关。 22.一个顺序表的第一个元素的存储地址是100，每个数据元素的长度是3，则第5个数据元素的存储地址是（112）。 23.在一个长度为n的顺序表中第i个元素之前插入一个元素时，需要移动（n-i+1）个元素。 24.在一个长度为n的顺序表中删除第i个元素时，需要移动（n-i）个元素。 25.线性表的常见链式存储结构有（单链表）、（循环链表）和（双链表）。 26.在带表头结点的单链表中，要删除某个指定的结点，必须找到该结点的（直接前驱）。 27.设一个单链表的结点格式为 Info next ，指针p指向单链表的一个非空结点A，若要删除结点A的直接后继，则需要修改指针的操作为（p->next=p->next->next）。 28.一个具有n个结点的单链表，在p所指结点后插入一个新结点s的时间复杂性为（O（1））；在给定值x的结点后插入一个新结点的时间复杂性为（O（n））。 29.顺序表中逻辑上相邻的元素的物理位置（必须）相邻。单链表中逻辑上相邻的元素的物理位置（可以不）相邻。 30.一个具有n个结点的单链表，在p所指结点后插入一个新结点s时，需执行的指针操作为（s->next=p->next;p->next=s）。 31.当线性表的元素个数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用(顺序)存储结构。 32.当对一个线性表经常进行插入和删除操作时，则采用(链式)存储结构最节省时间。 33.线性表的顺序存储是通过(数据元素的前后次序)来反应元素之间的逻辑关系。 34.线性表的链式存储结构是通过(元素的指针或指针)来反应元素之间的逻辑关系。 35.已知指针p指向单链表L中的某结点，则删除其后继结点的语句是： ( q=p→next; p→next=q→next; free(q);) 36.某线性表采用顺序存储结构，每个元素占据4个存储单元，首地址为100，则第10个元素的存储地址为(136)。 37.顺序表L=（a1,a2,…,an），假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是(（n-1）/2 ) 。 38.设单链表的结点结构为(data,next)，next为指针域，已知指针p指向单链表中data为x的结点，指针q指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:(q→next=p→next；p→next=q；) 39.对于双向链表,在两个结点之间插入一个新结点需修改的指针共 (4)个。 ********************* 第 3 章 ************************************** 40.栈称为（后进先出）线性表，它的插入操作叫（入栈），删除操作叫（退栈）。 41.队列称为（先进先出）线性表，它的插入操作叫（入队），删除操作叫（出队）。 Info next 栈空的条件是42.设一个链栈的栈顶指针为ls，栈中结点的格式为 ,（ls=NULL）;如果栈不空，则退栈的操作为（p=ls;ls=ls->next;free(p);）. 43.设有二维数组M[10][20],每个元素占2个存储单元，数组的起始地址为2000，元素M[5][10]的存储位置为（），元素M[8][19]的存储位置为（）。 44.用push表示入栈操作，用pop表示出栈操作。设有一个空栈，栈顶指针为1000H，现有输入序列为1、2、3、4、5，经过push,push,pop,push,pop,push,push后，输出的序列是(2 3），栈顶指针值为（1003H）。 45.用push表示入栈操作，用pop表示出栈操作。设有一个空栈，现有输入序列为1、2、3、4，为了得到1、3、4、2的出栈顺序，相应的出栈和入栈操作序列为（ ）。 46.一维数组Data[n]用来表示循环队，对头指针front和队尾指针rear定义为整型变量，计算队中元素个数的公式是( (rear-front+n)%n )。 47.一维数组Data[n]用来表示循环队，对头指针front和队尾指针rear定义为整型变量，队空的条件是(rear==front)，队满的条件是（（rear+1）%n==front）。 48.一个矩阵A中，如果非零元素个数远远小于矩阵的元素个数，并且非零元素的分布没有规律，则称A为（稀疏矩阵）；对这类矩阵，我们一般采用（三元组表）来表示。 49.设有一个空栈，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_______ 。 ２ ３ 50.在栈中，可进行插入和删除操作的一端称_______________。 栈顶 51._______是限定仅在一端进行插入或删除操作的线性表。 栈 52.在作进栈运算时应先判别栈是否_ _， 满 53.在作退栈运算时应先判别栈是否_ 。 空 54.队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其修改的原则是_____________。 先进先出 55.在顺序队列中，当尾指针等于数组的上界，即使队列不满，再作入队操作也会产生溢出，这种现象称为_____________。 假溢出 56.循环队列的引入，目的是为了克服_____________。 顺序队列的假溢出问题 57.循环队列存储在数组A[0..m]中，则入队时的操作为 rear= 。 (rear+1)mod(m+1) 58.循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是_______。 (rear-front+m)%m 59.二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，且A[0][0]的地址是200，则A[6][12]的地址是 。 326 60.有一个10阶对称矩阵A，采用以行为主序的压缩存储方式，每个元素占一个存储单元，A[0][0]的地址为1，则A[8][5]的地址是 。 42 **************** 第 4章 ************************************************ 61.树上任一结点所拥有的子树的数目称为该结点的（度），一棵树上所有结点的最大层数称为该树的（高度或深度），子树的根结点称为该结点的(孩子), 该结点称为其子树根结点的(双亲)。 i-1 62.二叉树第i层上至多有（2）个结点；一棵有n（n>0）个结点的满二叉树共有((n+1)/2 )个叶子结点和（(n-1)/2）各分支结点。 kk-1 63.深度为k(k>=1)的二叉树至多有（2-1）个结点；所含叶子结点的个数最多为(2)。 64.具有100个结点的完全二叉树的叶子结点数为（ ）。 65.在具有n个结点的二叉链表中，共有( 2n )个指针域, 其中(n-1 )个指针指向其左右孩子, ( n+1)个指针则是空的。 66.设高度为h的二叉树上只有度数为0和度数为2的结点，该二叉树的结点数可能达到的 h 最大值是(2-1), 最小值是(2h-1)。 67. 设高度为h的二叉树上只有度数为0和度数为1的结点，该二叉树的结点数只能是( h )。 68.具有n(n>0)个结点的二叉树的深度至少为( )。 69.具有n个叶子结点的满二叉树，其结点总数为（2n-1）。 70.一棵具有n个结点的树，所有分支结点的度均为k，则该树的叶子结点个数为()。 71.一棵树的先根遍历和后根遍历是一样的，则此树一定是（空树或只有一个结点的树）。 72.某二叉树的先根遍历序列和中根遍历序列均为abcd,则它的后根遍历序列为（dcba）。 73. 已知二叉树有200个叶子结点，则该二叉树的总结点数至少是_____________。 399 74.在二叉树中，指针p所指结点为叶子结点的条件是_____________。 p→lchild==NULL && p→rchlid==NULL 75.具有n个结点的满二叉树，其叶结点的个数是_____________。 (ｎ+1)/2 76.含有ｎ个结点的二叉树，采用二叉链表存储结构，所包含的空链域的个数为 。 ｎ+1 77.树的先根遍历序列与此树所对应的二叉树的 序列相同。 先序遍历 78.树的后根遍历序列与此树所对应的二叉树的 序列相同。 中序遍历 79.拥有100个结点的完全二叉树的最大层数为_____________。 ７ 80.高度为8的完全二叉树至少有______个叶子结点。 ６４ 81.如果结点A有 3个兄弟，而且B是A的双亲，则B的度是______。 ４ 82.若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的______序列中的最后一个结点。 先序 83.有100个结点的树有______________条分支。 99 84.假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是______。 *************** 第 6章 *************************************** 85.长度为20的有序表采用二分查找，共有( )各元素只要3次比较就可以查找到。 86.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100}, 当二分查找值为82的结点时，( )次比较后查找成功. 87.用序列{20,35,40,15,30,25,38}从空树开始，构造成一棵二叉排序树后值15在此树的第（ ）层上。 88.对n个结点的二叉排序树，在最好的情况下平均查找长度是（ ），在最坏的情况下平均查找长度是（ ）。 89.在n个结点的有序顺序表中进行二分查找，最大的比较次数是（log_2 n+1）。 90.一个索引顺序表由两部分组成：一个是（顺序表）和一个是（索引表）。 在对有20个元素的递增有序表作二分查找时，查找长度为5的元素的下标从小到大依次为_____________。（设下标从1开始） 4，9，14，17，20 91.可以唯一的标识一个数据元素的关键字称为__________。 主关键字 92.已知二叉排序树的左右子树均不为空，则__________上所有结点的值均小于它的根结点值。 左子树 93.已知二叉排序树的左右子树均不为空，则__________上所有结点的值均大于它的根结点的值。 右子树 94.动态查找表和静态查找表的重要区别在于前者包含有_________________运算，而后者不包含这两种运算。 插入和删除 95.在n个记录的有序顺序表中进行折半查找，最大比较次数是__________。 ㏒2」+1 96.分块查找中，要得到最好的平均查找长度，应对256个元素的线性查找表分成_____________块。 １６ 97.如果按关键字值递增的顺序依次将n个关键字值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__________。 （n+1）/2 ************************* 第8章 ******************************** 98.对n个待排序记录序列进行起泡排序，所需要的最好时间是( ), 最坏时间是( ). 99.对n个待排序记录序列进行快速排序，所需要的最好时间是( ), 最坏时间是( ). 100.在所有排序方法中，（ ）是从未排序序列中挑选元素，并将其放入已排好的序列的一端。 101.排序的方法有很多种，（ ）方法是从未排序序列依次取出元素，与已经排序序列中的元素作比较，将其放入已排序序列的正确位置上。 102.在所有排序方法中，交换排序是对序列中元素进行一系列的比较，当被比较的两元素为逆序时进行交换，（冒泡排序）和（快速排序）是基于这类方法的两种排序方法。其中（快速排序）方法效率更快一些。 103.在所有排序方法中，（直接选择排序）和（堆排序）是基于选择排序方法的两种排序方法。其中（堆排序）方法效率更快一些。 104.对n个元素进行冒泡排序，在（所有元素有序）的情况下比较的次数最少，其比较次数为（n-1）；在（所有元素逆序）情况下比较的次数最多，其比较次数为（ ）。 105.对n个元素进行插入排序，在所有元素（有序）的情况下比较的次数最少，其比较次数为（n-1）；在所有元素（逆序）情况下比较的次数最多，其比较次数为（ ）。 106.对一组记录（54，38，96，23，18，70，61，44，80）进行直接插入排序，当把第7个记录61插入到有序表时，为寻找插入位置需比较（5）次。 107.在直接插入排序、冒泡排序、快速排序、直接选择排序、堆排序、二路归并排序中，（）是不稳定的排序方法。 108.在直接插入排序、冒泡排序、快速排序、直接选择排序、堆排序、二路归并排序中，如果记录基本有序，则采用（）排序方法比较好。 n 109.对n 个记录的文件进行堆排序，最坏情况下的执行时间是 。O(nlog２) 110.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的比较和记录的_____。 移动 111.对n个记录进行简单选择排序，所需进行的关键字间的比较次数为_______。n(n-1)/2 112.从平均时间性能而言，__________排序最佳。 快速 113.设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},请写出按二路归并排序方法对该序列进行一趟扫描后的结果_______。 {D,Q,F,X,A,P,B,N,M,Y,C,W} 114.对初态为有序的表分别采用堆排序，快速排序，冒泡排序和归并排序，则最省时间的是____ _排序。 冒泡 115.对初态为有序的表分别采用堆排序，快速排序，冒泡排序和归并排序，则最费时间的是______ 排序。 快速 116.在堆排序、快速排序和归并排序中，若只从排序结果的稳定性考虑，则应选取 排序。 归并 n 因篇幅问题不能全部显示，请点此查看更多更全内容