[东北师范大学]《算法分析与设计》19秋在线作业1(100分）

admin

【奥鹏】[东北师范大学]算法分析与设计19秋在线作业1
试卷总分:100    得分:100
* X: G3 \! Z7 T0 K$ m0 S; p" I% ?第1题,下列算法描述所用的方法是()
6 P; f$ s+ S( J: P4 B  nBegin（算法开始）
输入 A，B，C
3 ]8 c. M& `0 `. V" eIF AB 则 A→Max
0 l! e9 R& l" t5 ?否则 B→Max
IF CMax 则 C→Max
Print Max
! g! q2 X+ ]$ a4 P2 {9 tEnd （算法结束）
3 [& p  l' K" A# _4 P: v4 SA、流程图
$ M2 }, I/ Q* N2 x+ sB、N-S流程图
C、伪代码表示
, r3 l! J( j6 sD、程序设计语言
正确资料:


2 [' T, X/ l1 Q) Z第2题,某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为（）。
: {1 y3 X; A! E; J& ~( N/ w' \A、n+1
& W) I/ ~4 }2 ^% u0 H, PB、n-1
C、2n
0 N- T0 z+ p. J" `3 c3 h5 nD、n/2
0 T2 Z$ N1 @. S' Q, Z/ y9 |7 F4 _正确资料:


' S, |+ E& @; u第3题,下列叙述中正确的是（）
9 q. {9 o$ }2 ~8 G8 U) i4 r6 eA、线性链表是线性表的链式存储结构
B、栈与队列是非线性结构
C、双向链表是非线性结构
- K& f1 Z4 e$ C6 @; y. |1 MD、只有根结点的二叉树是线性结构
正确资料:


$ L/ K8 C& {. o" g第4题,设有如下函数定义
' [2 f$ Z# {0 F! Zint fun(int k)
( m" N/ [6 i/ j" R! `" [0 c{ if (k1) return 0; else if(k==1) return 1; else return fun(k-1)+1;
9 M, P9 T* P7 _}
若执行调用语句：n=fun(3);，则函数fun 总共被调用的次数是()。
# |/ l6 R* ]! f6 R9 I9 N$ l- CA、2
0 ]7 f  W+ H, j; g, wB、3
C、4
8 ~' E: Y, t9 C0 F/ hD、5
正确资料:
* j9 b5 M* D$ {1 N) a* M" z

第5题,strchr（）函数用来（）。
A、字符串连接
) ?  @' @& T8 L4 `1 T& ^' @B、比较字符
; ~* u: g% E' C3 ]+ eC、求字符位置
D、求子串位置
; D2 J  \3 O0 o; H+ O+ T5 N: g正确资料:
  G$ n0 w7 a+ F- }$ E& r6 n$ s
. u! m$ ]# Q% B* ]1 h) b) a
8 u+ m4 [7 O0 P; m1 t  v第6题,下面4句话中，最准确的表述是()。
; ^" s9 C( g/ @' L$ Q) j: _A、程序=算法+数据结构
, X1 I5 S3 ]; bB、程序是使用编程语言实现算法
C、程序的开发方法决定算法设计
D、算法是程序设计中最关键的因素
, Q4 G! k0 x8 Y# r8 \+ x8 B正确资料:
8 {1 n$ G5 `+ G# `7 Y( y

7 u( G# ^; y8 x7 F第7题,一个递归算法必须包括()。
& f# @8 B1 U% W; k# I! f- r8 q. sA、递归部分
B、终止条件和递归部分
4 c3 b6 q: P; P3 r9 w" XC、循环部分
0 x: R+ K. c! SD、终止条件和循环部分
# `# c& a6 L7 u( o& }正确资料:
& k, h2 {) ~) @8 [$ }

) L: \/ T1 U- @第8题,插入排序在最好情况下的时间复杂度为()
1 L7 O; N3 J8 {7 `A、O(logn)
B、O(n)
1 n3 k4 V, w: j2 W* K! lC、O(n*logn)
7 l3 U0 d7 U+ s5 `/ P* QD、O(n2)
正确资料:

" C  P! o. S4 A- l# w: x8 U9 F
第9题,已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（C）。
A、39
9 H# y9 `8 R. V* _  K" [( H" F! RB、52
C、111
D、119
正确资料:
: Y/ L- Q! P9 k7 l  r% h7 A

9 ^/ d$ v  b% j6 X$ f* M第10题,strstr（）函数用来（）。
4 k4 C  N* Y4 SA、字符串连接
B、比较字符
C、求字符位置
D、求子串位置
& D# M* _2 L# G正确资料:

0 m' p9 A6 d3 P/ K3 z
第11题,在程序代码编辑框外（一般都是程序代码的最左侧）双击，就成功设置了一个断点，设置成功后会在该行的最前面显示一个圆点，这样的过程称作()。
A、设置断点
B、单步调试
' X. o/ m0 k: w9 l: N( K3 {C、程序编译
+ i, U7 H3 J% }0 E* mD、程序调试
* I& \' Z# ^& g9 E# S正确资料:


第12题,有以下程序
; g" B9 r( v6 }8 X* X% }# m#include stdio.h
$ ^6 z/ n, F& r* |7 S) r& x1 Q- uint f(int t[ ], int n );
main()
{ int a[4]={1, 2, 3, 4}, s; s=f(a, 4); printf("%d\n", s);
}
; u/ Q" s6 g/ F, v9 hint f(int t[ ], int n )
+ D3 @* Q) k7 S' E9 ^{ if(n0) return t[n-1]+f(t, n-1); else return 0;
/ P8 x: n# M- _: h# f}
# [4 f  n! w: l! j( R% Z/ J程序运行后的输出结果是()。
A、4
B、10
C、14
D、6
9 V' w4 T  G  l6 A& d正确资料:
( u8 R  b9 H* |0 {" V% L
- U- ]! _' C: t8 p3 T& u* D- a1 {
; U" o9 T4 Q! a( D% \. ]第13题,八进制中最大的数码是（）。
A、6
B、7
C、8
D、9
正确资料:


第14题,将f=1+1/2+1/3+…+1/n转化成递归函数，其递归体是()。
A、f(1)=0
B、f(1)=1
& l& k! w6 W+ `- e; t# e& kC、f(0)=1
D、f(n)=f(n-1)+1/n
正确资料:

: H8 m7 g$ \* Y8 f9 F, r
) x1 [/ w  Q; P第15题,分治法是把一个复杂的问题分成相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题解的()
A、合并
B、最大值
C、最小值
: h$ k5 C9 C/ f6 S4 }D、平均值
1 F+ _/ U7 m8 Y+ k7 G正确资料:
) V+ [! i3 f* B% e  d. b2 b. W! T2 m
, a0 b! B/ a6 w0 a- y6 ?
9 g8 x7 ?0 j* M2 R第16题,自动化的工具同样也能够帮助你跟踪程序，尤其当程序很复杂时效果更加明显，这种工具叫做()。
( O9 {! n% N" x; D8 }! }A、调试器
B、编辑器
C、编译器
D、调解器
正确资料:
. A. k0 O. X- r1 e: _$ |

第17题,strcpy（）函数用来（）。
7 _# m" u  v+ I! C+ dA、求字符串长度
B、比较字符
C、求子串
D、字符串拷贝
( B+ g% ^& T; j/ X, z正确资料:

% ^& ~, ], E, d( D( ]
% K3 _# l- f0 q) E4 }. k7 Q" z第18题,cd 目录名的功能是()。
5 L0 I& F% x& Z+ C  kA、退回到根目录
B、退回到上一级目录
C、进入特定的目录
D、显示出文本文件的内容
) q' a  |3 X" o9 S" C" w正确资料:
" p! ~0 N1 ~4 z

第19题,对于长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为（）。
A、log2n
7 B5 V0 D+ T6 _, o, \/ i; u  q/ FB、n/2
C、n
% b. x" n. d0 m, n- M0 OD、n+1
, V1 w3 Y6 B9 M4 E正确资料:
2 g4 _, R# g0 ^$ u# b- v, ?# F

  Z' s' t. H7 r9 j5 ?' x第20题,()嵌在源程序体中，用于描述其后的语句或程序段做什么工作，也就是解释下面要做什么，或是执行了下面的语句会怎么样。而不要解释下面怎么做，因为程序本身就是怎么做。
: Z: C4 D1 L( \* K- UA、文件注释
4 f0 Z0 \3 k$ ^$ vB、函数注释
C、功能注释
D、程序注释
8 b! W4 M+ G# i) f) f# ^) |# |0 `正确资料:

! b4 _0 |$ K' F/ L! X( k5 h1 {/ x
第21题,顺序结构、选择结构、循环结构三种结构共同特点是()
/ x! r8 E2 Z5 I. f0 xA、只有一个入口
6 Y3 Z7 Y1 ^- D" M8 ^B、只有一个出口
C、结构内的每一部分都有机会被执行到（不存在死语句）
: x: K  e# ?6 ]  pD、结构内不存在死循环（永远执行不完的循环）。
正确资料:
1 g" R: x  Q) M% a3 j

4 |" T; H5 l4 x( U5 f5 I; h第22题,字符串有关的格式字符有（ ）。
* K9 a  W' @2 mA、"%c"
B、"%d"
, d- h/ k0 j4 P& }7 C' A3 ]9 r/ gC、"%f"
D、"%s"
正确资料:
# \3 S% j! x) m0 U& T
# M  Y  E/ X3 ~
第23题,递归算法的执行过程分()和()两个阶段。
A、递归
B、递推
+ d$ p' h. V9 ]* r6 e8 _C、回归
D、回溯
正确资料:


5 V. t) U3 v9 z1 G& [第24题,设计递归算法有两点最为关键()和()。
* T: C5 K# ^3 a7 B# o) c4 w- yA、确定递推公式
' T+ e& h5 r' bB、确定边界（终了）条件（递归出口）
! a- C* h& o. `2 g. t. U5 fC、每次递归调用，都必须向基本条件前进
D、如果结果已知，那么，不用再重复调用递归
. H9 D# [1 l1 P3 j正确资料:


第25题,简单选择排序算法在最好情况下的时间复杂度为O（N）。
" H- _) Q& d; T9 @8 q* q: h% w5 IA、错误
B、正确
正确资料:
5 r/ V+ n" H. \$ k

0 b5 m+ B0 x' J1 r7 i2 i3 E5 c第26题,顺序查找是从线性表的一端开始，依次将每个元素的关键字同给定值K进行比较，若某元素关键字与K相等，则查找成功；若所有元素都比较完毕，仍找不到关键字为K的元素，则查找失败。
1 a0 g1 G: o% A$ CA、错误
: [% A( H% V# J0 P+ q3 J. IB、正确
' S4 ?- ]0 X7 z- A2 T; {正确资料:
$ ~. Q" [" Y- P9 Y+ i' @, N

第27题,冒泡排序的时间复杂度为O(n*n)。
9 @& z2 B2 X1 ]2 K' q/ wA、错误
B、正确
正确资料:


; a  h: @: c" w第28题,内排序要求数据一定要以顺序方式存储。
A、错误
B、正确
正确资料:

7 I/ S% v' r0 G, _  u' V  Q0 ^
& T2 ]3 V/ g$ a3 i! _& T% V! n2 O6 z9 K第29题,排序速度，进行外排序时，必须选用最快的内排序算法。
A、错误
/ `5 A' T# I( ]0 BB、正确
正确资料:

3 ?4 x6 F9 Q& d7 V* m: b" }
/ U# y8 m7 c9 {9 C6 I& G  {$ F第30题,gets()函数一次可以输入多个字符串。
A、错误
B、正确
( ]; A: D; g  C4 W正确资料:
( j$ H" U4 P6 S

第31题,采用顺序查找方式查找长度为n的线性表时，平均查找长度为(n-1)/2。
9 R2 ~1 i% i  @' }A、错误
8 `( Q. n" o& [( {B、正确
正确资料:
, E& h& C7 c0 ]# e  ~
' {: Y: Z* h7 ~# N3 C
! G% X7 u$ Z7 Q' D第32题,穷举法，也称辗转法，是一种针对于密码的破译方法，即将密码进行逐个推算直到找出真正的密码为止。
: R, H/ b# I1 DA、错误
B、正确
& Z  A6 O% K8 p% \* H: L; \正确资料:


6 a$ W) W( h. W; o第33题,程序调试的作用是将程序测试过程中发现的错误改正过来，程序调试后需要再次进行测试。
A、错误
B、正确
正确资料:
2 q  R  d' o9 b/ }
: g. r9 l, \3 U
第34题,具有10个顶点的无向图，边的总数最多为44。
A、错误
B、正确
正确资料:


* Y- m+ S& ]& N5 m" K/ y* a' ]第35题,递推实现的关键是找出递推公式。
6 Q. d# w* J1 S( o0 _/ v5 l5 qA、错误
B、正确
1 P8 L" S% `. a3 d% _. ^9 q正确资料:
* k" ~6 o7 m( e: H
* P9 _1 T  h/ z# m+ n4 i/ @: [
第36题,冒泡排序法每次比较的是相邻的两个数：a[i]和a[i+1]，如果前一个数比后一个数大，则马上交换。
% V* S! o) |3 [2 o1 J# k  j4 ^A、错误
B、正确
正确资料:
1 s; i8 w1 i" F& [6 l% r
# S5 e5 Z: h0 T. T! i- x
第37题,字符型和整型一般情况下可以通用。
0 G; V$ O% f8 d0 e5 L/ T, kA、错误
B、正确
正确资料:


' y; N( k" ]$ j第38题,在深度为7的满二叉树中，度为2的结点个数为64。
A、错误
B、正确
7 Y6 ~  g+ k9 Y" t3 v9 o正确资料:


& E% C$ h7 T& ?第39题,用二分（对半）查找表的元素的速度比用顺序法快。
: M/ p9 f: U1 l3 N& RA、错误
B、正确
6 h, F6 ^/ e2 j+ m+ h, m0 u正确资料:
: c- L$ y+ K" ]) q3 G

第40题,某二叉树中度为2的结点有18个，则该二叉树中有20个叶子结点。
A、错误
- e* v3 ~3 [# B% V% ^B、正确
正确资料:
/ d9 |- S2 [8 z+ n  p! ]& ?
. n1 J5 T% r0 K) `. v
第41题,线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的顺序存储结构。
5 E( V! _! Y0 v) vA、错误
% Z. u. ]% b6 ], }" b: ]8 a" C* YB、正确
正确资料:

' j. r$ u+ ~( Z! n9 K3 D
0 F* Q6 {* n0 e第42题,C语言中，数组名代表该数组的起始地址。
A、错误
6 k0 V6 t1 B8 N# FB、正确
- ~$ y% Q, T# z" Y正确资料:
/ l3 C- i1 u; s- W: S

9 d2 Z! A$ \' m4 i第43题,线性表需要为表示结点间的逻辑关系而增加额外的存储空间。
A、错误
B、正确
正确资料:
% m  B9 f4 L5 k( K1 z) J
, `  A* |6 ~8 b1 s" l# l4 m( `
第44题,在待排数据基本有序的情况下，快速排序效果最好。
A、错误
5 c4 ^* ~% A0 Q# x$ zB、正确
; \8 h& W- u- N+ F' Y: t正确资料:
' f3 J- Z% o  k
; T' Q% N2 }; ?/ _+ t' g2 x
3 m" c* U! E3 F' i1 q) E第45题,在后序遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。
A、错误
B、正确
正确资料:
) E9 h! `% P  u" Y
9 x  T. M$ [) u% u5 s0 H
7 y7 ~& \+ I; Z第46题,scanf()、printf()可以输入输出几个字符串。
A、错误
2 n$ ?! }* Y/ l5 uB、正确
正确资料: