whut数据结构复习题+参考答案

1复习题集一判断题（×）1．线性表在物理存储空间中也一定是连续的。（×）2．顺序存储方式只能用于存储线性结构。（√）3．栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（√）4．两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（×）5．二叉树的度为2。（√）6．若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。（×）7．二叉树中每个结点的两棵子树的高度差等于1。（√）8．用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（×）9．在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。（×）10．计算机处理的对象可以分为数据和非数据两大类。[计算机处理的对象都是数据]（×）11．数据的逻辑结构与各数据元素在计算机中如何存储有关。（×）12．算法必须用程序语言来书写。（×）13．判断某个算法是否容易阅读是算法分析的任务之一。（×）14．顺序表是一种有序的线性表。[任何数据结构才用顺序存储都叫顺序表]（√）15．分配给顺序表的内存单元地址必须是连续的。（√）16．栈和队列具有相同的逻辑特性。[它们的逻辑结构都是线性表]（√）18．树形结构中每个结点至多有一个前驱。（×）19．在树形结构中，处于同一层上的各结点之间都存在兄弟关系。（×）20．如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。（×）21．如果表示图的邻接矩阵是对称矩阵，则该图一定是有向图。（×）22．顺序查找方法只能在顺序存储结构上进行。（×）23．折半查找可以在有序的双向链表上进行。（√）24．满二叉树中不存在度为1的结点。（×）25．完全二叉树中的每个结点或者没有孩子或者有两个孩子。（√）26．对n个元素执行快速排序，在进行第一次分组时，排序码的比较次数总是n-1次。（√）27．在有向图中，各顶点的入度之和等于各顶点的出度之和。一、选择题（A）1.在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是：A)访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）C)删除第i个结点（1≤i≤n）B)在第i个结点后插入一个新结点（1≤i≤n）D)将n个结点从小到大排序（C）2.算法分析的目的是：A)找出数据结构的合理性B)研究算法中的输入和输出的关系C)分析算法的效率以求改进D)分析算法的易懂性和文档性2（A）3.算法分析的两个主要方面是：A)空间复杂性和时间复杂性B)正确性和简明性C)可读性和文档性D)数据复杂性和程序复杂性（B）4.计算机算法必须具备输入、输出和等5个特性。A)可行性、可移植性和可扩充性B)可行性、确定性和有穷性C)确定性、有穷性和稳定性D)易读性、稳定性和安全性（B）5.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是:（A）110（B）108（C）100（D）120（A）5.链接存储的存储结构所占存储空间：（A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针（B）只有一部分，存放结点值（C）只有一部分，存储表示结点间关系的指针（D）分两部分，一部分存放结点值，另一部分存放结点所占单元数（B）6.一个栈的输入序列为1，2，3，…，n，若输出序列的第一个元素是n，输出第i（1≤i≤n）个元素是。A)不确定B)n－i＋1C)iD)n－i（B）7.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。A)(rear＋1)%n==frontB)rear===frontC)rear＋1==frontD)(rear－l)%n==front（A）8.循环队列A[0..m－1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是:A)(rear－front＋m)%mB)rear－front＋1C)rear－front－1D)rear－front（C）9.按照二叉树的定义，具有3个结点的二叉树有（）种。A)3B)4C)5D)6[利用排列组合知识来做]（B）10.具有n(n0)个结点的完全二叉树的深度为:(Ａ)log2(n)(Ｂ)log2(n)(Ｃ)log2(n)+1(Ｄ)log2(n)+1（C）11．在高度为h的完全二叉树中，表述正确的是（）A.度为0的结点都在第h层上B.第i(1≤ih)层上的结点都是度为2的结点C.第i(1≤ih)层上有2i-1个结点D.不存在度为1的结点（B）12.深度为5的二叉树至多有（）个结点。A)32B)31C)16D)10（A）13.用邻接表表示图进行深度优先遍历时，通常采用()结构来时实现算法。A)栈B)队列C)树D)图（D）14.对N个记录作顺序查找时，当查找成功时，平均查找长度是（）。A)N2B)N2/2C)ND)（N﹢1)/2（B）15.当一个有n个顶点的图用邻接矩阵A表示时，顶点Vi的度是（）。A)nijiA1],[B)njjiA1],[C)niijA1],[D)nijiA1],[+njijA1],[（C）16．某算法的时间复杂度为O(2n)，表明该算法的（）A.问题规模是2nB.执行时间等于2nC.执行时间近似与2n成正比D.问题的规模近似与2n成正比（D）17．“二叉树为空”意味着二叉树（）A.由一些没有赋值的空结点构成B.根结点没有子树C.不存在D.没有结点3（D）18．数据结构的研究内容不涉及（）A.数据如何组织B.数据如何存储C.数据的运算如何实现D.算法用什么语言描述（C）19．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法（D）20．数据采用顺序存储，要求（）A.存储的是属于线性结构的数据B.根据结点值的大小，有序存放各结点C.按存储单元地址由低到高的顺序存放各结点D.各结点存放方法有规律，能隐含表示结点间的逻辑关系（D）21．一个顺序表所占存储空间大的大小与（）无关A.顺序表长度B.结点类型C.结点中各字段的类型D.结点存放顺序（A）22．数据采用链接存储，要求（）A.每个结点占用一片连续的存储区域B.所有结点占用一片连续的存储区域C.结点的最后一个字段是指针型的字段C.每个结点有多少个后继，就设多少个指针字段（A）23．算法的时间复杂度与（）有关A.问题规模B.计算机硬件性能C.编译程序质量D.程序设计语言（C）24．在程序中，为了设置一个空的顺序表，必须（）A.给各数组元素赋空值B.给各顺序表元素赋空值C.给表示顺序表长度的变量赋初始值D.给数组变量名赋初始值（D）25．若变量H是某个带表头结点循环单向链表的表头指针，则在该链表最后的一个结点的后继指针域中存放的是（）A.H的地址B.H的值C.表头结点的值D.首元结点的地址（A）26．栈和队列的共同点在于（）A.逻辑特性B.存储结构C.运算方法D.元素类型（C）27．栈和队列的共同点在于（）A.都对存储方法作了限制B.都是只能进行插入、删除运算C.都对插入、删除的位置作了限制D.都对插入、删除两中操作的先后顺序作了限制（C）28．若5个元素的进栈序列是1,2,3,4,5，则不可能得到出栈序列（）A.1，2，3，4，5B.3，4，2，5，1C.4，2，1，3，5D.5，4，3，2，1（A）29．顺序循环队列中是否可以插入下一个元素，（）A.与队首指针和队尾指针的值有关B.只与队尾指针的值有关，与队首指针的值无关C.只与数组大小有关，与队首指针和队尾指针的值无关D.与曾经进行过多少次插入操作有关（A）30．在顺序队列中，元素的排列顺序（）A.由元素插入队列的先后顺序决定B.与元素值的大小有关C.与队首指针和队尾指针的取值有关D.与数组大小有关（C）31．在高度为h的完全二叉树中，（）A.度为0的结点都在第h层上B.第i(1≤ih)层上的结点都是度为2的结点C.第i(1≤ih)层上有2i-1个结点D.不存在度为1的结点（B）32．一颗二叉树如图所示，其中序遍历的序列为（）4A.ABDGCEFHB.DGBAECHFC.GDBEHFCAD.ABCDEFGH二、填空题1.在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。2.已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾结点，试从下列提供的答案中选择合适的语句序列。删除P结点的直接后继结点的语句序列是(11)(4)(14)。删除P结点的语句序列是(10)(12)(7)(4)(14)。(1)P=P-next;(2)P-next=P;(3)P-next=P-next-next(4)P-next=P-next-next;(5)while(P!=NULL)P=P-next;(6)while(Q-next!=NULL){P=Q;Q=Q-next;}(7)while(P-next!=Q)P=P-next;(8)while(P-next-next!=Q)P=P-next;(9)while(P-next-next!=NULL)P=P-next;(10)Q=P;(11)Q=P-next;(12)P=L;(13)L=L-next;(14)free(Q);3.栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。4.用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为SXSSXSXX。5．数据的逻辑结构可以分为线性和非线性两大类。6．数据的运算用算法表示。7．逻辑上相邻的结点在存储器中也相邻，这是顺序存储结构的特点。8．在长度为n的顺序表上实现定位操作，其算法的时间复杂度为O(n)。9．为了实现随机访问，线性结构应该采用顺序存储。10．在长度为n的顺序表中插入一个元素，最多要移动n个元素。11．栈的存储结构主要有顺序和链式两种。12．在编写程序的时候，如果栈的最大长度难以预先估计，则最好使用链式栈。13．在树形结构中，如果某结点没有前驱（双亲），则称该结点为根结点；如果某结点没有后继（孩子），则称该结点为叶子。14．在树形结构中，每个结点最多只有一个前驱（双亲）。15．由3个结点所构成的二叉树有5种形态。16．二叉树的前序遍历按如下三个步骤进行：①访问根结点；②前序遍历左子树；③前序遍历右子树。【注意：②③中一定要加“前序”两字！】17．二叉树的中序遍历按如下三个步骤进行：①中序遍历左子树；②访问根结点；③中序遍历左子树。ACEBFGDH5【注意：①③中一定要加“中序”两字！】18．在n个顶点的无向图中，至少有0条边，至多有n(n-1)/2条边。19．在n个顶点的有向图中，至少有0条边，至多有n(n-1)条边。20．如果排序不改变关键字相同的记录之间的相对次序，则称该排序方法是稳定的。21．如果排序改变了关键字相同的记录之间的相对次序，则称该排序方法是不稳定的。22．在一个图中，所有顶点的度数之和是所有边数的2倍。23．无向图中边的数目等于邻接矩阵中非零元素个数的0.5倍。24．在有序表（2，4，6，8，10，12，14，16，18）上用折半查找法查找元素9，其中第二次被比较的元素是4。25．在有序表（2，4，6，8，10，12，14，16，18）上用折半查找法查找元素9，其中第三次被比较的元素是6。三、简答题1.写出下列程序段的输出结果（队列中的元素类型QElemType为char）。voidmain(){QueueQ;InitQueue(Q);Charx=’e’;y=’c’;EnQueue(Q,’h’);EnQueue(Q,’r’);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,’a’);while(!QueueEmpty(Q))