数据结构期末复习题一、单选题1．设有两个串T和P，求P在T中首次出现的位置的串运算称作( )。
A.联接B.求子串C.字符定位D.子串定位2．8×8的整型数组A，其每个数组元素占2个字节，已知A[0][0]在内存中的地址是100，按列主序，A[5][6]的地址是( ) 。
A.192B.206C.92D.1063．一个具有767个结点的完全二叉树，其叶子结点个数为（）。
A.383B.384C.385D.3864．具有65个结点的完全二叉树的高度为（）。
（根的层次号为0）A.8B.7C.6D.55．一个数组元素a[i]与（）的表示等价。
A.*(a+i)B.a+iC.*a+iD.&a+i6．在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于( )。
A.2^(h-1)B.2^(h+1)C.2^(h-1)D.2^h7. 已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS种元素e的运算是（）A. head(tail(LS))B. tail(head(LS))C. head(tail(head(tail(LS))))D. head(tail(tail(head(LS))))8．串S=’software’,其子串的数目是（）。
A. 8B. 37C. 36D. 99.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。
A. n-2B. n-1C. nD. n+110. 设有一个n*n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（）处。
A.(i+3)*i/2B.(i+1)*i/2C.(2n-i+1)*i/2D.(2n-i-1)*i/211．在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是( ) 。
A.p=p->next;B.p->next=p->next->next;C.p->next=p;D.p=p->next->next;12．下列算法的时间复杂度为（）。
for ( i =1；i<m ；i++ )for ( j = i + 1；j < n；j++ )a[i][j]=i*j;A.O(m*n)B.O( n2 )C.O(m2 )D.O(m+n)13．研究数据结构就是研究（）。
A.数据的逻辑结构B.数据的存储结构C.数据的逻辑结构和数据的存储结构D.数据的逻辑结构、存储结构及其数据的抽象运算。
14. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着( )。
A.数据元素具有同一特点B.不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致。
C.每个数据元素都一样。
D.数据元素所包含的数据项的个数要相等。
15．假定一个顺序循环队列的队首和队尾指针分别用front和rear表示，则判队空的条件是（）。
A. front+1==rearB.front==rear+1C.front==0D.front==rear16. 假定一个顺序循环队列存储于数组A[n]中，队首和队尾指针分别用front和rear表示，则判断队满的条件是( )。
A.（rear-1）%n==frontB.（rear+1）%n==frontC. rear==（front-1）%nD. rear==（front+1）%n17．若采用邻接矩阵法存储一个N个顶点的无向图，则该邻接矩阵是一个（）。
A．上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵18. 如果待排序序列中两个数据元素具有相同的值，在排序后它们的位置发生颠倒，则称该排序是不稳定的。
（）就是不稳定的排序方法。
A．起泡排序 B．归并排序 C．直接插入法排序 D．简单选择排序19．在一棵具有5层的满二叉树中结点数为（）。
A．31 B. 32 C. 33 D. 1620. 5阶B树中，每个结点最多有（）个关键码。
A．2 B．3 C．4 D．521、在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（）A．O (n) B．O (1) C．O (n2 ) D．O (log2 n)22、设单链表中结点的结构为（data , link）。
已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作？（）A．s->link= p->link; p->link=s；B．q->link=s; s->link=p；C．p->link=s->link; s->link=p；D．p->link=s; s->link=q；23、若让元素1，2，3依次进栈，则出栈次序不可能出现（）种情况。
A．3，2，1 B．2，1，3 C．3，1，2 D．1，3，224、一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（）A．较快 B．较慢 C．相同25、树中所有结点的度等于所有结点数加（）A．0 B．1 C．-1 D．226、在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）A．n B．n-1 C．n+1 D．2*n27、对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为（）A．n/2 B．(n+1)/2 C．(n –1)/2 D．n/428、在无向图中定义顶点V i与V j之间的路径为从V i到达V j的一个（）A．顶点序列 B．边序列 C．权值总和 D．边的条数29、如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（）方法最快。
A．起泡排序 B．快速排序 C．堆排序 D．直接选择排序30、设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列表项应能够至少容纳（）个表项。
（设搜索成功的平均搜索长度为S nl={1+1/(1-α)}/2其中α为装填因子）A．400 B．526 C．624 D．676二、填空题1．在程序运行过程中不能扩充的数组是分配的数组。
这种数组在声明它时必须指定它的大小。
2．将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中。
对于任意给定数组元素A[ I ][ J ]，如果它能够在数组B中找到，则它应在位置。
3．链表适用于查找。
4．队列的插入操作在进行，删除操作在进行。
5．设有一个顺序栈S，元素S1，S2，S3，S4，S5，S6依次进栈，如果6个元素的出栈顺序为S2，S3，S4，S6，S5，S1，则顺序栈的容量至少应为。
6．通常程序在调用另一个程序时，都需要使用一个来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。
7．广义表A（（a，b，c），（d，e，f））的表尾为。
8．在一棵树中，结点没有前驱结点。
9．一棵树的广义表表示为a（b（c，d（e，f），g（h）），i（j，k（x，y））），结点k的所有祖先的结点数为个。
10．根据一组记录（56，42，50，64，48）依次插入结点生成一棵AVL树（高度平衡的二叉搜索树）时，当插入到值为的结点时需要进行旋转调整。
11.快速排序算法的最坏情况的时间复杂度是。
12.文件可以有多种不同的组织方式：顺序文件、散列文件、和倒排文件。
13.B－树的一个变体用于文件的动态索引结构，被称为。
14.冒泡排序算法的最坏情况的时间复杂度是。
15.一棵树中结点的后根序列与对应二叉树中结点的__ _序列相同。
16．在具有n 个结点的中根线索二叉树中，非空指针的个数是。
17.给出所有不同形态的二叉树，它们的先根序列和后根序列完全相同： _____ _。
18.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为__________ __。
19.对于一个具有N个结点和E条边的无向图，若采用邻接表表示，则顶点表的大小为N，所有边链表中边结点的总数为。
20．判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用。
21.一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点f的层数为________。
假定树根结点的层数为0。
22.一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有________子女。
23.含有n个结点的树有多少条边_______ _ 。
24.一个连通图的生成树是该图的连通子图。
若这个连通图有N个顶点, 则它的生成树有条边。
25.能够成功完全拓扑排序的图一定是一个____________。
26.数组是一种态的数据结构，其上未定义运算。
7.一棵树中结点的后根序列与对应二叉树中结点的___ __序列相同。
27．在具有n 个结点的中根线索二叉树中，非空指针的个数是。
三、判断题（）1.连通分量是无向图中的极小连通子图；（）2.强连通分量是有向图中的极大强连通子图；（）3.霍夫曼树一定是完全二叉树。
（）4.有n个结点的不同的二叉树有n！棵。
（）5.折半搜索只适用于有序表，包括有序的顺序表和有序的链表。
（）6. 二维数组可以视为数组元素为一维数组的一维数组。
（）7. 链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，通常存储器中还有空闲存储空间，就不会产生存储溢出的问题。
（）8．在用单链表表示的链式队列中，队头在链表的链尾位置。
（）9．凡是递归定义的数据结构都可以用递归算法来实现它的操作。
（）10．当向一个小根堆（最小堆）中插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。
（）11．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（n）。
（）12．进行折半搜索的表必须是顺序存储的有序表。
（）13．一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。
（）14．在散列法中采取开散列（链地址）法来解决冲突时，其装载因子的取值一定在（0，1）之间。
（）15．一棵3阶B树是平衡的3路搜索树，反之，一棵平衡的3路搜索树是3阶B 树。
（）16.若让元素1，2，3依次进栈，则出栈次序不可能出现2，1，3的情况。
（）17.假定一个链式队列的对头和对尾指针分别为front和rear，则判断对空的条件为front==rear（）18.在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置。
（）19.对于AOE网络，加速任一关键活动都能使整个工程提前完成。
（）20.由树转化成二叉树，其根的右子女指针总是空的。