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

admin

资料来源：谋学网（www.mouxue.com）-[南开大学]21春学期（1709、1803、1809、1903、1909、2003、2009、2103）《数据结构》在线作业
0 l, r$ Z+ h1 d试卷总分:100    得分:100
第1题,一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是()
A、110
B、108
C、100
D、120
正确资料:

; b0 I' q/ `/ k! \- ^+ Q# @
第2题,链表是一种采用        存储结构存储的线性表
A、顺序
& w1 N, b4 d+ V. aB、链式
C、星式
& h8 D0 u# U9 H# n1 L8 U6 wD、网状
# C2 v% @2 m7 k0 i- a. g$ u4 N3 R: U- A正确资料:
0 Y6 f* [9 y+ A3 g
  f8 ^( R$ R3 _+ G& f5 l- ]
9 n/ ]( O: {: ^1 u2 y* a0 s第3题,设串s1='ABCDEFG'，s2='PQRST'，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是（）
A、BCDEF
: X# n1 A+ g  p& [9 b; GB、BCDEFG
C、BCPQRST
7 H1 q& E3 G8 @1 {9 z- D: eD、BCDEFEF
& S3 s6 G9 V: N" v正确资料:
/ U9 b0 t) b4 T# ?
) e: F* Y# r( x0 X
2 M, ^; |- t) ?$ d9 D" I' a第4题,堆的形状是一棵()
6 s3 z( j5 |3 Y7 W5 hA、二叉排序树
- p* ?- b0 a% {  ^- j# j, A4 CB、满二叉树
9 J0 k5 z% k7 a4 bC、完全二叉树
' e9 c9 ~' k5 D  M1 ND、平衡二叉树
  n+ P6 s% O) g* @正确资料:

9 j7 t, f7 Z! u: b/ X
( M& T3 o& O* W  \6 L) u! P资料来源：谋学网（www.mouxue.com）,对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是()
A、O(n)
B、O(n2)
C、O(nlog2n)
D、O(n3)
正确资料:

$ f/ c. F; G. u6 @
+ y, [7 c) Q8 o5 b第6题,二叉树是非线性数据结构，所以（）
) m- k3 x* ~5 a; DA、它不能用顺序存储结构存储
: p/ d. |& H( U( T0 S( YB、它不能用链式存储结构存储
C、顺序存储结构和链式存储结构都能存储
D、顺序存储结构和链式存储结构都不能使用
正确资料:
+ C6 D# V& C/ f& I; B3 P9 u
7 X$ q5 C* L3 ]$ _, G
% R) [4 y2 w' d0 |2 y0 c第7题,从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为()
A、希尔排序
B、归并排序
4 y6 f! `$ g" g; Q$ D/ E/ P$ GC、插入排序
D、选择排序
9 o( `! t8 ^# ~! H& X5 |正确资料:
% s( g# F) H% W

% ]- q8 k- C6 N- P  s+ D第8题,一棵具有 n个结点的完全二叉树的树高度（深度）是（  ）
A、
B、
1 s0 Y6 a" Z* oC、
D、
正确资料:
! |9 ^& ?* `, H6 C5 C5 |* w
! F8 g5 u9 r; _4 I
第9题,对22个记录的有序表作折半查找，当查找失败时，至少需要比较()次关键字。
+ x4 z# c+ P1 o3 U: _A、3
B、4
4 d' T: M5 _1 J3 ~2 x; E2 f# q2 iC、5
& ^& k4 U% J* t+ sD、6
; L- [! R8 [& l正确资料:


* y* ]7 W% N5 c, z( f6 }& T, y资料来源：谋学网（www.mouxue.com）,已知图的邻接矩阵，根据算法，则从顶点0出发，按深度优先遍历的结点序列是（  ）
8 y8 N$ z! \7 Z! F# d8 A) x0 |A、0 2 4 3 1 5 6
3 c8 R2 ]# @5 U* t* @' UB、0 1 3 5 6 4 2
C、0 4 2 3 1 6 5
D、0 1 3 4 2 5 6
9 }* _5 E% ?2 V6 y  j+ J, z正确资料:
; Q: @) m( K8 \, @5 @

第11题,数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为()
A、存储结构
$ K1 q: d7 v8 ~* eB、逻辑结构
- \2 C$ n2 r# V/ t) SC、顺序存储结构
6 u$ p& g( K$ d! V* ?5 mD、链式存储结构
正确资料:


7 H% a* Y; k: k" G1 _资料来源：谋学网（www.mouxue.com）,有8个结点的无向图最多有（）条边
8 h1 t: X, e( TA、14
B、28
" A) D+ p9 M$ A* [5 k$ N5 _C、56
D、112
% }! T  g" P- F4 z正确资料:

1 ?7 ]- N- \  n2 N, u; l1 Z# B" A
第13题,下列关键字序列中，()是堆
A、16,72,31,23,94,53
B、94,23,31,72,16,53
- w- M' [: T1 {1 ]1 ]5 u/ E! NC、16,53,23,94，31,72
* {, S' G. K' a1 N1 tD、16,23,53,31,94,72
/ G, h8 J- \: O正确资料:
8 B! R9 d& A0 X) _" C* e

第14题,若已知一个栈的入栈序列是1，2，3，...，n，其输出序列为p1，p2，p3，...，pn，若p1=n，则pi为（）
: u" r! b) d8 s  M$ q& cA、i
B、n=i
C、n-i+1
D、不确定
7 F0 V! [. V* |, m2 B& z正确资料:
9 a6 v/ _' v1 `

. S3 E' q. [2 z/ C( P资料来源：谋学网（www.mouxue.com）,深度优先遍历类似于二叉树的()
A、先序遍历
! {; e( U; v1 _3 y/ M$ M# jB、中序遍历
C、后序遍历
D、层次遍历
正确资料:
+ l  G0 L* M/ n2 ]+ [

8 U: y$ t! y' v; c( A) w第16题,线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）
' I" d* v9 b5 o4 b' \4 vA、必须是连续的
B、部分地址必须是连续的
1 |( @7 y0 |3 A; U; n0 Z+ SC、一定是不连续的
D、连续或不连续都可以
- L! i; J+ W8 f/ s/ {正确资料:

6 b% `  @) E: F  w9 Z% S0 Y- K
+ `, J  H0 r1 x+ G! G+ ]* @第17题,具有n(n0)个结点的完全二叉树的深度为（  ）
% z& _- X/ i' v# |% A6 aA、
B、
C、
D、
$ g0 A+ f( ?4 A7 }7 J2 [正确资料:

0 i& e' y. k0 S5 P, ^
第18题,设有两个串p和q，求q在p中首次出现的位置的运算称作（）
A、连接
B、模式匹配
) s" _# w- F3 Z5 K/ D6 XC、求子串
9 V, p' n: ]0 M- E6 I) J/ x% |" pD、求串长
# e, {, g6 D2 n: N正确资料:
/ T9 l0 d9 `4 p6 d$ t9 ^" F

第19题,有8个结点的有向完全图有（）条边
A、14
B、28
  _. `0 i9 x) X2 ~. f1 _C、56
; k5 `8 G7 \2 @: z2 o) DD、112
正确资料:
2 u0 ]" H1 {3 ]( m1 |6 q

资料来源：谋学网（www.mouxue.com）,已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（）
  `7 _; p5 S7 G/ {A、0 1 3 2
/ N& }4 }" g9 v  r1 [3 _& g* ^# [6 }B、0 2 3 1
C、0 3 2 1
6 Y. [- Z0 h9 V( oD、0 1 2 3
正确资料:
; m3 b5 R/ M" z0 H. R3 I9 e

第21题,用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的
A、栈
B、队列
* o! H1 U: |  d. `+ t2 R* nC、树
' N  t; \+ ?/ aD、图
正确资料:

) w. U2 N5 c! c' R' B, e
第22题,已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ ）
" r' y* }- D4 DA、0 2 4 3 1 5 6
6 f: G$ T9 t6 f+ ?; TB、0 1 3 6 5 4 2
' J1 s4 I. D" I) V9 J, l" RC、0 4 2 3 1 6 5
D、0 3 6 1 5 4 2
) B8 I" \# e7 k8 w正确资料:
( q+ A) a0 `: j& D) B. H

% n4 {# b) ^( _  @5 V第23题,在表长为ｎ的链表中进行线性查找，它的平均查找长度为（  ）
4 y% [6 e, y& C2 [4 I3 T8 aA、ＡＳＬ＝ｎ
. u  b/ b2 L. y. c0 BB、ＡＳＬ＝（ｎ＋１）／２
C、
4 P- \: W* V) f/ w5 ~  BD、
正确资料:


7 O0 X6 _) V$ s- g0 E. i# {第24题,在一个图中，所有顶点的度数之和等于图的边数的（）倍
A、1/2
B、1
+ e6 x6 K. K/ j5 [! cC、2
2 o  U" I7 C* e" b, r' z- zD、4
. Z" {; y: ~4 Q正确资料:


  d2 J2 m& a% X9 Q  v/ o资料来源：谋学网（www.mouxue.com）,向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素
6 v9 N: B3 C/ ZA、8
) K( `) f4 B4 E1 I& DB、63.5
C、63
D、7
正确资料:


第26题,已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）
8 S9 P# C! }4 v+ [: w$ eA、0 2 4 3 6 5 1
B、0 1 3 6 4 2 5
C、0 4 2 3 1 5 6
+ m0 ?1 O' P) Z. g/ VD、0 1 3 4 2 5 6
( |" k( T0 X' L) [* U正确资料:


; y5 B7 z% ?$ b+ s% O第27题,广度优先遍历类似于二叉树的()
0 s& `1 v2 L! L; O/ z% e3 h8 s6 @A、先序遍历
B、中序遍历
C、后序遍历
9 E% D+ U/ G% p1 e5 ]D、层次遍历
正确资料:

5 F0 m' o# n) I* r* \$ }
$ \! r7 V8 P5 N) ~: d- b第28题,排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为()
A、希尔排序
# B( ~$ f' o0 D" \" J/ N/ l6 d; @B、冒泡排序
- L: I6 ?$ W. n1 {9 ?3 {* nC、插入排序
D、选择排序
# ~! r- e9 [% \6 H- w- n正确资料:
/ z$ P' b- @# {

第29题,栈中元素的进出原则是（）
0 L! O9 w: ~% S& HA、先进先出
B、后进先出
C、栈空则进
D、栈满则出
正确资料:
" ]' f9 c* r9 W. i  L# O" ^

6 a8 B6 R2 @3 S1 p% u" @. |0 h- Z资料来源：谋学网（www.mouxue.com）,设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）
A、循环链表
+ P; Q* x# B" w4 s' z3 Y9 u7 v0 kB、单链表
1 ?/ I6 r5 V. f: f& x% }C、双向循环链表
- C$ W& u. h: W+ c" BD、双向链表
正确资料:
! d8 [8 b4 E( G5 E5 W+ L3 u

第31题,栈和队列是一种非线性数据结构。
A、错误
B、正确
, I' U- t' x9 d/ N! |正确资料:
, ^& h6 X! c& q* ?9 m) N! R% P! C
6 C! e* `  a" d* x* r2 `
第32题,栈和队列的存储方式既可是顺序方式，也可是链接方式。
4 T. P8 @( V1 s! G" \A、错误
- @1 s% G" F4 ?& mB、正确
正确资料:

0 S# C' w8 \9 [+ s% r. l
' D1 U2 x9 }6 Z1 h% }9 K' T) v; m第33题,两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
$ J" Y- p$ o6 T3 N8 _A、错误
B、正确
正确资料:
3 e5 }9 {( I* D& T

8 {7 ^% {- t2 C第34题,顺序存储方式只能用于存储线性结构。
9 }3 H! E& k/ _1 T' J& |A、错误
, [: y" g' d5 a- H4 N  z* IB、正确
正确资料:
1 Z* L- y; C/ t& U6 T/ L# D4 B; Z

第35题,栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
A、错误
0 F9 M5 R& }. P" ]9 h2 jB、正确
正确资料:

2 |7 h  X% e. F9 O$ p  B7 Q
第36题,线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
A、错误
B、正确
正确资料:

. m. P& s$ H2 k# H8 _& `, c
! H5 g  v# G9 j/ [1 @  t( S第37题,二叉树中每个结点有两棵非空子树或有两棵空子树。
A、错误
8 _0 J9 k* y- v6 O! k; H7 rB、正确
正确资料:

" R! c/ D7 Q; M* I1 ?
第38题,二叉树中所有结点个数是2k-1-1，其中k是树的深度。
A、错误
B、正确
$ F6 C- V" C+ R6 K1 R6 V正确资料:


第39题,对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i-1个结点。
1 c4 C" N. b7 J& UA、错误
B、正确
正确资料:
) B2 W- n. v: m
. D  B4 c) }8 D
1 X" E, k# X/ C* x- Q# m/ V/ a' U" \5 z第40题,对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表
4 p5 ~; W" k# k) Q# ~A、错误
B、正确
正确资料:

; r/ j9 D8 n* ?% \
0 ^; i6 Q' O* i第41题,线性表的逻辑顺序与存储顺序总是一致的。
A、错误
B、正确
正确资料:
  q, A) ^5 P8 T

2 O: V* s) U4 ?1 k- a1 m第42题,二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。
4 c, F1 j, F1 ^6 v7 A: v! B& j) rA、错误
- ^4 N4 ?8 T% L0 Q+ ?/ pB、正确
; b8 M8 g% v% }# f  i" }) _2 n# C正确资料:

/ s4 t0 [7 y% h
% e% {! H/ N. M( {' t( j/ ~  ]第43题,链表的每个结点中都恰好包含一个指针。
A、错误
B、正确
' \* I4 M4 v& _+ ]5 N: S1 \正确资料:

& I- C# {. D4 x2 x/ `, V
第44题,在表结构中最常用的是线性表，栈和队列不太常用。
A、错误
& g% P% u" |. l/ y; B- ^4 k1 DB、正确
正确资料:


# [- I' K3 Y0 M" y' F6 W5 Y第45题,顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
A、错误
1 n! ?* O- w6 O6 l- a, vB、正确
* z, L+ \2 @5 W2 j5 @- ^正确资料:

$ R: ]1 Q3 \. X2 J! P6 A
) H# ~. N' `: Z. N$ x. W第46题,线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
6 v$ N( [, X0 T! aA、错误
5 K4 {3 E3 h; {+ N% IB、正确
正确资料:


第47题,链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
9 y8 _4 G. G( u8 m5 F5 vA、错误
, x2 c. Y( N: t) GB、正确
0 t- F% a8 d* S5 K8 A% w正确资料:
' `9 i+ F+ U5 e' m! i2 d
2 c2 G& f& z% ]8 X, C& m
第48题,栈和链表是两种不同的数据结构。
A、错误
( `& d1 m' p: l( Y: D8 R: xB、正确
8 G! Z) ]9 X3 P# n正确资料:
7 i, S& K8 S- w8 i% S

第49题,链表的物理存储结构具有同链表一样的顺序。
A、错误
' E. a) p4 q! J" N& n: k# ^B、正确
" P' T! q8 G% c; g& V* o* g( z2 M正确资料:


0 G6 ]8 q/ v% y( n资料来源：谋学网（www.mouxue.com）,线性表在物理存储空间中也一定是连续的。
! Z1 b% d/ g$ u% w5 I. M! c+ R# ]A、错误
+ j4 q  x( N3 b6 R( c& l0 ~2 {" MB、正确
) L( _5 t) }' m: |. [正确资料:
2 ~% v5 w0 D# X/ n8 U3 b


2 C; ?4 T2 ~7 c+ a) {# j
6 H$ s5 E8 b4 d



) c1 F$ o9 ~7 ~8 K- b


( {" a3 K- f4 L; q  K: C6 i

1 q/ w0 D& ?3 |0 j" |' I