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

admin

资料来源：谋学网（www.mouxue.com）-[南开大学]21春学期（1709、1803、1809、1903、1909、2003、2009、2103）《数据结构》在线作业
1 k3 x! T" l, q7 k试卷总分:100    得分:100
第1题,已知图的邻接矩阵，根据算法，则从顶点0出发，按深度优先遍历的结点序列是（  ）
9 y! g2 r3 `) K  ^5 [4 iA、0 2 4 3 1 5 6
B、0 1 3 5 6 4 2
C、0 4 2 3 1 6 5
D、0 1 3 4 2 5 6
- ~/ `2 z$ f. Y9 j/ ^1 n正确资料:


第2题,设有两个串p和q，求q在p中首次出现的位置的运算称作（）
! J; N0 ]3 S# j3 r  TA、连接
$ F" b. K7 s$ S9 ?7 PB、模式匹配
C、求子串
( u5 `7 y( a% I/ b0 i9 `* v, hD、求串长
正确资料:
( ^/ V1 ~2 c: t/ X- E3 t2 ?

4 v5 |3 C. A  |+ Y  @第3题,折半搜索与二叉搜索树的时间性能()
( U' Y& }8 w* ?, }1 j9 BA、相同
B、完全不同
C、有时不相同
6 [9 I7 }6 x' _8 `5 ID、数量级都是O（log2n）
4 B, _  B8 {6 u5 R9 O) \2 ~正确资料:
' d& A. X5 n: J" |" w1 M8 d
4 o9 y0 [/ k, R
; C, D1 E1 J- h2 v# N第4题,在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）
! O" [/ B. c) u$ |- T6 e% W2 e) iA、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
. q2 x. ]% O8 ?: {( D# ]" lB、在第i个结点后插入一个新结点（1≤i≤n）
C、删除第i个结点（1≤i≤n）
D、将n个结点从小到大排序
3 w) m0 q4 {; a& x. V正确资料:
* m# R: I8 E  _9 t' T
$ `: v9 I+ I# U. Z
资料来源：谋学网（www.mouxue.com）,已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）
A、0 2 4 3 6 5 1
B、0 1 3 6 4 2 5
6 n1 Z# D' m' F7 V% u5 hC、0 4 2 3 1 5 6
D、0 1 3 4 2 5 6
正确资料:
) r  L2 p! x. ~& C/ S5 m5 W; {
4 _; \! R4 k+ v( T0 R6 W, q
第6题,在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
A、1/2
B、1
& a& w- |0 Y% L7 x% W. M9 \C、2
D、4
$ j0 P* U- C1 e! S8 d4 {. S0 e正确资料:

, l( V, s7 y" F  Y
( o3 s! r' l7 l7 [5 d# D5 C8 E7 b+ W第7题,用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的
A、栈
B、队列
C、树
D、图
/ r" v, U7 E. r* q9 H正确资料:
0 r  S2 z  ^' l6 C

第8题,若已知一个栈的入栈序列是1，2，3，...，n，其输出序列为p1，p2，p3，...，pn，若p1=n，则pi为（）
% K" {- |  U: p% TA、i
B、n=i
C、n-i+1
2 T! q  H2 ]: l3 M$ mD、不确定
正确资料:
2 F' M* U) I1 K( a% G9 H2 B( ?

; t3 Z7 y. l0 C  o第9题,快速排序在下列哪种情况下最易发挥其长处()
A、被排序的数据中含有多个相同排序码
) m2 L( }( Q3 F' D* P" hB、被排序的数据已基本有序
# @( _! \  d, jC、被排序的数据完全无序
  M' h; J2 X6 z% m/ H! xD、被排序的数据中的最大值和最小值相差悬殊
正确资料:

2 ]0 l9 o* E8 v% m8 o  K
" e3 l7 e" S' c( f资料来源：谋学网（www.mouxue.com）,堆的形状是一棵()
* D! @; b6 v- Q& R/ g* k3 |+ J9 PA、二叉排序树
/ b' f% l- ^4 j$ cB、满二叉树
- n$ P0 w9 X! k& ~: pC、完全二叉树
D、平衡二叉树
正确资料:

9 L8 k4 ?; y/ B, B4 S* ]5 g. l5 {" X
第11题,判定一个队列QU（最多元素为m0）为满队列的条件是（）
A、QU-rear － QU-front = = m0
B、QU-rear － QU-front －1= = m0
9 t, `" ~" u2 r) \C、QU-front = = QU-rear
D、QU-front = = QU-rear+1
正确资料:

, s: @' \; _, g+ @' r$ a/ z
资料来源：谋学网（www.mouxue.com）,一棵具有 n个结点的完全二叉树的树高度（深度）是（  ）
A、
) H/ w+ w, o7 l$ {B、
( u/ G& H4 k5 P! L4 TC、
D、
正确资料:
& u& {* {' C& C! F

' Z/ }; d5 ?  Y: J, e7 A7 Q第13题,堆是一种()排序。
A、插入
B、选择
C、交换
1 y6 l- A1 P5 O( A, ED、归并
正确资料:
2 _0 L- ?  b" h' V
6 n6 j- p( K4 u
第14题,有8个结点的无向连通图最少有（）条边
4 ^+ v1 {# I; }A、5
B、6
C、7
4 w+ H( e3 B1 q% XD、8
" ^) }& j$ B# w# B5 f: g正确资料:
$ d1 E+ c, y+ h2 A+ i

资料来源：谋学网（www.mouxue.com）,链表是一种采用        存储结构存储的线性表
A、顺序
B、链式
C、星式
" |2 H! P2 e) g( UD、网状
正确资料:


: x0 I$ M6 V4 ]! ]. W( k" |第16题,不含任何结点的空树（）
0 C# T( n- j2 |+ P" ?/ G; k' v2 V2 i" U3 XA、是一棵树
- `8 o1 I, p) k( Z& b+ P" s5 k7 C& JB、是一棵二叉树
C、是一棵树也是一棵二叉树
D、既不是树也不是二叉树
5 }2 G% n6 k- l+ K正确资料:
9 J0 A& W9 ~' Y' V: o

5 J8 C9 C! y1 F0 c: |* t6 n. u$ K第17题,数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为()
! P( u2 i& }9 v7 v1 PA、存储结构
B、逻辑结构
C、顺序存储结构
$ b; ]- O% n; S* f# f3 g9 YD、链式存储结构
; p0 h; S5 ?' s6 k0 F正确资料:

- ^7 f3 ~: l2 X
4 \! ?1 i5 i. Q7 l$ }7 P第18题,已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ ）
" t; U4 g& r- [" Z! d8 ]/ L$ gA、0 2 4 3 1 5 6
B、0 1 3 6 5 4 2
C、0 4 2 3 1 6 5
D、0 3 6 1 5 4 2
+ y& D* o6 J8 o2 c5 Q- [$ z正确资料:

5 O( }8 |7 C1 S
$ D* [6 ~/ m1 z, O第19题,下列关键字序列中，()是堆
' U3 x3 ~: U; |# X4 pA、16,72,31,23,94,53
B、94,23,31,72,16,53
C、16,53,23,94，31,72
8 P9 `" X3 d7 J, V% s5 `3 RD、16,23,53,31,94,72
正确资料:
9 k( G1 [" E2 l3 x0 T7 a9 H! V
! z2 r# ?; o( W. f
资料来源：谋学网（www.mouxue.com）,排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为()
A、希尔排序
4 y) _8 \- \: W& M3 ^: TB、冒泡排序
) ~, K- t: D( D7 }) ~3 L% E8 WC、插入排序
3 j0 ]3 e) X' N6 p' ], ^D、选择排序
正确资料:


+ c  B% \9 |0 {4 Z- D% U第21题,在表长为ｎ的链表中进行线性查找，它的平均查找长度为（  ）
7 a) h2 [. b, {; IA、ＡＳＬ＝ｎ
* L" o- a5 y' K+ L7 Y# |/ G, s) \B、ＡＳＬ＝（ｎ＋１）／２
8 O+ `6 J5 t) T! C( eC、
& b  m0 i! Q5 V9 u/ {& lD、
正确资料:


" O  x6 ]4 n8 ~& m+ V6 o# \3 r第22题,设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）
3 y) Z  ~& O1 \  O% s* M/ K7 PA、循环链表
B、单链表
C、双向循环链表
4 T' v2 q' T' D4 N" QD、双向链表
正确资料:

* {( Y/ `4 v8 {# b' a# }
第23题,将5个不同的数据进行排序，至多需要比较()次
A、8
0 T' @6 V1 a7 f& Y( c: o/ J0 EB、9
C、10
) h' h" X7 n9 U0 |- QD、25
6 U/ i, ?: q! l: x: c3 J3 u正确资料:


) @% X; F+ m1 _7 e第24题,若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为()
A、79,46,56,38,40,84
+ z0 x6 t9 w+ y+ I4 N$ B! xB、84,79,56,38,40,46
& k1 f' w8 |0 }; c8 A9 kC、84,79,56,46,40,38
D、84,56,79,40,46,38
正确资料:


) s. U' O" r8 i% k, J3 ^资料来源：谋学网（www.mouxue.com）,任何一个无向连通图的最小生成树()
A、只有一棵
B、一棵或多棵
C、一定有多棵
D、可能不存在
% k; `4 g) l( u/ H3 K正确资料:


第26题,单链表的存储密度（）
A、大于1
: i7 S/ m; w( |0 L" DB、等于1
C、小于1
D、不能确定
0 I' J8 `7 E- r正确资料:
- x  w  i2 V. e5 p

第27题,已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（）
/ W( a( ]. u+ M8 n5 q0 ^: I8 F" r; x  YA、0 1 3 2
4 w, G! R- Y' j4 n2 hB、0 2 3 1
  T6 ]# `) }5 I. p1 J- iC、0 3 2 1
1 b1 z1 `- S% c+ rD、0 1 2 3
正确资料:


0 x7 Q& X; Z/ @. n' F第28题,已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为()
1 d0 |! j: I7 k0 E# _A、CBEFDA
B、FEDCBA
7 A  q: f7 |: e+ p4 s! k- YC、CBEDFA
D、不定
5 g' C2 A3 v5 |5 o% `正确资料:
' c& {- K3 a& k% A1 Z2 W2 a
6 K; l% m' z7 l0 f$ p
第29题,判定一个栈ST（最多元素为m0）为空的条件是（）
A、ST-top0
4 d7 Z" w6 b+ P3 t. fB、ST-top=0
* o' J! s9 w8 @6 L# R* p) PC、ST-topm0
6 x5 b/ W, H( Z* q2 ED、ST-top=m0
正确资料:
+ l+ |  p9 l* S! ?

资料来源：谋学网（www.mouxue.com）,把一棵树转换为二叉树后，这棵二叉树的形态是（）
$ q- P! s/ u6 v2 ^2 D  NA、唯一的
B、有多种
" H9 Y" z9 f. A% M; u& fC、有多种，但根结点都没有左孩子
D、有多种，但根结点都没有右孩子
正确资料:

. S( T' v# k) |3 x5 V4 A& F0 p
+ z- I6 b6 N0 ~% {- @& {第31题,二叉树中每个结点的两棵子树的高度差等于1。
0 s/ G7 V8 y. v. v2 D7 k& z* B1 KA、错误
B、正确
正确资料:


第32题,链表的每个结点中都恰好包含一个指针。
A、错误
B、正确
/ |; o+ C/ A) d# F正确资料:
" X8 a- L% S/ K! l
6 v$ a/ Y% ?/ b) j* R! u5 F
第33题,栈和链表是两种不同的数据结构。
* I% n" O& d, `& v8 MA、错误
B、正确
, n: f" r! y" K, N正确资料:

. \, t. L' R; z1 u/ A- p
7 v7 b; m9 B! Q8 }0 ^! L: s5 \第34题,线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
A、错误
( K* ?+ c6 s0 C4 AB、正确
8 y) [: A+ V( q% {" j正确资料:
/ ]; ?6 B* f, s2 w8 o

第35题,对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表
A、错误
B、正确
正确资料:
) D% X" o6 W1 H

第36题,顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
  @3 ^( ?6 J2 vA、错误
B、正确
- D! ?7 K( Q; g" j正确资料:


: O1 i, J- v# M, E+ i第37题,在表结构中最常用的是线性表，栈和队列不太常用。
+ K2 x# w. v& P) z2 TA、错误
' k9 s% S1 b' w, X7 PB、正确
正确资料:

- y6 P$ R) T4 G0 ?8 Y4 Q% A
第38题,一个栈的输入序列是12345，则栈的输出序列不可能是12345。
A、错误
4 N4 q9 y$ ^0 J1 a4 U. AB、正确
/ o1 N. ?/ ^7 W; d# k. ^1 H7 L正确资料:


" n. q$ c) f- Y0 P( b第39题,二叉树中每个结点的两棵子树是有序的。
A、错误
, M  g" v  }2 G& b# F7 U5 H, n5 wB、正确
" g  Y, T1 S% F; Y1 {正确资料:

) |* p: x/ s2 b9 F
$ E+ a6 H) o& x! n. j( Z8 D. |6 \第40题,栈和队列是一种非线性数据结构。
- {3 b; M9 J7 z! Y0 _- FA、错误
B、正确
正确资料:
) c0 g' \' N) Q" Y  v

' @/ R8 j+ D$ {; S1 u* h, q% q第41题,链表的物理存储结构具有同链表一样的顺序。
+ h; l0 Y3 H7 a/ E7 h6 jA、错误
B、正确
正确资料:

- T5 L0 e+ N0 Z0 M
) S# T- _1 l% Z( ~) Y4 E( T/ f第42题,具有12个结点的完全二叉树有5个度为2的结点。
A、错误
B、正确
正确资料:
; n8 X5 Z2 O9 x5 N# f3 i$ i, G
8 P! j" b0 \& h/ Q; T9 e/ p
- ^  E  @4 l/ \# O+ I6 Y第43题,用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
" Q$ [. w& Y9 ^  X% y5 b! V6 N5 HA、错误
B、正确
正确资料:

0 a( h* X; A; L) B  K9 _( E
  G- @. ]+ r6 g9 R# W第44题,栈和队列的存储方式既可是顺序方式，也可是链接方式。
A、错误
B、正确
! q3 m* M; j" z% u% f, N3 l& j正确资料:
0 \  ]+ r5 j( ^$ [& y3 m
7 H) C1 g3 M! ?: [2 b, Q0 j
7 `; a$ N- C6 I; k. O) n5 C第45题,线性表的逻辑顺序与存储顺序总是一致的。
A、错误
B、正确
正确资料:
  o9 k+ o( ~7 P# K: S7 d

& p2 E" @- ?  u9 t" z7 m第46题,线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
A、错误
8 h" f5 M! w% B! ^8 i4 jB、正确
" |0 ^& T  d7 V$ O8 g) D正确资料:
8 @+ L& i4 n/ P8 T
: ^6 r5 [% P. R6 ~/ x
; Q/ M1 n1 G! r5 ], q/ U) K* ~* d第47题,两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
A、错误
B、正确
正确资料:
( d2 r  |: d- i$ T  a7 p) X
* Y+ R. p) C# ~" i/ R
% V% }' N7 E' C5 G& r$ O3 `第48题,顺序存储方式只能用于存储线性结构。
- [( Z2 T1 t4 f2 E& QA、错误
B、正确
正确资料:


第49题,顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
A、错误
B、正确
- C) x9 v. M5 e' p% f. h( x/ Q正确资料:
& f/ w7 T; f, Z2 p1 ]

资料来源：谋学网（www.mouxue.com）,二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
A、错误
2 K1 i$ i( I2 R* e6 ^! q  tB、正确
* s# y% d& q# _8 e2 a正确资料:
6 j2 ]1 t( ?+ S% z( v9 T% j
- x1 Z; n7 o, G. ]" k


0 }$ ]2 X: m, r) h8 i


& t0 i4 l0 _* `+ m

2 {1 X- M5 x6 l/ y3 ^" R( i



, J# J6 N0 G6 ^0 ^4 y* F$ s3 ?- I7 t. l& }