20秋吉大《数据结构》在线作业二-1

admin

资料来源：谋学网（www.mouxue.com）-[吉林大学]吉大《数据结构》在线作业二
; g5 W5 Q7 e) G8 O1 b) B- R试卷总分:100    得分:100
" T* ^* r7 E: {3 ~4 m; x5 a" e第1题,从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较( )个结点。
9 R- R# r7 g( @/ @1 iA、n
B、n/2
' q% M# l# q7 G0 r$ A( n: JC、(n-1)/2
D、(n+1)/2
" I) X9 w% i* m8 k正确资料:


第2题,任何一颗二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置( )。
A、肯定发生变化
5 r- ^( k7 j- X- IB、有时发生变化
C、肯定不发生变化
8 A7 @. j- r* H: C: A. wD、无法确定
正确资料:
7 u4 A( i3 D, r' ~9 ]) e0 l! e
/ y( y3 z. t  f7 ]2 v. e
6 g- q+ b( W" l( K- a第3题,通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）
A、数据元素具有同一特点
B、不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
" k1 |, ?# C; @* g; R9 i. z( X  d4 NC、每个数据元素都一样
* A4 |5 R8 J$ f8 zD、数据元素所包含的数据项的个数要相等
正确资料:

- ]& @8 ?/ ^  Q% v
第4题,非空的循环单链表head的尾结点(由指针p所指)满足( )。
) r: _* e+ L' GA、p-next=NULL
B、p=NULL
' A! |# J: w* S# nC、p-next=head
/ W& x3 E2 }4 G) Y( ^& ZD、p=head
正确资料:
. L9 K6 g7 n7 v& Z+ k

& |! z  _6 V. \资料来源：谋学网（www.mouxue.com）,在具有n个单元的循环队列中，队满共有_______个元素。
( a  e6 S& E( x5 NA、n
B、n-1
# ]+ l2 R; g$ eC、n+1
D、n+2
2 ^( n/ v5 W# M* s% C7 l; ~+ ^9 R正确资料:


* }, x3 Z4 l- |* |, W. ?第6题,当文件局部有序或文件长度较小的情况下，最佳的排序方法是( )。
$ g& U# s+ X9 R( T8 jA、直接插入排序
+ }4 M9 q$ i6 }4 ?B、直接选择排序
C、冒泡排序
$ G% i" t1 {9 y8 X2 r7 ~D、归并排序
正确资料:
: C- x' p' D2 }' ^4 l1 N+ T

