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

skystar

[吉林大学]吉大《数据结构》在线作业二
试卷总分:100    得分:100
第1题,链栈与顺序栈相比，有一个比较明显得优点是( )  `  j4 a; E3 b5 x
A、通常不会出现栈满的情况- |! U! P! k8 ^- F; I8 ]) x
B、通常不会出现栈空的情况4 H6 r, `" c: U6 `( D8 e
C、插入操作更加方便
D、删除操作更加方便/ Z+ X+ q( ^% r, d2 q
正确答案:; Q7 i! k; m  O


第2题,带头结点的单链表head为空的判断条件是()。
A、head=NULL2 j# ~# e3 A/ N. o. t- Y' S' Y% H
B、head-next=NULL
C、head-next=head
D、head!=NULL; a9 y1 o  c  @: ~
正确答案:
% h/ _6 A  j7 w* @
' s$ F( Y* V4 {' o
第3题,PUSH和POP命令常用于（ ）操作. i7 l; m* V4 l% L4 Q; d! A( C
A、队列8 h2 [/ S( g+ _# J  n8 t
B、数组
C、栈( [* W$ }: g8 m1 H. z) V6 k! N
D、记录
正确答案:# l& ?/ j+ r4 B5 S; R# P
( F8 ?- `3 |4 P$ M$ C/ k
# N  ]: M) k3 A! o) V2 x# Q
第4题,深度为6的二叉树最多有( )个结点。
A、64. z+ I+ L( s+ b& e8 `3 _. x
B、63
C、326 X/ Z( G( [7 w" P
D、315 U% \: ^0 P4 e" C) p9 O9 |! n
正确答案:% S2 \6 ]: c4 {- k' ]

在无向图中，所有顶点的度数之和是所有边数的( )倍。
A、0.56 `/ S% h: |3 d
B、1
C、2
D、4
正确答案 E7 o4 i4 I& Z; e' r1 M6 b2 F


第6题,线性表是具有n个（ ）的有限序列
A、表元素
B、字符
C、数据元素
D、数据项0 o3 l# h2 [1 ~5 @
正确答案:
. V$ ?# l6 O) u
- Z6 j2 B  G: a# V$ g. Q) m
第7题,含n个顶点的连通图中的任意一条简单路径，其长度不可能超过( )。
A、1
B、n/2- y) H: W; F: @
C、n-1
D、n
正确答案:


第8题,在单链表中，删除p所指结点的直接后继的操作是( )
A、p-next=p-next-next;
B、p=p-next;p-next=p-next-next;
C、p-next=p-next;& E1 h% {0 x, y' \
D、p=p-next-next;
正确答案:* S' W+ N' }( N; t7 y* c


第9题,设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少( )个。9 T. i+ \' G3 @
A、k+11 [7 u+ c3 c) P3 F0 c  c
B、2k$ P6 Z- G. G: V
C、2k-1. @$ V; ]3 @/ D2 x6 ?
D、2k+1
正确答案:

通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）9 {1 a5 `- J5 C$ o. F
A、数据元素具有同一特点
B、不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致3 t/ [7 Q/ e9 w. N
C、每个数据元素都一样' P, \) e0 q% B2 M
D、数据元素所包含的数据项的个数要相等
正确答案:! P5 W& ^, ?' ^7 p  i


第11题,图的存储结构有（）+ z* q& u! p2 o' M. `
A、邻接矩阵# t$ \) N' ]/ [; m4 u4 o( G3 n
B、邻接表
C、数组表示法- A0 }) F- D5 m4 s7 \. E% E" f
D、十字链表# G- \6 o. n8 k' _4 ~1 q. h- u1 h
正确答案:,B,C,D' b& t0 H! J! k7 x2 [) K
属于插入排序的排序方法有（）% s3 L1 O3 @4 P
A、直接插入排序" ^' \6 O% k0 l3 \6 _
B、对半插入排序
C、渐减增量排序
D、冒泡排序
正确答案:,B,C


第13题,类string中包含的串运算有（ ）
A、Find()
B、Substr()/ Y$ f. w* @! c3 {6 v% `# n/ a
C、Insert()
D、Length()
正确答案:,B,C,D3 [- }, y% L5 n3 O1 ?9 a5 J


第14题,以下属于操作受限的顺序表是（ ）! q% l+ ]( `5 h  A
A、栈
B、队列2 y6 ~* _3 d4 ^1 A2 H
C、单链表
D、树
正确答案:,B

二叉树的遍历方式有（）
A、先根遍历1 I1 A. @( H+ ^1 d% n) B
B、中根遍历3 S0 i' E! h0 R  }/ r
C、后根遍历, z+ H6 N* T6 M4 i7 i+ x$ N2 u5 z. \. p
D、深度遍历
正确答案:,B,C1 S9 ?2 d" ?  e

! h+ u" H* L: \4 C2 e5 q
第16题,对于前序遍历和中序遍历结果相同的二叉树为所有结点只有右孩子的二叉树. Y& w+ p; p3 X5 T$ D! @
A、错误
B、正确/ \# {' \" h2 N$ o; w
正确答案:

) }" a0 h+ y' m: r. o% Z1 ~
第17题,具有n（n0）个顶点的无向图最多含有n(n-1)/2条边' Z( W# Q6 z# X4 j3 {
A、错误  s# m: T# H" O1 Y; I
B、正确+ c8 q9 M# |8 L& z3 j
正确答案:

0 [8 F$ x8 Z9 @* l
第18题,字符串是一种线性表，其特殊性表现在它的数据元素是一个字符4 ^4 q; l" L, H  J& @1 e
A、错误
B、正确
正确答案:

$ X/ \' D* T: f% k
第19题,从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法称为插入排序
A、错误
B、正确
正确答案 M8 s2 o7 X! h! }0 Y; ^) f  E
在一颗非空二叉树中，叶子节点的总数比度为2的节点总数多1个$ L) W6 \; ?' e1 Y
A、错误
B、正确
正确答案:

* ?2 r/ `0 Q# ~- g( K& _# |# n
第21题,设栈的输入序列是1,2,3,4，则1,4,3,2不可能是其出栈序列
A、错误2 c4 n0 _1 c9 y6 @! c
B、正确
正确答案:  `  T  d; I$ {0 t" x/ ~8 E
* h9 ]2 j! U& {  [/ H) U! O; b

第22题,任何一棵二叉树中至少有一个结点的度为2。( )
A、错误
B、正确; _0 k8 y1 d5 D* `8 t
正确答案:

) n3 s2 S, ^) Y. [" i
第23题,由权值为9,2,5,7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度44
A、错误7 y3 |& j# l8 s/ i2 z
B、正确
正确答案:

* x9 Q5 @( |9 ]5 Z
第24题,在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终的排序算法是冒泡排序, r: Z7 l& L- Y
A、错误
B、正确
正确答案:

在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是归并排序+ b2 V* h! z3 B3 \0 Z; ?% U  p* @4 o
A、错误) b( B  E' L2 Z; Y- D8 u
B、正确+ }% h& ^7 B8 q1 o
正确答案: