福建师范大学2020年2月课程考试《数据结构概论》作业考核试题(【答案】)

[复制链接]
查看44 | 回复0 | 2020-1-20 08:49:29 | 显示全部楼层 |阅读模式
数据结构概论期末考核试卷+ ~: R1 c: s4 e2 D- A1 P5 A
一、单项挑选题 (每小题2分,共30分)
+ y# N; X" w' {+ i8 \1.下列编码中属前缀码的是(  )# L2 z( p( U9 _* l
A.{1,01,000,001}        B.{1,01,011,010}
" [. ^5 x+ ?/ s* i. E0 G8 Z+ m, V- WC.{0,10,110,11}         D.{0,1,00,11}
9 s2 s9 j/ E7 Z$ O2. 设栈S和行列Q的初始状况为空,元素a,b,c,d,e,f顺次进栈,一个元素退栈后即进入行列Q,若6个元素的出队的序列是b,d,c,f,e,a,则栈S的容量至少应当是(  )6 V2 v/ F7 ^$ P  a" {$ [
A.6    B.4    C.3      D.2
: G+ ~" C4 ]! m4 G- l1 E3 x3.在具有n个结点的有序单链表中刺进一个新结点并使链表依然有序的时刻杂乱度是(  )
8 k1 U2 q7 S  Q: o% WA.O(1)          B.O(n), r4 ~1 `3 s, D& a' t( ^" h) `
C.O(nlogn)        D.O(n2)
/ f+ a9 S, v4 w. e7 p4.要表明省,市,区,大街的有关数据及其关系,挑选(  )对比适宜。, @9 A! v8 w1 h  [" {# ^4 R$ @: F6 x
A.线性结构          B.树结构
5 |4 ~9 A$ N3 a4 JC.图结构          D.调集结构
7 z, g% V: k4 o& G) w* M  B5.链栈与次序栈比较,对比显着的长处是(  )  ]! U/ H# z& [* U1 H3 M- Y0 o3 c
A.刺进操作愈加便利        B.删去操作愈加便利
' r% [2 \* c4 d1 q+ cC.不会呈现下溢的状况        D.不会呈现上溢的状况
$ X; `: o. x/ T/ j2 H6.二叉树中第5层上的结点个数最多为(  ); @1 ?, n: {. s0 ?" o8 W
A.8         B.15
$ ?3 Q" y5 T/ n$ C% u) m$ PC.16        D.32+ S6 |: }5 P# N: Z) K1 L% [! V
7.在表长为n的链表中进行线性查找,查找成功时,它的均匀查找长度为(  )
6 h; j+ H+ a7 `6 S+ VA.ASL=n         B.ASL=(n+1)/29 Y6 M9 {" c1 W$ @% l' w* H* L  f
C.ASL= +1      D.ASL≈log2(n+1)-1
) l- E! t  A4 A8 d* r# P+ X8.对22个记载的有序表进行减半查找,当查找失利时,至少需求对比(  )次关键词。6 b% V  ]  T! K: n# ?2 l/ I. E
A.3        B.4
5 J: y5 y# T0 T( t* n: J* |/ e" NC.5        D.6
2 V. `' K8 h& r- Y, h4 u# h5 c3 m3 K9.已知图的邻接表如下所示,依据算法,则从极点0动身按广度优先遍历的结点序列是(  )* X1 D0 v0 j( c# L5 h( q
A. 0 3 2 1        B. 0 1 2 3
8 N- Z9 n* n$ [5 s( c3 eC. 0 1 3 2        D.0 3 1 2
5 z6 [7 \3 d6 k8 m; X- b5 z
; S; @# L! g/ d" L(第9题配图:数组的下标为0,1,2,3)
5 E% P! t2 u' @) S10.关于哈希函数H(key)=key%13,被称为近义词的关键词是(  )" ^2 `3 y) a$ p2 s/ V+ \0 m$ e, m: _
A.35和41        B.23和39) i4 q$ a( W8 J/ V
C.15和44        D.25和51
7 l( J2 I+ v* N3 b2 V* k11.图的深度优先遍历相似于二叉树的(  )
" r7 r* v  p) p/ }3 p! y7 TA.先序遍历        B.中序遍历: k0 f/ I7 h5 w8 O2 h
C.后序遍历        D.层次遍历& O  s) Y* m$ B8 K2 a4 l' ^  K: O
12.下述几种排序方法中,安稳的排序算法是(  )
) {3 ^& z5 [, c2 O! H! E* A# i! FA.直接刺进排序      B.疾速排序" ]& c; D4 R2 e* U' t5 v
C.堆排序        D.希尔排序
5 f# ?, D' L+ `: ?% u0 X13.顺次取出元素与已排序序列(初始时为空)中的元素进行对比,将其放入已排序序列的正确方位上的方法,称为(  )
" L0 U( R- a8 @A.希尔排序         B.冒泡排序
* K* q0 Q6 u: [1 k+ zC.刺进排序         D.挑选排序
3 j! _5 v% O2 c, T. m! a14.二叉树对错线性数据结构,所以 (  )
! G6 z  c4 o$ T- q6 yA.它不能用次序存储结构存储    B.它不能用链式存储结构存储0 a2 z% Q9 J/ g  d$ P; b
C.次序存储结构和链式存储结构都能存储  D.次序存储结构和链式存储结构都不能运用6 S9 _( X+ y7 G5 l! J4 t* f
15.有8个结点的无向图最多有(  )条边。0 \- H# Z8 s: b
A.14         B.28
$ `8 S7 e* z+ ]6 x" n8 ~7 v6 w0 ]C.56         D.1129 ]! L* V" }% a( T
二、填空题(每小题1分,共15分)! f: w/ G2 `$ G9 C/ ~) f
1 当疑问的规划n趋向无量大时,算法履行时刻T(n)的数量级被称为算法的________。
. t/ X# e7 F5 q, F, i2 设数组a[M](M为最大空间个数)作为循环行列Q的存储空间,front为队头指针(指向榜首个寄存数据的方位),rear为队尾指针(指向最终一个寄存数据方位的下一个),则断定Q行列的队满条件是_____________。  H9 O( q3 I) s" G; l8 r# B! w  o
3 若已知一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列必是________。* V. k6 _5 `3 P. X- }
4假定S和X别离表明进栈和出栈操作,由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX,则由“a*b+c/d”得到“ab*cd/+”的操作序列为___________。
; D2 t7 I9 }0 Z* ^5 在一棵度为3的树中,度为2的结点个数是1,度为0的结点个数是6,则度为3的结点个数是________。
5 W; w) S/ a3 ~& G6 在数据的寄存无规律而言的线性表中进行检索的最好方法是____________。
( S( K% i9 G8 p* b5 Z5 W; i/ U- r0 ^7 n个极点e条边的图选用邻接矩阵存储,深度优先遍历算法的时刻杂乱度为_______________;若选用邻接表存储时,该算法的时刻杂乱度为______________ 。
" Z. {  ~  R6 P5 _8 在堆排序和疾速排序中,若初始记载挨近正序或反序,则选用______________;若初始记载根本无序,则最佳选用_______________。" ^  }. e: N# e1 b$ i0 B
9 若要求一个稠密图G的最小生成树,最佳用______________算法来求解。( G5 e' }! R7 j7 O! M: |' T& X
10 一棵深度为6的满二叉树有 ________________ 个分支结点和____________个叶子。
+ v# s/ v0 D* j11 在各种查找方法中,均匀查找长度与结点个数n无关的查找方法是_____________。( a! y$ q) |6 n0 Q
12 有向图G用邻接矩阵存储,其第i行的一切元素之和等于极点i的____________。& K' L. e0 t! b* H, B
三、回答题(每小题8分,共40分)) }9 Y! e8 _" n7 g' k
1. 用普里姆(prim)算法从右图中的极点1开端逐渐结构最小生成树,要求画出结构的每一步。
& B; S) W) l" {4 D7 z5 F1 ~8 @
, H1 }+ ^/ n  o' D4 g; g5 r2. 假定通讯电文运用的字符集为{a,b,c,d,e,f,g},若这些字符在电文中呈现的频度别离为:3,35,13,15,20,5和9,别离求出这些字符的等长编码以及哈夫曼编码,并对比他们的编码长度。
; J" q! ^8 v  T / V9 T! I! w# v  L; z, Z5 X
3. 待排序的序列为:25,47,36,21,90,84,62,78,15,32。写出用(小根)堆排序的每一趟的成果。
5 p% p7 x, ]) J" N, L4. 已知一棵树的前序序列为:abefcgdhijk,后序序列为:efbgcijkhda。画出这棵树。  ]8 I0 R" F# x
5.已知闭散列表的长度为10(散列地址空间为0..9),散列函数为H(K)=K%8,选用线性从头散列技术处理抵触,将下列一组数据{25,17,39,47,83,55,99,34}顺次刺进到散列表中,请画出散列表。+ F+ V# u4 |- {9 D3 u0 O+ x
四、算法阅览、设计(共5分). }) Z, }! V0 t
1 阅览下列函数algo,并答复疑问:(5分)3 n0 X- u  B( [+ f0 j
void algo(Queue *Q)
/ v, S" l. J- @/ I2 I{# B. ]0 m* G, `% d2 m( O
Stack S;
1 K; `/ w4 P, y; IInitStack(&S);) i' J/ Z: C. u
while (!QueueEmpty(Q))8 m$ C: G1 A9 i0 S7 G- f
  Push(&S, DeQueue(Q));
: A4 n% t4 z+ `- U, z* kwhile (! StackEmpty(&S))" v1 t. k$ }( g8 o( x) C
  EnQueue(Q,Pop(&S));5 I' n: ~3 q1 c* C8 T, D( ?1 F5 t
}
' `9 t( b" g: d9 x7 z(1)假定行列q中的元素为(2,4,5,7,8),其间“2”为队头元素。写出履行函数调用algo(&q)后的行列q;5 R- w. N# P4 S" r  Y2 s0 Q
(2)简述算法algo的功用。
1 w* V' Z# t4 u* J五、程序设计题(共10分)' e0 f' w/ V3 J. l
1、已知r[]为一维数组,其间r[0]到r[n-1]为待排序的n个元素,排序好的元素仍放在r[0]到r[n-1]中,请写出对该数组进行非递归的直接刺进排序算法,取名为insertsort(elemtype r[],int n)。(10分)




上一篇:福建师范大学2020年2月课程考试《网络管理与应用 》作业考核试题(【答案】)
下一篇:福建师范大学2020年2月课程考试《比较文化学》作业考核试题【答案】
奥鹏在线作业,离线作业,毕业论文,免费选题(包通过)。 联系QQ: 3326650399 439328128 联系微信:cs80188
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则