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

admin

算法分析与设计19春在线作业1-0004
3 b5 ]. A* |- |) O: U* U2 u试卷总分:100  得分:100
: w0 M. A' r4 t( j! z( _/ i9 t8 N一、单选题 (共 20 道试题,共 40 分)
5 ?0 c& u0 M: O7 h$ B/ u1.字符串"China Beijing"的长度是（）
A.12
B.13
4 ]4 {+ V' {9 g- sC.14
D.15
正确资料:
+ h* }7 @  y6 e) Y7 T
2.一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树的总结点数为（ ）。
A.219
B.221
C.229
D.231
/ N' a' ^8 u0 E$ N4 B正确资料:

3 G5 v: c. p/ o3.栈和队列的共同点是（ ）
4 ~* D& d& c# D8 pA.都是先进先出
' ]  i0 Y, g4 R! fB.都是先进后出
C.只允许在端点处插入和删除元素
D.没有共同点
正确资料
! n! S% C* k* h7 @- D6 s" J- D
5 e0 f$ O$ J7 Z0 y4.使用简单选择排序法对n个数进行排序要进行()趟比较。
& l' k* |! i7 Z% BA.n
2 I4 F7 R4 B5 e+ h  A) f% h& ]B.n-1
C.n+1
D.不一定
正确资料:
6 ~) i1 F1 d7 D8 o6 c/ j
% I$ T$ q" {9 T% Y. L, \5.下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是()。
A.选择排序法
B.插入排序法
C.快速排序法
8 v, t) m0 o- x: aD.堆积排序法
正确资料:
$ O5 y8 m4 U) b( x: c
6.图中有关路径的定义是（）。
, f8 j* @0 Y+ n. |( m1 WA.由顶点和相邻顶点序偶构成的边所形成的序列
& Z5 c" S7 M5 Y6 V# p  g( \" KB.由不同顶点所形成的序列
C.由不同边所形成的序列
D.上述定义都不是
  O; c5 g2 E) W- ^8 m, s正确资料:
& W& c6 V; `+ i6 @6 ^- Z5 X
: l0 H0 \  Q' ^1 w1 ~7.执行memset(s,'a',4)后，s的值为（）。
0 `# F; ^: O! Q( ?/ AA."aaaa"
B."a4"
C."4a"
D."eeee"
正确资料:

8.一个算法的评价主要从空间复杂度和()来考虑。
1 _5 A( J; M& _1 D# L5 N3 h( K& xA.时间复杂度
B.算法有效性
C.算法有穷性
  E, R! M" g5 b, UD.算法可读性
正确资料:

9 F& q. `5 k2 L% m0 Z9.下面的时间复杂度按数量级递增的顺序排列，正确的是注释从功能上可以分为()。
A.平方阶O(n2)，对数阶O(log2n)，指数阶O(2n)
B.线性对数阶O(nlog2n)，指数阶O(2n)，立方阶O(n3)
C.常数阶O(1)，线性阶O(n)，指数阶O(2n)
4 w$ ?$ J0 N! Q2 d- f" GD.k次方阶O(nk)，指数阶O(2n)，对数阶O(log2n)
正确资料

9 \' `. k" z) u) J10.()嵌在源程序体中，用于描述其后的语句或程序段做什么工作，也就是解释下面要做什么，或是执行了下面的语句会怎么样。而不要解释下面怎么做，因为程序本身就是怎么做。
4 T! V* {+ Q% h3 E3 n0 U% D  uA.文件注释
* O3 p2 [( n% F3 B; Z' U6 \' ?B.函数注释
  @5 P( n9 F, m+ C; {C.功能注释
" W, N0 j. ~, R) J( J. BD.程序注释
正确资料
/ n( c4 ^+ T0 S2 i3 R
$ H( [& Z9 u# g6 S& P/ a11.n个结点的完全有向图含有边的数目（）。
A.n*n
B.n（n＋１）
; j$ Y3 r5 Y& A8 B3 Q1 b' l2 wC.n／2
D.n*（n－l）
正确资料来自谋学网（www.mouxue.com）

4 y- p/ ?: K" V0 x; {12.递归法是一总种编程策略，它需要有递归前进段、递归返回段和()。
A.判断条件
  K; ^! X: g7 ?- AB.初始条件
! `, C* E5 w1 F" |  VC.边界条件
D.决策条件
正确资料

13.对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100}进行二分查找，等概率的情况下查找成功的平均查找长度（平均比较次数）是（）。
A.35/11
B.34/11
- A! e0 r, C) \  d) g0 TC.33/11
D.32/11
( Q, P: [, @9 g& _  Y正确资料
9 A% _- S! _4 a' ]
' f+ r8 s& U3 A9 c0 L* \14.与二进制数101.01011等值的十六进制数为( )。
, Z3 s7 K0 d9 q% `0 I" X3 IA.B
" E2 t) I+ ]/ {0 BB.5.51
C.51
9 T5 I2 A+ H5 D; w$ m; m: ^D.5.58
正确资料来自谋学网（www.mouxue.com）
6 q  A+ l9 x  O1 z5 c% F0 n2 T
15.字符串比较的函数是（）。
. a! @$ I( D( s+ P6 l+ M! tA.strlen()
( l' e& p3 y9 s% k- _; v# HB.strcpy()
  \- N  `! L1 O( _$ c# fC.strcmp()
3 @# q3 `( j& ?8 \1 Z  DD.strcat()
5 m4 S$ v9 |) s% s正确资料
0 A) T, ~  c2 t, s- K
16.在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（）。
  I4 S: h1 N7 b9 L* u3 o: OA.O(n)
B.O(n2)
5 u1 o5 M: G9 {4 f% y" nC.O(log2n)
& ^( u5 V* L# O: O1 @D.O(nlog2n)
2 u4 m" c; z( ?4 Q; r2 m正确资料

17.下列说法错误的是()
A.使用高级计算机语言，如C、C++、Java，编写的程序，都需要经过编译器编译或解释，才能转化成机器能够识别并能执行的二进制代码。
2 p. Q7 T/ R' b7 G/ I$ R/ tB.如何一步步的跟踪代码，找到问题，搞明白为何程序不能正常运行，这个过程称为调试程序。
C.自动化的工具同样也能够帮助你跟踪程序，尤其当程序很复杂时效果更加明显，这种工具叫做调试器。
D.调试器并能解决程序中出现的问题。
. F+ F% G5 l) K- y* y# h- l正确资料来自谋学网（www.mouxue.com）
; ]0 N1 ?/ k4 @4 s6 s
/ I. N# \0 o2 u6 g$ N18.字符数组在进行指定初值时，若未指定数组长度，则长度（）初值个数。
  N$ b" c+ }# d. z% EA.小于
9 ^9 ^/ e, A- E1 JB.等于
" M9 f7 ]9 H: @# h# lC.大于
D.不等于
正确资料:

7 z% ]  p7 s: R1 ~7 r3 h; Y19.采用简单选择排序，比较次数与移动次数分别为()。
A.O(n),O(logn)
% z0 @9 H7 D2 B/ C" n& IB.O(logn),0(n*n)
C.0(n*n),0(n)
5 L. p9 ^0 u3 B0 y* v1 f+ nD.0(nlogn),0(n)
$ V5 ~' _. f- Y% _0 v正确资料

20.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：()。
+ t& V& ]: A' n$ jA.直接插入排序
B.快速排序
C.直接选择排序
$ Q) S/ T( Z% f) V4 f( XD.堆排序
- a6 F; c* T& |- A# K4 \! t正确资料:

" N) e) S8 C! i二、多选题 (共 4 道试题,共 16 分)
21.字符串有关的格式字符有（ ）。
A."%c"
B."%d"
; e2 q9 l* u$ J; I2 E7 Z  S7 bC."%f"
D."%s"
% @6 `# b8 f9 P% ]1 n: }) h( }正确正确资料来自谋学网（www.mouxue.com）
5 W6 ?( R1 W; ^
+ O7 W& D5 |- q5 r+ b# e( s6 S22.顺序结构、选择结构、循环结构三种结构共同特点是()
$ ~, B9 H! N9 g$ dA.只有一个入口
B.只有一个出口
C.结构内的每一部分都有机会被执行到（不存在死语句）
D.结构内不存在死循环（永远执行不完的循环）。
& a2 y6 a% m- R) F5 f8 D8 _正确正确正确资料D

23.递归算法的执行过程分()和()两个阶段。
A.递归
4 @/ J6 r) O+ Z) hB.递推
C.回归
2 s- n! T( d& X( ND.回溯
; P2 y1 v: T( l8 ^正确正确资料
7 X6 i! b- G/ Y( G3 S# E" G
24.设计递归算法有两点最为关键()和()。
4 Y( s/ V8 J  V  G! _( OA.确定递推公式
B.确定边界（终了）条件（递归出口）
, ~; B9 F& @; }- O; `# [5 JC.每次递归调用，都必须向基本条件前进
D.如果结果已知，那么，不用再重复调用递归
正确正确资料:

三、资料来源：谋学网（www.mouxue.com） (共 22 道试题,共 44 分)
6 o( U+ u5 b! m" G) Q5 l25.int a[10]; 说明整型数组a，有10个元素。
资料:正确
6 i& J% Q/ d$ L+ [( E( ]- f
26.函数atoi("1234")的函数返回值是1234。
7 r! U# t  B1 I" X3 ~0 p; p资料:正确
* |: |3 g1 R) M) S9 p1 A
27.递推分倒推法和顺推法两种形式。
6 M6 G& D: h: z& `( W2 a: x资料:正确
) O2 W  F$ U3 F5 ]( w
28.字符数组要求其最后一个元素是'\0'。
资料:错误

- j# @- |: o/ K* D% s: @; F( w) }7 y4 }29.在后序遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。
$ \4 C; u7 h6 l/ ]资料:错误
0 E) `& o% T" z) D9 {
30.C语言允许对数组的大小作动态定义，即定义行中的数组长度能包括变量。
资料:错误
/ S+ c6 Y) r4 N
31.高精度计算时可以用数组来存储运算结果。
7 e4 b/ W7 N' m5 U2 ^. o' I资料:正确
3 t  E1 c/ ^1 b
32.C程序执行的入口是main()函数，所以main函数必须放在程序的开头。
5 S0 [0 K, U& z  x6 P资料:错误
7 c7 ~7 h% H% E% R
' e2 V" {$ B! o5 n% D8 l0 B33.字符串的结束标记在输出时也会被输出。
. K1 W0 _. W) w+ T6 u4 s资料:错误

% m) A0 \! r# v$ E$ v34.某二叉树由5个度为2的结点以及3个度为1的结点，则该二叉树中共有15个结点。
6 L' j9 r  z2 L* z' ~7 N资料:错误

35.交换排序法是对序列中的元素进行一系列比较，当被比较的两个元素逆序时，进行交换，冒泡排序和快速排序是基于这类方法的两种排序方法，冒泡排序算法的最坏时间复杂性是O（n*n） ，而快速排序算法的最坏时间复杂性是O（nlog2n）；所以快速排序比冒泡排序效率更高。
资料:错误

36.下列程序段实现的是顺序查找功能（） int Search(int array[], int n, int key) { int i; array[n] = key; for(i=0;key!=array[i];i++); return(i<n?i:-1); }
( L) `% S4 c! k7 L6 ]资料:正确

6 |' D8 t- Z6 K37.注释内容太多会影响程序的执行效率。
6 V  S+ T& y) [# \5 D资料:错误

38.C语言中，数组名代表该数组的起始地址。
资料:正确

; u7 |0 p1 }# K. _39.查找就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。
资料:正确
& r0 I7 S' d( _8 G: I; F
40.确定性是指算法的每一个步骤必须要确切地定义。
资料:正确
& l0 K8 u+ W# a
41.遗传算法是计算数学中用于解决最优化的搜索算法，是进化算法的一种。
  @  q7 c6 k9 A; @) {9 g4 m资料:正确

42.有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。
- x5 c. N# r  `" t4 \& ~资料:错误

! ^. w5 N/ x3 V3 u) j5 y43.关键字是数据元素（或记录）中某个数据项的值，可以标识一个记录，称为主关键字。
资料:错误

44.在任何情况下，顺序表中进行结点的插入操作时都不需要移动结点。
资料:错误
" Y6 e/ t1 n+ k
8 ^8 z2 S/ v( W2 Q) d0 g+ A/ M45.C语言中，字符串作为字符数组来处理。
* c+ r0 a  q( t9 P+ Y" B2 Y( A/ s资料:正确
2 G% K  h4 `4 R, X/ G( q; C
; _( B, t% `) r& r! K% _46.对于任意一棵二叉树，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。
8 v* X) q6 b) f4 z资料:正确

9 y; ?0 O* ?  A( `

6 L; c' ]7 `) ~: N
5 h% ~# v/ J4 G9 E8 b; U


. ~' E, J& {* L
: e  q0 X* `& R6 A. y1 W4 b


$ m% z9 W! r. N