一、填空(30分):1、二维数组A[10,20]采用以行为主的方式存储,每个元素占一个存储单元,并且A[1,1]的存储地址是200,则A[6,12]的地址是_______________。
2、线性表、栈和队列都是___________结构,栈的特点是____________,队列的特点是____________。
3、在一个长度为n的线性表中删除第i个元素(1≤i≤n)时,需向前移动个元素。
4、对分查找的存储结构仅限于________________,且是______________。
5、在双向链表中,每个结点有两个指针域,一个指向________________,另一个指向________________。
6、已知一个有向图的邻接矩阵表示,计算第i个结点的入度的方法是________________。
7、已知某二叉树的前序遍历序列是“stuwv”,中序遍历序列是“uwtvs”,它的后序遍历序列是_________________。
8、下列程序段的时间复杂性是_________________。
For i = 1 To nFor j = 1 To mA(i,j) = 09、以数据集{4,5,6,7,10,12,18}为结点权值所构造的Huffman树的带权路径长度为____________。
10、n个顶点的连通图至少有条边。
11、数据结构被形式地定义为(D,R),其中D是______________的有限集合,R是D 上____________的有限集合。
12、线性表的逻辑顺序与存储顺序总是一致的,这种说法是否正确,_________。
13、数据结构的存储方式主要有______________和_____________两种它们之间的本质区别是_______________。
14、栈的操作方式是________________,队列的操行方式是__________________。
15、数据的逻辑结构包括_____________、________________和______________三种类型。
16、在图形结构中,每个结点的前件结点数和后件结点数可以有____________。
17、判定一个队列Q(最多元素为m0)为空队列的条件是________________,为满队列的条件是________________;判定一个循环队列Q(最多元素为m0)为空队列的条件是________________,为满队列的条件是________________。
18、已知某二叉树的后序遍历序列是“dabec”,中序遍历序列是“debac”,它的前序遍历序列是_________________。
19、如果对于给定的一组权值,所构造出的二叉树的带权路径长度最小,则称该树为。
20、向一个长度为n的线性表的第i个元素(1≤i≤n+1)之前插入一个元素时,需向后移动______________个元素。
21、设栈S和队列Q的初始状态为空,元素a1、a2、a3、a4、a5和a6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队的顺序是a2、a4、a3、a6、a5、a1,则栈的容量至少应该是_______________。
22、二维数组A[10,20]采用以行为主的方式存储,每个元素占一个存储单元,并且A[1,1]的存储地址是200,则A[6,12]的地址是_______________。
23、线性表、栈和队列都是___________结构,可以在线性表的____________位置插入和删除元素;对于栈只能在____________插入和删除元素;对于队列只能在__________插入元素和__________删除元素。
24、对分查找的存储结构仅限于________________,且是______________。
25、在双向链表中,每个结点有两个指针域,一个指向________________,另一个指向________________。
27、对于长度为n的线性表,若进行顺序查找,则时间复杂性为O (n),若采用二分查找法,则时间复杂性为O (log2n),若采用分块法查找,时间复杂性介于和之间。
28、二维数组A[10,20]采用以列为主的方式存储,每个元素占一个存储单元,并且A[1,1]的存储地址是200,则A[6,12]的地址是_______________。
29、在分块查找方法中首先查找_______________,然后再查找相应的____________。
30、一组序列为{46、79、56、38、40、84},利用堆排序的方法建立的初始堆为_______________________________________。
31、设循环队列的容量为50(序号从1到50),现经过一系列的入队和退队运算后,有front=20,rear=15,循环队列中有________个元素。
32、数据结构的存储方式主要有_____________和___________两种,这两种存储结构的本质区别是__________________________。
33、将递归算法转换为非递归算法时,通常需要使用______来存储尚待处理的元素。
34、在无向图G的邻接矩阵A中,若A[i,j]=1 , 则A[j,i] 等于______。
35、n个顶点的连通图至少有条边。
36、已知一个图的邻接矩阵表示,删除所有从第i个结点出发的边的方法是。
(将矩阵第i行全部置为零)37、若数据元素序列 (K1, K2, K3, … , Kn) 是一个堆,则序列中元素的关系是____________________________________。
38、二叉树的前序遍历序列中,任何一个结点均处在其子女结点的前面,这种说法是否正确________;而对于中序遍历序列,这种说法是否正确__________。
39、对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小是________。
40、在一个双向链表的p结点之后插入s结点的操作是____________________________________________________________________________________________________ __。
41、设n行n列的下三角矩阵A已压缩到一维数组B[1:n(n+1)/2]中,若以行为主存储,则A[i , j ] ( i ≥j ) 对应的B中的存储位置是________________。
40、有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当用二分查找法查找值为82的结点时,_____次比较后查找成功。
41、采用链式存储结构的有序表能否用二分查找法进行查找__________。
43、排序方法中,从未排序序列中依次取出元素与已排序序列(初始为空)中的元素进行比较,将其放入已排序序列的正确位置上的方法,称为___________________。
44、一组序列为{46、79、56、38、40、84},利用堆排序的方法建立的初始堆为_______________________________________。
48、下列程序段的时间复杂性是_________________。
for i = 1 To n-1{ y=y+1for j = 1 To 2*nx = x + 1}49、下列程序段的时间复杂性是_________________。
Sum=0 ;for i = 1 To n{ p=1 ;for j = 1 To ip = p * j ;sum = sum + p ;}49、数据逻辑结构可分为两大类,它们分别是和。
50、数据结构的存储应存储两方面的内容,它们分别是和;数据存储结构也可分为两大类,它们分别是和。
51、设栈S和队列Q的初始状态为空,元素a1、a2、a3、a4、a5、a6、a7和a8依次通过栈S,一个元素出栈后即进入队列Q,若8个元素出队的顺序是a4、a6、a5、a7、a3、 a2、a8、a1,则栈的容量至少应该是_________。
52、线性表L={a1、a2、……、a n},如删除表中任一元素的概率相同,则删除一个元素平均需要移动元素的个数是。
53、若二叉树前遍历访问结点顺序为abdgcefh,中序遍历访问结点顺序为dgbaechf,则其后序遍历访问结点顺序为。
54、二维数组A[10,20]采用以列为主的方式存储,每个元素占一个存储单元,并且A[1,1]的存储地址是100,则A[8,12]的地址是_______________。
55、如要求一个线性表既能很快地查找,又能适应动态变化的要求,在分块查找法、顺序查找法和二分查找法中最好采用哪种方法______________。
56、已知一个有向图的邻接矩阵表示,计算第i个结点的出度的方法是________________。
57、线性表的逻辑顺序与存储顺序总是一致的,这种说法是否正确。
58、设n行n列的下三角矩阵A已压缩到一维数组S[1, n*(n+1)/2]中,若按行为主存储,则A[i , j ]对应的S中的存储位置是。
( i*(i-1)/2+j )59、有一个10阶对称矩阵A,采用压缩存储方式存储(以行为主存储,且A[1,1]=1),则A[8,5]的地址为。
( 33 )60、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的倍。
61、在一个具有n个顶点的无向图中,要连通全部顶点至少需要条边。
62、对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小是。
63、根据所用数据模型的不同,数据库系统可以分为______________、________________、___________________三类。
64、关系模型中,一个关系的_____________称为关系模式。
65、在关系模型中,把数据库看成是一个二维表,每一个二维表称为一个_________,表中每一行称为__________,表中每一列称为__________。
66、E-R图称为________________,它是用于描述数据库____________的有效工具,用E-R图可以简单明了地描述__________________________。
67、关系数据库中有三种基本操作,从表中取出满足条件的属性的操作称为;从表中选出满足某种条件的元组的操作称为;将两个关系中具有共同属性值的元组连接到一起,构成新表称为。
68、假设学生关系为S(学号,姓名,性别),课程关系为C(课程号,课程名,教师),学生选课关系为SC(学号,课程号,分数),要查找选修“物理”课的男学生姓名,将涉及到关系。