2022年数据结构概论资料 .pdf

《2022年数据结构概论资料 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构概论资料 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、福建师范大学试卷纸第 1 页 共 7 页数据结构概论考核题一、单项选择题 ( 每小题 2 分，共 30 分) 1. 下列编码中属前缀码的是( A ) A.1,01,000,001 B.1,01,011,010 C.0,10,110,11 D.0,1,00,11 2. 设栈 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 3. 在具有 n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( B ) A.O(1) B.O

2、(n) C.O(nlogn) D.O(n2) 4. 要表示省，市，区，街道的有关数据及其关系，选择( B )比较合适。 A. 线性结构 B.树结构 C. 图结构 D.集合结构5. 链栈与顺序栈相比，比较明显的优点是( D ) A. 插入操作更加方便 B.删除操作更加方便 C. 不会出现下溢的情况 D.不会出现上溢的情况6. 二叉树中第5 层上的结点个数最多为( C ) A.8 B.15 C.16 D.32 7. 在表长为的链表中进行线性查找，查找成功时，它的平均查找长度为( B ) A.ASL=n B.ASL=(n+1)/2 C.ASL=n+1 D.ASLlog2(n+1)-1 8. 对 22

3、 个记录的有序表进行折半查找，当查找失败时，至少需要比较( B )次关键字。 A.3 B.4 C.5 D.6 9. 已知图的邻接表如下所示，根据算法，则从顶点0 出发按广度优先遍历的结点序列是( A ) A. 0 3 2 1 B. 0 1 2 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - 福建师范大学试卷纸第 2 页 共 7 页 C. 0 1 3 2 D.0 3 1 2 （第 9 题配图：数组的下标为0,1,2,3）10.

4、 对于哈希函数H(key)=key%13, 被称为同义词的关键字是( D ) A.35和 41 B.23和 39 C.15和 44 D.25和 51 11. 图的深度优先遍历类似于二叉树的( A ) A. 先序遍历 B.中序遍历 C. 后序遍历 D.层次遍历12. 下述几种排序方法中，稳定的排序算法是( A ) A. 直接插入排序 B.快速排序 C. 堆排序 D.希尔排序13. 依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为( C ) A. 希尔排序 B.冒泡排序 C. 插入排序 D.选择排序14. 二叉树是非线性数据结构，所以 ( A )

5、A. 它不能用顺序存储结构存储 B.它不能用链式存储结构存储 C. 顺序存储结构和链式存储结构都能存储 D.顺序存储结构和链式存储结构都不能使用15. 有 8 个结点的无向图最多有( B )条边。 A.14 B.28 C.56 D.112 二、填空题（每小题1 分，共 15 分）1 当问题的规模n 趋向无穷大时，算法执行时间T(n) 的数量级被称为算法的_时间复杂度 _。2 设数组aM(M 为最大空间个数) 作为循环队列Q的存储空间，front为队头指针 ( 指向第一个存名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整

6、理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - 福建师范大学试卷纸第 3 页 共 7 页放数据的位置) ，rear为队尾指针 ( 指向最后一个存放数据位置的下一个) ，则判定Q队列的队满条件是 _ front=rear _。3 若已知一棵二叉树的前序序列是BEFCGDH， 中序序列是FEBGCHD， 则它的后序序列必是_ FEGHDCB_。4 假设 S和 X分别表示进栈和出栈操作，由输入序列“ABC ” 得到输出序列 “BCA ” 的操作序列为SSXSXX ，则由“ a*b+c/d ”得到“ ab*cd/+ ”的操作序列为_ b，c， d ，a_。5

