精品文档---下载后可任意编辑试 题 B一、填空题（18 小题，40 个空，每空分，共 20 分）1、数据结构是一门讨论非数值计算的程序设计问题中计算机的 以及它们之间的 和运算等的学科。2、线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。3、在顺序表中插入或删除一个元素，需要平均移动 ，具体移动的元素个数与 有关。4、在顺序表中访问任意一结点的时间复杂度均为 ，因此，顺序表也称为 的数据结构。5、顺序表中逻辑上相邻的元素的物理位置 相邻。单链表中逻辑上相邻的元素的物理位置 相邻。6、若 n 为主串长，m 为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为 。7、求下列广义表操作的结果：（1） GetHead【((a,b),(c,d))】=== ; //头元素不必加括号（2） GetHead【GetTail【((a,b),(c,d))】】=== ;（3） GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== ;（4） GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== ;8、一棵具有２５７个结点的完全二叉树，它的深度为 。9、设一棵完全二叉树具有 1000 个结点，则此完全二叉树有 个叶子结点，有 个度为 2 的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。10、图有 、 等存储结构，遍历图有 、 等方法。11、n 个顶点 e 条边的图采纳邻接矩阵存储，广度优先遍历算法的时间复杂度为 ；若采纳邻接表存储，该算法的时间复杂度为 。12、用 Dijkstra 算法求某一顶点到其余各顶点间的最短路径是按路径长度 的次序来得到最短路径的。13、假设在有序线性表 a[20]上进行折半查找，则比较一次查找成功的结点数为 1；比较两次查找成功的结点数为 ；比较四次查找成功的结点数为 ；平均查找长度为 。14、在各种查找方法中，平均查找长度与结点个数 n 无关的查找方法是 。大多数排序算法都有两个基本的操作： 和 。15、在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第 7 个记录 60 插入到有序表时，为寻找插入位置至少需比较 次。16、在插入和选择排序中，若初始数据基本正序，则选用 ；若初始数据基本反序，则选用 。17、对于 n 个记录的集合进行归并排序，所需要的平均时间是 ，所需要的附加空间是 。18、对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为 。二、选择题（18 小题，20 个选项，...
