|
资料来源:谋学网(www.mouxue.com)-[东北大学]20春学期《数据结构Ⅱ》在线平时作业1
0 C" d- c3 @3 c" E7 Q* O3 t% i试卷总分:100 得分:100' P$ ^+ v! Z0 j7 H1 P6 o9 J
第1题,适宜进行批量处理的文件类型是
- ~) w$ x5 g9 q3 h0 Z' h' w# CA、顺序文件) {: H, y( h Z1 N- `
B、索引顺序文件
. g1 ]1 }. d6 `# pC、散列文件6 i8 J: D4 H0 p
D、多关键字文件
& E6 s/ t# s2 Y) e. h3 @% r正确资料:
* `5 m/ ?- d$ l% \" P6 x2 b9 n( i0 y
% }- d, z3 I+ w5 K- ~) E
9 V% P' I4 R5 A/ k/ H( T第2题,用有向无环图描述表达式(A+B)*((A+B)/A),至少需要顶点的数目为; m: t: b' k4 M! ]4 ?
A、5
5 z; {$ H" F c* Q+ t/ QB、6! y% Q# R# f* B
C、8
* k+ }7 i# ~0 v; E( W$ i/ o7 zD、9* Y7 \# i: D, m1 C N
正确资料: u8 S6 B% ~" a( {: N) x
$ n: s9 x7 P1 t- p
9 W! T9 r5 J2 _- Z% m
第3题,若在9阶B-树中插入关键字引起结点分裂,则该结点在插入前含有的关键字个数为
$ N0 [ g g- Z$ ]A、4
' M H1 a# @7 `* `1 h/ EB、5. q$ |1 Z' y9 N$ o" D
C、87 P4 W0 a+ E i# k- k; \. D; U
D、9
; K8 [. G7 I3 e. e7 `0 \) g0 u正确资料:
8 J" k7 X0 ^2 E8 F$ F
; v7 z' x" B- D, k3 Z9 l* Z3 |: y; m0 {0 h, I, j/ l w
第4题,假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中,其中根结点存放在BT[0],若BT[i]中的结点有左孩子,则左孩子存放在
! V$ k4 T: `! `0 S% b/ g; a9 AA、BT[i/2]' {' G5 C8 H+ Q# C. J) b
B、BT[2*i-1]; ]7 j7 n$ Y+ F3 F8 A* V
C、BT[2*i] B; @$ Y# ]- k1 ] b, p, t# i& V
D、BT[2*i+1]' e5 a% G3 I! ]) C( A1 |6 r+ {7 \" f
正确资料:5 V$ B3 O3 t4 U3 B% x U
, A9 H7 S. `1 r
& V, y& A' ~# H, Y& n
资料来源:谋学网(www.mouxue.com),下列陈述中正确的是) q- B' y0 G8 Y% j5 }7 B
A、二叉树是度为2的有序树% }6 T9 T) l( g
B、二叉树中结点只有一个孩子时无左右之分
* H$ Q3 ]4 Y8 O* ^# W* B wC、二叉树中必有度为2的结点
0 {+ } ?4 D( pD、二叉树中最多只有两棵子树,并且有左右之分
" I% L) A- K" h" @$ l' L3 {9 v- h% ~. P正确资料:
4 W# S8 z7 d+ b! G/ q" J" f# Y/ {( {6 W) T' ]+ I. v
) l2 E N( C9 P$ k5 ~. t2 _
第6题,设有一个顺序栈,6个元素1、2 、3、4、5、6依次入栈,如果6个元素出栈的顺序是2、3、4、6、5、1,则栈的容量至少应该是
' h0 J+ F4 l8 p7 {: y3 UA、2$ b5 t3 z$ e- o; z- l9 P" P' Y
B、3
, x8 l- X v- f: Z& E& cC、55 T7 T' `" U4 u. @7 `) g% X
D、6* _- m' o/ g p# T' [
正确资料:
- r$ K$ e; ^! f$ z; @$ z7 V( @% G' |- G. b- L6 ~
/ v) m6 z( Q$ V$ b: H6 j! J, D第7题,将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是; F* y- [, N( g/ l l( M9 m6 `
A、n7 z- B& D) n4 [
B、2n-1
, H/ o' M) `; Y$ w; n, C: dC、2n
3 d( ^& m0 T( Z; v' o) ]2 E( PD、n-1. r; K* F) g0 K' D8 Y+ k
正确资料:
6 u" b& W: z' w* [
6 L. B. f& X7 j8 _" A
# G; C. f4 u" L6 r第8题,栈和队列都是
/ P8 w8 P# C5 t" n4 u: {A、限制存取位置的线性结构
L; z z8 L" J- t0 [1 C* qB、顺序存储的线性结构: m: w4 i6 v3 b7 l, o
C、链式存储的线性结构7 S: X$ r: J. L4 {, f: |
D、限制存取位置的非线性结构
6 R) b6 @! r. B( n( n0 ^正确资料:) L) H& G# t$ O" @, z6 a! }: v
3 U* X8 B2 `# { w2 m7 R! Q, F9 U) N8 }3 r3 Z* r" j
第9题,带行表的三元组表是稀疏矩阵的一种
- g4 g7 b0 p( W' d L6 T( v" tA、顺序存储结构
% c! k, j8 h1 z2 y: e. F$ \& d5 T! d& UB、链式存储结构3 i. t- R; F- p9 T3 Y; f, m6 Z
C、索引存储结构( k$ Y7 @ ]+ g$ q
D、散列存储结构- D2 Z. ]' }$ h" [$ ~3 Q/ {
正确资料:
) c E; X2 c+ {
/ F8 R/ p& v3 o& T' O3 k: ~& x9 f Y' O# s
资料来源:谋学网(www.mouxue.com),若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为6 E% u$ |) c6 d; e8 X
A、O(0)
& O5 R P3 O$ f" k- A5 ZB、O(1)
* X, u/ Z( {& N8 j+ U( yC、O(n)$ ]! i }- T* V- W4 p6 n8 _
D、O(n2)
2 ~, S7 n. }& ]3 T正确资料:
& u- L; H3 E. ~5 {5 j# R! B; m+ {) T, ?! x1 ]8 Q+ B! G2 o: P* o
- h; Z3 V2 q' c, P1 L0 ^
第11题,下面说法错误的是 (1)算法原地工作的含义是指不需要任何额外的辅助空间 (2)在相同的规模n下,复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 (3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界 (4)同一个算法,实现语言的级别越高,执行效率就越低
! r) I8 y& Z p. `7 lA、(1)
; c5 }% j/ e! p) _& W5 d1 QB、(1),(2)
) d7 X; ]! w7 Q1 P$ i+ xC、(1),(4)8 `- L5 J7 M0 g. [ \# X2 L1 W% N) x
D、(3) B( X" j, t0 N& g9 p
正确资料:
: v% y9 d- [ S. f& P0 r! r4 m S# m! g- H/ R) f2 E, M# u4 k
# @2 g/ M+ c9 E X; a) T' b4 J/ \2 s资料来源:谋学网(www.mouxue.com),以下属于逻辑结构的是0 Y) M1 }" l/ x2 O
A、顺序表6 M ]3 J6 \- R2 L ?% U
B、哈希表/ v( P4 j' f" Q: h! s
C、有序表
9 w6 z, o; n2 g/ r* lD、单链表! d: k4 J* M/ F! p8 M7 u4 J
正确资料:
/ Q2 E s- ~; w$ g& }; l
2 a9 K3 Y# ` n& B$ }; f7 R9 a! a* {
第13题,ALV树是一种平衡的二叉排序树,树中任一结点的$ p/ p. P; I% v" H( ~+ b) B& o
A、左、右子树的高度均相同
- e) }$ j$ [$ s5 cB、左、右子树高度差的绝对值不超过1
" g1 X% E! G2 M8 P* A% b$ NC、左子树的高度均大于右子树的高度
. F7 w& s% f d/ @ P* u; AD、左子树的高度均小于右子树的高度
% X! r7 B0 e+ j3 A1 o3 i9 Z正确资料:7 S; Y; v& O* k- P$ E! F, b
2 M# D( v' ]" @2 Z$ `% g* l# ]6 X' ]9 a4 v
第14题,栈的两种常用存储结构分别为, C# H; t- s; N! \
A、顺序存储结构和链式存储结构
& z1 \+ I `# g2 t' L* n+ ^B、顺序存储结构和散列存储结构
q8 P# H7 r4 kC、链式存储结构和索引存储结构; S- p% K$ r: C$ }" v. s6 Q7 m+ l
D、链式存储结构和散列存储结构
& L4 T" [9 K4 N/ S正确资料:
' n. z. y( _- ^! S5 u) r$ P" Q, X# e; ?2 K$ D
& }, \. u3 |# E# l8 c3 w# o2 K
资料来源:谋学网(www.mouxue.com),在图采用邻接表存储时,求最小生成树的 Prim 算法的时间复杂度为! U: o- G) E7 c% p6 e) O
A、O(n)
* x' Y7 z3 T) I. m6 o0 qB、O(n+e)
3 d2 m5 e' L4 s, c5 C1 vC、O(n2)
# x6 u" y' d& g& w4 Q) l9 gD、O(n3)
. G( t: [' Z0 y# R/ z7 e正确资料:
, y) ^9 E* V& x1 e
( D' ^7 }1 U* a# {' t5 o) x: u6 @' i
$ c% |) G' x' h A第16题,当采用分快查找时,数据的组织方式为0 Q+ P3 U: e2 N5 w# c
A、数据分成若干块,每块内数据有序3 x: T7 `) }) V2 G, }6 S2 U
B、数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块
. I# f: @- T- o0 |; @- n" f# AC、数据分成若干块,每块内数据有序,每块内最大(或最小)的数据组成索引块
, ?0 I. f$ _ MD、数据分成若干块,每块(除最后一块外)中数据个数需相同0 i7 l* Z* R) h% l- k
正确资料:, W7 |5 u# H# _9 y( y1 `; `
+ M9 `4 F1 n. F$ I/ l, Y7 |
( L% d+ S( {. P \ |$ a第17题,倒排文件的主要优点是( Q* _/ T( D( s; H4 v/ g
A、便于进行插入和删除运算
; W/ k- }5 H5 D; {/ I% d$ PB、便于进行文件的恢复% b) t9 ]0 l% K% b6 N& u
C、便于进行多关键字查询
; V6 y) `" N; ` K/ kD、节省存储空间0 X7 R8 E8 H' f+ u" k
正确资料:
# Q; `* d5 b" \! Y
$ G- ~9 O8 v8 M! \' z& k
3 l$ i1 j- B: s3 R6 X第18题,引起循环队列队头位置发生变化的操作是
( `/ w7 ?, O3 T4 ^" f; eA、出队
. t+ y: b0 Q9 N* JB、入队# s! F- i6 j; x5 Y
C、取队头元素1 m& I$ o" b6 e. f1 g
D、取队尾元素
( j. K5 K; N/ n# \7 O3 w8 u正确资料:1 ?% C; V! @, [3 s4 k+ O$ \; l
; c! O$ t A0 Q1 j. M. p( y0 t) r7 {4 M9 \3 w( [# l) d& x
第19题,下面关于线性表的叙述中,错误的是* d) P* s- R6 e& w; P. v f
A、线性表采用顺序存储,必须占用一片连续的存储单元。
6 e; A5 _5 ]; y4 sB、线性表采用顺序存储,便于进行插入和删除操作。4 M4 o z8 S# D: O+ w/ }
C、线性表采用链接存储,不必占用一片连续的存储单元。
2 { t8 P( w/ R7 P1 _1 J1 _D、线性表采用链接存储,便于插入和删除操作。; j& e3 k0 D' q! d1 B- G/ u! T3 p
正确资料:6 e$ ~7 G7 n0 ?0 m U
0 D* V1 C8 V# A9 q( h. H$ g5 w" j$ k: K3 m
资料来源:谋学网(www.mouxue.com),在目标串T[0..n-1]=″xwxxyxy″中,对模式串P[0..m-1]=″xy″进行子串定位操作的结果是4 z* S2 `! Y D( o% I7 r
A、1
7 P; ]2 T! A* _% uB、2
p5 f5 a W: C; B' qC、3- B5 K f7 r0 q6 _+ N9 [4 ]7 l6 B4 h
D、5
9 A: u4 w3 P9 I' `+ Y正确资料:
* H9 t7 o7 ^$ Y( k+ k- o s4 w1 R7 c/ t6 V) ~+ N5 l
; r4 K( X/ b) ^( z8 C3 }! Z
- j% [% l0 w$ f% Z" o
7 E# I0 r) f7 q' M8 p$ u2 H
! L, ~7 d2 Q/ m' W
# |1 e) q, [' U2 H4 f9 h' J# _
( D2 y9 O: J2 T8 z" z; Y G. g) y7 j1 o0 P5 ?: H+ s) J
( h8 a- N0 X2 ?0 X+ D7 w
' O d2 l4 d( F2 p/ U
3 x2 z2 n R# A' R* @
9 S6 V; a* u) p+ o* q! e* S. A! K8 i- x: N- c3 v K2 f: R- {/ X
* [9 B# K$ T- }3 g |
|