数据结构期末总复习题（参考）.docx

套题1一、选择题（每题2 分，共15题，总计30 分）1 以下叙述中正确的是_____。A 数组是数据的最小单位B 数据对象就是一组数据元素的集合C 顺序存储方式只能用于存储线形结构D 树对应到的二叉树其根结点的右子树总是空的2 一个数组的第一个元素的存储地址是100，每个元素长度为2，则第5个元素的存储地址是_____。A 110 B 108 C 100 D 1203 一个栈的入栈顺序是a,b,c,d,e，则其出栈顺序不可能是_____。A a,b,c,d,e B e,d,c,b,aC d,c,e,a,b D d,e,c,b,a4栈的特点是_____。A 先进先出 B 先进后出 C 随即存取 D 链式实现5 一个队列的入队顺序是1，2，3，4，5，那么出队顺序是_____。A 5，4，3，2，1 B 1，2，3，5，4C 1，2，3，4，5 D 1，3，2，4，56 向一个长度为10的数组的第5个元素之前插入一个元素时，需向后移动_____个元素。A 3B 5C 6 D77若一棵二叉树有101个结点，且无度为1的结点，则叶结点的个数为_____。 A 48　 B 49　　 C 50　 D 518 高度为6的完全二叉树中第4层结点的个数为_____。A 2　 B 4　　 C 8　 D 169具有n个顶点的无向完全图，其边数为_____。A n　 B n(n-1)　 C n(n-1)/2　 D n210具有n个顶点的有向完全图，其边数为_____。A n　 B n(n-1)　 C n(n-1)/2　 D n211在有7个顶点的无向图中至少有_____条边才能确保该图连通。A 1　 B 6　　　 C 7　 D 2112对于一个有n个顶点的无向图，若采用邻接矩阵表示法，则该矩阵的大小是_____。A n-1　 B n　 C (n-1)2　 D n213在序列1，10，12，15，23，40，66，77，85中利用直接查找，查找15所需的比较次数为_____。A 2 B 3 C 4 D 614 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为_____。AO( n)　 B O(nlogn)　 C O(n2)　 D O(logn)15 在待排序元素基本有序的前提下，效率最高的排序方法是_____。A 插入排序 B 选择排序 C 快速排序 D 归并排序二、填空题（每空2 分，共20空，总计40 分）1 判定下列程序段的时间复杂度为_________________，其中语句A[i][j]频度为___________________for(i=0;in;i++) { for(j=0;j=n;j++) A[i][j]=0; B[j][i]=1;}2对线性表进行二分查找时，要求线性表必须_______________且______________。3 对于一个头指针为head的带头结点的单链表，判定该链表为空的条件是__________________，对于一个不带头指针的单链表，判定该链表为空的条件是__________________。4 在循环单链表中，头指针用head表示，队尾结点用p指向，那么p→next等于__________________。5 在选择数据结构的存储结构时，为了方便地定位和读取某特定元素，数据结构宜采用__________形式，为了方便地进行数据元素的插入删除操作，数据结构宜采用__________形式。6深度为5的二叉树，最多有___________个结点，最少有___________个结点。7若深度为5的二叉树中仅有度为0的结点和度为2的结点，那么这棵二叉树最多有___________个结点，最少有___________个结点。8 在线索二叉树中，若以ltag表示某结点的左标志域，以lch表示某结点的左孩子域，则结点t没有左子树的条件是。9在含有个8结点的二叉链表中有_______个空链域。10有_______个结点的二叉树将会呈现5种不同的表现形式。11在无向图的邻接矩阵中，若A[i][j]=1,A[j][i]= _______________。12如下图所示的有向图，顶点D的入度为，出度为，顶