浙江工商大学数据结构期末复习题2(2)

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] 子表或块 ，整个索引查找的平均查找长度等于查找索引表的平均查找长度与查找相应子表的平均查找长度之 [3] 和 。

28.在散列存储中，装填因子α的值越大，存取元素时发生冲突的可能性就 [1] 越大，

6

当α的值越小，存取元素时发生冲突的可能性就 [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

21.[1]inorder(bt->left) [2]printf(bt->data)

[3]inorder(bt->right)

7

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.线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表（ √ ）。

…… 此处隐藏：4562字，全部文档内容请下载后查看。喜欢就下载吧 ……