21春吉大《数据结构》在线作业一（答案）

skystar

[吉林大学]吉大《数据结构》在线作业一
试卷总分:100    得分:100
第1题,深度为6的二叉树最多有( )个结点。
A、64
B、63
C、329 `8 z: Y$ E5 o" r
D、313 x+ W" E& \. H: z4 }9 a5 v6 x
正确答案:4 L8 [" c$ I4 [0 x$ R  d8 e) u# f
- }2 G' l9 y5 E' p5 {' n6 Y  B
. v( @# `/ h2 v8 b
第2题,含n个顶点的连通图中的任意一条简单路径，其长度不可能超过( )。' y- o2 X2 Z& T
A、1: ^. x: U- p, P( X. s  U# i! f
B、n/2- f! ]+ O) o# U; h
C、n-1( f2 y5 c# N9 U: Y  N% X7 e
D、n
正确答案:
6 M2 ~: F3 \: T1 U3 k/ I

第3题,在 一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p,q之间插入s结点，这执行（ ）操作。* R' U- g" K4 x- _! a% t3 S4 \
A、s-next=p-next;p-next=s
B、q-next=s;s-next=p" C7 y. g7 U! Y4 g/ C9 g6 H6 d; L3 k
C、p-next=s-next;s-next=p;
D、p-next=s;s-next=q;' B" z- T) b- \% L
正确答案:, _( j0 e! c; d
! \/ A, B2 h( |

第4题,设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少( )个。
A、k+1" }/ C0 W: g/ l0 w
B、2k' h5 ~# H# r" X# O6 J
C、2k-1
D、2k+1
正确答案:


当文件局部有序或文件长度较小的情况下，最佳的排序方法是( )。
A、直接插入排序
B、直接选择排序
C、冒泡排序4 i, Y6 y: H7 R6 c* c" P  A
D、归并排序. y) m% ]1 {; @' G8 b7 n) F
正确答案:

7 H9 V" u$ h# L) Y- J
第6题,非空的循环单链表head的尾结点(由指针p所指)满足( )。
A、p-next=NULL
B、p=NULL0 h% B/ g! z1 K. u: _$ M
C、p-next=head
D、p=head
正确答案:
: M$ m% J2 N3 ?8 q, z' r
4 w  D+ A! e+ b0 v1 ]
第7题,在无向图中，所有顶点的度数之和是所有边数的( )倍。
A、0.50 {, x2 p, K) ?) Y& t8 J
B、1
C、2
D、4
正确答案:


第8题,通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）" `0 h. ^: n% {' h
A、数据元素具有同一特点1 K6 i8 o$ W/ \& [0 r/ ^! Z
B、不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致1 R8 {. X& e' P7 s7 ?7 I4 J
C、每个数据元素都一样4 ^, ^5 I' ~5 q; Q5 M$ i; p
D、数据元素所包含的数据项的个数要相等  K# L& \: F: t8 e  [* C
正确答案:" n( c( ]  g8 J8 j5 \# l


第9题,线性表是具有n个（ ）的有限序列5 T% \3 I' i" |9 H! R2 Y/ G9 B
A、表元素% E/ {; a6 B; ~  `  R! |2 G$ W
B、字符
C、数据元素
D、数据项. ]7 l% W  I5 J* \
正确答案:

从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较( )个结点。$ a( q, d$ X3 m7 z1 _
A、n
B、n/2
C、(n-1)/2
D、(n+1)/20 Y8 L5 l/ B# K0 j' X
正确答案:/ \6 q$ T( p/ S+ l* G
# t) a- O1 `0 H. x

第11题,类string中包含的串运算有（ ）
A、Find()5 F! R0 z  d) ~0 \' k
B、Substr()  J9 m2 }. @3 S! {
C、Insert()
D、Length()
正确答案:,B,C,D& p3 `, t& C; G1 A$ U2 }


数据结构指的是数据之间的关系，主要包含3部分的内容（ ）
A、数据的逻辑结构; K  z; G1 d* Q  Z$ X' `3 V, y/ v
B、数据的存储结构# [6 v" X" X3 R( L- R2 L
C、对数据施加的操作
D、算法
正确答案:,B,C
+ f5 A( E' f: y( N" U
, Q8 F( k- _# V! s
第13题,对线性表，可进行如下基本操作（ ）
A、随机存取& N. ]( @4 Q, u. p+ ]
B、插入
C、删除9 b' n9 c& R& M4 f* P
D、查找
正确答案:,B,C,D! k' o7 h% [+ X6 {; ]: I
* f2 i4 A5 A; q2 `
8 ~% f) B7 z4 t0 M" S5 N
第14题,递归过程中要保存的信息包括（ ）/ n! Z2 v+ O2 |5 x# X+ F
A、返回地址) J' q6 ^! D5 s8 r6 T6 P) W
B、本次调用中与形参结合的实参值, f$ d, q# a, M. Z+ C
C、本次递归调用中的局部变量值
D、执行结果
正确答案:,B,C6 I2 \$ Y) x& X6 Q0 n* l
图的存储结构有（）
A、邻接矩阵7 K5 B! t9 C  Q4 E* ~
B、邻接表: N  \  l) _, x) f4 p
C、数组表示法1 h9 F& q2 m1 d. J0 A4 ?% G
D、十字链表" E# B: c' h/ N3 M4 m+ ]' [! q
正确答案:,B,C,D" m' c% M: O" z7 S6 U


第16题,单链表中的头结点就是单链表的第一个结点。( )7 Q8 z7 C$ I- q$ J' k- ?1 P' l
A、错误
B、正确
正确答案:

6 c' N$ g% d( {( ?  @3 v
第17题,设栈的输入序列是1,2,3,4，则1,4,3,2不可能是其出栈序列
A、错误  B/ ^7 \  u  B% G& H) P
B、正确5 w9 |4 V! E0 S/ P; U' [9 {
正确答案:8 y, r1 T+ ~" S2 a$ w0 X' {. Q

5 ~# d3 W: @5 X: Z$ i" A
第18题,算法在发生非法操作时可以作出处理的特性称为健壮性
A、错误/ T8 F: s; A% B
B、正确& X4 m* w, ^9 J# J) J5 Y
正确答案:: W' V  l4 L; ~; v


第19题,在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终的排序算法是冒泡排序
A、错误
B、正确
正确答案:
算法和程序没有区别，所以在数据结构中二者是通用的。( )4 x9 i. J3 s( K5 B0 Z5 D1 ~
A、错误. I9 o8 z7 {1 T( A3 B4 a
B、正确% l$ L! T$ C6 v- y
正确答案:* d& |* U3 I2 t& Z, M3 ?( f
: d" x2 o+ @4 C5 p' K% x3 {
9 O; ?2 |9 d6 }4 I7 `" q
第21题,邻接多重表示法对于有向图和无向图的存储都适用
A、错误
B、正确
正确答案:
% H" m1 d3 @% ]  r* ]
& W3 I3 R( ]( n" f. ?/ N# M3 u
第22题,在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是归并排序3 D1 X! g5 j) P% W0 Y# ?# q7 u6 C
A、错误$ j) I, y- u; l
B、正确+ D1 ~5 e& j( G2 O7 ~
正确答案:/ T# d$ A5 m9 m' I: A* h


第23题,不是所有的AOV网都有一个拓朴序列
A、错误
B、正确5 ?4 ?' \% g. O# [
正确答案:" ?- m3 G; Q* d7 a


第24题,栈和队列都是限制取点的线性结构（）
A、错误8 }1 \3 p( X- n4 B; c
B、正确
正确答案:6 s$ g2 s# i( o( _! I
任何一棵二叉树中至少有一个结点的度为2。( )
A、错误* w' m. l, {2 }2 `/ R3 a! ^
B、正确
正确答案::