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

久爱奥鹏晓林

东北大学
11春学期《数据结构Ⅰ》在线作业三
单选题
1.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是
! l0 o9 O5 A  K! D! _* j/ lA. 访问第i个元素的前驱
B. 在第i个元素之后插入一个新元素
9 j0 t6 c& L! ^8 {C.
  a; Z1 J5 f+ E" o$ xD.
资料：B
2.多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为
2 ^: T8 Y4 C$ Z8 v. B6 _A. 数组的元素之间存在次序关系
& o; u7 p5 K+ q6 A2 H2 ~9 lB. 数组是多维结构，内存是一维结构
C.
D.
! M% l; Y0 H- c* v8 X2 @资料：B
3.对n个关键字的序列进行快速排序，平均情况下的空间复杂度为
A. O(1)
B. O(logn)
C.
+ Y/ `/ v* E$ @; }# c* |. WD.
资料：B
* P, V  I, h; I4.算法分析的目的是
A. 辨别数据结构的合理性
) E0 Z- E6 J) Z0 FB. 评价算法的效率
C.
1 F* F3 B2 w6 b9 U8 H" O6 ID.
资料：
* v( g' j, r" ~8 M, c5.设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
0 |. j$ {, s% ZA. 2
+ Z5 |" k$ u. k' P3 rB. 3
' }6 o8 H( X$ u, mC.
D.
- k: W  F8 x- O8 p6 Q资料：
6.若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为
A. 图中每个顶点的入度
7 u( ]; U7 q. s& ?5 B3 FB. 图中每个顶点的出度
+ a6 L! q) Q# v  vC.
D.
资料：
7.栈是一种操作受限的线性结构，其操作的主要特征是
A. 先进先出
B. 后进先出
C.
D.
资料：
8.ISAM文件和VSAM文件的区别之一是
A. 前者建立静态索引结构，后者建立动态索引结构
B. 前者的存储介质是磁盘，后者的存储介质不是磁盘
& Z  e1 ^* z5 G+ O" t' YC.
D.
资料：
% a5 N  A& e, U" O: |, w: `9 w9.一个具有1025个结点的二叉树的高h为
A. 11至1025之间
: `% h; A0 O2 l# @" O/ MB. 10至1024之间
C.
D.
资料：
) ~7 j! G0 g$ {' {10.n个顶点的强连通图中至少含有
; l: M$ W) y( S* {; p! i8 _A. n-1条有向边
/ t- e+ ]4 l7 l. j3 }8 Q  QB. n条有向边
C.
* _, M! t" @6 B) p, XD.
& P# r( q3 _' f8 B4 t% d6 H资料：
$ l  \0 N) A" K; ^5 i11.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为
A. 7
B. 8
- J" N0 M# E7 FC.
: L" W, `: E: k( rD.
资料：
- `: E- V. `5 P5 D" F0 L9 e12.判断两个串大小的基本准则是
A. 两个串中大写字母的多少
! b8 t4 ]- ^0 t# z5 H9 dB. 对应的第一个不等字符的大小
C.
D.
资料：
13.下列陈述中正确的是
A. 二叉树中必有度为2的结点
' ?. p; X4 ^3 f$ Z) F8 EB. 二叉树中最多只有两棵子树，并且有左右之分
) G7 L4 c' m1 }5 s+ i/ r, \. [3 |C.
( s/ v: P8 N( d9 f% rD.
资料：
14.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为
A. 11
( {7 |: U& |7 F8 t5 |% MB. 18
C.
D.
+ b! {) c+ ?  y5 B' q' p0 s( T资料：
' `% y+ ~9 u5 g# f# a; |, Q15.如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
" X  `: u4 x7 r+ kA. 深度优先搜索算法
* ~3 n. @, [6 o  T( eB. 广度优先搜索算法
6 P6 v' J$ h  b0 l6 WC.
D.
资料：
, z0 E" T' \  _) [8 A5 f16.已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
: M4 G1 y3 i$ q' y4 }  O" H' I3 [& F1 SA. 16
* L' t; n* e+ _8 }B. 17
8 c/ T/ Z# Q% w# l1 ?9 A1 SC.
) }) T5 K* z3 D( g: ~: r- b7 uD.
* Y# k6 G+ \- n# Z, e+ k资料：
! A6 T# }/ R  N9 K' _' z  j# Z17.关键路径是事件结点网络中
8 {5 L# X* M" ^* Z5 _A. 从源点到汇点的最长路径
) {1 [7 z; W8 H: s* l1 b6 _B. 从源点到汇点的最短路径
6 o' J$ d/ n$ t7 \% ZC.
D.
$ v+ Z5 Y* R. @% l$ q资料：
18.计算机识别、存储和加工处理的对象被统称为
A. 数据
! q9 z+ A- Y5 Z1 B& ^+ X; UB. 数据元素
% O% a  D2 P( v: W( r8 |C.
6 e* |' G* z" A" t! Z* RD.
资料：
19.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为
! K3 x7 n  T. B( [* fA. DEBAFC
# @% |* e( X1 y5 R- e) e, gB. DEFBCA
C.
D.
资料：
20.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为
6 k& [0 ^6 s3 vA. 41
B. 62
C.
D.
资料：