加载中…计算机竞赛-数据结构(填空题)
(2010-05-20 00:38:11)
标签：
杂谈 |
分类： 计算机教学 |
1、设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点
, 若将结点y插入结点x之后，则需要执行以下语句:
(py->next=px->nex)；(px->next=py)。
2、“树”是包含n个结点(n>0)的有限集合，除根结点外，集合中的每个结点有且仅有一个(前驱 答父结点或双亲结点也正确)。
3、数据的逻辑结构被分为_集合结构__、__线性结构__、___树形结构___和
_图形结构____四种。
4、数据的存储结构被分为__顺序结构__、__链接结构____、__索引结构____和
___散列结构____四种。
5.
在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着__1：1____、
___1：N（）和___M：N____的联系。
6.
一种抽象数据类型包括__数据（）_和____操作（）两个部分。
7.
当一个形参类型的长度较大时，应最好说明为__ 引用（）_，以节省参数值的传输时间和存储参数的空间。
8.
当需要用一个形参访问对应的实参时，则该形参应说明为（）引用（）。
9.
在函数中对引用形参的修改就是对相应____实参____的修改，对___值____形参的修改只局限在该函数的内部，不会反映到对应的实参上。
10.
当需要进行标准I/O操作时，则应在程序文件中包含__iostream.h___头文件，当需要进行文件I/O操作时，则应在程序文件中包含___fstream.h___头文件。
11.
在包含有__stdlib.h___头文件的程序文件中，使用___rand(
)%21__能够产生出0~20之间的一个随机整数。
12.
一个记录r理论上占有的存储空间的大小等于所有域的__长度之和__，实际上占有的存储空间的大小即记录长度为___sizeof(r)___。
13.
一个数组a所占有的存储空间的大小即数组长度为__ sizeof(r)__，下标为i的元素a[i]的存储地址为__a+i_，或者为_
(char * )a+i*sizeof(r)___。
14.
函数重载要求__参数类型___、__参数个数____或__排列次序__有所不同。
15.
对于双目操作符，其重载函数带有__2__个参数，其中至少有一个为_用户定义_的类型。
16.
若对象ra和rb中至少有一个是属于用户定义的类型，则执行ra==rb时，需要调用_ 等于号___重载函数，该函数的第一个参数应与___ra____的类型相同，第二个参数应与____rb____的类型相同。
17.
从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为__O(n)__，输出一个二维数组b[m][n]中所有元素值的时间复杂度为__O(m*n)____。
18. 在下面程序段中，s=s+p语句的执行次数为___n___，p*=j语句的执行次数为_
n(n+1)/2__，该程序段的时间复杂度为___ O(n2 )_。
19．在线性表的单链接存储结构中，每个结点包含有两个域，一个叫 值 域，另一个叫
指针 域。
20．在下面数组a中链接存储着一个线性表，表头指针为a[0].next，则该线性表为
（38, 56, 25, 60, 42, 74） 。
a
0
1 2
3
4
5
6 7 8
data
next 60 56 42 38 74 25
4 3 7 6 2 0 1
21．对于一个长度为n的顺序存储线性表，在表头插入元素的时间复杂度为 O(n) ，在表尾插入元素的时间复杂度为 O(1) 。
22．对于一个长度为n的单链接存储线性表，在表头插入元素的时间复杂度为 O(1) ，在表尾插入元素的时间复杂度为 O(n) 。
23．在线性表的顺序存储中，若一个元素的下标为i, 则它的前驱元素的下标为 i-1 ，后继元素的下标为 i+1 。
24．在线性表的的单链接存储中，若一个元素所在结点的地址为p， 则其后继结点的地址为 p->next ，若假定p为一个数组a中的下标，则其后继结点的下标为
a[p].next 。
25．在循环单链表中，最后一个结点的指针域指向 表头 结点。
26．在双向链表中每个结点包含有两个指针域，一个指向其 前驱 结点，另一个指向其 后继 结点。
27．在循环双向链表中结点的左指针域指向 表尾 结点，最后一个结点的右指针域指向 表头 结点。
28．在以HL为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为 HL－＞next=NULL 和 HL－＞next=HL 。
29．在由数组a中元素结点构成的单链表中，删除下标为i的结点后，需要把该结点插入到空闲表的表头，具体操作为 a[i].next = a[1].next ; a[1].next = i ; 。
30．在由数组a中元素结点构成的单链表中，在插入下标为i的结点之前，需要从空闲表中删除一个结点，并将该结点的下标赋给i,具体操作为 i
=a[1].next ; a[1].next= a[i].next ;。
31．在由数组a中元素结点构成的单链表中，删除下标为i的结点后，需要把该结点插入到空闲表的表头，具体操作为 p = a[i].next ; a[i].next = a[p].next ; i = p ; 。
32．在由数组a中元素结点构成的单链表中，在下标为i的结点的后面插入一个下标为j的结点时，需要进行的操作为 a[j].next=a[i].next ; a[i].next= j ; 。
33. 在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的_行号_、_列号___和__元素值___三项。
34. 在稀疏矩阵所对应的三元组线性表中，每个三元组元素按__行号___为主序、__列号___为辅序的次序排列。
35. 在初始化一个稀疏矩阵的函数定义中，矩阵形参应说明为___引用（）参数。
36. 在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应
__大于等于___对应三元组线性表的长度。
37．在稀疏矩阵的带行指针向量的链接存储中，每个结点包含有__4____个域，在相应的十字链接存储中，每个结点包含有____5____个域。
38．在稀疏矩阵的十字链接存储中，每个结点的down指针域指向__行号____相同的下一个结点，right指针域指向___列号（）相同的下一个结点。
39．一个广义表中的元素分为____表____元素和___单（）元素两类。
40．一个广义表的深度等于____括号____嵌套的最大层数。
41．在广义表的存储结构中，每个结点均包含有____3____个域。
42．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为__值____域和___子表指针____域。
43．若把整个广义表也看为一个表结点，则该结点的tag域的值为__true(或1)___，next域的值为__NULL(或0)____。
44．队列的插入操作在 队首 进行，删除操作在 队尾 进行。
45．栈又称为 后进先出 表，队列又称为 先进先出 表。
46．向一个顺序栈插入一个元素时，首先使 栈顶指针 后移一个位置，然后把待插入元素 写入 到这个位置上。
47．从一个栈删除元素时，首先取出 栈顶元素 ，然后再前移一位 栈顶指针 。
48．在一个顺序队列Q中，判断队空的条件为 Q.front= =Q.rear ，判断队满的条件为 (Q.rear+1)%QueueMaxSize= = Q.front 。
49．在一个顺序队列中，若栈顶指针等于 -1 ，则为空栈；若栈顶指针等于 StackMaxSize-1 ，则为满栈。
50．在一个链栈中，若栈顶指针等于NULL，则为 空栈 ；在一个链队中，若队首指针与队尾指针的值相同，则表示该队为 空 或该队 只含有一个结点 。
51．向一个链栈插入一个新结点时，首先把栈顶指针的值赋给 新结点的指针域 ，然后把新结点的存储位置赋给 栈顶指针 。
52．从一个链栈中删除一个结点时，需要把栈顶结点 指针域 的值赋给 栈顶指针 。
53．向一个顺序队列中插入元素时，需要首先移动 队尾指针 ，然后再向所指位置
写入 新插入的元素。
54．当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件为 top= =0 。
55．向一个栈顶指针为HS的链栈中插入一个新结点＊p时，应执行 p->next=HS; 和
HS=p; 操作。
56．从一个材顶指针为HS的非空链栈中删除结点并不需要返回材顶结点的值和回收结点时，应执行 HS=HS->next 操作。
57．假定front 和rear分别为一个链队的队首和队尾指针，则该链队中只有一个结点的条件为 (front==rear)&&(front!=NULL) 或(front==rear)&&(rear!=NULL) 。
58．中缀表达式 3*（x+2）-5 所对应的后缀表达式为 3 x + * 5 - 。
59．后缀表达式“4 5 *3 2+ -”的值为 15 。
60．在求解迷宫问题的递归算法中，输出一条通路上的每个位置的坐标是按照从入口到出口的 相反次序 进行的。
61．在进行函数调用时，需要把每个实参的值和调用后的 返回地址 传送给被调用的函数中。
62．当被调用的函数执行结束后，将自动按所保存的 返回地址 执行。
63．对于一棵具有n个结点的树，该树中所有结点的度数之和为__n-1____。
64.
假定一棵三叉树的结点个数为50，则它的最小深度为___5（），最大深度为___50____。
65．在一棵高度为h的四叉树中，最多含有___4h-1/3（）结点。
66．在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有___6（）个。
67．一棵深度为5的满二叉树中的结点数为___31（）个，一棵深度为3的满四叉树中的结点数为____21____个。
68．假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则树中所含的结点数为____10____个，树的深度为___4（），树的度为___3（）。
69．假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则度为3、2、1、0的结点数分别为___2___、___1___、___1___和___6___个。
70.
假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则结点H的双亲结点为___B（），孩子结点为____I_和_J（）。
71．在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为____6____个。
72．对于一棵二叉树，若一个结点的编号为i，则它的左孩子结点的编号为____2i____，右孩子结点的编号为__2i+1（）_，双亲结点的编号为_
i/2（）。
73．在一棵二叉树中，第5层上的结点数最多为__16____。
74．假定一棵二叉树的结点数为18，则它的最小深度为___5（），最大深度为____18____。
75．一棵二叉树的广义表表示为a(b(c,d),e(f(,g)))，则e结点的双亲结点为__a____，左孩子结点为____f____，右孩子结点为___空（）。
76.
一棵二叉树的广义表表示为a(b(c,d),e(f(,g)))，它含有双亲结点___2___个，单分支结点___2___个，叶子结点___3___个。
77．对于一棵含有40个结点的理想平衡树，它的高度为___6（）。
78.
假定一棵二叉树顺序存储在一维数组a中，则a[i]元素的左孩子元素为__a[2i]__，右孩子元素为__a[2i+1]____，双亲元素(i>1)为__a[i/2]（）_。
79．假定一棵二叉树顺序存储在一维数组a中，但让编号为1的结点存入a[0]元素中，让编号为2的结点存入a[1]元素中，其余类推，则编号为i结点的左孩子结点对应的存储位置为__2i-1（）_，若编号为i结点的存储位置用j表示，则其左孩子结点对应的存储位置为__2i+1（）_。
80.若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组a中，即编号为0的结点存储到a[0]中，其余类推，则a[i]元素的左孩子元素为_a[2i+1]__，右孩子元素为__
a[2i+2]__，双亲元素(i>0)为_ a[(i-1)/2]_。
81．对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为___2n____个，其中__n-1____个用于指向孩子结点，__n+1____个指针空闲着。
82.
一棵二叉树广义表表示为a(b(d(,h)),c(e,f(g,i(k))))，该树的结点数为___10____个，深度为___5（）。
83．在一棵高度为5的理想平衡树中，最少含有___16__个结点，最多含有__31___个结点。
84．在一棵高度为h的理想平衡树中，最少含有__2n-1__个结点，最多含有__2n-1___个结点。
85.
假定一棵二叉树广义表表示为a(b(c),d(e,f))，则对它进行的先序遍历结果为__a,b,c,d,e,f___，中序遍历结果为__c,b,a,e,d,f_，后序遍历结果为__c,b,e,f,d,a___，按层遍历结果为__a,b,d,c,e,f____。
86. 假定一棵普通树的广义表表示为a (b (e ), c (f (h, i, j),g ),d)，则先根遍历结果为
__a b e c f h i j g d ___，按层遍历结果为__a b c d e f g h i j___。
87. 在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定__小于___该结点的值，右子树上所有结点的值一定__大于等于____该结点的值。
88．对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个___有序序列（）。
89．从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明_查找成功__，若元素的值小于根结点的值，则继续向_左子树___查找，若元素的大于根结点的值，则继续向__右子树____查找。
90．在一个堆的顺序存储中，若一个元素的下标为i，则它的左孩子元素的下标为__2i+1___，右孩子元素的下标为__2i+2___。
91. 在一个小根堆中，堆顶结点的值是所有结点中的__最小值___，在一个大根堆中，堆顶结点的值是所有结点中的__最大值（）_。
92．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层__向上____调整，直到被调整到__堆顶____位置为止。
93．当从一个小根堆中删除一个元素时，需要把__堆尾____元素填补到__堆顶____位置，然后再按条件把它逐层__向下____调整。
94．在哈夫曼编码中，若编码长度只允许小于等于4，则除了已对两个字符编码为0和10外，还可以最多对____4___个字符编码。
95．在一个图中，所有顶点的度数之和等于所有边数的__2____倍。
96．在一个具有n个顶点的无向完全图中，包含有__n(n-1)/2__条边，在一个具有n个顶点的有向完全图中，包含有__
n(n-1)___条边。
97. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要_ n-1__条边。
98．表示图的三种存储结构为__邻接矩阵__、_邻接表__和_边集数组___。
99. 对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为__n*n（）_。
100．对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为____e____和___2e____条。
101.
在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有___出边（）和___入边（）结点。
102．对于一个具有n个顶点和e条边的有向图和无向图，若采用边集数组表示，则存于数组中的边数分别为__e__和___e___条。
103．对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表和边集数组表示时，求任一顶点度数的时间复杂度依次为__O(n)___、__O(e/n)__和__O(e)___。
104. 假定一个图具有n个顶点和e条边，则采用邻接矩阵、邻接表和边集数组表示时，其相应的空间复杂度分别为__ O(n2)__、__ O(n+e)__和__ O(e)__。
105. 对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为__ O(n2)__，对用邻接表表示的图进行任一种遍历时，其时间复杂度为_ O(e)___。
106．对于图7-1(a)所示的无向图，假定用邻接矩阵表示，则从顶点v0开始进行深度优先搜索遍历得到的顶点序列为_ v0 v1 v4 v2 v5 v3___，从顶点v0开始进行广度优先搜索遍历得到的顶点序列为__ v0 v1 v2 v3 v4 v5__。
107. 对于图7-1(b)所示的有向图，假定用邻接矩阵表示，则从顶点v0开始进行深度优先搜索遍历得到的顶点序列为__A,B,C,D,E__，从顶点v0开始进行广度优先搜索遍历得到的顶点序列为__A,B,C,E,D____。
108. 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为___n__和__n-1__。
109. 对于图7-5(a)所示的带权图，其最小生成树的权为___22___。
110．对于图7-5(a)所示的图，若从顶点v0出发，则按照普里姆算法生成的最小生成树中，依次得到的各条边为__5,3,6,8___。
111. 对于图7-5(a)所示的图，若按照克鲁斯卡尔算法产生最小生成树，则得到的各条边依次为___3,5,6,8___。
112．假定用一维数组d[n]存储一个AOV网中用于拓扑排序的顶点入度，则值为0的元素被链接成为一个__栈_。
113．以顺序查找方法从长度为n的线性表中查找一个元素时，平均查找长度为_ n(n-1)/2___，时间复杂度为__ O(n)___。
114．以二分查找方法从长度为n的线性表中查找一个元素时，平均查找长度小于等于_log2(n+1)____，时间复杂度为_O(log2n)____。
115．以二分查找方法从长度为12的有序表中查找一个元素时，平均查找长度为__37/12___。
116．以二分查找方法查找一个线性表时，此线性表必须是__顺序__存储的__有序___表。
117．从有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素时，其查找长度分别为__1 _和___3（）。
118．对于二分查找所对应的判定树，它既是一棵__二叉搜索树_，又是一棵_理想平衡树_。
119．假定对长度n=50的有序表进行二分查找，则对应的判定树高度为___6（），判定树中前5层的结点数为___31（），最后一层的结点数为___19（）。
120．在索引表中，每个索引项至少包含有__索引值___域和__子表开始域___域这两项。
121．假定一个线性表为(12,23,74,55,63,40,82,36)，若按Key % 3条件进行划分，使得同一余数的元素成为一个子表，则得到的三个子表分别为_(12,63,36)__、_(55,40,82)__和__(23,74)____。
122. 假定一个线性表为(”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”)，若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的a,b,c三个子表的长度分别为___3（）、____3____和___2（）。
123．在索引表中，若一个索引项对应主表中的一条记录，则称此索引为__稠密___索引，若对应主表中的若干条记录，则称此索引为___稀疏____索引。
124．在稀疏索引表上进行二分查找时，若当前查找区间为空，则不是返回-1表示查找失败，而是返回该区间的___下限值（）。
125．假定对长度n=100的线性表进行索引查找，并假定每个子表的长度均为
,则进行索引查找的平均查找长度为___11（），时间复杂度为__O( )____。
126. 若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个记录的索引，则一级索引表的长度为__500___，二级索引表的长度为___25___。
127．在线性表的___散列____存储中，无法查找到一个元素的前驱或后继元素。
128．在线性表的___链接（）存储中，对每一个元素只能采用顺序查找。
129．假定对线性表(38,25,74,52,48)进行散列存储，采用H(K)=K % 7作为散列函数，若分别采用线性探查法和链接法处理冲突，则对各自散列表进行查找的平均查找长度分别为___2____和___4/3（）。
130．假定要对长度n=100的线性表进行散列存储，并采用链接法处理冲突，则对于长度m=20的散列表，每个散列地址的单链表的长度平均为___5（）。
131．在线性表的散列存储中，装填因子又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则等于___n/m（）。
132. 在线性表的散列存储中，处理冲突有__开放定址法__和__链接法___两种方法。
133．对于线性表(18,25,63,50,42,32,90)进行散列存储时，若选用H(K)=K % 9作为散列函数，则散列地址为0的元素有___3___个，散列地址为5的元素有____2____个。
134．对于一棵含有N个关键字的m阶B_树，其最小高度为_ logm(N+1)____，
最大高度为__1+ logm/2((N+1)/2)___。
135. 已知一棵3阶B_树中含有50个关键字，则该树的最小高度为__4（）_，最大高度为____5____。
136．在一棵9阶的B_树中，每个非树根结点的关键字数目最少为___4（）个，最多为____8____个。
137．在一棵m阶B_树上，每个非树根结点的关键字数目最少为_m/2-1___个，最多为__m-1（）_个，其子树数目最少为__m/2（）_，最多为___m（）。
138.在一棵B_树中，所有叶子结点都处在__同一层（）_上，所有叶子结点中空指针等于所有__关键字（）_总数加1。
139．在对m阶B_树插入元素的过程中，每向一个结点插入一个索引项(叶子结点中的索引项为关键字和空指针)后，若该结点的索引项数等于__m（）个，则必须把它分裂为____两____个结点。
140．在从m阶的B_树删除元素的过程中，当一个结点被删除掉一个索引项后，所含索引项数等于__m/2-2（）_个，并且它的左、右兄弟结点中的索引项数均等于___m/2-1___个，则必须进行结点合并。
141．向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度__增加1（）。
30．从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树比原树的高度___减少1（）。
142．每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做__插入（）排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做___选择（）排序。
143．每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做___交换（）排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做__二路归并（）排序。
144．在直接选择排序中，记录比较次数的时间复杂度为__ O(n2)___，记录移动次数的时间复杂度为__ O(n)__。
145. 在堆排序的过程中，对n个记录建立初始堆需要进行__n/2（）_次筛运算，由初始堆到堆排序结束，需要对树根结点进行__n-1（）次筛运算。
146．在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为__ O(log2n)__，整个堆排序过程的时间复杂度为__ O(nlog2n)__。
147．假定一组记录的排序码为(46,79,56,38,40,84)，则利用堆排序方法建立的初始堆为__(84,79,56,38,40,46)（）__。
148. 快速排序在平均情况下的时间复杂度为__ O(nlog2n)___，在最坏情况下的时间复杂度为___ O(n2)____。
149．快速排序在平均情况下的空间复杂度为__ O(log2n)__，在最坏情况下的空间复杂度为___ O(n)____。
150．在快速排序方法中，进行每次划分时，是从当前待排序区间的_两端___向_中间__依次查找出处于逆序的元素并交换之，最后将基准元素交换到一个确定位置，从而以该位置把当前区间划分为前后两个子区间。
151. 假定一组记录的排序码为(46,79,56,38,40,80)，对其进行快速排序的一次划分的结果为__[ 38 40 ] 46 [
56 79 84 ]____。
152. 假定一组记录的排序码为(46,79,56,38,40,80)，对其进行快速排序的过程中，对应二叉搜索树的深度为___4（），分支结点数为__4（）_。
153．在二路归并排序中，对n个记录进行归并的趟数为__log2n____。
154. 在归并排序中，进行每趟归并的时间复杂度为___ O(n)（），整个排序过程的时间复杂度为___ O(nlog2n)（）_，空间复杂度为____ O(n)____。
155．对20个记录进行归并排序时，共需要进行___5（）趟归并，在第三趟归并时是把长度为____4____的有序表两两归并为长度为___8（）的有序表。
156．假定一组记录的排序码为(46,79,56,38,40,80)，对其进行归并排序的过程中，第二趟归并后的结果为__[38
46 56 79 ]
[40 84 ]（）。
2、“树”是包含n个结点(n>0)的有限集合，除根结点外，集合中的每个结点有且仅有一个(前驱 答父结点或双亲结点也正确)。
3、数据的逻辑结构被分为_集合结构__、__线性结构__、___树形结构___和
_图形结构____四种。
___散列结构____四种。
___1：N（）和___M：N____的联系。
19．在线性表的单链接存储结构中，每个结点包含有两个域，一个叫 值 域，另一个叫
指针 域。
20．在下面数组a中链接存储着一个线性表，表头指针为a[0].next，则该线性表为
（38, 56, 25, 60, 42, 74） 。
a
data
next
21．对于一个长度为n的顺序存储线性表，在表头插入元素的时间复杂度为 O(n) ，在表尾插入元素的时间复杂度为 O(1) 。
22．对于一个长度为n的单链接存储线性表，在表头插入元素的时间复杂度为 O(1) ，在表尾插入元素的时间复杂度为 O(n) 。
23．在线性表的顺序存储中，若一个元素的下标为i, 则它的前驱元素的下标为 i-1 ，后继元素的下标为 i+1 。
24．在线性表的的单链接存储中，若一个元素所在结点的地址为p， 则其后继结点的地址为 p->next ，若假定p为一个数组a中的下标，则其后继结点的下标为
25．在循环单链表中，最后一个结点的指针域指向 表头 结点。
26．在双向链表中每个结点包含有两个指针域，一个指向其 前驱 结点，另一个指向其 后继 结点。
27．在循环双向链表中结点的左指针域指向 表尾 结点，最后一个结点的右指针域指向 表头 结点。
28．在以HL为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为 HL－＞next=NULL 和 HL－＞next=HL 。
29．在由数组a中元素结点构成的单链表中，删除下标为i的结点后，需要把该结点插入到空闲表的表头，具体操作为 a[i].next = a[1].next ; a[1].next = i ; 。
31．在由数组a中元素结点构成的单链表中，删除下标为i的结点后，需要把该结点插入到空闲表的表头，具体操作为 p = a[i].next ; a[i].next = a[p].next ; i = p ; 。
32．在由数组a中元素结点构成的单链表中，在下标为i的结点的后面插入一个下标为j的结点时，需要进行的操作为 a[j].next=a[i].next ; a[i].next= j ; 。
33. 在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的_行号_、_列号___和__元素值___三项。
34. 在稀疏矩阵所对应的三元组线性表中，每个三元组元素按__行号___为主序、__列号___为辅序的次序排列。
35. 在初始化一个稀疏矩阵的函数定义中，矩阵形参应说明为___引用（）参数。
36. 在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应
__大于等于___对应三元组线性表的长度。
37．在稀疏矩阵的带行指针向量的链接存储中，每个结点包含有__4____个域，在相应的十字链接存储中，每个结点包含有____5____个域。
38．在稀疏矩阵的十字链接存储中，每个结点的down指针域指向__行号____相同的下一个结点，right指针域指向___列号（）相同的下一个结点。
39．一个广义表中的元素分为____表____元素和___单（）元素两类。
40．一个广义表的深度等于____括号____嵌套的最大层数。
43．若把整个广义表也看为一个表结点，则该结点的tag域的值为__true(或1)___，next域的值为__NULL(或0)____。
44．队列的插入操作在 队首 进行，删除操作在 队尾 进行。
45．栈又称为 后进先出 表，队列又称为 先进先出 表。
46．向一个顺序栈插入一个元素时，首先使 栈顶指针 后移一个位置，然后把待插入元素 写入 到这个位置上。
47．从一个栈删除元素时，首先取出 栈顶元素 ，然后再前移一位 栈顶指针 。
48．在一个顺序队列Q中，判断队空的条件为 Q.front= =Q.rear ，判断队满的条件为 (Q.rear+1)%QueueMaxSize= = Q.front 。
49．在一个顺序队列中，若栈顶指针等于 -1 ，则为空栈；若栈顶指针等于 StackMaxSize-1 ，则为满栈。
50．在一个链栈中，若栈顶指针等于NULL，则为 空栈 ；在一个链队中，若队首指针与队尾指针的值相同，则表示该队为 空 或该队 只含有一个结点 。
51．向一个链栈插入一个新结点时，首先把栈顶指针的值赋给 新结点的指针域 ，然后把新结点的存储位置赋给 栈顶指针 。
52．从一个链栈中删除一个结点时，需要把栈顶结点 指针域 的值赋给 栈顶指针 。
53．向一个顺序队列中插入元素时，需要首先移动 队尾指针 ，然后再向所指位置
写入 新插入的元素。
54．当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件为 top= =0 。
55．向一个栈顶指针为HS的链栈中插入一个新结点＊p时，应执行 p->next=HS; 和
HS=p; 操作。
56．从一个材顶指针为HS的非空链栈中删除结点并不需要返回材顶结点的值和回收结点时，应执行 HS=HS->next 操作。
57．假定front 和rear分别为一个链队的队首和队尾指针，则该链队中只有一个结点的条件为 (front==rear)&&(front!=NULL) 或(front==rear)&&(rear!=NULL) 。
58．中缀表达式 3*（x+2）-5 所对应的后缀表达式为 3 x + * 5 - 。
59．后缀表达式“4 5 *3 2+ -”的值为 15 。
60．在求解迷宫问题的递归算法中，输出一条通路上的每个位置的坐标是按照从入口到出口的 相反次序 进行的。
61．在进行函数调用时，需要把每个实参的值和调用后的 返回地址 传送给被调用的函数中。
62．当被调用的函数执行结束后，将自动按所保存的 返回地址 执行。
63．对于一棵具有n个结点的树，该树中所有结点的度数之和为__n-1____。
86. 假定一棵普通树的广义表表示为a (b (e ), c (f (h, i, j),g ),d)，则先根遍历结果为
__a b e c f h i j g d ___，按层遍历结果为__a b c d e f g h i j___。
87. 在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定__小于___该结点的值，右子树上所有结点的值一定__大于等于____该结点的值。
88．对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个___有序序列（）。
89．从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明_查找成功__，若元素的值小于根结点的值，则继续向_左子树___查找，若元素的大于根结点的值，则继续向__右子树____查找。
90．在一个堆的顺序存储中，若一个元素的下标为i，则它的左孩子元素的下标为__2i+1___，右孩子元素的下标为__2i+2___。
91. 在一个小根堆中，堆顶结点的值是所有结点中的__最小值___，在一个大根堆中，堆顶结点的值是所有结点中的__最大值（）_。
92．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层__向上____调整，直到被调整到__堆顶____位置为止。
93．当从一个小根堆中删除一个元素时，需要把__堆尾____元素填补到__堆顶____位置，然后再按条件把它逐层__向下____调整。
94．在哈夫曼编码中，若编码长度只允许小于等于4，则除了已对两个字符编码为0和10外，还可以最多对____4___个字符编码。
103．对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表和边集数组表示时，求任一顶点度数的时间复杂度依次为__O(n)___、__O(e/n)__和__O(e)___。
104. 假定一个图具有n个顶点和e条边，则采用邻接矩阵、邻接表和边集数组表示时，其相应的空间复杂度分别为__ O(n2)__、__ O(n+e)__和__ O(e)__。
105. 对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为__ O(n2)__，对用邻接表表示的图进行任一种遍历时，其时间复杂度为_ O(e)___。
106．对于图7-1(a)所示的无向图，假定用邻接矩阵表示，则从顶点v0开始进行深度优先搜索遍历得到的顶点序列为_ v0 v1 v4 v2 v5 v3___，从顶点v0开始进行广度优先搜索遍历得到的顶点序列为__ v0 v1 v2 v3 v4 v5__。
107. 对于图7-1(b)所示的有向图，假定用邻接矩阵表示，则从顶点v0开始进行深度优先搜索遍历得到的顶点序列为__A,B,C,D,E__，从顶点v0开始进行广度优先搜索遍历得到的顶点序列为__A,B,C,E,D____。
108. 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为___n__和__n-1__。
109. 对于图7-5(a)所示的带权图，其最小生成树的权为___22___。
110．对于图7-5(a)所示的图，若从顶点v0出发，则按照普里姆算法生成的最小生成树中，依次得到的各条边为__5,3,6,8___。
111. 对于图7-5(a)所示的图，若按照克鲁斯卡尔算法产生最小生成树，则得到的各条边依次为___3,5,6,8___。
112．假定用一维数组d[n]存储一个AOV网中用于拓扑排序的顶点入度，则值为0的元素被链接成为一个__栈_。
113．以顺序查找方法从长度为n的线性表中查找一个元素时，平均查找长度为_ n(n-1)/2___，时间复杂度为__ O(n)___。
114．以二分查找方法从长度为n的线性表中查找一个元素时，平均查找长度小于等于_log2(n+1)____，时间复杂度为_O(log2n)____。
115．以二分查找方法从长度为12的有序表中查找一个元素时，平均查找长度为__37/12___。
116．以二分查找方法查找一个线性表时，此线性表必须是__顺序__存储的__有序___表。
117．从有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素时，其查找长度分别为__1 _和___3（）。
118．对于二分查找所对应的判定树，它既是一棵__二叉搜索树_，又是一棵_理想平衡树_。
119．假定对长度n=50的有序表进行二分查找，则对应的判定树高度为___6（），判定树中前5层的结点数为___31（），最后一层的结点数为___19（）。
120．在索引表中，每个索引项至少包含有__索引值___域和__子表开始域___域这两项。
121．假定一个线性表为(12,23,74,55,63,40,82,36)，若按Key % 3条件进行划分，使得同一余数的元素成为一个子表，则得到的三个子表分别为_(12,63,36)__、_(55,40,82)__和__(23,74)____。
122. 假定一个线性表为(”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”)，若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的a,b,c三个子表的长度分别为___3（）、____3____和___2（）。
126. 若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个记录的索引，则一级索引表的长度为__500___，二级索引表的长度为___25___。
127．在线性表的___散列____存储中，无法查找到一个元素的前驱或后继元素。
128．在线性表的___链接（）存储中，对每一个元素只能采用顺序查找。
129．假定对线性表(38,25,74,52,48)进行散列存储，采用H(K)=K % 7作为散列函数，若分别采用线性探查法和链接法处理冲突，则对各自散列表进行查找的平均查找长度分别为___2____和___4/3（）。
130．假定要对长度n=100的线性表进行散列存储，并采用链接法处理冲突，则对于长度m=20的散列表，每个散列地址的单链表的长度平均为___5（）。
131．在线性表的散列存储中，装填因子又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则等于___n/m（）。
132. 在线性表的散列存储中，处理冲突有__开放定址法__和__链接法___两种方法。
133．对于线性表(18,25,63,50,42,32,90)进行散列存储时，若选用H(K)=K % 9作为散列函数，则散列地址为0的元素有___3___个，散列地址为5的元素有____2____个。
134．对于一棵含有N个关键字的m阶B_树，其最小高度为_ logm(N+1)____，
最大高度为__1+ logm/2((N+1)/2)___。
135. 已知一棵3阶B_树中含有50个关键字，则该树的最小高度为__4（）_，最大高度为____5____。
136．在一棵9阶的B_树中，每个非树根结点的关键字数目最少为___4（）个，最多为____8____个。
137．在一棵m阶B_树上，每个非树根结点的关键字数目最少为_m/2-1___个，最多为__m-1（）_个，其子树数目最少为__m/2（）_，最多为___m（）。
138.在一棵B_树中，所有叶子结点都处在__同一层（）_上，所有叶子结点中空指针等于所有__关键字（）_总数加1。
139．在对m阶B_树插入元素的过程中，每向一个结点插入一个索引项(叶子结点中的索引项为关键字和空指针)后，若该结点的索引项数等于__m（）个，则必须把它分裂为____两____个结点。
140．在从m阶的B_树删除元素的过程中，当一个结点被删除掉一个索引项后，所含索引项数等于__m/2-2（）_个，并且它的左、右兄弟结点中的索引项数均等于___m/2-1___个，则必须进行结点合并。
141．向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度__增加1（）。
142．每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做__插入（）排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做___选择（）排序。
143．每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做___交换（）排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做__二路归并（）排序。
144．在直接选择排序中，记录比较次数的时间复杂度为__ O(n2)___，记录移动次数的时间复杂度为__ O(n)__。
145. 在堆排序的过程中，对n个记录建立初始堆需要进行__n/2（）_次筛运算，由初始堆到堆排序结束，需要对树根结点进行__n-1（）次筛运算。
146．在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为__ O(log2n)__，整个堆排序过程的时间复杂度为__ O(nlog2n)__。
147．假定一组记录的排序码为(46,79,56,38,40,84)，则利用堆排序方法建立的初始堆为__(84,79,56,38,40,46)（）__。
148. 快速排序在平均情况下的时间复杂度为__ O(nlog2n)___，在最坏情况下的时间复杂度为___ O(n2)____。
149．快速排序在平均情况下的空间复杂度为__ O(log2n)__，在最坏情况下的空间复杂度为___ O(n)____。
150．在快速排序方法中，进行每次划分时，是从当前待排序区间的_两端___向_中间__依次查找出处于逆序的元素并交换之，最后将基准元素交换到一个确定位置，从而以该位置把当前区间划分为前后两个子区间。
151. 假定一组记录的排序码为(46,79,56,38,40,80)，对其进行快速排序的一次划分的结果为__[ 38
152. 假定一组记录的排序码为(46,79,56,38,40,80)，对其进行快速排序的过程中，对应二叉搜索树的深度为___4（），分支结点数为__4（）_。
153．在二路归并排序中，对n个记录进行归并的趟数为__log2n____。
154. 在归并排序中，进行每趟归并的时间复杂度为___ O(n)（），整个排序过程的时间复杂度为___ O(nlog2n)（）_，空间复杂度为____ O(n)____。
155．对20个记录进行归并排序时，共需要进行___5（）趟归并，在第三趟归并时是把长度为____4____的有序表两两归并为长度为___8（）的有序表。
156．假定一组记录的排序码为(46,79,56,38,40,80)，对其进行归并排序的过程中，第二趟归并后的结果为__[38
喜欢
0
赠金笔
前一篇：计算机竞赛-数据库技术(填空题)
后一篇：2010年06月06日