数据结构期末总复习题

《数据结构期末总复习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、19套题1一、选择题（每题2分，共15题，总计30分）1以下叙述中正确的是_____。A数组是数据的最小单位B数据对象就是一组数据元素的集合C顺序存储方式只能用于存储线形结构D树对应到的二叉树其根结点的右子树总是空的2一个数组的第一个元素的存储地址是100，每个元素长度为2，则第5个元素的存储地址是_____。A110B108C100D1203一个栈的入栈顺序是a,b,c,d,e，则其出栈顺序不可能是_____。Aa,b,c,d,eBe,d,c,b,aCd,c,e,a,bDd,e,c,b,a4栈的特点是_____。A先进先出B先进后出C随即存取D链式实现5一个队列的入队

2、顺序是1，2，3，4，5，那么出队顺序是_____。A5，4，3，2，1B1，2，3，5，4C1，2，3，4，5D1，3，2，4，56向一个长度为10的数组的第5个元素之前插入一个元素时，需向后移动_____个元素。A3B5C6D77若一棵二叉树有101个结点，且无度为1的结点，则叶结点的个数为_____。A48　　B49　　　C50　　D518高度为6的完全二叉树中第4层结点的个数为_____。A2　　B4　　　C8　　D169具有n个顶点的无向完全图，其边数为_____。An　　Bn(n-1)　　　Cn(n-1)/2　　Dn210具有n个顶点的有向完全图，其边数为_

3、____。An　　Bn(n-1)　　　Cn(n-1)/2　　Dn211在有7个顶点的无向图中至少有_____条边才能确保该图连通。A1　　B6　　　C7　　D2112对于一个有n个顶点的无向图，若采用邻接矩阵表示法，则该矩阵的大小是_____。An-1　　Bn　　　C(n-1)2　　Dn213在序列1，10，12，15，23，40，66，77，85中利用直接查找，查找15所需的比较次数为_____。A2B3C4D614采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为_____。AO(n)　　BO(nlogn)　　CO(n2)　　DO(logn)15在待排

4、序元素基本有序的前提下，效率最高的排序方法是_____。A插入排序B选择排序C快速排序D归并排序二、填空题（每空2分，共20空，总计40分）1判定下列程序段的时间复杂度为_________________，其中语句A[i][j]频度为___________________for(i=0;i

5、________，对于一个不带头指针的单链表，判定该链表为空的条件是__________________。4在循环单链表中，头指针用head表示，队尾结点用p指向，那么p→next等于__________________。5在选择数据结构的存储结构时，为了方便地定位和读取某特定元素，数据结构宜采用__________形式，为了方便地进行数据元素的插入删除操作，数据结构宜采用__________形式。6深度为5的二叉树，最多有___________个结点，最少有___________个结点。7若深度为5的二叉树中仅有度为0的结点和度为2的结点，那么这棵二叉树最多有____

6、_______个结点，最少有___________个结点。8在线索二叉树中，若以ltag表示某结点的左标志域，以lch表示某结点的左孩子域，则结点t没有左子树的条件是。9在含有个8结点的二叉链表中有_______个空链域。10有_______个结点的二叉树将会呈现5种不同的表现形式。11在无向图的邻接矩阵中，若A[i][j]=1,A[j][i]=_______________。12如下图所示的有向图，顶点D的入度为，出度为，顶点D的度为。ABCDEF三、操作题（共4题，总计20分）1已知一棵二叉树如下图所示：①写出该二叉树的先根遍历序列(2分)②写出该二叉树的中根遍历序

7、列(2分)③判断正误：这棵二叉树的先根、中根、后根遍历序列中，叶子结点的相对次序保持不变，其实，任意一棵二叉树，其叶子结点在先根、中根、后根遍历序列中的相对次序都保持不变。（2分）p2下面的程序段是一个在单链表表示的有序序列a,b,d,e中插入新值c并保持有序的算法，已知插入位置的前驱用p指向，请将程序段补充完整。(6分)19abde∧headStatusListInsert_L(LinkList&L,charc){s=(LinkList)malloc(sizeof(LNode));;s→next=;p→next=;returnOK;}/