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

久爱奥鹏晓林

一、单选题（共 20 道试题，共 100 分。）V 1.  在线性表的下列运算中，不改变数据元素之间结构关系的运算是
* ^! Y* V5 O  p# O9 c) i! X2 _A. 插入
7 j/ E/ @+ P7 JB. 删除
3 F! K" [: Y  q) R; m: B0 mC. 排序
7 |, ~, h+ W1 r& Y0 SD. 定位
      满分：5  分
2.  设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为
A. m
! A5 Y8 x* t% \B. n-m
C. n-m+1
D. n
      满分：5  分
7 [- B" k$ [7 y2 p: n3.  下面关于数据结构正确的说法是
A. 一种数据类型
B. 数据的存储结构
C. 一组性质相同的数据元素的集合
7 u& u! p6 q! U$ ?$ wD. 相互之间存在一种或多种特定关系的数据元素的集合
& c# ~, S) |" _+ c9 n: t      满分：5  分
4.  在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为
A. n-i+1
B. n-i
C. i
D. i-1
      满分：5  分
5.  以下与数据的存储结构无关的术语是
A. 循环队列
B. 链表
$ a' `- e6 y0 @- nC. 哈希表
D. 栈
: _& H/ R3 c2 w- _      满分：5  分
9 ~$ O( G. o) h6 Z3 E: W6.  顺序存储设计时，存储单元的地址
, U$ B# y; b; CA. 一定连续
/ s( [# k. a  c/ z+ jB. 一定不连续
C. 不一定连续
D. 部分连续，部分不连续
      满分：5  分
7 l" o3 I4 H- `9 \- p7.  在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是
% v, |6 K4 t! B6 zA. 访问第i个元素的前驱
B. 在第i个元素之后插入一个新元素
% V1 ?) Z3 g+ O1 F6 u0 CC. 删除第i个元素
8 q5 N! A4 V  z3 o( Y5 E. TD. 对顺序表中元素进行排序
+ k/ }8 ?9 r  @. P' R      满分：5  分
) V( A$ ]$ t4 B( H/ _! a& k- }9 K8.  已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t 到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到
+ [4 H5 \; |6 S- \& OA. P=″SCIENCE″
B. P=″STUDY″
C. S=″SCIENCE″
D. S=″STUDY″
      满分：5  分
4 c- k. s8 n& L3 `  v! }9.  三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A［３］[4][5]的存储地址为
A. 356
B. 358
C. 360
D. 362
4 n5 {1 }* ^6 O      满分：5  分
10.  已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为
A. q->next=s->next；s->next=p；
B. s->next=p；q->next=s->next；
, p' f* }2 o& i7 R/ ^% ]C. p->next=s->next；s->next=q；
; G2 Y8 B% x2 G' ]) {$ WD. s->next=q；p->next=s->next；
      满分：5  分
11.  若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上
; V+ N6 V+ o4 p' RA. 操作的有限集合
B. 映象的有限集合
' S. C& L3 z3 c' T7 O' b4 a4 bC. 类型的有限集合
D. 关系的有限集合
2 g* J$ u3 j3 x; Y  L      满分：5  分
12.  多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为
" ]& q7 P3 g0 L& fA. 数组的元素处在行和列两个关系中
1 g5 o1 ^( Y4 i8 cB. 数组的元素必须从左到右顺序排列
( k9 j% n" ^' R' Y9 L( MC. 数组的元素之间存在次序关系
D. 数组是多维结构，内存是一维结构
; ^) ~" k7 Z. s. y" X5 K      满分：5  分
& ]% A  ]& g. r) e2 b% V13.  从逻辑上可以把数据结构分为两大类，即
A. 动态结构、静态结构
& ^+ g5 P" [/ F7 g0 [  FB. 顺序结构、链式结构
C. 线性结构、非线性结构
D. 初等结构、构造型结构
      满分：5  分
14.  若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则节省时间的存储方式是
A. 顺序表
B. 双链表
) X' o, s! [& {4 L+ w' EC. 带头结点的双循环链表
D. 单循环链表
      满分：5  分
15.  栈是一种操作受限的线性结构，其操作的主要特征是
) z# e) w# s' E' |' OA. 先进先出
- S# ^/ z1 E' B5 C3 vB. 后进先出
$ ?$ R7 |$ J" r* {C. 进优于出
$ A: p; u* }6 xD. 出优于进
      满分：5  分
16.  在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next= head,则
7 {- f$ K, {2 H  O) @A. p指向头结点
, J# a: u" m5 q2 wB. p指向尾结点
/ u2 _  o3 U# [7 r) qC. p的直接后继是头结点
D. P的直接后继是尾结点
/ t$ E; A- g, V/ ~+ t9 }) N      满分：5  分
6 ]9 `& z8 q: R17.  判断两个串大小的基本准则是
# F5 X7 Z8 |0 r  g9 W3 }A. 两个串长度的大小
% c5 W5 E) H) ]- nB. 两个串中首字符的大小
4 I& D% `4 f* P2 k# sC. 两个串中大写字母的多少
3 q/ v( j. x" qD. 对应的第一个不等字符的大小
      满分：5  分
18.  在执行简单的串匹配算法时，最坏的情况为每次匹配比较不等的字符出现的位置均为
A. 模式串的最末字符
B. 主串的第一个字符
4 p0 H  _& O! w. n. h8 dC. 模式串的第一个字符
D. 主串的最末字符
      满分：5  分
19.  在一个单链表中，若删除*p结点的后继结点，则执行操作
A. q=p->next;p->next=q->next;free(q);
  t! B# b+ o3 t& aB. p=p->next;p->next=p->next->next;free(p);
C. p->next=q->next;free(p->next);
8 \. Y: {4 B( M' pD. p=p->next->next;free(p->next);
      满分：5  分
/ h3 l7 F' q$ i7 Q5 W& M" p) ?2 Z20.  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］； 上列程序的时间复杂度为
A. O（m+n×t）
, b# W7 Y' C) Q8 H+ `; oB. O（m+n+t）
C. O（m×n×t）
D. O（m×t+n）
5 j) x, ?4 F3 T- h      满分：5  分
$ p- _% E4 b  N; {! \! W) I1 j
* r( }& q8 R9 N- _; a! Z需要满分标准资料请直接加QQ :1306998094