东北师范《算法分析与设计》》21秋学期在线作业2答卷

admin

算法分析与设计19春在线作业2-0001
3 p5 ^, X6 T4 {/ C/ d* [* }试卷总分:100  得分:100
一、单选题 (共 20 道试题,共 40 分)
# U/ h/ ]7 T. a1.用计算机解决问题的过程可以分成哪三个阶段()。
A.输入、测试和输出
B.分析问题、设计算法和实现算法
: b' P, g+ X6 l8 M# e& UC.输入、算法设计和输出
2 J' u) M/ y4 i! z8 O: z% V% m4 gD.分析问题、测试和实现
/ |6 \8 F8 H1 w0 C7 r/ X: ~( n/ H正确资料:

# e, p0 h( o2 f( U2.()命令主要用来查看磁盘中文件的命令。
A.dir
B.cd
C.type
D.fc
正确资料:
. V  _+ k: W$ r% B) b1 I% g! b! X
, @' s+ j; {6 [+ Y3.cd 目录名的功能是()。
A.退回到根目录
B.退回到上一级目录
6 K3 C' m3 H0 H8 _2 y  m0 jC.进入特定的目录
' r# R1 H5 A. ]. l1 E% wD.显示出文本文件的内容
正确资料

4.IDE的全程是()。
A.集成开发环境
B.集成环境
  J- [+ n& P" V2 K$ V) OC.开发软件
D.调试过程
正确资料:
  `+ u9 }5 X% p$ ~1 i
5.在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是()。
A.选择
B.冒泡
/ f! P6 D* R# Q& t; {) ]C.插入
  v$ k" @. X7 `( XD.堆
+ t% G- R. T4 R; W+ ]正确资料
  k) x8 q1 A( t3 E* N- C
2 v( S, |, p. Q! j6.在下列排序算法中,哪一个算法的时间复杂度与初始排序无关()。
9 O* F! t5 B) E. |/ gA.直接插入排序
% [- _/ `: Z+ o; _/ R. l+ h) kB.冒泡排序
( g3 h) S) w- }C.快速排序
D.直接选择排序
: d3 f/ L* n9 s& u6 c8 q正确资料来自谋学网（www.mouxue.com）
5 l) b. s6 b1 d7 _( R3 {
' x2 X8 R, s" Y9 c9 g% @! D; R7.下列叙述中，正确的是()。
4 t. y9 M" ~1 a3 o" K% uA.对长度为n 的有序链表进行查找，最坏情况下需要的比较次数为n
B.对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为(n/2)
C.对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为(log2n)
2 V+ B' z& j: [+ ID.对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为(nlog2n)
正确资料:
% f  Y+ c; M8 o4 Q1 W4 m
8.按F5开始调试，程序便会直接运行到断点处。接下来可以逐行来运行程序，查看各个变量的值，也可以直接运行到下一个断点或程序结束，这样过程被称作()。
A.设置断点
) J/ Z9 `4 D" hB.单步调试
* o- H( Q' ?& F, B. qC.程序编译
D.程序调试
正确资料:
( E( t! L! z% b* `+ g
9.已知某二叉树的后序遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是（ ）
A.acbed
! z: v# C: }. |2 F# uB.deabc
2 R; T$ H/ Z- s2 I9 yC.decab
D.cedba
正确资料来自谋学网（www.mouxue.com）

' F! O6 {; i! }' h( ~* D10.对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100}进行二分查找，等概率的情况下查找成功的平均查找长度（平均比较次数）是（）。
A.35/11
B.34/11
C.33/11
. n3 K& Z) X' p) xD.32/11
正确资料

11.某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是（）
A.10
) O  Q1 E" O/ k- `9 Q2 g9 _( EB.8
: k% q5 g# }- r. zC.6
* t  P* |  R) D8 f4 v- I% @/ SD.4
4 ~. C- I/ R" l1 s7 V* B  W$ ?正确资料

% G. G* W5 z4 _1 ^/ O: u12.如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。()就是不稳定的排序方法。
A.起泡排序
2 \6 }; m4 A3 k. u' C( b4 P( ?B.归并排序
0 e( T& D# O) M' l6 r; iC.Shell排序
6 O( u' \# x1 x8 L2 z' S; v: FD.直接插入排序
" G' s. {2 [. t4 q/ D正确资料
  F! z; ]6 N0 g/ y3 t/ l" |8 o
13.在程序代码编辑框外（一般都是程序代码的最左侧）双击，就成功设置了一个断点，设置成功后会在该行的最前面显示一个圆点，这样的过程称作()。
A.设置断点
B.单步调试
C.程序编译
D.程序调试
* q( l2 A) C7 `6 k* T/ x正确资料:

6 u! L; l/ @4 O14.如何一步步的跟踪代码，找到问题，搞明白为何程序不能正常运行，这个过程称为()。
; M. q$ Z$ y3 \8 ZA.编写程序
+ l& n. m  p( e' r$ LB.调试程序
C.执行程序
* l( |& _4 C# Z" L" E1 yD.编译程序
正确资料:
, \! M7 [' z- k( @
15.变量名=属性 + 类型 + 对象描述，其中每个对象的名称都要有明确含义，可以取对象的名字全称或名字的一部分，这种命名规则是()。
; j/ v. E* M" |& oA.匈牙利命名法
B.骆驼命名法
, A( z4 G2 }) A! ^4 O/ hC.下划线命名法
D.帕斯卡命名法
正确资料:
7 M( I! G) C% L) j! G! M
3 y' k) A0 q5 c. H) B) J; ^8 l16.支持子程序调用的数据结构是（ ）
: _  Z% g- }  U# Z  LA.栈
B.树
- b% T' l( ^6 Y: k/ i4 ]4 p  WC.队列
D.二叉树
正确资料:
; `3 K# t1 A4 u$ }' G) ?. _" G
' c" R* K+ C  {2 s0 r5 l9 K$ k17.下列数据结果中，能够按照"先进后出"原则存取数据的是（ ）
A.循环队列
B.栈
3 U8 Q- h. |$ R. dC.队列
D.二叉树
& z6 T% `9 H3 @* ^+ A正确资料:
2 L0 c  K) k" x  S6 G
5 k, H; N* b2 O$ y18.十进制中最小的数码是（）。
A.10
B.9
3 n! }4 c. R1 P- iC.1
1 b1 x( _0 ]/ O/ @2 xD.0
# g& R: }9 ^& w( m3 C4 I正确资料来自谋学网（www.mouxue.com）

19.在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（）。
A.O(n)
B.O(n2)
C.O(log2n)
6 h; q- g. t, H3 S- c$ \* OD.O(nlog2n)
正确资料

( ?2 e, C# T$ f20.strchr（）函数用来（）。
5 _; h; W( O1 zA.字符串连接
B.比较字符
C.求字符位置
: H$ r& g' i  g; z5 oD.求子串位置
正确资料
0 l$ P. f. n1 i$ [
二、多选题 (共 4 道试题,共 16 分)
. @. o; w9 }( R# F21.递归算法的执行过程分()和()两个阶段。
: J, A& i" a% Z/ A; |A.递归
B.递推
) K# q9 S2 u6 \/ n+ EC.回归
. K( r% _7 s. n+ D. f6 f7 UD.回溯
正确正确资料
7 B3 t! w2 L' ^$ f0 `( A5 j
6 K7 l8 F' k4 W6 m+ v" L2 u22.设计递归算法有两点最为关键()和()。
A.确定递推公式
B.确定边界（终了）条件（递归出口）
9 c: {+ p1 J0 j) ^& d: O# a$ \' b0 |) iC.每次递归调用，都必须向基本条件前进
D.如果结果已知，那么，不用再重复调用递归
正确正确资料:
7 s3 ~& ~0 J$ m' O$ f- W4 C: f
23.顺序结构、选择结构、循环结构三种结构共同特点是()
5 s/ \8 Z' e% v$ E4 yA.只有一个入口
B.只有一个出口
( I9 U  ~* j. KC.结构内的每一部分都有机会被执行到（不存在死语句）
: m/ i) y5 v" r. U' V$ P# x/ jD.结构内不存在死循环（永远执行不完的循环）。
正确正确正确资料D

24.字符串有关的格式字符有（ ）。
A."%c"
# {/ {3 L5 T) N( ?1 {3 r& W5 kB."%d"
+ U9 a8 v0 n* p! uC."%f"
D."%s"
正确正确资料来自谋学网（www.mouxue.com）
2 U3 T0 G4 p$ @2 G0 ]/ R* h0 |$ U
; `1 _8 e. b% T3 t$ U7 h三、资料来源：谋学网（www.mouxue.com） (共 22 道试题,共 44 分)
25.在查找其关键字等于给定值的过程中，需要和给定值进行比较的关键字个数的期望值称为查找成功时的平均查找长度，则称为平均查找长度ASL。
9 ~* B! \" @3 y4 j" t* u资料:正确
1 S7 j5 b* f3 u- i
26.puts不需要格式控制符，且自动换行。
1 T9 Y1 Y7 I  S# R; b资料:正确

# ]7 I; W$ j0 ~6 J# m% \27.已知一棵度为3的树有2个度为1的结点，3个度过为2的结点，4个度为3的结点，则该树中有12个叶子结点。
资料:正确

& d) d* H) Z1 o- ]$ L& I3 u. W% f6 {28.对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为log2n。
+ \  d! S/ ]$ `  H! Y资料:错误
% ]( ^7 V7 j4 e" h+ H% R
' @2 I9 F$ t" f* n0 D29.冒泡排序是一种不稳定排序方法。
资料:错误

* U( U' [, ]3 ^$ A- n9 N30.二分法插入排序所需比较次数与待排序记录的初始排列状态相关。
资料:错误

31.在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n )。
资料:错误
2 ]/ R0 `4 i! u, m
32.递归算法是一种用若干步可重复的简单运算（规律）来描述复杂问题的方法。
资料:错误

33.gets()函数一次可以输入多个字符串。
资料:错误
1 \1 n8 M% Y9 N4 R+ {& w* }2 H
34.递推就是在函数里调用自身。
' m6 @) |2 k' k0 B资料:错误
- u1 h: _) h/ Y' ]& N
35.一个函数直接或间接调用自己本身，这种函数叫递归函数。
9 r, r8 r  o" K; q9 V7 @# Y8 B! U# N资料:正确
( [3 D2 L6 E- B  b. ^$ h6 r6 G
36.字符串的结束标记在输出时也会被输出。
. t8 M" P8 w/ D4 R资料:错误

37.内排序要求数据一定要以顺序方式存储。
6 `7 F4 ^! ~( t资料:错误
6 F& a' i7 @* f; K
8 f  l( j0 L- T: R2 ?38.有一组数据{6，202，100，301，38，8，1}，使用简单选择排序需要进行6趟比较。
资料:正确
8 m2 ?6 t" J2 F6 P
39.长度不同的字符串一定不会相等。
0 R) P% c4 W' _6 v: \) w资料:正确

40.在待排数据基本有序的情况下，快速排序效果最好。
4 K4 h7 r) w8 z2 w- p9 u资料:错误
% }# {; l# \5 H% e2 R& k# r$ N
! G# L+ ^5 }) w0 Q  ~* P6 J% `41.在顺序表中进行结点的删除操作平均须移动一半结点。
资料:正确
. T2 ^  ^1 ?$ ^, ]# E
42.一棵二叉树第6层（根结点为第一层）的结点数最多为31个。
资料:错误

43.顺序查找法适合于存储结构为散列存储的线性表
( F* m  N4 d( l/ z7 H+ @资料:错误
3 B: M$ o. C2 r# p6 f6 Y7 }
44.字符数组的初始化可以逐个元素进行初始化。
资料:正确

: f5 Y# U+ W, a3 [. B; _45.线性表需要为表示结点间的逻辑关系而增加额外的存储空间。
资料:错误
- N8 {$ Y' j- c5 T& R6 V7 z
46.快速排序的时间复杂度为O(n*n)。
资料:错误
. Z1 l  {4 h9 l/ K  M: h7 D



; x. d* C# H" ?


( u0 y5 k1 {/ l# p6 [

% l2 g' K, u6 |- G% P