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