22年春吉大《数据结构》在线作业一

admin

资料来源：谋学网（www.mouxue.com）数据结构-[吉林大学]吉大《数据结构》在线作业一
( U! W! t! g1 y. D# r试卷总分:100    得分:100
  @4 C, ?. I$ [% h3 H2 l第1题,在单链表中删除p所指结点的直接后继的操作是
& d$ {5 c$ f7 c6 h5 w5 R; c5 C9 aA、p-next=p-next-next;
B、p=p-next;p-next=p-next-next;
C、p-next=p-next;
2 l" c; H3 y6 `7 eD、p=p-next-next;
正确资料:谋学网

  e$ e' |7 M  l5 ?% I1 I* ~
第2题,单链表中增加头结点的目的是为了
: w: I) n1 H, n! c9 o/ aA、方便运算的实现
6 e& G" x: {8 I7 vB、用于标识单链表
C、使单链表中至少有一个结点
7 U" Z+ ~+ b& o, O0 `$ X1 wD、用于标识起始结点的位置
正确资料:谋学网
" v0 t6 F# J9 f9 b: l* P* U

第3题,任何一颗二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置
A、肯定发生变化
B、有时发生变化
C、肯定不发生变化
/ G8 i: w3 Z4 D: A& k) s5 j1 RD、无法确定
+ z- r9 J! v; [; \9 x: ~" O+ y正确资料:
. j8 \7 f* U5 [9 \0 D6 o. v$ y

第4题,在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的
% h; ]8 o6 l, W: x- U2 i6 mA、先根遍历
B、中根遍历
4 Q8 V( f$ i" Q, y1 O1 ~  _5 RC、后根遍历
/ v$ O; B9 d" P9 t6 Z/ t, ?D、按层次遍历
正确资料:谋学网

( c6 K) y1 M. [7 f; R1 B4 X' A
" [' ]+ \$ F1 X资料来源：谋学网（www.mouxue.com）,非空的循环单链表head的尾结点由指针p所指满足
A、p-next=NULL
! _% ]7 y4 r2 \9 m( dB、p=NULL
! c1 h* T2 V6 wC、p-next=head
4 \# K: x$ R5 h; U4 w" Y: ^D、p=head
6 e% \( Y# N  p' ^# L4 b: ~2 \% i正确资料:


第6题,在具有n个单元的循环队列中队满共有个元素
A、n
, v- P' p" X$ `2 KB、n-1
# A% V, {$ f, R' D+ mC、n+1
' Q  R7 B/ r' |5 b, _D、n+2
  F; Z* i/ b. O, A% G" D7 o- C正确资料:


4 m) v4 N! W# s' h6 t& H; f* A3 N- q/ g第7题,深度为6的二叉树最多有个结点
# a1 H+ }) S% @A、64
B、63
; A& h) o# c* @, t+ d# {C、32
D、31
9 U& Z. H! p3 O' x7 N正确资料:

' _" P1 ^" }0 B7 D7 y  j- t1 q
第8题,带头结点的单链表head为空的判断条件是
2 S, A8 o% o6 E2 w# ZA、head=NULL
7 U, Y$ }( t; o  z' ~5 \B、head-next=NULL
C、head-next=head
/ ]* [% m/ @* s( Y/ _. o, OD、head!=NULL
正确资料:
  m" |- D7 C1 f9 y6 D% T. a

. B$ m* F, F4 d第9题,含n个顶点的连通图中的任意一条简单路径其长度不可能超过
1 E) T! q) l6 R) ^A、1
5 g% Y/ W, B+ ]! p6 _B、n/2
C、n-1
! S9 d% X5 M9 g7 N; Z8 V4 `D、n
正确资料:
4 J/ S8 I7 L. O+ R3 k0 G0 Z0 l
+ b0 q4 U' A/ x. O* u
资料来源：谋学网（www.mouxue.com）,在一个单链表中已知q所指结点是p所指结点的直接前趋若在pq之间插入s结点这执行操作
# Y8 P2 F0 e. S- {$ B( X+ |, ZA、s-next=p-next;p-next=s
; p  f" L* a) c5 n- y( O& IB、q-next=s;s-next=p
: W. Q* \( @- P0 nC、p-next=s-next;s-next=p;
( b% s  z- w6 D5 C  PD、p-next=s;s-next=q;
- K3 l& Q( l6 z( p# }* m0 H  Y正确资料:
% g7 {5 f7 \  N# Z* F( u+ e. ]

% I6 M  p# Y9 f0 B- `- _5 X& ~7 d5 k第11题,图的存储结构有
A、邻接矩阵
' ~8 r: b4 E- x' t8 i8 z: SB、邻接表
C、数组表示法
D、十字链表
8 H* i, b: x* [1 S5 Z, l正确资料:谋学网,B,C,D
1 v8 E6 U! \6 @

4 n0 `( Z0 t! \# _$ y8 s4 m; u* i资料来源：谋学网（www.mouxue.com）,二叉树的遍历方式有
0 `+ F( z1 k, J0 y! a8 eA、先根遍历
B、中根遍历
, b+ o$ s; S9 b8 a) I; E* _. R: BC、后根遍历
' m/ P, d8 M% D2 xD、深度遍历
+ s3 N4 A6 z2 k6 x/ }4 v正确资料:谋学网,B,C
" |- M5 `6 I7 o# m, c
. L9 b* p8 }1 y
( i3 u& E0 k0 C8 @& C5 K! [第13题,递归过程中要保存的信息包括
A、返回地址
; f. Z+ A( X" U! e$ J. w9 D9 RB、本次调用中与形参结合的实参值
+ N. ^# [* `- A  g: G  IC、本次递归调用中的局部变量值
# O$ L0 Y6 R! VD、执行结果
正确资料:谋学网,B,C

/ a- N: m6 w; [7 u- |! A7 i1 E
第14题,属于插入排序的排序方法有
A、直接插入排序
0 O3 J+ H3 ?) PB、对半插入排序
( n7 U; Z7 j+ d; s6 M& ZC、渐减增量排序
D、冒泡排序
+ d) Z( w+ K% c2 u1 k. P$ h9 H; |正确资料:谋学网,B,C
; z/ v* H. l% E. \5 E
! Y- C. B) p) p- B* W- K: R
资料来源：谋学网（www.mouxue.com）,一个好的算法应具备以下性质
A、正确性
  x$ l2 b/ v$ c% B" G7 `( _B、可读性
1 o+ N. S) V7 c7 D0 {C、稳健性
; s5 G( V7 q* @& j; ]D、有穷性
/ i/ }' E2 y# E* C6 R; B7 b! u正确资料:谋学网,B,C,D
7 m7 W* n' g& `# I. V. T

第16题,设有两个串p和q求q在p中首次出现的位置的运算称作模式匹配
0 }2 r- W6 N  O' U/ H8 \4 [% cA、错误
B、正确
正确资料:
0 j7 J: _# M, b5 p) `

