数据结构题库

判断题一.绪论1、程序是用计算机语言表述的算法。（）TOC\o"1-5"\h\z2、算法一定要有输入和输出。（ ）3、算法分析的目的旨在分析算法的效率以求改进算法。（ ）4、数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。（ ）5、程序就是算法，但算法不一定是程序。（ ）6、程序越短，程序运行的时间就越少。（ ）.数据元素是数据的最小单位。（）.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。（）.算法和程序原则上没有区别，在讨论数据结构时二者是通用的。（）.数据的逻辑结构与数据元素本身的内容和形式无关。（）.算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。（）.只有用面向对象的计算机语言才能描述数据结构算法。（）.插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常被使用。（）.在使用后缀表示实现计算器类时用到一个栈的实例，它的作用是暂存运算器对象。（）.每种数据结构都应具备三种基本运算：插入、删除和搜索。（）.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。（ ）1、V2、X 3、V4、X5、V6、X7、X8、V9、X10、V11、X12、X13、X13、X14、V15、X16、V二.线性表1、线性表的逻辑顺序与物理顺序总是一致的。（）2、线性表的顺序存储表示优于链式存储表示。（）3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。（）4、二维数组是其数组元素为线性表的线性表。（）5、假定有两个用单链有序表表示的集合，则这两个集合的交运算可得到一个新的集合单链表，其长度小于等于参加运算的任意一个集合单链表的长度。（）6、假定有两个用单链有序表表示的集合，则这两个集合的差运算可得到一个新的集合单链表，其长度小于参加运算的任意一个集合单链表的长度。（）TOC\o"1-5"\h\z7、线性表中的每个结点最多只有一个前驱和一个后继。（ ）8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（ ）9、单链表从任何一个结点出发，都能访问到所有结点（ ）10、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（ ）11、用一组地址连续的存储单元存放的元素一定构成线性表。（ ）12、非空线性表中任意一个数据元素都有且仅有一个直接后继元素。（ ）13、若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适。（ ）14、若线性表采用顺序存储结构，每个数据元素占用4个存储单元，第12个数据元素的存储地址为15、则第1个数据元素的存储地址是101。（ ）16、若长度为n的线性表采用顺序存储结构，删除表的第i个元素之前需要移动表中n-i+1个元素。（ ）17、符号p->next出现在表达式中表示p所指的那个结点的内容。（ ）18、要将指针p移到它所指的结点的下一个结点是执行语句p=p->next。（ ）19、线性链表中各个链结点之间的地址不一定要连续。（ ）20、线性表只能采用顺序存储结构或者链式存储结构。（ ）21、线性表的链式存储结构是通过指针来间接反映数据元素之间逻辑关系的。（ ）22、已知指针P指向链表L中的某结点，执行语句P=P->next不会删除该链表中的结点。（ ）23、在非空线性链表中由p所指的结点后面插入一个由q所指的结点的过程是依次执行语句：q->next=p->next;p->next=q。（ ）24、非空双向循环链表中由q所指的结点后面插入一个由p指的结点的动作依次为:p->prior=q,p->next=q->next,q->next=p,q->prior->next=p。（ ）25、删除非空链式存储结构的堆栈（设栈顶指针为top）的一个元素的过程是依次执行：p=top,top=p->next,free（p）。（ ）.在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。（）.顺序表和一维数组一样，都可以按下标随机（或直接）访问。（）.线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。（）.线性表若采用链式存储表示，在删除时不需要移动元素。（）.在对双向循环链表做删除一个结点操作时，应先将被删除结点的前驱结点和后继结点链接好再执行删除结点操作。（）1-5XXVVV6-10XXXXV11-15VXXXV16-20XXVVV21-25VVVVV26-30XVVVV三.栈和队列TOC\o"1-5"\h\z1、栈和队列逻辑上都是线性表。（ ）2、堆栈在数据中的存储原则是先进先出。（ ）3、队列在数据中的存储原则是后进先出。（ ）4、堆栈、队列和数组的逻辑结构都是线性表结构。（ ）5、若某堆栈的输入序列为1,2,3,4,则4,3,1,2不可能是堆栈的输出序列之一。（ ）6、不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。（ ）7、在链队列中，即使不设置尾指针也能进行入队操作。（ ）8、采用循环链表作为存储结构的队列就是循环队列。（ ）9、堆栈是一种插入和删除操作在表的一端进行的线性表。（ ）10、队列是一种可以在表头和表尾都能进行插入和删除操作的线性表。（ ）.每次从队列中取出的是具有最高优先权的元素，这种队列就是优先级队列。（ ）.链式栈与顺序栈相比，一个明显的优点是通常不会出现栈满的情况。（）.在一个顺序存储的循环队列中，队头指针指向队头元素的后一个位置。（ ）.栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。（ ）.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。（）.若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。（ ）.在用单链表表示的链式队列Q中，队头指针为Q->front,队尾指针为Q->rear,则队空条件为Q->front==Q->rear。（ ）1-5VXXVV6-10VVXVX11-15VVXVV16-17XX递归.递归定义的数据结构通常用递归算法来实现对它的操作。（）.递归的算法简单、易懂、容易编写，而且执行效率也高。（）.递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用本身需要分配额外的空间和传递数据和控制，所以时间与空间开销通常都比较大。（）.递归方法和递推方法本质上是一回事，例如求n!时既可用递推的方法，也可用递归的方法。（）.将£=1+1/2+1/3+…+1/n转化为递归函数时，递归部分为f（n）=f（n-1）+1/n递归结束条件为f（1）=1。（）18、V19、X20、V21、X22、V.串TOC\o"1-5"\h\z1、确定串T在串S中首次出现的位置的操作称为串的模式匹配。（ ）2、如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（ ）3、一个任意串是其自身的子串。（）1、V2、X3、V.数组和广义表1、多维数组是向量的推广。（ ）2、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（3、除插入和删除操作外，数组的主要操作还有存取、修改、检索和排序等。（ ）4、稀疏矩阵中0元素的分布有规律，因此可以采用三元组方法进行压缩存储。（5.如果采用如下方式定义一维字符数组:constintmaxSize=30;chara[maxSize];则这种数组在程序执行过程中不能扩充。.数组是一种静态的存储空间分配，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进行分配。.多维数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。.使用三元组表示稀疏矩阵中的非零元素能节省存储空间。.用字符数组存储长度为n的字符串，数组长度至少为n+1。1-5XXXXV6-10XXVVV11、一个广义表的深度是指该广义表展开后所含括号的层数。()一个广义表的表头总是一个广义表。()一个广义表的表尾总是一个表。()一个广义表((a),((b),c),(((d))))的长度为3,深度为4。()一个广义表((a),((b),c),(((d))))的表尾是(((b),c),(((d))))。(129)TOC\o"1-5"\h\z11、V12、X 13、V 14、V 15、V六.树1、一般树和二叉树的结点数目都可以为0。( )2、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。( )3、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。()TOC\o"1-5"\h\z4、哈夫曼树一定是满二叉树。（ ）5、给定一组权值，可以唯一构造出一棵哈夫曼树。（ ）6、深度为h的非空二叉树的第i层最多有2i-1个结点。（ ）7、满二叉树也是完全二叉树。（ ）8、已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。（ ）9、非空二叉排序树的任意一棵子树也是二叉排序树。（ ）10、对一棵二叉排序树进行前序遍历一定可以得到一个按值有序的序列。（ ）11、设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。（ ）12、哈夫曼树一定是完全二叉树。（ ）13、由一棵二叉树的前序序列和后序序列可以唯一确定它。（ ）14、在完全二叉树中，若某结点元左孩子，则它必是叶结点。（ ）15、树的带权路径长度最小的二叉树中必定没有度为1的结点。（ ）16、二叉树可以用0W度W2的有序树来表示。（ ）17、一组权值，可以唯一构造出一棵哈夫曼树。（ ）18、将一棵树转换成二叉树后，根结点没有左子树；（ ）19、用树的前序遍历和中序遍历可以导出树的后序遍历；（ ）.二叉树是一棵无序树。（ ）.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。（）.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。（）

