南开大学22春学期《数据结构》在线作业

admin

资料来源：谋学网（www.mouxue.com）数据结构-[南开大学]22春学期（高起本1709、全层次1803-2103）《数据结构》在线作业
试卷总分:100    得分:100
第1题,有8个结点的有向完全图有条边
  \8 B. Q4 U1 U) ]A、14
0 L0 l% D$ N) WB、28
  c6 d3 a# ~1 P4 HC、56
D、112
正确资料:
1 x# k2 I5 P, I" l! V/ N

. H' q3 ]1 f8 F0 }6 i9 G( X. F第2题,有8个结点的无向图最多有条边
! z( ?8 F2 K5 C/ x* u5 oA、14
4 z; Q, B* G) L1 C& e! DB、28
' R+ ~% n5 ~. c3 h. B3 i6 NC、56
) x/ z* A4 j8 Q! ?8 F, ~D、112
- ]6 C7 v# [# L! l( I$ V正确资料:
( G6 k3 h9 i5 |, \( @- v
) m+ d4 f) G  K3 ^' }3 J3 Z( `8 e
, w5 f% a' O4 d/ U" Y第3题,一个向量第一个元素的存储地址是100每个元素的长度为2则第5个元素的地址是
1 ^. _7 {$ `# g& m8 E7 l( J# c1 l( o! bA、110
0 t5 X' ~8 O' l" b% s; M& F3 B; VB、108
C、100
' c( d- ^5 r% D. d8 h$ K( C0 N) J, N$ QD、120
正确资料:

- e- I/ j9 Y* f# F: M4 A  d
第4题,已知图的邻接矩阵根据算法则从顶点0出发按广度优先遍历的结点序列是
) O& D0 {. P4 x! m% }* _A、0 2 4 3 6 5 1
5 {' ]' r  w, o7 i$ E2 W8 ^1 eB、0 1 3 6 4 2 5
C、0 4 2 3 1 5 6
8 h! F" k1 |( F4 tD、0 1 3 4 2 5 6
正确资料:
7 [& z9 ]& ^: t. R* ~/ t, F

  |# h8 [  O4 D资料来源：谋学网（www.mouxue.com）,折半搜索与二叉搜索树的时间性能
! A/ o. [! n' [2 S8 J$ \A、相同
B、完全不同
& G( a& T+ B  ^C、有时不相同
D、数量级都是O（log2n）
正确资料:
# u; ~- f7 ^/ i) n) Z) A
: I' M- E- \2 i* x( Y
; S( N" K& i. U' t- O  k; W( G第6题,堆的形状是一棵
3 C+ J5 E) C) m3 j" E1 ?' eA、二叉排序树
6 }/ \6 w% z) _$ i; C% f1 TB、满二叉树
" j) H2 j- i3 X6 s( uC、完全二叉树
D、平衡二叉树
2 Y+ V$ u& A6 d* k正确资料:
9 `: r- a' ?1 q  l8 ?+ x" i  N/ d

7 M0 H+ r% I: V, w第7题,线性表Ｌ在情况下适用于使用链式结构实现
; M! f3 g1 t' X  }, S9 Y7 fA、需经常修改Ｌ中的结点值
) q4 s! ]% h! P7 A: tB、需不断对Ｌ进行删除插入
/ B/ N# q2 R( S( h8 U$ V9 {# MC、Ｌ中含有大量的结点
; W$ l: y8 W8 l4 B: }. |8 O  I5 v* hD、Ｌ中结点结构复杂
正确资料:


第8题,从未排序序列中挑选元素并将其依次插入已排序序列初始时为空的一端的方法称为
/ Z3 c" o' N% R# H+ o+ J: X$ t# @A、希尔排序
2 n8 f. ?4 L4 X7 v- t/ ~B、归并排序
8 l4 f) \6 L& g  YC、插入排序
) g) C2 T3 n3 o8 u; [$ w6 tD、选择排序
正确资料:

/ o5 X' g: f7 I8 v) B: M0 [
; {) _+ ?) ]- t' w7 O/ ^. O第9题,引入二叉线索树的目的是
A、加快查找结点的前驱或后继的速度
B、为了能在二叉树中方便的进行插入与删除
) ?' w$ j4 \( a/ r2 \2 Q: YC、为了能方便的找到双亲
D、使二叉树的遍历结果唯一
正确资料:
) _1 I6 i9 W, f# _9 s, G+ V

