数据结构复习题（课程代码 252259）一、填空题（本大题共40小题）1.队列中是按照______先进先出______的原则进行数据元素的增删。

2.___栈__又称为LIFO表。

3.在顺序存储的完全二叉树中，若编号为i的结点有左孩子结点，则其右孩子结点的编号为___2i+1___。

4.存储地址与关键字之间存在某种映射关系的存储结构为_______散列存储结构_______。

5.在串S=“structure”中，以r为首字符的子串有_9_个。

6.设有整型二维数组M[4][3]，每个元素（整数）占2个存储单元，元素按行的顺序存储，数组的起始地址为200，元素M[1][1]的地址是___208____。

7.在一个具有n个顶点的无向完全图中，包含有___ n(n-1)/2_____条边，在一个具有n个顶点的有向完全图中，包含有__ n(n-1)______条边。

8.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为_____（12，40）（）（74）（23,55，63）____。

9.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度____增加1______。

10.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为__ O(log2n)______，整个堆排序过程的时间复杂度为__ O(nlog2n)______。

11.在快速排序、堆排序、归并排序中，____归并_____排序是稳定的。

12.一棵深度为5的满二叉树中的结点数为_______31_______个。

13.在含n个顶点和e条边的无向图的邻接矩阵中,非零元素的个数为__2e __。

14.从一棵二叉排序树中查找一个元素时，若元素的值大于根结点的值，则继续向____右子树____查找。

15._____拓朴排序______可以判断出一个有向图中是否有环。

16.栈又称为______后进先出__________的线性表。

17.数据结构在计算机中的表示称为数据的__物理结构____。

18.有4个结点的不同的二叉树有__9___棵。

19.含有60个结点的树有____59____条分支。

20.在图结构中，前驱元素和后继元素之间存在着_____多对多____的联系。

21.____哈夫曼树____又称最优二叉树。

22.一棵二叉树有67个结点，这些结点的度要么是0，要么是2。

这棵二叉树中度为2的结点有___33___个。

23.在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=______ p－＞next－＞next ____。

24.栈顶的位置是随着_____进栈和出栈______操作而变化的。

25.设一个散列表的容量为M，用线性探测法解决冲突.。

若要查找一个键值，至少要进行1次比较，至多要进行_____M_____次比较。

26.在n个结点的线索二叉链表中，有____ n-1___个线索指针。

27.具有180个结点的二叉树，其深度至少为___8______。

28.序列中有1000个元素基本按键值递增顺序排列，就算法的比较次数而言，应选择___________直接插入_____排序算法。

29.若堆栈的入栈序列为1,2,3,…,n-1,n，输出元素i需要进行____ n-i+1______次出栈操作。

30.对于队，只能在队尾插入元素，只能在队头删除元素。

31.抽象数据类型ADT可以用三元组（D，S，P）表示，它们分别表示：数据对象、数据关系和基本操作。

32.栈是一种受限制的线性表，也叫LIFO结构，LIFO的含义是后进先出33.在单链表中，若要在指针p所指结点后插入指针s所指结点，则需要执行下列两条语句：s->next=p->next；p->next=s34.通常从四个方面评价算法的质量：___正确性易读性强壮性高效率_____。

35.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为___ O(n)_____。

36.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为___9_______个，树的深度为_____3______，树的度为___3______。

37.后缀算式9 2 3 +- 10 2 / -的值为____－1______。

中缀算式（3+4X）-2Y/3对应的后缀算式为_______3 4 X * + 2 Y * 3 / -________________________。

38.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。

在这种存储结构中，n个结点的二叉树共有___2n_____个指针域，其中有__n-1______个指针域是存放了地址，有_______n+1_________个指针是空指针。

39.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_____e__个和____2e____个。

40.AOV网是一种________有向无回路___________的图。

二、单项选择题（本大题共50小题）1．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（D ）A）O（1）B）O（n）C）O（m）D）O（m+n）2．如下所示的图的拓扑序列为（D）A） C1，C2，C3，C4，C5，C6B)C1，C2，C5，C3，C4，C5，C7C)C1，C4，C2，C3，C5，C6D)C1，C2，C5，C4，C3，C63．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( D ) A）e B）2e C）n2－e D）n2－2e4．设有6个结点的无向图，该图至少应该有(A)条边才能确保是一个连通图A．5 B．6 C．7 D．85．有N个结点的图的邻接矩阵存储法中，链表的表头结点有（A ）个。

A、NB、2NC、N/2D、N*NE、N-26．具有4个顶点的无向完全图有（A ）条边。

A、6B、12C、16D、207．邻接矩阵是对称矩阵的图为(D ）。

A、有向图B、带权有向图C、带权连通图D、无向图8．在长度为n的线性表中查找值为x的数据元素的时间复杂度为（ C ）。

A）O(0) B）O(1) C）O(n) D）O(n2)9．若一个栈的输入序列是1，2，3，……，n，输出序列的第一个元素是n，则第i个输出元素是（ D ）。

A）不确定 B）n-i C、n-i-1 D、n-i+110．设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2,e4,e3,e6,e5,e1，则栈的容量至少应该是（ C ）。

A、6B、4C、3D、211．一个栈的入栈序列是1，2，3，4，5，则栈的不可能的出栈序列是（ C ）。

A、5，4，3，2，1B、4，5，3，2，1C、4，3，5，1，2D、1，2，3，4，512．设计一个判别表达式中左右括号是否匹配的算法，采用（ B ）数据结构最佳。

A、顺序表B、栈C、队列D、链表13．在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印缓冲区，该缓冲区应该是一个（ B ）结构。

A、栈B、队列C、数组D、线性表14．线性表若采用链表存储结构，要求内存中可用存储单元地址( D )A．必须连续B．部分地址必须连续C．一定不连续D．连续不连续均可15．依次在初始为空的队列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是（ C ）A）X B）Y C）Z D）W16．已知一个有向图如下图所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS 序列为（ A ）。

A) a d b e f cB) a d c e f bC) a d c b f eD) a d e f c b17．若连通无向图G有n个顶点，则图G的生成树有（B ）条边A）n B）n-1 C）n(n-1)/2 D）n/218．设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（D ）A）front=front+1 B）front=(front+1)%(m-1)C）front=(front-1)%m D）front=(front+1)%m19．设某算法的问题规模函数f(n)=25n3+5000n2，则它的渐进时间复杂度为（ A ）。

A）O(n3) B）O(n2) C）O(n) D）O(1)20．假定一个顺序队列的队首和队尾指针分别为f和r，则判断队空的条件为( D )。

A）f+1==r B）r+1==f C）f==0 D）f==r21．线性表采用链式存储时，结点的存储地址（B ）A）必须是不连续的B）连续与否均可C）必须是连续的D）和头结点的存储地址相连续22．设计递归问题的非递归算法一般需要用到（ D ）。

A）链表B）队列C）树D）堆栈23．对下面二叉树，按中序遍历所得到的结点序列为（ A ）。

A）DBEAFCB）DEBFCAC）BDEACFD）ABCDEF24．对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组的大小为（A ）。

A）n B）n+1 C）n-1 D）n+边数25．设有一个含有n 个(n>2)关键字的有序表，设s和h分别是用顺序查找法和二分查找法进行查找时的等概率情况下查找成功的平均查找次数，则s和h的关系是（ B ）。

A）s = h B）s > h C）s < h D）不能确定26．一棵深度为7的满二叉树有（ D ）叶子结点。

A）7 B）14 C）32 D）6427．设二叉树根结点的层次为1，含有15个结点的二叉树中的最小高度是（ 4 ）A）6 B）5 C）4 D）328．在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数为（ B ）。

A）i-1 B）n-i+1 C）i D）n-i29．一棵深度为8的满二叉树有（ C ）叶子结点。

A）256 B）255 C）128 D）12730．在一非空二叉树的中序遍历序列中，根结点的右边(A )A．只有右子树上的所有结点B．只有右子树上的部分结点C．只有左子树上的所有结点D．只有左子树上的部分结点31．以下关于数据结构的叙述，正确的是( C)A．线性表的线性存储结构优于链式结构B．二叉树的第I层上有2的（I-1）次幂个结点，深度为K的二叉树上有2的（k-1）次幂个结点C．二维数组是其数据元素为线性表的线性表D．栈的操作方式是先进先出32．在单链表中，增加头结点的目的是为了（C ）。