二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(37)

21. 如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（ ）

22. 设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（ ）

23. 分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块

号，然后再在相应的块内进行顺序查找。（ ）

24. 向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（ ）

25. 如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（ ）

26. 非空的双向循环链表中任何结点的前驱指针均不为空。（ ）

27. 不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为

O(n)。（ ）

28. 图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问

过。（ ）

29. 有向图的邻接表和逆邻接表中表结点的个数不一定相等。( )

30. 对链表进行插入和删除操作时不必移动链表中结点。( )

31. 子串“ABC”在主串“AABCABCD”中的位置为2。( )

32. 若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序

遍历序列中的最后一个结点。( )

33. 希尔排序算法的时间复杂度为O(n2)。( )

34. 用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边

数有关。( )

35. 中序遍历一棵二叉排序树可以得到一个有序的序列。( )

36. 入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。( )

37. 顺序表查找指的是在顺序存储结构上进行查找。（ ）

38. 堆是完全二叉树，完全二叉树不一定是堆。（ ）

三、计算题

1. 在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。

data

next 2.

3. 已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};

E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,

(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};

用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。

4. 画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。

5. 设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择

排序和第4趟直接插入排序后的结果。

6. 设指针变量p

指向双向链表中结点A，指针变量q指向入结点B，要求给出在结点

A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。

7. 设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用

二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。

8. 设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要

求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。

9. 设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。

10. 设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给

出构造过程。

11. 已知二叉树的前序遍历序列是AEFBHIKJ，中序遍历序列是EFAGBCHKIJD，画

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25557-37.html