东北师范《数据结构》2022年春学期在线作业1答卷

admin

数据结构19春在线作业1-0005
试卷总分:100  得分:100
一、单选题 (共 20 道试题,共 60 分)
1.求顶点间的最短路径问题，考虑的是下面的哪一种图 ()。
A.无向图
3 q  W' \9 V( |B.有向图
C.带权的无向图
8 g5 a/ p* F0 w1 RD.带权的有向图
正确资料来自谋学网（www.mouxue.com）

6 k5 [1 j5 E1 D6 j; `2.一棵左子树为空的二叉树在前序线索化后，其中空的链域的个数是：( )。
8 o1 W9 i# O; x7 V! N2 m' bA.不确定
B.0
; z- w/ |: v; M) \C.1
! \5 y- S& U+ ~D.2
正确资料来自谋学网（www.mouxue.com）

3.ISAM是索引顺序存取方法，该方法是专为下面的哪一种设备设计的 ()。
6 D, R  |, |6 S" [8 AA.磁带
B.磁盘
C.光盘
D.外存储器
正确资料:
5 W; K4 j8 h( B% ^- }7 v( b1 ]
1 a3 H$ S: I; n- s4.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是 ()。
A.直接插入排序
1 B$ s) v7 o- ~9 {) mB.快速排序
C.直接选择排序
+ E% f% u  M5 M9 ZD.堆排序
5 w4 i: \+ @4 ?1 o4 h7 o正确资料:

5.在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是 ()。
A.O(log2n )
B.O( 1 )
C.O(n )
# G0 p# s& t$ bD.O(nlog2n )
正确资料:

4 K. i" c( a4 B& K3 ~: W. o1 g! M6.下面关于串的叙述中，哪一个是不正确的? ( )
A.串是字符的有限序列
4 x$ V' ]% Z8 @- v0 N' J: lB.空串是由空格构成的串
5 r7 R2 m6 U6 w0 g! SC.模式匹配是串的一种重要运算
D.串既可以采用顺序存储，也可以采用链式存储
正确资料:
! ?& d/ n* u, o% l2 X
' A& ]; `; e. ?  l% Q* k3 \9 r4 f7.在具有n个结点的完全二叉树中，若设根结点的编号为1，则编号为i(i>1)的结点的双亲结点的编号是 ( )。
A.2i
5 o. o; f; N7 d' e( GB.2i+1
C.?i/2?
: r; i) ?! n9 u+ Q8 O- W% HD.不存在
3 L! C0 x6 V  B$ w  }正确资料
  k( R5 @. s6 i9 ~! I& R7 L
* r/ V* X/ \/ v0 m; E8.n个结点的线索二叉树上含有的线索数为 ( )。
A.n-1
B.n
C.n +1
D.2n
正确资料
1 {' Q: W0 l7 {7 t; q2 d
9.用ISAM组织文件适合于 ()。
A.磁带
4 N' ]7 c0 S9 O2 B5 n: K* H+ }, lB.磁盘
C.光盘
D.外存储器
' V- C. `3 x: P* p) j) ~; D正确资料:

0 `$ D) }9 z  f4 E' s' o) S8 z10.下列哪项不是利用查找表中数据元素的关系进行查找的方法 ()。
A.有序表的查找
2 s) K4 @2 d' M7 x; ?, U6 F5 v# IB.二叉排序树的查找
7 t5 c1 ]8 i  b0 ~8 XC.AVL树
9 ^8 S6 T0 V. o1 i# r- \D.散列查找
正确资料来自谋学网（www.mouxue.com）

11.二叉树在中序线索化后，仍不能有效求解的问题是 ( )。
A.求指定结点的前序后继
$ v% K4 G9 i- O3 dB.求指定结点的中序前驱
C.求指定结点的中序后继
8 W. L+ M2 E3 O3 YD.求指定结点的后序后继
正确资料来自谋学网（www.mouxue.com）
# `- Q3 o" M$ s0 ]
- V. }) R  ?5 }6 N- c( [; D12.一个栈的入栈序列是a、b、c，则栈的不可能的输出序列是 ( )。
4 \  j% M$ k# F6 ?/ rA.acb
( j4 b1 z( c! |" B! E7 i6 w) rB.abc
C.bca
D.cab
正确资料来自谋学网（www.mouxue.com）
, M' z/ j2 D# e5 Q# |9 G" J  n
7 }8 X& Q  X2 C) U) R3 y3 P13.下面说法不正确的是 ()。
, T' F" c& `4 F% W) ^, v7 YA.广义表的表头总是一个广义表
) Q( y( f# S" n( m8 YB.广义表的表尾总是一个广义表
  K5 O2 f2 Q1 Q1 nC.广义表常采用链接存储结构
D.广义表可以是一个多层次的结构
正确资料:
- o- w" P3 X" p& O4 \9 X% W
  e; Z7 b4 I3 ~- ]14.在k叉树中，结点度数的最大值为 ( )。
A.k-1
B.k
C.k+1
; n" d' D2 d3 Q  |7 ^1 h! \/ y! QD.k*n
6 m, f% ~  N) B% f6 f" h正确资料:
4 @, t  ~# E! a9 o4 Q0 U
/ |# }% C7 `+ V9 _' g15.若X是中序线索二叉树中一个有左子女的结点，且X不为根，则X的中序前驱为 ( )。
. q& {. J# ]9 [( e. S5 t( vA.X的双亲
# u( c  u6 r. |; y  k/ aB.X的右子树中最左下的结点
C.X的左子树中最右下的结点
D.X的左子树中最右下的叶结点
正确资料
. ]8 L/ {7 a3 U' ~& [5 e
16.设有n个结点的AVL树，其平均查找长度为 ()。
* z+ B7 b+ o" H+ |2 ]) XA.Ο( 1 )
; ^/ w1 V$ V' L# u7 U. sB.Ο(log2n)
C.Ο(n)
D.Ο(nlog2n)
) k) q2 |  ^" c* r1 [6 |. H4 }* r正确资料:
  ~9 l, b+ e8 T: H  u
