1． 数据的物理存储方式有4种：1）顺序存储。2）链式存储。3）索引存储。4）散列存储
2． 判断算法时间复杂度的根据是当n趋向无穷大时函数的极限，确定时间复杂度的步骤是：1）计算算法的语句频度。2）由语句频度给出时间复杂度。
例：
void f(int n)
{
int i = 91,j=100;
while(j>0)
{
if(i>100)
{
x-=10;
y--;
}
else
i++;
}
}
因为while循环与n无关，所以T(n)=O(1)。
3，一个顺序表L=(a1,a2…an),设计一个算法，要求用最少的时间把所有值为负数的元素，移动到全部值为正数的前面。
分析：题目中的“最少的时间”就意味着时间复杂度为O(n).
#include <stdio.h>
struct SqList
{
int data[20];//顺序表存储空间
int length;//当前长度
};
void Move(struct SqList &L)
{
int i = 0,j = L.length-1;
int tmp;
while(i<j)
{
while(L.data[i]<=0)i++;
while(L.data[j]>=0)j--;
if(i<j)
{
tmp = L.data[i];
L.data[i] = L.data[j];
L.data[j] = tmp;
}
}
}
void travel(struct SqList &L)
{
int i = 0;
while(i<L.length)
{
printf("%d\t",L.data[i++]);
}
}
int main()
{
struct SqList L;
int i = 0;
L.length = 10;
while(i<10)
{
L.data[i++] = -i;
L.data[i++] = i;
}
i = 0;
travel(L);
Move(L);
travel(L);
return 0;
}
4.顺序表A=(a1,a2…an,b1,b2…bm),将A换成(b1,b2…bm,a1,a2..an),要求不能够用额外的辅助空间。
分析：由于没有说m=n,所以不能够用“对应元素互换”不行，因此先将整个表逆置，再分别逆置两个子表。
void Sq_Reverse(SqList &L,int begin,int end)
{
int i,j;
ElemType tmp;
for(i=begin,j=end;i<end;i++,j--)
{
tmp = L.data[i];
L.data[i] = L.data[j];
L.data[j] = tmp;
}
}
void process(SqList &L,int m,int n)
{
Sq_Reverse(0,m+n-1);
Sq_Reverse(0,n-1);
Sq_Reverse(n,m+n-1);
}
注：比较单链表的逆置：
void Link_Reverse(LinkList &head)
{
LNode *p = head->next,*q;
head->next = NULL;
while(p!=NULL)
{
q = p->next;
p->next = head->next;
head->next = p;
p = q;
}
}
5．为了合并两个各自含有n个元素的有序表LA和LB,在最坏情况下，至少要2n-1次比较。
6．Head是带头结点的单链表的头指针，编写递归算法，逆序输出表中各个元素的值。
void Output(LNode *head)
{
if(head!=NULL)
{
Output(head->next);
printf("%d",head->data);
}
}
7.简单选择排序带头结点的双向链表
void SelectSort(DLinkList &L)
{
DLink *p,*q,*r;
p = L->next;
while(p!=NULL)
{
q = p->next;
r = p;
while(q!=NULL)
{
if(q->data<r->data) r = q;
q = q->next;
}
if(r!=p)
{
tmp = p->data;
p->data = r->data;
r->data = tmp;
}
p = p->next;
}
8,确定N个数中的第K大者。
#include <stdio.h>
int a[]={9,2,4,5,6,8,5,3};
int k=4,n=8;
void sort(int a[],int n)
{
int i,j,tmp;
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
if(a[i]<a[j])
{
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
}
void travle(int a[],int n)
{
int i;
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
printf("\n");
}
void process(int a[],int num,int n)
{
int i=0,j;
while(i<n&&a[i]>=num)i++;
for(j=k-2;j>=i;j--)
{
a[j+1] = a[j];
}
a[i] = num;
}
int main()
{
int i;
travle(a,n);
sort(a,k);
for(i=k;i<n;i++)
{
process(a,a[i],n);
}
travle(a,n);
printf("%d\n",a[3]);
return 0;
}
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2006/09/08/499052.html，如需转载请自行联系原作者
