东大11春学期《数据结构Ⅱ》在线作业三

久爱奥鹏晓林

一、单选题（共 20 道试题，共 100 分。）V 1.  在线性表的下列运算中，不改变数据元素之间结构关系的运算是
A. 插入
& r6 E& E7 I! K8 X% I! GB. 删除
C. 排序
D. 定位
      满分：5  分
) T* n) n" d# ?# W2.  设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为
A. 21
  O; r5 f3 ?0 F5 |& E' s; IB. 41
C.
$ M2 N4 V+ X6 y0 Y; o) M- P  XD.
( j4 k/ F5 E9 o, _* @* @      满分：5  分
8 H  \& Q7 s: w$ A7 Z- u3.  对记录序列(314，298，508，123，486，145)依次按个位和十位进行两趟基数排序之后所得结果为
- |& B0 B+ ~( K# LA. 123,145,298,314,486,000
( G5 C- o7 P) y+ i! w+ O+ J3 g. ZB. 508,314,123,145,486,000
6 G; t, P- m3 [: z2 C( RC.
0 a: K. L# H  o9 V3 _$ ID.
# \& A9 y9 b; @0 ]/ ]      满分：5  分
4.  以下说法不正确的是
A. 无向图中的极大连通子图称为连通分量
3 D1 J3 x0 ?& }9 z( WB. 有向图的遍历不可采用广度优先搜索
C.
. X1 I, {2 {  _6 jD.
1 v) O  \8 S8 t" N4 Z: i7 Q      满分：5  分
5.  一个具有1025个结点的二叉树的高h为
) M7 p8 |% q2 F6 ?; O& D! [A. 11
B. 11至1025之间
C.
D.
* p" c6 c) ^1 Q4 r% M! o      满分：5  分
6.  最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是
A. (rear+1) MOD n=front
2 ]$ ?% w$ _% x; N7 ?" _8 N  DB. rear=front
C. rear+1=front
D. (rear-l) MOD n=front
      满分：5  分
; u! g5 r2 ]- C+ D# z7.  下列数据结构中，属于非线性数据结构的是
/ @, w' D8 z, T( tA. 广义表
, V% z5 R" Y( p0 d1 Z, h) MB. 二叉树
C. 稀疏矩阵
D. 串
) Q+ b! J1 _( u/ j5 M; u      满分：5  分
' Y; P3 P$ X" g$ Y, E8.  若<vi, vj>是有向图的一条边，则称
A. vi邻接于vj
$ _' G' D" W5 }4 N' n5 V9 ZB. vj邻接于vi
C.
D.
      满分：5  分
$ |! q0 t% }) f3 h% U( S( F9.  在执行简单的串匹配算法时，最坏的情况为每次匹配比较不等的字符出现的位置均为
A. 模式串的最末字符
. g% H& u. S" {  ^B. 主串的第一个字符
! w" G" N2 i( a/ u$ ?" o- M3 f4 wC. 模式串的第一个字符
D. 主串的最末字符
2 Q+ X* f) m! h: K1 V7 y! K2 c      满分：5  分
  X- n1 T9 z3 D10.  对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用遍历方式是
A. 先序
B. 中序
& `* y& M, ^. JC. 后序
( ?) K! ~. {& J8 L0 bD. 从根开始的层次遍历
      满分：5  分
11.  若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则节省时间的存储方式是
A. 顺序表
B. 双链表
% v/ @+ y; O! R) E# v: u+ eC. 带头结点的双循环链表
2 d2 `5 D9 S/ r; `5 ^6 V7 fD. 单循环链表
$ O9 n4 a, ~+ `4 i$ F      满分：5  分
% o, a* s! c3 Z: K! m* v# [) b12.  下述哪一条是顺序存储结构的优点
- y) W) `* M- c" _; k' e2 gA. 存储密度大
B. 插入运算方便
  ?6 Y  h; k/ v: `3 WC. 删除运算方便
& o( I5 L4 d9 G1 M6 J( oD. 可方便地用于各种逻辑结构的存储表示
      满分：5  分
13.  已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为
+ {! s! r  c% r( s% e: L: bA. q->next=s->next；s->next=p；
B. s->next=p；q->next=s->next；
: q6 E0 a3 ]) i% v! G- c9 _4 i, BC. p->next=s->next；s->next=q；
D. s->next=q；p->next=s->next；
      满分：5  分
14.  数组A[1..5，1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5，5]的地址为
A. 1140
( h* B! g6 h; `* O0 D' v- M$ ZB. 1145
C. 1120
6 v: o/ A( k8 ~. DD. 1125
      满分：5  分
15.  二叉树中第5层上的结点个数最多为
A. 8
9 Q! ~. V  a( O- ~( vB. 16
C.
D.
      满分：5  分
16.  已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为
! r- J$ h% V3 j  B, R0 WA. 5
B. 11
$ U; n5 {9 a3 P1 x5 {( z0 w  WC.
% \$ k: H; L1 \, ^/ b1 j4 s" PD.
( e% u0 _2 E$ A$ T( w1 E' b      满分：5  分
; @4 N( `8 r% X. ]/ I) _17.  无向图中一个顶点的度是指图中
A. 通过该顶点的简单路径数
" X3 {' w: r- HB. 与该顶点相邻接的顶点数
C. 通过该顶点的回路数
$ H+ I. i6 @) h7 C$ f# TD. 与该顶点连通的顶点数
      满分：5  分
; p8 N; v0 d6 `18.  在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为
A. n-i+1
B. n-i
' N/ R6 t0 l7 f, wC. i
D. i-1
      满分：5  分
: B% M! s% b; Q/ s2 K19.  for（i=0；i<m；i++） for（j=0；j<t；j++）　　　　　　　c［i］［j］=0；　　　　　for（i=0；i<m；i++）　　　　　　　for（j=0；j<t；j++）　　　　　　　　　for（k=0；k<n；k++）　　　　　　　c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］； 上列程序的时间复杂度为
" W1 Y7 Y0 d! xA. O（m+n×t）
# y$ s) Y5 v2 q6 cB. O（m+n+t）
C. O（m×n×t）
8 Y2 Q8 B- K+ k7 L8 qD. O（m×t+n）
      满分：5  分
5 G3 d. D6 ?  w5 J4 i/ q0 {20.  根据数据元素的关键字直接计算出该元素存储地址的存储方法是
  V' H% A, J( w( {4 {3 P$ wA. 顺序存储方法
% Q; }/ [+ C1 m5 T9 E% lB. 散列存储方法
C.
D.
: L& n% b2 }/ u2 q4 l      满分：5  分