南开21春学期《数据结构》在线作业-2100分

admin

资料来源：谋学网（www.mouxue.com）-[南开大学]21春学期（1709、1803、1809、1903、1909、2003、2009、2103）《数据结构》在线作业
试卷总分:100    得分:100
4 Z1 g+ A- Y$ v$ W, S# _4 N4 x7 \第1题,已知图的邻接矩阵，根据算法，则从顶点0出发，按深度优先遍历的结点序列是（  ）
2 t& {2 p* q. a6 gA、0 2 4 3 1 5 6
B、0 1 3 5 6 4 2
( Y/ H! E% k8 v3 w- g" W9 iC、0 4 2 3 1 6 5
D、0 1 3 4 2 5 6
7 |/ R' x4 t) Y6 O2 |: n正确资料:
3 A" I) U+ R7 X! l% A8 j% l9 m. |

第2题,设有两个串p和q，求q在p中首次出现的位置的运算称作（）
. B" q6 C9 A* _( z6 f2 V+ f( zA、连接
0 S) N: d; U8 A; r% ~2 y0 UB、模式匹配
C、求子串
4 K8 {$ Q5 p" O+ y# |- LD、求串长
5 O/ U0 Z' Y  k* G0 j正确资料:

" f( |! ]0 G+ @' x1 T
第3题,折半搜索与二叉搜索树的时间性能()
A、相同
0 U6 F/ Z* v# v+ R3 |+ B  jB、完全不同
* k# f/ c: y5 tC、有时不相同
8 r" g4 k( ~6 ~& V' x  SD、数量级都是O（log2n）
正确资料:
0 W, r, ?2 F8 F  B- I

6 d$ M6 ~  M( M+ ]8 t, c5 N5 g/ V. J# }第4题,在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）
A、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
( T! D  o; C) x0 kB、在第i个结点后插入一个新结点（1≤i≤n）
/ e3 y" W- u% A. w0 JC、删除第i个结点（1≤i≤n）
D、将n个结点从小到大排序
正确资料:
9 a. `( l2 g7 p3 q+ b$ \& `
8 K: ~1 _2 b& Y6 O6 y+ @8 r1 W
' R' L" T' A/ x: M/ a9 h资料来源：谋学网（www.mouxue.com）,已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）
7 o$ U( B: P+ s- b; T- K, jA、0 2 4 3 6 5 1
- g6 x" @: Q; V" u# C: ]B、0 1 3 6 4 2 5
, O- b1 J0 `/ B) ]# }C、0 4 2 3 1 5 6
D、0 1 3 4 2 5 6
1 |" o0 q, H1 o) c+ e正确资料:
; |2 N8 h/ G7 E2 ]

5 I% r# ]2 }2 C第6题,在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
$ D# R, N0 P  i- N" U+ mA、1/2
, w; k2 o2 A+ n' V8 OB、1
C、2
) Y! m  R! O# b8 {) CD、4
正确资料:

3 m- d* m/ T' d+ D. O$ ~
第7题,用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的
A、栈
B、队列
C、树
D、图
正确资料:
3 A" p# S$ J1 `3 n  M: l- e

第8题,若已知一个栈的入栈序列是1，2，3，...，n，其输出序列为p1，p2，p3，...，pn，若p1=n，则pi为（）
A、i
B、n=i
C、n-i+1
  X: G& m' y/ |3 l. J( {D、不确定
正确资料:


6 |; _$ ]' Q8 ^! l9 s5 v第9题,快速排序在下列哪种情况下最易发挥其长处()
A、被排序的数据中含有多个相同排序码
0 c+ d* g- M; ^: q. F7 dB、被排序的数据已基本有序
C、被排序的数据完全无序
D、被排序的数据中的最大值和最小值相差悬殊
( y' a7 b" M/ L& P8 d% F正确资料:
- Y' z( D+ q% b
3 Y' r9 t: @: H
资料来源：谋学网（www.mouxue.com）,堆的形状是一棵()
A、二叉排序树
B、满二叉树
/ a# V5 e* l7 g  J; E5 JC、完全二叉树
D、平衡二叉树
) U8 Q1 O7 p; v; a; N6 q, b& [正确资料:
+ U/ \) T& R$ d0 |4 `& o7 m1 k

第11题,判定一个队列QU（最多元素为m0）为满队列的条件是（）
( Q& d  ^' L( k3 Y3 C( q* fA、QU-rear － QU-front = = m0
& B" v# g: H2 S: D* mB、QU-rear － QU-front －1= = m0
C、QU-front = = QU-rear
D、QU-front = = QU-rear+1
正确资料:

! Z( B( @6 a5 x" f% s) ?$ V
资料来源：谋学网（www.mouxue.com）,一棵具有 n个结点的完全二叉树的树高度（深度）是（  ）
8 B$ ?) g- f# G; T; fA、
B、
4 O+ T. R5 w7 x7 VC、
5 |' h0 U" q, V( |2 t  ID、
" q! a# H$ R: M  M8 A" z正确资料:
) u1 r  d4 I( V4 z# B4 g$ ?
; g6 ^5 k) d+ {7 B( y# h7 i; Z
4 r6 Q$ j& c8 O# c1 Z第13题,堆是一种()排序。
A、插入
8 t0 `/ i* A3 ]- x1 w2 AB、选择
C、交换
D、归并
正确资料:
3 f3 E4 w& H: g4 k5 N; n6 F1 p
$ U& @  `3 P! Z; A9 A
第14题,有8个结点的无向连通图最少有（）条边
3 J2 {/ \( C4 d7 pA、5
9 B! \9 M2 j8 A% C+ SB、6
- A2 o9 [2 G1 p  y- W1 yC、7
3 O4 i) M; j8 T1 j/ h6 `5 XD、8
3 b1 E, L# H+ L. C. c6 n; N正确资料:

! a; F" g2 F* u! }
$ G0 Z5 M! }, z  @. ~2 L资料来源：谋学网（www.mouxue.com）,链表是一种采用        存储结构存储的线性表
A、顺序
B、链式
C、星式
- x6 b. t/ C$ t0 }( E9 r' pD、网状
正确资料:
& d- w6 u  v' h
8 I& q1 k7 u+ }# U! i& t
& H, w4 h7 ^9 q) R8 a, x  ^; G第16题,不含任何结点的空树（）
A、是一棵树
4 r$ e" u! T: e( z2 C: g6 {B、是一棵二叉树
C、是一棵树也是一棵二叉树
; P, I: j( y* Y/ x8 f* ?D、既不是树也不是二叉树
正确资料:
2 e5 E# {3 l) @. m8 c2 w# S+ O7 S' M

第17题,数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为()
A、存储结构
2 g# k* I6 ]; X- ^/ @( ^5 {B、逻辑结构
C、顺序存储结构
D、链式存储结构
正确资料:


) s; G# a$ f" h! ~& e. G第18题,已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ ）
A、0 2 4 3 1 5 6
B、0 1 3 6 5 4 2
C、0 4 2 3 1 6 5
! d; G: a) k0 U" w1 Q. MD、0 3 6 1 5 4 2
正确资料:


