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

skystar

[吉林大学]吉大《数据结构》在线作业二
试卷总分:100    得分:100
第1题,在 一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p,q之间插入s结点，这执行（ ）操作。5 J% Z' n* D$ A
A、s-next=p-next;p-next=s
B、q-next=s;s-next=p
C、p-next=s-next;s-next=p;1 v3 c* L  e2 j+ Y9 a( W$ h" [
D、p-next=s;s-next=q;
正确答案:
% [; J) z5 j2 {9 O9 s- T
+ R# A- F+ }2 f3 Z, j& W
第2题,在数据结构中，逻辑上数据结构可分为：（ ）2 y+ i' U; m$ A$ }& X% j
A、动态结构和静态结构
B、线性结构和非线性结构
C、紧凑结构和非紧凑结构
D、内部结构和外部结构
正确答案 |, z9 e% c; W7 X5 i6 G  B


第3题,任何一颗二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置( )。0 D+ l0 B  s6 ^% d! X
A、肯定发生变化" u+ j- n* r+ k. t6 C" u
B、有时发生变化! M" e1 Z; e! |9 t" C6 n  q1 [
C、肯定不发生变化; s: _: O5 b2 Y% r! Q7 R3 ~- J
D、无法确定
正确答案:
+ [! J2 a, i' d# D

第4题,含n个顶点的连通图中的任意一条简单路径，其长度不可能超过( )。; ]4 b: X1 p/ H* Y; `8 u0 d
A、16 _6 `! p2 j, H  K6 Q8 M2 X1 R
B、n/23 F0 Z+ j- ?' Q3 N: l( U# Q, S
C、n-1
D、n* L7 a' f- ~- p' d. h+ O
正确答案:

在无向图中，所有顶点的度数之和是所有边数的( )倍。  ~0 O6 j( p/ f
A、0.5
B、15 n2 }" [) I3 Y' Y1 A5 F% P7 E
C、23 e6 D* r3 \% \6 Q
D、48 @4 B8 s. `$ P! S! L) a
正确答案 H6 M3 X$ u. k/ u/ a. g3 `

7 L% p; ]* Y% @
第6题,在排序过程中，键值比较的次数与初始序列的排列顺序无关的是()。
A、直接插入排序和快速排序: e# Q3 w4 d5 o7 _" s
B、直接插入排序和归并排序1 R* U& ~9 ^& a7 [" X; U5 @
C、直接选择排序和归并排序4 Q0 t4 J5 v8 ^- Z5 C8 F
D、快速排序和归并排序和归并排序1 K- w1 `1 J& H+ r% u7 Y" q# Z
正确答案:3 V( `2 J, b  v9 F, N0 e
9 N' [( @' f7 Y1 Q" \' Q$ z

第7题,从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较( )个结点。+ d9 ]# l! }5 {  w+ N( B
A、n5 U, [2 i* r1 p1 t* c: W: W
B、n/27 _' n! L( C/ r0 C% m0 \
C、(n-1)/25 M0 X+ r* w% H
D、(n+1)/2" j* L; u4 U$ C1 M2 h
正确答案:& {0 {- u4 {8 m) O: A4 ], E0 Z
( ^4 o# x3 m+ `5 O2 _% w

第8题,在具有n个单元的循环队列中，队满共有_______个元素。
A、n0 `9 n1 T  z. Z3 `8 k
B、n-1) }+ b( `% l2 t. a( n
C、n+1& J$ q4 s3 W. B( h9 z8 W
D、n+22 r$ K; v7 r& l2 U) C2 R
正确答案:: K3 w$ F" \) [% V6 F. |
. y3 {' y5 J; t! t

第9题,单链表中，增加头结点的目的是为了( )。
A、方便运算的实现
B、用于标识单链表+ ]& C* t# P( E5 j/ j
C、使单链表中至少有一个结点7 x" O+ k. A) g. n" p+ Z6 R! f' N
D、用于标识起始结点的位置
正确答案:
链栈与顺序栈相比，有一个比较明显得优点是( )
A、通常不会出现栈满的情况
B、通常不会出现栈空的情况
C、插入操作更加方便/ I2 z* V2 ?7 |. I  D, a, e
D、删除操作更加方便- x; e, c7 d) v" S8 i
正确答案:" W6 b) N  H; P# ^$ e* F& \9 L& `


第11题,二叉树的遍历方式有（）
A、先根遍历1 R% u+ ~" _5 |: D3 `! ^6 n& a
B、中根遍历
C、后根遍历
D、深度遍历" z( c2 m) ~. ?- e
正确答案:,B,C& w2 [; Y( |: \0 U1 H# {4 u

数据结构指的是数据之间的关系，主要包含3部分的内容（ ）5 k% L- A. w* O9 O( }! n  y
A、数据的逻辑结构
B、数据的存储结构6 ~( o& Q: z0 [: s1 `
C、对数据施加的操作
D、算法$ [0 W* @  Z/ B6 y  |! }) P
正确答案:,B,C& L9 [- K  |- l+ x8 V

+ h9 u. p' x: j! T# F* o
第13题,对线性表，可进行如下基本操作（ ）; f. |& M* t0 m# z. Z( x! n
A、随机存取
B、插入  J$ n# ^! w/ Q% S+ Z
C、删除
D、查找' a  u: c) H2 \1 Q
正确答案:,B,C,D


第14题,以下属于操作受限的顺序表是（ ）& ]2 d. ]7 E, V. H: g
A、栈/ X1 K, {, A. `, z* S3 L
B、队列
C、单链表
D、树# \6 y0 @( |# F# @$ W
正确答案:,B% c( ]1 }, a2 r9 Y) Z
一个好的算法应具备以下性质（ ）; n0 R3 n& N, C8 ]1 b" Z  I+ B: H
A、正确性
B、可读性
C、稳健性1 ~( n, p9 C* G% n  N/ ^  P
D、有穷性
正确答案:,B,C,D9 F& I6 U& E( `' B. Q! s
# O) J" ]2 E2 `$ {! v1 N, F
7 O# @9 F0 i; s5 D' X' c! U
第16题,算法和程序没有区别，所以在数据结构中二者是通用的。( )* L, `3 S: M4 t
A、错误
B、正确
正确答案:
/ T" l1 R4 S% Z% ^7 X

第17题,算法在发生非法操作时可以作出处理的特性称为健壮性
A、错误5 m. t6 Z: H& N) b* b; x
B、正确5 ^  O* s; }* s& x' V  x( a8 n+ Z
正确答案:
! ^. Q8 {# G9 S  V

第18题,判断一个表达式中左右括号是否匹配，采用栈实现较为方便
A、错误
B、正确8 E7 n2 |/ I( [5 L( \+ @
正确答案:' T, X3 Y# R# h3 ]9 B! p

0 }& R/ M. f, L0 }- ]) o  B
第19题,栈和队列都是限制取点的线性结构（）
A、错误
B、正确
正确答案:* P' u5 D( `5 d

邻接多重表示法对于有向图和无向图的存储都适用
A、错误
B、正确
正确答案 F7 w/ c/ g8 o5 m* S- S

7 Z- M" `7 j7 O) u: L. M
第21题,对于前序遍历和中序遍历结果相同的二叉树为所有结点只有右孩子的二叉树0 @$ |- |% a- k5 f5 U7 b
A、错误# |! k- h$ L4 O$ t1 Z7 N+ J9 Z9 F
B、正确
正确答案:
) u" m. _7 g, l# a, W
  P! A6 U6 D$ _: C) [
第22题,字符串是一种线性表，其特殊性表现在它的数据元素是一个字符
A、错误
B、正确
正确答案:

7 s, C, {4 W* |  A# j0 R3 x; `
第23题,在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是归并排序- N4 F4 J6 ?5 Q# _# O$ ~, @+ H
A、错误8 K/ H3 k$ G/ h4 g! U9 i% E
B、正确8 Q! V' `; e* q, ~3 a8 L
正确答案:


第24题,Huffman树、平衡二叉树都是数据的逻辑结构+ P* O: g. l& `0 D! H6 G* q2 W% |
A、错误
B、正确
正确答案:
若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是归并排序
A、错误$ \" m3 R$ M7 ]/ y) Z
B、正确3 v; a( R) o$ y6 p6 d% }5 \& P
正确答案: