22年春东北大学《数据结构Ⅱ》在线平时作业3-1

admin

资料来源：谋学网（www.mouxue.com）数据结构Ⅱ-[东北大学]《数据结构Ⅱ》在线平时作业3
试卷总分:100    得分:100
第1题,在待排关键字序列基本有序的前提下效率最高的排序方法是
A、直接插入排序
B、快速排序
0 a2 {8 N8 g. G9 s: L, WC、直接选择排序
6 _8 L1 z  R* L  e, w) Z8 q5 xD、归并排序
" V5 F9 k) A3 ]正确资料:
8 l0 P) j' F* X% g/ r$ _9 t+ ?$ x

# G& Y3 {; I, q第2题,一个具有1025个结点的二叉树的高h为
A、11
) n2 u$ J6 c8 O9 K) G& }B、10
% C. _: B) h4 T# A+ A' z4 p% O7 T& sC、11至1025之间
/ K* O; n. z' P: k0 FD、10至1024之间
正确资料:

( ]* B; C  D% E) M
第3题,已知含10个结点的二叉排序树是一棵完全二叉树则该二叉排序树在等概率情况下查找成功的平均查找长度等于
1 B8 a+ g" A: ^# l% W6 I4 }A、1.0
B、2.9
C、3.4
1 t6 Q0 M6 f6 A" Z7 qD、5.5
" {, E; ~3 b/ D0 T( h% M6 _4 v正确资料:
3 k* N$ K5 Z. s0 j/ }1 B, }
& ?/ `, v, R7 I  Z* t
第4题,一棵树高为K的完全二叉树至少的结点是
" D$ g! P' j$ i+ V. o- ZA、2k -1
, K6 @  |" R( G0 K# o) OB、2k-1 -1
C、2k-1
D、2k
- g8 Q/ p3 g& O正确资料:
; x5 z5 E$ ?. f% C3 T, x

+ {& i, v3 A6 U0 ]5 Q资料来源：谋学网（www.mouxue.com）,在线性表的下列运算中不改变数据元素之间结构关系的运算是
A、插入
% T* |$ o$ q$ _! g' i! [/ b- sB、删除
) p* I/ _8 ]+ i* Y# |0 |6 sC、排序
- ?( W) m. T8 nD、查找
2 X# U6 O( R- k" P. A6 W正确资料:
0 d% U6 u- r7 ~6 v, w/ f. d
, j8 |5 n+ b7 ?6 r$ ~
) C8 R7 N2 p& E. o. b0 L5 |第6题,有关二叉树下列说法正确的是
A、二叉树的度为2
B、一棵二叉树的度可以小于2
; q* Y0 Q4 |% @# `' d. C! ?& F7 `C、二叉树中至少有一个结点的度为2
D、二叉树中任何一个结点的度都为2
) h8 s7 }0 P$ [+ `; L5 ]- Z正确资料:
; x  d& ]- W' E5 Y4 y

第7题,若要在O1的时间复杂度上实现两个循环链表头尾相接则应对两个循环链表各设置一个指针分别指向
A、各自的头结点
: n5 e, N2 S1 M! D. lB、各自的尾结点
0 S- {9 x1 Z, f" m2 Q) jC、各自的第一个元素结点
/ R0 O4 r  d+ v% X; _/ |2 [& l7 ID、一个表的头结点，另一个表的尾结点
正确资料:

: h/ h# a/ j$ e
1 T/ s/ T9 m  P; Y- Q0 Q第8题,对长度为n的关键字序列进行堆排序的空间复杂度为
% k5 T& Q) a8 z% L9 H! @; O* YA、O（log2n）
3 i; C6 Z  l# E# yB、O（1）
C、O（n）
, k" D" E; r3 cD、O（n*log2n）
正确资料:

  `2 _1 e5 c0 H5 R3 U
6 v2 a( u0 s6 @0 K$ D5 A3 m/ D第9题,多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为
) N- j4 L& \: \# PA、数组的元素处在行和列两个关系中
9 k- N& p4 `- G& Y' kB、数组的元素必须从左到右顺序排列
1 `+ u1 z; a1 }3 i9 tC、数组的元素之间存在次序关系
D、数组是多维结构，内存是一维结构
正确资料:
0 H# z& l& y7 i4 f* ~: H/ A, C5 B

资料来源：谋学网（www.mouxue.com）,对n个关键字的序列进行快速排序平均情况下的空间复杂度为
" ]! A  e& S, L5 q: v, \( m/ \) _A、O(1)
+ w6 l5 A: L& J% Z  ~+ Z5 ]B、O(logn)
$ \- Y2 S, n  Y1 ^) q- V# SC、O(n)
" k6 v/ z" y' w, K: J/ L5 ^1 W# \* ND、O(n logn)
: z2 V, x% V, c/ t正确资料:


