关系 的集合R。
** 4.对于一个二维数组A[1..m,1..n]，若按行序为主序存储，则任一元素A[i,j]的相对地址（即偏移地址）为 [1] (i-1)*n+j-1 。 5.对于顺序存储的线性表，当随机插入或删除一个元素时，约需平均移动表长 [1] 一半 的元素。
6.对于长度为n的顺序表，插入或删除元素的时间复杂性为 [1] O(n) ；对于顺序栈或队列，插入或删除元素的时间复杂性为 [2] O(1) 。
7.在具有n个单元、顺序存储的循环队列中，队满时共有 [1] n-1 个元素。
8.从顺序表中删除第i个元素时，首先把第i个元素赋给 [1] 变参或函数名 带回，接着从 [2] 链接指针 开始向后的所有元素均 [3] 前移 一个位置，最后使线性表的长度 [4] 减1 。
9.在线性表的顺序存储中，元素之间的逻辑关系是通过 [1] 相邻位置 决定的；在线性表的链接存储中，元素之间的逻辑关系是通过 [2] 链接指针 决定的。 10.一个单链表中删除*p结点时，应执行如下操作: (1)q=p->next;
(2)p->data=p->next->data;
(3)p->next= [1] q->next或p->next->next ;
(4)free(q);
11.若要在一个单链表中的*p结点之前插入一个*s结点时，可执行如下操作: (1)s->next= [1] p->next ; (2)p->next=s;
(3)t=p->data;
(4)p->data= [2] s->data ; (5)s->data= [3] t ;
12.对于线性表的顺序存储，需要预先分配好存储空间，若分配太多则容易造成存储空间的 [1] 浪费 ，若分配太少又容易在算法中造成 [2] 溢出 ，因此适应于数据量变化不大的情况；对于线性表的链接存储(假定采用动态结点)，不需要 [3] 预先分配 存储空间，存储器中的整个 [4] 动态存储区 都可供使用，分配和回收结点都非常方便，能够有效地利用存储空间，在算法中不必考虑 [5] 溢出 的发生，因此适应数据量变化较大的情况。
13.无论对于顺序存储还是链接存储的栈和队列来说，进行插入或删除运算的时间复 杂性均相同，则为 [1] O(1) 。
┏0 0 2 0┓
**14.一个稀疏矩阵为 ┃3 0 0 0┃，则对应的三元组线性表为
┃0 0 -1 5┃ ((1,3,2),(2,1,3),(3,3,-1),(3,4,5))。 ┗0 0 0 0┛
15.对于一棵具有n个结点的树，则该树中所有结点的度之和为 n-1 。
16.在一棵二叉树中，度为0的结点的个数为n0 ，度为2的结点的个数为n2 ，则： n0 = n2 +1 。
17.在二叉树的顺序存储中，对于下标为5的结点，它的双亲结点的下标为 [1] 2 ， 若它存在左孩子，则左孩子结点的下标为 [2] 10 ，若它存在右孩子，则右孩子结点的下标为 [3] 11 。
18.假定一棵二叉树的广义表表示为A(B(，D)，C(E(G)，F))，则该树的深度为 [1]4 ， 度为0的结点数为 [2]3 ，度为1的结点数为 [3] 2 ，度为2的结点数为 [4]2 ；C结点
5
是A 结点的 [5] 右 孩子，E结点是C结点的 [6] 左 孩子。
19.在一棵二叉排序树中，按 中序 遍历得到的结点序列是一个有序序列。
20.由分别带权为3,9,6,2,5的共五个叶子结点构成一棵哈夫曼树，则带权路径长度为 55 。
┏━━┳━━┳━━━┓
21.假定在二叉树的链接存储中，每个结点的结构为┃left┃data┃right ┃，其中 ┗━━┻━━┻━━━┛
data为值域，left和right分别为链接左、右孩子结点的指针域，请在下面中序遍历算法
中画有横线的地方填写合适的语句。
void inorder(bt); { if bt!=nil {
(1) [1] inorder(bt->left) ； (2) [2] printf(bt->data) ； (3) [3] inorder(bt->right) ；}
}
22.在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该 顶点的 [1] 度数 ，对于有向图来说等于该顶点的 [2] 出度数 。
23.假定一个图具有n个顶点和e条边，则采用邻接矩阵表示的空间复杂性为 [1] O(n2 ) ， 采用邻接表表示的空间复杂性为 [2] O(n+e) 。
24.已知一个无向图的邻接矩阵如下所示，则从顶点A出发按深度优先搜索遍历得到的 顶点序列为 [1] ABCDFE ，按广度优先搜索遍历得到的顶点序列为 [2] ABCEFD 。 A B C D E F ┏0 1 1 0 1 0┓A ┃1 0 1 0 1 1┃B ┃1 1 0 1 0 0┃C ┃0 0 1 0 0 1┃D ┃1 1 0 0 0 1┃E
┗0 1 0 1 1 0┛F
25.已知一个图如下所示，在该图的最小生成树中，各边的权值之和为 20 。 10
① ② 15 5 2 8 ⑤
12
③ 3 ④
26.假定在有序表A[1..20]上进行二分查找，则比较一次查找成功的结点数为 [1]1 ， 比较两次查找成功的结点数为 [2]2 ，比较三次查找成功的结点数为 [3]4 ，比较四次查找成功结点数为 [4]8 ，比较五次查找成功的结点数为 [5]5 ，平均查找长度为 [6]3.7 。
27.在索引查找或分块查找中，首先查找 [1] 索引表 ，然后再查找相应的 [2]
6
子表或块 ，整个索引查找的平均查找长度等于查找索引表的平均查找长度与查找相应子表的平均查找长度之 [3] 和 。
28.在散列存储中，装填因子α的值越大，存取元素时发生冲突的可能性就 [1] 越大，当α的值越小，存取元素时发生冲突的可能性就 [2] 越小 。
29.给定线性表(18,25,63,50,42,32,90)，用散列方式存储，若选用h(K)=K % 9作为散列函数，则元素18的同义词元素共有 [1]2 个，元素25的同义词元素共有 [2]0 个，元素50的同义词元素共有 [3]1 个。
30.在对一组记录(54,38,96,23,15,72,60,45,83)进行直接选择排序时，第四次选择和交换后，未排序记录(即无序表)为 (54,72,60,96,83) 。
31.在对一组记录(54,38,96,23,15,72,60,45,38)进行冒泡排序时，第一趟需进行相邻记录交换的次数为 [1]7 ，在整个冒泡排序过程中共需进行 [2]5 趟后才能完成。 32.在归并排序中，若待排序记录的个数为20，则共需要进行 [1]5 趟归并，在第三趟归并中，是把长度为 [2]4 的有序表归并为长度为 [3]8 的有序表。
33.在直接插入和直接选择排序中，若初始数据基本正序，则选用 [1] 直接插入排序 ，若初始数据基本反序，则选用 [2] 直接选择排序 。
34.在堆排序、快速排序和归并排序中，若只从节省空间考虑，则应首先选取 [1] 堆排序 方法，其次选取 [2] 快速排序 方法，最后选取 [3] 归并排序 方法；若只从排序结果的稳定性考虑，则应选取 [4] 归并排序 ；若只从平均情况下排序最快考虑，则应选取 [5] 快速排序 方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取 [6] 堆排序 方法。
填空题参考答案
1. [1]无 [2]一 [3]无 [4]一 2. [1]前趋 [2]一 [3]后继 [4]后继 3. [1]数据元素 [2]二元关系
4. [1](i-1)*n+j-1 5. [1]一半
6. [1]O(n) [2]O(1) 7. [1]n-1 预先
8. [1]变参或函数名 [2]第i+1个元素 [3]前移 [4]减1 9. [1]相邻位置 [2]链接指针 10.[1]q->next或p->next->next
11.[1]p->next [2]s->data [3]t
12.[1]浪费 [2]溢出 [3] 预先分配 [4]动态存储区 [5]溢出 13.[1]O(1)
14.[1]((1,3,2),(2,1,3),(3,3,-1),(3,4,5))
15.[1]n-1 16.[1]n2 +1
17.[1]2 [2]10 [3]11 18.[1]4 [2]3 [3]2 [4]2 [5]右 [6]左 19.[1]中序 20.[1]55
7
21.[1]inorder(bt->left)
[2]printf(bt->data)
[3]inorder(bt->right) 22.[1]度数 [2]出度数
23.[1]O(n2 ) [2]O(n+e) 24.[1]ABCDFE [2]ABCEFD 25.[1]20
26.[1]1 [2]2 [3]4 [4]8 [5]5 [6]3.7
27.[1]索引表 [2]子表或块 [3]和 28.[1]越大 [2]越小
29.[1]2 [2]0 [3]1 30.[1](54,72,60,96,83) 31.[1]7 [2]5
32.[1]5 [2]4 [3]8 33.[1]直接插入排序 [2]直接选择排序
34.[1]堆排序 [2]快速排序 [3]归并排序 [4]归并排序 [5]快速排序 [6]堆排序 三、判断题
1．数据元素是数据的最小单位（× ）。 2．数据项是数据的基本单位（ × ）。
3．顺序存储的线性表可以随机存取（ √ ）。
4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性， 因此，是属于同一数据对象（ √ ）。
5．在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点查找任何一个元素（× ）。
6．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构（ × ）。
7．链表的每个结点中，都恰好包含一个指针（× ）。 **8．数组是同类型值的集合（× ）。 //不是集合//
**9．使用三元组表示稀疏矩阵的元素，有时并不能节省存储时间（√ ）。
**10.线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表（ √ ）。
11.由树转换成二叉树，其根结点的右子树总是空的（√ ）。
12.后序遍历树和中序遍历与该树对应的二叉树，其结果不同（ × ）。
13.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子 树的前序遍历序列中的最后一个结点（× ）。
14.若一个树叶是某子树的中序遍历序列中的最后一个结点，则它必是该子树的前序 遍历序列中的最后一个结点（√ ）。 15.已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树，因为不知道树 的根结点是哪一个（× ）。 16.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理（× ）。
17.有回路的图不能进行拓扑排序（√ ）。
8
相关推荐：
loading