4 v, A9 s- r5 g$ c7 ]1 m% Y资料来源：谋学网（www.mouxue.com）,链表是一种采用存储结构存储的线性表
* v( t! T; C- p( C1 j# m% h3 eA、顺序
B、链式
C、星式
D、网状
% g1 k( u% I" F" d7 w. V正确资料:
) M9 ~% S8 t) P% ?  d' o
0 ]8 j& [1 g& T  M4 z# |4 A! P# E
第11题,一棵具有n个结点的完全二叉树的树高度深度是
! S1 H9 E0 s" o$ }A、
B、
* Z4 O+ }/ [. M" z  {/ qC、
* d" h& K2 P) S" JD、
正确资料:
0 B" D( z6 q2 n  d& j3 a6 z

资料来源：谋学网（www.mouxue.com）,用邻接表表示图进行深度优先遍历时通常是采用来实现算法的
A、栈
B、队列
! [4 S# q/ \7 H0 |3 X2 C4 z( jC、树
D、图
* W- q  ?, K9 j( ^正确资料:


第13题,设有两个串p和q求q在p中首次出现的位置的运算称作
A、连接
B、模式匹配
C、求子串
D、求串长
/ f" }/ y9 L5 G' z正确资料:


第14题,已知一棵二叉树的前序遍历结果为ABCDEF中序遍历结果为CBAEDF则后序遍历的结果为
A、CBEFDA
: {' {: E" G8 ?$ qB、FEDCBA
C、CBEDFA
D、不定
+ I+ r( ]; `7 T正确资料:


! |. ^+ j% h; ~; t资料来源：谋学网（www.mouxue.com）,在n个结点的顺序表中算法的时间复杂度是O1的操作是
9 D3 ?3 y1 E" ^8 }$ l, `A、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
1 m0 S8 n0 n' s- BB、在第i个结点后插入一个新结点（1≤i≤n）
5 ]/ ]0 z0 s5 C% p1 NC、删除第i个结点（1≤i≤n）
6 ]! n- w2 t/ C3 U$ GD、将n个结点从小到大排序
正确资料:


第16题,快速排序在下列哪种情况下最易发挥其长处
A、被排序的数据中含有多个相同排序码
B、被排序的数据已基本有序
C、被排序的数据完全无序
D、被排序的数据中的最大值和最小值相差悬殊
  Z# G3 b0 I1 Y$ A: b正确资料:


第17题,判定一个队列QU最多元素为m0为满队列的条件是
A、QU-rear － QU-front = = m0
B、QU-rear － QU-front －1= = m0
$ ~% \( `: Q, K3 K  }* NC、QU-front = = QU-rear
D、QU-front = = QU-rear+1
正确资料:


* Y* K; @4 T# M& z4 h第18题,具有nn0个结点的完全二叉树的深度为
A、
$ }  ^, \. C( _' GB、
9 E6 }% J* h7 Q, nC、
4 a) N/ ^, s; [4 r  {D、
9 O6 \/ J: v, _* U3 T正确资料:
7 j6 G0 u9 k" Y* ?8 T0 N9 N( I

第19题,已知图的邻接矩阵根据算法思想则从顶点0出发按深度优先遍历的结点序列是
5 w% i$ Z+ S! u- e/ vA、0 2 4 3 1 5 6
- k* I& j/ B* Y: ?; xB、0 1 3 6 5 4 2
- U) e8 G( c" i4 QC、0 4 2 3 1 6 5
D、0 3 6 1 5 4 2
" g6 a5 t, F+ N9 t/ Q# q6 I正确资料:
" M, [7 S) @1 W

资料来源：谋学网（www.mouxue.com）,向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变平均要移动个元素
A、8
. v0 z% @$ u( q4 vB、63.5
C、63
! s7 D5 c; {, Y, JD、7
正确资料:

' u* S. [8 \1 b- r% I3 }
第21题,若已知一个栈的入栈序列是123...n其输出序列为p1p2p3...pn若p1=n则pi为
) B8 P) r# o& g( ]A、i
  U, \1 A! [+ W. B  B7 fB、n=i
C、n-i+1
D、不确定
5 [5 E9 ~* y2 ?: Z8 e5 x正确资料:
6 h/ A% I) K9 P# c3 c( E

第22题,链接存储的存储结构所占存储空间
A、分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B、只有一部分，存放结点值
C、只有一部分，存储表示结点间关系的指针
2 c+ t: h/ S# u; X1 q/ oD、分两部分，一部分存放结点值，另一部分存放结点所占单元数
正确资料:
3 W. t+ d* T; A

第23题,对有n个记录的表作快速排序在最坏情况下算法的时间复杂度是
A、O(n)
1 a9 H9 }( m/ _. ~6 MB、O(n2)
C、O(nlog2n)
1 H. O% F) T4 n% C; cD、O(n3)
# Z' s0 z  h) v& B& s正确资料:
9 V) A8 N8 s  u) ?$ {4 |% ^+ B

7 o0 o9 ?% a# ~7 ]0 ]' g; f+ p第24题,数据在计算机存储器内表示时物理地址与逻辑地址相同并且是连续的称之为
: u4 F7 @  p0 ^: {- Z" LA、存储结构
B、逻辑结构
C、顺序存储结构
6 l! G: E  f% pD、链式存储结构
$ F$ T( h7 U1 r8 k( \3 `正确资料:
+ B* }) o- R: e  @! |: @

