数据结构总复习题(JAVA).doc

《数据结构总复习题(JAVA).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.一、填空题1.栈和队列的共同特点是（只允许在端点处插入和删除元素）。2.在深度为5的满二叉树中，叶子结点的个数为（31）3.算法分析的目的是（分析算法的效率以求改进）。4.由两个栈共享一个存储空间的好处是（节省存储空间，降低上溢发生的机率）。5.串的长度是（串中所含字符的个数）。6.设有两个串p和q，求q在p中首次出现位置的运算称做（模式匹配）7.N个顶点的连通图中边的条数至少为（N-1）。8.N个顶点的强连通图的边数至少有（N）。9.对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为（N）。P25910.假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为（n(

2、n-1)/2）。P29211.在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。12.在具有n个单元的循环队列中，队满时共有n-1个元素。13.有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的出度。14.用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度递增的次序来得到最短路径的。教育资料.15.在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。16．在一个循环队列中，队首指针指向队首元素的前一个位置。17．在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有

3、关。18.线性表中结点的集合是有限的，结点间的关系是一对一的。19.数据结构被形式地定义为（D,R），其中D是数据元素的有限集合，R是D上的关系有限集合。20.线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。21.一个算法的效率可分为时间效率和空间效率。22.在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。23.在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。24.在具有n个单元的循环队列中，队满时共有n-1个元素。25.对于栈只能在栈顶插入和删除元素；

4、对于队列只能在队尾插入和队首删除元素。26.一棵深度为6的满二叉树有n1+n2=0+n2=n0-1=31个分支结点和26-1=32个叶子。27.有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的教育资料.出度。27.用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度递增的次序来得到最短路径的。29.n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为O(n2)。二、单项选择题1.线性表L＝（a1,a2,a3,……ai,……an），下列说法正确的是（）  A.每个元素都有一个直接前件和直接后件  B.线性表中至少要有一个元素C.表中诸元素的排列顺序必须是由小到

5、大或由大到小D.除第一个和最后一个元素外，其余每个元素都有一个且只有一个直接前趋和直接后继（A）2.算法分析的两个主要方面是：A)空间复杂性和时间复杂性B)正确性和简明性C)可读性和文档性D)数据复杂性和程序复杂性（A）3.判定一个队列QU（最多元素为m0）为满队列的条件是Ａ．QU->front==(QU->rear+1)%m0Ｂ．QU->rear－QU->front－1==m0Ｃ．QU->front==QU->rearＤ．QU->front==QU->rear+1（B）4．线性表Ｌ在情况下适用于使用链式结构实现。Ａ.需经常修改Ｌ中的结点值Ｂ.需不断对Ｌ进行删除插入教育资料.Ｃ.Ｌ中含有

6、大量的结点Ｄ.Ｌ中结点结构复杂5.从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是A，第二次出栈得到的元素是B是；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是C，第二次出队得到的元素是D。经操作后，最后在栈中或队中的元素还有E个。供选择

7、的答案：A～D：①a1②a2③a3④a4E：①1②2③3④0答案：A=（②）B=（④）C=（①）D＝（②）E=（②）（B）6.有8个结点的无向图最多有条边。A．14B.28C.56D.1127．从供选择的答案中，选出应填入下面叙述内的最确切的解答，把相应编号写在答卷的对应栏内。栈是一种线性表，它的特点是A。设用一维数组A[1,…教育资料.,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入