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

admin

【奥鹏】[东北师范大学]算法分析与设计18秋在线作业2
0 \" y8 O  c' [试卷总分:100    得分:100
第1题,一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树的总结点数为（ ）。
A、219
: D7 M8 G3 W5 X. [- C- b" VB、221
C、229
D、231
, X- H7 O& q3 W# A  Y4 W2 P
- `0 o1 I7 _2 q6 d
+ D+ r, S0 M( u" Y
3 u6 V/ l" S6 I7 a( ~: h/ _  r第2题,深度优先搜索的搜索策略是()。
A、尽可能"深"地搜索图
B、尽可能"深"地搜索树
  G" Z/ c& g! g) Y* VC、尽可能"深"地搜索表
D、尽可能"深"地搜索队列

: [  \- p/ z$ u6 L% m
" A/ v* P- b( U: |9 q9 Y1 ]% x! q
第3题,八进制的基数是（）。
A、2
B、8
: q( H/ F' R. k0 Q) e! d5 a4 oC、10
% y3 Y, J; i# {3 k& a1 [/ t* CD、16


. S& C, `+ s5 |( K
2 z# X' P% u7 a$ }1 Y8 s* ~  I+ \第4题,在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为()。
8 M; r: X% b7 x( d& }5 u2 YA、63
B、64
C、6
D、7

# K: q4 u) c* ]# p) D0 N2 Y
2 Z, u, ^7 q5 H' e% f3 n% i
第5题,strlen(str)是用来（）。
" U& V2 s; n  VA、求字符串长度
B、比较字符
9 ]- F& l' R2 {8 v# a/ Q$ G: n3 i3 z% ZC、求子串
D、字符串拷贝


7 q7 n* F7 U( F" ^% g4 i" U/ |' _
第6题,图中有关路径的定义是（）。
A、由顶点和相邻顶点序偶构成的边所形成的序列
/ {( X( j! \' @6 AB、由不同顶点所形成的序列
. N( K2 m' E) }1 P8 WC、由不同边所形成的序列
D、上述定义都不是
" K& _3 d4 h# e, A/ x6 A, R
% k' X2 I. Q5 a/ m
! a9 l: b7 P9 @5 J4 \
第7题,在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为()。
A、5, 8, 10, 12
5 k0 ]8 c1 I" j! d. M4 q; lB、6, 9, 11, 12
C、4, 7, 9, 12
D、1, 4, 8, 12


7 s6 z; ~1 G: `
第8题,设无向图的顶点个数为n，则该图最多有（）条边。
: p( j  L4 F) `- EA、n-1
( \8 g/ j1 _! u9 ^6 E& K9 ?- EB、n(n-1)/2
  c4 q3 U, h: g0 r3 {' e) t- UC、n(n+1)/2
4 J% e8 @4 z4 t* A7 g# tD、n2



. }7 x6 a7 B5 f) _3 {第9题,对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为()。
A、（N+1）/2
4 S& I6 e  Y# n9 P& x9 W/ n, mB、N/2
( ?( C7 c* y6 u8 Z# g8 wC、N
+ k- z  r' x# E0 f( z" {D、[（1+N）*N ]/2
3 s, C$ A3 }4 ?0 W' j) E


第10题,字符数组在进行指定初值时，若未指定数组长度，则长度（）初值个数。
A、小于
- \$ t9 z& G9 y& ]& ?/ UB、等于
; t5 u4 u1 B$ L% }& D2 A8 A6 aC、大于
D、不等于



, m9 m4 Q& v" s2 U% p0 e第11题,数制也称计数制，是用一组固定的符号和统一的规则来表示（）的方法。
" D# A" _0 Y4 g6 {A、数值
4 F4 x5 `; l# b7 r+ ?- tB、字母
C、文字
; E- g/ `& Z3 t" g& lD、信息


" m0 o4 i, V7 N- \
第12题,递归法是一总种编程策略，它需要有递归前进段、递归返回段和()。
A、判断条件
# ^. E" H; p* G0 H" ]B、初始条件
C、边界条件
D、决策条件



1 C. F5 i5 d. @2 z  P第13题,cd 目录名的功能是()。
A、退回到根目录
B、退回到上一级目录
% C" g0 C$ u$ l- B/ F0 d3 v) ]9 TC、进入特定的目录
/ N5 l6 g) t3 P1 I7 L, N; t3 lD、显示出文本文件的内容

$ Z+ }3 ?6 ]' ^5 p. j7 O7 O0 k

/ _2 g  @; Z: O  m) z第14题,以C语言为例，下列四个选项中，均是不合法的用户标识符的是()。
7 g% j: Y# J" [A、BA、x_0、do
( f/ z% Z; M: Q" W, DB、float、1a0、_Y
8 W7 W' w3 W* ^- PC、x-y、goto、123
. m' q# p$ V8 iD、_123、tmp、CHAR
- N1 A6 n$ W" X
5 t% `% D1 o; _: \

0 u; X+ O( o* r7 _* C7 R第15题,下列数据结构中，能用二分法进行查找的是()。
: h$ x2 N4 _* P* C7 V* ^+ y9 c, tA、顺序存储的有序线性表
B、线性链表
; U/ a2 s4 S0 W* uC、二叉链表
D、有序线性链表



第16题,strcmp("a","b")返回的值是（）
A、2
, k. h( N, R( l( VB、1
C、0
D、-1

" e# K3 Z) `7 u" l" P

. p9 L' ~( H/ J; S  G2 m/ i第17题,()是一个开放源代码的、基于Java的可扩展开发平台。
8 a/ e; f0 r! b/ w" O8 GA、VS
4 _0 C: n" U0 R. ~9 T% PB、Dev-C++
C、Eclipse
) n$ Y& w7 D' Y, H- @8 VD、JDK

  n) e4 `9 L) v7 f0 K

8 U5 c( |% S. E7 M5 R: q第18题,如何一步步的跟踪代码，找到问题，搞明白为何程序不能正常运行，这个过程称为()。
* K4 v5 z7 h# G. i: j+ EA、编写程序
4 g( b- d! p/ W$ BB、调试程序
# U: E) K- b) \C、执行程序
D、编译程序
3 S  D) k: l# \


第19题,下列排序算法中，占用辅助空间最多的是：()
A、归并排序
B、快速排序
6 N3 h) E) c1 q2 L9 EC、希尔排序
D、堆排序
& U" [6 W/ F! S5 R& Q* U$ f
" |" g% X# k# T  b3 H3 a. ]. Q

第20题,语句 printf("%d\n",strlen("ATS\n012\1\\"));的输出结果是（）。
$ ~/ y& V8 i; A' w9 BA、11
, }9 K; q- }# e4 p: vB、10
. Y0 F3 h: W, b& @' n- FC、9
D、8

7 O& H  J8 I5 G9 o" I$ e

第21题,设计递归算法有两点最为关键()和()。
( t" Z2 Y5 p% H' S4 ]+ hA、确定递推公式
B、确定边界（终了）条件（递归出口）
C、每次递归调用，都必须向基本条件前进
D、如果结果已知，那么，不用再重复调用递归
,B
1 T! _0 |3 R$ `  Y! M4 i
( y7 T: J2 i; k% m
第22题,字符串有关的格式字符有（ ）。
) U  z8 k  o# S6 _$ Z, v! oA、"%c"
B、"%d"
' v5 F# @$ E1 x  b% fC、"%f"
$ k4 S7 S! _6 pD、"%s"
,D

& b' r$ z/ s/ f0 W7 O4 c
第23题,顺序结构、选择结构、循环结构三种结构共同特点是()
- k( ~# B; z% ~2 a' kA、只有一个入口
9 M. m/ d' O: s9 \0 DB、只有一个出口
+ j' D  M7 O6 F9 W8 \* hC、结构内的每一部分都有机会被执行到（不存在死语句）
D、结构内不存在死循环（永远执行不完的循环）。
,B,C,D


第24题,递归算法的执行过程分()和()两个阶段。
3 X3 R0 F2 ]7 B; I! p. EA、递归
B、递推
0 x: @/ [0 w( @& C3 s) B4 |C、回归
6 f  A2 q6 C, c' O2 zD、回溯
/ N' N! d, X4 m, d- f$ {4 u,C
. h2 u) a$ G5 V7 \; N) b0 ?

第25题,十进制数转换成二进制数，须将整数部分和小数部分分别转换。
A、错误
8 p, {* z/ R4 }2 y' m( xB、正确
; B6 E# e# D0 e  i
5 @' F; T( S$ D

) o0 f# n* s3 E; e* K: Q第26题,在深度为7的满二叉树中，度为2的结点个数为64。
A、错误
3 r. f1 {+ ]6 k2 |: h# OB、正确

) L4 R8 O' V- w1 h/ [. g
% u( g9 F: C9 w
第27题,一棵二叉树有10个度为1的结点，7个度为2的结点，则该二叉树共有25个结点。
A、错误
# G7 B6 t$ T( AB、正确


8 k& ~. _% K  u+ A+ j* u7 Y. m/ I
第28题,查找就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。
% V: y# X: [$ M7 o& h7 d3 U3 Q/ TA、错误
/ q3 ^$ T5 L. H0 ?8 v' z5 k; w2 FB、正确
  g, a( u; U+ S+ v
3 I2 u4 Q7 n9 ~% E( U% S/ y% X
# G5 `6 r9 U1 t. H
& M+ w  C: I; \% z: F4 o- ?% j第29题,字符数组的初始化可以逐个元素进行初始化。
A、错误
* h* I$ O$ V, \, W" W  H- nB、正确
0 n  ?5 `. W. ~+ e8 R0 b; Z: @9 A
. v4 f( O1 E3 x' z
- w. t  u. U: u% d
第30题,插入排序是一种稳定排序方法。
% S: c$ N% t5 I# i. IA、错误
( E4 ?& s, x5 N0 hB、正确
( e9 @# n9 z& q0 d4 D

  l- q! z5 j1 e) ^
第31题,一个栈的初始状态为空，首先将元素5，4，3，2，1依次入栈，然后退栈一次，再将元素A、B、C、D依次入栈，之后将所有元素全部退栈，则所元素退栈（包括中间退栈的元素）的顺序为1DCBA2345。
A、错误
B、正确



  o1 m: a1 f3 o8 e第32题,在进行单步调试时，按F4开始调试，程序便会直接运行到断点处。
A、错误
B、正确

3 W' P0 y" G7 ?( k$ b" m( Q6 ?/ c) e
; H4 t5 o' S! X" ]! P1 C) m
( D( |+ l1 {2 V. z, N( A- A1 L第33题,递推就是在函数里调用自身。
A、错误
B、正确
" V' A4 M5 M5 f3 B5 @) H


- p0 [1 F( t' @- a3 M! ~% s  S6 U第34题,顺序查找是从线性表的一端开始，依次将每个元素的关键字同给定值K进行比较，若某元素关键字与K相等，则查找成功；若所有元素都比较完毕，仍找不到关键字为K的元素，则查找失败。
& K4 g- x/ |+ f, D& FA、错误
$ R# F( O! m% L4 ~. f- M) qB、正确

: w! s, X  U0 m$ m

5 E" m+ B) d5 [第35题,递推实现的关键是找出递推公式。
A、错误
B、正确


# n4 f* l' b$ ^" @9 ?
第36题,字符串"Hello"与字符串"hello"相等。
7 ~4 u* [0 E$ T+ DA、错误
* E& w+ F+ P$ ]$ }  ?! o" z+ c+ pB、正确

- o9 [  B! Q" x5 E* o
. l1 s  m! C4 m8 ^
; B# @' j) j! b8 `! f8 J+ d第37题,排序的关键操作是：一是比较两个关键字大小，二是将记录从一个位置移动到另一个位置。
A、错误
+ _  m' m- i+ }; `# r& A, RB、正确



第38题,查找算法的效率用平均查找长度（ASL）进行度量
  T4 c/ z0 L( P( ?, |; m$ ?( uA、错误
3 q- l( u6 @3 S+ {8 E! i* K# d( rB、正确

  {6 n; r4 N: n( z3 w2 K
$ U0 a& L  T, h( z) W# {* o2 {
% S6 t4 g$ s+ L  U- i, Y第39题,从已知条件出发，逐步推出要解决的问题，这种方法称为倒推法。
8 F+ R. Q/ \3 f$ _9 _, PA、错误
B、正确
* E3 S0 y1 U( G3 v( w- `
6 v# t7 L! S+ a
" E" @, h2 c7 \+ l0 [
第40题,float b[4][5]；定义b为5×6(5行6列)的数组。
A、错误
# T1 Y9 s) q9 v, o! U# ?/ P& [& tB、正确
+ V! }0 z1 t+ d; p7 J( @: ~
; _" U. m7 ^" n. J3 k+ c: w+ Z

1 B3 W4 G7 p( v! p9 k0 }! B第41题,已知一棵度为3的树有2个度为1的结点，3个度过为2的结点，4个度为3的结点，则该树中有12个叶子结点。
A、错误
B、正确


$ C( K4 x5 O- L  [+ j. A$ K  T
第42题,折半查找的先决条件：表中结点按关键字有序，且顺序（一维数组）存储。
- N( G3 Q$ n8 F# l/ h5 \A、错误
B、正确



第43题,含有空格字符的串称为空格串，其长度为0。
; C! c! A! }" b  s8 IA、错误
6 v! g; G; Y$ n7 g( BB、正确
5 F+ M& W- A: U% |. g' `


4 L- z# E6 W/ ^第44题,程序调试的作用是将程序测试过程中发现的错误改正过来，程序调试后需要再次进行测试。
A、错误
6 t1 g+ n: x/ wB、正确
8 ~* h6 v% j+ y0 O/ Y- e
7 V! Z& A& E; G8 U2 }& j

0 D/ h, o! `* @( i第45题,对于二分查找，表必须有序，表可以顺序方式存储，也可以链表方式存储。
; y6 y8 B- a  E) o% f- FA、错误
B、正确


3 W+ b- ^2 z$ }# r& d  a
第46题,冒泡排序法每次比较的是相邻的两个数：a[i]和a[i+1]，如果前一个数比后一个数大，则马上交换。
# n; G% J4 R6 _  s; d1 l6 ]A、错误
B、正确



" s% l6 v! b4 W; E0 j
! j2 O; ?7 s! u! n3 f1 B8 R$ [5 o

+ v  X" j- E" @: e  b: C6 c, `
# {5 T8 z; ]+ x; S# D6 I8 g7 R) i



8 t; f" ~4 U( k. ?1 K! m$ u
* S# F1 q/ c; C5 e& m6 ^& A1 u
2 w/ t: \) u% c, O3 ^7 I