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

skystar

[吉林大学]吉大《数据结构》在线作业一
试卷总分:100    得分:100
第1题,链栈与顺序栈相比，有一个比较明显得优点是( )
A、通常不会出现栈满的情况+ g1 d+ W9 m& R3 g
B、通常不会出现栈空的情况( S: j0 O; h" ~8 c- x
C、插入操作更加方便/ R8 n3 e: H6 \: U" s
D、删除操作更加方便1 _6 q7 J8 `, r, Z1 Z* I+ S
正确答案:% b: w$ W; L8 h% C" Z) N


第2题,从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较( )个结点。
A、n
B、n/2) v; u' B. B) g0 u( M( b4 G7 V+ M; E
C、(n-1)/2
D、(n+1)/2
正确答案:& k2 K6 `8 R6 L/ ?9 e3 Z7 l$ {


第3题,非空的循环单链表head的尾结点(由指针p所指)满足( )。9 U$ B1 i# G6 k/ c
A、p-next=NULL
B、p=NULL
C、p-next=head* C4 ], @! d6 |; S  r# s8 B% V
D、p=head
正确答案:
" Z, o0 E8 D4 s) C; \2 C

第4题,当文件局部有序或文件长度较小的情况下，最佳的排序方法是( )。1 U: \& u! H6 L* u! r
A、直接插入排序- d0 Y" t6 A( m1 j
B、直接选择排序  h) U. E# b* a0 c( x2 b" h
C、冒泡排序/ i  }% D& G( b. y
D、归并排序) r4 ]/ N+ M8 L9 o( e% e" M
正确答案:' G& m: A; x2 m( M9 s# v$ j& b1 B
: n  H, D2 p9 n. K
在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的( )。2 T9 o! j+ P( \% Q3 z
A、先根遍历: ?1 p8 h2 @! |9 b6 S0 I! \' B
B、中根遍历7 P. W( P2 ^- p3 m5 {% |
C、后根遍历
D、按层次遍历
正确答案:! h) f# g, d5 u! w" w0 W  M

' _: q  Z/ ]8 F+ B5 c
第6题,任何一颗二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置( )。
A、肯定发生变化
B、有时发生变化7 B9 E" N) s$ B: i
C、肯定不发生变化: {( r6 c: T1 x1 f
D、无法确定
正确答案:  @: }' s2 w6 ]. w; F( T
: }* D" l6 o5 g( l6 B1 o; T3 o

第7题,通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）# W0 Z7 u. r4 o3 r; p
A、数据元素具有同一特点
B、不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
C、每个数据元素都一样
D、数据元素所包含的数据项的个数要相等
正确答案:
. p& G$ g' n0 n% V6 U

第8题,在排序过程中，键值比较的次数与初始序列的排列顺序无关的是()。  {( X$ O5 E# @& |
A、直接插入排序和快速排序
B、直接插入排序和归并排序7 V* j# Y- V* N+ G- w9 S1 }
C、直接选择排序和归并排序
D、快速排序和归并排序和归并排序1 c- }) r5 |; D
正确答案:
/ c8 Q. v/ x4 A: E+ @) a6 C: i  ^
9 h" ]  K8 ^' I. d( }: e
第9题,含n个顶点的连通图中的任意一条简单路径，其长度不可能超过( )。
A、19 R2 \- n& C! n" l
B、n/2
C、n-1
D、n
正确答案:4 G5 H! J" T) X- {9 K. V; t
线性表是具有n个（ ）的有限序列  o5 D) G# \/ _1 f
A、表元素9 r  I& G. o( L* J! @/ V, a
B、字符' R5 {, R, @: a6 C: [( J2 d
C、数据元素; t/ G) F- @, C% [4 H3 {# v
D、数据项* V3 s# F$ Q, |. r
正确答案:


第11题,类string中包含的串运算有（ ）8 d" v. [& J8 J5 O. b
A、Find()  M1 w! O. `, N. r# x
B、Substr()( m0 L  J: z7 c
C、Insert()0 m4 B/ u  d% j
D、Length()
正确答案:,B,C,D3 [, T- `: {5 @9 m3 j  p

对线性表，可进行如下基本操作（ ）
A、随机存取' ]+ ?8 y* y, W: o( F
B、插入
C、删除$ {! U/ n. c4 l  J3 i
D、查找; k! B) ~7 U4 I  d1 \
正确答案:,B,C,D

4 z$ t7 w0 Y! v, {% k
第13题,属于插入排序的排序方法有（）
A、直接插入排序
B、对半插入排序
C、渐减增量排序
D、冒泡排序- E- D7 m1 k9 }) W( K2 F
正确答案:,B,C2 G5 q  b, N" S+ y) [0 [2 h+ A


第14题,二叉树的遍历方式有（）- p" f( Z" a5 f
A、先根遍历2 x5 E2 Q- Q6 y1 }7 A; d
B、中根遍历* z1 P& t) F# ~( ]0 |- W
C、后根遍历
D、深度遍历
正确答案:,B,C' U% L6 \4 i7 ?

对有序表的查找方式有以下几种（）1 r' `% k$ G) [; }
A、折半查找
B、斐波那契查找1 T' }  L5 l/ I1 b7 R3 i% M
C、插值查找/ I' Y$ H/ i! f" A" o" |! T
D、二叉树查找
正确答案:,B,C

$ h( Z* H( E5 {' X- `$ x9 q! I
第16题,单链表中的头结点就是单链表的第一个结点。( )
A、错误
B、正确# r8 X, F* a& ~1 P/ v
正确答案:8 L/ |4 t2 d  A) \  e+ k% @8 Q


第17题,若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是归并排序/ G( M9 [; W0 S' v. [1 B
A、错误7 S* Z+ V) d, J  k
B、正确
正确答案:. |5 D  v1 \8 t& |


第18题,字符串是一种线性表，其特殊性表现在它的数据元素是一个字符) i& I8 d$ D8 q" t9 |
A、错误
B、正确" x- x3 y8 |5 F7 y5 v: n0 E8 D
正确答案:4 U& {6 }$ g. a1 T/ d) A' A

6 a, P. q3 j5 J$ H
第19题,不是所有的AOV网都有一个拓朴序列) O5 m# D, L# K$ j) q9 y! S$ a
A、错误5 H6 S5 c3 [4 Q8 S6 I
B、正确
正确答案 J* y+ m/ q8 i7 b/ i2 _
具有n（n0）个顶点的无向图最多含有n(n-1)/2条边( [; c  |% U0 F* @
A、错误; @9 N6 k: e+ r) G$ `9 s* t
B、正确
正确答案:

5 H9 D& G6 z8 f% G
第21题,在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是归并排序
A、错误/ p* y0 g8 i+ L4 f0 u+ R3 c  M/ B
B、正确; e4 _) _) O7 O  g/ ]
正确答案:

7 b5 \" V5 U4 D1 l# o
第22题,设有两个串p和q，求q在p中首次出现的位置的运算称作模式匹配, R) i4 k& G3 ?$ b4 |- _
A、错误
B、正确
正确答案:! E; K# i/ T- W# f
) J& U4 l7 ~& j$ }% W$ Z
; D9 C7 I6 o4 u- {& R4 `
第23题,从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法称为插入排序; i# Z4 N& F7 o  i3 F" H& ~
A、错误
B、正确
正确答案:+ g. I  }' @6 @7 G6 W% u1 ~' I

( ?* E! X0 F+ n# z
第24题,对于前序遍历和中序遍历结果相同的二叉树为所有结点只有右孩子的二叉树
A、错误8 A8 `) z, A0 }7 D4 @: ~
B、正确- Q2 {$ d( v% s2 `5 p. f5 R
正确答案:

算法和程序没有区别，所以在数据结构中二者是通用的。( )5 D% x, S8 Z( t) k) ]  g& O
A、错误
B、正确
正确答案: