[南开大学]21秋学期《数据结构》在线作业

admin

资料来源：谋学网（www.mouxue.com）数据结构-[南开大学]21秋学期（1709、1803、1809、1903、1909、2003、2009、2103）《数据结构》在线作业
试卷总分:100    得分:100
第1题,有8个结点的有向完全图有条边
A、14
, |4 y9 C$ Y, k9 a3 OB、28
C、56
D、112
+ v9 Z6 |8 j* O正确资料:


第2题,已知一棵二叉树的前序遍历结果为ABCDEF中序遍历结果为CBAEDF则后序遍历的结果为
/ w, |5 c+ ^( i) K  i( J9 tA、CBEFDA
+ T( {6 [3 O$ @B、FEDCBA
2 _5 W, j+ W9 l9 m& a' u9 MC、CBEDFA
# M6 n6 g# f8 |' N- o* C7 n) w7 C9 s/ vD、不定
正确资料:

* ]( c# Q% b" i. ?+ K2 }8 j" u
2 n) e- e/ [5 m  {5 {  F! E1 m第3题,若一组记录的排序码为467956384084则利用堆排序的方法建立的初始堆为
( J0 u- [2 ~' f7 ^8 v1 BA、79,46,56,38,40,84
B、84,79,56,38,40,46
* t+ n) a, O' A5 pC、84,79,56,46,40,38
D、84,56,79,40,46,38
. y: w; ]6 B2 o: x. `2 h' V正确资料:


: @; ~3 I4 _# Z2 r, p- l- n; e3 Q第4题,对ｎ个不同的排序码进行冒泡排序在下列哪种情况下比较的次数最多
A、从小到大排列好的
B、从大到小排列好的
' l7 O% c: U3 tC、元素无序
D、元素基本有序
正确资料:
$ f4 l, `6 [0 n% _1 L6 r
# ?( V$ t- Y( H. |8 _' z. C9 Z
资料来源：谋学网（www.mouxue.com）,设有两个串p和q求q在p中首次出现的位置的运算称作
# M5 U2 U  O# H% I; \( n! qA、连接
$ D/ A7 a0 ?3 h' E* z8 ^3 yB、模式匹配
0 M7 t( p6 y9 y/ A. i; NC、求子串
D、求串长
* f! W- P* C. E7 f/ Z3 ]正确资料:
2 U" k& v( O6 F  ~4 v! h% m

第6题,在n个结点的顺序表中算法的时间复杂度是O1的操作是
A、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
3 A$ h( g, S/ v) e9 MB、在第i个结点后插入一个新结点（1≤i≤n）
C、删除第i个结点（1≤i≤n）
D、将n个结点从小到大排序
' o6 d, `! Y# r0 l9 i正确资料:


: r0 @- O" X6 r( x. o% f第7题,二叉树是非线性数据结构所以
$ W: T1 {) z1 X, BA、它不能用顺序存储结构存储
* S) j0 @5 g. w8 [. L* }2 dB、它不能用链式存储结构存储
& `/ [8 e+ Q" ]. {C、顺序存储结构和链式存储结构都能存储
D、顺序存储结构和链式存储结构都不能使用
  Z; ]- p6 ]. O7 q" l正确资料:
- X) ?- A+ h( [! E0 V) \: |
- N6 u9 }8 O$ r" t5 V# a! e# x
第8题,具有nn0个结点的完全二叉树的深度为
4 V+ T; }0 m3 y& |/ `A、
B、
( v+ a' a8 ?0 E8 @) @C、
D、
) j% f+ _1 ^! |$ u$ n/ n% F正确资料:

, b1 R5 M; V5 P3 \
5 g# m$ O; T) T第9题,用邻接表表示图进行深度优先遍历时通常是采用来实现算法的
A、栈
B、队列
: e; b3 p8 \9 H, C! ^$ s$ i' LC、树
* a4 r0 b" o! q. i, D  z& HD、图
5 t* b& D! I  d8 y/ R, v正确资料:


资料来源：谋学网（www.mouxue.com）,若已知一个栈的入栈序列是123...n其输出序列为p1p2p3...pn若p1=n则pi为
) f+ y4 [& c& ?$ f( SA、i
' b$ z+ a* Q1 u& u4 s4 D/ K' f! eB、n=i
C、n-i+1
D、不确定
" Q0 d6 Q# K3 }* R+ N正确资料:

& F& w. w/ E6 w& I% C5 H! D2 B
第11题,堆是一种排序
A、插入
B、选择
9 I- n/ {# v' l* R& jC、交换
D、归并
: n- v0 o, |# ]# T2 g8 a0 @2 A正确资料:


! Y, o% y4 k! ~! S6 H1 h, B7 a% j资料来源：谋学网（www.mouxue.com）,下列关键字序列中是堆
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
正确资料:

- s# ]9 O6 S% V
第13题,已知图的邻接表如下所示根据算法则从顶点0出发按深度优先遍历的结点序列是
- V3 f& X8 a& i& r, h, V: UA、0 1 3 2
) W$ b- p& T! l( W! Q- T" ?# I- nB、0 2 3 1
C、0 3 2 1
D、0 1 2 3
# q6 H5 N- K& M正确资料:
$ W0 @: J) {; @$ x2 g# ]
/ I2 V8 T  C* j
( `+ a" {& P( S7 J% r" v2 }第14题,数组Ｑ［ｎ］用来表示一个循环队列ｆ为当前队列头元素的前一位置ｒ为队尾元素的位置假定队列中元素的个数小于ｎ计算队列中元素的公式为
A、r－f
B、（n＋f－r）% n
C、n＋r－f
D、（n＋r－f）% n
6 j, n1 w+ @; M& D$ n  M0 v5 j正确资料:
1 R- b+ a! n+ \9 ~% D! F6 A
5 {5 S/ p" [0 @8 L( b3 C
3 i5 Z0 W/ I( D& p资料来源：谋学网（www.mouxue.com）,折半搜索与二叉搜索树的时间性能
2 J9 K3 V2 f) u. h* y2 b+ EA、相同
B、完全不同
$ D0 I; ^; @+ d6 ~' ^/ q+ b9 ^C、有时不相同
. T/ F' W4 y* V4 |# h, J/ h; xD、数量级都是O（log2n）
正确资料:
% F& E  O9 i6 ?* g5 {0 M7 Z, V
, Y- c( _5 S) d
6 ]0 `. H! |3 M& ?' }' F0 h# f& ~第16题,栈中元素的进出原则是
A、先进先出
B、后进先出
# B$ ]" S) K& q$ BC、栈空则进
. y' W" w; i6 W- `* S1 g( eD、栈满则出
8 O9 r0 [' l$ P! W' d正确资料:
8 P" @& J+ o( Z* }0 a6 I

第17题,已知图的邻接矩阵根据算法则从顶点0出发按深度优先遍历的结点序列是
3 e/ U4 b9 I' {7 l3 A/ X1 e0 sA、0 2 4 3 1 5 6
3 i3 w+ A. u1 T7 ?" ^4 _0 FB、0 1 3 5 6 4 2
  \1 s- X) J; }; Z0 q+ B& L' RC、0 4 2 3 1 6 5
D、0 1 3 4 2 5 6
* s2 h3 u. Y, T3 N3 Z5 v# C8 ]正确资料:
$ [- N- G6 k" X2 [. g, N& b

# n! S* o/ O5 |: ]. r& L第18题,设a1、a2、a3为3个结点整数P034代表地址则如下的链式存储结构称为
) W6 H8 @& K+ g3 s1 h; g& sA、循环链表
B、单链表
8 {8 B% X- q; W" p( k$ t0 MC、双向循环链表
" K+ z& p0 n  M4 j0 ID、双向链表
正确资料:
& w/ ~6 L# L) e' u0 O- V2 ]( p
% d% Y' b% Y0 `' R8 O
' T+ {0 K$ A$ z! h: b6 g第19题,已知图的邻接表如下所示根据算法则从顶点0出发按广度优先遍历的结点序列是
A、0 3 2 1
B、0 1 2 3
C、0 1 3 2
D、0 3 1 2
: ^1 f3 [4 C) a; s6 A% W% h9 ?& F8 p正确资料:


; X% Y- C* G) D7 |) f资料来源：谋学网（www.mouxue.com）,在一个图中所有顶点的度数之和等于图的边数的倍
A、1/2
B、1
+ [8 c6 |6 u( D- f, vC、2
& F' X, S+ y: [7 F& C3 V% cD、4
2 f7 _/ `5 ~1 f& |" s( V0 |) ~& @正确资料:

2 J. d) }( z/ F
# M8 K' q; m% A/ V第21题,链接存储的存储结构所占存储空间
A、分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
. b$ y0 ~5 q, wB、只有一部分，存放结点值
C、只有一部分，存储表示结点间关系的指针
- r1 K& i7 n2 b% L+ S7 cD、分两部分，一部分存放结点值，另一部分存放结点所占单元数
4 L) M/ }+ s; d: S! @正确资料:
- Z) C9 A/ M, P* i

第22题,已知图的邻接矩阵根据算法则从顶点0出发按广度优先遍历的结点序列是
A、0 2 4 3 6 5 1
- M' n# z  r; n, e& pB、0 1 3 6 4 2 5
C、0 4 2 3 1 5 6
: Z2 U  B' h. eD、0 1 3 4 2 5 6
* `, g5 R! @( I* Z# j# _4 f正确资料:
& o# V3 a6 X$ _* S- S, E* x
% A2 V* t# S* B' a( T! y7 T
" e% W5 `# R: `第23题,向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变平均要移动个元素
8 D# J( r# E  c' w. v/ {+ YA、8
B、63.5
+ E( i( m, t# I# l/ a1 MC、63
; U) C  i7 s& E- LD、7
正确资料:


第24题,从未排序序列中挑选元素并将其依次插入已排序序列初始时为空的一端的方法称为
3 q( Q9 }8 Y5 {. W* UA、希尔排序
B、归并排序
. E0 L1 A- A6 O. p7 MC、插入排序
+ d& e- p* C: D# p% h7 h; i8 `) CD、选择排序
# r' H3 R2 f, w( K# ~正确资料:
/ s& \$ W4 L' W6 {" j( i* i

资料来源：谋学网（www.mouxue.com）,对22个记录的有序表作折半查找当查找失败时至少需要比较次关键字
A、3
7 ~* O# O/ q& Z, UB、4
C、5
D、6
正确资料:

9 {, Z+ T- D$ N9 |; R, C
# I# ?! ~: z* K0 G) L4 F8 D第26题,已知图的邻接矩阵根据算法则从顶点0出发按广度优先遍历的结点序列是
A、0 2 4 3 1 6 5
8 Q! T# F+ |4 n/ S- v! ?0 sB、0 1 3 5 6 4 2
6 C0 D7 R% Z2 ~C、0 1 2 3 4 6 5
. ?5 {4 h/ s" YD、0 1 2 3 4 5 6
0 |+ y% @' Q, C2 b9 _. l4 D& X9 z正确资料:

5 J3 `6 {! E( M$ B( Q) p; N9 ]2 ^
第27题,单链表的存储密度
A、大于1
" h! z5 G3 d) c6 j- s6 E0 JB、等于1
C、小于1
D、不能确定
7 ~0 ~  ?; `, W4 T9 y正确资料:
! f8 K1 X* e6 F2 Y3 D

* I, L4 C4 Z5 P- f9 K- M( S第28题,在表长为ｎ的链表中进行线性查找它的平均查找长度为
; g: q; J( _! |1 J1 c- ^1 KA、ＡＳＬ＝ｎ
" r" z4 z# E4 O0 M7 S/ b0 `3 j, e$ VB、ＡＳＬ＝（ｎ＋１）／２
' C9 x$ d( w8 x+ dC、
. z' D9 @8 {$ a4 |D、
正确资料:
- |( Z* B1 r5 H" K2 ^* N2 R: N
4 m8 H0 p/ I0 K( R0 D  b# ]. |
第29题,堆的形状是一棵
A、二叉排序树
B、满二叉树
C、完全二叉树
0 N, a: z7 E0 @1 ~/ @0 {D、平衡二叉树
正确资料:


" [, E( g5 Z) @资料来源：谋学网（www.mouxue.com）,深度优先遍历类似于二叉树的
A、先序遍历
B、中序遍历
3 S0 d" ]1 n! u4 |2 r( m' f0 JC、后序遍历
$ M  Y5 m0 g; c( S  _) WD、层次遍历
正确资料:


1 w9 _# i0 k3 a- x1 V! \' v# N$ t6 t第31题,一个栈的输入序列是12345则栈的输出序列不可能是12345
: E  ~6 y! \2 pA、错误
( G. U5 L4 u$ P4 N! SB、正确
) y: a3 C9 E8 u* u4 c( c正确资料:
; x+ L  `0 Q( @+ N( E

第32题,在表结构中最常用的是线性表栈和队列不太常用
0 ~% w+ k) n, m" d- z$ y9 VA、错误
8 h7 ~; J# k# d# ^B、正确
正确资料:
, M9 k/ d0 d) z+ }
6 P( h) d2 T, ?& t% m$ Z8 e
4 c& p( j. N/ p( _, N1 P第33题,二叉树中所有结点如果不存在非空左子树则不存在非空右子树
* z! H, _0 ]7 q# ~6 Y6 h  g* S1 X, U- fA、错误
1 d. F7 }1 v" \% MB、正确
5 g2 W1 m' r1 j正确资料:
8 j+ e/ I1 K4 R4 ~7 X

第34题,链表的物理存储结构具有同链表一样的顺序
A、错误
9 a3 D- _0 j' qB、正确
正确资料:


第35题,二叉树中每个结点有两棵非空子树或有两棵空子树
A、错误
6 x  G# [+ o& l! J8 k8 Y$ Q, S) f6 |B、正确
. e1 P8 H4 ]- e) a" \正确资料:

- w2 o6 c, j7 u
第36题,二叉树中每个结点的两棵子树是有序的
: g9 V* Z, k6 g& M* Q! QA、错误
1 w# e( z1 W% U( u# b1 AB、正确
# N8 y( A% g1 H( U  s/ q! t3 W# \正确资料:
0 c- r" Z3 ^0 [
, v+ f# [. s% X6 t) ?& ~
第37题,二叉树中每个结点的关键字值大于其左非空子树若存在的话所有结点的关键字值且小于其右非空子树若存在的话所有结点的关键字值
$ w/ i% p; q2 \  aA、错误
9 N, y" C. Q1 J- G, U! \7 d9 gB、正确
7 H1 c, I2 e0 `8 M正确资料:
4 i& q5 w: e1 c& q4 O% B" q, ~
: I6 z0 d; B& p( r
第38题,顺序存储方式的优点是存储密度大且插入、删除运算效率高
  \- r3 i- H/ D- M1 BA、错误
B、正确
正确资料:

# G6 T# B) }1 B" u4 A9 Y" H! j
, a! ?# C* }0 V0 r9 ?- S$ ?4 s+ Q第39题,栈和队列的存储方式既可是顺序方式也可是链接方式
9 q: x! o- y' W. e; r8 }& OA、错误
6 P+ M& }% g4 Q! e2 }B、正确
正确资料:

8 P/ X- V) ^  j8 h9 v
2 a6 E9 W: k) S4 p: k/ |5 F第40题,对于不同的使用者一个表结构既可以是栈也可以是队列也可以是线性表
A、错误
B、正确
. x8 n+ f  Z: R* P正确资料:


0 M3 E0 ~4 H# i2 I. k第41题,对于一棵非空二叉树它的根结点作为第一层则它的第i层上最多能有2i1个结点
A、错误
& Z- ]3 H9 v! T5 PB、正确
: T- O/ J3 G: v$ u6 S正确资料:


" X; F  M6 k/ e9 [$ O' X0 V第42题,具有12个结点的完全二叉树有5个度为2的结点
A、错误
/ W/ W% G5 U/ oB、正确
+ C# z4 u2 F+ n  T正确资料:
, Z1 S: K5 [4 p/ o  M. E& E" B0 Y" F

第43题,两个栈共享一片连续内存空间时为提高内存利用率减少溢出机会应把两个栈的栈底分别设在这片内存空间的两端
A、错误
B、正确
" X& T% j6 D! V* Q7 _3 L正确资料:
3 M6 `/ l) q2 F' S( {/ W0 Z5 @5 J

第44题,顺序表结构适宜于进行顺序存取而链表适宜于进行随机存取
A、错误
+ r7 ^  h! @% E# \( j1 s! q, TB、正确
2 H# a; W& i8 B& S/ q0 ]# O正确资料:


, w# a' J* J% D! y: L$ F第45题,二叉树中每个结点的两棵子树的高度差等于1
$ ~5 p' o; Z$ g2 W1 |A、错误
, n% t- z' H- Q1 {. |& L3 FB、正确
正确资料:
. L+ Z1 k* G( X# O( a

第46题,线性表的逻辑顺序与存储顺序总是一致的
A、错误
B、正确
正确资料:
' {: B. V4 G1 j. v

8 L, A( U- L, v3 J9 s第47题,用二叉链表法linkrlink存储包含n个结点的二叉树结点的2n个指针区域中有n+1个为空指针
A、错误
B、正确
正确资料:
9 j1 n5 `* L2 ?, b1 O

第48题,栈是一种对所有插入、删除操作限于在表的一端进行的线性表是一种后进先出型结构
A、错误
B、正确
正确资料:
# Z2 q+ p+ \, S4 n

( N9 M9 T. W( ?第49题,线性表的每个结点只能是一个简单类型而链表的每个结点可以是一个复杂类型
. t) L2 |- ?6 ?- {7 {; l& x9 oA、错误
B、正确
正确资料:
, o4 Q  y5 ^% n2 F/ @# l: ^

资料来源：谋学网（www.mouxue.com）,栈和链表是两种不同的数据结构
# l2 {, u% r) q5 I$ e( `' ZA、错误
B、正确
正确资料:
) R& G( ^4 ~; V( C6 x
8 i0 v. y  n/ r! M, ^2 \3 k
/ |5 y" @/ W: A' F& |( `
' u% I* d, y; F# G! }7 I* j4 x- n6 c
/ Q! u" X% y2 p( l/ u+ w
$ c2 y. e8 U* A3 d






' z6 m/ B- f" J- p
5 w1 i, j; E3 v7 [3 l# ?  D
. i7 Z1 K$ c6 z5 \6 a/ N5 G7 r. T+ A