7、 在一棵度为3 的树中，度为2 的结点个数是1，度为 0 的结点个数是6，则度为 3 的结点个数是_2_。6 在数据的存放无规律而言的线性表中进行检索的最佳方法是_线性查找 _。7 n 个顶点 e 条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为_1_；若采用邻接表存储时，该算法的时间复杂度为_2_ 。8 在堆排序和快速排序中，若初始记录接近正序或反序，则选用_堆排序 _；若初始记录基本无序，则最好选用_快速排序 _。9 若要求一个稠密图G的最小生成树，最好用_普里姆 _算法来求解。10 一棵深度为6 的满二叉树有 _1_ 个分支结点和 _2_个叶子。11 在各种查找方法中，平均查找长

8、度与结点个数n 无关的查找方法是_散列表法 _。12 有向图 G用邻接矩阵存储，其第i 行的所有元素之和等于顶点i 的_出度 _。三、解答题 ( 每小题 8 分，共 40 分) 1. 用普里姆 (prim) 算法从右图中的顶点1 开始逐步构造最小生成树，要求画出构造的每一步。14562316621192618145119答：假设 N=(V,E)是一个具有n 个顶点的连通网，T=(U,TE) 是所求的最小生成树，其中U 是 T 的顶点集， TE 是 T 的边集。（1）初始 U=u0(u0 V),TE= ；（2）在所有 uU, vV-U 的边中选一条代价最小的边（u0，v0）并入集合 TE，同时将

9、 v0 并入 U；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - 福建师范大学试卷纸第 4 页 共 7 页（3）重复（ 2） ，直到 U=V 为止。此时， TE 中必含有n-1 条边，则T=（V，TE ）为 N 的最小生成树。2. 假设通信电文使用的字符集为a,b,c,d,e,f,g，若这些字符在电文中出现的频度分别为：3，35，13，15，20，5 和 9，分别求出这些字符的等长编码以及哈夫曼编码，并比较他们的编码长度。名师资

10、料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 福建师范大学试卷纸第 5 页 共 7 页3. 待排序的序列为：25,47,36,21,90,84,62,78,15,32。写出用（小根）堆排序的每一趟的结果。int main(int argc, char *argv) int array10 = 24, 17, 85, 13, 9, 54, 76, 45, 5, 63; int num = sizeof(array)/sizeof(in

11、t); 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, arrayi); if(i = num-1) printf(n); 4. 已知一棵树的前序序列为：abefcgdhijk，后序序列为：efbgcijkhda。画出这棵树。答：前序序列为：abefcgdhijk，后序序列为：efbgcijkhda 5

12、. 已知闭散列表的长度为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 与 (4)冲突 , 于是线性重新散列即查找7 后面的空槽 , 此时 8 为空, 因此将 79 放入 8（第九个位置）中(6) H(82) = 2 (7) H(51) = 3 a b c d e f g h z j k 名师资料总结 - -

13、-精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 福建师范大学试卷纸第 6 页 共 7 页(8) H(39) = 7 与（ 4）冲突 , 于是线性重新散列即查找7 后面的空槽 , 此时 8 已经有元素（ 5）,9为空 , 因此将 39 放入 9（第十个位置）中, 所以最终闭散列表的存储情况如下所示：位置：（0） （1） （2） （3） （4） （ 5） （6）（7） （8） （9）值： 16 25 82 51 空空 38 47 79 39。四、算法阅读

14、、设计( 共 5 分) 1 阅读下列函数algo, 并回答问题： (5 分) void algo(Queue *Q) Stack S; InitStack(&S); while (!QueueEmpty(Q) Push(&S, DeQueue(Q); while (! StackEmpty(&S) nQueue(Q,Pop(&S); (1) 假设队列q 中的元素为 (2,4,5,7,8),其中“ 2”为队头元素。写出执行函数调用algo(&q) 后的队列 q；(2) 简述算法algo 的功能。答: (1)87542 (2)队列倒置五、程序设计题（共10 分）1、已知 r 为一维数组，其中r0

15、到 rn-1为待排序的n 个元素，排序好的元素仍放在r0 到rn-1中，请写出对该数组进行非递归的直接插入排序算法，取名为insertsort(elemtype r,int n)。 (10分) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - 福建师范大学试卷纸第 7 页 共 7 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -