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

久爱奥鹏晓林

东北大学
11春学期《数据结构Ⅰ》在线作业三
单选题
1.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是
: d, i! z6 z9 _9 b! M9 [A. 访问第i个元素的前驱
B. 在第i个元素之后插入一个新元素
& S9 M& @  ?# wC.
D.
7 s0 ?. w; Q' E" V资料：B
0 M' ?% i, j* g. A2.多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为
A. 数组的元素之间存在次序关系
- @3 s* z# O( M6 V6 t" J4 z% [2 ?B. 数组是多维结构，内存是一维结构
C.
8 K+ b. w8 B; X& U5 t0 wD.
资料：B
3.对n个关键字的序列进行快速排序，平均情况下的空间复杂度为
. [2 k- j! K" A5 O: ZA. O(1)
! [# a7 d, |2 b! _3 Y6 C$ gB. O(logn)
: P. P# k6 }; K" I* t, y$ R' ]7 ~C.
D.
' v& K/ o4 `) ?7 @+ |+ l资料：B
' T3 y& O1 P5 `: s4.算法分析的目的是
A. 辨别数据结构的合理性
( d/ y9 K5 W! I; ]- P% PB. 评价算法的效率
* R2 O' D* |1 c7 \% I" Y0 L5 G& N" R2 kC.
D.
: @6 ~" Z5 f6 ^5 `& R4 U% d3 n资料：
5.设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
A. 2
B. 3
C.
( p7 K% J: A! X" x" CD.
) y2 W& _: c/ C+ @资料：
6.若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为
A. 图中每个顶点的入度
8 M( A& k4 w9 y' m. ^( q2 P: ]B. 图中每个顶点的出度
C.
D.
资料：
7.栈是一种操作受限的线性结构，其操作的主要特征是
A. 先进先出
B. 后进先出
C.
D.
& h- u" \# v4 d( X$ v资料：
) h9 U' j  T0 a0 G8.ISAM文件和VSAM文件的区别之一是
0 R) \) F& @% d, r6 J  k; J( K& KA. 前者建立静态索引结构，后者建立动态索引结构
B. 前者的存储介质是磁盘，后者的存储介质不是磁盘
C.
D.
( S5 L2 \4 `* U/ B; }资料：
9.一个具有1025个结点的二叉树的高h为
A. 11至1025之间
6 X: E" E, v8 |# S% y: F5 KB. 10至1024之间
8 T) H/ {& U/ {6 }4 Q$ DC.
4 L$ }$ P# T) u# eD.
资料：
# K" R( h$ l! E: \6 _10.n个顶点的强连通图中至少含有
( E$ w3 @+ T- N9 LA. n-1条有向边
B. n条有向边
C.
+ ?3 R  H' ~2 @; y  r9 m$ K. JD.
1 Q, O  r4 q0 l/ c资料：
2 S: D" Y( B- |. ^11.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为
5 j0 @, e5 O+ Y/ @; yA. 7
B. 8
/ {, k5 [  z/ Y& G4 ?) b/ xC.
D.
资料：
/ l! n, T9 C9 ]. V12.判断两个串大小的基本准则是
) Z; H+ `3 s3 ?A. 两个串中大写字母的多少
B. 对应的第一个不等字符的大小
C.
D.
资料：
13.下列陈述中正确的是
A. 二叉树中必有度为2的结点
: _4 |1 N3 b0 U5 bB. 二叉树中最多只有两棵子树，并且有左右之分
C.
; }, P+ ]4 k* f# u" g, I) xD.
6 ?, {9 V% K- d资料：
9 J7 `$ o0 n* f$ y5 P. `* i14.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为
A. 11
1 u" Z6 W3 V' f* _* E0 p, _1 Z, iB. 18
C.
D.
' d5 B6 i' w  ?) {' b2 _: E7 ^4 H资料：
" n+ S5 [% D9 o8 r- r15.如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
( I$ W% S& `3 B9 X; n+ qA. 深度优先搜索算法
+ [) |" G. S9 B0 z8 W- ^/ j' j) xB. 广度优先搜索算法
5 F6 X& x/ q* d4 t0 ^5 rC.
D.
资料：
16.已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
9 a1 y" ^  T& ^! Y+ Q: s6 U3 RA. 16
B. 17
: Q; P8 b# G9 X* D1 u# }9 bC.
/ \9 o  }5 ]2 D5 [  M/ h" ^D.
* h% y' F3 I) t; P- r- ]( X! V资料：
17.关键路径是事件结点网络中
A. 从源点到汇点的最长路径
: E; S. F% F- f" x8 _% gB. 从源点到汇点的最短路径
3 J3 H8 Y5 g- i3 P) o/ w) EC.
4 x4 w  n4 c" |# PD.
资料：
4 Y4 Q( e* L2 F, m& d: Q! P18.计算机识别、存储和加工处理的对象被统称为
3 R! w# K/ ]$ W1 tA. 数据
  S/ {) B  @) AB. 数据元素
C.
* e2 v; S) d/ ?5 w. w: \D.
资料：
$ l8 v7 }, {8 P: E8 I* ]6 O4 A19.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为
# M# e5 ^& |: m* q' u, ?+ K6 EA. DEBAFC
B. DEFBCA
9 s2 }% ?1 ?  M/ h  f$ _C.
D.
资料：
2 \' `0 k9 x6 [. r2 b' m0 \0 n20.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为
A. 41
* N+ ]6 V0 B3 T( `4 q$ A, p1 e+ q' v, _, WB. 62
2 Q" A4 H# }6 _0 CC.
' v5 `$ i5 G: wD.
资料：