.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中根遍历，则具有相同的结果。()TOC\o"1-5"\h\z.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和按层遍历，则具有相同的结果。( ).在树的存储中，若使每个结点带有指向双亲结点的指针，这为在算法中寻找双亲结点带来方便。( ).对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。().对于一棵具有n个结点，其高度为h的任何二叉树，进行任一种次序遍历的时间复杂度均为O(h)。( ).对于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为O(logW。().在一棵具有n个结点的线索二叉树中，每个结点的指针域可能指向子女结点，也可能作为线索，使之指向某一种遍历次序的前驱或后继结点，所有结点中作为线索使用的指针域共有n个。( ).线索二叉树中的每个结点通常包含有5个数据成员。( ).已知一棵树的前序遍历和后序遍历序列能唯一地确定这棵树。( )1-5VXVXX11-15XXXVV1-5VXVXX11-15XXXVV21-25XVXVV31V七.图6-10XVXVX16-20XXXVX26-30VXXXV1、若图G的最小生成树不唯一，则G的边数一定多于n-1,并且权值最小的边有多条（其中n为G的顶点数）。（）TOC\o"1-5"\h\z2、带权连通图中某一顶点到图中另一定点的最短路径不一定唯一。（ ）3、在n个结点的无向图中，若边数等于n-1,则该图必是连通图。（ ）4、若一个有向图的邻接矩阵中，对角线以下元素均为0,则该图的拓扑有序序列必定存在。（）5、对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。（）6、无向图的邻接矩阵是对称的有向图的邻接矩阵是不对称的。（ ）7、具有n个顶点的连通图的生成树具有n-1条边（）.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。（ ）.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（）.邻接矩阵适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）。（）.存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（上）三角部分。（）.强连通分量是有向图中的极大强连通子图。（）.对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果都是唯一的。（）.有回路的有向图不能完成拓扑排序。（）.在AOE网络中一定只有一条关键路径。（）.用边表示活动的网络（AOE网）的关键路径是指从源点到终点的路径长度最长的路径。（）.对于AOE网络，加速任一关键活动就能使整个工程提前完成。（）.对于AOE网络，任一关键活动延迟将导致整个工程延迟完成。（）.在AOE网络中，可能同时存在几条关键路径，称所有关键路径都需通过的有向边为桥。如果加速这样的桥上的关键活动就能使整个工程提前完成。（）.对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。（）.图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。（）.如果无向图中每个顶点的度都大于等于2,则该图中必有回路。（）.如果有向图中各个顶点的度都大于2,则该图中必有回路。（）.图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。（）.图的广度优先搜索算法通常采用非递归算法求解。（）.对一个有向图进行拓扑排序，一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。（）1、V2、V3、X4、V5、V6、X 7、V 8、V9、X10、V 11、V12、V13、X14、V15、X16、V17、X18、V19、V20、V21、V22、V23、X24、V25、V26、X八.查找1、散列表的查找效率主要取决于所选择的散列函数与处理冲突的方法。（）2、折半查找方法可以用于按值有序的线性链表的查找。（ ）3、哈希的查找无需进行关键字的比较。（）4、一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内，以尽可能减少冲突。（）5、在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不与表的个数有关，而与每一块中的元素个数有关。（）.在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度。（）.进行折半搜索的表必须是顺序存储的有序表。（）.能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相同。（）.折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树。（）.对于同一组关键码互不相同的记录，若生成二叉搜索树时插入记录的次序不同则得到不同形态的二叉搜索树。（）.对于同一组记录，生成二叉搜索树的形态与插入记录的次序无关。（）.对于两棵具有相同记录集合而具有不同形态的二叉搜索树，按中序遍历得到的结点序列是相同的。（）.在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越大的结点离树根越近，则得到的是最优二叉搜索树。（）.在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树。（）.装载因子是散列表的一个重要参数，它反映了散列表的装满程度。（）.在用散列表存储关键码集合时，可以用双散列法寻找下一个空位置。在设计再散列函数时，要求计算出的值与表的大小m互质。（）.一棵3阶B树是平衡的3路搜索树，反之，一棵平衡的3路搜索树是3阶B树。（）.闭散列法通常比开散列法时间效率更高。（）.一棵m阶B树中每个结点最多有m-1个关键码，最少有「m/21-1个关键码。（）.在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。（）.在索引顺序结构的搜索中，对索引表既可以采取顺序搜索，也可以采用折半搜索。（）.在散列法中采取开散列（链地址）法来解决冲突时，其装载因子的取值一定在（0,1）之间。（）.AVL树（平衡二叉搜索树）的所有叶结点不一定在同一层次上，同样，平衡m路搜索树的叶结点也不一定在同一层次上。（）.在一棵B-树中，所有叶结点都处在同一层上，所有叶结点中空指针数等于所有关键码的总数加1。（）.向一棵B-树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高度减少1。（）.从一棵B-树删除关键码的过程中，若最终引起树根结点的合并，则新树比原树的高度增加1。（）.折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（）1、V2、X3、X4、V5、X6、V 7、V8、X9、V 10、V11、X12、V13、V14、X15、V16、V17、X18、X19、X20、V21、V22、X 23、V 24、V 25、X 26、X 27、X九.排序1、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（）2、快速排序是排序算法中最快的一种。（）3、直接选择排序是一种不稳定的排序方法。（ ）4、对一个堆按层次遍历，不一定能得到一个有序序列。（）5、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（）6、希尔排序在效率上较直接插入排序有较大的改进。但是不稳定的。（）7、在平均情况下，快速排序法最快，堆积排序法最节省空间。（）TOC\o"1-5"\h\z8、快速排序法是一种稳定性排序法。（ ）9、序列初始为逆序时，冒泡排序法所进行的元素之间的比较次数最多。（ ）10、给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。（ ）11、由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。（ ）12、101，88，46，70，34，39，45，58，66，10）是堆；（ ）13、排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。（ ）.当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。.当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。.对具有n个结点的堆进行插入一个元素运算的时间复杂度为O（n）。.直接选择排序是一种稳定的排序方法。.若将一批杂乱无章的数据按堆结构组织起来，则堆中数据必然按从小到大的顺序线性排列。.当输入序列已经基本有序时，起泡排序需要比较关键码的次数，比快速排序还要少。.在任何情况下，快速排序需要进行关键码比较的次数都是O（nlog2n）。.若用m个初始归并段参加k路平衡归并排序，则归并趟数应为「log2ml.堆排序是一种稳定的排序算法。.任何基于排序码比较的算法，对n个数据对象进行排序时，最坏情况下的时间复杂度都不会大于O（nl0g2n）。1-5XXXVV6-10VVXVV11-15XVVVV16-20XVXVX21-23XXX二、填空题：一.绪论1、《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和运算。2、数据结构算法中，通常用时间复杂度和 空间复杂度两种方法衡量其效率。3、一个算法一该具有.有穷,确定，——可行_,_输入和_输出―这五种特性。.数据是—信息的载体，它能够被计算机程序识别、存储和加工处理。.数据结构包括逻辑结构、―存储结构和数据的运算三个方面。.数据结构的逻辑结构包括线性结构和.非线性结构两大类。.数据结构的存储结构包括顺序、.链接、索引和散列等四种。.基本数据类型是计算机已经实现了的—数据结构。.抽象数据类型的特点是.数据封装、信息隐蔽、使用与实现分离。.算法的一个特性是—有穷性，即算法必须执行有限步就结束。1.运算2空间复杂度 3有穷性确定性可行性输入输出4信息5存储结构6非线性7.链接8.数据结构 9.数据封装10.有穷性二.线性表1、若频繁地对线性表进行插入与删除操作，该线性表应采用—链表存储结构。2、在非空线性表中除第一个元素外，集合中每个数据元素只有一个—直接前驱;除最后一个元素之外，集合中每个数据元素均只有一个—直接后继3、线性表中的每个结点最多有—1个直接—前驱和一个直接后继。4、.循环链表从任何一个结点出发，都能访问到所有结点。5、链式存储结构中的结点包含数据域，指针域。6、在双向链表中，每个结点含有两个指针域，一个指向.前驱结点，另一个指向—后继 结点。7、某带头结点的单链表的头指针head，判定该单链表非空的条件head->next!=NULL。8、在双向链表中，每个结点含有两个指针域，一个指向.前驱结点，另一个指向.后继―结点。9、已知指针p指向单链表中某个结点，则语句p->next=p->next->next的作用—删除p的后继结点_。10、已知在结点个数大于1的单循环链表中，指针p指向某个结点，则下列程序段结束时，指针q指向*p的前驱结点。q=p;while(q->next!=p)q=q->next;11、若要在单链表结点*P后插入一结点*S，执行的语句s->next=p->nextp->next=s。12、线性表的链式存储结构地址空间可以—不连续，而向量存储必须是地址空间连续。.线性表是由n(n20)个数据元素组成的有限序列。

.链表是一种采用链式存储结构存储的线性表。.在链表中进行插入和—删除 操作的效率比在顺序存储结构中进行相同操作的效率高。.链表对于数据元素的插入和删除不需要移动结点，只需要改变相应结点的指针的值。.链接存储表示的结点存储空间一般在程序的运行过程中进行动态地分配和释放。.单链表中逻辑上相邻的结点而在物理位置上—不一定相邻。.在单链表中，除了表头结点外，任意结点的存储位置由其直接.前驱结点的指针域的值所指示。.在单链表设置表头结点的作用是插入和删除表中第一个元素时不必对表头指针进行特殊处理。.若设L是指向带表头的单链表，语句L->link=L->link->link的作用是删除单链表中的第一个结点。.在双向链表中，每个结点除了数据域外，还有两个指针域，它们分别指向前驱结点和后继结点。.线性表的链接存储只能通过链接指针顺序访问。.链表与顺序表、索引表、散列表等都是数据逻辑结构的存储表示。.设双向循环链表每个结点结构为 (data,llink,rlink),则结点*p的前驱结点的地址为p->llink。1、链表 2、直接前驱，直接后继 3、1个直接，1个直接4、循环5、指针，数据6、前驱，后继 7、head->next!=Null8、前驱，后继重题9、删除p的后继结点 10、后继11、s->next=p->next;p->next=s12、不连续，连续11、s->next=p->next;p->next=s12、不连续，连续13.数据元素14.链式(或链接)15.删除16.链式(或链接)15.删除16.指针域17.分配18.不一定19.前驱20.表头指针 21.删除 22.前趋结点和后继结点23.链接指针 24.存储25.p->llink三.栈和队列1、栈结构允许进行删除操作的一端为栈顶。2、在栈的顺序实现中，栈顶指针top,栈为空条件top=-1。3、对于单链表形式的队列，其空队列的F指针和R指针都等于头结点的指针。4、若数组s[0..n-1]为两个栈s1和s2的共用存储空间，仅当s[0..n-1]全满时，各栈才不能进行栈操作，则为这两个栈分配空间的最佳方案是： s1和s2的栈顶指针的初值分别为__s[0]s[n-1] 。5、允许在线性表的一端插入，另一端进行删除操作的线性表称为.队列。插入的一端为—队尾,删除的一端为—队头―。6、设数组A[m]为循环队列Q的存储空间，font为头指针，rear为尾指针，判定Q为空队列的条件Q->font==Q->rear。7、对于顺序存储的队列，存储空间大小为n,头指针为F,尾指针为R。若在逻辑上看一个环，则队列中元素的个数为__(_R-F)%n。8、已知循环队列的存储空间为数组data[21],且头指针和尾指针分别为8和3,则该队列的当前长度17。.栈是一种限定在表的一端进行插入和删除的线性表，又被称为先进后出表。.队列是一种限定在表的一端插入，在另一端删除的线性表，它又被称为—先进先出表。.向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给。.队列的删除操作在进行。.向一个顺序栈插入一个元素时，首先使后移一个位置，然后把待插入元素写入到这个位置上。.若设顺序栈的最大容量为MaxSize，top==-1表示栈空，则判断栈满的条件是—.当用长度为MaxSize的数组顺序存储一个栈时，若用top==MaxSize表示栈空，则表示栈满的条件为__top==0。.向一个循环队列中插入元素时，需要首先移动—队尾指针，然后再向所指位置写入新元素。.向一个栈顶指针为top的链式栈中插入一个新结点*p时，应执行—p->link=top和top=p操作。.在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有__1个结点。.在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有个结点。1、栈顶2、 top==-1 3、 头节点的指针 4、s[0]，s[n-1]5、队列，队尾队头 6、Q->font=Q->rear7、（R-F）%n 8、179.后出先进10.先进先出 11.栈顶指针12.队头（或队首）13.栈顶指针 14.top==MaxSize-1 15.top==0 16.队尾17.p->link=top 18.1 19.一.如果一个对象部分地包含自己，或自己定义自己，则称这个对象是递归—的对象。.如果一个过程直接或间接地调用自己，则称这个过程是一个—递归的过程。.递归工作栈起到两个作用，其一是将递归调用时的实际参数和返回地址传递给下一层递归；其二是保存本层的形式参数和一局部变量 。.函数内部的局部变量是在进入函数过程后才分配存储空间，在函数过程执行结束后就—释放局部变量所占用的存储空间。.迷宫问题是一个回溯控制的问题，最好使用递归的方法来解决。.递归 21.递归 22.局部变量 23.释放24.递归四.串1、一个串的任意个连续的字符组成的子序列称为该串的―子串,包含该子串的串称为—主串。2、求串T在主串S中首次出现的位置的操作是―Index(S,T,pos)。3、在初始为空的队列中插入元素A,B,C,D以后，紧接着作了两次删除操作，此时的队尾元素是―D。4、在长度为n的循环队列中，删除其节点为x的时间复杂度为O(n)。5、已知广义表L为空，其深度为1。6.若设串S="documentHash.doc\0"，则该字符串S的长度为16。1、子串，主串2、Index(S,T,pos)3、D4、O(n)5、1 6.16五.数组和广义表1、已知一顺序存储的线性表，每个结点占用k个单元，若第一个结点的地址为DA1,则第i个结点的地址为―DA1+(i-1)*k。2、设一行优先顺序存储的数组A[5][6],A[0][0]的地址为1100,且每个元素占2个存储单元，则A[2][3]的地址为__1130。3、设有二维数组A[9][19],其每个元素占两个字节，第一个元素的存储地址为100,若按行优先顺序存储，则元素A[6,6]的存储地址为340，按列优顺序存储，元素A[6,6]的存储地址为220。/*100+(6*9+6)*2*/4、假设以行为优先存储的三维数组A[5][6][7]，A[0][0][0]的地址为1100，每个元素占两个存储单元，则A[4][3][2]的地址为__1482。/*1100+{(4*6+3)*7+2}*2*/4、设二维数组A[m][n]按列优先存储，每个元素占1个存储单元，元素A。。的存储地址10c(A。。)，则Aij的存储地址10c(A)=_loc(A00)+j*_m+i。6、稀疏矩阵一般采用—三元组 方法进行压缩存储。7、稀疏矩阵可用—三元组 进行压缩存储，存储时需存储非零元的—行号、列号、_值 。8、若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为三对角矩阵。9、若一个n阶矩阵A中的元素满足：八：八典(0<=I,j<=n-1)则称A为—对称矩阵；若主对角线上方(或下方)的所有元素均为零时，称该矩阵为(上)下三角矩阵。10、对于上三角形和下三角形矩阵，分别以按行存储和按列存储原则进行压缩存储到数组M[k]中，若矩阵中非0元素为Aj，则k对应为__i*(i-1)/2+j-1(i>=j)―和_j*(j-1)/2+i-1(i<j) 。11、设有一上三角形矩阵A[5][5]按行压缩存储到数组B中，B[0]的地址为100，每个元素占2个单元，则A[3][2]地址为108。/*{3*(3-1)/2+2-1}*2=8*/.一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的一下标存取的。.在程序运行过程中不能扩充的数组是_静态分配的数组。这种数组在声明它时必须

指定它的大小。.在程序运行过程中可以扩充的数组是动态分配的数组。这种数组在声明它时需要使用数组指针。.二维数组是一种非线性结构，其中的每一个数组元素最多有个直接前驱(或直接后继)。.若设一个nn的矩阵A的开始存储地址LOC(0,0)及元素所占存储单元数d已知，按行存储时其任意一个矩阵元素a[i][j]的存储地址为.LOC(0,0)+(i*n+j)d。.对称矩阵的行数与列数—相等 且以主对角线为对称轴，匕=2亚，因此只存储它的上三角部分或下三角部分即可。.将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则一维数组需要存储__n*(n+1)/2个矩阵元素。.将一个n阶对称矩阵A的上三角部分按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中，则A[I][J]在IWJ时将存放于数组B的— 位置。TOC\o"1-5"\h\z.利用三元组表存放稀疏矩阵中的非零元素，则在三元组表中每个三元组元素对应一个非零元素的行号、列号和—值 。1、DA1+(i-1)*k 2、1100+(6*2+3)*2=1130 3、100+(19*6+6)*2=340,100+(9*6+ )*2=220 4、1482 5、loc(a00)+(j*m+i)*1 6、三元组7、三元组，行号，列号，值 8、三对角矩阵 9、上(下)三角矩阵 10、i*(i-1)/2+j-1(i2j),j*(j-1)/2+i-1(i<j) 11、10812.下标(或顺序号)13.静态14.动态15.两个16.LOC(0,0)+(i*n+j)*d 17.相等18.n(n+1)/2相等18.n(n+1)/219.2n-I-1)*I/2+J 20.值21、广义表(A,(a,b),d,e,((i,j),k)),则广义表的长度为5,深度为322、已知广义表A=((a,b,c),(d,e,f)),则运算head(head(tail(A))))=d23、已知广义表ls=(a,(b,c,d),e),运用head和tail函数取出ls中的原子b的运算是head(head(tail(s)))。.非空广义表的除第一个元素外其他元素组成的表称为广义表的—表尾。.广义表A((a,b,c),(d,e,f))的表尾为__25.((d,e,f)).广义表是一种递归的数据结构，子表结点则指示下一层广义表的—表头结点。.广义表的深度定义为广义表括号的一层数。21、5,3 22、d23、head(head(tail(s)))24.表尾25.((d,e,f))26.表头结点 27.层数六.树1、在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个前驱,且存在一条从根到该结点的路径。2、度数为0的结点，即没有子树的结点叫作叶子结点或—终端结点。同一个结点的儿子结点之间互称为兄弟结点。3、假定一棵树的广义表为A(B(e),C(F(h,i,j),g),D),则该树的度为3—，树的深度为4，终端结点为__ehijgD—，单分支结点为日，双分支结点个数为1，三分支结点为__A_F,C结点的双亲结点是__A，孩子结点是F,g。4、完全二叉树、满二叉树、线索二叉树和二叉排序树这四个名词术语中，与数据的存储结构有关系的是—线索。5、有三个结点的二叉树，最多有―5—种形状。6、高度为k的二叉树具有的结点数目，最少为_k,最多为_2h1。/*高度？深度？*/7、对任何一棵二叉树，若n0,n1,n2分别是度为0,1,2的结点的个数，则n0=__n2+1。8、在含100个结点的完全二叉树，叶子结点的个数为_50。9、将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫.排序―。10、若一棵满二叉树含有121个结点，则该树的深度为7。11、一个具有767个结点的完全二叉树，其叶子结点个数为__384。12、深度为90的满二叉树，第11层有—1024个结点。13、有100个结点的完全二叉树，深度为―7。14、设一棵二叉树中度为2的结点10个，则该树的叶子个数为11。/*n0=n2+1*/15、含有3个2度结点和4个叶结点的二叉树可含个1度结点。16、一棵具有5层满二叉树中节点总数为31。17、一棵含有16个结点的完全二叉树，对他按层编号，对于编号为7的结点，他的双亲结点及左右结点编号为3、14、15。18、深度为k（设根的层数为1）的完全二叉树至少有个结点，至多有个结点。19、若要对某二叉排序树进行遍历，保证输出所有结点的值序列按增序排列，应对该二叉排序树采用—中序遍历法。20、在序列⑵5,8,11,15,16,22,24,27,35,50）中采用折半查找（二分查找）方法查找元素24,需要进行4次元素之间的比较。/*16、27、22、24*/21、设有10个值，构成哈夫曼树，则该哈夫曼树共有19个结点。/*10个值就是10个叶子结点；没有1度的结点*/22、从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。.对于一棵具有n个结点的树，该树中所有结点的度数之和为_n-1。/*每一个结点对应

一个棍就是一度(除根节点外)*/.一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y))),结点k的所有祖先的结点数为__2 个。.一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点f的层数为3—。假定树根结点的层数为0。.假定一棵三叉树(即度为3的树)的结点个数为50，则它的最小高度为_4。假定树根结点的深度为0。.在一棵高度为3的四叉树中，最多含有255个结点，假定树根结点的高度为0。.在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有6个。.一棵高度为5的完全二叉树中，最多包含有63个结点。假定树根结点的高度为0。/*2*2*2*2*2*2-1*/.假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则该树的高度为3。假定树根结点的高度为0。.在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为6个。/*n0=n2+n1*/.假定一棵二叉树的结点数为18,则它的最小高度为3。假定树根结点的高度为0。1、前驱，路径 2、叶子，终端，兄弟 3、3；3；e,h,I,j,g；C；A,F；A；F,g4、线索5、5 6、k，2k-1 7、n1+n2 8 、 509、排序10、7 11、384 12、1024 13、7 14、11 15、1(0) 16、 3117、3，14，15 18、2k-1，2k-1 19、中序20、4 21、19 22、路径23.n-124.225.3 26.4 27.85 28.6 29.63

