(完整版)数据结构概论

1、数据结构概论考核题一、单项选择题 (每小题 2 分，共 30 分)下列编码中属前缀码的( A)A.1,01,000,001B.1,01,011,010C.0,10,110,11D.0,1,00,11设栈S 和队列Q 的初始状态为空，元素a,b,c,d,e,f依次进栈，一个元素退栈后即进入队列若6个元素的出队的序列是b,d,c,f,e,a，则栈S的容量至少应当( C)A.6B.4C.3D.2在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度( BA.O(1)B.O(n)C.O(nlogn)要表示省，市，区，街道的有关数据及其关系，选(B比较合适A.线性结构树结构C.图结构集合

2、结构5.链栈与顺序栈相比，比较明显的优点是(D)A.插入操作更加方便B.删除操作更加方便C.不会出现下溢的情况D.不会出现上溢的情况二叉树中第5层上的结点个数最多( C)A.8B.15C.16D.32在表长为的链表中进行线性查找，查找成功时，它的平均查找长度(BA.ASL=nB.ASL=(n+1)/2C.ASL= n+1D.ASLlog2(n+1)-1对 22 个记录的有序表进行折半查找，当查找失败时，至少需要比(B次关键字。A.3B.4C.5D.6已知图的邻接表如下所示，根据算法，则从顶点0 出发按广度优先遍历的结点序列(A)A. 0 3 2 1B. 0 1 2 3福建师范大学试卷纸 第 1

3、 页 共 6 页C. 0 1 3 2D.0 3 1 2（第 9 题配图：数组的下标为 0,1,2,3）对于哈希函数H(key)=key%13,被称为同义词的关键字( D)A.35和41B.23和39C.15和44D.25和51图的深度优先遍历类似于二叉树( A)先序遍历中序遍历C.后序遍历层次遍历下述几种排序方法中，稳定的排序算法( AA.直接插入排序快速排序C.堆排序希尔排序依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确置上的方法，称( C)希尔排序冒泡排序C.插入排序选择排序二叉树是非线性数据结构，所以 (A )它不能用顺序存储结构存储它不能用链式存储结构

4、存储C.顺序存储结构和链式存储结构都能存储顺序存储结构和链式存储结构都不能使用有8个结点的无向图最多(B条边。A.14B.28C.56D.112二、填空题（每小题 1 分，共 15 分）当问题的规模n 趋向无穷大时，算法执行时间T(n)的数量级被称为算法时间复杂。aM(MQfront福建师范大学试卷纸 第 2 页 共 6 页放数据的位)，rear 为队尾指指向最后一个存放数据位置的下一)，则判定 Q 队列的满条件front=rear。若已知一棵二叉树的前序序列是BEFCGDFEBGCH_FEGHDCB。假设S和X分别表示进栈和出栈操作由输入序AB得到输出序BC的操作序列为则由“a*b+c/d”

5、得到“ab*cd/+”的操作序列b，c， d，a。321，063 2。在数据的存放无规律而言的线性表中进行检索的最佳方法线性查。n 个顶点e 条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度1若采用邻接表存储时，该算法的时间复杂度2。在堆排序和快速排序中，若初始记录接近正序或反序，则选堆排；若初始录基本无序，则最好选快速排。若要求一个稠密图G 的最小生成树，最好普里算法来求解。一棵深度为6的满二叉树有1个分支结点2个叶子。在各种查找方法中，平均查找长度与结点个数n 无关的查找方法散列表。有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的出。三、解答题(每小题 8 分，共 40 分

6、)(prim111625211914693261165418答：假设n 是所求的最小生成树，其中U 是T 点集，TE 是T 的边集。（1）初始U=u0(u0V),TE=；uU, vV-U v0 并入U；福建师范大学试卷纸 第 3 页 共 6 页重复2，直到U=V 为止。此时，TE 中必含有n-1 条边，则T=（V，TE）为N 的最小生成树。a,b,c,d,e,f,g，若这些字符在电文中出现的频度分别为：3， 35，13，15，20，5 和 9长度。福建师范大学试卷纸 第 4 页 共 6 页3. 待排序的序列为：25,47,36,21,90,84,62,78,15,32。写出用（小根）堆排序的每

7、一趟的结果。int main(int argc, char *argv) int array10 = 24, 17, 85, 13, 9, 54, 76, 45, 5, 63;int num = sizeof(array)/sizeof(int); for(int i = 0; i num-1; i+) for(int j = 0; j num - 1 - i; j+) if(arrayj arrayj+1) int tmp = arrayj; arrayj = arrayj+1; arrayj+1 = tmp;for(int i = 0; i num; i+) printf(%d, arra

8、yi);if(i = num-1) printf(n);efbgcijkhda答：前序序列为：abefcgdhijk，后序序列为：efbgcijkhdaabcdefghzjk已知闭散列表的长度为 10(散列地址空间为 0.9)，散列函数为H(K)=K%8，采用线性重新散列25,17,39,47,83,55,99,34列表。答：(1) H(25) = 1(2)H(16)=0(3)H(38)=6(4)H(47)=7(5)H(79)=7 与 (478798（第九个位置）(6) H(82) = 2(7) H(51) = 3福建师范大学试卷纸 第 5 页 共 6 页(8) H(39) = 7 与（4）冲突,于是线性重新散列即查找 7 后面的空槽,此时 8 已经有元素（5）,9 为空,因此将 39 放入 9（第十个位置）中,所以最终闭散列表的存储情况如下所示：（0（12（34（5） （7（89）值：16258251空空384779。四、算法阅读、设计(共 5 分)1 阅读下列函数algo,并回答问题：(5 分) void algo(Queue *Q)Stack S; InitStack(&S);while (!QueueEmpty(Q) Push(&S, while (! nQueue(Q,Pop(&S);假设队列 q 中的元素为(2,4,5,7,8)algo(&qq