《数据结构》复习资料⼀、单项选择题
1. 若需要利⽤形参直接访问实参，则应把形参变量说明为( B )参数。A. 指针B. 引⽤C. 传值D. 常值
2. 以下说法错误的是（C ）。A. 抽象数据类型具有封装性。B. 抽象数据类型具有信息隐蔽性。
C. 使⽤抽象数据类型的⽤户可以⾃⼰定义对抽象数据类型中数据的各种操作。D. 抽象数据类型的⼀个特点是使⽤与实现分离。
3. 设有⼀个n n的对称矩阵A，将其上三⾓部分按⾏存放在⼀个⼀维数组B中，A[0][0]存放于B[0]中，那么第i⾏的对⾓元素A[i][i]存放于B中（C）处。A. (i+3)*i/2B. (i+1)*i/2C. (2n-i+1)*i/2D. (2n-i-1)*i/2
4. 已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（ C ）。A. O(1)B. O(m)C. O(n)D. O(m+n)
5. 假定⼀个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( D)。A. front == rearB. front != NULLC. rear != NULLD. front == NULL6. 设有⼀个递归算法如下int fact(int n) { //n⼤于等于0if(n<=0) return 1;else return n*fact(n-1);}
则计算fact(n)需要调⽤该函数的次数为（ B ）次。
A．n B．n+1 C．n+2 D．n-1
7. 在⼀棵⾼度为h(假定树根结点的层号为0)的完全⼆叉树中，所含结点个数不⼩于( D )。A. 2h-1B. 2h+1C. 2h-1D. 2h
8. ⼀棵树的⼴义表表⽰为a(b,c(e,f(g)),d)，当⽤左⼦⼥-右兄弟链表表⽰时，右指针域⾮空的结点个数为( C )。A 1B 2C 3D 4
9. 向具有n个结点的、结构均衡的⼆叉搜索树中插⼊⼀个元素的时间复杂度⼤致为( B)。A. O(1)B. O(log2n )C. O(n)D. O(nlog2n)
10. 具有n个顶点的有向⽆环图最多可包含( C)条有向边。A．n-1 B．n C．n(n-1)/2 D．n(n-1)
11. 图的⼴度优先搜索类似于树的（ D）次序遍历。A. 先根B. 中根C. 后根D. 层次
12. 如果将所有中国⼈按照⽣⽇（不考虑年份，只考虑⽉、⽇）来排序，那么使⽤下列排序算法中( D)算法最快。A. 归并排序B. 希尔排序C. 快速排序D. 基数排序
13．算法指的是（D）
A．计算机程序 B．解决问题的计算⽅法C．排序算法 D．解决问题的有限运算序列
14．线性表采⽤链式存储时，结点的存储地址（B）A．必须是不连续的B．连续与否均可C．必须是连续的
D．和头结点的存储地址相连续
15．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（C）A．O（1） B．O（n） C．O（m） D．O（m+n）16．由两个栈共享⼀个向量空间的好处是：（B）A．减少存取时间，降低下溢发⽣的机率B．节省存储空间，降低上溢发⽣的机率C．减少存取时间，降低上溢发⽣的机率D．节省存储空间，降低下溢发⽣的机率
17．设数组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)%m
18．在⼀棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( C)
A．4 B．5 C．6 D．7
19．在含n个顶点和e条边的⽆向图的邻接矩阵中,零元素的个数为(D)A．e B．2e C．n2－e D．n2－2e
20．⽤某种排序⽅法对关键字序列（25，84，21，47，15，27，68，35，20）进⾏排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采⽤的排序⽅法是（D ）
A．选择排序 B．希尔排序 C．归并排序 D．快速排序21．适于对动态查找表进⾏⾼效率查找的组织结构是（C ）A．有序表 B．分块有序表 C．⼆叉排序树 D．线性链表22. 设有⼀个递归算法如下int fact(int n) { //n⼤于等于0if(n<=0) return 1;else return n*fact(n-1);}
则计算fact(n)需要调⽤该函数的次数为（ B ）次。A．n B．n+1 C．n+2 D．n-1
23. 在⼀棵⾼度为h(假定树根结点的层号为0)的完全⼆叉树中，所含结点个数不⼩于( D)。A. 2h-1B. 2h+1C. 2h-1
D. 2h
24. 图的⼴度优先搜索类似于树的（ D）次序遍历。A. 先根B. 中根C. 后根D. 层次
25. 在⼀个长度为n的顺序表的任⼀位置插⼊⼀个新元素的渐进时间复杂度为（A ）。A. O(n)B. O(n/2)C. O(1)D. O(n2)
26. 当利⽤⼤⼩为n的数组顺序存储⼀个队列时，该队列的最⼤长度为（B ）。A. n-2B. n-1C. nD. n+1
27. 在⼀棵⼆叉树的⼆叉链表中，空指针域数等于⾮空指针域数加（ A ）。A. 2B. 1C. 0D. –1
28. 在有向图中每个顶点的度等于该顶点的（ C）。A. ⼊度B. 出度
C. ⼊度与出度之和D. ⼊度与出度之差
29. 设单链表中结点的结构为（data , link）。已知指针q所指结点是指针p所指结事业的直接前驱，若在*q与*p之间插⼊结点*s，则应执⾏下列哪⼀个操作？（B）A．s ->link= p->link ; p->link=s B．q->link=s ;s->link=pC．p->link=s->link ;s->link=p D．p->link=s ;s->link=q
30. 若让元素1，2，3依次进栈，则出栈次序不可能出现（C）种情况。A．3，2，1 B．2，1，3 C．3，1，2 D．1，3，2
31. ⼀个递归的定义可以⽤递归过程求解，也可以⽤⾮递归过程求解，但单从运⾏时间来看，通常递归过程⽐⾮递归过程（B）
A．较快 B．较慢 C．相同
32. 树中所有结点的度等于所有结点数加（ C ）A．0 B．1 C．-1 D．2
⼆、填空题
1．数据的逻辑结构是从逻辑关系上描述数据，它与数据的_存储_⽆关，是独⽴于计算机的。2．在⼀个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head 可⽤p表⽰为head= p－>next－>next _____。3．栈顶的位置是随着进栈和退栈操作⽽变化的。
4．在串S=“structure”中，以t为⾸字符的⼦串有_12____个。
5．假设⼀个9阶的上三⾓矩阵A按列优先顺序压缩存储在⼀维数组B中，其中B存储矩阵中第1个元素a1,1,则B中存放的元素是a4,8_。
6．已知⼀颗完全⼆叉树中共有768结点，则该树中共有_384__个叶⼦结点。
7．已知⼀个图的⼴度优先⽣成树如右图所⽰，则与此相应的⼴度优先遍历序列为_abefcdg 。8．在单链表上难以实现的排序⽅法有快速排序、堆排序、希尔排序。
9．在有序表（12，24，36，48，60，72，84）中⼆分查找关键字72时所需进⾏的关键字⽐较次数为_2____。10．多重表⽂件和倒排⽂件都归属于多关键字⽂件。
11. 数据结构的存储结构包括顺序、_链式__、索引和散列等四种。
12. 在程序运⾏过程中可以扩充的数组是动态_分配的数组，这种数组在声明它时需要使⽤数组指针；在程序运⾏过程中不能扩充的数组是_静态分配的数组，这种数组在声明它时必须指定它的⼤⼩。
13. 在链表中进⾏插⼊和删除操作的效率⽐在顺序存储结构中进⾏相同操作的效率⾼。14. 栈是⼀种限定在表的⼀端进⾏插⼊和删除的线性表，⼜被称为后进先出_表。
15. 如果⼀个对象部分地包含⾃⼰，或⾃⼰定义⾃⼰，则称这个对象是递归的对象。16．栈顶的位置是随着_进栈与出栈操作⽽变化的。
17．已知⼀颗完全⼆叉树中共有768结点，则该树中共有_384_个叶⼦结点。18.链表适⽤于顺序查找。
19.队列的插⼊操作在_队尾_ 进⾏，删除操作在_队头_进⾏。
20.设有⼀个顺序栈S，元素S1，S2，S3，S4，S5，S6依次进栈，如果6个元素的出栈顺序为S2，S3，S4，S6，S5，S1，则顺序栈的容量⾄少应为_3_。
21．在⼀棵树中，_根_结点没有前驱结点。
22．通常程序在调⽤另⼀个程序时，都需要使⽤⼀个栈来保存被调⽤程序内分配的局部变量、形式参数的存储空间以及返回地址。
23.链表对于数据元素的插⼊和删除不需移动结点，只需改变相关结点的指针域的值。三、判断题
1、⼆维数组可以视为数组元素为⼀维数组的⼀维数组。（√）
2、链接存储表⽰的存储空间⼀般在程序的运⾏过程中动态分配和释放，通常存储器中还有空闲存储空间，就不会产⽣存储溢出的问题。（√）
3、在⽤单链表表⽰的链式队列中，队头在链表的链尾位置。（×）4、凡是递归定义的数据结构都可以⽤递归算法来实现它的操作。（√）
5、当向⼀个⼩根堆（最⼩堆）中插⼊⼀个具有最⼩值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为⽌。（√）
6、对于⼀棵具有n个结点，其⾼度为h的⼆叉树，进⾏任⼀种次序遍历的时间复杂度为O（n）。（√）。
7、进⾏折半搜索的表必须是顺序存储的有序表。（√）
8、数组是⼀种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。（√）
9、链式存储在插⼊和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。（×）10、通常递归的算法简单、易懂、容易编写，⽽且执⾏的效率也⾼。（×）四、运算题
1、已知⼀棵⼆叉树的中序和前序序列如下，求该⼆叉树的后序序列。中序序列：c，b，d，e，a，g，I，h，j，f前序序列：a，b，c，d，e，f，g，h，I，j后序序列：c，e，d，b，i，j，h，g，f，a2、已知⼀个带权图的顶点集V和边集G分别为：V={0,1,2,3,4,5,6};
E={(0,1)16,(0,2)10,(0,3)14,(1,2)6,(1,5)5,(2,3)26,(2,4)15,(3,4)18,(4,5)6,(4,6)6,(5,6)12};
试根据迪克斯特拉(Dijkstra)算法求出从顶点0到其余各顶点的最短路径，在下⾯填写对应的路径长度。顶点： 1 2 3 4 5 6
路径长度五、算法分析题
1. 指出下⾯算法的功能并求出其时间复杂度。void matrimult(int a[M][N], int b[N][L], int c[M][L]){ //M、N、L均为全局整型量int i, j, k;for(i=0; ifor(j=0; jfor(i=0; ifor(j=0; jfor(k=0; k
c[i][j]+=a[i][k]*b[k][j];}
功能为：矩阵相乘，即a[M][N] ×b[N][L]= c[M][L]时间复杂度为：O(M×N×L)六、算法设计题
1. 试编写⼀个函数，在⼀个顺序表A中查找出具有最⼤值和最⼩值的整数。
函数的原型如下所⽰，原型的参数表中给出顺序表对象为A，通过算法执⾏，从参数表中的引⽤参数Max中得到表中的最⼤整数，Min中得到表中的最⼩整数。
注意，函数中可使⽤顺序表的如下两个公有函数：
int Length( ); 求表的长度；
int getData(int k); 提取第k个元素的值。#include “SeqList.h”template
void FindMaxMin(SeqList& A, int& Max, int& Min){
Max=Min=A.getData(0);for(int i=1; i
if(A.getData(i)>Max) Max=A.getData(i);else if(A.getData(i)}}
2. 已知⼆叉树中的结点类型BinTreeNode定义为:
struct BinTreeNode {char data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右⼦⼥结点的指针域，根据下⾯函数声明编写出判断两棵⼆叉树是否相等的算法，若相等则返回1否则返回0。算法中参数T1和T2为分别指向这两棵⼆叉树根结点的指针。当两棵树的结构完全相同并且对应结点的值也相同时才被认为相等。
int BTreeEqual(BinTreeNode* T1,BinTreeNode* T2){
//若两棵树均为空则返回1表⽰相等
if(T1==NULL && T2==NULL) return 1;//若⼀棵为空⼀棵不为空则返回0表⽰不等 else if(T1==NULL || T2==NULL) return 0; //若根结点值相等并且左、右⼦树对应相等则两棵树相等
else if(T1->data==T2->data && BTreeEqual(T1->left, T2->left) && BTreeEqual(T1->right, T2->right) )return 1; //若根结点值不等或左、右⼦树对应不等则两棵树不等elsereturn 0;}
因篇幅问题不能全部显示，请点此查看更多更全内容