演算法題軍訓

A. 數據結構演算法設計題

某鏈表中最常用的操作是在最後一個元素之後插入一個元素和刪除最後一個元素,則採用( )存儲方式最節省運算時間. (A)...已知帶頭結點的單鏈表L中的結點是按整數值遞增排列的,試寫一演算法,將值為x 的結點插入到表L中,使得L仍然有序

B. 演算法設計 題求解

1.
外層執行n+1次循環，內姿伏虧層m+1次，所以時間復雜度
O（n*m)=(n+1)*（m+1);
2.
外層執行n次循環，
內層跡神i次循環，i=0,1,2,..,n-1;
n次循環對應的次數：
0，1，2，...,n-1；
等於
（1+2+...+n-1)=n(n-1)/廳耐2;
演算法執行次數如上：
它的時間復雜度
O（n*n);

C. 九月初，王紅同學升入中學老師宣布學校要組織初一年級的學生去外地參加軍訓，要求每位同學准備好一周

設:第一天為X，第培拆二天為X+1，依次類推，直兄中段到第七羨譽天為X+6
X+X+1+ X+2+ X+3+ X+4+ X+5+ X+6=49
7X+21=49
7X=28
X=4

所以是第4天出發

D. 數據結構演算法 試題 急！ 試構造下圖的最小生成樹，要求分步給出構造過程。

圖有如下參數:

邊數=8頂點數=5

頂點頂點邊的權值
v1v26
v1v34
v1v42
v2v35
v2v48
v2v56
v3v45
v4v57

用Kruskal(克魯斯卡爾)演算法,求最小生成樹.

先將所有邊的權值按照從小到大排序:

頂點頂點邊的權值
v1v42
v1v34
v2v35
v3v45
v1v26
v2v56
v4v57
v2v48

然後,每次提取權值最小邊,逐步組成最小生成樹:

(1)取最小邊(v1,v4,2)

v1--v4

(2)取邊(v1,v3,4),不會產生環路.

v1--v4
|
|
v3

(3)取邊(v2,v3,5),不會產生環路.

v1--v4
|
|
v3--v2

(4)如果取邊(v3,v4,5),會產生環路,所以不能取.
如果取邊(v1,v2,6),會產生環路,所以不能取.
取邊(v2,v5,6),不會產生環路.

v1--v4
|
|
v3--v2--v5

這就是最小生成樹,連通了所有頂點,總權值最小.

頂點邊的權值
(v1,v4)2
(v1,v3)4
(v2,v3)5
(v2,v5)6


//C語言測試程序

//最小生成樹Kruskal(克魯斯卡爾)演算法
#include"stdio.h"

#defineMAXEDGE20
#defineMAXVEX20
#defineINF65535

typedefstruct
{
	intarc[MAXVEX][MAXVEX];
	intnumVertexes,numEdges;
}MGraph;

typedefstruct
{
	intbegin;
	intend;
	intweight;
}Edge;//對邊集數組Edge結構的定義

//創建圖
voidCreateMGraph(MGraph*G)
{
	inti,j;

	G->numEdges=8;//邊數
	G->numVertexes=5;//頂點數

	for(i=0;i<G->numVertexes;i++)//初始化圖
	{
		for(j=0;j<G->numVertexes;j++)
		{
			if(i==j)
				G->arc[i][j]=0;
			else
				G->arc[i][j]=G->arc[j][i]=INF;
		}
	}

	G->arc[0][1]=6;
	G->arc[0][2]=4;
	G->arc[0][3]=2;
	G->arc[1][2]=5;
	G->arc[1][3]=8;
	G->arc[1][4]=6;
	G->arc[2][3]=5;
	G->arc[3][4]=7;

	for(i=0;i<G->numVertexes;i++)
	{
		for(j=i;j<G->numVertexes;j++)
		{
			G->arc[j][i]=G->arc[i][j];
		}
	}
}

//交換權值以及頭和尾
voidSwapn(Edge*edges,inti,intj)
{
	inttemp;
	temp=edges[i].begin;
	edges[i].begin=edges[j].begin;
	edges[j].begin=temp;
	temp=edges[i].end;
	edges[i].end=edges[j].end;
	edges[j].end=temp;
	temp=edges[i].weight;
	edges[i].weight=edges[j].weight;
	edges[j].weight=temp;
}

//對權值進行排序(選擇排序法)
voidsort(Edgeedges[],MGraph*G)
{
	inti,j,min;
	for(i=0;i<(G->numEdges-1);i++)
{
min=i;
for(j=i+1;j<G->numEdges;j++)
{
if(edges[min].weight>edges[j].weight)
{
min=j;
}
}
if(i!=min)
{
Swapn(edges,i,min);
}
}

	printf("邊的權值排序之後:
");
	for(i=0;i<G->numEdges;i++)
	{
		printf("(%d,%d)%d
",edges[i].begin,edges[i].end,edges[i].weight);
	}
}

//查找連線頂點的尾部下標
intFind(int*parent,intf)
{
	while(parent[f]>0)
	{
		f=parent[f];
	}
	returnf;
}

//生成最小生成樹
voidMiniSpanTree_Kruskal(MGraphG)
{
	inti,j,n,m;
	intk=0;
	intparent[MAXVEX];//定義一數組用來判斷邊與邊是否形成環路

	Edgeedges[MAXEDGE];//定義邊集數組,edge的結構為begin,end,weight,均為整型

	//用來構建邊集數組並排序
	for(i=0;i<G.numVertexes-1;i++)
	{
		for(j=i+1;j<G.numVertexes;j++)
		{
			if(G.arc[i][j]<INF)
			{
				edges[k].begin=i;
				edges[k].end=j;
				edges[k].weight=G.arc[i][j];
				k++;
			}
		}
	}
	sort(edges,&G);//從小到大排序

	for(i=0;i<G.numVertexes;i++)
{
parent[i]=0;
}

	printf("列印最小生成樹：
");
	for(i=0;i<G.numEdges;i++)	//循環每一條邊
	{
		n=Find(parent,edges[i].begin);
		m=Find(parent,edges[i].end);
		if(n!=m)//假如n與m不等，說明此邊沒有與現有的生成樹形成環路
		{
			parent[n]=m;	//將此邊的結尾頂點放入下標為起點的parent中
							//表示此頂點已經在生成樹集合中
			printf("(%d,%d)%d
",edges[i].begin,edges[i].end,edges[i].weight);
		}
	}
}

intmain(void)
{
	MGraphG;
	CreateMGraph(&G);
	MiniSpanTree_Kruskal(G);
	return0;
}

E. 演算法分析與設計題目

第一題用貪心思想 找出用時最短的m個作業交給機器同時開始加工 然後再依次將剩下的作業中最短完成作業取出放入已完成的機器加工 當最後一台機器完工時間就是所用最短時間 思路是這樣子 具體演算法實現的話。。由於我也是學生=、=寫代碼還不是很熟練。。可能等我寫好了你考試來不及。。。你還是自己來吧

第二題
1.背包問題是什麼=、=我們教材不一樣 不了解具體問題。。
2.4皇後
#include<iostream.h>
const int n = 4 ;
const int n_sub = n - 1 ;
int queen[n] ;
bool row[n] ;
bool passive[2*n-1];
bool negative[2*n-1];
int main()
{
int cur = 0 ;
bool flag = false ;
queen[0] = -1 ;
int count = 0 ;
while(cur>=0)
{
while(cur>=0 && queen[cur]<n && !flag)
{
queen[cur]++ ;
if(queen[cur] >= n)
{
queen[cur] = -1 ;
cur-- ;
if(cur>=0)
{
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;
}
false ;
}
else
{
if(row[queen[cur]] == false)
{
flag = true ;
if( passive[queen[cur] + cur] == true || negative[n_sub + cur - queen[cur]] == true) {
flag = false ;
}
else
flag = true ;
if(flag) {
if(cur == n-1)
{
count++ ;
}
row[queen[cur]] = true ;
passive[queen[cur] + cur] = true ;
negative[n_sub + cur - queen[cur]] = true ;
cur++ ;
if(cur >= n) {
cur-- ;
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;
}
flag = false ;
}
}
}
}
}
cout<<n<<"皇後問題一共有"<<count<<"種解法"<<endl ;
return 0 ;
}
這個是代碼。。。狀態空間樹這里畫不出來。。。

第三題
你網路下基本都有的=、=。。。我網路出來不好意思貼了你自己去看下吧
比如1.的答案：
最壞情況給出了演算法執行時間的上界，我們可以確信，無論給什麼輸入，演算法的執行時間都不會超過這個上界，這樣為比較和分析提供了便利。

F. python習題（演算法）

這個就是循環2n次呀。先是讓x=x+c,在把c更新一下c=c+b，最後讓b=b+a，這就完成一次循環了。
不過你給的程序不完整。