" g! [6 Z4 ?" I- t: T4 y第7题,深度为6的二叉树最多有( )个结点。
! L- `3 X  T( B9 n6 M6 p% q1 A8 EA、64
B、63
2 m6 K) i  z2 ~$ F# V$ PC、32
* e! P# [  e# g% x  f1 {: N) U5 |5 Z0 {D、31
: s/ o! M$ ?6 x正确资料:


第8题,链栈与顺序栈相比，有一个比较明显得优点是( )
3 s- ?5 A* f/ J0 c) f% ?2 e6 Q  BA、通常不会出现栈满的情况
: m& o- ^5 b+ S3 }/ {+ u- RB、通常不会出现栈空的情况
C、插入操作更加方便
D、删除操作更加方便
$ m7 a" ~* t! j" n/ G正确资料:
( \. G0 s  s: z. Q. p
. I% y% p0 y, }# t( @8 @6 u
' C% z  k2 f% |+ ?, K第9题,在排序过程中，键值比较的次数与初始序列的排列顺序无关的是()。
( b1 X; e, e4 y$ f9 ZA、直接插入排序和快速排序
5 K# l6 Y3 J2 m: P& wB、直接插入排序和归并排序
* K+ |9 ]& W6 V* V# VC、直接选择排序和归并排序
D、快速排序和归并排序和归并排序
正确资料:
% {! b; b: B0 |' u+ w1 z; `

) R7 L8 w) k6 _+ S/ d资料来源：谋学网（www.mouxue.com）,单链表中，增加头结点的目的是为了( )。
6 q( H# U5 ^+ C! g: C# aA、方便运算的实现
( f% Z! `6 ^& Z2 w3 ?- A$ C( a- _B、用于标识单链表
C、使单链表中至少有一个结点
D、用于标识起始结点的位置
6 Q( T. ~/ g" q% T正确资料:


第11题,递归过程中要保存的信息包括（ ）
$ N' T, f0 ]# N! B- s, WA、返回地址
5 }. g. U* m* d6 zB、本次调用中与形参结合的实参值
C、本次递归调用中的局部变量值
5 w+ S9 U1 R* b/ C) u/ p3 R# YD、执行结果
3 \( h9 C2 K) b正确资料:,B,C
. S. Z& }$ t7 C, I( O) K5 r
; N8 p* _% Y2 y: k: i( x
# N' \6 n4 g3 c9 X# m. _资料来源：谋学网（www.mouxue.com）,数据结构指的是数据之间的关系，主要包含3部分的内容（ ）
8 D. ^' G2 |! h" q( L% |8 n9 ZA、数据的逻辑结构
8 a3 y( O' V) d% ^7 h4 RB、数据的存储结构
C、对数据施加的操作
D、算法
! X  J' q7 ^3 Z$ W+ p正确资料:,B,C


第13题,属于插入排序的排序方法有（）
A、直接插入排序
8 L! g( P: e1 [5 x' KB、对半插入排序
C、渐减增量排序
. \! u1 j3 Q: k; cD、冒泡排序
正确资料:,B,C

# Q2 Z! e; I& h  {
5 J! y4 n4 l" [( u- R& f第14题,以下属于操作受限的顺序表是（ ）
A、栈
B、队列
C、单链表
D、树
正确资料:,B

4 o/ |1 J! q( @
资料来源：谋学网（www.mouxue.com）,二叉树的遍历方式有（）
0 {: ~1 |3 [: `% r/ TA、先根遍历
B、中根遍历
C、后根遍历
D、深度遍历
/ }# b- ]; m( A' A2 }9 q# C  O. T正确资料:,B,C


第16题,设有两个串p和q，求q在p中首次出现的位置的运算称作模式匹配
7 w' d$ ^0 l0 C9 ^6 W- }A、错误
B、正确
正确资料:


2 i4 S, E" E* q9 @  k: {! v/ ^: @第17题,任何一棵二叉树中至少有一个结点的度为2。( )
! o2 h5 q4 a, nA、错误
, e) E, i% S( ~) W) \( z& K+ DB、正确
正确资料:
: {# i$ G4 y5 d7 Z3 p

# \! C8 U% A2 S. i  K7 @# z7 q第18题,快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少
A、错误
% w7 c- j# n/ w& w/ w! SB、正确
: ]9 w  S4 G2 P8 q9 i正确资料:
" M4 J& q/ J2 D4 p$ M. N$ O
0 s  o% d, I# F, W5 x; }; d
第19题,字符串是一种线性表，其特殊性表现在它的数据元素是一个字符
$ \3 A1 }/ l* a" eA、错误
B、正确
正确资料:
7 j( R; D$ b* n% n. Z  C
+ \( B5 v+ ~, s5 U9 }. f
资料来源：谋学网（www.mouxue.com）,若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是归并排序
* T/ n0 U2 a- q6 Y. f8 H' aA、错误
B、正确
正确资料:

$ \  Q0 q& Y& [) ~  f7 V  l0 l: L
第21题,在一颗非空二叉树中，叶子节点的总数比度为2的节点总数多1个
/ y' C+ L$ T9 H, |& RA、错误
B、正确
正确资料:

/ o/ N! e- h+ M3 K# u: p
第22题,从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法称为插入排序
A、错误
$ D9 t9 `% E5 d" \+ u# ?" R8 zB、正确
7 u5 Z5 e* d& R7 A. f正确资料:

- [* ^$ s) \* Z* I$ \4 u5 F. h+ g
第23题,由权值为9,2,5,7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度44
A、错误
B、正确
% m/ G* L3 [- a正确资料:
- Z8 n' I" \, n

# m- `+ F& p- P第24题,邻接多重表示法对于有向图和无向图的存储都适用
8 c3 ~! i9 n; o: iA、错误
  Q7 w+ d- V. b3 e/ iB、正确
正确资料:
5 v* _+ [! C$ e

资料来源：谋学网（www.mouxue.com）,不是所有的AOV网都有一个拓朴序列
2 d1 S4 b9 s7 n/ u/ B" O2 |A、错误
! s2 J" L( d2 _! _  H& M4 U5 b4 k/ S/ bB、正确
- D/ h7 T, d, ?- [: ?4 B+ f正确资料:
5 C' [, z/ Q7 |/ m; |$ x! m- q+ L


. R, U: I- V' P' x
7 }% h. k6 S; ~$ c# ~& J
2 M3 h0 u; I/ A5 l; Z

2 @) J1 _4 d* e/ g+ w6 }6 t: \
4 G& v9 x% J# r5 y


0 b7 I6 v& j2 C& k) y1 t
. s" `/ L4 L8 A' b8 M
" p: M3 b; E3 w$ s" ~