2010山东省C语言版深入
- 格式:pdf
- 大小:100.75 KB
- 文档页数:5
c 2010教程C 2010是一种编程语言,广泛应用于软件开发和计算机编程领域。
它是一种面向对象的高级语言,是C语言的延伸,拥有更强大的功能和更高的效率。
在本文中,将介绍C 2010的基本概念、语法和用法。
C 2010作为一种面向对象的编程语言,具有许多优点。
首先,它具有高效的执行速度和卓越的性能。
这使得C 2010非常适合开发底层系统和需要高度优化的应用程序。
其次,C 2010拥有丰富的标准库,包括输入输出函数、字符串处理函数、数学函数等,方便开发人员快速实现各种功能。
此外,C 2010还支持多线程编程,使得程序能够更好地利用多核处理器的能力。
接下来,我们将介绍C 2010的基本语法。
C 2010的程序由一系列语句组成,每个语句以分号结尾。
变量是C 2010程序中的基本元素,用于存储数据。
要声明一个变量,需要指定其类型和名称。
C 2010支持包括整型、浮点型、字符型等多种类型的变量。
下面是一个C 2010程序的示例:#include <stdio.h>int main(){int num1 = 5;int num2 = 10;int sum = num1 + num2;printf("The sum of %d and %d is %d\n", num1, num2, sum);return 0;}在上面的示例中,我们定义了三个整型变量num1、num2和sum,并通过“+”运算符计算它们的和。
然后,使用printf函数将计算结果输出到屏幕上。
除了基本的语法规则外,C 2010还提供了许多控制结构和语句,用于实现条件判断、循环和函数调用等。
例如,if语句用于根据条件执行不同的代码块,while和for循环语句用于重复执行一段代码。
C 2010中还提供了丰富的函数库,用于实现各种功能。
例如,stdio.h库中包含了输入输出函数,math.h库中包含了数学函数等。
总之,C 2010是一种功能强大的编程语言,广泛应用于软件开发和计算机编程领域。
根据《山东省教育厅关于做好2010年普通高等教育学分互认和专科升本科工作的通知》(鲁教高字〔2009〕24号)和《关于做好2010年普通高等教育学分互认和专升本考试录取工作的通知》(鲁教高处函(2009)50号)文件(以下简称《通知》)精神,现将山东省2010年普通高等教育专升本考试工作有关事项通知如下:一、招生类别、专业和计划招生类别分为:普通专升本(含师范和高职高专)。
按照《山东省教育厅关于下达2010年普通专升本招生计划的通知》(鲁教计字〔2009〕7号),2010年山东省普通高等教育专升本招生学校、招生专业和计划见附件1,各专业考试科目见附件2。
二、报名专科(高职)生所在学校为生源学校,承担2010年专升本考试任务的学校为主考学校。
(一)报名时间普通专升本实行统一时间报名,具体时间及方式如下。
(二)报名范围及方法我省普通本科院校和专科学校(含普通专科学校、高等职业学院和成人高等学校)中的应届普通专科(高职)毕业生(含在校期间已参加过学分互认选拔但未能进入本科段学习的应届普通专科毕业生)。
此类考生在自己的生源学校报名。
具有我省辖区户籍的普通高等教育专科(高职)往届毕业生(不含成人、自学考试、网络教育)和经我省教育招生考试院录取,目前在其他省、市、自治区高校学习的2010年普通高等教育专科(高职)应届毕业生。
此类考生统一到济南大学报名,报名方式及办法见济南大学招生信息网站公布的《2010年山东省普通高等教育专升本考试报名办法》。
(三)填报志愿报名参加普通专升本考试的学生须填写《2010年山东省普通高等教育专升本考试考生报名表》(见附件3)。
填报志愿时,如果同一专业的招生学校有2所以上,考生可填报第一志愿1个,第二志愿不超过3个(平行志愿),并在“是否服从调剂录取”栏中填写“是”或“否”,若不填写,视为不服从调剂。
允许非师范类毕业生报考师范类专业,允许师范类毕业生报考非师范类专业,考生报考专业可与毕业专业不同,但每个考生只能报考师范类或非师范类中的一个专业。
2010年度山东省高等学校省级精品课程名单
2010年度山东省高等学校省级精品课程名单
2010年度山东省高等学校省级精品课程名单
2010年度山东省高等学校省级精品课程名单
2010年度山东省高等学校省级精品课程名单
2010年度山东省高等学校省级精品课程名单
2010年度山东省高等学校省级精品课程名单
2010年度山东省高等学校省级精品课程名单
2010年度山东省高等学校省级精品课程名单
2010年度山东省高等学校省级精品课程名单
2010年度筹备建设的山东省高等学校省级精品。
Problem A Phone NumberWe know that if a phone number A is another phone number B’s prefix, B is not able to be called. For an example, A is 123 while B is 12345, after pressing 123, we call A, and not able to call B.Given N phone numbers, your task is to find whether there exits two numbers A and B that A is B’s prefix.InputThe input consists of several test cases.The first line of input in each test case contains one integer N(0<N<1001), represent the number of phone numbers.The next line contains N integers, describing the phone numbers.The last case is followed by a line containing one zero.OutputFor each test case, if there exits a phone number that cannot be called, print “NO”, otherwise print “YES” instead.Sample Input Output for the Sample Input2012 012345 212 012345 0 NO YESProblem B BalloonsBoth Saya and Kudo like balloons. One day, they heard that in the central park, there will be thousands of people fly balloons to pattern a big image.They were very interested about this event, and also curious about the image.Since there are too many balloons, it is very hard for them to compute anything they need. Can you help them?Y ou can assume that the image is an N*N matrix, while each element can be either balloons or blank.Suppose element A and element B are both balloons. They are connected if: i) They are adjacent;ii) There is a list of element C 1, C 2, … , C n , while A and C 1 are connected, C 1 and C 2 are connected …C n and B are connected.And a connected block means that every pair of elements in the block is connected, while any element in the block is not connected with any element out of the block.To Saya, element A (,)xa ya and B (,)xb yb is adjacent if ||||1xa xb ya yb -+-≤ But to Kudo, element A (,)xa ya and element B (,)xb yb is adjacent if ||1xa xb -≤ and||1ya yb -≤They want to know that there’s how many connected blocks with there own definition of adjacent?InputThe input consists of several test cases.The first line of input in each test case contains one integer N (0<N ≤100), which represents the size of the matrix.Each of the next N lines contains a string whose length is N , represents the elements of the matrix. The string only consists of 0 and 1, while 0 represents a block and 1represents balloons.The last case is followed by a line containing one zero.OutputFor each case, print the case number (1, 2 …) and the connected block’s numbers with Say a and Kudo’s definition. Y our output format should imitate the sample output. Print a blank line after each test case.Sample InputOutput for the Sample Input5 11001 00100 11111 11010Case 1: 3 210010 0Problem C ClockwiseSaya have a long necklace with N beads, and she signs the beads from 1 to N. Then she fixes them to the wall to show N-1 vectors – vector i starts from bead i and end up with bead i+1.One day, Kudo comes to Saya’s home, and she sees the beads on the wall. Kudo says it is not beautiful, and let Saya make it better.She says: “I think it will be better if it is clockwise rotation. It means that to any vector i (i<N-1), it will have the same direction with vector i+1 after clockwise rotate T degrees, while 0≤T<180.”It is hard fo r Saya to reset the beads’ places, so she can only remove some beads. To saving the beads, although she agrees with Kudo’s suggestion, she thinks counterclockwise rotation is also acceptable. A counterclockwise rotation means to any vector i (i<N-1), it will have the same direction with vector i+1 after counterclockwise rotate T degrees, while 0<T≤180.”Saya starts to compute at least how many beads she should remove to make a clockwise rotation or a counterclockwise rotation.Since the necklace is very-very long, can you help her to solve this problem?InputThe input consists of several test cases.The first line of input in each test case contains one integer N (2<N≤300), which represents the number of beads.Each of the next N lines contains two integer x and y, represents the coordinate of the beads. Y ou can assume that 0<x, y<10000.The last case is followed by a line containing one zero.OutputFor each case, print your answer with the following format:If it is clockwise rotation without removing an y beads, please print “C; otherwise if it is counterclockwise rotation without removing any beads, print “CC” instead; otherwise, suppose remove at least x beads to make a clockwise rotation and remove at least y beads to make a counterclockwise rotation. If x≤y, print “Remove x bead(s), C”, otherwise print “Remove x bead(s), CC” instead.Y our output format should imitate the sample output. Print a blank line after each test case. Sample Input Output for the Sample Input31 12 23 331 12 2 CCCRemove 1 bead(s), C1 141 12 23 3 2 2Problem D ShoppingSaya and Kudo go shopping together.Y ou can assume the street as a straight line, while the shops are some points on the line.They park their car at the leftmost shop, visit all the shops from left to right, and go back to their car.Y our task is to calculate the length of their route.InputThe input consists of several test cases.The first line of input in each test case contains one integer N (0<N<100001), represents the number of shops.The next line contains N integers, describing the situation of the shops. Y ou can assume that the situations of the shops are non-negative integer and smaller than 2^30.The last case is followed by a line containing one zero.OutputFor each test case, print the length of their shopping route.Sample Input Output for the Sample Input424 13 89 3767 30 41 14 39 42 0152 70Explanation for the first sample: They park their car at shop 13; go to shop 24, 37 and 89 and finally return to shop 13. The total length is (24-13) + (37-24) + (89-37) + (89-13) = 152Problem E EmergencyKudo’s real name is not Kudo. Her name is Kudryavka Anatolyevna Strugatskia, and Kudo is only her nickname.Now, she is facing an emergency in her hometown:Her mother is developing a new kind of spacecraft. This plan costs enormous energy but finally failed. What’s more, because of the failed project, the government doesn’t have enough resource take measure to the rising sea levels caused by global warming, lead to an island flooded by the sea.Dissatisfied with her mother’s spacecraft and the government, civil war has broken out. The foe wants to arrest the spacecraft project’s participants and the “Chief criminal” –Kudo’s mother –Doctor T’s family.At the beginning of the war, all the cities are occupied by the foe. But as time goes by, the cities recaptured one by one.To prevent from the foe’s arrest and boost morale, Kudo and some other people have to distract from a city to another. Although they can use some other means to transport, the most convenient way is using the inter-city roads. Assuming the city as a node and an inter-city road as an edge, you can treat the map as a weighted directed multigraph. An inter-city road is available if both its endpoint is recaptured.Here comes the problem.Given the traffic map, and the recaptured situation, can you tell Kudo what’s the shortest path from one city to another only passing the recaptured cities?InputThe input consists of several test cases.The first line of input in each test case contains three integers N(0<N≤300), M (0<M≤100000) and Q (0<Q≤100000), which represents the number of cities, the numbers of inter-city roads and the number of operations.Each of the next M lines contains three integer x, y and z, represents there is an inter-city road starts from x, end up with y and the length is z. Y ou can assume that 0<z≤10000.Each of the next Q lines contains the operations with the following format:a)0 x– means city x has just been recaptured.b) 1 x y– means asking the shortest path from x to y only passing the recaptured cities.The last case is followed by a line containing three zeros.OutputFor each case, print the case number (1, 2 …) first.For each operation 0, if city x is already recaptured (that is,the same 0 x operation appears again), print “City x is already recaptured.”For each operation 1, if city x or y is not recaptured yet, print “City x or y is not available.” otherwise if Kudo can go from city x to city y only passing the recaptured cities, print the shortest path’s length; otherwise print “No such path.”Y our output format should imitate the sample output. Print a blank line after each test case.Sample Input Output for the Sample Input3 3 60 1 11 2 10 2 31 02 0 00 21 02 1 2 0 0 20 0 0 Case 1:City 0 or 2 is not available. 3No such path.City 2 is already recaptured.Problem F Fairy taleIt is said that in a school’s underground, there is a huge treasure which can meet any desire of the owner.The Spy Union (SU) is very interest in this legend. After much investigation, SU finally get the answer and let the youngest spy sneak into the school. That’s why Saya is now here.Today, Saya found the entrance eventually.She enters the entrance, and found her in a fairy-tale world.“Welcome!” says a fairy, “I am Ivan. My responsibility is to protect the treasure, and give it to the one who have the ability to own it.”Then Ivan gives Saya three problems.With your help, Saya finished the first and the second problem (Problem H and I). Here comes the third. If Saya can solve this problem, the treasure belongs to her.There is a big maze protecting the treasure. Y ou can assume the maze as an N*N matrix while each element in the matrix might be N (North), S (South), W (West) or E (East). At first, Saya is at the element (1, 1) – the north-west corner, and the treasure is at (N, N) – the south-east corner.The designer have enchant to this matrix, so that the treasure might move from time to time respecting the following rules:Suppose the treasure is in an element which marked with E. The treasure might eastward move a cell after a unit time. It is similar to S, W and N.After a unit time, all the mark will change: E to W, W to S, S to N, and N to E. In another word, suppose an element which marked with E at time 0. At time 1, it might change to W, change to S at time 2, change to N at time 3, change to E at time 4, and so on.Saya doesn't know the initial status of the marks. She is affected by this rule, but she decides to do something more.Ivan gave Saya a special prop which called Riki. With Riki’s help, she can get the position of the treasure.In each unit time, Saya will do all of the following three things:Firstly, she will check the treasure’s position with Riki.Secondly, she will move follow the designer’s magic the same with the treasure.(If no element exists in the direction of movement,the movement will be cancelled.)Thirdly, Saya can either move to one direction (N, S, E, and W) a cell or stay there. Saya prefers to be closer with the treasure; if there are many ways with the same geometrical distance, Saya prefers to stay there than move, prefer E than W, W than N, and N than S. Here we should use the position checked at the first step.Y ou are given the size of the matrix and all the marks of the elements at time 0. Y our task is to simulate Saya and the treasure’s movement, and then tell Saya the result.InputThe input consists of several test cases.The first line of input in each test case contains one integer N (0<N≤30), which represents the size of the matrix.Each of the next N lines contains a string whose length is N, represents the elements of the matrix. The string only consists of N, E, W and S.The last case is followed by a line containing one zero.OutputF or each case, print the case number (1, 2 …) and the result of Saya’s explore.If Saya can get the treasure at step x (x≤100)(that means at the begainning of time x, Saya and the treasure stay in the same cell), print “Get the treasure! At step x.”.If after simulating x(x≤100) steps, you found out that Saya can't get the treasure, print “Impossible. At step x.”If you have simulated 100 steps but don’t know whether Saya can get the treasure, print “Not sure.”Y our output format should imitate the sample output. Print a blank line after each test case. Sample Input Output for the Sample Input5 EWSSE NNENN EENNE SWSEW NSNSW0 Case 1:Get the treasure! At step 12.Q&AQ: How can I know it’s impossible for Saya to get the treasure?A: Suppose at time 5, Saya at (1, 1) while the treasure at (2, 2); at time 13, Saya at (1, 1) while the treasure at (2, 2) again. Since both Saya and the treasure go to the same place and have the same direction again, it is a loop, and they will just repeats the moves forever. So at time 13, we can judge it is impossible.Problem G Greatest NumberSaya likes math, because she think math can make her cleverer.One day, Kudo invited a very simple game:Given N integers, then the players choose no more than four integers from them (can be repeated) and add them together. Finally, the one whose sum is the largest wins the game. It seems very simple, but there is one more condition: the sum shouldn’t larger than a number M.Saya is very interest in this game. She says that since the number of integers is finite, we can enumerate all the selecting and find the largest sum. Saya calls the largest sum Greatest Number (GN). After reflecting for a while, Saya declares that she found the GN and shows her answer.Kudo wants to know whe ther Saya’s answer is the best, so she comes to you for help.Can you help her to compute the GN?InputThe input consists of several test cases.The first line of input in each test case contains two integers N (0<N≤1000) and M(0<M≤1000000000), which represent the number of integers and the upper bound.Each of the next N lines contains the integers. (Not larger than 1000000000)The last case is followed by a line containing two zeros.OutputFor each case, print the case number (1, 2 …) and the GN.Y our output format should imitate the sample output. Print a blank line after each test case.Sample Input Output for the Sample Input2 10Case 1: 810020 0Problem H Hello World!We know that Ivan gives Saya three problems to solve (Problem F), and this is the first problem.“We need a programmer to help us for some projects. If you show us that you or one of your friends is able to program, you can pass the first hurdle.I will give you a problem to solve. Since this is the first hurdle, it is very simple.”We all know that the simplest program is the “Hello World!” program. This is a problem just as simple as the “Hello World!”In a large matrix, there are some elements has been marked. For every marked element, return a marked element whose row and column are larger than the showed element’s row and column respectively. If there are multiple solutions, return the element whose row is the smallest; and if there are still multiple solutions, return the element whose column is the smallest. If there is no solution, return -1 -1.Saya is not a programmer, so she comes to you for help.Can you solve this problem for her?InputThe input consists of several test cases.The first line of input in each test case contains one integer N (0<N≤1000), which represents the number of marked element.Each of the next N lines containing two integers r and c, represent the element’s row and column. Y ou can assume that 0<r, c≤300. A marked element can be repeatedly showed.The last case is followed by a line containing one zero.OutputFor each case, print the case number (1, 2 …), and for each element’s row and column, output the result. Y our output format should imitate the sample output. Print a blank line after each test case.Sample Input Output for the Sample Input31 22 3 2 30 Case 1: 2 3-1 -1-1 -1Problem I Ivan comes again!The Fairy Ivan gave Saya three problems to solve (Problem F). After Saya finished the first problem (Problem H), here comes the second.This is the enhanced version of Problem H.There is a large matrix whose row and column are less than or equal to 1000000000. And there are three operations for the matrix:1)add: Mark an element in the matrix. The element wasn’t marked before it is marked.2)remove: Delete an element’s mark. The element was marked before the element’s markis deleted.3)find: Show an element’s row and column, and return a marked element’s row andcolumn, where the marked element’s row and column are larger than the showed element’s row and column respectively. If there are multiple solutions, return the element whose row is the smallest; and if there are still multiple solutions, return the element whose column is the smallest. If there is no solution, return -1.Of course, Saya comes to you for help again.InputThe input consists of several test cases.The first line of input in each test case contains one integer N(0<N≤200000), which represents the number of operations.Each of the next N lines containing an operation, as described above.The last case is followed by a line containing one zero.OutputFor each case, print the case number (1, 2 …) first. Then, for each “find” operation, output the result. Y our output format should imitate the sample output. Print a blank line after each test case.Sample Input Output for the Sample Input4add 2 3 find 1 2 remove 2 3 find 1 20 Case 1: 2 3-1Problem J Jerry MouseKudo and Saya are good friends, and they are always together.But today, since Saya is not here (Where is Saya? Y ou can get the answer at Problem F), Kudo fells very bored. So Kudo starts to watch TV for fun.Now, she is watching the famous cartoon “Tom and Jerry”. Jerry’s home have many entrance, he always enter his home in an entrance and get out from another.Kudo suddenly thought that what will happen if there are many Jerrys?Kudo finds out a paper box and dig many holes in the side of the box. Then, she marks every hole with an integer, representing its owner. Finally, she signs the box “Kudo’s House” as shown in Figure 1.Figure 1 The gray part represents a hole, and the numbers means its owner, i.e. the two gray parts in the lower left corner means the two holes belongs to mouse 2.Kudo think it is very interesting, so she makes a lot of boxes, and sign them “Saya’s House”, “Riki’s House”, “Lin’s House” and so on.Figure 2 The jointed gray parts represent the same hole.At last, she combines them together to make a large box as shown in Figure 2.She defined mouse A and mouse B is the same mouse if and only if:a)mouse A and mouse B are in a same house and A equals to B;b)mouse A and mouse B are in different houses, but they have a hole that combinedtogether, such as mouse 3 in Kudo’s House and mouse 7 in Lin’s House;c)There exits a lists of mouse M1, M2 … Mp, while A and M1 are the same, M1 and M2are the same … Mp and B are the same.But there is a problem: Suppose mouse 3 in Kudo’s House is the same with mouse 7 in Lin’s House, while mouse 7 in Lin’s House is the same with mouse 4 in Kudo’s House. It means that mouse 3 and 4 in Kudo’s H ouse are the same!Kudo is very confused, so she comes to you for help.Given the initial N boxes, can you tell her finally each hole belongs to whom?Here, N always equals to 1, 4, 9, 16, 25, 36, 49, 64, 81 or 100. Kudo always combines the boxes as shown in Figure 3, while n N=.Figure 3 How Kudo combines the boxes.InputThe input consists of several test cases.The first line of input in each test case contains two integers N (0<N≤100) and M (0<M≤1000), which represent the number of boxes and the number of holes in each side of the box. In every side of the N boxes,Y ou can assume that there are always M holes, and the M holes are arranged with equal spacing.Each of the next N lines containing 4M integers representing the holes on the boxes. The first M integers represent the holes on the upside, from left to right; the second M integers represent the holes on the downside, from left to right; the third M integers represent the holes on the leftward, from up to down; the forth M integers represent the holes on the rightward, from up to down. Y ou can assume that the hole number is not greater than M*2.The last case is followed by a line containing two zeros.Output=) represents the For each case, print the case number (1, 2 …) and 4*n*M integers (n Nholes on the upside, downside, leftward and rightward side of the large box, using the same format as the input file.In your answer, the holes signed by the same numbers should belong to the same mouse, while the holes signed by different numbers should belong to different mouse. The number should be an integer, starting from 1. Since there are multiply solutions, please print the one whose firstnumber is the least. If there are still multiply solutions, print the one whose second number is the least, and so on.Y our output format should imitate the sample output. Print a blank line after each test case. Sample Input Output for the Sample Input4 12 2 1 1 2 2 1 1 1 1 2 2 1 1 2 20 0 Case 1:1 2 1 2 3 4 3 4。
1、本题要求建立有序的循环链表。
从头到尾扫描数组A,取出A[i](0<=i<n),然后到链表中去查找值为A[i]的结点,若查找失败,则插入。
LinkedList creat(ElemType A[],int n)//由含n个数据的数组A生成循环链表,要求链表有序并且无值重复结点{LinkedList h;h=(LinkedList)malloc(sizeof(LNode));//申请结点h->next=h; //形成空循环链表for(i=0;i<n;i++){pre=h;p=h->next;while(p!=h && p->data<A[i]){pre=p; p=p->next;} //查找A[i]的插入位置if(p==h || p->data!=A[i]) //重复数据不再输入{s=(LinkedList)malloc(sizeof(LNode));s->data=A[i]; pre->next=s; s->next=p;//将结点s链入链表中}}//forreturn(h);}算法结束2、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树,下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列,生成一棵用二叉链表表示的二叉树并打印出后序遍历序列,请写出程序所缺的语句。
#define MAX 100typedef struct Node{char info; struct Node *llink, *rlink; }TNODE;char pred[MAX],inod[MAX];main(int argc,int **argv){ TNODE *root;if(argc<3) exit 0;strcpy(pred,argv[1]); strcpy(inod,argv[2]);root=restore(pred,inod,strlen(pred));postorder(root);}TNODE *restore(char *ppos,char *ipos,int n){ TNODE *ptr; char *rpos; int k;if(n<=0) return NULL;ptr->info=(1)_______;for((2)_______ ; rpos<ipos+n;rpos++) if(*rpos==*ppos) break;k=(3)_______;ptr->llink=restore(ppos+1, (4)_______,k );ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k);return ptr;}postorder(TNODE*ptr){ if(ptr=NULL) return;postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info); }3、对二叉树的某层上的结点进行运算,采用队列结构按层次遍历最适宜。
int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(k>1) 层上叶子结点个数{if(bt==null || k<1) return(0);BiTree p=bt,Q[]; //Q是队列,元素是二叉树结点指针,容量足够大int front=0,rear=1,leaf=0; //front 和rear是队头和队尾指针, leaf是叶子结点数int last=1,level=1; Q[1]=p; //last是二叉树同层最右结点的指针,level 是二叉树的层数while(front<=rear){p=Q[++front];if(level==k && !p->lchild && !p->rchild) leaf++; //叶子结点if(p->lchild) Q[++rear]=p->lchild; //左子女入队if(p->rchild) Q[++rear]=p->rchild; //右子女入队if(front==last) {level++; //二叉树同层最右结点已处理,层数增1last=rear; } //last移到指向下层最右一元素if(level>k) return (leaf); //层数大于k 后退出运行}//while }//结束LeafKLevel4、连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边,最小生成树是边上权值之和最小的生成树。
故可按权值从大到小对边进行排序,然后从大到小将边删除。
每删除一条当前权值最大的边后,就去测试图是否仍连通,若不再连通,则将该边恢复。
若仍连通,继续向下删;直到剩n-1条边为止。
void SpnTree (AdjList g)//用“破圈法”求解带权连通无向图的一棵最小代价生成树。
{typedef struct {int i,j,w}node; //设顶点信息就是顶点编号,权是整型数node edge[];scanf( "%d%d",&e,&n) ; //输入边数和顶点数。
for (i=1;i<=e;i++) //输入e条边:顶点,权值。
scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);for (i=2;i<=e;i++) //按边上的权值大小,对边进行逆序排序。
{edge[0]=edge[i]; j=i-1;while (edge[j].w<edge[0].w) edge[j+1]=edge[j--];edge[j+1]=edge[0]; }//fork=1; eg=e;while (eg>=n) //破圈,直到边数e=n-1.{if (connect(k)) //删除第k条边若仍连通。
{edge[k].w=0; eg--; }//测试下一条边edge[k],权值置0表示该边被删除k++; //下条边}//while}//算法结束。
connect()是测试图是否连通的函数,可用图的遍历实现,5、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针,p 和q分别为指向该二叉树中任意两个结点的指针,试编写一算法ANCESTOR(ROOT,p,q,r),该算法找到p和q的最近共同祖先结点r。
6、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。
所谓“破圈法”就是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。
请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。
注:圈就是回路。
7、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>}写出G的拓扑排序的结果。
G拓扑排序的结果是:V1、V2、V4、V3、V5、V6、V78、设从键盘输入一整数的序列:a1, a2, a3,…,an,试编写算法实现:用栈结构存储输入的整数,当ai≠-1时,将ai进栈;当ai=-1时,输出栈顶整数并出栈。
算法应对异常情况(入栈满等)给出相应的信息。
设有一个背包可以放入的物品重量为S,现有n件物品,重量分别为W1,W2,...,Wn。
问能否从这n件物品中选择若干件放入背包,使得放入的重量之和正好是S。
设布尔函数Knap(S,n)表示背包问题的解,Wi(i=1,2,...,n)均为正整数,并已顺序存储地在数组W中。
请在下列算法的下划线处填空,使其正确求解背包问题。
Knap(S,n)若S=0则Knap←true否则若(S<0)或(S>0且n<1)则Knap←false否则若Knap(1) , _=true则print(W[n]);Knap ←true否则 Knap←Knap(2) _ , _设有一个顺序栈S,元素s1, s2, s3, s4, s5, s6依次进栈,如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1,则顺序栈的容量至少应为多少?画出具体进栈、出栈过程。
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间。
例如:设str1和str2是分别指向两个单词的头结点,请设计一个尽可能的高效算法,找出两个单词共同后缀的起始位置,分析算法时间复杂度。
将n(n>1)个整数存放到一维数组R中。
设计一个尽可能高效(时间、空间)的算法,将R中保存的序列循环左移p(0<p<n)个位置,即将R中的数据(x0, x1, x2,…, xn-1),变换为(xp, xp+1, … , xn-1 ,x0 , x1,…, xp-1)。
9、请编写一个判别给定二叉树是否为二叉排序树的算法,设二叉树用llink-rlink法存储。
10、#define maxsize 栈空间容量void InOutS(int s[maxsize])//s是元素为整数的栈,本算法进行入栈和退栈操作。
{int top=0; //top为栈顶指针,定义top=0时为栈空。
for(i=1; i<=n; i++) //n个整数序列作处理。
{scanf(“%d”,&x); //从键盘读入整数序列。
if(x!=-1) // 读入的整数不等于-1时入栈。
if(top==maxsize-1){printf(“栈满\n”);exit(0);}else s[++top]=x; //x入栈。
else //读入的整数等于-1时退栈。
{if(top==0){printf(“栈空\n”);exit(0);}else printf(“出栈元素是%d\n”,s[top--]);}}}//算法结11、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>}写出G的拓扑排序的结果。