数据结构概论.docx

数据结构概论考核题一、单项选择题 (每小题 2 分，共 30 分) 下列编码中属前缀码的是( A ) A.{1,01,000,001} B.{1,01,011,010} C.{0,10,110,11} D.{0,1,00,11} 设栈S 和队列Q 的初始状态为空，元素a,b,c,d,e,f 依次进栈，一个元素退栈后即进入队列Q， 若 6 个元素的出队的序列是b,d,c,f,e,a，则栈S 的容量至少应当是( C ) A.6 B.4 C.3 D.2 在具有n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( B ) A.O(1) B.O(n) C.O(nlogn) D.O(n2) 要表示省，市，区，街道的有关数据及其关系，选择( B )比较合适。A.线性结构 B.树结构 C.图结构 D.集合结构 5.链栈与顺序栈相比，比较明显的优点是( D ) A.插入操作更加方便 B.删除操作更加方便 C.不会出现下溢的情况 D.不会出现上溢的情况 二叉树中第 5 层上的结点个数最多为( C ) A.8 B.15 C.16 D.32 在表长为ｎ的链表中进行线性查找，查找成功时，它的平均查找长度为( B ) A.ASL=n B.ASL=(n+1)/2 C.ASL= n +1 D.ASL≈log2(n+1)-1 对 22 个记录的有序表进行折半查找，当查找失败时，至少需要比较( B )次关键字。 A.3 B.4 C.5 D.6 已知图的邻接表如下所示，根据算法，则从顶点0 出发按广度优先遍历的结点序列是( A ) A. 0 3 2 1 B. 0 1 2 3 福建师范大学试卷纸 第 1 页 共 6 页 C. 0 1 3 2 D.0 3 1 2 （第 9 题配图：数组的下标为 0,1,2,3） 对于哈希函数H(key)=key%13,被称为同义词的关键字是( D ) A.35 和 41 B.23 和 39 C.15 和 44 D.25 和 51 图的深度优先遍历类似于二叉树的( A ) 先序遍历 B.中序遍历 C.后序遍历 D.层次遍历 下述几种排序方法中，稳定的排序算法是( A ) A.直接插入排序 B.快速排序 C.堆排序 D.希尔排序 依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为( C ) 希尔排序 B.冒泡排序 C.插入排序 D.选择排序 二叉树是非线性数据结构，所以 ( A ) 它不能用顺序存储结构存储 B.它不能用链式存储结构存储 C.顺序存储结构和链式存储结构都能存储 D.顺序存储结构和链式存储结构都不能使用 有 8 个结点的无向图最多有( B )条边。 A.14 B.28 C.56 D.112 二、填空题（每小题 1 分，共 15 分） 当问题的规模n 趋向无穷大时，算法执行时间T(n)的数量级被称为算法的 时间复杂度 。 设数组 a[M](M 为最大空间个数)作为循环队列 Q 的存储空间，front 为队头指针(指向第一个存 福建师范大学试卷纸 第 2 页 共 6 页 放数据的位置)，rear 为队尾指针(指向最后一个存放数据位置的下一个)，则判定 Q 队列的队满条件是 front==rear 。 若已知一棵二叉树的前序序列是BEFCGDH，中序序列是 FEBGCHD，则它的后序序列必是_ FEGHDCB_。 假设S 和X 分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为 b，c， d，a 。 在一棵度为 3 的树中，度为 2 的结点个数是 1，度为 0 的结点个数是 6，则度为 3 的结点个数是 2 。 在数据的存放无规律而言的线性表中进行检索的最佳方法是 线性查找 。 n 个顶点e 条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 1 ； 若采用邻接表存储时，该算法的时间复杂度为 2 。 在堆排序和快速排序中，若初始记录接近正序或反序，则选用 堆排序 ；若初始记录基本无序，则最好选用 快速排序 。 若要求一个稠密图G 的最小生成树，最好用 普里姆 算法来求解。 一棵深度为 6 的满二叉树有 1 个分支结点和 2 个叶子。 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列表法 。 有向图G 用邻接矩阵存储，其第i 行的所有元素之和等于顶点i 的 出度 。 三、解答题(每小题 8 分，共 40 分) 用普里姆(prim)算法从右图中的顶点 1 开始逐步构造最小生成树，要求画出构造的每一步。 1 16 2 5 21 19 14 6 9 3 26 11 6 5 4 18 答：假