奥鹏作业资料东大11春学期《数据结构Ⅰ》在线作业三

久爱奥鹏晓林

东北大学
( I/ T/ d3 c/ F4 k11春学期《数据结构Ⅰ》在线作业三
( r6 C& l  j' \单选题
1.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是
  K* @! P$ h; r% I% T: [$ @A. 访问第i个元素的前驱
B. 在第i个元素之后插入一个新元素
C.
$ B3 j) \/ L, e( R& hD.
资料：B
: H( F  d" R4 M" ^5 y2.多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为
A. 数组的元素之间存在次序关系
2 L4 [' j) G/ zB. 数组是多维结构，内存是一维结构
C.
D.
2 D! B) `7 Z) Z; j# Y- F资料：B
6 G9 x* j/ S. m5 @: l9 S" u3.对n个关键字的序列进行快速排序，平均情况下的空间复杂度为
9 P  j4 p8 Y7 [8 m8 a2 w0 @  qA. O(1)
B. O(logn)
C.
D.
资料：B
4.算法分析的目的是
A. 辨别数据结构的合理性
" D: L6 t1 _3 }! s' D% r- D) cB. 评价算法的效率
: @, T- z4 c; f5 L6 QC.
& T4 n! J4 Q8 E! hD.
资料：
5.设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
: M9 O  G" v* s1 R8 r8 y) v0 XA. 2
B. 3
+ J- F8 o% u9 F9 X1 Z' J+ n$ AC.
D.
1 H0 [; k& P) Z- s/ b* ~资料：
6.若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为
0 O9 w6 K  x, u0 {! u8 c) TA. 图中每个顶点的入度
3 [: p: N' ]) i. O9 B8 iB. 图中每个顶点的出度
$ n8 [% [& @) k4 J! |7 kC.
D.
8 L& `/ m: c0 o' X: l: _资料：
7.栈是一种操作受限的线性结构，其操作的主要特征是
A. 先进先出
B. 后进先出
  C. j  p% o2 QC.
% H6 @: s$ k3 |2 `" dD.
资料：
8.ISAM文件和VSAM文件的区别之一是
% d8 u6 j0 H  x: v+ Z" P: x" @' nA. 前者建立静态索引结构，后者建立动态索引结构
% ~% ~: o" \& @& k  fB. 前者的存储介质是磁盘，后者的存储介质不是磁盘
C.
1 y( E$ {4 ^" zD.
8 ^' U5 s) s4 D) D0 g; ?资料：
# ^+ q- T% L/ O6 Q/ j; P9.一个具有1025个结点的二叉树的高h为
. z0 a" o% U) D3 PA. 11至1025之间
B. 10至1024之间
C.
$ z2 V2 u; V- [+ I$ AD.
资料：
6 m: k) ?; S& @# W! ]8 ~10.n个顶点的强连通图中至少含有
; ]/ y4 B6 L' _6 B" fA. n-1条有向边
B. n条有向边
4 b, G* ^0 W/ Z/ b2 E/ U+ uC.
% Q5 [- {1 m6 ?" P. Z; ~D.
1 j2 n5 K  ]4 f- O7 W! z* W2 j资料：
11.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为
. I- d6 e) X8 l4 e' u; NA. 7
! p( y4 [% y" T# u7 @. HB. 8
0 Y  A2 i! E) c$ p' ~5 MC.
1 m$ h+ G+ G  x% \# D0 M9 AD.
资料：
12.判断两个串大小的基本准则是
7 A3 F7 h2 `' }: k. Z, y! XA. 两个串中大写字母的多少
B. 对应的第一个不等字符的大小
; ^" Y! c1 \$ O4 H$ y0 CC.
" @5 F5 [6 h4 o) [! U# sD.
资料：
$ Q% F- |" N* y' I13.下列陈述中正确的是
A. 二叉树中必有度为2的结点
B. 二叉树中最多只有两棵子树，并且有左右之分
C.
D.
3 U. \/ b7 h$ |2 E0 i资料：
14.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为
A. 11
! f" @6 i6 A. LB. 18
C.
D.
+ Y3 E) J/ W% Z, }; N) U! z资料：
% }* R3 p* }# g1 N$ {15.如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
* \- `7 {, r" d1 N9 d- jA. 深度优先搜索算法
. Z4 K9 e% k' f* q5 \1 R8 N0 w0 zB. 广度优先搜索算法
C.
D.
& G( Z1 l% E" E5 g$ M' D3 |资料：
* o; P+ s; F# o, a& k. _16.已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
. X# R+ K5 d5 |- c: o4 aA. 16
B. 17
C.
D.
" E; ^- J+ L! o资料：
17.关键路径是事件结点网络中
6 E( Y* S  k# g/ F, s) A/ w6 FA. 从源点到汇点的最长路径
3 F; F7 j; H9 U: [) y) t2 cB. 从源点到汇点的最短路径
3 J5 {; n- l* j3 A: b5 EC.
D.
资料：
& q* S2 u1 U' T# Z/ @/ F18.计算机识别、存储和加工处理的对象被统称为
: Q; p0 |0 N1 o( t% e) H  {& G2 Q8 mA. 数据
- L0 }" U0 C& UB. 数据元素
C.
D.
7 D, o( H' d1 K& n8 `资料：
- |6 ~6 t9 H2 Z% o6 _19.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为
1 W. i& w2 z$ B: }A. DEBAFC
B. DEFBCA
: q+ n9 s/ D' M" b0 j' YC.
D.
资料：
; C0 _9 t+ |. b2 E1 }20.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为
6 r: m: p, m7 Z9 ]A. 41
1 O) u1 _" l- ^3 g; x& YB. 62
1 h  [5 j( N1 b' mC.
2 l% `) A5 {' A+ b# \D.
资料：