《汇编选集福建师范大学2020年2月课程考试《数据结构概论》作业考核试题(答案)》由会员分享，可在线阅读，更多相关《汇编选集福建师范大学2020年2月课程考试《数据结构概论》作业考核试题(答案)（8页珍藏版）》请在金锄头文库上搜索。
1、汇编选集福建师范大学2020年2月课程考试数据结构概论作业考核试题(答案)7 j5 VN. c+ n, t5 # h数据结构概论期末考核试卷3 B& L) M9 R1 u% RR) n一、单项选择题 (每小题2分，共30分)1 x3 K: _! D. 9 3 y7 G1 j, r( ) C* q& 5 P+ W6 n: P1.下列编码中属前缀码的是( )* Y" M% r/ t4 X/ C: IA.1,01,000,001 B.1,01,011,010+ D* B: r; : pC.0,10,110,11 D.0,1,00,11& o8 & 3 a4
2、- k/ k2 e* Q# _( 2 _& p5 1 |+ |2 S5 T2. 设栈S和队列Q的初始状态为空，元素a,b,c,d,e,f依次进栈，一个元素退栈后即进入队列Q，若6个元素的出队的序列是b,d,c,f,e,a，则栈S的容量至少应当是( )/ c+ v# d1 r% L/ gA.6 B.4 C.3 D.29 x1 D7 K; - 6 | F0 _. c7 E* p" i% R" d3.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( )% A" 4 g5 _! n4 A.O(1) B.O(n)% X u$ P7 w?C.
3、O(nlogn) D.O(n2)* k7 d: . Y. g! L/ h% A9 p/ _1 - Q# o4.要表示省，市，区，街道的有关数据及其关系，选择( )比较合适。- O" O! z5 B7 b% Q# c8 EA.线性结构 B.树结构3 7 I0 h1 2 dC.图结构 D.集合结构 Q9 k ; k0 J! V% D7 F; dt* Q3 v& D" a, k/ m5.链栈与顺序栈相比，比较明显的优点是( )- + j: h, i; g( x: D6 uA.插入操作更加方便 B.删除操作更加方便- m) s; G5 a" / q) S0 l,
4、K. NC.不会出现下溢的情况 D.不会出现上溢的情况5 w# W( c. V& w0 J; k5 # N$ o" i- G. * E$ g3 w+ |6.二叉树中第5层上的结点个数最多为( )+ Z" O0 I W" u$ S5 7 V/ l3 k/ cA.8 B.15. 5 j1 G: i, I8 PC.16 D.32. l/ P5 a0 M! + i4 x9 M6 | C/ W& h$ H- 5 v+ g7.在表长为的链表中进行线性查找，查找成功时，它的平均查找长度为( )1 E8 n" t" I; sA.ASL=n B.
5、ASL=(n+1)/2, # f1 q& P1 x# m$ z2 Q0 Q. hC.ASL= +1 D.ASLlog2(n+1)-10 v) k5 v/ r1 a: ?4 V$ Z3 7 t* P8 XR. X1 c8.对22个记录的有序表进行折半查找，当查找失败时，至少需要比较( )次关键字。; K1 Y- x, EA.3 B.41 W6 E9 Z5 s2 w9 8 V- D9 DC.5 D.6- X9 c w& C6 V# U! V0 T( B1 S5 u$ P8 T# Z9.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是( )3 v$ d+ O
6、5 D4 o: X o( jA. 0 3 2 1 B. 0 1 2 3+ B3 v+ X6 d+ V; 8 P! DC. 0 1 3 2 D.0 3 1 2Q" i, D0 r4 S4 |- U3 y 9 m- z2 E, C: W （第9题配图：数组的下标为0,1,2,3）# g6 Q A m6 M8 D* I, S, f4 |7 h$ % J0 R, e10.对于哈希函数H(key)=key%13,被称为同义词的关键字是( )9 x1 r, m) h. _: B E$ Y6 6 A.35和41 B.23和39/ J5 r# T: v$ H6 f" r% ?C.15和44
7、 D.25和51& J3 q, r, z9 0 q6 S3 S, e3 . 4 g! % c/ g- k0 f6 X8 N11.图的深度优先遍历类似于二叉树的( )1 D$ ! E" r. X3 t; G% T N% KA.先序遍历 B.中序遍历# M/ a J9 A# d/ d- c: C.后序遍历 D.层次遍历! c9 t) d3 m0 m. E# L# + K5 G- m0 z; C) . L12.下述几种排序方法中，稳定的排序算法是( )4 M" I4 x+ E9 J1 S r( j S, hA.直接插入排序 B.快速排序+ 4 V/ K" i9
8、* M8 _! x6 9 L0 jC.堆排序 D.希尔排序, t( M7 H* J& e9 z: r8 M/ ?9 d; L$ d8 y, T: 7 D# 0 q" J13.依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为( )+ M3 b! Y3 $ kA" _7 Z. ?. . aA.希尔排序 B.冒泡排序g s) L! n8 " a) C.插入排序 D.选择排序3 t9 h# 4 g) t5 9 d6 : N+ w9 B# E9 y# v6 h14.二叉树是非线性数据结构，所以 ( )( S6 q2
9、K) x$ P; C0 7 i7 e$ BA.它不能用顺序存储结构存储 B.它不能用链式存储结构存储0 2 M; F1 N& a4 n. _! ?, S7 s0 O; JC.顺序存储结构和链式存储结构都能存储 D.顺序存储结构和链式存储结构都不能使用% L2 e9 Y6 G! - B% x# h& b4 . r# W2 C6 n15.有8个结点的无向图最多有( )条边。1 n6 d6 z+ P" V+ c: nA.14 B.28! n6 w/ |6 a8 U6 c% qC.56 D.1122 V- Bm3 K9 Y$ $ |/ H) V3 X) z- d. 1 L7
10、d* n/ ! 6 t% S. m9 N二、填空题（每小题1分，共15分）5 e* / L: 6 ! k" c4 a& K; O& J1 当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的_。, k1 f2 e- o1 b" A. L4 e2 设数组aM(M为最大空间个数)作为循环队列Q的存储空间，front为队头指针(指向第一个存放数据的位置)，rear为队尾指针(指向最后一个存放数据位置的下一个)，则判定Q队列的队满条件是_。5 m/ W; o5 r% J! I- T3 若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCH
11、D，则它的后序序列必是_。- v. F- Q# W1 P" v6 c _4假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为_。6 |! f+ j2 z$ b. o( H0 a9 K4 p! d, K2 V0 h( P5 在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是_。1 x( C: K6 W; X: X7 _" O9 y) M2 wA5 q# M7 k6 在数据的存放无规律而言的线性表中进行检索的最佳方法是_。( 1 i/ m
12、2 M; X. Z5 g( u- l! 7 L7 n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为_；若采用邻接表存储时，该算法的时间复杂度为_ 。3 |% Y+ H1 F+ B. h |# J4 c" h$ J+ 9 J. f& i s8 在堆排序和快速排序中，若初始记录接近正序或反序，则选用_；若初始记录基本无序，则最好选用_。. ?, _ |5 R& t- k; b( q. |+ , U" E/ X1 u% Q0 8 t0 W7 E9 若要求一个稠密图G的最小生成树，最好用_算法来求解。1 j2 Q# T- j# o4 e. g* .
13、 Y5 Z4 l" a4 o0 T% J10 一棵深度为6的满二叉树有 _ 个分支结点和_个叶子。- S# d* V1 n) k* O1 y" _( H: f, % Y4 V3 Q+ j/ v11 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是_。% I% 3 R! u ?( * o8 M5 U d4 3 ?: d6 X# g+ f12 有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的_。+ l& |1 , f5 F: E, ( f4 k6 M* j; |8 f# ( U1 V. p: v* 8 e- r9 g7 X" r"
14、 3 S( 8 三、解答题(每小题8分，共40分)% _4 v9 W8 3 z1. 用普里姆(prim)算法从右图中的顶点1开始逐步构造最小生成树，要求画出构造的每一步。& B- D3 t* J% L + E- ! q. ?r1 M# R m; Y: F9 c! O2. 假设通信电文使用的字符集为a,b,c,d,e,f,g，若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，分别求出这些字符的等长编码以及哈夫曼编码，并比较他们的编码长度。6 % Z/ _& |% N) 2 D z6 T! |! Q c8 i; C7 V" ?5 U) S& r 5 R% : S" H. |1 ; o7 Z3. 待排序的序列为：25,47,36,21,90,84,62,78,15,32。写出用（小根）堆排序的每一趟的结果。
