演算法設計題

㈠ 演算法設計與分析習題誰會做

這個是利用分治思想來解
考點是快排
可以用二分法對原數組進行排序
快排(QuickSort)是一種基於分治思想的二分排序法。對於一段序列，我們先

選出一個劃分元素，然後用線性的時間復雜度將大於和小於劃分元素的元素

移動到劃分元素的兩邊，再由劃分元素處將序列拆分為兩部分，分別進一步

處理。顯然這里劃分元素的選擇決定了拆分序列的平均程度。

因為演算法是二分的，每段序列的處理是線性的，易知時間復雜度為O(nlgn)。

可是假設每一次選擇的劃分元素都是序列里最大或最小的，那麼拆分的時間

復雜度也會變成線性的，所以快排在最壞情況下的時間復雜度為O(N^2)。

㈡ 求解數據結構的演算法設計題

想法：先將兩表合並，然後再倒轉……或者在合並的時候，在每個節點的前面添加後處理的節點，然後返回最後的節點的首地址

##########################################
思路就這樣了，沒有時間寫了……相信你有這實力寫出來的……加油
逐步比較，然後就將這個的next指針指向已經處理的首地址，循環下去
等待高手寫演算法吧
#############################################
有時間就寫了一下……
#include<stdio.h>
typedef struct link
{
int num;
struct link * next;
}LINK,*Link;
Link addlink(Link * link,int i,int where)
{
Link tmp=(Link)malloc(sizeof(LINK)),next;
tmp->num=i;
if(where==0)//after
{ (*link)->next=tmp;
tmp->next=NULL;
}
if(where==1)//before
{
tmp->next=(*link);
}
return tmp;
}
void initfirst(Link * link)
{
(*link)=(Link)malloc(sizeof(LINK));
(*link)->num=0;
(*link)->next=NULL;
}
Link initlink()
{
Link tmp, tmp1,tmp2;
initfirst(&tmp);
int i=0,num=0,num1=0;
printf("\n請輸入數字的個數，然後輸入各個數字，請安遞增排列:");
scanf("%d",&num);
tmp1=tmp;
for(;i<num;i++){
scanf("%d",&num1);
if(i==0)
{
tmp->num=num1;
continue;
}

tmp1=addlink(&tmp1,num1,0);
}
return tmp;

}
void putlink(Link link)
{
Link tmp=link;
while(tmp!=NULL)
{
printf("%d->",tmp->num);
tmp=tmp->next;
}
}
Link joinlink(Link la,Link lb)
{
Link tmp,tmp1,tmp2,*lc;
initfirst(&tmp);
tmp1=tmp;
int i=0,min=0;
while(la!=NULL&&lb!=NULL)
{
if(la->num>lb->num)
{lc=&lb;
min=lb->num;}
else
{lc=&la;
min=la->num;
}
if(i==0)
{
tmp->num=min;
tmp=tmp->next;
i++;

}
else
{ tmp=addlink(&tmp,(*lc)->num,1);
(*lc)=(*lc)->next;
}
}
while(la!=NULL)
{
tmp=addlink(&tmp,la->num,1);
la=la->next;
}
while(lb!=NULL)
{
tmp=addlink(&tmp,lb->num,1);
lb=lb->next;
}
tmp1=NULL;
return tmp;
}
int main()
{
Link la,lb,lc;
printf("初始化LA：");
la=initlink();
printf("\nLa=");putlink(la);
printf("\n初始化LB：");
lb= initlink();

printf("\nLb=");
putlink(lb);
lc=joinlink(la,lb);
printf("\nLc=");
putlink(lc);
system("pause > nul");
return 0;
}

㈢ 求解一道演算法設計題

void invert(sequenlist *p)
{
char mid;
int i,j;
i=0;
j=p->last-1;
while(i<j)
{
mid=p->data[i];
p->data[i]=p->data[j];
p->data[j]=mid;
i++;j--;
}
}

㈣ 數據結構演算法設計題

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

㈤ 一道數據結構的演算法設計題

#include<iostream>
#include<stack>
structTreeNode
{
intval;
TreeNode*left;
TreeNode*right;
TreeNode(intx):val(x),left(NULL),right(NULL){}
};
voidmaxDepthAndNodesNum(TreeNode*root)
{
if(root==NULL)
{
std::cout<<"maxdepth:"<<0<<std::endl;
std::cout<<"nodesnum:"<<0<<std::endl;
}
intmax_depth=0,nodes_num=0;
std::deque<TreeNode*>nodes;
nodes.push_back(root);
while(!nodes.empty())
{
max_depth++;
std::size_tcount=nodes.size();
nodes_num=nodes_num+count;
for(std::size_ti=0;i!=count;++i)
{
root=nodes.front();
if(root->left!=NULL)
{
nodes.push_back(root->left);
}
if(root->right!=NULL)
{
nodes.push_back(root->right);
}
nodes.pop_front();
}
}
std::cout<<"maxdepth:"<<max_depth<<std::endl;
std::cout<<"nodesnum:"<<nodes_num<<std::endl;
}
intmain(intargc,charconst*argv[])
{
TreeNodenode1(3),node2(4),node3(6),node4(8),node5(9),node6(123),node7(10);
node1.left=&node2;
node1.right=&node3;
node2.left=&node4;
node2.right=&node5;
node4.left=&node6;
node4.right=&node7;
maxDepthAndNodesNum(&node1);
getchar();
return0;
}

㈥ 數據結構演算法設計題和2個計算題（重分）

1：
至少為3
進棧：s1,s2,
s3,
s4,
s5,s6
出棧：
s2,
s3,
s4,
s6,s5,s1
棧內
元素
個數：1，2，1，2，1，2，1，2，3，2，1，0
2：
2^0+2+2^2+2^3+……+2^(h-1)=2^h-1
》》[2^h-1]<n<[2^(h+1)-1]
所以h=[log2
(n+1)]向下取整
演算法設計題好久沒看了，很傷腦筋
希望對你有用

㈦ 演算法設計題

（再版）
0-1背包問題

0-1背包問題：給定n種物品和一個背包。項目我的體重是無線網路，它的價格是vi背包容量C.

Q：我應該如何選擇裝載物品的背包，使得裝入背包的總價值呢？

選擇項目裝入背包的每個項目我只有兩種選擇，即裝入背包或不裝入背包。項目i裝入背包多次，不僅載入的項目我。

因此，這個問題被稱為0-1背包問題。

?0-1解向量（X1，X2，...，XN），西安∈{0,1}，1 <= I <= N。

動態編程解決方案：

集0-1背包問題給定的子最優值，M（I，J），M（我，j）是第j背包容量，可選擇的項目我，我+1，...，N 0-1背包問題的最優值

無效背包（）

INT I，J;

為（i = 0; I <=我+ +）
為（J = 0 J <= JMAX; J + +）

M [] [J] = 0;

（i = 0; <= n; i + + ）

為（J = 0; <= JMAX; J + +）

（W [I]> J）

米[I] [J] = M [I-1] [J];

其他

M [] [J] = MAX（M [I-1] [J]，M [I-1] [JW [我] + V [I]）;

printf的（「％d \ N」，M [N] [C]）; BR />
}

回溯解決方案：

無效1背包（I）

{
BR />（>），百視通= CV

其他

{

（CW + W [I] <= C ）
{

CW + = W [我];

CV + = V [I];

背包（i +1）;

CW-= W [I];

CV-= V [I];

}
a>
背包（+1）;

}

}