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

admin

资料来源：谋学网（www.mouxue.com）-[南开大学]21春学期（1709、1803、1809、1903、1909、2003、2009、2103）《数据结构》在线作业
6 N1 F0 t; h" D4 y: f: `3 _试卷总分:100    得分:100
5 @5 z  L) C; @( N& Q! |第1题,一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是()
A、110
7 X! I# u) G4 m+ K! q  mB、108
C、100
* ?3 x7 S3 ~# F, i; d0 DD、120
正确资料:
  `' J+ s$ X( j& w

第2题,链表是一种采用        存储结构存储的线性表
A、顺序
B、链式
C、星式
D、网状
* G& q. Z  I& ?: h* z$ @4 x正确资料:


第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))的结果串是（）
# U3 s- ?6 `; ?3 M7 BA、BCDEF
* p+ S# f* q3 R% W4 @  z: DB、BCDEFG
C、BCPQRST
D、BCDEFEF
- o  \2 |4 P$ e; _+ x$ \正确资料:
7 U3 |  L/ q' D# T  T4 Z
, ~( f- q: a. G0 p& U8 z& s
( T  n5 V7 Y" A/ M1 v7 l+ i+ e5 J, C第4题,堆的形状是一棵()
5 R8 ^2 X1 I# H" bA、二叉排序树
- s. ?6 M" T* n# x6 w; N, r# Z4 N/ lB、满二叉树
" M+ O* |" v9 B8 {C、完全二叉树
D、平衡二叉树
正确资料:


7 X; U+ [! V* S: f5 H* \8 ?资料来源：谋学网（www.mouxue.com）,对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是()
1 s' O$ v" u" O' a4 }! VA、O(n)
$ N* [& m1 E' U% @7 Q9 R; n. iB、O(n2)
' m7 r5 |/ K0 V9 x5 `C、O(nlog2n)
D、O(n3)
1 e2 I+ n, S* V正确资料:

8 q1 r' R. Q/ D: J
" \) c# L1 V# o" W# h( }; O第6题,二叉树是非线性数据结构，所以（）
, o. s# P% t& r4 \9 E" lA、它不能用顺序存储结构存储
  R  V' j# w" F# A) D4 N7 @B、它不能用链式存储结构存储
- k" W0 X+ D2 M3 rC、顺序存储结构和链式存储结构都能存储
D、顺序存储结构和链式存储结构都不能使用
/ F- l# P8 }+ k+ V正确资料:
/ g3 s2 p7 X% l# a
, w) ^. `) L$ c; i2 C5 M6 {
) L' Q! F" T5 d/ n$ _  Q0 A: S第7题,从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为()
9 K* ]; [; G5 _  a1 f, O1 E# QA、希尔排序
% [9 G. s1 D& R1 }) \) c( [' {B、归并排序
. {6 w! w8 H7 Z% Y1 l% BC、插入排序
: Z3 R( q) V5 z* E) J' KD、选择排序
' Z# I" a$ b* o. F正确资料:
* I2 v- O+ J# g! M& r& B

第8题,一棵具有 n个结点的完全二叉树的树高度（深度）是（  ）
A、
B、
- d  m& r& C0 {: ~6 G' x1 gC、
D、
正确资料:
8 f+ x- j5 p- \! H8 |, T  C4 b
% v: H( @) _7 q/ N
9 ]5 h- p* F1 z7 A第9题,对22个记录的有序表作折半查找，当查找失败时，至少需要比较()次关键字。
A、3
B、4
- G: Q4 p% J; o8 _( K- UC、5
D、6
正确资料:


资料来源：谋学网（www.mouxue.com）,已知图的邻接矩阵，根据算法，则从顶点0出发，按深度优先遍历的结点序列是（  ）
A、0 2 4 3 1 5 6
) O+ o8 ?* {; l2 cB、0 1 3 5 6 4 2
C、0 4 2 3 1 6 5
* C- T* T$ A+ h# }9 w/ X6 x/ xD、0 1 3 4 2 5 6
4 \7 q+ Y* o. |0 L4 u正确资料:

3 G+ j; K6 {0 K7 h4 J( M+ W
第11题,数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为()
- t& a7 H* m( H- K/ @5 P$ u) mA、存储结构
6 E4 V1 E5 {( _( _B、逻辑结构
# }. F6 t5 h  r# m% D4 B# \7 pC、顺序存储结构
D、链式存储结构
/ O) I1 v- b. `+ h' e正确资料:

% a# c5 r5 y) ]: b* m( R
资料来源：谋学网（www.mouxue.com）,有8个结点的无向图最多有（）条边
A、14
B、28
C、56
D、112
% T/ t# b/ @0 t4 S" g2 v正确资料:

' |; u9 Y) A$ t9 O
5 j. Q7 U7 s+ j- P- f) q2 ~第13题,下列关键字序列中，()是堆
" M2 D; R  o' o( pA、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
正确资料:
6 \/ {( p; T% Q

+ v3 ]4 c0 Y- R+ {第14题,若已知一个栈的入栈序列是1，2，3，...，n，其输出序列为p1，p2，p3，...，pn，若p1=n，则pi为（）
- K5 L. g) @; SA、i
B、n=i
C、n-i+1
D、不确定
正确资料:

  N# o$ ]# Z  \- p/ x! m& i( ?7 m
资料来源：谋学网（www.mouxue.com）,深度优先遍历类似于二叉树的()
A、先序遍历
B、中序遍历
C、后序遍历
  W7 w# k/ ]8 o# HD、层次遍历
正确资料:

4 X8 v/ J/ V( j4 W4 i
第16题,线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）
' L, x- a/ f3 P0 Z. e* DA、必须是连续的
8 L6 x+ |( D) s0 g  uB、部分地址必须是连续的
C、一定是不连续的
# p$ Q0 Q3 d4 C  C4 }' ^" ND、连续或不连续都可以
  m/ K- @  f7 G* W% j$ j0 @$ ^# p正确资料:


第17题,具有n(n0)个结点的完全二叉树的深度为（  ）
' n; \8 i" ^4 e, bA、
" B0 N! H7 D; F# a2 l. j( u6 P/ `B、
; b  B+ P0 ~* XC、
D、
正确资料:


第18题,设有两个串p和q，求q在p中首次出现的位置的运算称作（）
A、连接
# m$ s7 o& o1 d! OB、模式匹配
C、求子串
D、求串长
正确资料:


( G& u$ H: R5 {第19题,有8个结点的有向完全图有（）条边
9 @6 B9 P0 K! T( bA、14
B、28
C、56
D、112
正确资料:
3 z4 x# p4 t1 d- ?

% T" q! y+ ?" X% ]1 F. F: g6 @资料来源：谋学网（www.mouxue.com）,已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（）
A、0 1 3 2
0 A3 Y0 N( Z! QB、0 2 3 1
* e6 u8 r' \8 H6 I  A4 t% Z$ kC、0 3 2 1
D、0 1 2 3
正确资料:

, F, O% P9 G  B3 }" L: e/ b
第21题,用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的
4 \! d+ V3 f  b% ]4 ~! P; MA、栈
+ ]' y+ Q" B5 i( B" w3 s1 KB、队列
C、树
D、图
# z: K1 K0 x4 k/ z% b& V' G正确资料:

& ^# p) K) l. M1 J! V' p
/ `' D9 S* I& }, ~/ l第22题,已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ ）
' \; \0 M& `% N7 r0 fA、0 2 4 3 1 5 6
0 Z3 F0 k6 o$ v$ f* E. O* TB、0 1 3 6 5 4 2
C、0 4 2 3 1 6 5
1 v/ Q$ ]3 B  X3 A1 N/ r9 qD、0 3 6 1 5 4 2
正确资料:

% A+ ^8 Y+ _9 i/ ~5 G/ _
第23题,在表长为ｎ的链表中进行线性查找，它的平均查找长度为（  ）
1 `8 I& ?+ \7 B* OA、ＡＳＬ＝ｎ
B、ＡＳＬ＝（ｎ＋１）／２
C、
D、
正确资料:


- t! T7 c: V9 ], c, [8 M4 @7 S" o第24题,在一个图中，所有顶点的度数之和等于图的边数的（）倍
A、1/2
B、1
C、2
* J+ X  x6 q' x) d9 P1 hD、4
$ Q/ g: ^0 q( M正确资料:

  [! g' I! I6 }6 F
# G: V6 ]" e4 o资料来源：谋学网（www.mouxue.com）,向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素
2 ]5 G  e/ F1 x- Q% NA、8
B、63.5
9 A8 j- [9 v* Z. CC、63
: l8 e/ a* S' M# E3 p# {4 l5 LD、7
正确资料:

, q/ H3 ~7 ?/ E+ F( p( W
第26题,已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）
- Z  c, y! D& V. X& A3 Y% ]A、0 2 4 3 6 5 1
5 g9 @- v& k% ~7 r! T" OB、0 1 3 6 4 2 5
C、0 4 2 3 1 5 6
# k* e/ v, B  `, j& iD、0 1 3 4 2 5 6
. u  U4 h* g6 E; N% k  \正确资料:
- E" f1 `# x4 n

5 x$ s6 M" s; g4 C; l0 M第27题,广度优先遍历类似于二叉树的()
A、先序遍历
B、中序遍历
C、后序遍历
" K; ?7 P. m, DD、层次遍历
正确资料:


/ ~' t9 A; H4 M. _$ v/ k. \第28题,排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为()
- p; k  `* X" P1 \) ]0 l- I! L' I' b2 hA、希尔排序
2 w6 b) I  e+ ^2 w9 z5 ~B、冒泡排序
C、插入排序
+ X) T0 s0 u/ E  X( K* M5 ^D、选择排序
" c5 F% M; \5 y: E正确资料:

& q4 I) {$ ?& B* _9 q! {4 E8 o& Y
第29题,栈中元素的进出原则是（）
6 g/ d# D7 C8 A- E0 r' w3 aA、先进先出
B、后进先出
C、栈空则进
& B& p1 @1 f+ q, K+ [D、栈满则出
7 c1 J, Y" u! A4 J( h正确资料:
5 A4 C6 W. C. `% C, m* `
* W) Y# ?# ?9 l4 s9 l3 t, H# S& [
资料来源：谋学网（www.mouxue.com）,设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）
8 ]4 R8 I; r. U- A0 P7 |A、循环链表
B、单链表
C、双向循环链表
D、双向链表
正确资料:

; f) N) s6 z* I# ~. Y8 v
: m. `+ }$ X- @* W' A$ P9 }第31题,栈和队列是一种非线性数据结构。
A、错误
. i* `4 U% v- V1 wB、正确
& T* \% R- N6 B$ }$ H正确资料:

& P' W9 ], @5 ~) ?0 I1 }1 V0 b
第32题,栈和队列的存储方式既可是顺序方式，也可是链接方式。
A、错误
, e( `7 b8 Y0 R0 g$ u3 JB、正确
正确资料:
4 b+ l; M) l# v0 k; q9 o
8 P! A; `! A' K4 C% Y' z
/ U- r9 I( J" F, A' F: D第33题,两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
A、错误
2 e5 j9 k4 Z* j( S4 JB、正确
正确资料:
6 u3 F  Z6 J: j) M; P- {- q# U8 x

第34题,顺序存储方式只能用于存储线性结构。
; B: V' p" i& S/ z4 hA、错误
B、正确
* W; d9 T' V6 A; n9 I8 ^正确资料:


第35题,栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
+ ?. S2 s8 N8 Y# q# O* WA、错误
B、正确
& |! v- {& o/ M* ]正确资料:


第36题,线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
# j4 u! u& }) F, F; ^A、错误
8 y1 \9 k' u+ U, y4 x, n% HB、正确
2 j6 y) T, n0 F5 C4 \/ X5 H' S正确资料:

1 T# b3 j6 Z% N- o6 G3 H
第37题,二叉树中每个结点有两棵非空子树或有两棵空子树。
A、错误
B、正确
! V* I3 j; i0 w8 R8 N+ W- b正确资料:
" e: I  W) e  P8 ]* e

- T* ?: i* Y8 C  ]5 n" i/ ~8 E, I第38题,二叉树中所有结点个数是2k-1-1，其中k是树的深度。
A、错误
B、正确
7 Z, Q: e5 M0 X$ t; U8 X/ M* J4 v. Q正确资料:
6 ~/ x' J0 j. l: z- p! d  H

& ^: o; w7 B7 o. Y第39题,对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i-1个结点。
A、错误
B、正确
正确资料:
. P8 O* D4 ^) e' ~* |4 O8 ?7 r
; k% @. |, a6 i+ K: h& W2 R
  R. E8 o& z" s  ]  Y0 z0 s第40题,对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表
+ s/ n) f8 u$ N0 C8 P: a# kA、错误
B、正确
) i% y. G9 f5 {9 O1 y' U0 ?$ b1 l正确资料:

# I; b+ [2 V! C% s) c
; K" W1 O# K0 B; g第41题,线性表的逻辑顺序与存储顺序总是一致的。
8 v5 h0 R/ E/ TA、错误
  m& K7 C: k0 ?1 W, {6 V7 r' lB、正确
正确资料:


第42题,二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。
# u* B6 Z6 t0 D1 s) }+ p7 o9 SA、错误
+ c1 Q( n; G, ?$ z' OB、正确
- F$ c% A/ g3 {2 A& D正确资料:
: m! _3 e3 P, j- M

% X' R. ]' n. ^6 n/ X8 z第43题,链表的每个结点中都恰好包含一个指针。
A、错误
8 ^7 V) O3 s& z6 T0 ^) M& C8 B! cB、正确
% ?* ?. g2 A* {! I6 X0 z& O& M$ u& q& Y正确资料:

5 H  D; s2 r5 H  v1 j/ E
, w) `/ n0 E0 A7 |4 A第44题,在表结构中最常用的是线性表，栈和队列不太常用。
5 L5 j$ v9 B- i# ~. z4 r$ `A、错误
! {0 ^& P& \8 Z" e. }B、正确
/ {) W: i+ M0 d$ z. s; Z$ H正确资料:


  O! x( r7 E3 u/ X; H第45题,顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
* B6 S& _2 T' n" P" ]A、错误
" K4 B8 J( [4 @$ ~- w' n- Q8 TB、正确
, R- c( H* A2 Q' v4 g8 l正确资料:
1 p- ]2 o" j7 k# a
! d& h; `, N6 k. E
2 U% O" M; }- j第46题,线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
A、错误
B、正确
正确资料:

" Q' k. K+ e) x: h! O
' G: U1 I0 W6 q. P第47题,链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
" v. W' L+ g( p" U9 C8 a  u+ RA、错误
B、正确
! S( G2 h# `1 u6 Z" Q5 K- {正确资料:

- R& A5 v. A7 \6 I4 j7 [& v! V
第48题,栈和链表是两种不同的数据结构。
. I2 V  @& S+ xA、错误
B、正确
正确资料:

) g$ Q, ?$ Z) K4 K
& M" M$ R8 {# z! v第49题,链表的物理存储结构具有同链表一样的顺序。
A、错误
' U" }, }; w( C1 z% ]- C  LB、正确
4 t: h0 q  ?* p正确资料:

- K8 e$ |2 M0 R' Q4 l  d, k+ g
7 W, T" A& x' @$ c8 J资料来源：谋学网（www.mouxue.com）,线性表在物理存储空间中也一定是连续的。
4 v3 |  u0 W6 m" xA、错误
3 y$ q: s% Y& ^' T9 a  yB、正确
; C  h9 ?9 A$ R! a正确资料:

, S& D  H1 X9 }' T) Z" L2 n$ O
6 U8 h' M; N3 H6 a
8 s+ k& i4 j/ W# x# l7 t; p' |6 t* x

2 q. k4 O1 M6 h- I( m7 R# \

/ y9 f. N: B8 t# y) E

5 c: z$ a: T6 o) @

5 |* W' i1 Q" n1 _' T9 J4 z  z

! N9 M+ L( I5 c* `  i