+ l  W, p- f0 R$ X+ r8 p2 k8 }资料来源：谋学网（www.mouxue.com）,任何一个无向连通图的最小生成树
3 m8 w4 j) q, g3 \A、只有一棵
% V0 C. V% M/ a; s/ M6 f$ lB、一棵或多棵
  q3 p& R8 G. k' LC、一定有多棵
D、可能不存在
! m' s4 L% k0 E6 \正确资料:
+ ^8 b& `0 b4 g4 Q9 ?
& g: c7 B0 Z. i& u& q
: \' R& k: N* i- i. s% X3 f7 P第26题,将5个不同的数据进行排序至多需要比较次
6 D5 Q9 ]0 |2 D9 `0 X- Y2 q% e0 NA、8
1 D  a6 K* t2 Q& vB、9
C、10
D、25
正确资料:
$ g4 a4 ~7 Q; Q
, n  x6 e, t! R" x2 P0 ?7 }$ a6 u
第27题,广度优先遍历类似于二叉树的
$ ?' o  z, V  d# t" k* sA、先序遍历
; u/ Y; f  {, q- z. {' xB、中序遍历
C、后序遍历
D、层次遍历
正确资料:


第28题,用邻接表表示图进行广度优先遍历时通常是采用来实现算法的
A、栈
5 y6 H2 R& D, C7 U2 t% C! C. m8 LB、队列
C、树
D、图
正确资料:

8 H+ `  W9 p. S6 Y6 C
0 G9 }2 H1 a6 g7 k. i第29题,设串s1='ABCDEFG's2='PQRST'函数conxy返回x和y串的连接串subssij返回串s的从序号i开始的j个字符组成的子串lens返回串s的长度则consubss12lens2subss1lens22的结果串是
A、BCDEF
& f1 [1 e( `* b, }  Q  sB、BCDEFG
C、BCPQRST
% Z7 ?8 @8 a5 d7 ^3 l+ u  {) C3 zD、BCDEFEF
正确资料:

) U6 n4 ]+ A# S% k1 R6 J' m6 ]! V
资料来源：谋学网（www.mouxue.com）,设a1、a2、a3为3个结点整数P034代表地址则如下的链式存储结构称为
A、循环链表
B、单链表
- w4 w. l, F: W5 p) yC、双向循环链表
( c. b) a0 b2 F5 pD、双向链表
正确资料:
) l& K! V5 N3 E- i, I
# `# i/ q1 I$ k: K2 @/ n5 a
5 g$ L+ k2 f! k% |第31题,具有12个结点的完全二叉树有5个度为2的结点
A、错误
! u* S4 m0 X& x/ }B、正确
( G& J9 l! s. y% L5 G正确资料:

( s2 M2 V' t' G) N
  k, _+ x( E. U& \; `- x第32题,链表的删除算法很简单因为当删除链中某个结点后计算机会自动地将后续的各个单元向前移动
# J& `- Q7 B. o) `A、错误
  S8 m( A! o* y5 G7 \B、正确
正确资料:

, _0 Z0 V8 M0 R: ~. ]5 r" I. n
第33题,线性表的每个结点只能是一个简单类型而链表的每个结点可以是一个复杂类型
2 k, A6 F: D+ o' Y2 F2 WA、错误
B、正确
正确资料:


$ `2 W. P- U2 c6 q! U  j: p/ C第34题,栈和链表是两种不同的数据结构
A、错误
7 ^1 Z% y* J; `+ }$ H/ fB、正确
5 S+ V6 Z* e2 W正确资料:
, ^. n: o5 V9 A# H) S

第35题,线性表的逻辑顺序与存储顺序总是一致的
A、错误
1 H, P/ g: ~5 u4 yB、正确
正确资料:


第36题,二叉树中所有结点如果不存在非空左子树则不存在非空右子树
5 k( y3 T  u* \. u! b+ S- pA、错误
& ~: N2 ~4 T3 ~- U+ f6 s. [B、正确
正确资料:


" O& V: G% H$ ?( h  {; Z第37题,一个栈的输入序列是12345则栈的输出序列不可能是12345
A、错误
B、正确
正确资料:
5 z* X; ~& z- Q. |' q6 E, F! p" V

第38题,线性表在顺序存储时逻辑上相邻的元素未必在存储的物理位置次序上相邻
( }$ b- R% Q' m+ E. A1 \! cA、错误
# L4 [, F1 q( QB、正确
: j* o8 S7 q/ t! |! B6 n4 u正确资料:


7 {8 R: R" ^8 d第39题,两个栈共享一片连续内存空间时为提高内存利用率减少溢出机会应把两个栈的栈底分别设在这片内存空间的两端
A、错误
0 x# W( p1 e2 N9 h9 F3 X% ?B、正确
正确资料:

: D( Q" p; r& {* z- B5 t
第40题,若二叉树用二叉链表作存贮结构则在n个结点的二叉树链表中只有n1个非空指针域
A、错误
B、正确
正确资料:
+ g( M* ~; e- t( D% G5 O$ b

! s' J+ C3 {8 ^$ z0 o" W5 ~2 x第41题,线性表在物理存储空间中也一定是连续的
1 r7 Y& l/ H/ `) q# x: f! dA、错误
B、正确
正确资料:

) Y, n& X) q. i) \5 k
! g- l, [3 c; {" Z, T0 i第42题,队是一种插入与删除操作分别在表的两端进行的线性表是一种先进后出型结构
( h5 F4 e! N. gA、错误
B、正确
" G4 T$ ?8 Y, g9 P正确资料:

- X- \1 ~6 @- a, x4 q" p4 k
. I5 _1 {. l0 m- z) @2 |: g第43题,二叉树中每个结点的两棵子树的高度差等于1
/ O$ [( F- h! W& kA、错误
B、正确
1 k* q* s: ?" ~# b, @1 {正确资料:

. d, o8 s4 r$ N
: p7 X) K3 A, R1 l1 B第44题,栈是一种对所有插入、删除操作限于在表的一端进行的线性表是一种后进先出型结构
* ]: D# }4 b* J- zA、错误
0 E0 q" |- v0 ^# H  C- OB、正确
正确资料:


- L9 @  V- e2 M第45题,顺序存储方式只能用于存储线性结构
A、错误
, N$ r( F4 c0 f  m# \8 QB、正确
1 O% O1 ~& [+ l# F正确资料:


$ [- S: }$ s  Q7 d7 I7 [; f3 d第46题,对于一棵非空二叉树它的根结点作为第一层则它的第i层上最多能有2i1个结点
  r, p6 P# j$ C) v$ _  q* R- I. k7 xA、错误
9 R' K, `+ C5 G& [B、正确
正确资料:
8 x+ E. }" C) o6 i" G/ D& ?
- F* d7 R, p) C* G  g" f) b" k
第47题,用二叉链表法linkrlink存储包含n个结点的二叉树结点的2n个指针区域中有n+1个为空指针
4 \0 R& U$ q# jA、错误
B、正确
正确资料:

" N3 g/ S; ?* w" Q( {# N
/ N! B+ Z% ]6 f第48题,链表的物理存储结构具有同链表一样的顺序
A、错误
# g) x1 Q0 @4 x" C8 xB、正确
正确资料:
. _5 `# m" e: v! P8 l; }/ W8 E
0 _/ X9 L' H3 k, ~+ m
2 b% A& R0 h4 B第49题,栈和队列的存储方式既可是顺序方式也可是链接方式
A、错误
B、正确
正确资料:
; ]* ]. x# D1 _2 B0 s

资料来源：谋学网（www.mouxue.com）,栈和队列是一种非线性数据结构
A、错误
9 G$ G% D4 _9 S8 R$ j/ yB、正确
. }: [+ T# W" E) s正确资料:
# |0 O0 _  F# r* b% ^3 y
3 i8 F) i2 {" a0 c2 S! g5 |, E0 |
& N0 U2 u+ n0 z- r: \

4 E4 ]7 D+ x6 ^) ^9 k6 q0 l% u





& H: Y9 I9 m. _/ o
, I% P3 n. D! b* f5 `* _5 S
. Q4 i$ M0 u- ^3 |
8 P. m  x# p4 y4 w! i, L$ s! T1 _
) d8 l$ X" b3 R, o" G+ A