java数据结构综合练习

综合练习一、单项选择题1.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（C）。A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构2.设语句x++的时间是单位时间，则以下语句的时间复杂度为（B）。for(i=1;i=n;i++)for(j=i;j=n;j++)x++;A.O(1)B.O(2n)C.O(n)D.O(3n)3.链式存储结构的最大优点是（D）。A.便于随机存取B.存储密度高C.无需预分配空间D.便于进行插入和删除操作4.假设在顺序表{a0,a1,……,an－1}中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地址为100，则第7个数据元素的存储地址是（D）。A.106B.107C.124D.1285.在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（A）存储方式。A.顺序表B.带头结点的单链表C.不带头结点的单链表D.循环单链表6.在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用（C）存储方式。A.顺序表B.用头指针标识的循环单链表C.用尾指针标识的循环单链表D.双向链表7.在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（C）。O(1)B.O(log2n)C.O(n)D.O(n2)8.要将一个顺序表{a0,a1,……,an-1}中第i个数据元素ai(0≤i≤n-1)删除，需要移动（B）个数据元素。A.iB.n-i-1C.n-iD.n-i+19.在栈中存取数据的原则是（B）。A.先进先出B.先进后出C.后进后出D.没有限制10.若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（D）。A．1234B.1324C.4321D.142311.在链栈中，进行出栈操作时（B）。A．需要判断栈是否满B.需要判断栈是否为空C.需要判断栈元素的类型D.无需对栈作任何差别12.在顺序栈中，若栈顶指针top指向栈顶元素的存储单元，且顺序栈的最大容量是maxSize，则顺序栈的判空条件是（B）。A．top==0B.top==-1C.top==maxSizeD.top==maxSize-113.在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（D）。A．top==0B.top==-1C.top==maxSizeD.top==maxSize-114.在队列中存取数据元素的原则是（A）。A．先进先出B.先进后出C.后进后出D.没有限制15.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判空条件是（A）。A．front==rearB.front!=rearC.front==rear+1D.front==(rear+1)%maxSize16.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判满条件是（D）。A．front==rearB.front!=rearC.front==rear+1D.front==(rear+1)%maxSize17.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（C）。A．rear-frontB.rear-front+1C.(rear-front+maxSize)%maxSizeD.(rear-front+1)%maxSize18.设长度为n的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，则入队操作的时间复杂度为（B）。A．O(1)B．O(n)C．O(log2n)D．O(n2)19.串的长度是指(A)A.串中包含的字符个数B.串中包含的不同字符个数C.串中除空格以外的字符个数D.串中包含的不同字母个数20.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（C）A．求子串B．联接C．模式匹配D．求串长21.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主进行存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（B）。A.13B.33C.18D.4022.7.有一个二维数组A[1..6,0..7]，每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组占用的存储空间大小是（D）个字节。A.48B.96C.252D.28823.在哈夫曼树中，任何一个结点它的度都是（C）。A.0或1B.1或2C.0或2D.0或1或224.对一棵深度为h的二叉树，其结点的个数最多为（D）。A.2hB.2h-1C.2h-1D.2h-1C.只有一个根结点D.任意一棵二叉树25.假设一棵二叉树中度为1的结点个数为5，度为2的结点个数为3，则这棵二叉树的叶结点的个数是（C）A．2B.3C.4D.526.若某棵二叉树的先根遍历序列为ABCDEF，中根遍历序列为CBDAEF，则这棵二叉树的后根遍历序列为（B）。A.FEDCBAB.CDBFEAC.CDBEFAD.DCBEFA27.在有n个结点的二叉树的二叉链表存储结构中有（C）个空的指针域。A．n-1B.nC.n+1D.028.在一个有错误!未找到引用源。个顶点的有向图中，若所有顶点的出度之和为错误!未找到引用源。，则所有顶点的入度之和为（A）。A.错误!未找到引用源。B.错误!未找到引用源。C.错误!未找到引用源。D.错误!未找到引用源。29.具有6个顶点的无向图至少应有（A）条边才能确保是一个连通图。A.5B.6C.7D.830.一个有n个顶点的无向图最多有（C）条边。A.错误!未找到引用源。B.错误!未找到引用源。C.错误!未找到引用源。D.错误!未找到引用源。31.对某个无向图的邻接矩阵来说，下列叙述正确的是（A）。A.第错误!未找到引用源。行上的非零元素个数和第错误!未找到引用源。列上的非零元素个数一定相等B.矩阵中的非零元素个数等于图中的边数C.第错误!未找到引用源。行与第错误!未找到引用源。列上的非零元素的总数等于顶点错误!未找到引用源。的度数D.矩阵中非全零行的行数等于图中的顶点数32.任何一个无向连通图的最小生成树（B）。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在33.对线性表进行二分查找时，要求线性表必须(B)A.以顺序方式存储B.以顺序方式存储，且结点按关键字值有序排列C.以链接方式存储D.以链接方式存储，且结点按关键字值有序排列34.用二分查找法查找具有n个结点的顺序表时，查找每个结点的平均比较次数是(D)A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)35.若有一个长度为64的有序表，现用二分查找方法查找某一记录，则查找不成功，最多需要比较(B)次。A.9B.7C.5D.336.当采用分块查找时，数据的组织方式为(C)A.数据必须有序B.数据不必有序C.数据分成若干块，每块内数据不必有序，但块间必须有序D.数据分成若干块，每块内数据必须有序，但块间不必有序37.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为(D)A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构38.下面给出的四种排序算法中，(B)是不稳定的排序。A．插入排序B．堆排序C．二路归并排序D．冒泡排序39.在下列排序算法中，哪一种算法的时间复杂度与初始排序序列无关（D）。A．直接插入排序B．冒泡排序C．快速排序D．直接选择排序40.关键字序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中(C)的两趟排序后的结果。A．选择排序B.冒泡排序C.插入排序D.堆排序41.一组记录的关键字为（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)42.在对一组关键字序列{70，55，100，15，33，65，50，40，95}，进行直接插入排序时，把65插入，需要比较(A)次。A.2B.4C.6D.843.从待排序的序列中选出关键字值最大的记录放到有序序列中，该排序方法称为(B)。A.希尔排序B.直接选择排序C.冒泡排序D.快速排序44.当待排序序列基本有序时，以下排序方法中，(B)最不利于其优势的发挥。A.直接选择排序B.快速排序C.冒泡排序D.直接插入排序45.在待排序序列局部有序时，效率最高的排序算法是(B)。A.直接选择排序B.直接插入排序C.快速排序D.归并排序二、填空题1.一个串的任意连续字符组成的子序列称为串的子串，该串称为主串。2.若两个串的长度相等且对应位置上的字符也相等，则称两个串相等。3.寻找子串在主串中的位置，称为模式匹配。其中，子串又称为模式串。4.设数组A[1..5,1..6]的基地址为1000，每个元素占5个存储单元，若以行序为主序顺序存储，则元素A[5,5]的存储地址为1140。5.在稀疏矩阵的三元组顺序表存储结构中，除表示非零元的三元组表以外，还需要表示矩阵的行数、列数和非零元个数。6.一个n×n的对称矩阵，如果以相同的元素只存储一次的原则进行压缩存储，则其元素压缩后所需的存储容量为n(n+1)/2。7.对矩阵压缩的目的是为了节省存储空间。8.循环顺序队列是将顺序队列的存储区域看成是一个首尾相连的环，首尾相连的状态是通过数学上的求模（或取余）运算来实现的。9.一棵具有100个结点的完全二叉树，其叶结点的个数为50。10.以{5，9，12，13，20，30}为叶结点的权值所构造的哈夫曼树的带权路径长度是217。11.有m个叶结点的哈夫曼树中，结点的总数是2m-1。12.若一棵完全二叉树的第4层(根结点在第0层)有7个结点，则这棵完全二叉树的结点总数是11。13.在深度为k的完全二叉树中至少有k个结点，至多有2k-1个结点。14.假定待查找记录个数为n,则在等概率的情况下，顺序查找在查找成功情况下的平均查找长度为(n+1)/2；在查找失败情况下的平均查找长度为n+1。15.对线性表进行二分查找时，要求线性表必须以顺序方式存储，且数据有序。16.分块查找分为两个阶段，分别是确定待查元素所在的块和在块内查找待查的元素。17.哈希法存储中，冲突指的是不同关键字值对应到相同的存储地址。18.一棵二叉排序树用中序遍历输出的信息是递增序列。19.哈希法存储的基本思想是根据关键字来决定存储地址。20.若用错误!未找到引用源。表示图中顶点数，则有错误!未找到引用源。条边的无向图称为完全图。21.错误!未找到引用源。个顶点的连通无向图至少有错误!未找到引用源。条边，至多有错误!未找到引用源。条边。22.若有向图错误!未找到引用源。的邻接矩阵为：则顶点错误!未找到引用源。的入度是3。23.对于一个有向图，若一个顶点的度为错误!未找到引用源。，出度为错误!未找到引用源。，则对应逆邻接表中该顶点单链表中的边结点数为错误!未找到引用源。。24.在求最小生成树的两种算法中，克鲁斯卡尔算法适合于稀疏图。25.数据结构中的迪杰斯特拉算法是用来求某个源点到其余各顶点的最短路径。26.执行排序操作时，根据使用的存储器可将排序算法分为内排序和外排序。27.在对一组记录序列{50,40,95,20,15,70,60,45,80}进行直接插入排序时，当把第7个记录60插入到有序表中时，为寻找插入位置需比较3次。28.在直接插入排序和直接选择排序中，若初始记录序列基本有序，则