, O* i" Q. G, X+ I; E$ I第19题,下列关键字序列中，()是堆
A、16,72,31,23,94,53
B、94,23,31,72,16,53
C、16,53,23,94，31,72
D、16,23,53,31,94,72
正确资料:
2 {+ ?+ i8 k4 f2 h

) q8 l* \) y8 C' n资料来源：谋学网（www.mouxue.com）,排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为()
A、希尔排序
) \4 g4 v& F6 oB、冒泡排序
- u: h; E+ `/ p6 O7 F* j- E. ?C、插入排序
D、选择排序
# R, y! b$ w! M$ [: c正确资料:

- y* m& k7 c& v
第21题,在表长为ｎ的链表中进行线性查找，它的平均查找长度为（  ）
A、ＡＳＬ＝ｎ
B、ＡＳＬ＝（ｎ＋１）／２
# |! i: a/ P5 F% ?1 @! y( [C、
& O  A) ?1 i8 S- N$ S* xD、
" Q7 [- n$ p/ n2 S! i6 M2 ^正确资料:
  }- {# O" _# K2 M  ~; E+ A  X8 G
  y/ b' Z0 C2 }6 k
7 C6 @/ D: R6 H& W# A& e! O第22题,设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）
: [" u+ T( w1 y  s" n; oA、循环链表
B、单链表
C、双向循环链表
D、双向链表
正确资料:
+ X3 ^0 ~- P6 G5 i

第23题,将5个不同的数据进行排序，至多需要比较()次
& w4 {: N; `/ K5 a' K+ NA、8
' Y0 X" k" p2 Q( ]3 FB、9
/ L% Q* g' q; b% _' u; WC、10
D、25
正确资料:


