数据结构章节练习(2019.07.07)

来源：考试资料网

1 向二叉搜索树中插入一个元素时，其时间复杂度大致为（）。

2 若一个图的边集为{<1，2>，<1，4>，<2，5>，<3，1>，<3，5>，<4，3>}，则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为（）。

3.判断题二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。

4.判断题朴素模式匹配算法，算法时间复杂度为O（m*n）。

5 五节车厢以编号1，2，3，4，5顺序进入铁路调度站（栈），可以得到（）的编组。

6.问答题设计求结点在二叉排序树中层次的算法。

7.填空题两个字符串相等的充要条件是（）和（）。

参考答案：两个串的长度相等；对应位置的字符相等

8.判断题基于某种逻辑结构之上的基本操作，其实现是唯一的。

9.问答题编写在以BST为树根指针的二叉搜索树上进行查找值为item的结点的非递归算法，若查找成功则由item带回整个结点的值并返回true，否则返回false。

10.填空题无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为（）