[东北师范大学]《数据结构》19秋在线作业14(100分）

admin

【奥鹏】[东北师范大学]数据结构19秋在线作业1
6 g+ G* D2 j- Z- R) {; p试卷总分:100    得分:100
' t) V$ z/ d7 W) }! O* c第1题,算法的计算量的大小称为计算的（）。
3 h& d* K4 u9 p. v- m, qA、效率
B、复杂性
; r% ^( Y6 c! k. dC、现实性
# F1 }, V9 e" t) V; t. z. A2 rD、难度
9 @7 A9 s3 W! Y/ d5 h! D  R正确资料:

7 J8 t( b3 m% |
5 s. [: S# S+ c- s5 S2 [- A第2题,若对n阶对称矩阵A按行优先顺序将其下三角形的元素（包括主对角线上的所有元素）依次存放于一维数组B [1..n(n+1)/2 ] 中，则在B中确定aij ( i  j）的位置k的关系为 () 。
A、i*(i-1)/2+j
B、j*(j-1)/2+i
C、i*(i+1)/2+j
D、j*(j+1)/2+i
正确资料:

! f3 x) d7 O' R2 ]
$ ]& r! o/ O+ y# j第3题,设二维数组A[0..m-1][0..n-1]按行优先顺序存储且每个元素占c个单元，则元素A[i][j]的地址为 ()。
A、LOC(A[0][0]) + (j*m+i)*c
% G  A( i3 c0 k5 K- o" D* f* ~( BB、LOC(A[0][0]) + (i*n+j)*c
  V# F: W) U1 B; ?C、LOC(A[0][0]) + [(j-1)*m+i-1]*c
3 D+ U# @, n" _% A7 uD、LOC(A[0][0]) + [(i-1)*n+j-1]*c
/ b1 o' G! g3 y" A1 \# K! H1 Y% P正确资料:

' ~; E3 J& v& }$ t$ s. G# n$ m
第4题,( ) 的遍历仍需要栈的支持。
A、前序线索二叉树
5 o" v, t& C0 h; G; wB、中序线索二叉树
; {; `, x- T2 |- D3 X" YC、后序线索二叉树
1 d" ~3 T, r1 b5 z3 `D、前三种均需要
正确资料:


0 k0 }+ a0 E) J, p第5题,若X是中序线索二叉树中一个有右子女的结点，且X不为根，则X的中序后继为 ( )。
A、X的双亲
- j% n  j' L! H$ `+ C$ qB、X的右子树中最左下的结点
# G9 g# s' F$ x# b2 Y; X( r: A/ W8 @C、X的左子树中最右下的结点
' P% p. a9 c  g: D. d+ xD、X的右子树中最左下的叶结点
正确资料:
* z8 R6 }7 b% |1 C2 M
/ ~( n  v" h; Q0 `% ^
第6题,下面的排序方法中，辅助空间为O( n ) 的是 ()。
A、希尔排序
B、堆排序
C、选择排序
9 k8 S5 z, p3 [$ k- C; gD、归并排序
正确资料:


- {" l! }6 |* O+ J  P7 }6 f第7题,在下述几种排序方法中，辅助空间需要最多的是 ()。
) E& L: q" S5 h& ?# _% H5 E: mA、直接插入排序
B、快速排序
C、直接选择排序
D、归并排序
正确资料:

3 Z% w# \! O: T  y4 m2 I2 s
第8题,非线性结构的逻辑特征是一个结构可能有 ( )。
A、一个前驱和一个后继
B、多个前驱和一个后继
C、一个前驱和多个后继
5 h0 q3 t- G6 Q' ID、多个前驱和多个后继
正确资料:

, C2 T) ^; ?' p  [& @
# ]3 |6 n% H6 U0 e/ M+ U, }: M- J4 W第9题,用ISAM组织文件适合于 ()。
9 h4 }7 Q/ m, R# B% Z+ TA、磁带
4 V0 `8 u4 V- B" b: zB、磁盘
6 w/ k" Z+ G1 k$ ^C、光盘
D、外存储器
正确资料:

# ?( N6 p2 Q* X2 t
4 b& v5 @6 K9 q" \0 D第10题,设有n个结点的二叉排序树，对于成功的查找，最多的比较次数为()。
A、Ο( 1 )
B、Ο(log2n)
/ b  x( ]; u( e9 f- \C、Ο(n)
D、Ο(nlog2n)
/ b+ L' w. t' }! V/ p正确资料:
, `6 C6 i% }. t
  W+ I$ J0 i  c- \8 e6 s' L
- U0 e2 Z5 J% G' G8 k: \' w3 \/ m第11题,下列排序算法中，其中 () 是稳定的。
A、堆排序，起泡排序
' }3 U' s3 q# i2 ?0 g# `* n- R7 TB、快速排序，堆排序
/ T+ }* c, D. _' _C、归并排序，起泡排序
D、直接选择排序，归并排序
正确资料:
7 j* b; \2 L$ k  K& t
" L% W$ U7 Z. Y) v% e: @
第12题,在具有n个结点的完全二叉树中，若设根结点的编号为1，则编号为i(i1)的结点的双亲结点的编号是 ( )。
A、2i
# v( ^% i) X4 Z# A: W( b4 c( M5 UB、2i+1
C、?i/2?
6 y5 \- M: [2 L" FD、不存在
正确资料:
' q: M  F& Y- ~; ]% X* V" ^" c; O( P/ J

第13题,设有n个结点的AVL树，其平均查找长度为 ()。
A、Ο( 1 )
; J% Y+ X; V2 p# V: o  `B、Ο(log2n)
/ w8 |& ^' E. Z' GC、Ο(n)
5 ~  q$ q' y( ~D、Ο(nlog2n)
正确资料:


第14题,若一组记录的排序码为 { 46,79,56,38,40,84 }，则利用堆排序的方法建立的初始堆为 ( )。
A、79,46,56,38,40,84
B、84,79,56,38,40,46
5 R; }) z% b5 t$ @C、84,79,56,46,40,38
D、84,56,79,40,46,38
; P( R2 x! {1 c正确资料:

( Y4 F  M# L% S8 @! ?, U7 R
第15题,设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为100，每个元素占一个地址空间，则a 85的地址为 ()。
A、112
( @2 w8 y( U; I; P+ _5 IB、132
6 v7 p0 O5 |2 G% m. ~( w0 _5 r- MC、118
9 }- u. i$ f" P' b2 T" N1 cD、140
4 ]( y# P$ ^; i, m' s" {. O2 c% S正确资料:


第16题,串是一种特殊的线性表，其特殊性体现在 ( )。
, i0 B3 i# ?, P2 d' _) z8 j2 nA、可以顺序存储
% }, n0 q5 w8 I6 }/ l  PB、数据元素是一个字符
, C/ }5 ~& @0 R3 J1 O5 `C、可以链接存储
D、数据元素可以是多个字符
  T/ o" p5 X1 K6 k+ U8 j4 W" O- O正确资料:


8 t9 [# J9 Q" x% z9 n/ |6 w2 n第17题,顺序表中逻辑上相邻的结点其物理位置也 ( )。
A、一定相邻
- B8 c3 W% u7 B0 z4 S/ WB、不必相邻
4 @+ f; k) B5 c9 n8 \C、按某种规律排列
0 q. t  p" `) ?% u" YD、无要求
正确资料:
' c, l2 g6 f* S5 G8 S

第18题,静态链表中的指针表示的是()。
( [& I. a# r8 t# p* {' w& ^A、内存地址
B、数组下标
& `5 Z$ g* ?6 x0 pC、下一元素地址
3 s% ~8 O& L4 U1 _1 S( w$ QD、左、右子女地址
& c* o: o( s9 v) A& j1 Z5 S正确资料:
4 Q) Z# `2 a( o7 j/ ~

8 J4 E0 F' [2 X+ j/ ^第19题,引入线索二叉树的目的是 ( )。
A、加快查找结点的前驱或后继的速度
, W/ J: P# U; ~5 e) SB、为了能方便地找到双亲
C、为了能在二叉树中方便地进行插入与删除
D、使二叉树的遍历结果唯一
+ z0 g3 O! M2 k正确资料:

2 D3 l+ x! v/ K" b" A
- f9 Z7 q5 _, ^6 A0 L第20题,下列描述中正确的是 ( )。
: w) k8 w% I( }A、线性表的逻辑顺序与存储顺序总是一致的
$ K& @: e& E" e6 [# c7 v: mB、每种数据结构都具备查找、插入和删除三种基本运算
4 W! j+ \. a% D+ l5 {9 `7 dC、数据结构实质上包括逻辑结构和存储结构两方面的内容
D、选择合适的数据结构是解决应用问题的关键步骤
正确资料:

  A9 u7 I3 d& R
( q, d1 J5 h( W+ O3 ?第21题,数据结构的运算(操作)是定义在数据的逻辑结构之上的。
A、错误
7 a) f$ \& R* \0 J3 i5 |* l2 lB、正确
6 Z; Y" u# A9 v' `正确资料:
5 e" @3 v* D. U$ a' \" a2 W
4 N2 X  H0 T: s( c$ r
第22题,对于插入、删除运算来说，链接存储结构一定优于顺序存储结构。
A、错误
" r, [4 `  K0 D# P* W# V- u' [B、正确
正确资料:


: }$ c: {0 s$ R8 t2 W% t第23题,堆是满二叉树。
A、错误
B、正确
正确资料:


' H" P1 L0 \$ I& c第24题,树形结构中元素之间存在一对多的关系。
A、错误
B、正确
正确资料:
* x- a* ?( ~* f- H
7 N. L. i7 L0 ?# H6 z* y- D
第25题,在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。
) T8 B& p9 d4 j. b$ f3 fA、错误
B、正确
; p5 N, ?5 y. Z" G/ b9 Y正确资料:
0 \0 |, P$ x& a" Y8 y& ?9 P
" `4 p/ I5 J/ l! S2 p
7 M, b+ r6 ?3 |第26题,快速排序总比简单的排序方法快。
A、错误
7 }6 y4 ]2 N1 a1 h* b3 gB、正确
正确资料:
- b4 I) G  x+ d# k: P9 U

第27题,在图G的最小生成树T中，可能会有某条边的权值超过未选边的权值。
% J/ I  h* }8 {9 z4 r2 |4 `7 R/ vA、错误
% \& L% n8 E, a5 |9 uB、正确
; ?( k: N2 X- O; |正确资料:


3 {2 o; l* o2 K4 o& _$ I第28题,最佳二叉排序树是AVL树 ( 平衡二叉排序树 ) 。
A、错误
% M- F% G' v  n4 z+ SB、正确
正确资料:
( s1 Q$ y+ C' Y
# [9 E  |* `  d$ [: \. Q
/ B  n' h5 j7 V0 |第29题,无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。
A、错误
0 T0 ?% ]9 O/ @/ {) u; yB、正确
4 L& U$ v# \% \( @正确资料:
( l$ p6 N* y" u2 L; _  P  u

1 u6 t: G4 `. j, a; m第30题,N个结点的二叉排序树有多种，其中树的高度为最小的二叉排序树是最佳的。
A、错误
B、正确
4 ]. I- o3 _8 a0 B2 L$ J; [正确资料:

' t/ v, m& @: U
第31题,二叉树只能用二叉链表表示。
0 \3 o- Y, U3 s. T1 r! UA、错误
B、正确
正确资料:
+ c* f' j+ a0 M, _2 r# t2 V* X
7 x  |1 U' {# v; Z; u# R
# f. A- b- G& k* [+ \第32题,通常使用队列来处理函数或过程的调用。
A、错误
B、正确
正确资料:
& Q  B6 L7 s  _7 f* e) k9 `' ~  q$ c, o
; ?& p1 ~$ z. T+ w
第33题,广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。
6 h/ X4 P( T2 iA、错误
B、正确
# i* m$ B5 J) B& _  ~正确资料:
2 V0 H+ U% @: e  Z7 J

第34题,存放在磁盘、磁带上的文件，既可以是顺序文件，也可以是索引结构或其他结构类型的文件。
6 N+ Z: L  T1 n9 d! mA、错误
B、正确
% }- y; p$ R& E8 r) b正确资料:
, E5 H! Y# S. b1 Z+ ]3 f

9 x* q1 |0 z; t( S+ p) d第35题,在任何情况下，归并排序都比直接插入排序快。
A、错误
! \; q  v. x% M  b+ r: TB、正确
正确资料:
$ g' ]* S/ [" q$ Y5 @) Q

第36题,二叉树结点的前序遍历序列与后序遍历序列可以唯一地确定该棵二叉树。
A、错误
B、正确
& r+ [* T3 {0 R9 t& v正确资料:
1 ]9 W* y$ b% y5 ]
; X. e6 E, ^, C. F, h. n# u
第37题,堆排序是稳定的排序方法。
A、错误
* {$ N& a/ d$ B& rB、正确
3 L9 i0 v$ e  s3 }1 l7 I. k正确资料:


第38题,连通分量是无向图中的极大连通子图。
A、错误
B、正确
正确资料:
6 w" A& i  M) x! I. M/ `

第39题,哈夫曼树是带权 ( 外部 ) 路径长度最短的树，路径上权值较大的结点离根较近。
A、错误
B、正确
正确资料:
8 h0 Z( }, B4 F- T: n1 B! W

第40题,为了方便的插入和删除数据，可以使用双向链表来存放数据。
) W9 l' \/ \( N* B% O# T1 Y9 TA、错误
$ _! s# L" A" Y9 T* |; sB、正确
正确资料: