[东北师范大学]《数据结构》20春在线作业2-2（资料100分）

admin

资料来源：谋学网（www.mouxue.com）-[东北师范大学]数据结构20春在线作业2
试卷总分:100    得分:100
第1题,判断线索二叉树中某结点p有右子女的条件是 ( )。
: C: x( ?  O: e' iA、p-rtag = = 0
3 g3 |2 S$ q, m: p. sB、p-rtag = = 1
6 O. W1 M5 l/ A+ s" l$ aC、p ! = NULL
D、p-lchild ! = NULL
正确资料:
* M$ s/ g" g# l$ N) o* C. n! \

第2题,采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 ()。
9 x- L8 R  a7 e' y6 A+ hA、n
8 ^# _# Q( L" _! K: x% b, d5 wB、(n-1)/2
C、n/2
0 m6 J# D3 i9 g- M$ [" W' z' d: {D、(n+1)/2
正确资料:


% \8 U3 ^4 Z/ r8 D* @第3题,用ISAM组织文件适合于 ()。
7 A3 x% e6 h5 b( y0 n: oA、磁带
B、磁盘
: P$ ]1 p* H, q; a: `) U5 @C、光盘
D、外存储器
. f' n, R, z% l3 ~正确资料:

: r' E% w& o" w" o  G# v  p% U
9 j; o+ ?/ ~: h9 W第4题,在k叉树中，无父母的结点称为 ( )。
A、根
B、叶
C、祖先
5 X( _; f6 m  g4 s& B, LD、子孙
正确资料:


7 s0 {; U, D- u, A7 r1 x$ D资料来源：谋学网（www.mouxue.com）,一棵左右子树均不空的二叉树在前序线索化后，其中空的链域的个数是：( )。
A、不确定
* W$ `* J4 {- b' Y! PB、0
. v3 R- X" J7 z4 p* n4 T+ |. o" QC、1
& e2 \  ?& S( k% ]4 Z0 k! ^D、2
# z7 w) c: _0 r% `! x正确资料:

# [  p3 r" l, n7 m( g( u4 T
9 K' \( y/ f; L4 g" R第6题,设二维数组A[0..m-1][0..n-1]按行优先顺序存储且每个元素占c个单元，则元素A[i][j]的地址为 ()。
A、LOC(A[0][0]) + (j*m+i)*c
! j# c% h. E% j5 `B、LOC(A[0][0]) + (i*n+j)*c
C、LOC(A[0][0]) + [(j-1)*m+i-1]*c
D、LOC(A[0][0]) + [(i-1)*n+j-1]*c
, b1 w9 o5 w6 {* ^8 n8 ~5 v正确资料:
: B, b/ u; i& u2 r0 ~, |; @

6 ]& l0 {# l! d2 M5 [第7题,下面关于串的叙述中，哪一个是不正确的? ( )
A、串是字符的有限序列
B、空串是由空格构成的串
C、模式匹配是串的一种重要运算
D、串既可以采用顺序存储，也可以采用链式存储
正确资料:


第8题,广义表运算式tail ( ( ( a , b ) , ( c , d ) ) ) 的操作结果是 ()。
9 e, N7 a; u! G! {& GA、( c , d )
' ~5 k7 ^: |; c: z# S- {; nB、c , d
5 E' P. ^9 [7 m7 }6 TC、( ( c , d ) )
- W4 v) C4 }' {, p* i! nD、d
  H* ?7 ~' `5 K( [正确资料:

  n& o  u( t* Q: E# k
第9题,在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行 ( )。
A、p-next = s; s-next = q;
+ p! @) H: Q: @7 q5 HB、s-next = p-next; p-next = s;
C、p-next = s-next; s-next = p;
D、q-next = s; s-next = p;
正确资料:
0 [* F% b3 T3 O  ]8 g' F3 s) |5 k
5 y- L! {/ V3 y2 U* P8 @
( F* h( G1 Z7 w6 t* v  h资料来源：谋学网（www.mouxue.com）,若有向图的邻接矩阵中，主对角线以下元素均为零，则该图的拓扑有序序列()。
A、存在
, n8 }- V! Y8 r3 z& E2 t1 YB、不存在
C、不一定存在
D、可能不存在
9 B9 h& g5 I+ [5 T正确资料:
- I! d  P, I9 A

第11题,下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是 ()。
. a! ?/ R1 t/ P+ F7 mA、直接插入排序
B、快速排序
C、直接选择排序
D、堆排序
' j( U3 b: ]' S: ]2 V正确资料:
' p. y6 P1 |8 F  o! T. {
5 R- @5 f. H9 r
% C5 }6 C! j! z5 H! n8 U, k资料来源：谋学网（www.mouxue.com）,设s1 = "abc" ，则strlen(s1) =  ( )。
A、0
0 C5 m0 M  G# d: L. a- LB、1
C、2
: U) f: h, q# ~& x* CD、3
正确资料:


6 ~. D& H2 ]5 e1 k第13题,B+ 树应用在 () 文件系统中。
A、ISAM
/ j' h! m2 b2 g" @B、VSAM
) ?% n) V1 f1 J3 Z- L/ g4 T3 ~. \C、顺序
D、散列
正确资料:


第14题,四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU,x)操作后，队头元素是 ( )。
A、U
! ^+ ]: b- X: r, ?3 H$ qB、V
4 |  ^/ e+ F' R; tC、X
D、Y
正确资料:


3 d  ^. B1 q/ d0 ?$ V* i* I! i资料来源：谋学网（www.mouxue.com）,串是一种特殊的线性表，其特殊性体现在 ( )。
A、可以顺序存储
B、数据元素是一个字符
# J3 U4 A' U9 U4 [* @4 Q; dC、可以链接存储
0 h& d% ?% I' h2 R! D8 eD、数据元素可以是多个字符
! t0 O9 h# W: W2 l5 E正确资料:


3 s; ?" _! b* V3 D) L7 W' o# T' W第16题,稀疏矩阵常用的压缩存储方法有两种，它们是 ()。
) [( d5 t( q( _A、二维数组和三维数组
! V/ }  v3 ?. C; l9 K" o) \B、三元组和散列
C、三元组和十字链表
$ b! T! a- C9 \, ^+ a6 P$ xD、散列和十字链表
% ~% E8 v  F! D; n8 M! z/ ^1 B正确资料:

! i) e. m2 ~% Z$ O
  M! g- A8 d7 |# q第17题,如果要求一个线性表既能较快地查找、又能适应动态变化的要求，则可采用的查找方法是 ()。
A、顺序查找
B、折半查找
' x2 M8 k4 K+ Q3 q! KC、分块查找
D、基于属性的查找
4 T- W. d, n. ]8 O正确资料:


第18题,下列描述中正确的是 ( )。
A、线性表的逻辑顺序与存储顺序总是一致的
8 h% ]# v9 s2 c% {2 n" _B、每种数据结构都具备查找、插入和删除三种基本运算
C、数据结构实质上包括逻辑结构和存储结构两方面的内容
( Y- e- P/ L- E7 \% CD、选择合适的数据结构是解决应用问题的关键步骤
正确资料:


8 ]: j# r  [" u6 P第19题,散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值 ()。
A、同等概率
# o# |  H# N, S" L2 dB、最大概率
C、最小概率
# t+ |( ?5 Z" a' i  PD、平均概率
正确资料:
! D* r. k2 Z1 r% T( `7 [

资料来源：谋学网（www.mouxue.com）,对于3个结点a、b、c，可构成不同的二叉树的棵数为 ( )。
A、24
B、28
C、30
9 ?4 o& ~) w% t4 xD、32
& Y; d0 H( k6 p+ e& O: z正确资料:
& F5 |  M: \3 Q- v  z
, P& I0 A* b; l
7 n" }& k5 B1 V, H# i第21题,二叉树中除叶结点外，任一结点X ，其左子树根结点的值小于该结点X的值；其右子树根结点的值大于等于该结点X的值，则此二叉树一定是二叉排序树。
. J1 b) |) S) v4 LA、错误
7 Y3 S3 B) [' q( l' IB、正确
正确资料:
5 u  S4 l; H, F# t

第22题,对无序表用折半查找比顺序查找快。
# y: ], ~# W1 g) s0 T- MA、错误
+ \( M4 B8 k' aB、正确
: |5 {/ I/ Q  S+ u' K) E正确资料:


第23题,最小生成树问题是构造带权连通图 ( 网 ) 的最小代价生成树。
A、错误
- _8 T- e) a. b. C6 r# R; E7 Y% jB、正确
正确资料:

) H/ s9 K' l9 X& m, ]
第24题,结构的存储密度定义为数据本身所占的存储量与整个结构所占的存储量之比。
  _  Z! ]" U+ g& G8 a& A+ o8 iA、错误
B、正确
正确资料:

% O& N0 `; U0 k& M& D- J) ^
: `' x4 @1 s/ f0 v0 R资料来源：谋学网（www.mouxue.com）,链接存储结构属静态存储方式。
$ D6 r3 a' Q- R$ |7 e, |A、错误
& }$ ~" ?8 N! N! r$ s# kB、正确
正确资料:

1 T8 d8 Y$ D8 F8 o  g" y
; n7 ~) I2 v( p+ @$ ~- R- C第26题,分块查找在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中的元素个数有关。
# e8 u1 K9 h9 TA、错误
6 L5 V1 Q; h% v" B9 R) i* S% iB、正确
正确资料:
; T2 Q( Z1 x  I# O% ?, ^4 r' b

% `6 y3 W8 Y8 Q  y5 ^3 u8 c5 y2 u第27题,链表与顺序存储结构相比，在链表中进行插入、删除操作的效率高。
5 M& {& \5 Z$ @2 h3 ^; @A、错误
B、正确
* E0 I' x/ z9 r8 K- l& M1 y3 k正确资料:
$ u: Y4 }, }- L5 p  x

0 q1 e+ w! P4 t; Y第28题,栈和队列都是限制存取点的线性结构。
# w4 l- g5 n$ u5 B! HA、错误
B、正确
正确资料:
, U- S3 o/ g. R2 v
( e8 A2 }( F3 ^3 J% T
第29题,数组是同类型值的集合。
A、错误
$ Y+ G6 X: b, l7 u9 x3 h0 TB、正确
7 l: L$ p: z, Y3 B! x正确资料:
( S% B0 P& a. P3 v5 d. x. m
6 }! a* @0 M9 I
- x- l8 u! p2 }. c6 V& m资料来源：谋学网（www.mouxue.com）,归并排序的辅助存储空间代价为O(1 )。
A、错误
B、正确
5 R$ h; q: j4 D% g正确资料:
$ j4 ]4 E2 C: F' y/ L) w
  C8 P, D  W2 J
. Y6 r( v! {4 }$ c, G- k第31题,在二叉树中插入结点，则此二叉树便不再是二叉树了。
A、错误
B、正确
: h2 b6 {3 u( s: H1 o* ^0 F3 L$ A正确资料:
+ J  ^2 w9 U1 f' ?4 _9 B- k  |
8 g7 ^6 }2 ]+ h. q3 G+ T
) i7 ]. J& f+ N4 ^7 s, G/ Q第32题,将森树转成二叉树，根结点没有右子树。
* I8 p5 F1 d; }8 X; gA、错误
+ e% `7 m( V, G7 I5 |* cB、正确
正确资料:


第33题,邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。
A、错误
B、正确
. c' p! p! D% A; T3 n, V正确资料:
9 r9 X2 L. ^' L! K! T! i2 q

5 L2 K" Y  z0 `  x* U第34题,健壮的算法不会因非法的输人数据而出现莫名其妙的状态。
* i/ F& F5 R- m0 I- g0 U# Q2 sA、错误
! K5 x1 c( z7 a! }$ a! }+ PB、正确
8 D5 d; j! J) Z6 Y正确资料:

6 P) b+ P$ {% I1 h8 q1 b" g
6 G  W) D/ e: W: K第35题,在指定结点之后插入新结点时，双链表比单链表更方便。
" T# E+ ^$ f5 ?) v8 hA、错误
( }8 A/ ?% v2 ?0 K0 [' ?) UB、正确
正确资料:


第36题,无向图的邻接矩阵可用一维数组存储。
0 V5 R( u( ~! Q) LA、错误
B、正确
正确资料:


第37题,若一个广义表的表头为空表，则此广义表亦为空表。
A、错误
B、正确
正确资料:
+ y7 X8 ^* i1 F$ Y

" k1 A0 f% ?2 F+ j- D( N* j; }2 A第38题,稀疏矩阵压缩存储后，必会失去随机存取功能。
A、错误
B、正确
6 G) i: ^  ?) u  U正确资料:
  r) ^# `5 D+ o- d7 `$ R& C) s5 {

第39题,程序一定是算法。
A、错误
5 _7 i" [5 N3 V$ V8 D/ z% j: L# AB、正确
正确资料:


7 Q" n6 J8 G+ H* k4 B9 `第40题,广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。
2 U" I" W! J& m, nA、错误
B、正确
8 a* H) k" Y3 q; L正确资料:



6 [! y# ]+ J2 B% O& K
0 y6 _4 z, w, s4 D9 j5 H& y
- P9 o9 j" D1 a; A

) M* K0 Q2 P+ I$ Z- g# t" M; ^& d


+ e* f% t8 [" n/ a1 m) u  g2 Q$ _
7 V' h, v+ ~* P3 @# V