第17题,快速排序的速度在所有排序方法中为最快而且所需附加空间也最少
* N$ J7 X# c; a6 [9 nA、错误
+ n8 x) S9 z! N) Y$ M; EB、正确
8 n7 S5 V: x, w- A! R" K正确资料:谋学网
! j5 p7 e" x4 B5 u
$ ~$ x, Q9 j# P5 E
6 y! \+ ~4 |' Q/ C8 D" ?第18题,不是所有的AOV网都有一个拓朴序列
* D- F4 }% D( BA、错误
B、正确
' g6 a6 F3 A. J2 ?6 u9 Y: a正确资料:
$ T! e; F# t# q& _

第19题,对于前序遍历和中序遍历结果相同的二叉树为所有结点只有右孩子的二叉树
A、错误
+ H. }: U  b+ t8 D- t' rB、正确
正确资料:
) B8 G5 Y( N% P: B% F& ?
9 m+ N" Z5 |# m/ m( a
% B: U2 d; V0 O$ j6 D! j资料来源：谋学网（www.mouxue.com）,算法和程序没有区别所以在数据结构中二者是通用的
9 }& I" Y# k6 L% I/ hA、错误
B、正确
$ W1 c0 ~5 Z  \4 K正确资料:谋学网

7 |# ?! E$ `6 d6 R. R) ^
第21题,判断一个表达式中左右括号是否匹配采用栈实现较为方便
: ?& O1 M; s3 r8 n, M2 AA、错误
B、正确
5 ~$ x' l$ O% ~9 x) w: ^正确资料:
% b/ P8 j2 }6 _

4 H% K: k5 n9 ?' X# g第22题,邻接多重表示法对于有向图和无向图的存储都适用
* d8 V" p5 N; y( i  {A、错误
" g3 I1 z6 A! @+ r' s# h& _' |( ^9 y  UB、正确
正确资料:

4 w& |8 E# q! H3 i
3 p  v2 M- U( d7 q, n* m7 q7 J第23题,从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较然后将其放在已排序序列的合适位置上该排序方法称为插入排序
A、错误
2 J% A! {; X, `/ u' l) TB、正确
7 \! t& h; _) T正确资料:


& L3 u" x( ^% G" Z- b' T第24题,在最好和最坏情况下的时间复杂度均为Onlogn且稳定的排序方法是归并排序
# v; z' N7 m" m  pA、错误
B、正确
$ K7 i* e+ Q  o$ n' x8 \正确资料:
$ Q2 |. m  K' P# S9 d5 u

4 c9 W! a+ [5 n/ \/ N0 q6 o: }" A资料来源：谋学网（www.mouxue.com）,由权值为9257的四个叶子结点构造一棵哈夫曼树该树的带权路径长度44
- ]3 L' _% V$ P  i) M/ zA、错误
; z2 H1 V2 R2 f. xB、正确
正确资料:


2 o6 y* M3 I0 F- x1 |6 Z: G
, W3 D9 {# E: Y, z# Q
* F2 T& q' b) M$ d
4 n! v4 S5 h* s3 N' }3 M: F
. i* m' N: j4 _) Q
" [0 N" [2 r! J. N

1 T0 P  A* a3 d7 f- g- g) i
  b3 r) k9 w7 h2 h" u( s2 S

/ S0 t* E/ T7 Q
/ ]& \, o7 O/ B