算法设计与分析（20秋）形考作业1

试卷总分:100  得分:100

一、单选题 (共 14 道试题,共 56 分)

1.八进制的基数是（）。

A.2

B.8

C.10

D.16

2.isupper（）函数用来（）。

A.判断字母

B.判断数字

C.判断大写

D.判断小写

3.栈和队列的共同点是（ ）

A.都是先进先出

B.都是先进后出

C.只允许在端点处插入和删除元素

D.没有共同点

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

A.匈牙利命名法

B.骆驼命名法

C.下划线命名法

D.图灵命名法

5.下列排序算法中，占用辅助空间最多的是：()

A.归并排序

B.快速排序

C.希尔排序

D.堆排序

6.有以下程序，执行后的输出结果是()。 fun(int x) { int p; if(x==0||x==1) return (3); p=x-fun(x-2); return p; } main() { printf(“%d\n”,fun(7)); }

A.7

B.3

C.2

D.0

7.数制中表示基本数值大小的不同数字符号称为（）。

A.进制

B.基数

C.位权

D.数码

8.strchr（）函数用来（）。

A.字符串连接

B.比较字符

C.求字符位置

D.求子串位置

9.对于循环队列，下列叙述中正确的是（ ）

A.队头指针是固定不变的

B.队头指针一定大于队尾指针

C.队头指针一定小于队尾指针

D.队头指针可以大于队尾指针，也可以小于队尾指针

10.()是一个开放源代码的、基于Java的可扩展开发平台。

A.VS

B.Dev-C++

C.Eclipse

D.JDK

11.九进制，就表示某一位置上的数运算时是逢（）进一位。

A.2

B.8

C.9

D.10

12.字符串比较的函数是（）。

A.strlen()

B.strcpy()

C.strcmp()

D.strcat()

13.IDE的全程是()。

A.集成开发环境

B.集成环境

C.开发软件

D.调试过程

14.十六进制的213，1的位权是（）。

A.0

B.1

C.8

D.16

二、多选题 (共 1 道试题,共 4 分)

15.顺序结构、选择结构、循环结构三种结构共同特点是()

A.只有一个入口

B.只有一个出口

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

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

三、判断题 (共 10 道试题,共 40 分)

16.puts()函数一次可以输出多个字符串。

17.注释内容太多会影响程序的执行效率。

18.插入排序的时间复杂度为O（n）。

19.当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为上溢。

20.递归算法是一种用若干步可重复的简单运算（规律）来描述复杂问题的方法。

21.快速排序总比简单排序快。

22.假如A="Jinlin changchun"，B="changchun",则B是A的子串。

23.归并排序在任何情况下都比所有简单排序速度快。

24.为提高在外排序过程中，对长度为N的初始序列进行“置换—选择”排序时，可以得到的最大初始有序段的长度不超过N/2。

25.strncmp（）函数和stricmp（）函数相同。

算法设计与分析（20秋）形考作业2

试卷总分:100  得分:100

一、单选题 (共 14 道试题,共 56 分)

1.在启发式搜索中,最重要的是() 。

A.对搜索位置进行评估

B.对搜索时间进行限定

C.对搜索速度进行控制

D.对搜索目标的设定

2.下面的时间复杂度按数量级递增的顺序排列，正确的是注释从功能上可以分为()。

A.平方阶O(n2)，对数阶O(log2n)，指数阶O(2n)

B.线性对数阶O(nlog2n)，指数阶O(2n)，立方阶O(n3)

C.常数阶O(1)，线性阶O(n)，指数阶O(2n)

D.k次方阶O(nk)，指数阶O(2n)，对数阶O(log2n)

3.下列叙述中正确的是 （ ）

A.循环队列有队头和队尾两个指针，因此，循环队列是非线性结构

B.在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况

C.在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况

D.循环队列中元素的个数是由队头指针和队尾指针共同决定

4.有以下程序 #include<stdio.h> void fun(int x) { if(x/2>1) fun(x/2); printf("%d", x); } main() { fun(7); printf("\n"); } 程序运行后的输出结果是()。

A.1 3 7

B.7 3 1

C.7 3

D.3 7

5.十六进制数C1B转换为二进制数是（）。

A.1100101101011

B.110000011011

C.10110101010

D.11101001011

6.函数strlen("JinlinChangchun")的函数值是()

A.15

B.16

C.17

D.18

7.十进制中最小的数码是（）。

A.10

B.9

C.1

D.0

