东师15秋《算法分析与设计》在线作业答案

[在线作业]东师15秋《算法分析与设计》在线作业答案

一、单选题(共20道试题，共40分。)

1.文件注释不包括以下()。

A.程序的标题或文件名

B.程序的目的、功能说明

C.核心算法

D.文件作者、最后修改日期等说明。

满分：2分

2.遗传算法主要模拟生物中的()。

A.遗传、复制、传递和分裂

B.遗传、突变、选择和杂交

C.遗传、突变、传递和转录

D.遗传、复制、转录和逆转录

满分：2分

3有以下程序#include<stdio.h>intf(intt[],intn);main(){inta[4]={1,2,3,

4},s;s=f(a,4);printf("%d\n",s);}intf(intt[],intn){if(n>0)return

t[n-l]+f(t,n-1);elsereturn0;}程序运行后的输出结果是()。

A.4

B.10

C.14

D.6

满分：2分

4.下列叙述中正确的是()

A.数据的逻辑结构与存储结构必定是一一对应的

B.由于计算机在存储空间上是向量式的存储结构，因此，利用数组只能处

理线性结构

C.程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理

线性结构

D.以上说法都不对

满分：2分

5.函数strlen("JinlinChangchun")函数值是()

A.15

B.16

C.17

D.18

满分：2分

6.下列排序算法中()排序在一趟结束后不一定能选出一个元素放在其最终

位置上。

A.选择

B.冒泡

C.归并

D.堆

满分：2分

7.一个有n个结点的图，最多有()个连通分量。

A.0

B.1

C.n-1

D.n

满分：2分

8.strcmp("a",“b")返回的值是()

A.2

B.1

C.0

D.-1

满分：2分

9.有以下程序，程序的运行结果是()。#include<stdio.h>intf(intx){inty;if

(x==Ollx==l)return(3);y=x*x-f(x-2);returny;}main(){intz;z=f(3);

printf("％d\n”,z);}

A.0

B.9

C.6

D.8

满分：2分

lO.isalpha()函数用来()。

A.判断字母

B.判断数字

C.判断大写

D.判断小写

满分：2分

11.数制中表示基本数值大小的不同数字符号称为()。

A.进制

B.基数

C•位权

D.数码

满分：2分

12.字符串“ChinaBeijing"的长度是O

A.12

B.13

C.14

D.15

满分：2分

13.一个算法中的语句的()被称为语句频度或时间频度。

A.执行时间

B,占用空间

C.执行速度

D.执行次数

满分：2分

14.一般情况下，算法中基本操作重复执行的次数是问题规模n的某个()。

A.导数

B.指数

C.对数

D.函数

满分：2分

15.cd目录名的功能是()。

A.退回到根目录

B,退回到上一级目录

C.进入特定的目录

D,显示出文本文件的内容

满分：2分

16.使用()，可以简化日常或重复性任务，使用方便、灵活，功能强大，自

动化程度高。

A.文件读写函数

B.批处理文件

C.单步调试功能

D,设置断点

满分：2分

17.()命令主要用来查看磁盘中文件的命令。

A.dir

B.cd

C.type

D.fc

满分：2分

18.能正确进行字符串赋值、赋初值的语句组是()。

A.chars[5]={'a','e','i','o','u')；

B.char*s;s="good!";

C.chars[5]="good!";

D.chars[5]="good!";

满分：2分

19.下面命名规则中，哪项不是现在比较常用的命名规则()。

A.匈牙利命名法

B.骆驼命名法

C.下划线命名法

D.图灵命名法

满分：2分

20.下面不是递归算法的特点的是()。

A.递归就是在函数里调用自身

B.在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口

C.递归算法解题通常显得很简洁，递归算法的运行效率较高

D.在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存

储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程

序。

满分：2分

二、多选题（共5道试题，共20分。）

1.高精度运算主要解决（）。

A.

B,加数

C.减数

D.运算结果的输入

E.运算结果的存储

满分：4分

2.设计递归算法有两点最为关键（）和（）。

A.确定递推公式

B.确定边界（终了）条件（递归出口）

C.每次递归调用，都必须向基本条件前进

D.如果结果已知，那么，不用再重复调用递归

满分：4分

3.字符串有关的格式字符有（）。

A."%c"

B."%d"

C."%f"

D."%s"

满分：4分

4.顺序结构、选择结构、循环结构三种结构共同特点是0

A.只有一个入口

B.只有一个出口

C.结构内的每一部分都有机会被执行到（不存在死语句）

D,结构内不存在死循环（永远执行不完的循环）。

满分：4分

5.递归算法的执行过程分（）和（）两个阶段。

A.递归

B.递推

C.回归

D.回溯

满分：4分

三、判断题(共20道试题，共40分。)

l.stricmp()函数和strcmp()函数相同。

A.错误

B.正确

满分：2分

2.用二分(对半)查找表的元素的速度比用顺序法快。

A.错误

B.正确

满分：2分

3.快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。

A.错误

B.正确

满分：2分

4.已知有序表(13,18,24,35,47,50,62,83,90,115,134),当折半查找值为90的元

素时，查找成功的比较次数为4次

A.错误

B.正确

满分：2分

5.当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能

进行入队运算。这种情况称为下溢。

A.错误

B.正确

满分：2分

6.一个栈的初始状态为空，首先将元素5,4,3,2,1依次入栈，然后退

栈一次，再将元素A、B、C、D依次入栈，之后将所有元素全部退栈，则

所元素退栈（包括中间退栈的元素）的顺序为1DCBA2345。

A.错误

B.正确

满分：2分

7.使用冒泡排序法对n个数进行排序必须要进行n趟比较。

A.错误

B.正确

满分：2分

8.内排序要求数据一定要以顺序方式存储。

A.错误

B.正确

满分：2分

9.长度不同的字符串一定不会相等。

A.错误

B.正确

满分：2分

10.从已知条件出发，逐步推出要解决的问题，这种方法称为倒推法。

A.错误

B.正确

满分：2分

11.一棵二叉树第6层（根结点为第一层）的结点数最多为32个。

A.错误

B.正确

满分：2分

12.折半查找的先决条件：表中结点按关键字有序，且顺序（一维数组）存

储。

A.错误

B.正确

满分：2分

13.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。

A.错误

B.正确

满分：2分

14.遗传算法是计算数学中用于解决最优化的搜索算法，是进化算法的一

种。

A.错误

B.正确

满分：2分

15.下列程序段实现的是顺序查找功能()intSearch(intarray[],intn,intkey)

{inti;array[n]=key;for(i=0;key!=array[i];i++);return(i<ni:-l);}

A.错误

B.正确

满分：2分

16.在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n)。

A.错误

B.正确

满分：2分

17.插入排序的时间复杂度为O(n)o

A.错误

B.正确

满分：2分

18.一个scanf函数输入多个字符串，输入时以“空格”键作为字符串间的

分隔。

A.错误

B.正确

满分：2分

19.树中所有结点度的最大值就是树的深度。

A.错误

B.正确

满分：2分

20.当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能

进行入队运算。这种情况称为上溢。

A.错误

B.正确

满分：2分算法分析与设计15秋在线作业2

试卷总分：100测试时间：--

一、单选题(共20道试题，共40分。)

1.一个递归算法必须包括()。

A.递归部分

B.终止条件和递归部分

C.循环部分

D.终止条件和循环部分

满分：2分

2.如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互

位置发生颠倒，则称该排序算法是不稳定的。()就是不稳定的排序方法。

A.起泡排序

B.归并排序

C.Shell排序

D,直接插入排序

满分：2分

3.在编写代码时，除了要保证代码的正确性，还要保证代码的()。

A.完美性

B.美观性

C.独特性

D,可读性

满分：2分

4.在有序表A[L12]中，采用二分查找算法查等于A[12]的元素，所比较的

元素下标依次为()。

A.5,8,10,12

B.6,9,11,12

C.4,7,9,12

D.1,4,8,12

满分：2分

5.如何一步步的跟踪代码，找到问题，搞明白为何程序不能正常运行，这

个过程称为()。

A.编写程序

B.调试程序

C.执行程序

D.编译程序

满分：2分

6.将f=l+l/2+l/3+-+l/n转化成递归函数，其递归体是()。

A.f(l)=O

B.f(l)=l

C.f(O)=l

D.f(n)=f(n-l)+l/n

满分：2分

7.在长度为n的线性表中，寻找最大项至少需要比较()次

A.n

B.n-1

C.n/2

D.(n-l)/2

满分：2分

8.设无向图的顶点个数为n,则该图最多有()条边。

A.n-1

B.n(n-l)/2

C.n(n+l)/2

D.n2

满分：2分

9.有以下程序，其运行后的结果是()。#include<stdio.h>voidfun(intn,int*p)

{intfl,f2;if(n==llln==2)*p=l;else{fun(n-1,&fl);fun(n-2,&f2);

*p=fl+f2;}}main(){ints;fun(3,&s);printf("%d\n",s);}

A.2

B.3

C.4

D.5

满分：2分

10.下列数据结果中，能够按照“先进后出”原则存取数据的是()

A.循环队列

B.栈

C.队列

D.二叉树

满分：2分

11.在字符数组中每个元素最多可存放()个字符。

A.0

B.1

C.2

D.任意

满分：2分

12.分枝定界法的基本思想()。

A.不断用变量的旧值递推新值的过程

B,把全部可行的解空间不断分割为越来越小的子集(称为分支)，并为每

个子集内的解的值计算一个下界或上界

C.将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原

问题的解

D.一种用若干步可重复的简运算(规律)来描述复杂问题的方法

满分：2分

13.将递归算法转换成对应的非递归算法时，通常需要使用()。

A.栈

B.队列

C.链表

D.树

满分：2分

14.已知一列数{897,4,1,2},使用简单选择排序法对其按照升序进行排列,

第0趟比较之后数列为()

A.8,9,7,4,1,2

B.1,9,7,4,8,2

C.8,7,4,1,2,9

D.1,2,8,9,7,4

满分：2分

15.例如“camelCase”和"printEmployeePaychecks()”这样的命名规则是

()o

A.匈牙利命名法

B.骆驼命名法

C.下划线命名法

D.帕斯卡命名法

满分：2分

16.在程序代码编辑框外(一般都是程序代码的最左侧)双击，就成功设置

了一个断点，设置成功后会在该行的最前面显示一个圆点，这样的过程称

作()。

A,设置断点

B.单步调试

C.程序编译

D.程序调试

满分：2分

17.charszValue[20];函数itoa(32,szValue,16)使得szValue的内容变为()

A.32

B.20

C.16

D.40

满分：2分

18.运算式(2008)10—(3723)8的结果是()。

A.0

B.-5

C.5

D.10

满分：2分

19.对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次

数中正确的是()。

A.冒泡排序为n/2

B.冒泡排序为n

C.快速排序为n

D.快速排序为n(n-l)/2

满分：2分

20.()是一个基本完整的开发工具集，它包括了整个软件生命周期中所需要

的大部分工具，如UML工具、代码管控工具、集成开发环境等等。

A.VM

B.VS

C.Dev-C++

D.IDE

满分：2分

二、多选题(共5道试题，共20分。)

1.字符串有关的格式字符有()。

A."%c"

B."%d"

C."%f"

D."%s"

满分：4分

2.高精度运算主要解决（）。

A.

B,加数

C.减数

D.运算结果的输入

E.运算结果的存储

满分：4分

3.顺序结构、选择结构、循环结构三种结构共同特点是0

A.只有一个入口

B.只有一个出口

C.结构内的每一部分都有机会被执行到（不存在死语句）

D,结构内不存在死循环（永远执行不完的循环）。

满分：4分

4.递归算法的执行过程分（）和（）两个阶段。

A.递归

B.递推

C.回归

D.回溯

满分：4分

5.设计递归算法有两点最为关键()和()。

A.确定递推公式

B.确定边界(终了)条件(递归出口)

C.每次递归调用，都必须向基本条件前进

D.如果结果已知，那么，不用再重复调用递归

满分：4分

三、判断题(共20道试题，共40分。)

1.深度为k(k>=l)的二叉树至多有2Ak-l个结点。

A.错误

B.正确

满分：2分

2.具有10个顶点的无向图，边的总数最多为44。

A.错误

B.正确

满分：2分

3.C语言中，数组名代表该数组的起始地址。

A.错误

B.正确

满分：2分

4.从已知条件出发，逐步推出要解决的问题，这种方法称为倒推法。

A.错误

B.正确

满分：2分

5.字符数组的初始化可以逐个元素进行初始化。

A.错误

B.正确

满分：2分

6.在前序遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接

跟在该结点之后。

A.错误

B.正确

满分：2分

7.有向图G的强连通分量是指极大强连通子图。

A.错误

B.正确

满分：2分

8.递归是计算机中的一种常用算法。它是按照一定的规律来计