. F) g3 y2 H7 j1 H第24题,若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为()
3 A: Q. Z5 ]8 _1 LA、79,46,56,38,40,84
( V1 [3 a/ j+ O9 Z) D7 g0 |9 aB、84,79,56,38,40,46
C、84,79,56,46,40,38
- K  R, v% D/ \, uD、84,56,79,40,46,38
正确资料:
  s) v; _' C# i/ b7 X) a/ B3 Z/ B
8 ?2 e' ]+ E0 V, X
8 l2 g, L- i3 p5 W6 @7 ^, ]资料来源：谋学网（www.mouxue.com）,任何一个无向连通图的最小生成树()
4 `! C" S0 \$ R  ^) ?A、只有一棵
3 v. q4 B, G2 m( J  z$ aB、一棵或多棵
C、一定有多棵
9 w1 `7 x" k4 o* YD、可能不存在
正确资料:
4 e- d& U. v  x5 M0 X" G

8 K4 t' j% M2 |  Z3 a( `& j% L( m第26题,单链表的存储密度（）
A、大于1
5 r( ^0 y  z6 y) a! `6 a. ZB、等于1
C、小于1
" l) V" k/ I+ [' Q. u# {3 wD、不能确定
; @6 L! d% u2 ^4 c正确资料:
1 ]; e# T2 }8 M! F
$ z5 z2 b) d& w. O
, {! V) v, B  U, I/ w2 T. G0 O% T. Y第27题,已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（）
; g" b5 [- n2 E; mA、0 1 3 2
5 d2 I3 i7 ]& k9 WB、0 2 3 1
% z5 ?) |% ]  d. GC、0 3 2 1
D、0 1 2 3
正确资料:
# B3 V$ m7 E3 D9 P7 B
5 J5 M+ g# [4 E) G
+ @8 L) E* w9 m: A, o5 g7 M第28题,已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为()
A、CBEFDA
B、FEDCBA
- V4 e  Y; G+ e) r$ HC、CBEDFA
D、不定
$ U1 O, P6 O! I& b5 J& r/ v% l$ A正确资料:


第29题,判定一个栈ST（最多元素为m0）为空的条件是（）
2 V/ B# J, b) ], i& hA、ST-top0
- c; B9 O! Z. _; |" r* ~& r/ ?B、ST-top=0
C、ST-topm0
4 A, C% n6 L# d+ t/ |( P, KD、ST-top=m0
正确资料:
4 |) B- O2 o2 U! z' t# h) z! f

1 t; c7 i5 y  ~资料来源：谋学网（www.mouxue.com）,把一棵树转换为二叉树后，这棵二叉树的形态是（）
) u: k: T8 d- l4 WA、唯一的
) E$ U7 D: W$ aB、有多种
9 }3 X6 g6 O; B7 y- D/ ]C、有多种，但根结点都没有左孩子
4 w0 ]' m9 V' o3 ~( A" sD、有多种，但根结点都没有右孩子
7 Q" w5 F4 d; w( w/ ~5 ?% l正确资料:


8 F( D- `  m3 N2 h+ I第31题,二叉树中每个结点的两棵子树的高度差等于1。
7 m: ]  H, G2 R6 L5 N& ^  MA、错误
# K% j) i6 g9 T# nB、正确
正确资料:
4 q6 N* ?: F8 S6 O. M  p1 V- m. G- X

  k9 i" R1 M2 E! f2 c* {第32题,链表的每个结点中都恰好包含一个指针。
7 f) j, d& x3 R, v! s+ CA、错误
' @. u' U! i2 `B、正确
正确资料:


第33题,栈和链表是两种不同的数据结构。
A、错误
8 [( v) G( n3 u5 E" u1 xB、正确
正确资料:

% p) r9 G9 t  c/ ~
8 ?& f& e. I  h% s5 C( w3 C+ q第34题,线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
A、错误
; ]% S4 r+ |/ q: C$ AB、正确
" ~# x6 p% e: s正确资料:

8 R1 o' {7 H2 s7 W
第35题,对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表
A、错误
( Z' h4 P5 U) `- j1 W" lB、正确
正确资料:


第36题,顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
) d9 B  L+ t  Z7 k6 H/ [. O2 z7 pA、错误
B、正确
( i& E- w/ n1 N" Z6 Q正确资料:
" T( O3 e* g/ `( A5 N
- Z1 b1 C- O: q# [5 N$ j
第37题,在表结构中最常用的是线性表，栈和队列不太常用。
: B1 G, _$ w* B; ]8 u  Z# ~A、错误
) t; H/ n7 Z% u& s- CB、正确
  Y. C# k# }$ p5 s0 f3 ?9 X正确资料:


第38题,一个栈的输入序列是12345，则栈的输出序列不可能是12345。
A、错误
B、正确
正确资料:
& |4 `3 d2 K4 k+ ]- P4 [
" l% d) f1 @' J  s, s1 ?
第39题,二叉树中每个结点的两棵子树是有序的。
A、错误
B、正确
正确资料:

7 L9 i4 ?, W7 J/ k
0 G" J) Y- ]4 R+ m" @) |第40题,栈和队列是一种非线性数据结构。
7 N/ w: g/ H3 Q3 V* `3 wA、错误
B、正确
正确资料:
1 Q& {3 ~: }- p) P4 p7 S$ T: q
' O, E8 C: z# L& A# h( E# \# d
; j9 y9 E* c2 l1 r- Q, u( w第41题,链表的物理存储结构具有同链表一样的顺序。
A、错误
) j/ P+ U* F% i) S/ XB、正确
正确资料:
: S$ R# `7 c) h+ F! b3 L
" w( t5 A+ g" O" t" x7 V. `
/ k5 C+ }! @" a' U  B2 h; X% X# o第42题,具有12个结点的完全二叉树有5个度为2的结点。
A、错误
3 f* e# ?, L: z7 OB、正确
( h! y" O2 B1 m! f1 [, J正确资料:
6 V1 m+ \0 x) u$ y5 B' U, E" s

第43题,用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
% {1 G! s6 j0 t  a$ gA、错误
B、正确
正确资料:

: x& d3 v$ r. C- x$ O( f/ c
. {; Q$ B% _/ U+ s; d第44题,栈和队列的存储方式既可是顺序方式，也可是链接方式。
A、错误
2 a  x3 C  u7 a2 YB、正确
( i; G% s8 A1 f$ b正确资料:
) g6 }7 B: d4 B3 Q8 C
; \' y+ C- Z6 S- ]7 O5 Q
9 w% \+ O2 [* ?' W第45题,线性表的逻辑顺序与存储顺序总是一致的。
A、错误
B、正确
. O# V- s# R# }2 ~- t正确资料:

: O( x+ P- D. q6 F" W
第46题,线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
$ m; m6 X# M& j- Z( K, j( OA、错误
B、正确
# I, n* p- d3 g) A; A; m正确资料:

1 r( M" u' s1 \: Q0 C4 D% _
- s% G: s8 a0 ]" Q第47题,两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
A、错误
6 @! N% f; e& C7 o) A, Z1 OB、正确
正确资料:
. G) }# u3 t0 H6 w: {1 t4 B

第48题,顺序存储方式只能用于存储线性结构。
A、错误
B、正确
) s4 z+ S$ [$ j) U正确资料:

2 w& h/ ^$ w' i4 T: \
第49题,顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
A、错误
! |8 T1 r0 j# \B、正确
正确资料:

# y4 Q. e6 u9 D" U
资料来源：谋学网（www.mouxue.com）,二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
A、错误
B、正确
" o; q" ~# i8 q! n# r5 B! B. S正确资料:
" T7 _2 a! [' [6 w" s. |% K

5 }; S# l0 f; C9 v0 X( J5 {
; t3 a& C5 w& e

7 {8 G# S0 e$ P4 {0 d% {
2 `% o! N+ n% I$ B3 e* j
! m7 ]* o# j6 T" G& \


( K. C) v# C8 G0 L

5 F" j* H( P: s

# R$ l( u! b* B1 c. x