17.若由树转化得到的二叉树是非空的二叉树，则二叉树形状是 ( )。
A.根结点无右子树的二叉树
, \; ^0 j0 Y) q' g0 |. t( i6 ]B.根结点无左子树的二叉树
C.根结点可能有左子树和右子树
1 i* w+ S3 [, s9 n. u& g# o- E- vD.各结点只有一个子女的二叉树
2 O( c% z! A) K" Y* T- D' h. c正确资料:

9 f" D/ Z! s- M6 Y- d  j18.线性表若采用链式存储结构时，要求内存中可用存储单元的地址 ( )。
8 G8 Y* b, j0 o! i1 R, n; UA.必须是连续的
# j, R' v0 Q3 r* JB.部分地址必须是连续的
" ~5 D  l( ~  s+ c8 S+ jC.一定是不连续的
( E6 X; `. T( |* e, b7 s& ?, J  `D.连续或不连续都可以
正确资料来自谋学网（www.mouxue.com）
) k( i* H; C" |$ w" f4 G, x( S* `
6 A; r2 f! y% S: e5 `19.对于3个结点a、b、c，可构成不同的二叉树的棵数为 ( )。
A.24
B.28
C.30
; H& j6 f, _; E& P3 f: ^3 [D.32
$ u; A% l2 v" j" j+ t5 X) ?正确资料

20.树最适合用来表示 ( )。
8 `; `0 u! T7 U; B8 YA.有序数据元素
B.无序数据元素
C.元素之间具有分支层次关系的数据
; f' u8 L/ C1 P" u% C, ?, b' bD.元素之间无联系的数据
' E, ^2 s' [$ p: h" h1 V正确资料

二、资料来源：谋学网（www.mouxue.com） (共 20 道试题,共 40 分)
21.二叉树中序线索化后，不存在空指针域。
. S2 [9 |) }7 x( ]资料:错误
: Y% j0 e2 n3 U
22.拓扑排序算法仅适用于有向无环图。
资料:错误

23.哈希法(散列法)的平均查找长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。
资料:正确

2 M/ ~5 Q2 ]4 f8 j/ C24.空串与空格串是相同的。
" ^& W' `9 U2 x5 [+ H; ~$ n# C资料:错误
# c! Q2 W  K' d3 T6 K8 P
8 z) u) N+ E& u: t25.数据对象是具有相同性质的数据元素的集合。
5 Z+ d; d* K, n' n+ j资料:正确
+ L5 x( @* U" k( w7 H
* I$ N' P7 j" z% @. x; |, s; \/ _: O26.倒排文件是对次关键字建立索引。
# b" Z$ n- }% K# O9 n: }资料:正确
; Y- U: }8 h- m; w4 q0 g" v
27.连通分量是无向图中的极大连通子图。
资料:正确

7 h+ g! M9 v1 `1 o; k28.二叉排序树删除一个结点后，仍是二叉排序树。
资料:正确
  W; q+ ^+ E7 u. J  O. L8 p9 j8 K
' y( {0 l: \2 i- L7 u" M! J29.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大
资料:错误
3 K1 c% c* k- o0 ?$ n# a# J6 h, h
  m4 Z4 j1 U! H  e30.需要借助于一个栈来实现DFS算法。
资料:正确

6 U1 I7 N+ S: X+ n31.任何一棵二叉树都可以不用栈实现前序线索二叉树的前序遍历。
资料:正确

32.二叉树是度为2的有序树。
资料:错误
$ U7 T8 e/ i8 J! V9 I
5 O  z, v# ]' }8 L. a/ X# ^33.数据结构的运算(操作)是定义在数据的逻辑结构之上的。
2 x! a& F* M( s! f7 }6 S8 p% e# x资料:正确

34.无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。
资料:错误

35.两个串相等的充分必要条件是两个串的长度相等且对应位置的字符相同。
资料:正确
2 [0 a6 E$ X2 O1 i1 d
- n  X  K% v% _9 i3 f8 l36.广义表的同级元素（直属于同一个表中的各元素）具有线性关系。
6 V" y( M; Q+ S资料:正确

, k  x& U2 |+ X- C37.折半插入排序所需比较次数与待排序记录的初始排列状态无关。
资料:正确
) M+ o. i/ ~4 v' n0 G+ M
: w; [# U, N  ?7 D7 ?38.对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。
资料:错误
- K7 G' P; ^0 G( p. Q& _( m
39.对无环有向图进行拓扑排序一定能够得到完整的拓扑序列。
6 h* U) J. Z" ?资料:正确

40.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。
资料:错误

+ n) W! V  C% F9 q- Y
7 }4 j2 i8 B: h% J+ q


& A/ v! d" N/ z% O0 h7 V& O

/ z7 ]! H/ Q) M0 D: k* N) ]


: V+ y  Z; z5 T- w
, n( i. K3 y. H: j0 ]) i1 \