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

admin

算法分析与设计19春在线作业1-0004
试卷总分:100  得分:100
4 H! X9 l$ ]: e+ Y4 r3 h一、单选题 (共 20 道试题,共 40 分)
1.字符串"China Beijing"的长度是（）
" B7 B" m, @; K: x0 |6 `6 t0 E4 iA.12
9 n7 L& p% f9 d& r5 F! HB.13
C.14
2 J* F0 g+ d3 m3 z2 v* HD.15
正确资料:
$ _2 @" x# f4 |* a8 [" J- K/ c# k
2.一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树的总结点数为（ ）。
" `7 x2 t! X- L2 t6 {7 O6 f6 `A.219
# g7 P% ?- h  o- e4 q% i2 ?; }% yB.221
/ ?1 a* E* x# NC.229
D.231
: z' y0 |9 o( ?4 `8 b+ d! `正确资料:
  \" C- l2 e6 M/ i9 r
3.栈和队列的共同点是（ ）
A.都是先进先出
B.都是先进后出
C.只允许在端点处插入和删除元素
D.没有共同点
* c1 c" H7 {' s" u, ?) r正确资料

- ?, m! n& D" A3 W3 f, u4.使用简单选择排序法对n个数进行排序要进行()趟比较。
A.n
  d* e! a% ^% y8 Q& TB.n-1
C.n+1
1 U, _. c( c8 b: V2 `9 L4 nD.不一定
正确资料:
0 O2 X6 Z( u! G  c$ ?
5.下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是()。
# r! {- [3 t) \' Q- Q$ \% kA.选择排序法
B.插入排序法
C.快速排序法
D.堆积排序法
8 Z/ O9 u# V6 Q% U正确资料:
" z. F& _- \! U
6.图中有关路径的定义是（）。
4 ^/ @: O9 w2 w8 Z6 AA.由顶点和相邻顶点序偶构成的边所形成的序列
B.由不同顶点所形成的序列
C.由不同边所形成的序列
% v5 P. ?1 @! t# \0 G# B2 e: KD.上述定义都不是
1 Z4 j5 g" ?, a$ `正确资料:

$ ]- l0 y* \# d# J: ]" c7.执行memset(s,'a',4)后，s的值为（）。
# O; P) l+ U6 z5 k9 ]- s$ d+ vA."aaaa"
; x' Y8 z' A2 k" @4 [8 K3 a: I3 Y2 eB."a4"
% d3 E; }) V( Z( N+ ^3 _C."4a"
D."eeee"
. m6 N0 B+ W, n3 ^2 i0 q4 v$ S正确资料:
% K9 C7 |. O. I' v
8.一个算法的评价主要从空间复杂度和()来考虑。
5 O) d% V7 {9 T! K$ e7 m2 D4 h  |8 rA.时间复杂度
B.算法有效性
C.算法有穷性
D.算法可读性
正确资料:
+ \) w  r  o( l
3 ]' ]$ W  o% a2 w9 M- R- ?9.下面的时间复杂度按数量级递增的顺序排列，正确的是注释从功能上可以分为()。
A.平方阶O(n2)，对数阶O(log2n)，指数阶O(2n)
B.线性对数阶O(nlog2n)，指数阶O(2n)，立方阶O(n3)
8 s- N: ^1 @9 u6 L, J+ j7 eC.常数阶O(1)，线性阶O(n)，指数阶O(2n)
  \, [2 C6 K5 l9 C. G" A+ zD.k次方阶O(nk)，指数阶O(2n)，对数阶O(log2n)
- D( O# X$ v* O" X% R) S正确资料
/ |, f* ?/ J: G% X
* z& D4 [  \$ R, G2 d6 C10.()嵌在源程序体中，用于描述其后的语句或程序段做什么工作，也就是解释下面要做什么，或是执行了下面的语句会怎么样。而不要解释下面怎么做，因为程序本身就是怎么做。
9 n0 h. t+ l1 l$ B* ?4 k+ K) wA.文件注释
. p% w/ Y: f8 fB.函数注释
3 v/ _* F* A, c7 s  VC.功能注释
; ^* n+ r! N( N$ @8 FD.程序注释
正确资料

11.n个结点的完全有向图含有边的数目（）。
A.n*n
B.n（n＋１）
C.n／2
6 j- r7 x6 ^2 A$ |D.n*（n－l）
正确资料来自谋学网（www.mouxue.com）

12.递归法是一总种编程策略，它需要有递归前进段、递归返回段和()。
" K9 N1 M7 v+ ~) ?A.判断条件
' l. [6 b# K: m! T8 VB.初始条件
8 j  D. n0 H* A. Q  [$ sC.边界条件
D.决策条件
正确资料

: i* j0 c+ O$ ~; {1 U7 N, y13.对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100}进行二分查找，等概率的情况下查找成功的平均查找长度（平均比较次数）是（）。
2 Y% v  S$ v9 g! n4 _0 \# mA.35/11
B.34/11
C.33/11
( K% N- x1 C8 J4 J( x# D0 B; RD.32/11
正确资料

14.与二进制数101.01011等值的十六进制数为( )。
A.B
. J& f3 K$ v/ I0 z5 e7 B. DB.5.51
C.51
D.5.58
正确资料来自谋学网（www.mouxue.com）

- o% Y# w- _" @+ ^: Z* o15.字符串比较的函数是（）。
A.strlen()
) K3 |2 y0 n! B8 R5 EB.strcpy()
C.strcmp()
D.strcat()
正确资料
6 F  V# C2 f; E3 E7 S4 c
16.在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（）。
( L! h7 W8 @* H! j5 L$ q& oA.O(n)
B.O(n2)
C.O(log2n)
D.O(nlog2n)
正确资料
; x3 L0 T, P+ ^
$ x' e/ s$ v. X2 B8 w* ^17.下列说法错误的是()
A.使用高级计算机语言，如C、C++、Java，编写的程序，都需要经过编译器编译或解释，才能转化成机器能够识别并能执行的二进制代码。
, z; v) ^1 U# R- R+ ^2 SB.如何一步步的跟踪代码，找到问题，搞明白为何程序不能正常运行，这个过程称为调试程序。
C.自动化的工具同样也能够帮助你跟踪程序，尤其当程序很复杂时效果更加明显，这种工具叫做调试器。
D.调试器并能解决程序中出现的问题。
正确资料来自谋学网（www.mouxue.com）

4 G. K4 z+ \* m; S: `18.字符数组在进行指定初值时，若未指定数组长度，则长度（）初值个数。
A.小于
B.等于
C.大于
4 O' c  D  `" e: F. XD.不等于
正确资料:

19.采用简单选择排序，比较次数与移动次数分别为()。
6 [7 `2 G. {" o, _, sA.O(n),O(logn)
B.O(logn),0(n*n)
' O4 ?; E; Q/ W5 CC.0(n*n),0(n)
) n" L- |! n. |! w& m" @- z" ZD.0(nlogn),0(n)
正确资料

! l3 x. w+ L& G1 S, [20.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：()。
A.直接插入排序
+ L- |- T$ K" ^# i! k1 G+ fB.快速排序
C.直接选择排序
D.堆排序
& P/ ?5 J# ?" \& P- n, Y正确资料:
2 a2 R' K: x7 c7 C! J
) n% _+ j7 O/ m+ N$ {7 I% P二、多选题 (共 4 道试题,共 16 分)
& h0 Q, d: H* S. P6 f9 L: i21.字符串有关的格式字符有（ ）。
# j6 c8 k5 J* i. }2 A  \% uA."%c"
+ e: Y; \0 h3 ?2 b) W$ I) eB."%d"
C."%f"
$ q2 c' T/ ]) TD."%s"
正确正确资料来自谋学网（www.mouxue.com）

5 h$ i7 a9 u" j1 v+ L" I; N4 t22.顺序结构、选择结构、循环结构三种结构共同特点是()
A.只有一个入口
B.只有一个出口
C.结构内的每一部分都有机会被执行到（不存在死语句）
0 v5 I; k! b( a0 _6 x) h/ X# i1 {D.结构内不存在死循环（永远执行不完的循环）。
& i% Y* G  d0 }, V& @$ r3 X正确正确正确资料D

: _# Z& m0 k/ j0 {7 S23.递归算法的执行过程分()和()两个阶段。
A.递归
B.递推
& ~; T  }1 Y9 X  R6 e( I/ PC.回归
4 {" O+ ?9 }, Y( ND.回溯
正确正确资料

24.设计递归算法有两点最为关键()和()。
6 }" q) a" H3 [' `! |( w" ~, dA.确定递推公式
! E' y7 ]7 m. f" A7 Q9 I4 B  E, x! `B.确定边界（终了）条件（递归出口）
C.每次递归调用，都必须向基本条件前进
D.如果结果已知，那么，不用再重复调用递归
正确正确资料:
  Z; |3 U' n) `- o3 I) R0 {
7 }1 P2 W; h, @7 x' |三、资料来源：谋学网（www.mouxue.com） (共 22 道试题,共 44 分)
( A# d" a2 K* E+ Q% R- e25.int a[10]; 说明整型数组a，有10个元素。
6 s* X0 [1 @  [! Y3 S$ z( |资料:正确
* d  O4 P! D+ h- U0 u# f3 b& A
! s4 p3 r! S1 B# ~26.函数atoi("1234")的函数返回值是1234。
资料:正确

/ G* B4 n' ]: ?9 E6 q5 k4 s27.递推分倒推法和顺推法两种形式。
. ?7 k- ]- S+ B8 j, h8 W资料:正确
+ C2 p. u* d6 k3 V0 t
28.字符数组要求其最后一个元素是'\0'。
资料:错误
, M9 ^5 U& N+ G; s/ _
. a+ Y) @2 w/ h0 c9 `8 `29.在后序遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。
3 S8 J; t: F' Z6 @' y- o3 G资料:错误
4 i% S* V! F, @
: y! A1 s" O6 ]1 Y; [# ~0 l& k' `30.C语言允许对数组的大小作动态定义，即定义行中的数组长度能包括变量。
资料:错误
4 i$ a( M4 u' R# i& J
31.高精度计算时可以用数组来存储运算结果。
/ s+ j, q" [! }" R# D7 h4 p  ?资料:正确
7 g( g" u, e  J* X* q9 ]
" r1 X# J( g  O1 B% w  ]/ B32.C程序执行的入口是main()函数，所以main函数必须放在程序的开头。
/ R+ |* A- t2 `$ f/ T资料:错误
" J) N1 a- P1 H2 ]
" V8 Q$ k/ H$ W9 ^5 _33.字符串的结束标记在输出时也会被输出。
资料:错误
; J' Y  `$ F) d2 W
34.某二叉树由5个度为2的结点以及3个度为1的结点，则该二叉树中共有15个结点。
资料:错误
; E0 {( W$ q* f* m* k( ^; c  r
35.交换排序法是对序列中的元素进行一系列比较，当被比较的两个元素逆序时，进行交换，冒泡排序和快速排序是基于这类方法的两种排序方法，冒泡排序算法的最坏时间复杂性是O（n*n） ，而快速排序算法的最坏时间复杂性是O（nlog2n）；所以快速排序比冒泡排序效率更高。
资料:错误
% r  r5 [# p# J& O4 g6 N
$ ^( `: i& \! j- Z/ W3 [/ o, c36.下列程序段实现的是顺序查找功能（） 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); }
资料:正确

37.注释内容太多会影响程序的执行效率。
资料:错误
# K; e( i3 a" l" x) `& y1 D" A
7 O/ ]* Y: q. @( I, N. n38.C语言中，数组名代表该数组的起始地址。
资料:正确

39.查找就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。
* a- m3 |* }  e+ F# w' l5 T" [( P5 z资料:正确
5 K! `2 q& H/ W( e- j+ F
40.确定性是指算法的每一个步骤必须要确切地定义。
资料:正确
5 f8 K  d9 O' a$ A$ I7 [0 T
41.遗传算法是计算数学中用于解决最优化的搜索算法，是进化算法的一种。
( w9 N- \/ ?( ~. J+ D资料:正确

42.有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。
资料:错误

43.关键字是数据元素（或记录）中某个数据项的值，可以标识一个记录，称为主关键字。
) h1 i- H8 i0 G9 ^$ k9 v资料:错误
. @& I2 S1 X& d! P
44.在任何情况下，顺序表中进行结点的插入操作时都不需要移动结点。
2 w1 z8 \0 g' k2 G: E8 t4 u资料:错误

45.C语言中，字符串作为字符数组来处理。
资料:正确

46.对于任意一棵二叉树，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。
7 }$ Q9 v8 k& Q资料:正确
, Y2 `7 K" p$ U3 |2 \
! y" l7 g2 H2 Z9 s( F/ `- O/ s


! t5 f2 l' p8 {
+ C, Z4 i3 S& K' N7 }
7 \# G  ]6 g" ]& B
% j3 Y3 A. M; \! C! |, x/ ]9 E

" A( r/ T2 T% l# o' B& W
: [6 z. @5 N: u$ @* S/ p% [3 }