东大19秋学期《数据结构Ⅱ》在线平时作业1（参考）

admin

【奥鹏】[东北大学]19秋学期《数据结构Ⅱ》在线平时作业1
试卷总分:100    得分:100
第1题,高度为5的完全二叉树中含有的结点数至少为
/ U3 [8 D; z/ l" D+ M* ^& n* pA、16
  F- x2 b* `' o4 IB、17
C、31
D、32
1 w$ M: z( C, Z9 M3 c! m正确资料:
7 r4 J4 V2 w0 z# V5 a3 o7 }

  b& R( e; I+ Q2 J8 U% i第2题,通常将链串的结点大小设置为大于1是为了
; l" C! R, x4 Y  @; V# BA、提高串匹配效率
B、提高存储密度
C、便于插入操作
8 d# b( B5 k2 ?2 ]5 z$ AD、便于删除操作
正确资料:
& s6 c$ B/ H) ?# H
; ~. z% A4 X' i$ ^) v; N
第3题,在VSAM文件的控制区间中，记录的存储方式为
A、无序顺序
B、有序顺序
, A5 }' x& \5 @* h/ UC、无序链接
6 a* q+ _7 T; YD、有序链接
0 |! Q* j+ O/ P' ?+ L  Q正确资料:

2 r, C5 G9 _) [" t- Y/ r  U
1 I) W# s# E/ n9 a1 o* z第4题,在一棵高度为k的满二叉树中，结点总数为
3 {; k# u" r: g1 tA、2k-1
$ z1 u2 `" [# `9 P; k6 S* W2 yB、2k
C、2k-1
8 p( G. d, ]( a- RD、?log2k?+1
. X% j+ x+ x. R* R) T7 j" ]正确资料:

; J& Z  a/ i% D% T( p
; }  E$ |( O8 f第5题,已知广义表的表头为a，表尾为(b,c)，则此广义表为
A、.(a,(b,c))
: v" D2 T2 N( r3 J0 }5 kB、.(a,b,c)
C、.((a),b,c)
7 b9 |9 z# O5 p1 iD、.((a,b,c))
正确资料:


第6题,已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为
4 A3 I; l0 m' JA、5
9 m4 ^& x" Y; H+ dB、8
C、11
) n0 _, J+ j4 w$ C- z/ ^D、18
正确资料:
/ \! s1 l& ?& [# r
: r4 a; U8 c/ f. P% e: ^1 M
第7题,如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为
9 V' S; D! U- x; fA、插入排序
B、归并排序
6 q5 q4 c5 {1 {6 H, \C、冒泡排序
D、堆排序
0 K; R7 P, B8 p) M" U6 `正确资料:
7 p5 r. k1 |9 Z

第8题,栈是一种操作受限的线性结构，其操作的主要特征是
A、先进先出
B、后进先出
. ?$ b* L7 o) \' |5 \# iC、进优于出
" ?2 Y* }6 }1 u7 aD、出优于进
正确资料:

, V* f6 P7 M1 T1 J
6 r/ _& ~+ `) r" k3 G7 E第9题,下面的叙述不正确的是
& ?0 z, a2 R  MA、线性表在链式存储时，查找第i个元素的时间同i的值成正比
3 E; ~, j) L$ m" t' [4 VB、线性表在链式存储时，查找第i个元素的时间同i的值无关
C、线性表在顺序存储时，查找第i个元素的时间同i 的值成反比
D、线性表在顺序存储时，查找第i个元素的时间同i的值无关
正确资料:
2 g/ A  N7 O9 ]: R- F( ?

第10题,n个顶点的有向完全图中含有向边的数目最多为
A、n-1
# \5 S) [: g( ?3 _/ _; q7 ^B、n
C、n(n-1)/2
5 i6 i  u2 ?+ \! X4 [D、n(n-1)
正确资料:
  q8 ~% D# v( H( |+ u3 E& I' Z) O
$ ?7 P/ S, ?% J5 v1 ^
第11题,采用ISAM或VSAM组织的文件是
' E8 n: S* m* i0 [A、索引非顺序文件
0 l6 i: {0 N3 m- JB、顺序文件
  t8 T5 u* x2 l4 `* k, sC、索引顺序文件
D、散列文件
正确资料:
  L! T5 b7 H" L+ F# f2 _  Y

% U2 o  R+ F. o: O9 h* w8 c5 e. q第12题,除第一层外，满二叉树中每一层结点个数是上一层结点个数的
) |  j# N2 k' qA、1/2倍
B、1倍
1 O1 o  Q$ o$ QC、2倍
! i0 j/ D  J! }5 k! Q. HD、3倍
- Q* M% o% U0 |: Z+ W! D正确资料:


: d% K! t  y) f7 U! O* M+ |第13题,如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是
1 y7 F8 J7 c0 h" Z9 AA、栈
- G) z1 Y8 P* |B、队列
C、树
5 H8 s+ S3 q. R& D( RD、图
. V3 a  \  L/ ]$ K正确资料:


5 z. v+ d4 \: Q, B0 a/ s# \第14题,若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为
6 j/ x. p& |- b9 T0 t# O. {A、n-1
8 \. j4 Z+ Y& W4 j- TB、?n/m?-1
C、é(n-1)/(m-1)ù
D、én/(m-1)ù-1
+ K6 ?- t' j# G正确资料:


第15题,已知广义表LS=((a，b，c)，(d，e，f))，运算head和tail函数取出元素e的运算是
$ P- K0 Z( b5 J" x! uA、head(tail(LS))
: q$ l" b  }7 Y7 \6 {B、tail(head(LS))
# t2 M: D* \7 ^# }C、head(tail(head(tail(LS))))
D、head(tail(tail(head(LS))))
# a5 d% [5 l% _& D8 H正确资料:


- C) a2 V+ M) m+ G; e第16题,算法的时间复杂度主要取决于
2 O3 W3 g' _1 DA、问题的规模
4 Q1 o+ c& k/ K/ RB、待处理数据的初态
C、难度
5 C% k# I9 q4 ^; L0 M: Z6 fD、A和B
4 n* L. c" Q( X$ |4 W. Y正确资料:


第17题,已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有
/ `8 z. S8 [/ ]+ M. M- e4 i2 J% DA、dacb
) J; X% Q- l4 L4 O0 B7 ^4 DB、cadb
C、bdac
" a1 U1 `3 N1 @0 `D、以上资料都不对
正确资料:

3 n. ~* c  A: r: T: l& A4 V7 T9 V
第18题,设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是
8 ?2 t) B# }! F' h# C& |A、A，B，C，D
# P" C" {4 @* I3 RB、D，C，B，A
1 P: j- R& X! M9 ]- y5 _C、A，C，D，B
D、D，A，B，C
3 F& H) b% u& L( o正确资料:
  D+ v9 g& z3 W! {
6 D* M* y  r& e2 z6 h7 E9 h1 B
第19题,假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为
, R" h+ r; d4 n8 RA、n-1
0 g; c; y: K! q8 B, ]B、n
C、n+l
, f1 R' p6 \! X! _D、n+2
正确资料:


第20题,n个顶点的强连通图中至少含有
) @$ d0 o1 K) H" xA、n-1条有向边
B、n条有向边
: y3 p( A; D! J" ^1 q6 UC、n(n-1)/2条有向边
D、n(n-1)条有向边
1 d8 E  ], h5 {& F0 i' y0 R正确资料:
9 N& N1 X1 L& |
$ [" B' }  \' R/ K: A- i
& O, J. ~) f  C* B' h& \, ^