23.n-124.225.3 26.4 27.85 28.6 29.6330.331.30.331.632.4七.图1、对于一个图G,若边集合E(G)为无向边的集合，则称该图为无向图。2、对于一个图G,若边集合E(G)为有向边的集合，则称该图为有向图。3、对于有向图，顶点的度分为入度和出度，以该顶点为终点的边数目叫—入度;以该顶点为起点的边数目叫___出度。4、一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个对称矩阵。5、有一个n个顶点的有向完全图的弧数—2n。6、在无向图中，若从顶点A到顶点B存在—路径，则称A与B之间是连通的。7、在一个无向图中，所有顶点的度数之和等于所有边数的2—倍。8、一个连通图的生成树是该图的极小连通子图。若这个连通图有n个顶点，则它的生成树有n*(n-1)条边。9、无向图的邻接矩阵是一个对称矩阵。10、如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是 连通的 。11、若采用邻接表的存储结构，则图的广度优先搜索类似于二叉树的层次遍历。12、若图的邻接矩阵是对称矩阵，则该图一定是无向图。13、从如图所示的临接矩阵可以看出，该图共有_3个顶点。如果是有向图，该图共有_4ABC-011-A_。B=001B条边。010C条弧；如果是无向图，则共有3—条边。14、如果从一个顶点出发又回到该顶点，则此路径叫做一环/回路—15、一个具有个n顶点的无向图中，要连通全部顶点至少需要_n-116.n(n>0)个顶点的连通无向图各顶点的度之和最少为_2(_n-1).用邻接矩阵存储图，占用的存储空间与图中的一顶点数有关。.设图G=(V,E)，V={V0,JV2,VJ,E={(V0,V1),(V0,”，储Vj，(V『Vj,则从顶点V0开始的图G的不同深度优先序列有4种。.设图G=(V,E),V={1,2,3,4},E={<1,2>,<1,3>,<2,4>,<3,4>},从顶点1出发，对图G进行广度优先搜索的序列有_2种。.n(n>0)个顶点的无向图中顶点的度的最大值为__n-1。.在重连通图中每个顶点的度至少为。.n个顶点的连通无向图的生成树含有n-1条边。.11个顶点的连通网络N有10条边，其中权值为1,2,3,4,5的边各2条，则网络N的最小生成树各边的权值之和为30。/*2*(1+2+3+4+5)=30*/.在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个—连通分量 上，才会被加入到生成树中。.一般来说，深度优先生成树的高度比广度优先生成树的高度要高―。.求解带权连通图最小生成树的Prim算法使用图的—邻接矩阵作为存储结构。.设图的顶点数为n,则求解最短路径的Dijkstra算法的时间复杂度为.O(m)。1、无向图2、有向图3、入度，出度 4、对称矩阵5、n(n-1)6、路径7、28、极小(最小)，n-1 9、对称10、连通11、层次12、无向图13、3,4,314、环/回路15、n-1 16.2(n-1) 17.顶点18.4 19.2 20.n-121.2 22.n-1 23.30 24.连通分量 25.高26.邻接矩阵27.0(n2)八.查找1、若待散列的序列为(18,25,63,50,42,32,9),散列函数为H(key)=keyMOD9,与18发生冲突的元素有2个。/*18、63*/2、关键字自身作为哈希函数，即H(k)=k，也可自身加上一个常数作为哈希函数，即H(k)=k+C这种构造哈希函数的方式叫—直接定址法。3、折半搜索只适合用于有序表。4、结点关键字转换为该结点存储单元地址的函数H称为哈希函数或叫散列表。5、在索引查找中，首先查找索引表，然后查找相应的—子表，整个索引查找的平均查找长度等于查找索引表的平均长度与查找相应子表的平均查找长度的—和—。.链表只适用于 顺序查找。.在一棵高度为h的理想平衡二叉树中，最少含有_2h个结点。假定树根结点的高度为0。.在一棵高度为h的理想平衡二叉树中，最多含有_2h+1_-1个结点。假定树根结点的高度为0。.若将一棵树A(B(C,D,E),F(G(H),I))按照左子女-右兄弟表示法转换为二叉树，该二叉树中度为2的结点的个数为2—个。.将一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有__右 子女。.以顺序搜索方法从长度为n的顺序表或单链表中搜索一个元素的渐进时间复杂度为 —O(n)。.对长度为n的搜索表进行搜索时，假定搜索第i个元素的概率为p『搜索长度(即在搜索过程中依次同有关元素比较的总次数)为ci，则在搜索成功情况下的平均搜索长度的计算公式为fpc ii 。i=1.假定一个顺序表的长度为40，并假定顺序搜索每个元素的概率都相同，则在搜索成功情况下的平均搜索长度为__20.5。/*等差数列求和Sn=na1+n(n-1)d/2*/.从有序表(12,18,30,43,56,78,82,95)中折半搜索元素56时，其搜索长度为—3。.假定对长度n=50的有序表进行折半搜索，则对应的判定树中最底下一层的结点数为 个。.从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向.右子树继续搜索。.向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的左子树―上。.根据n个元素建立一棵二叉搜索树的渐进时间复杂度大致为—O(nlog2n)。.在一棵AVL树中，每个结点的左子树高度与右子树高度之差的绝对值不超过_1。.根据一组记录(56,42,50,64,48)依次插入结点生成一棵AVL树时，当插入到值为50的结点时需要进行旋转调整。.根据一组记录(56,74,63,64,48)依次插入结点生成一棵AVL树时，当插入到值为63的结点时需要进行先右后左双翻转调整。.根据一组记录(56,42,38,64,48)依次插入结点生成一棵AVL树时，当插入到值为38的结点时需要进行―向右单翻转调整。.根据一组记录(56,42,73,50,64,48,22)依次插入结点生成一棵AVL树时，当插入到值为48的结点时才出现不平衡，需要进行旋转调整。.在索引表中，若一个索引项对应数据对象表中的一个表项，则称此索引为稠密索引，若对应数据对象表中的若干表项，则称此索引为—稀疏索引。.假定对长度n=100的线性表进行索引顺序搜索，并假定每个子表的长度均为nn，则进行索引顺序搜索的时间复杂度为_0(10)。.假定对长度n=100的线性表进行索引顺序搜索，并假定每个子表的长度均为，则进行索引顺序搜索的平均搜索长度为。/*5.5+5.5=11*/.若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则一级索引表的长度为500..假定要对长度n=100的线性表进行散列存储，并采用开散列法处理冲突，则对于长度m=20的散列表，每个散列地址的同义词子表(单链表)的长度平均为5。/*100/20*/.在线性表的散列存储中，装载因子a又称为装载系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则a等于n/m。.对于包含n个关键码的m阶B树，其最小高度为―「l0gm(n+1)1。.已知一棵3阶B树中含有50个关键码，则该树的最小高度为4。.已知一棵3阶B树中含有50个关键码，则该树的最大高度为5。.在一棵m阶B树上，每个非根结点的关键码数最少为个。.在一棵m阶B树上，每个非根结点的子树最少为―「m/21棵。.在一棵m阶B树上，每个非根结点的关键码数最多为个。.在对m阶B树插入元素的过程中，每向一个结点插入一个关键码后，若该结点的关键码个数等于个，则必须把它分裂为2个结点。.在从m阶B树删除关键码的过程中，当从一个结点中删除掉一个关键码后，所含关键码个数等于「m/2]-2个，并且它的左、右兄弟结点中的关键码个数均等于，则必须进行结点合并。.在一棵具有n个结点的AVL树上进行插入或删除元素的渐进时间复杂度大致为1、2 2、直接定址法 3、有序表4、哈希函数，散列函数 5、索引表，子表，和6.顺序 7.2h8.2h+1-1 9.2 10.右11.O(n)xn一一 ,一…12.乙pc13.20.5 14.3 15.19 16.右子树iii=1

17.左子树18.O(nlog2n)19.117.左子树18.O(nlog2n)19.120.5021.先右后左双旋转 22.右单旋转 23.6424.稀疏25.O(\'n) 26.11 27.500 28.25 29.530.n/m31.「log(n+1)~| 32.4 33.5 34.「m/2~|-1 35.「m/2]m36.m-1 37.m38.「m/2~|-1 39.O(log2n)九.排序1、在进行直接插入排序时，其数据比较次数与数据的初始排列―有―关；而在进行直接选择排序时，其数据比较次数与数据的初始排列无—关。2、每一趟排序时从排好序的元素中挑出一个值最小的元素与这些未排小序的元素的第一个元素交换位置，这种排序方法成为选择排序法。3、给定序列{100,86,48,73,35,39,42,57,66,21},按堆结构的定义，则它一定大顶堆。4、从未排序序列中选择一个元素，该元素将当前参加排序的那些元素分成前后两个部分，前一部分中所有元素都小于等于所选元素，后一部分中所有元素都大于或等于所选元素，而此时所选元素处在排序的最终位置。这种排序法称为快速 排序法。.在一个堆的顺序存储中，若一个元素的下标为i(0WiWn-1),则它的左子女元素的下标为__2i+1 。.在一个堆的顺序存储中，若一个元素的下标为i(0WiWn-1),则它的右子女元素的下标为__2i+2 。.在一个最小堆中，堆顶结点的值是所有结点中的―最小的。.在一个最大堆中，堆顶结点的值是所有结点中的.最大的。.第i(i=1,2,…，n-1)趟从参加排序的序列中取出第i个元素，把它插入到由第0个至第i-1个元素组成的有序表中适当的位置，此种排序方法叫做 直接插入排序。.第i(i=0,1,...,n-2)趟从参加排序的序列中第i个至第n-1个元素中挑选出一个最小元素，把它交换到第i个位置，此种排序方法叫做—直接选择排序。.每次直接或通过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫做—交换排序。.每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做—二路归并排序。.在直接选择排序中，记录比较次数的时间复杂度为—O(n2)。.在直接选择排序中，记录移动次数的时间复杂度为。.在堆排序中，对n个记录建立初始堆需要调用次调整算法。.在堆排序中，如果n个对象的初始堆已经建好，那么到排序结束，还需要从堆顶结点出发调用—n-1次调整算法。.在堆排序中，对任意一个分支结点进行调整运算的时间复杂度为O(log2n)。.对n个数据对象进行堆排序，总的时间复杂度为—O(nO(nlog2n))。.给定一组数据对象的关键码为｛46,79,56,38,40,84｝，则利用堆排序方法建立的初始堆(最大堆)为_84,79,56,38,46,40。.快速排序在平均情况下的时间复杂度为。.快速排序在最坏情况下的时间复杂度为。.快速排序在平均情况下的空间复杂度为。.快速排序在最坏情况下的空间复杂度为O(nlog2n)。24给定一组数据对象的关键码为｛46,79,56,38,40，84｝，对其进行一趟快速排序处理，得到的右子表中有3个对象。.在对n个数据对象的二路归并排序中，每趟归并的时间复杂度为O(n)。.在对n个数据对象进行的二路归并排序中，整个归并过程的时间复杂度为—O(nlog2n).在索引表中，每个索引项至少包含有—关键码域和地址域这两项。.假定一个线性表为｛12,23,74,55,63,40,82,36｝，若按key%3条件进行划分，使得同一余数的元素成为一个子表，则包含74的子表长度为3。. 假定一个线性表为(“abcd“，"baabd"，“bcef“，“cfg“，“ahij“，"bkwte"，“ccdt“，“aayb”)，若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的以a为第一个字母的子表长度为3。1、有，无2、选择3、大根堆4、快速5.2i+16.2i+27.最小值8.最大值9.直接插入10.直接选择 11.交换12.二路归并3.O(n2)14.O(n)TOC\o"1-5"\h\z15.n/2 16.n-1 17.O(logn)18.O(nlogn)19.84,79,56,38,40，46 20.2 2O(nlog2n) 21.O(n2) 22.O(log尸) 23.O(n) 24.3 25.O(n)\o"CurrentDocument"26.O(nlogn)27.关键码28.2 29.32三、选择题：一.绪论()1.数据结构通常是研究数据的—及它们之间的联系。A存储和逻辑结构 B存储和抽象C理想和抽象 D理想与逻辑( )2.计算机识别、存储和加工处理的对象被统称为A.数据 B.数据元素C.数据结构 D.数据类型()3.若需要利用形参直接访问实参，则应把形参变量说明为—参数。A.指针 B.引用C.值 D.变量()4.算法指的是A.计算机程序 B.解决问题的计算方法C.排序算法 D.解决问题的有限运算序列( )5.若需要利用形参直接访问实参，则应把形参变量说明为参数。A指针 B引用C值 D常量( )6.下面算法的时间复杂度为―。intf(intn){if (n——0)return 1；else return n*f (n-1)；}A. O(1) B.O(n)C.O(n2) D.O(n!)( )7.数据结构是一门研究非数值计算的程序设计问题中计算机的(①)以及它们之间的(②)和运算的学科①A、操作对象B、计算方法C、逻辑存储D、数据映象②A、结构B、关系C、运算D、算法( )8.数据结构被形式地定义为(K,R),其中K是(①)的有限集合，R是K上(②)的有限集合①A、算法B、数据元素C、数据操作D、逻辑结韵

②A、②A、操作B、映象C、存储口、关系（ ）9.在数据结构中，从逻辑上可以把数据结构分为A、动态结构和静态结构 B、紧凑结构和非紧凑结构C、C、线性结构和非线性结构D、内部结构和外部结构（ ）10.线性表的顺序存储结构是一种的存储结构，线性表的链式存储结构是一种的存储结构A、随机存取 B、顺序存取C、索引存取 D、HASH存取（ ）11.算法分析的目的是（①），算法分析的两个主要方面是（②）①A、找出数据结构的合理性 C、分析算法的效率以求改进^、研究算法中的输入和输出的关系D、分析算法的易懂性和文档性②A、空间复杂性和时间复杂性C、可读性和文档性B、正确性和简明性 D、数据复杂性和程序复杂性（ ）12.计算机算法指的是（①），它必具备输入、输出和（②）等五个特性①A、计算方法 B、排序方法C、解决莱一问题的有限运算序列 D、调度方法②A、可执行性、可移植性和可扩充性 C、确定性、有穷性和稳定性B、可执行性、确定性和有穷性 D、易谩性、稳定性和安全性（）13.对于两个函数，若函数名相同，但只是不同则不是重载函数。A、参数类型 B、参数个数C、函数类型 D、函数变量（ ）14.若需要利用形参直接访问实参，则应把形参变量说明为参数B、引用AB、引用C、值 D、函数()15.下面程序段的时间复杂度为。for(inti=0;i<m;i++)for(intj=0;j<n;j++)A[i][j]=i*j;A、O(m2) B、O(n2)C、O(m*n) D、O(m+n)()16.执行下面程序段时，执行S语句的次数为。/*n*i*/for(inti=1;i<=n;i++)for(intj=1;j<=i;j++)S;A、n2 B、n2/2C、n(n+1) D、n(n+1)/2( )17.下面算法的时间复杂度为。intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);}A、O(1) B、O(n)C、O(n2) D、O(n!)1-5AAADA6-BDADACBA11-CACBCAC16-17DB二.线性表()1.设单链表中结点的结构为typedefstructnode{file:〃链表结点定义ElemTypedata；file:〃数据structnode*Link；file:〃结点后继指针}ListNode；已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作A.s->link=p；p->link=s； B.s->link=p->link；p->link=s；C.s->link=p->link；p=s； D.p->link=s；s->link=p；()2.设单链表中结点的结构为typedefstructnode{file:〃链表结点定义ElemTypedata；file:〃数据structnode*Link；file:〃结点后继指针}ListNode；非空的循环单链表first的尾结点(由p所指向)满足：A.p->link==NULL； B.p==NULL；C.p->link==first； D.p==first；()3.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是A.O(1) B.O(n)C.O(nlogn) D.O(n2)()4.在长度为n的顺序存储的线性表中，删除第i个元素(IWiWn)时，需要从前向后依

次前移一个元素。A、n-i B、n-i+1C、n-i-1 D、i( )5.在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行―。q—>next=p—>next；p—>next=q；C.q—>next=p—>next；p—>next=q；p一〉next=q—>next；q=p； D.p一〉next=q—>next；q一〉next=p；()6.线性表采用链式存储时，结点的存储地址 A.必须是不连续的 B.连续与否均可C.必须是连续的 D.和头结点的存储地址相连续()7.将长充为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为A.O(1) B.O(n)C.O(m) D.O(m+n)( )8.设单链表中结点的结构为(data,link).E知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s,则应执行下列哪一个操作A.s->link=p->link;p->link=s; B.p->link=s;s->link=q;p->link=s->link;s->link=p; D.q->link=s;s->link=p;()9.线性链表不具有的特点是。A.随机访问 B.不必事先估计所需存储空间大小C.插入与删除时不必移动元素 D.所需空间与线性表长度成正比( )10.线性表若采用链表存储结构时，要求内存中可用存储单元的地址 A、A、必须是连续的B、部分地址必须是连续的c、一定是不连续的D、连续不连续都可以()11.在一个长度为n的顺序存储线性表中，向第i个元素(1WiWn+1)之前插入一个新元素时，需要从后向前依次后移 个元素。A、n-i B、n-i+1C、n-i-1 D、i()12.在一个长度为n的顺序存储线性表中，删除第i个元素(1WiWn+1)时，需要从前向后依次前移个元素。A、n-i B、n-i+1C、n-i-1 D、i()13.在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度(即x同元素的平均比较次数，假定查找每个元素的概率都相等)为。A、n B、n/2C、(n+1)/2 D、(n-1)/2()14.在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行。HL=p;p->next=HL;C、p->next=HL;p=HL;p->next=HL;HL=p;D、p->next=HL->next;HL->next=p;()15.在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行。q->next=p->next;p->next=q;C、q->next=p->next;p->next=q;p->next=q->next;q=p; D、p->next=q->next;q->next=p;()16.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行。A、p=q->next;p->next=q->next;B、p=q->next;q->next=p->next;C、p=q->next;q->next=p;D、q->next=q->next->next;q->next=q1-5BCBAD6-10BCDAD11-15BADDD16B三.栈和队列)1.在堆栈中存取数据的原则是一。A先进先出 B后进先出C先进后出 D随意进出)2.由两个栈共享一个向量空间的好处是。A减少存取时间，降低下溢发生的机率 B节省存储空间，降低上溢发生的机率C减少存取时间，降低上溢发生的机率 D节省存储空间，降低下溢发生的机率)3.设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为A.O(1) B.O(log2n)C.O(n) D.O(n2)()4.队和栈的主要区别是A.逻辑结构不同 B.存储结构不同C.所包含的运算个数不同 D.限定插入和删除的位置不同( )5.链栈与顺序栈相比，比较明显的优点是A.插入操作更加方便 B.删除操作更加方便C.不会出现下溢的情况 D.不会出现上溢的情况()6.假定一个顺序队列的队首和队尾指针分别为f和r,则判断队空的条件为

