.
22. 假设有3种硬币，它们的面值分别是1元、5角、1角。现在有一个小孩买了价值6元3角的东
西，并给售货员10元钱。当售货员找给小孩零钱时，在各种硬币充足的情况下，如果按贪心算法进行找钱，1元、5角、1角的数量分别是_____。 ---A|B|C|D (A) 2、4、7 (B) 3、1、9 (C) 4、2、2 (D) 3、1、2
23. 用递归求n!, 当n=1时，f(1)=1,否则f(n)=f(n-1)*n。当n=3时，递归调用顺序正确的是
________。---A|B|C|D (A) f(1) 、f(2) 、f(3) (B) f(2)、f(3)、f(1) (C) f(3) 、f(2) 、f(1) (D) 以上都不对
24. 有4位选手参加羽毛球循环赛，循环赛共进行3次，每位选手要与其他3 位选手比赛一场，且
每位选手每天比赛一场，不能轮空 ，下面哪个方案符合分治算法安排的结果______。---A|B|C|D
A.
B.
C.
. .
.
D.
A. O（3n2+4n+5） B. O（3n2+4n） C. O（n2 ） D. O（1）
25. 如果一个算法的时间频度T(n)=3n2+4n+5，则其时间复杂度为_________。 ---A|B|C|D
26. 如果一个算法的时间频度T(n)= 4n+5，则其时间复杂度为（）---A|B|C|D
A. O（4n+5） B. O（4n） C. O（n） D. O（1）
27.
第7讲 数据结构
1. 数据结构是算法设计的重要步骤，针对不同问题的算法设计应该选择适当的数据结构，不同的数
据结构会使得解决问题的算法的性能有所不同。关于数据结构，下列说法不正确的是______________？--A|B|C|D
(A) 数据结构由逻辑结构、存储结构及运算3部分组成； (B) 存储结构定义了数据在存储器中的存储方式；
(C) 数组使用顺序存储结构，并借助元素在存储器中的相对位置来表示数据元素的逻辑关系； (D) 在树结构中，指针用于表达元素之间的逻辑关系——父子关系，每个元素的指针指向其父节点，因此一个元素可以有一个或多个指针。
2. 有关栈数据结构的说法，不正确的是_____。--A|B|C|D
(A) 栈按照先进先出（FIFO, First In First Out）的原理运作； (B) 栈按照后进先出（LIFO, Last In First Out）的原理运作； (C) 栈可以使用顺序存储结构作为存储结构； (D) 栈可以使用链式存储结构作为存储结构。
. .
.
3. 有关栈数据结构的基本运算，说法不正确的是_____。--A|B|C|D
(A) 入栈是将数据放入堆栈的顶端，栈顶端指针top加一； (B) 出栈是将栈顶端的数据取出，栈顶端指针top减一； (C) 如果栈顶端指针top为1，则栈为空；
(D) 如果是固定长度的栈，当栈顶端指针top与长度相等时，栈是满的。
4. 假定当前栈顶端指针top=10，欲将栈底的元素取出，其他的元素仍然保持在栈中，则需要进行
______次出栈（POP）操作，________次入栈（PUSH）操作。--A|B|C|D (A) 11，8 (B) 2，1 (C) 10，9 (D) 10，0
5. 算法的时间复杂性，可以表达为关于问题规模n的一个函数T(n)，T(n)可以用大O表示法来处
理。问T(n)=O(f(n))是什么意思？正确的是_________。---A|B|C|D。 (A)T(n)是关于f(n)的一个函数； (B)T(n)是与f(n)同数量级的函数；
(C)T(n)是将函数f(n)代入O(x)中所形成的新函数； (D)T(n)是依据f(n)计算出来的；
6. 关于SELECTION-SORT(选择排序)算法的基本思想，下列说法正确的是_____。---A|B|C|D。
(A)一个元素一个元素的处理。每次处理一个元素，通过与当前已排序元素的比较，将该元素放(B)一个轮次一个轮次的处理。将元素集合分成两个部分，已排序元素集合和未排序元素集合，开始时已排序元素集合为空。在每一轮次，从未排序元素集合中找出最小值的元素，将其移入已排序元素集合；直到未排序元素集合为空时则算法结束。
(C)一个轮次一个轮次的处理。在每一轮次中依次对待排序数组元素中相邻的两个元素进行比较：如不符合排序关系，则交换两个元素。直到某一轮次没有元素交换发生则结束。
7. 关于BUBBLE-SORT(冒泡排序)算法的基本思想，下列说法正确的是_____。---A|B|C|D。
(A)一个元素一个元素的处理。每次处理一个元素，通过与当前已排序元素的比较，将该元素放(B)一个轮次一个轮次的处理。将元素集合分成两个部分，已排序元素集合和未排序元素集合，开始时已排序元素集合为空。在每一轮次，从未排序元素集合中找出最小值的元素，将其移入已排序元素集合；直到未排序元素集合为空时则算法结束。
(C)一个轮次一个轮次的处理。在每一轮次中依次对待排序数组元素中相邻的两个元素进行比较：如不符合排序关系，则交换两个元素。直到某一轮次没有元素交换发生则结束。
(D)上述说法都不正确。
入到当前正确排序的位置。直到最后一个元素则算法结束。
(D)上述说法都不正确。
入到当前正确排序的位置。直到最后一个元素则算法结束。
. .
.
8. 关于排序的选择法和冒泡法，下列说法不正确的是_____。---A|B|C|D。
(A)“选择法”和“冒泡法”都是每一轮次找出一个最小值元素，它们寻找最小值元素的方法是一样(B)“选择法”通过将所有未排序元素与当前轮次待寻找的最小值元素进行比较，获得当前轮次的最小值元素；而“冒泡法”通过相邻元素的两两比较，一个轮次完成也能获得一个最小值元素；
(C)虽然“选择法”和“冒泡法”都是每一轮次找出一个最小值元素，但选择法每轮次仅比较，没有交换，直至找到最小值后做一次交换；而冒泡法每一轮次是通过相邻元素比较来找最小值，如果不满足排序，则交换相邻两个元素，交换可能频繁发生。这样来看，选择法比冒泡法要快一些；
9. 关于BUBBLE-SORT(冒泡排序)算法，已知N=10，下列说法正确的是_____。---A|B|C|D。
(A)第5轮次，是将第1个元素至第6个元素之间的元素，相邻者进行比较； (B)第4轮次，是将第1个元素至第10个元素之间的元素，相邻者进行比较； (C)第2轮次，是将第10个元素至第2个元素之间的元素，相邻者进行比较； (D)第3轮次，是将第10个元素至第1个元素之间的元素，相邻者进行比较；
10. 在逻辑上可以把数据结构分成_________。--A|B|C|D
(A) 线性结构和非线性结构 (B) 动态结构和静态结构 (C) 紧凑结构和非紧凑结构 (D) 内部结构和外部结构
11. 线性表的物理存储结构分为顺序结构和链式结构，其中链式结构中单链表用__________来表示各
结点之间的逻辑关系？--A|B|C|D A. 数据 B. 序号 C. 指针 D. 位置
12. 下面关于二分查找的叙述正确的是___________。 --A|B|C|D
A. B. C. D.
13. 对线性表进行二分查找时，要求线性表必须___________。---A|B|C|D
(A) 以顺序方式存储
. .
的；
(D)“选择法”是对“冒泡法”的改进算法，效率更高。
表必须有序，表可以顺序方式存储，也可以链表方式存储 表必须有序，而且只能从小到大排列
表必须有序且表中数据必须是整型，实型或字符型 表必须有序，且表只能以顺序方式存储