算法分析与设计基础第三版答案第一章
This?le contains the exercises,hints,and solutions for Chapter1of the book”Introduction to the Design and Analysis of Algorithms,”3rd edition,by A.Levitin.The problems that might be challenging for at least some students are marked by B;those that might be di?cult for a majority of students are marked by I
Exercises1.1
1.Do some research on al-Khorezmi(also al-Khwarizmi),the man from
whose name the word“algorithm”is derived.In particular,you should learn what the origins of the words“algorithm”and“algebra”have in common.
2.Given that the o?cial purpose of the U.S.patent system is the promo-
tion of the“useful arts,”do you think algorithms are patentable in this country?Should they be?
3.a.Write down driving directions for going from your school to your home
with the precision required from an algorithm’s description.
b.Write down a recipe for cooking your favorite dish with the precision
required by an algorithm.
4.Design an algorithm for computing b√ for any positive integer .Be-
sides assignment and comparison,your algorithm may only use the four basic arithmetical operations.
5.Design an algorithm to?nd all the common elements in two sorted lists
of numbers.For example,for the lists2,5,5,5and2,2,3,5,5,7,the output should be2,5,5.What is the maximum number of comparisons your algorithm makes if the lengths of the two given lists are and respectively?
6.a.Find gcd(31415,14142)by applying Euclid’s algorithm.
b.Estimate how many times faster it will be to?nd gcd(31415,14142)
by Euclid’s algorithm compared with the algorithm based on checking consecutive integers from min{ }down to gcd( )
7.B Prove the equality gcd( )=gcd( mod )for every pair of positive
integers and .
8.What does Euclid’s algorithm do for a pair of integers in which the?rst
is smaller than the second?What is the maximum number of times this can happen during the algorithm’s execution on such an input?
9.a.What is the minimum number of divisions made by Euclid’s algorithm
among all inputs1≤ ≤10?
1
b.What is the maximum number of divisions made by Euclid’s algorithm
among all inputs1≤ ≤10?
10.a.Euclid’s algorithm,as presented in Euclid’s treatise,uses subtractions
rather than integer divisions.Write pseudocode for this version of Euclid’s algorithm.
b.I Euclid’s game(see[Bog])starts with two unequal positive in-
tegers on the board.Two players move in turn.On each move,a player has to write on the board a positive number equal to the di?erence of two numbers already on the board;this number must be new,i.e.,di?erent from all the numbers already on the board.The player who cannot move loses the game.Should you choose to move?rst or second in this game?
11.The extended Euclid’s algorithm determines not only the greatest
common divisor of two positive integers and but also integers(not necessarily positive) and ,such that + =
a.Look up a description of the extended Euclid’s algorithm(see,e.g.,
[KnuI,p.13])and implement it in the language of your choice.
b.Modify your program to?nd integer solutions to the Diophantine
equation + = with any set of integer coe?cients , ,and . 12.B Locker doors There are lockers in a hallway,numbered sequentially
from1to .Initially,all the locker doors are closed.You make passes by the lockers,each time starting with locker#1.On the th pass, =
1 2 ,you toggle the door of every th locker:if the door is closed,you
open it;if it is open,you close it.After the last pass,which locker doors are open and which are closed?How many of them are open?
2
Hints to Exercises1.1
1.It is probably faster to do this by searching the Web,but your library
should be able to help,too.
2.One can?nd arguments supporting either view.There is a well established
principle pertinent to the matter,though:scienti?c facts or mathematical expressions of them are not patentable.(Why do you think it is the case?) But should this preclude granting patents for all algorithms?
3.You may assume that you are writing your algorithms for a human rather
than a machine.Still,make sure that your descriptions do not contain obvious ambiguities.Knuth provides an interesting comparison between cooking recipes and algorithms[KnuI,p.6].
4.There is a quite straightforward algorithm for this problem based on the de?nition of b√ c.
5.Try to design an algorithm that always makes less than comparisons.
6.a.Just follow Euclid’s algorithm as described in the text.
https://www.sodocs.net/doc/d72919629.html,pare the number of divisions made by the two algorithms.
7.Prove that if divides both and (i.e., = and = for some
positive integers and ),then it also divides both and = mod and vice versa Use the formula = + (0≤ )and the fact that if divides two integers and it also divides + and ? (Why?)
8.Perform one iteration of the algorithm for two arbitrarily chosen integers
9.The answer to part(a)can be given immediately;the answer to part
(b)can be given by checking the algorithm’s performance on all pairs
1 ≤10
https://www.sodocs.net/doc/d72919629.html,e the equality
gcd( )=gcd( ? )for ≥ 0
b.The key is to?gure out the total number of distinct integers that can be
written on the board,starting with an initial pair where ≥1 You should exploit a connection of this question to the question of part
(a).Considering small examples,especially those with =1and =2
should help,too.
11.Of course,for some coe?cients,the equation will have no solutions.
12.Tracing the algorithm by hand for,say, =10and studying its outcome
should help answering both questions.
3
Solutions to Exercises1.1
1.Al-Khwarizmi(9th century C.E.)was a great Arabic scholar,most famous
for his algebra textbook.In fact,the word“algebra”is derived from the Arabic title of this book while the word“algorithm”is derived from a translation of Al-Khwarizmi’s last name(see,e.g.,[KnuI,pp.1-2],[Knu96, pp.88-92,114]).
2.This legal issue has yet to be settled.The current legal state of a?airs
distinguishes mathematical algorithms,which are not patentable,from other algorithms,which may be patentable if implemented as computer programs(e.g.,[Cha00]).
3.n/a
4.A straightforward algorithm that does not rely on the availability of an approximate value of√ can check the squares of consecutive positive integers until the?rst square exceeding is encountered.The answer will be the number’s immediate predecessor.Note:A much faster algorithm for solving this problem can be obtained by using Newton’s method(see Sections11.4and12.4).
5.Initialize the list of common elements to empty.Starting with the?rst ele-
ments of the lists given,repeat the following until one of the lists becomes https://www.sodocs.net/doc/d72919629.html,pare the current elements of the two lists:if they are equal, add this element to the list of common elements and move to the next elements of both lists(if any);otherwise,move to the element following the smaller of the two involved in the comparison.
The maximum number of comparisons,which is made by this algorithm on some lists with no common elements such as the?rst positive odd numbers and the?rst positive even numbers,is equal to + ?1 6.a.gcd(31415 14142)=gcd(14142 3131)=gcd(3131 1618)=
gcd(1618 1513)=gcd(1513 105)=gcd(1513 105)=gcd(105 43)=
gcd(43 19)=gcd(19 5)=gcd(5 4)=gcd(4 1)=gcd(1 0)=1
b.To answer the question,we need to compare the number of divisions
the algorithms make on the input given.The number of divisions made by Euclid’s algorithm is11(see part a).The number of divisions made by the consecutive integer checking algorithm on each of its14142itera-tions is either1and2;hence the total number of multiplications is be-tween1·14142and2·14142.Therefore,Euclid’s algorithm will be between 1·14142 11≈1300and2·14142 11≈2600times faster.
4
7.Let us?rst prove that if divides two integers and it also divides
both + and ? .By de?nition of division,there exist integers and such that = and = Therefore
± = ± =( ± )
i.e., divides both + and ?
Also note that if divides it also divides any integer multiple of Indeed,since divides = Hence
= ( )=( )
i.e., divides
Now we can prove the assertion in question.For any pair of positive integers and if divides both and ,it also divides both and = mod = ? Similarly,if divides both and = mod = ? it also divides both = + and Thus,the two pairs ( )and( )have the same?nite nonempty set of common divisors, including the largest element in the set,i.e.,gcd( )=gcd( )
8.For any input pair such that0≤ Euclid’s algorithm simply
swaps the numbers on the?rst iteration:
gcd( )=gcd( )
because mod = if Such a swap can happen only once since gcd( )=gcd( mod )implies that the?rst number of the new pair ( )will be greater than its second number( mod )after every iteration of the algorithm.
9.a.For any input pair ≥ ≥1 in which is a multiple of Euclid’s
algorithm makes exactly one division;it is the smallest number possible for two positive numbers.
b.The answer is5divisions,which is made by Euclid’s algorithm in
computing gcd(5 8) It is not too time consuming to get this answer by examining the number of divisions made by the algorithm on all input pairs1 ≤10
Note:A pertinent general result(see[KnuII,p.360])is that for any input pair where0≤ the number of divisions required by Euclid’s algorithm to compute gcd( )is at most b log (3? ) )c where √5) 2.
=(1+
5
10.a.Here is a nonrecursive version:
Algorithm Euclid2( )
//Computes gcd( )by Euclid’s algorithm based on subtractions
//Input:Two nonnegative integers and not both equal to0
//Output:The greatest common divisor of and
while =0do
if swap( )
← ?
return
b.It is not too di?cult to prove that the integers that can be written on
the board are the integers generated by the subtraction version of Euclid’s algorithm and only them.Although the order in which they appear on the board may vary,their total number always stays the same:It is equal to gcd( ) where is the maximum of the initial numbers which includes two integers of the initial pair.Hence,the total number of possible moves is gcd( )?2 Consequently,if gcd( )is odd, one should choose to go?rst;if it is even,one should choose to go second.
11.n/a
12.Since all the doors are initially closed,a door will be open after the last
pass if and only if it is toggled an odd number of times.Door (1≤ ≤ ) is toggled on pass (1≤ ≤ )if and only if divides Hence,the total number of times door is toggled is equal to the number of its divisors.
Note that if divides i.e. = then divides too.Hence all the divisors of can be paired(e.g.,for =12 such pairs are1and12,2 and6,3and4)unless is a perfect square(e.g.,for =16 4does not have another divisor to be matched with).This implies that has an odd number of divisors if and only if it is a perfect square,i.e., = 2 Hence doors that are in the positions that are perfect squares and only such doors will be open after the last pass.The total number of such positions not exceeding is equal to b√ c:these numbers are the squares of the positive integers between1and b√ c inclusively.
6
Exercises1.2
1.Old World puzzle A peasant?nds himself on a riverbank with a wolf,
a goat,and a head of cabbage.He needs to transport all three to the
other side of the river in his boat.However,the boat has room for only the peasant himself and one other item(either the wolf,the goat,or the cabbage).In his absence,the wolf would eat the goat,and the goat would eat the cabbage.Solve this problem for the peasant or prove it has no solution.(Note:The peasant is a vegetarian but does not like cabbage and hence can eat neither the goat nor the cabbage to help him solve the problem.And it goes without saying that the wolf is a protected species.)
2.New World puzzle There are four people who want to cross a rickety
bridge;they all begin on the same side.You have17minutes to get them all across to the other side.It is night,and they have one?ashlight.A maximum of two people can cross the bridge at one time.Any party that crosses,either one or two people,must have the?ashlight with them.The ?ashlight must be walked back and forth;it cannot be thrown,for example.
Person1takes1minute to cross the bridge,person2takes2minutes, person3takes5minutes,and person4takes10minutes.A pair must walk together at the rate of the slower person’s pace.(Note:According to
a rumor on the Internet,interviewers at a well-known software company
located near Seattle have given this problem to interviewees.)
3.Which of the following formulas can be considered an algorithm for com-
puting the area of a triangle whose side lengths are given positive numbers , ,and ?
a. =p ( ? )( ? )( ? ) where =( + + ) 2
b. =1
sin where is the angle between sides and
2
c. =1
where is the height to base
2
4.Write pseudocode for an algorithm for?nding real roots of equation 2+
+ =0for arbitrary real coe?cients and (You may assume the availability of the square root function ( ) )
5.Describe the standard algorithm for?nding the binary representation of
a positive decimal integer
a.in English.
b.in pseudocode.
6.Describe the algorithm used by your favorite ATM machine in dispensing
cash.(You may give your description in either English or pseudocode, whichever you?nd more convenient.)
7
7.a.Can the problem of computing the number be solved exactly?
b.How many instances does this problem have?
c.Look up an algorithm for this problem on the Internet.
8.Give an example of a problem other than computing the greatest common
divisor for which you know more than one algorithm.Which of them is simpler?Which is more e?cient?
9.Consider the following algorithm for?nding the distance between the two
closest elements in an array of numbers.
Algorithm MinDistance( [0 ?1])
//Input:Array [0.. ?1]of numbers
//Output:Minimum distance between two of its elements
←∞
for ←0to ?1do
for ←0to ?1do
if = and| [ ]? [ ]|
←| [ ]? [ ]|
return
Make as many improvements as you can in this algorithmic solution to the problem.If you need to,you may change the algorithm altogether;if not, improve the implementation given.
10.One of the most in?uential books on problem solving,titled How To Solve
It[Pol57],was written by the Hungarian-American mathematician George Pólya(1887—1985).Pólya summarized his ideas in a four-point summary.
Find this summary on the Internet or,better yet,in his book,and compare it with the plan outlined in Section1.2.What do they have in common?
How are they di?erent?
8
Hints to Exercises1.2
1.The peasant would have to make several trips across the river,starting
with the only one possible.
2.Unlike the Old World puzzle of Problem1,the?rst move solving this
puzzle is not obvious.
3.The principal issue here is a possible ambiguity.
4.Your algorithm should work correctly for all possible values of the coe?-
cients,including zeros.
5.You almost certainly learned this algorithm in one of your introductory
programming courses.If this assumption is not true,you have a choice between designing such an algorithm on your own or looking it up.
6.You may need to make a?eld trip to refresh your memory.
7.Question(a)is di?cult,though the answer to it–discovered in1760s
by the German mathematician Johann Lambert–is well-known.By comparison,question(b)is incomparably simpler.
8.You probably know two or more di?erent algorithms for sorting an array
of numbers.
9.You can:decrease the number of times the inner loop is executed,make
that loop run faster(at least for some inputs),or,more signi?cantly,design
a faster algorithm from scratch.
10.n/a
9
Solutions to Exercises1.2
1.Let P,w,g,and c stand for the peasant,wolf,goat,and cabbage head,
respectively.The following is one of the two principal sequences that solve the problem:
Pwgc P g
w c
g
Pw c
Pwg
c
w
P gc
Pw c
g
w c
P g
Pwgc
Note:This problem is revisited later in the book(see Section6.6).
2.Let1,2,5,10be labels representing the men of the problem, represent
the?ashlight’s location,and the number in the parenthesis be the total amount of time elapsed.The following sequence of moves solves the problem:
(0) 1,2
(2)
2
(3)
2,5,10
(13)
5,10
(15)
1,2,5,10
(17)
3.a.The formula can be considered an algorithm if we assume that we know
how to compute the square root of an arbitrary positive number.
b.The di?culty here lies in computing sin Since the formula says
nothing about how it has to be computed,it should not be considered an algorithm.This is true even if we assume,as we did for the square root function,that we know how to compute the sine of a given angle.(There are several algorithms for doing this but only approximately,of course.) The problem is that the formula says nothing about how to compute angle either.
c.The formula says nothing about how to compute .
4.Algorithm Quadratic( )
//The algorithm?nds real roots of equation 2+ + =0
//Input:Real coe?cients
//Output:The real roots of the equation or a message about their absence if =0
← ? ?4? ?
if 0
←2?
1←(? + ( ))
2←(? ? ( ))
10
return 1 2
else if =0return? (2? )
else return‘no real roots’
else// =0
if =0return?
else// = =0
if =0return‘all real numbers’
else return‘no real roots’
Note:See a more realistic algorithm for this problem in Section11.4. 5.a.Divide the given number by2:the remainder (0or1)will be
the next(from right to left)digit of the binary representation in question.
Replace by the quotient of the last division and repeat this operation until becomes0.
b.Algorithm Binary( )
//The algorithm implements the standard method for?nding
//the binary expansion of a positive decimal integer
//Input:A positive decimal integer
//Output:The list ?1 1 0of ’s binary digits
←0
while =0
← mod2
←b 2c
← +1
6.n/a
7.a. ,as an irrational number,can be computed only approximately.
b.It is natural to consider,as an instance of this problem,computing
’s value with a given level of accuracy,say,with correct decimal digits.
With this interpretation,the problem has in?nitely many instances.
8.n/a
9.The following improved version considers the same pair of elements only
once and avoids recomputing the same expression in the innermost loop: Algorithm MinDistance2( [0 ?1])
//Input:An array [0.. ?1]of numbers
//Output:The minimum distance between two of its elements
11
←∞
for ←0to ?2do
for ← +1to ?1do
←| [ ]? [ ]|
if
←
return
A faster algorithm is based on the idea of presorting(see Section6.1).
10.Pólya’s general four-point approach is:
1.Understand the problem
2.Devise a plan
3.Implement the plan
4.Look back/check
12
Exercises1.3
1.Consider the algorithm for the sorting problem that sorts an array by
counting,for each of its elements,the number of smaller elements and then uses this information to put the element in its appropriate position in the sorted array:
Algorithm ComparisonCountingSort( [0 ?1], [0 ?1])
//Sorts an array by comparison counting
//Input:Array [0 ?1]of orderable values
//Output:Array [0 ?1]of ’s elements sorted in nondecreasing order for ←0to ?1do
[ ]←0
for ←0to ?2do
for ← +1to ?1do
if [ ] [ ]
[ ]← [ ]+1
else [ ]← [ ]+1
for ←0to ?1do
[ [ ]]← [ ]
a.Apply this algorithm to sorting the list60,35,81,98,14,47.
b.Is this algorithm stable?
c.Is it in place?
https://www.sodocs.net/doc/d72919629.html, the algorithms for the searching problem that you already know.
Give a good succinct description of each algorithm in English.(If you know no such algorithms,use this opportunity to design one.)
3.Design a simple algorithm for the string-matching problem.
4.K?nigsberg bridges The K?nigsberg bridge puzzle is universally accepted
as the problem that gave birth to graph theory.It was solved by the great Swiss-born mathematician Leonhard Euler(1707—1783).The problem asked whether one could,in a single stroll,cross all seven bridges of the city of K?nigsberg exactly once and return to a starting point.Following is a sketch of the river with its two islands and seven bridges:
13
a.State the problem as a graph problem.
b.Does this problem have a solution?If you believe it does,draw such
a stroll;if you believe it does not,explain why and indicate the small-
est number of new bridges that would be required to make such a stroll possible.
5.Icosian Game A century after Euler’s discovery(see Problem4),an-
other famous puzzle–this one invented by the renown Irish mathemati-cian Sir William Hamilton(1805-1865)–was presented to the world under the name of the Icosian Game.The game was played on a circular wooden board on which the following graph was carved:
Find a Hamiltonian circuit–a path that visits all the graph’s vertices exactly once before returning to the starting vertex–for this graph.
6.Consider the following problem:Design an algorithm to determine the
best route for a subway passenger to take from one designated station to another in a well-developed subway system similar to those in such cities as Washington,D.C.,and London,UK.
a.The problem’s statement is somewhat vague,which is typical of real-
life problems.In particular,what reasonable criterion can be used for de?ning the“best”route?
b.How would you model this problem by a graph?
7.a.Rephrase the traveling salesman problem in combinatorial object terms.
b.Rephrase the graph-coloring problem in combinatorial object terms.
14
8.Consider the following map:
b
a
d
c
e
f
a.Explain how we can use the graph-coloring problem to color the map
so that no two neighboring regions are colored the same.
https://www.sodocs.net/doc/d72919629.html,e your answer to part(a)to color the map with the smallest number
of colors.
9.Design an algorithm for the following problem:Given a set of points
in the Cartesian plane,determine whether all of them lie on the same circumference.
10.Write a program that reads as its inputs the( )coordinates of the
endpoints of two line segments 1 1and 2 2and determines whether the segments have a common point.
15
Hints to Exercises1.3
1.Trace the algorithm on the input https://www.sodocs.net/doc/d72919629.html,e the de?nitions of stability
and being in-place that were introduced in the section.
2.If you do not recall any searching algorithms,you should design a simple
searching algorithm(without succumbing to the temptation to?nd one in the latter chapters of the book).
3.This algorithm is introduced later in the book,but you should have no
trouble to design it on your own.
4.If you have not encountered this problem in your previous courses,you
may look up the answers on the Web or in a discrete structures textbook.
The answers are,in fact,surprisingly simple.
5.No e?cient algorithm for solving this problem for an arbitrary graph is
known.This particular graph does have Hamiltonian circuits that are not di?cult to?nd.(You need to?nd just one of them.)
6.a.Put yourself(mentally)in a passenger’s place and ask yourself what
criterion for the“best”route you would use.Then think of people that may have di?erent needs.
b.The representation of the problem by a graph is straightforward.Give
some thoughts,though,to stations where trains can be changed.
7.a.What are tours in the traveling salesman problem?
b.It would be natural to consider vertices colored the same color as
elements of the same subset.
8.Create a graph whose vertices represent the map’s regions.You will have
to decide on the edges on your own.
9.Assume that the circumference in question exists and?nd its center?rst.
Also,do not forget to give a special answer for ≤2
10.Be careful not to miss some special cases of the problem.
16
Solutions to Exercises1.3
1.a.Sorting60,35,81,98,14,47by comparison counting will work as
follows:
Array [0 5]
Initially []
After pass =0 []
After pass =1 []
After pass =2 []
After pass =3 []
After pass =4 []
Final state []
Array [0 5]
b.The algorithm is not stable.Consider,as a counterexample,the
result of its application to10,100
c.The algorithm is not in place because it uses two extra arrays of size
: and
2.Answers may vary but most students should be familiar with sequential
search,binary search,binary tree search and,possibly,hashing from their introductory programming courses.
3.Align the pattern with the beginning of the https://www.sodocs.net/doc/d72919629.html,pare the corre-
sponding characters of the pattern and the text left-to right until either all the pattern characters are matched(then stop–the search is success-ful)or the algorithm runs out of the text’s characters(then stop–the search is unsuccessful)or a mismatching pair of characters is encountered.
In the latter case,shift the pattern one position to the right and resume the comparisons.
4.a.If we represent each of the river’s banks and each of the two islands by
17
vertices and the bridges by edges,we will get the following graph:
a c
(This is,in fact,a multigraph,not a graph,because it has more than one edge between the same pair of vertices.But this doesn’t matter for the issue at hand.)The question is whether there exists a path (i.e.,a sequence of adjacent vertices)in this multigraph that traverses all the edges exactly once and returns to a starting vertex.Such paths are called Eulerian circuits ;if a path traverses all the edges exactly once but does not return to its starting vertex,it is called an Eulerian path .
b.Euler proved that an Eulerian circuit exists in a connected (multi)graph if and only if all its vertices have even degrees,where the degree of a ver-tex is de ?ned as the number of edges for which it is an endpoint.Also,an Eulerian path exists in a connected (multi)graph if and only if it has exactly two vertices of odd degrees;such a path must start at one of those two vertices and end at the other.Hence,for the multigraph of the puz-zle,there exists neither an Eulerian circuit nor an Eulerian path because all its four vertices have odd degrees.
If we are to be satis ?ed with an Eulerian path,two of the multigraph’s vertices must be made even.This can be accomplished by adding one new bridge connecting the same places as the existing bridges.For example,a new bridge between the two islands would make possible,among others,
18
the walk ? ? ? ? ? ? ? ?
c If we want a walk that returns to its starting point,all the vertices in
the corresponding multigraph must be even.Since a new bridge/edge changes the parity of two vertices,at least two new bridges/edges will be needed.For example,here is one such“enhancement”:
c This woul
d mak
e possible ? ? ? ? ? ? ? ? ? ,among several other such walks.
19
5.A Hamiltonian circuit is marked on the graph below:
6.a.At least three“reasonable”criteria come to mind:the fastest trip,a
trip with the smallest number of train stops,and a trip that requires the smallest number of train changes.Note that the?rst criterion requires the information about the expected traveling time between stations and the time needed for train changes whereas the other two criteria do not require such information.
b.A natural approach is to mimic subway plans by representing sta-
tions by vertices of a graph,with two vertices connected by an edge if there is a train line between the corresponding stations.If the time spent on changing a train is to be taken into account(e.g.,because the station in question is on more than one line),the station should be represented by more then one vertex.
7.a.Find a permutation of given cities for which the sum of the distances
between consecutive cities in the permutation plus the distance between its last and?rst city is as small as possible.
b.Partition all the graph’s vertices into the smallest number of disjoint
subsets so that there is no edge connecting vertices from the same subset.
8.a.Create a graph whose vertices represent the map’s regions and the
edges connect two vertices if and only if the corresponding regions have a common border(and therefore cannot be colored the same color).Here
20
算法分析与设计复习题及参考答案
网络教育课程考试复习题及参考答案算法分析与设计一、名词解释：1.算法 2.程序 3.递归函数 4.子问题的重叠性质 5.队列式分支限界法 6.多机调度问题7.最小生成树二、简答题： 1.备忘录方法和动态规划算法相 比有何异同？简述之。 2.简述回溯法解题的主要步骤。 3.简述动态规划算法求解的基本要素。 4.简述回溯法的基本思想。 5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 6.简要分析分支限界法与回溯法的异同。7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？8.贪心算法求解的问题主要具有哪些性质？简述之。9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。10.简述分析贪心算法与动态规划 算法的异同。三、算法编写及算法应用分析题： 1.已知有3个物品： (w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。 2.按要求完成以下关于排序和查找的问题。①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。③给出上述算法的递归算法。④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。已知，=1，2，3，4，5，6，=5，=10，=3，=12，=5，=50，=6，kijr*r1234567ii1求矩阵链积A×A×A×A×A×A的最佳求积顺序（要求给出计算步骤）。1234564.根据分枝限界算法基本过程,求解0-1背包问题。已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。 5.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。6.试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：①删除一个字符。②插入一个字符。③将一个字符改为另一个字符。请写出该算法。7.对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。be2g212ad323182cf2h 8.试写出用分治法对数组A[n]实现快速排序的算法。9.有n个活动争用一个活动室。已知活动i占用的时间区域为[s，f ]，活动i,j相容的条件是：sj≥f ii，问题的解表示为(x| x =1，2…，n,)，x表示顺序为i的活动编号活动，求一个相容的活动子集，iiii且安排的活动数目最多。xxx10.设、、是一个三角形的三条边，而且x+x+x=14。请问有多少种不同的三角形？给出解答过程。12312311.
算法设计与分析考试题及答案
算法设计与分析考试题 及答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】
一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分，衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD ｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ，先求解_子问题 ，然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4，在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ，且 (a 1,a 2,a 3,a 4)=(4,5,12,10)，(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}； 最优值为：38 4. 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0） 5. 设S=｛X 1，X 2，···，X n ｝是严格递增的有序集，利用二叉树的结点来存储S 中的元素，在表示S 的二叉搜索树中搜索一个元素X ，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i ，其概率为b i 。（2）在二叉搜索树的叶结点中确定X ∈（X i ，X i+1），其概率为a i 。在表示S 的二叉搜索树T 中，设存储元素X i 的结点深度为C i ；叶结点（X i ，X i+1）的结点深度为d i ，则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]=｛X i ，X i+1，···，X j ｝最优值为m[i][j]，W[i][j]= a i-1+b i +···+b j +a j ，则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj
2015年算法分析与设计期末考试试卷B卷
西南交通大学2015 — 2016学年第(一)学期考试试卷 课程代码 3244152课程名称 算法分析与设计 考试时间 120分钟 阅卷教师签字： __________________________________ 填空题(每空1分，共15分) 1、 程序是 (1) 用某种程序设计语言的具体实现。 2、 矩阵连乘问题的算法可由 (2) 设计实现。 3、 从分治法的一般设计模式可以看出，用它设计出的程序一般是 (3) 4、 大整数乘积算法是用 (4) 来设计的。 5、 贪心算法总是做出在当前看来 (5) 的选择。也就是说贪心算法并不从整体最优 考虑，它所做出的选择只是在某种意义上的 (6) o 6、 回溯法是一种既带有 (7) 又带有 (8) 的搜索算法。 7、 平衡二叉树对于查找算法而言是一种变治策略，属于变治思想中的 (9) 类型 8、 在忽略常数因子的情况下，0、门和0三个符号中， (10) 提供了算法运行时 间的一个上界。 9、 算法的“确定性”指的是组成算法的每条 (11) 是清晰的，无歧义的。 10、 冋题的(12) 是该冋题可用动态规划算法或贪心算法求解的关键特征。 11、 算法就是一组有穷 (13)，它们规定了解决某一特定类型问题的 (14) o 12、 变治思想有三种主要的类型：实例化简，改变表现， (15) o 、 ___________________________________________________________________________________ L 线订装封密 线订装封密 、 __________________ 二 线订装封密 级班 选择题(每题2分，共20 分)
建筑设计基础期末考试复习题及参考答案-专升本
《建筑设计基础》复习题 一、选择题 1、建筑物之间的距离主要依据（）的要求确定。 A.防火安全 B.地区降雨量 C.地区日照条件 D.水文地质条件 2、建筑立面的虚实对比，通常是由（）来体现的。 A.建筑色彩的统一变化 B.门窗的排列组合与墙面的对比 C.装饰材料的颜色变化 D.形体凹凸的光影变化 3、一般走道均为双向人流，一股人流宽（）mm 左右。 A.550 B.600 C.700 D.500 4、套间式组合一般适用于（）建筑类型。 A.住宅、学校 B.火车站、体育馆 C.展览馆、陈列馆 D.幼儿园、住宅 5、民用建筑物的走道宜有直接采光，解决采光最有效的方式是（）。 A.利用走道两侧门上亮采光 B. 利用楼梯间、门厅、过厅采光 及走廊端部开窗采光 C.走道两侧墙上开高窗采光 D. 用灯具照明 6、大厅式组合一般适用于（）建筑类型。 A. 医院、办公楼、中小学 B. 剧院、电影院、体育馆 C. 火车站、浴室、百货商店 D. 医院、展览馆、图书馆 7、建筑立面的重点处理常采用（）手法。 A. 韵律 B. 均衡 C. 统一 D. 对比 8、对于大多数建筑物来说，（）经常起着主导设计的作用。 A.建筑功能 B.建筑技术 C.建筑形象 D.经济 9、民用建筑中，窗子面积的大小主要取决于（）的要求。 A.室内采光 B.室内通风 C.室内保温 D.立面装饰 10、大厅式组合一般适用于（）建筑类型。 A医院、中小学、办公楼 B.火车站、浴室、百货商店C.剧院、电影院、体育馆 二、名词解释 1、开间 2、大厅式组合 3、高层建筑
4、耐火极限 三、简答题 1、简述建筑单体测绘的内容。 2、建筑平面组合主要应满足哪些方面的要求？ 3、在民用建筑设计中，确定矩形平面房间的开间和进深尺寸应考虑哪些要求？ 4、确定民用建筑中门的位置应考虑哪些问题？ 四、论述题 1、在进行平面组合时，如何处理建筑各部分之间的主次关系、内外关系以及联系与分隔？ 2、如何按功能要求进行建筑平面组合？
算法设计与分析复习题目及答案
一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ）
算法设计与分析考试题及答案
1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。
算法分析与设计试卷
《算法分析与设计》试卷(A) （时间90分钟满分100分） 一、填空题（30分,每题2分）。 1．最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法2．在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( B ). A.回溯法 B.分支限界法 C.回溯法和分支限界法 D.回溯法求解子集树问题 3．实现最大子段和利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法4．.广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法5．衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 6．Strassen矩阵乘法是利用（ A）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 7. 使用分治法求解不需要满足的条件是（ A ）。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并 D 原问题和子问题使用相同的方法解 8．用动态规划算法解决最大字段和问题，其时间复杂性为( B ). A.logn B.n C.n2 D.nlogn 9.解决活动安排问题，最好用（ B ）算法 A.分治 B.贪心 C.动态规划 D.穷举 10.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ） A．递归函数 B.剪枝函数C。随机数函数 D.搜索函数11. 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( C )之外都是最常见的方式. A.队列式分支限界法 B.优先队列式分支限界法 C.栈式分支限界法 D.FIFO分支限界法 12. .回溯算法和分支限界法的问题的解空间树不会是( D ). A.有序树 B.子集树 C.排列树 D.无序树 13.优先队列式分支限界法选取扩展结点的原则是（ C ）。 A、先进先出 B、后进先出 C、结点的优先级 D、随机14．下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解15．回溯法在解空间树T上的搜索方式是( A ). A.深度优先 B.广度优先 C.最小耗费优先 D.活结点优先 二、填空题（20分,每空1分）。 1.算法由若干条指令组成的又穷序列，且满足输入、输出、 确定性和有限性四个特性。 2.分支限界法的两种搜索方式有队列式(FIFO)分支限界法、优先队列式分支限界法，用一个队列来存储结点的表叫活节点表。
(完整版)算法设计与分析期末考试卷及答案a
一．填空题(每空 2 分，共30分) 1．算法的时间复杂性指算法中的执行次数。 2．在忽略常数因子的情况下，O、和三个符号中，提供了算法运行时间的一个上界。 3．设D n表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间, p(I)表示输入 I 出现的概率，则算法的平均情况下时间复杂性A(n)= 。 4．分治算法的时间复杂性常常满足如下形式的递归方程： f (n) d , n n0 f(n) af(n/c) g(n) , n n0 其中，g(n)表示。 5. 分治算法的基本步骤包括。6．回溯算法的基本思想是。 7．动态规划和分治法在分解子问题方面的不同点是。 8．贪心算法中每次做出的贪心选择都是最优选择。 9．PQ 式的分支限界法中，对于活结点表中的结点，其下界函数值越小，优先级 10．选择排序、插入排序和归并排序算法中，算法是分治算法。 11．随机算法的一个基本特征是对于同一组输入，不同的运行可能得到的结果。12. 对于下面的确定性快速排序算法，只要在步骤3 前加入随机 化步骤，就可得到一个随机化快速排序算法，该随机化步骤的功能是。 算法QUICKSORT 输入：n 个元素的数组A[1..n] 。 输出：按非降序排列的数组 A 中的元素
1. quicksort(1, n) end QUICKSORT ＿ ＿ 过程 quicksort(A, low, high) ＿ ＿ // 对 A[low..high] 中的元素按非降序排序。 ＿ 号 学 2. if low 内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 2010-2011学年第一学期《建筑设计基础》期末试卷 班级 _______________ 学号_____________ 姓名 ____________ 成绩 一、选择题（本大题共25小题） 1. 公共建筑空间一般由三个主要部分组成，下列哪项不在其中（）。 A. 使用空间B .辅助空间C .过渡空间D .交通空间 2. 下列（）项有误。 A. 10层以上的住宅为高层B .住宅超过100米时为超高层 C.公共建筑超过24米时为高层D .公共建筑超过100米时为超高层 3 .在居住建筑中，使用最广泛的木门是（）。 A.推拉门 B .弹簧门 C .转门 D .平开门 4 .供残疾人使用的坡道设计规定，下列哪一项是错误的（）。 A.宽度不应小于0.9m B .坡道两侧应设扶手 C.坡度不应大于1/8 D .休息平台的水平长度不应小于 1.5m 5.户内通往起居室、卧室的过道净宽不应小于（）。 A. 0.9 B. 1.0 C 1.2 D 1.1 6 .“尺度”的含义是（） A .要素的真实尺寸的大小 B .人感觉上要素的尺寸的大小 C .要素给人感觉上的大小印象与其真实大小的关系 D .要素给人感觉上各部分尺寸大小的关系 7 .可持续能源的基本特征是（） A .不间断、高效、无污染 B .可重复利用、经济、寿命长 C .清洁、安全、永久性 D .清洁、廉价、稳定性 8 .纪念性建筑和特别重要的建筑的使用年限（） A . 20 B . 50 C . 100 D . 200 9 .以下柱式中哪一个不是古希腊时期创造的（） A .塔斯干式 B .多立克式 C .科林斯式 D .爱奥尼式 10 .车流量较大的基地，其连接城市道路的出入口位置距大中城市主干道交叉口的距离自道路红线交点量起不应小于（） A. 60m B . 70m C . 80m D . 90m 11 .消防车道的宽度B和道路上空遇有障碍物时的净高H分别应符合（） A. B>3.5 H>3.5 B . B>4 H>4 C . B>3.5 H>4 D . B>4 H>3.5 12 .以下哪些属于低层住宅的有点（） a, 适应性强b,结构简单c,利于通风采光d,节约投资 A . a,b,c B . b,c C . a,b,d D . a,c,d 13 .下述何为点式住宅的突出优点（） 湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:1２０分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14 算法分析与设计复习题及答案一、单选题 1．D 2．B 3．C 4．D 5．D 6．D 7．C 8．D 9．B 10．C 11．D 12．B 13．D 14．C 15．C 16．D 17．D 18．D 19．D 20．C 1．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 2．根据执行算法的计算机指令体系结构，算法可以分为（）。 Ａ精确算法与近似算法Ｂ串行算法语并行算法 Ｃ稳定算法与不稳定算法Ｄ３２位算法与６４位算法 3．具有１0个节点的完全二叉树的高度是（）。 Ａ６Ｂ５Ｃ3Ｄ 2 4．下列函数关系随着输入量增大增加最快的是（）。 Ａlog2n B n2 C 2n D n! 5．下列程序段的S执行的次数为( )。 for i ←0 to n-1 do for j ←0 to i-1 do s //某种基本操作 A.n2 B n2/2 C n*(n+1) D n(n+1)/2 6．Fibonacci数列的第十项为( )。 A 3 B 13 C 21 D 34 7．4个盘子的汉诺塔，至少要执行移动操作的次数为( )。 A 11次 B 13次 C 15次 D 17次 8．下列序列不是堆的是（）。 A 99，85，98，77，80，60，82，40，22，10，66 B 99，98，85，82，80，77，66，60，40，22，10 C 10，22，40，60，66，77，80，82，85，98，99 D 99，85，40，77，80，60，66，98，82，10，22 9．Strassen矩阵乘法的算法复杂度为（）。 ＡΘ(n3)ＢΘ(n2.807) ＣΘ(n2) ＤΘ(n) 10．集合A的幂集是（）。 A．A中所有元素的集合 B. A的子集合 C． A 的所有子集合的集合 D. 空集 11．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 12．从排序过程是否完全在内存中显示，排序问题可以分为（）。 Ａ稳定排序与不稳定排序Ｂ内排序与外排序 Ｃ直接排序与间接排序Ｄ主排序与辅助排序 13．下列（）不是衡量算法的标准。 Ａ时间效率Ｂ空间效率 Ｃ问题难度Ｄ适应能力 14．对于根树，出度为零的节点为（）。 Ａ０节点Ｂ根节点Ｃ叶节点Ｄ分支节点 15．对完全二叉树自顶向下，从左向右给节点编号，节点编号为１0的父节点编号为（）。 Ａ０Ｂ２Ｃ４Ｄ６ 16．下列程序段的算法时间的复杂度为（）。 for i ←0 to n do for j ←0 to m do Program算法设计与分析基础中文版答案 习题 5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. Hint: 根据除法的定义不难证明: 如果d整除u和v, 那么d一定能整除u±v; 如果d整除u,那么d也能够整除u的任何整数倍ku. 对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。 数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r) 6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint: 对于任何形如0<=m 设sqrt(x)是求平方根的函数) 算法Quadratic(a,b,c) 描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述 解答： a.将十进制整数转换为二进制整数的算法 输入：一个正整数n 输出：正整数n相应的二进制数 第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n 第二步：如果n=0，则到第三步，否则重复第一步 第三步：将Ki按照i从高到低的顺序输出 b.伪代码 算法 DectoBin(n) .n]中 i=1 while n!=0 do { Bin[i]=n%2; n=(int)n/2; i++; } while i!=0 do{ print Bin[i]; i--; } 9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进. 算法 MinDistance(A[0..n-1]) 《算法分析与设计》期末试题及参考答案 一、简要回答下列问题： 1.算法重要特性是什么？ 1.确定性、可行性、输入、输出、有穷性 2. 2.算法分析的目的是什么？ 2.分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。 3. 3.算法的时间复杂性与问题的什么因素相关？ 3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。 4.算法的渐进时间复杂性的含义？ 4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。 5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？ 5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的 算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度： W(n) = max{ T(n，I) } , I∈Dn 平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和： A(n) =∑P(I)T(n，I) I∈Dn 6.简述二分检索（折半查找）算法的基本过程。 6. 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较， 如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2] 一、选择题 1．一个.java文件中可以有（）个public类。 A．一个B．两个C．多个D．零个 2．一个算法应该是（） A．程序B．问题求解步骤的描述 C．要满足五个基本特性D．A和C 3．用计算机无法解决“打印所有素数”的问题，其原因是解决该问题的算法违背了算法特征中的（）A．唯一性B．有穷性C．有0个或多个输入D．有输出 4．某校有6位学生参加学生会主席竞选，得票数依次为130，20，98，15，67，3。若采用冒泡排序算法对其进行排序，则完成第二遍时的结果是（） A．3，15，130，20，98，67B．3，15，20，130，98，67 C．3，15，20，67，130，98 D．3，15，20，67，98，130 5．下列关于算法的描述，正确的是（） A．一个算法的执行步骤可以是无限的B．一个完整的算法必须有输出 C．算法只能用流程图表示D．一个完整的算法至少有一个输入 6．Java Application源程序的主类是指包含有（）方法的类。 A、main方法 B、toString方法 C、init方法 D、actionPerfromed方法 7．找出满足各位数字之和等于5的所有三位数可采用的算法思路是（） A．分治法B．减治法C．蛮力法D．变治法 8．在编写Java Application程序时，若需要使用到标准输入输出语句，必须在程序的开头写上( )语句。 A、import java.awt.* ; B、import java.applet.Applet ; C、import java.io.* ; D、import java.awt.Graphics ; 9．计算某球队平均年龄的部分算法流程图如图所示，其中：c用来记录已输入球员的人数，sum用来计算有效数据之和，d用来存储从键盘输入的球员年龄值，输入0时表示输入结束。 1、用计算机求解问题的步骤：1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性： 确定性： 可行性： 输入： 输出： 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解； 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有 关。 复杂性的渐近性态 设T(N)是算法A的复杂性函数，使得当N→∞时有： (T(N)-T’(N))/T(N) → 0 那么，我们就说T’(N)是T(N)当N→∞时的渐近性态，或叫T’(N)为算法A当N→∞的渐近复杂性而与T(N)相区别。 P = NP 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 分而治之法 1、基本思想 将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以 便各个击破，分而治之。 分治法所能解决的问题一般具有以下几个特征： （1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。 3、分治法的基本步骤 （1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题； （2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题； （3）合并：将各个子问题的解合并为原问题的解。 递归： 直接或间接的调用自身的算法，叫做递归算法。 1·期盘覆盖 用分治策略，可以设计解棋盘问题的一个简捷的算法。 当k>0时，将2^k * 2^k棋盘分割为4个2^(k-1) * 2^(k-1)子棋盘 特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，我们可以用一个L型骨牌覆盖这3个较小的棋盘的汇合处，如下图所示，这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格，从而将原问题化为4个较小规模的棋盘覆盖问题。递归的使用这种分割，直至棋盘简化为1x1棋盘。 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性: 确定性,有穷性,可行性,0个或多个输入,一个或多个输出。 2.算法的复杂性有时间复杂性和空间复杂性之分，衡量一个算法好坏的标准是时间复杂度高低。 3.某一问题可用动态规划算法求解的显著特征是该问题具有最优子结构性质。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD｝。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解。 6.动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法。 8.0-1背包问题的回溯算法所需的计算时间为o(n*2n) ,用动态规划算法所需的计算时间为o(min{nc,2n})。 9.动态规划算法的两个基本要素是最优子结构和重叠子问题。 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质； ②构造最优值的递归关系表达式； ③最优值的算法描述； ④构造最优解； 2.流水作业调度问题的johnson算法的思想。 ②N1={i|ai 算法分析与设计习题集 基础篇 1、算法有哪些特点？它有哪些特征？它和程序的主要区别是什么？ 2、算法的时间复杂度指的是什么？如何表示？ 3、算法的空间复杂度指的是什么？如何表示？ 4、设某一函数定义如下： 编写一个递归函数计算给定x的M（x）的值。 本函数是一个递归函数，其递归出口是： M（x）= x-10x>100 递归体是： M（M（x+11））x ≤100 实现本题功能的递归函数如下： intm ( intx ) { int y; if ( x>100 )return(x-10 ); else { y =m(x+11) ; return (m (y )); } } 5、已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数删除表中多余的值相 同的元素。 本题的算法思想是：由于顺序表中元素已按元素值非递减有序排列，值相同的元素比为相邻的元素，因此依次比较相邻两个元素，若值相等，则删除其中一个，否则继续向后查找，直到最后一个元素。实现本题功能的函数如下： voiddel ( seqlist*a ) { inti=0, j; while ( i ①计算结点总数 int CountNode(BinTree *root) { int num1,num2; if(root==Null) return(0); else if(root->lchild==Null&&rooot->rchild==Null) return(1); else { num1=CountNode(root->lchild); num2=CountNode(root->rchild); return(num1+num2+1); } } ②计算叶子总数 int CountLeafs(BinTree *root) { int num1,num2; if(root==Null) return(0); else if(root->lchild==Null&&root->rchild==Null) return(1); else { num1=CountLeafs(root->lchild); num2=CountLeafs(root->rchild); return(num1+num2); } } 分治术 7、有金币15枚，已知其中有一枚是假的，而且它的重量比真币轻。要求用一个天平将假 的金币找出来，试设计一种算法（方案），使在最坏情况下用天平的次数最少。 8、利用分治策略，在n个不同元素中找出第k个最小元素。 9、设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表。 （1）每个选手必须与其它n-1选手各赛一次； （2）每个选手一天只能赛一次。 10、已知序列{503，87，512，61，908，170，897，275，652，462}，写一个自底向上的 归并分类算法对该序列作升序排序，写出算法中每一次归并执行的结果。 void Merge(ElemType *r，ElemType *rf，int u，int v，int t) { f or(i=u，j=v，k=u；i算法设计与分析试卷(2010)
建筑设计基础试题(附有答案)
算法设计与分析试卷及答案
算法分析与设计复习题及答案
算法设计与分析基础课后习题答案
《算法分析与设计》期末试题及参考答案
《算法分析与设计》期末复习题
算法设计与分析期末试题-考试版(汇编)
算法设计与分析试题与答案
算法分析与设计习题集
相关文档
- 算法分析与设计部分含计算的复习题及参考答案
- 算法设计与分析王算法设计基础精品PPT课件
- 算法分析与设计基础答案11章
- 程序设计与算法分析
- 算法设计与分析基础课后习题答案(中文版)54551
- 算法分析与设计基础知识习题
- 最新算法设计技巧与分析答案
- 算法设计与分析基础课后习题答案
- 算法设计与分析基础习题参考答案
- 最新算法分析与设计习题集答案
- 算法分析与设计基础第三版答案第一章
- 算法设计与分析复习题目及答案
- 算法分析与设计习题集
- 2020智慧树知到《算法分析与设计》章节测试完整答案
- 算法与设计算法分析基础-整体框架
- 算法与设计算法分析基础-整体框架
- 算法设计与分析基础课后习题答案solu3
- 算法分析和设计基本知识点复习共30页文档
- 算法分析与设计基本知识点复习
- 《算法分析与设计》期末考试复习题纲(完整版)