东师《数据结构》11春第二次在线作业

久爱奥鹏晓林

一、单选题（共 20 道试题，共 60 分。）V 1.  下述文件中适合于磁带存储的是 ()。
A. 顺序文件
5 x4 I. S, \5 {: H: RB. 索引文件
. G  j* v6 J, aC. 散列文件
8 y. s& D' L# L4 Q$ m% ~D. 多关键字文件
      满分：3  分
7 b* j9 |+ k0 n$ {' V0 m0 e2.  下面说法不正确的是 ()。
A. 广义表的表头总是一个广义表
B. 广义表的表尾总是一个广义表
; }5 E7 z' p  p1 v' g  ^; }0 vC. 广义表常采用链接存储结构
" k+ T2 B2 j4 D+ E$ r1 a1 O/ tD. 广义表可以是一个多层次的结构
      满分：3  分
0 A. I, @1 j1 r3.  有一个100*90的稀疏矩阵，非零元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是 () 。
A. 60
B. 66
C. 18000
5 C; t/ h6 d5 ^- U9 t! a+ QD. 33
3 X" L" O1 Q- B7 G, W/ j. z      满分：3  分
4.  下列哪项不是利用查找表中数据元素的关系进行查找的方法 ()。
A. 有序表的查找
/ Y& X) Q  R2 v0 a: [4 TB. 二叉排序树的查找
C. AVL树
D. 散列查找
9 k4 @  Z4 ^5 {9 r+ J$ X) ]      满分：3  分
& _" j+ a* }6 @5 a2 m$ G4 x2 z5.  ISAM文件和VSAM文件属于 ()。
' L# U/ h5 A1 [: u; Q" i6 @A. 索引非顺序文件
# W0 @5 A* l5 C5 ^B. 索引顺序文件
C. 顺序文件
D. 散列文件
3 r2 }; C6 R; M      满分：3  分
6.  平衡的二叉排序树(AVL树)属于()的数据结构。
- m7 N' Q2 E' I9 e  FA. 动态
0 f1 m( W9 C- s: X  ^B. 静态
C. 线性
D. 无结构
      满分：3  分
7.  稀疏矩阵常用的压缩存储方法有两种，它们是 ()。
2 n+ M' p: i& n$ wA. 二维数组和三维数组
6 `4 ?8 w8 w3 |1 x3 m) d/ ^B. 三元组和散列
8 `/ _* P  p- AC. 三元组和十字链表
D. 散列和十字链表
      满分：3  分
2 p! x+ P  P9 Y) w( r" m8.  若要求尽可能快地对序列进行稳定的排序，则应选 () 。
A. 快速排序
B. 归并排序
C. 起泡排序
3 I' J/ q, P7 b% l7 ?6 k7 O7 SD. 希尔排序
' Q2 _( x5 b. W* z- H4 k      满分：3  分
/ d5 O5 j' S+ {3 g2 [% Z9.  对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是 ()。
$ w/ U$ r0 i8 _2 _, J$ \$ g7 TA. 直接插入排序
B. 冒泡排序
C. 快速排序
D. 归并排序
" g5 O! m3 W1 Z      满分：3  分
3 R" ^# e3 J* Y% r% K) T10.  有n个顶点的无向图的边数最多为 ()。
A. n
8 X2 P, _  @, {0 M. Z& Z* `B. n(n-1)
C. n(n-1)/2
+ T) G, t9 k( }6 _% p- fD. 2n
      满分：3  分
9 H' v; T' {2 s; I% L3 u! t11.  设二维数组A[0..m-1][0..n-1]按列优先顺序存储且每个元素占c个单元，则元素A[i][j]的地址为 ()。
  }0 @+ c! F5 `# pA. LOC(A[0][0]) + (j*m+i)*c
; I6 K" K0 c0 W. _% fB. LOC(A[0][0]) + (i*n+j)*c
& I% k; d2 S$ [& k) G9 B& h* FC. LOC(A[0][0]) + [(j-1)*m+i-1]*c
, _( z& h9 O; J7 x2 w! X$ \D. LOC(A[0][0]) + [(i-1)*n+j-1]*c
      满分：3  分
7 e% E' r2 v) {" w9 b, A* ~12.  若对n阶对称矩阵A按行优先顺序将其下三角形的元素（包括主对角线上的所有元素）依次存放于一维数组B [1..n(n+1)/2 ] 中，则在B中确定aij ( i < j）的位置k的关系为 () 。
) b0 r' I+ h- ~( d( M' W* }A. i*(i-1)/2+j
7 J; B1 e( y7 W; e1 W7 h) C" R; dB. j*(j-1)/2+i
+ \+ T! a4 {( zC. i*(i+1)/2+j
/ a- Y6 ]. f5 Y6 [' ^D. j*(j+1)/2+i
/ A3 ^! ]4 A: a1 r. q7 z3 O0 g      满分：3  分
13.  采用邻接表存储的图的广度优先遍历类似于二叉树的 ()。
A. 前序遍历
B. 中序遍历
C. 后序遍历
7 B2 l$ J& G4 ?! O* \% BD. 层次遍历
      满分：3  分
; \7 d1 i/ C8 f; Y' |% f14.  快速排序算法在下述哪种情况下效率最高 ()。
3 E# x0 b% p, i) N2 _+ n% M( VA. 被排序的数据已完全有序
B. 被排序的数据中含有多个相同的排序码
0 Q% M2 j/ |7 E" Y+ P% ?C. 被排序的数据已基本有序
D. 被排序的数据完全无序
      满分：3  分
15.  设有n个结点的二叉排序树，对于成功的查找，最少的比较次数为()。
6 ?  w# Z7 v' N( gA. Ο( 1 )
0 e- V1 }# C3 b# |# t0 {/ _4 F1 MB. Ο(log2n)
( h5 ?; A! [* i5 S  WC. Ο(n)
D. Ο(nlog2n)
9 F+ u- `& ~/ f1 t) D) j# d# ~      满分：3  分
, X( O( ]7 V/ R16.  在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关 ()。
A. 直接插入排序
B. 冒泡排序
0 g. d7 G& F/ Y1 I% UC. 快速排序
( m4 p/ Q/ L- H( n) [! }D. 直接选择排序
1 r# M+ l  e- E1 y( A      满分：3  分
% F7 H: z+ A+ ~17.  散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值 ()。
# d7 [' ^: F! H; _" XA. 同等概率
2 y; h( g% z4 f$ y3 t3 a/ v5 }B. 最大概率
C. 最小概率
D. 平均概率
# |5 |. B, s3 V" V' l3 U* t      满分：3  分
  @: B, @- g! K$ W& K/ n9 v18.  排序趟数与序列的原始状态有关的排序方法是 () 排序法。
A. 直接插入
B. 直接选择
( n( k' n7 w* V* [  m! E( UC. 冒泡
% q( [( r$ x( B) V, I9 ID. 归并
0 W; L0 Y( Z# y6 q5 E8 r/ L+ y      满分：3  分
19.  设有n个结点的二叉排序树，对于成功的查找，最多的比较次数为()。
8 ]$ J$ ~, Y5 y6 E% CA. Ο( 1 )
B. Ο(log2n)
C. Ο(n)
D. Ο(nlog2n)
% L2 X8 l4 s0 g      满分：3  分
- S4 r9 ?0 G/ i20.  散列文件使用哈希函数将记录的关键字值计算转化为记录的存储地址，因为哈希函数是一对一的关系，则选择好的 () 方法是散列文件的关键。
# Y% @# E3 `6 mA. 哈希函数
B. 除余法中的质数
: ^9 x6 F; i4 w% ?C. 冲突处理
D. 哈希函数和冲突处理
      满分：3  分
" Z7 K( b& n# [) I* ?9 T% r
二、判断题（共 20 道试题，共 40 分。）V 1.  归并排序的辅助存储空间代价为O(1 )。
5 O7 O: {* X, `0 c2 |A. 错误
% x4 m) H5 E" QB. 正确
6 T( ~  m2 _! X      满分：2  分
2.  快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n )。
A. 错误
B. 正确
      满分：2  分
8 b# C) ?' \( {2 t. N) x; I3.  排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。
& `3 \' y7 m/ V3 b2 {( B$ d  XA. 错误
* r' {2 q! l1 L1 s: AB. 正确
      满分：2  分
4.  二维以上的数组其实是一种特殊的广义表。
$ \- y4 P# R  r( @4 K* WA. 错误
$ {% v' _2 C7 Y) A  Y' J$ `B. 正确
      满分：2  分
5.  哈希表(散列表)的结点中只包含数据元素自身的信息，不包含任何指针。
- g2 z" A/ \* wA. 错误
; ?3 @9 U' g9 B! X+ q+ tB. 正确
      满分：2  分
- ^4 A/ e+ ^& Z; g% p4 }6.  任何无向图都存在生成树。
A. 错误
- D# E/ H0 c/ D. L; rB. 正确
      满分：2  分
7.  当待排序记录已经从小到大排序或从大到小有序时，快速排序的执行时间最省。
. m5 i1 t: `, s- I$ TA. 错误
# z& T8 [2 E' Y1 n  Y9 d! K: R5 \1 UB. 正确
1 V5 i$ g! Z6 B( L9 u6 P6 [4 H' L      满分：2  分
8.  内部排序要求数据一定要以顺序方式进行存储。
A. 错误
B. 正确
+ T  \" S1 ~& u      满分：2  分
9.  对有序的单链表可以进行折半查找。
! h- h" ^/ Z5 ^2 X' K0 ZA. 错误
7 ^, p5 C: z$ a4 F1 O: d$ V  zB. 正确
      满分：2  分
0 o. a4 H) r' y10.  AOV网的含义是以顶点表示活动的网。
A. 错误
B. 正确
      满分：2  分
11.  一个有向图的邻接表和逆邻接表中结点的个数可能不等。
- ]! S7 a7 Q/ C" I5 {2 w/ jA. 错误
3 m9 F6 v4 q' |$ GB. 正确
      满分：2  分
* r# K9 D0 d5 }0 s12.  哈希法(散列法)的平均查找长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。
A. 错误
B. 正确
4 h7 a/ ~8 r/ X% `4 _5 H5 j      满分：2  分
13.  哈希函数越复杂越好，因为这样随机性好，冲突概率小。
A. 错误
B. 正确
      满分：2  分
14.  就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大
1 S1 `: r+ q5 J/ \/ JA. 错误
B. 正确
4 P* _6 }% `# z- C; H4 A- G* L2 |6 c      满分：2  分
15.  无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。
A. 错误
& \5 k  J8 V' S6 B- A3 d4 L4 tB. 正确
      满分：2  分
1 K5 s# x4 Z6 `0 B16.  对无环有向图进行拓扑排序一定能够得到完整的拓扑序列。
8 ^6 f) y; c/ e' T' L; @+ RA. 错误
) A0 K7 \( P" kB. 正确
      满分：2  分
8 }7 d* B) T: Z6 W% h1 f17.  快速排序的速度在所有排序方法中最快，而且所需附加空间也最少。
A. 错误
B. 正确
      满分：2  分
18.  倒排文件与多重表文件的次关键字索引结构是不同的。
A. 错误
3 o) V8 x! d2 x! r" C/ E7 wB. 正确
      满分：2  分
9 F/ |* d' ~* K+ V+ A19.  最佳二叉排序树是AVL树 ( 平衡二叉排序树 ) 。
A. 错误
B. 正确
7 j* }: R; O7 ?, l4 v3 e+ R      满分：2  分
20.  文件系统采用索引结构是为了节省存储空间。
A. 错误
B. 正确
      满分：2  分