A、A、f+1==rf==0 D、f==r( )7.在一个顺序队列中，队首指针指向队首元素的—位置。A.前一个 B.后一个C.当前 D.最后一个()8.由两个栈共享一个向量空间的好处是：A.减少存取时间，降低下溢发生的机率B.节省存储空间，降低上溢发生的机率C.减少存取时间，降低上溢发生的机率D.节省存储空间，降低下溢发生的机率()9.设数组Data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为front=front+1 B.front=(front+1)%(m-1)front=(front-1)%m D.front=(front+1)%m( )10.链式栈与顺序栈相比，一个比较明显的优点是。A.插入操作更加方便 B.通常不会出现栈满的情况C.不会出现栈空的情况 D.删除操作更加方便( )11.若让元素1,2,3依次进栈，则出栈次序不可能出现种情况。A.3,2,1 B.2,1,33,1,2 D.1,3,2( )12.假定一个顺序队列的队首和队尾指针分别为front和rear,存放该队列的数组长度为N,则判断队空的条件为。A.(front+1)%N==rear C.front==0B.(rear+1)%B.(rear+1)%N==frontD.front==rear（）13.栈的插入和删除操作在进行.（A）.栈顶 （B）.栈底（C）.任意位置 （D）.指定位置（ ）14.在一个顺序循环队列中，队首指针指向队首元素的位置。A.后两个 B.后一个C.当前 D.前一个（ ）15.在以下的叙述中，正确的是A、线性表的线性存储结构优于链表存储结构 C、栈的操作方式是先进先出B、二维数组是它的每个数据元素为一个线性表的线性表D、队列的操作方式是先进后出（）16.栈的插入与删除操作在进行。A、栈顶 B、栈底C、任意位置 D、指定位置（）17.当利用大小为N的一维数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行语句修改top指针。A、top++ B、top--C、top=0 D、top（）18.若让元素1,2,3依次进栈，则出栈次序不可能出现种情况。A、3,2,1 B、2,1,3C、3,1,2 D、1,3,2（）19.在一个循环顺序队列中，队首指针指向队首元素的位置。A、前一个 B、后一个C、当前DC、当前()20.当利用大小为N的一维数组顺序存储一个循环队列时，该队列的最大长度为。A、N-2 B、N-1C、N D、N+1()21.从一个循环顺序队列删除元素时，首先需要。A、前移一位队首指针 B、后移一位队首指针C、取出队首指针所指位置上的元素 D、取出队尾指针所指位置上的元素()22.假定一个循环顺序队列的队首和队尾指针分别为f和r,则判断队空的条件是。A、f+1==r B、r+1==fC、f==0 D、f==r()23.假定一个链队的队首和队尾指针分别为front和rear,则判断队空的条件是。A、 front==rear B、front!=NULLC、 rear!=NULL D、front==NULL栈和队列 1—5CBC D D 6—10 D A B DB11—15CDADBTOC\o"1-5"\h\z16—20AB C A B 21—23 B DA四.串( )1.在目标串T[0…n-1]="xwxxyxy”中，对模式串p[0・「m-1]="xy”进行子串定位操作的结果A.0 B.2C.3 D.5()2.如下陈述中正确的是A.串是一种特殊的线性表 B.串的长度必须大于零C.串中元素只能是字母 D.空串就是空白串

（）3.若目标串的长充为n,模式串的长度为[n/3],则执行模式匹配算法时，在最坏情况下的时间复杂度是A.O（1） B.O（n）C.O（n2） D.O（n3）串1—3CAB五.数组和广义表（）1.二维数组A按行顺序存储，其中每个元素占1个存储单元。若A[1][1]的存储地址为420,A[3][3]的存储地址为446,则A[5][5]的存储地址为A.470 B.471C.472 D.473（）2.在稀疏矩阵的十字链接存储中，每个列单链表中的结点都具有相同的。A.行号 B.列号C.元素值 D.地址（）3.一个数组元素A[i]与的表示等价。A、*（A+i） B、A+iC、*A+i D、&A+i（）4.在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的A、行号B、列号C、C、元素值D、地址数组1—4CAAA广义表()1.已知广义表的表头为A,表尾为(B,C),则此广义表为A.(A,(B,C)) B.(A,B,C)C.(A,B,C) D.(