数据结构填空练习题
一
1. 通常从四个方面评价算法的质量：_________、_________、_________和________。 2. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3. 假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为__________个，树的深度为___________，树的度为_________。
4. 后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。
5. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩
子的两个指针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。
6. 对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_______个和________个。
7. AOV网是一种___________________的图。
8. 在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。
9. 假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 10. 向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。
11. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。
12. 在快速排序、堆排序、归并排序中，_________排序是稳定的。 1.
正
确
性
易
读
性
强
壮
性
高
效
率 2. O(n) 3. 9 3 3
4. -1 3 4 X * + 2 Y * 3 / - 5. 2n n-1 n+1 6. e 2e
7. 有向无回路 8. n(n-1)/2 n(n-1)
. 学习.资料.
. . . .
9. （12，40） （ ） （74） （23,55，63） 10.增加1 11.O(log2n) O(nlog2n) 12.归并
二
1. 设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第
二个栈顶指针top2的初值为n，则判断共享栈满的条件是______________。 2. 在图的邻接表中用顺序存储结构存储表头结点的优点是________________。 3. 设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包
括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。
4. 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把
栈称为__________表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。 5. 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的
前序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。
6. 设一棵完全二叉树有128个结点，则该完全二叉树的深度为________，有 __________个叶子结点。
7. 设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素
个数之和等于顶点i的________，第i列中所有非零元素个数之和等于顶点i的__________。 8. 设一组初始记录关键字序列(k1，k2，„„，kn)是堆，则对i=1，2，„，n/2 而言满足的条件为_______________________________。
9. 下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。
10. 下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。
. 学习.资料.
. . . .
} 答案
1. top1+1=top2
2. 可以随机访问到任一个顶点的简单链表 3. i(i+1)/2+j-1 4. FILO，FIFO
5. ABDECF，DBEAFC，DEBFCA 6. 8，64
7. 出度，入度
8. ki<=k2i && ki<=k2i+1 9. n-i，r[j+1]=r[j]
10. mid=(low+high)/2，r[mid].key>k
三
1. 数据结构按逻辑结构可分为两大类，分别是______________和_________________。 2. 数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。
3. 线性结构反映结点间的逻辑关系是__________________的，非线性结构反映结点间的逻辑关系是__________________的。
4. 一个算法的效率可分为__________________效率和__________________效率。 5. 在树型结构中，树根结点没有__________________结点，其余每个结点的有且只有__________________个前趋驱结点；叶子结点没有__________________结点；其余每个结点的后续结点可以__________________。
6. 在图型结构中，每个结点的前趋结点数和后续结点数可以__________________。 7. 线性结构中元素之间存在__________________关系；树型结构中元素之间存在__________________关系；图型结构中元素之间存在__________________关系。
. 学习.资料.
. . . .
8. 下面程序段的时间复杂度是__________________。
第8题 9题 10题 11题
9. 下面程序段的时间复杂度是__________________。 10. 下面程序段的时间复杂度是__________________。 11. 下面程序段的时间复杂度是__________________。
12. 衡量算确性的标准通常是____________________________________。
13. 算法时间复杂度的分析通常有两种方法，即___________和___________的方法，通常我们对算法求时间复杂度时，采用后一种方法。 答案
1. 线性结构，非线性结构 2. 集合，线性，树，图 3. 一对一，一对多或多对多 4. 时间，空间 5. 前趋，一，后继，多 6. 有多个
7. 一对一，一对多，多对多
12. 程序对于精心设计的典型合法数据输入能得出符合要求的结果。 13. 事后统计，事前估计
四
1. 线性表是一种典型的_________结构。
2. 在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移____个元素。 3. 顺序表中逻辑上相邻的元素的物理位置________。
4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_______一个位置，移动过程是从_______向_______依次移动每一个元素。
5. 在线性表的顺序存储中，元素之间的逻辑关系是通过_______决定的；在线性表的存储中，元素之间的逻辑关系是通过_______决定的。
. 学习.资料.
. . . .
6. 在双向链表中，每个结点含有两个指针域，一个指向_______结点，另一个指向_______结点。
7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_______存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。 8. 顺序表中逻辑上相邻的元素，物理位置_______相邻，单链表中逻辑上相邻的元素，物理位置_______相邻。
9. 线性表、栈和队列都是_______结构，可以在线性表的______位置插入和删除元素；对于栈只能在_______位置插入和删除元素；对于队列只能在_______位置插入元素和在_______位置删除元素。
10. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_________和_______；而根据指针的联接方式，链表又可分为________和_________。 11. 在单链表中设置头结点的作用是________。
12. 对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为_______。
13. 对于一个栈作进栈运算时，应先判别栈是否为_______，作退栈运算时，应先判别栈是否为_______，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为_______。为了增加存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的存空间时，应将两栈的_______分别设在这片存空间的两端，这样只有当_______时才产生上溢。
14. 设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop, push, pop, push, push后，输出序列是_________。
15. 无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为__________。 答案
1．线性 2．n-i+1 3．相邻 4．前移，前，后 5．物理存储位置，链域的指针值 6．前趋，后继 7．顺序， 8．一定，不一定 9．线性，任何，栈顶，队尾，队头
10．单链表，双链表，非循环链表，循环链表
11．使空表和非空表统一；算法处理一致 12．O(1)，O(n)
. 学习.资料.
. . . .
13．栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇 14．2、3 15．O(1)
五
1. 计算机软件系统中，有两种处理字符串长度的方法：一种是___________，第二种是___________________。
2. 两个字符串相等的充要条件是_____________________和___________________。 3. 设字符串S1= “ABCDEF”，S2= “PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为___________________。 4. 串是指___________________。
5. 空串是指___________________，空格串是指___________________。 1. 固定长度，设置长度指针
2. 两个串的长度相等，对应位置的字符相等 3. “BCDEDE” 4. 含n个字符的有限序列 （n≥0）
5. 不含任何字符的串，仅含空格字符的字符串
六
1. 一维数组的逻辑结构是______________，存储结构是______________；对于二维或多维数组，分为______________和______________两种不同的存储方式。
2. 对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址为______________。
3. 一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度为_____，深度为_____。 4. 一个稀疏矩阵为 如右图，则对应的三元组线性表为_____________。
5. 一个n×n的对称矩阵，如果以行为主序或以列为主序存入存，则其容量为______________。
6. 已知广义表A=((a,b,c),(d,e,f))，则运算head(tail(tail(A)))=____________。
7. 设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a85的地址为______________。 8. 已知广义表Ls=(a,(b,c,d),e)，运用head和tail函数取出Ls中的原子b的运算是______________。
. 学习.资料.
. . . .
9. 三维数组R[c1„d1,c2„d2,c3„d3]共含有______________个元素。（其中：c1≤d1,c2≤d2,c3≤d3）
10. 数组A[1„10，-2„6，2„8]以行优先的顺序存储，设第一个元素的首地址是100，每个元素占3个存储长度的存储空间，则元素A[5，0，7]的存储地址为______________。
1. 线性结构，顺序结构，以行为主序，以列为主序
2. i×n+j个元素位置 3. 5，3 4.（（0，2，2），（1，0，3），（2，2，-1），（2，3，5）） 5. n×(n+1)/2
6. e
7. 41
8. head(head(tail(Ls)))
9.（d1-c1+1）×（d2-c2+1）×（d3-c3+1） 10. 913
七
1. 假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为_____，树的深度为_____，终端结点的个数为______，单分支结点的个数为______，双分支结点的个数为______，三分支结点的个数为_______，C结点的双亲结点为_______，其孩子结点为_______和_______结点。
2. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有_______个。
3. 对于一个有n个结点的二叉树，当它为一棵________二叉树时具有最小高度，即为_______，当它为一棵单支树具有_______高度，即为_______。
4. 由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为___。 5. 在一棵二叉排序树上按_______遍历得到的结点序列是一个有序序列。
6. 对于一棵具有n个结点的二叉树，当进行存储时，其二叉链表中的指针域的总数为_______个，其中_______个用于孩子结点，_______个空闲着。
7. 在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=______。 8. 一棵深度为k的满二叉树的结点总数为_______，一棵深度为k的完全二叉树的结点总数的最小值为_____，最大值为______。
9. 由三个结点构成的二叉树，共有____种不同的形态。
10. 设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。
. 学习.资料.
. . . .
11. 一棵含有n个结点的k叉树，______形态达到最大深度，____形态达到最小深度。 12. 对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为________，右孩子结点的编号为________，双亲结点的编号为________。 13. 对于一棵具有n个结点的二叉树，采用二叉链表存储时，链表中指针域的总数为_________个，其中___________个用于孩子结点，_____________个空闲着。 14. 哈夫曼树是指________________________________________________的二叉树。 15. 空树是指________________________，最小的树是指_______________________。 16. 二叉树的链式存储结构有______________和_______________两种。 17. 三叉链表比二叉链表多一个指向______________的指针域。 18. 线索是指___________________________________________。
19. 线索链表中的rtag域值为_____时，表示该结点无右孩子，此时______域为指向该结点后继线索的指针。
20. 本节中我们学习的树的存储结构有_____________、___________和___________。
1. 3，4，6，1，1，2，A，F，G 2. n+1
4. 55 5. 中序 6. 2n，n-1，n+1 7. n2+1 8. 2k-1，2k-1，2k-1 9. 5 10. 2h-1 11. 单支树，完全二叉树 12. 2i，2i+1，i/2（或
i/2
） 13. 2n，n-1，n+1
14. 带权路径长度最小 15. 结点数为0，只有一个根结点的树
16. 二叉链表，三叉链表 17. 双亲结点 18. 指向结点前驱和后继信息的指针 19. 1，RChild 20. 孩子表示法，双亲表示法，长子兄弟表示法
八
1. 在一个图中，所有顶点的度数之和等于所有边数的________倍。
2. 在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。
3. 假定一个有向图的顶点集为{a,b,c,d,e,f}，边集为{ 4. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要________条边。 5. 表示图的两种存储结构为__________和__________。 . 学习.资料. . . . . 6. 在一个连通图中存在着________个连通分量。 7. 图中的一条路径长度为k，该路径所含的顶点数为________。 8. 若一个图的顶点集为{a,b,c,d,e,f}，边集为{(a,b),(a,c),(b,c),(d,e)}，则该图含有________个连通分量。 9. 对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为________________。 10. 对于具有n个顶点和e条边的有向图和无向图，在它们对应的邻接表中，所含边结点的个数分别为________和________。 11. 在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别着该顶点的所有________和________结点。 12. 对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为________和________。 13. 假定一个图具有n个顶点和e条边，则采用邻接矩阵和邻接表表示时，其相应的空间复杂度分别为________和________。 14. 一个图的边集为{(a,c),(a,e),(b,e),(c,d),(d,e)}，从顶点a出发进行深度优先搜索遍历得到的顶点序列为____________，从顶点a出发进行广度优先搜索遍历得到的顶点序列为____________。 15. 一个图的边集为{ 16. 图的________优先搜索遍历算法是一种递归算法，图的________优先搜索遍历算法需要使用队列。 17. 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为________和________。 18. 若一个连通图中每个边上的权值均不同，则得到的最小生成树是________（唯一/不唯一）的。 19. 根据图的存储结构进行某种次序的遍历，得到的顶点序列是__（唯一/不唯一）的。 20. 假定一个有向图的边集为{ 1. 2 2. n(n-1)/2，n(n-1) 3. 2，4 4. n-1 . 学习.资料. . . . . 5. 邻接矩阵，邻接表 6. 1 7. k+1 8. 3 9. n，n 10. 2e，e 11. 出边，入边 12. O（n），O（e/n） 13.O（n2），O（n+e） 14. acdeb，acedb （答案不唯一） 15. acfebd，acefbd （答案不唯一） 16. 深度，广度 17. n，n-1 18. 唯一 19. 唯一 20. aebdcf（答案不唯一） 九 1. 以顺序查找方法从长度为n的顺序表或单链表中查找一个元素时，平均查找长度为________，时间复杂度为________。 2. 对长度为n的查找表进行查找时，假定查找第i个元素的概率为pi,查找长度（即在查找过程中依次同有关元素比较的总次数）为ci，则在查找成功情况下的平均查找长度的计算公式为________。 3. 假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长度________，在查找不成功情况下的平均查找长度________。 4. 以折半查找方法从长度为n的有序表中查找一个元素时，平均查找长度约等于________的向上取整减1，时间复杂度为________。 5. 以折半查找方法在一个查找表上进行查找时，该查找表必须组织成________存储的________表。 6. 从有序表(12,18,30,43,56,78,82,95)中分别折半查找43和56元素时，其比较次数分别为________和________。 7. 假定对长度n=50的有序表进行折半查找，则对应的判定树高度为________，最后一层的结点数为________。 8. 假定在索引查找中，查找表长度为n，每个子表的长度相等，设为s，则进行成功查找的平均查找长度为____________。 9. 在索引查找中，假定查找表（即主表）的长度为96，被等分为8个子表，则进行索引查找的平均查找长度为________。 10. 在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定________该结点的值，右子树上所有结点的值一定________该结点的值。 11. 对一棵二叉排序树进行中序遍历时，得到的结点序列是一个________。 12. 从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明_______， . 学习.资料. . . . . 若元素的值小于根结点的值，则继续向________查找，若元素的值大于根结点的值，则继续向________查找。 13. 向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则接着向根结点的________插入，若元素的值大于根结点的值，则接着向根结点的________插入。 14. 根据n个元素建立一棵二叉排序树的时间复杂度大致为________。 15. 在一棵平衡二叉排序树中，每个结点的左子树高度与右子树高度之差的绝对值不超过________。 16. 假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K % 7作为哈希函数，采用线性探测法处理冲突，则在建立哈希表的过程中，将会碰到________次存储冲突。 17. 假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K % 7作为哈希函数，采用线性探测法处理冲突，则平均查找长度为________。 18. 在线性表的哈希存储中，装填因子又称为装填系数，若用m表示哈希表的长度，n表示线性表中的元素的个数，则等于________。 19. 对线性表(18,25,63,50,42,32,90)进行哈希存储时，若选用H(K)=K % 9作为哈希函数，则哈希地址为0的元素有________个，哈希地址为5的元素有________个。 1. (n+1)/2, O(n) 3. 20.5, 41 4. 序 6. 1 ， log2(n+1) ，O(log2n) 5. 顺序 有 3 7. 6， 19 8. (n/s+s)/2+1 9. 11 10. 小于，大于 11. 有序序列 12. 查找成功，左子树，右子树 13. 左子树，右子树 14. O(nlog2n) 15. 1 16. 5 17. 2 18. n/m 19. 3， 2 . 学习.资料. 因篇幅问题不能全部显示，请点此查看更多更全内容