/ [1 Y2 F  b6 O第11题,在一个单链表中若删除*p结点的后继结点则执行操作
A、q=p-next;p-next=q-next;free(q);
B、p=p-next;p-next=p-next-next;free(p);
C、p-next=q-next;free(p-next);
" u$ y4 w+ @& Y& E) U  ~, ^; L# U( JD、p=p-next-next;free(p-next);
7 H3 k0 E/ E& V' V$ m( q$ E正确资料:
+ ]3 g# y* V' q+ U+ e5 ?

资料来源：谋学网（www.mouxue.com）,为便于判别有向图中是否存在回路可借助于
3 q- Q3 P5 K9 r3 m% Q5 f6 b6 IA、广度优先搜索算法
' x9 T$ e& F9 M- h2 gB、最小生成树算法
+ V7 {' x. K. Q( |* C% a. J7 OC、最短路径算法
D、拓扑排序算法
正确资料:


第13题,连通图是指图中任意两个顶点之间
A、都连通的无向图
B、都不连通的无向图
$ f' {/ |; Z& ]9 R  Q# _C、都连通的有向图
D、都不连通的有向图
正确资料:
. O; J* t6 T& p5 ~) ^( b! v

第14题,能进行二分查找的线性表必须以
- X5 s+ Z  ?7 s  z; C: J0 ^2 nA、顺序方式存储,且元素按关键字有序
B、链式方式存储,且元素按关键字有序
/ Z+ J( l1 j1 y9 t' @' F6 [C、顺序方式存储,且元素按关键字分块有序
3 S" T& ^. m' G2 X5 @; ~D、链式方式存储,且元素按关键字分块有序
正确资料:
4 A$ h: d% ~+ z" ?
( f/ k5 }4 j1 }- I2 [3 ?
# @4 S! }/ E/ n3 d* H" M资料来源：谋学网（www.mouxue.com）,二维数组A的每个元素是由6个字符组成的串其行下标i=0l...8列下标为j=12．...．10设每个字符占一个字节若按行先存储元素A[85]的起始地址与A按列存储时起始地址相同的元素是
2 z* K( @% M2 bA、A[8，5]
6 [' B3 Q" ]; }, RB、A[3，10]
  [- w; R- T& Z% T5 u0 v) T5 UC、A[5，8]
( i5 |, L" u5 \; P' ~" R2 W2 _9 GD、A[0，9]
/ ]0 \' t& i9 E% g: b7 J正确资料:


第16题,下面的说法中正确的是1任何一棵二叉树的叶子节点在三种遍历中的相对次序不变2按二叉树定义具有三个节点的二叉树共有6种
A、(1)，(2)
B、(1)
C、(2)
D、(1)，(2)都错
正确资料:


第17题,以下与数据的存储结构无关的术语是
1 d# U- E: M1 F; X, \A、循环队列
, S* X& i& G8 B3 ]B、链表
) I) A# e$ b" L  e6 T3 jC、哈希表
D、栈
3 L2 J5 w9 c7 L: S9 l  g% u正确资料:


第18题,如果求一个连通图中以某个顶点为根的高度最小的生成树应采用
A、深度优先搜索算法
B、广度优先搜索算法
; g1 T5 Y5 A: J* OC、求最小生成树的prim算法
/ `- P" `& {6 E' X5 N6 jD、拓扑排序算法
2 Q! g7 U4 b$ ^正确资料:

$ u  l: K6 s$ W  d( C
第19题,若长度为n的线性表采用顺序存储结构在其第i个位置插入一个新元素的算法的时间复杂度为
2 Y8 D, ^" }; }A、O(0)
B、O(1)
, n( W5 ?0 m  b7 LC、O(n)
D、O(n2)
正确资料:
. i+ @; S; M" i

资料来源：谋学网（www.mouxue.com）,在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是
A、O(1)
B、O(n)
6 i3 h: s- I8 p0 w$ e* Y  lC、O(nlogn)
D、O(n2)
. i  C* ]/ q9 u: T2 r正确资料:
4 H1 F) j% x* ?/ _! }& x4 B2 B
0 I% r: p# \! N% }


2 k+ @  X& y0 ?/ T" y' O: k
( x+ v! z2 w) b  ]



( Y- V% g$ F) L- B5 `


) z9 p1 p7 C6 f1 e
. R4 M% f  T1 P4 D# e% T
2 K! A# ~: Y7 [/ v* x7 z8 T