数据结构期末考试复习试题(整理完的)

数据结构与算法复习题一、选择问题。1 .在数据结构中，逻辑上数据结构可分为c。c .线性结构和非线性结构2 .数据结构在计算机存储器中的显示是指a。a .数据的存储结构3 .在数据结构中，与使用的计算机无关，是数据的a结构。a .逻辑4 .在存储数据的情况下，通常不仅存储各个数据要素的值，还存储c。c .数据元素之间的关系5 .决定选择哪个存储结构通常不考虑a。a .各节点的值如何？6 .以下说法正确的是d。d .一些表面上非常不同的数据可以具有相同的逻辑结构7 .算法分析的目的是c，算法分析的两个主要方面是a。(1)分析和改进c .算法的效率；(2)A .空间复杂度和时间复杂度8 .下一段的时间复杂性是O(n2)。s=0；for(I=0； inext=NULL16 .一个表中最常用的操作用于在最后一个节点之后插入节点或删除最后一个节点d存储方式最节省运算时间。d .起始节点的双循环链路表17 .需要分配很大的空间，需要插入并删除不需要移动元素的线性表，其存储结构为b。b .静态链表18 .非空循环链路表头的尾部节点(用p指示)满足c。C.p-next=head19 .在循环双链接表的p所指的节点之前插入s所指的节点的操作是d。D.s-next=p； s-prior=p-prior； p-prior-next=s； p-prior=s20 .如果最常用的操作将采用第I个节点及其前驱体，则d存储方案最能节省时间。d .序表21 .在具有n个节点的有序单链路表中插入新节点，维持有序的时间复杂度为b。B.O(n )22 .在长度为n(n1 )的单个链接表中设置开头和末尾的两个指针，执行b操作与链接表的长度有关。b .删除链表的最后一个元素2-3 .双链路显示的一个优势是与单链路显示相比，d。d .依次访问相邻节点更为灵活24 .如果对路线表只有两个操作，建议使用b删除第一个元素，并在最后一个元素之后插入新元素。b .只有表末尾的指针没有标题指针的循环链接表25 .将元素(1 i n 1)插入长度为n的顺序表中的第I个位置，并且将元素的移动次数设置为a。a.ni1b.nIC.id.I126 .只对表头、尾的两端进行插入操作的线性表的情况下，应该采用的记忆构造是c。c .以尾指针表示的循环链路表27 .以下哪一项是顺序存储结构的优点？ c。c存储密度高28 .以下关于线性表的描述中，哪个是错误的？ b。a线表采用顺序存储，必须占用连续的存储单元b线表采用顺序存储，易于插入和删除。c线制表采用链式记忆，无需占用连续的记忆单元d线表是链式记忆的，容易插入和删除。29 .线性表是具有n个b的有限序列。b .数据要素30 .在n个节点的线性表阵列实现中，算法的时间复杂度为O(1)的操作为a。a .访问第I个节点(i(1=i=n )求第I个节点的直接前驱体(1next=p-next； p-next=s；36 .线性表的顺序存储结构是a。a .随机访问的存储结构37 .堆栈的特征是b，队列的特征是a。a .先进先出b .先进后出38 .堆栈和队列的共同点是c。c .只允许在端点处插入和删除元素39 .如果一个堆栈的输入序列为a、b、c、d和e，那么堆栈的不可能输出序列为c。A.edcba B.decba C.dceab D.abcde40 .有一个堆栈，元素按顺序堆栈的顺序是a、b、c、d、e。 下面的c是不可能的堆栈序列。A.A，b，c，d，E B.B，c，d，e，A C.E，a，b，c，d.e，d，c，b，a41 .以下b不是队列的基本运算吗？a .从队列末尾插入新的元素b。 从队列中删除第I个元素c .读取确定队列是否为空的d .队列标头元素的值42 .如果发现一个堆栈的堆栈序列是1，2，3，n，其输出序列是p1，p2，p3，pn，并且如果p1=n，则pi是c。A.i B.n-i C.n-i 1 D .不明43 .一个序列堆栈st (最大要素是MaxSize )判定为空的条件是b。B.st-top=-144 .判定一个序列堆栈st (最大要素是MaxSize )已满的条件是d。D.st-top=MaxSize45 .如果一个队列的入队序列是1、2、3、4，则该队列的输出序列是b。b.1，2，3，446 .一个循环队列qu (最大元素是最大元素)确定为空的条件是c。C.qu-rear=qu-front47 .如果在循环队列中前端和后端分别指示头元素和尾元素的位置，则确定循环队列为空的条件为c。C.front=rear48 .在一个堆栈指针为h的开头节点的链堆栈中插入指针s指向的节点时，执行d操作。D.s-next=h-next； h-next=s；49 .如果输入序列可以是ABC并且可以是CBA，则通过堆栈操作b。b .推，推，推，推，pop，pop50 .堆栈以依次存储方式存储，如果当前两个堆栈分别表示第1个和第2个堆栈的堆栈顶部，堆栈1的底部是V1，堆栈2的底部是Vm，则堆栈满足的条件是b。B. top1 1=top251 .设计了一种用于判断公式中的左、右括号是否成对的算法，并且d数据结构是最优的。d .堆栈52 .队列允许的操作是d。d .删除队列元素53 .关于循环队列d。a无法判断队列是否为空b无法判断队列是否已满c .行列d .以上的说法是错误的54 .使用1个大小为6的数值来实现循环队列，如果当前的rear和front的值分别为0和3，则从队列中删除1个要素，并且再加上2个要素，则rear和front的值分别为b。B.2和455 .队列的“先进先出”特性指d。d .每次从队列中删除时插入的第一个元素56 .与有序堆栈相比，链式堆栈具有明显的优点是a。a .通常堆栈不会装满57 .在没有开头节点的链接表中存储队列，如果该开头指针指向队列的开头节点，末尾指针指向队列的末尾节点，则进行出场操作时c。c .可能会修改开头、结尾的指针58 .如果串s=软件，则该子串的数目是b。B.3759 .字符串的长度指b。b .字符串中包含的字符数60 .字符串是特殊的线性表，其特殊性出现在b。b .数据元素是字母61 .有两列p和q，求q在p首次出现的位置的运算称为b。b .模式匹配62 .对于阵列a，每个元素的长度是3字节，下标I是1到8，下标j是1到10，并且在从开头地址SA连续存储的存储器中，该阵列是以行存储的元素A85的开头地址是c。C.SA 22263 .对于阵列a，每个元素的长度是3字节，下标I是1到8，下标j是1到10，并且在从开头地址SA连续存储的存储器中，该阵列是以行存储的元素A58的开头地址是c。C.SA 22264 .声明浮点数组时，froat average=new float30；假设阵列的存储器开始位置是200，并且average15的存储器地址是c。C.26065 .一旦将二维阵列A1 m，1 n逐行存储在阵列b中，则在二维阵列元素Ai，j的一维阵列b中，下标记为a。A.n*(i-1) j如果存在10090个稀疏矩阵，其中具有除了66.0之外的元素，每个整数占用2个字节，则以三元组表示该矩阵所需的字节数为b。B. 66包括在阵列A0 4，- 13，57 中的元素的数目是a。A.5568 .压缩并存储矩阵是为了d。d .减少存储容量69 .有一个10层的对称矩阵a，采用压缩存储方式，行顺序为主存储，a 1，1为第一要素，其存储地址为1，各要素占据一个地址空间，a 8，5的地址为b。B. 3370 .稀疏矩阵的一般压缩存储方式有c这两种。c .三元组和十字链表71 .树最适合代表c。c .要素之间存在分支层次关系的数据72 .深度为5的二叉树最多有c个节点。C. 3173 .一个满二叉树，m个叶，n个节点，深度h，d。D n=2h-174 .任何一个二叉树的叶节点以前序、中序和后序扫描阵列中的相对顺序a。a .没有变更75 .在线索化树中，必须对每个节点设置表示其左右链是指定树结构信息还是指定线索化信息的标志。 如果0代表树结构信息，1代表线索，并且对应的叶节点的左右链段应当表示为_ D _。D.1176 .在以下讨论中，正确的是d。只有一个节点的二叉树的度为0二叉树的度为2 二叉树左右的子树可以任意交换深度k的顺二叉树的节点数在深度相同的满二叉树以下。A. B. C. D.77 .设与森林f对应的二叉树为b，其中有m个节点，设b的根为p，p的右侧子树的节点数为n，森林f的最初的树的节点数为a。A.m-n78 .如果一个二叉树具有10个度为2的节点和5个度为1的节点，则度为0的节点的数目为b。B.1179 .具有10个叶节点的二叉树有b个度为2的节点。B.980 .在无向图中，所有顶点的度数之和等于所有边数的c倍。C 2战斗机81 .在有向图中，所有顶点的进度之和等于所有顶点的出度之和的b倍。B 1战斗机82 .某二叉树节点的中序序列为ABCDEFG，后序序列为BDCAFGE，其左子树的节点数为： cC.483 .众所周知，算术式的后缀形式为a b * cd/e，后缀形式为abc*de/-，后缀形式为d。d .a * BC/de84 .如图所示，从顶点a用深度