8.一般情况下，算法中基本操作重复执行的次数是()的某个函数。

A.问题类型

B.问题难度

C.问题结构

D.问题规模

9.如何一步步的跟踪代码，找到问题，搞明白为何程序不能正常运行，这个过程称为()。

A.编写程序

B.调试程序

C.执行程序

D.编译程序

10.在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是()。

A.选择

B.冒泡

C.插入

D.堆

11.如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。()就是不稳定的排序方法。

A.起泡排序

B.归并排序

C.Shell排序

D.直接插入排序

12.十进制数2024等值于十六制数为( )。

A.7E8

B.6F7

C.7AB

D.3DF

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

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

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

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

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

14.在下列排序算法中,哪一个算法的时间复杂度与初始排序无关()。

A.直接插入排序

B.冒泡排序

C.快速排序

D.直接选择排序

二、多选题 (共 1 道试题,共 4 分)

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

A."%c"

B."%d"

C."%f"

D."%s"

三、判断题 (共 10 道试题,共 40 分)

16.递推实现的关键是找出递推公式。

17.以特定的图形符号加上说明表示算法的图，称为框图。

18.非线性结构的逻辑特征是一个结点可能有多个直接前趋和直接后继。

19.函数atoi("1234")的函数返回值是1234。

20.快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。

21.在程序中关键字和变量名之间不需要加空格。

22.快速排序的基本思想是将每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。

23.当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。

24.归并排序是一种稳定的排序方法。

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

算法设计与分析（20秋）形考作业3

试卷总分:100  得分:100

一、单选题 (共 14 道试题,共 56 分)

1.下列说法错误的是()

A.使用高级计算机语言，如C、C++、Java，编写的程序，都需要经过编译器编译或解释，才能转化成机器能够识别并能执行的二进制代码。

B.如何一步步的跟踪代码，找到问题，搞明白为何程序不能正常运行，这个过程称为调试程序。

C.自动化的工具同样也能够帮助你跟踪程序，尤其当程序很复杂时效果更加明显，这种工具叫做调试器。

D.调试器并能解决程序中出现的问题。

2.十六进制的基数是（）。

A.2

B.8

C.10

D.16

3.九进制，就表示某一位置上的数运算时是逢（）进一位。

A.2

B.8

C.9

D.10

4.十进制的123，1的位权是（）。

A.1

B.2

C.10

D.100

5.一个有n个结点的图，最多有（）个连通分量。

A.0

B.1

C.n-1

D.n

6.()通常位于函数或过程的开头部分，它应当给出函数或过程的整体说明，对于理解程序本身具有引导作用。

A.文件注释

B.函数注释

C.功能注释

D.程序注释

7.一个良好算法的基本单元是：顺序结构、循环结构和()。

A.线性结构

B.离散结构

C.数据结构

D.选择结构

8.支持子程序调用的数据结构是（ ）

A.栈

B.树

C.队列

D.二叉树

9.广度优先搜索的原则()。

A.按时间遍历解空间

B.按代价遍历解空间

C.按层遍历解空间

D.按速度遍历解空间

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

A.文件读写函数

B.批处理文件

C.单步调试功能

D.设置断点

11.下列说法正确的是()。

A.关键字是数据元素（或记录）中某个数据项的值，可以标识一个记录，称为主关键字。

B.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。

C.对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为log2n。

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

12.以下选项中合法的字符常量是（）。

A."B"

B.68

C.D

D.'\010'

13.八进制的基数是（）。

A.2

B.8

C.10

D.16

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

A.匈牙利命名法

B.骆驼命名法

C.下划线命名法

D.图灵命名法

二、多选题 (共 1 道试题,共 4 分)

15.递归算法的执行过程分()和()两个阶段。

A.递归

B.递推

C.回归

D.回溯

三、判断题 (共 10 道试题,共 40 分)

16.在前序遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。

17.stricmp（）函数和strcmp()函数相同。

18.strncmp（）函数和stricmp（）函数相同。

19.一个队列的初始状态为空。现将元素A,B,C,D,E,F,5,4,3,2,1 依次入队，然后再依次退队，则元素退队的顺序为54321ABCDEF。

20.字符串的结束标记在输出时也会被输出。

21.二叉树第i(i>=1)层上至多有2^(i-1)个结点。

22.递推算法是一种用若干步可重复的简单运算（规律）来描述复杂问题的方法。

23.能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解很容易构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。

24.高精度计算时可以用字符串来存储运算结果。

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