16-18真题

1. 循环双链表，结点previous,data,next和访问频度域freq,初试为0，每当链表进行一次Locate(L,x)运算时，令x结点freq域的值加1，并使其链表结点频度按递减顺序排序，并实现Locate(L,x)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//1. 找到指定结点 2. 访问频度+1 3. 进行排序
#include<iostream>
using namespace std;
const int N=100010;
struct DNode{
    int data;
    int freq;
    struct DNode *next;
    struct DNode *prior;
};
DNode *h;
void sort(DNode *h){//根据freq降序排列，写成一个函数
    DNode *p,*q,*pre;
    p=h->next->next;//指向第二个结点
    h->next->next=NULL;//隔开第一个结点和第二个结点
    while(p!=NULL){
        q=p->next;
        pre=h;
        //根据freq降序
        while(pre->next!=NULL&&(pre->next->freq)>(p->freq))
            pre=pre->next;
        p->next=pre->next;
        if(pre->next!=NULL){
            pre->next->prior=p;
        }
        pre->next=p;
        p->prior=pre;
        p=q;
    }
}
void LocateNode(DNode *h,int x){
    DNode *p;
    p=h->next;
    int i=0;
    //查找x所在位置
    while(p!=NULL&&p->data!=x){
        p=p->next;
        ++i;
    }
    p->freq++;//x元素的freq++
    //sort(h);//下面是sort
    DNode *q,*pre;
    p=h->next->next;
    h->next->next=NULL;
    while(p!=NULL){
        q=p->next;
        pre=h;
        //根据freq降序
        while(pre->next!=NULL&&(pre->next->freq)>(p->freq))
            pre=pre->next;
        p->next=pre->next;
        if(pre->next!=NULL){
            pre->next->prior=p;
        }
        pre->next=p;
        p->prior=pre;//双链表需要链接四个指针
        p=q;
    }
}

2. X和Y是用结点大小为1的单链表表示的串，请设计算法找出X中第一个不在Y中出现的字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//X(1-n)：Y(对于X中的每一个结点遍历Y中的所有结点)
void find(LinkList L1,LinkList L2){
    LinkList p,q;
    p=L1->next;
    q=L2->next;
    while(1){
        if(p->data==q->data){
            p=p->next;
            q=L2->next;
        }else
            q=q->next;
        if(p==NULL){
            cout<<"x中的字符全部在y中出现过"<<endl;
            break;
        }
        if(q==NULL){
            cout<<"x中第一个不在Y中出现的字符为："<<endl;
            cout<<p->data<<endl;
            break;
        }
    }
}

3. 试编写算法以单链表存储结构实现直接选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//n个数据，排n-1次,每次选择待排序列中最小值交换到待排序列中的第一位置
void ListChooseSort(LNode *head){
    //用选择法进行排序
    LNode *p,*q;
    LNode *temp;
    for(p=head->next;p->next;p=p->next){//从第一个结点开始，到倒数第二个结点结束
        temp=p;
        for(q=p->next;q;q=q->next){//从p的下一个结点开始，到倒数第二个结点结束
            if(temp->data>q->data)
                temp=q;//选择q
        }
        swap(p->data,temp->data);//把待排序列中最小值交换到p结点的数据域
    }
}

4. Rand为[0,1]均匀随机产生数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int main(){
    int a[1000];
    int i;
    for(i=0;i<1000;i++)
        a[i]=rand()*2;
    for(i=0;i<1000;i++)
        printf("%d,",a[i]);
    return 0;
}
1. rand()不需要参数，它会返回一个从0到最大随机数的任意整数，最大随机数的大小通常是固定的一个大整数
2. 0~99这100个整数中的一个随机数，可以表达为:int num=rand()%100;
3. 产生1~100，表达为:int num=rand()%100+1;

5. 二分法实现快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
double fun(double x,int n){
    if(n==0)//递归结束条件
        return 1;
    double half;
    if(n%2==1){//递归转移方程
        half=fun(x,n/2);//x的n/2次方
        return x*half*half;
    }else{
        half=fun(x,n/2);
        return half*half;
    }
}
double pow(double x,int n){
    double result=fun(x,n);
    if(n<0)
        result=1/result;
    return result;
}

int pow(int x,int n){
    int t=1;
    while(n){
        if(n%2==1){
            n=n-1;
            t*=x;
        }
        x*=x;
        n/=2;
    }
    return t;
}

6. 实现一个栈Stack，要求实现Push(入栈)，Pop（出栈），Min的时间复杂度为O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
使用两个栈_data和_min，_min作为辅助栈。元素value入栈时，将value和_min栈顶元素做比较，如果value小于等于_min.top()，将value分别push到_data和_min，否则value只push到_data中，元素出栈时_data和_min都执行pop操作
*/
#include<iostream>
#include<stack>
using namespace std;
stack<int> _data,_min;
void Push(int value){
    //把新元素添加到辅助栈
    _data.push(value);
    //当新元素比之前的最小元素小时，把新元素插入到辅助栈里
    //否则把之前的最小元素重复插入辅助栈里
    if(_min.size() == 0 || value < min.top())
        _min.push(value);
    else
        _min.push(_min.top());
}
void Pop(){
    if(_data.size()<=0)
        return;
    _data.pop();
    _min.pop();
}
int Min(){
    if(!min_empty())
        return _min.top();
}

7. 用二叉树的存储结构将一棵二叉树变成二叉排序树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//先遍历一遍二叉树获得所有结点值，再依次插入二叉排序中
int BTSInsert(BTNode *p,int data){
    if(p==NULL){
        p=(BTNode*)malloc(sizeof(BTNode));
        p->lchild=p->rchild=NULL;
        p->data=data;
        return 1;
    }
    else{
        if(data==p->data)
            return 0;
        else if(data<p->data)
            return BTSInsert(p->lchild,data);
        else
            return BTSInsert(p->rchild,data);
    }
}

8. 有两个n维向量相乘，求其点乘的最小值

两个n维的向量，向量的点乘是指向量对应维度的乘积相加，但是我们可以将向量维度交换下可以得到更小的向量点乘，例如三维向量【1,3,-5】和【4,-2,-1】，最小向量点乘为27，即将维度变为【3,1,-5】和【-2,-1,4】
只要把第一个向量进行全排列，就可以得到所有的乘积
程序设计要求：输入一个整数n为向量的维度，然后输入两个n维度的向量，用空格区别向量元素，输出为一行，包含一个整数，为最小的点乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
1. 进行全排列:三行代码 交换 进入下一层 再交换
2. 当排列好之后进行点乘，当结果小于当前最小值时候进行更新
*/

#include<iostream>
using namespace std;
const int Maxnn=1e9+1;//数值的最大值
const int Maxn=1e2+1;//数组的最大值
int n;
int ans=Maxnn;
int a[Maxn],b[Maxn];
int sum;
void backtrack(int t){
    if(t>n){
        sum=0;
        for(int i=1;i<=n;i++)
            sum+=a[i]*b[i];
        if(sum<ans)
            ans=sum;
    }else{
        for(int i=t;i<=n;i++)//从第t个元素交换到第n的元素
        {
            swap(a[t],a[i]);
            backtrack(t+1);
            swap(a[t],a[i]);//回溯，使得a[t]的值不变
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    backtrack(1);
    cout<<ans<<endl;
    return 0;
}

9. 给出五位任意字母或者数组，输出他们排列组合所得到的的所有的合法序列。合法序列是指字符串包含元音字母，且元音字母前后都必须是辅音字母。元音字母为:aeiou

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//1. 有元音字母2. 0,4不能为元音 3. 不能有两个元音相邻的情况
void reverse(char *s,int i,int n){
    int temp=0;
    while(n>i){
        temp=s[i];
        s[i]=s[n];
        s[n]=temp;
        i++;
        n--;
    }
}
//用来判断是否可以打印，0不能打印，1可以打印
int isPrint(char *perm,int to){
    char first=perm[0];//0
    char end=perm[to];//4
    if(first=='a'||first=='e'||first=='i'||first=='o'||first=='u'||end=='a'||end=='e'||end=='i'||end=='o'||end=='u')
        return 0;
    int flag=0;//对一个元素都标记一次
    for(int i=0;i<=to;i++){
        char tmp=perm[i];
        if(tmp=='a'||tmp=='e'||tmp=='i'||tmp=='o'||tmp=='u'){
            if(flag==1){//前面一个元素是原因
                return 0;
            }else{
                flag=1;//表明这个元素是元音
            }
        }else{
            flag=0;//表明这个元素是辅音
        }
    }
    int sum=0;
    for(i=0;i<=to;i++){
        if(perm=='a'||perm=='e'||perm=='i'||perm=='o'||perm=='u')
            sum++;
    }
    if(sum<1)
        return 0;
    return 1;
}
void CalAllPer(char *perm,int from,int to)//from:0 to:4
{
    if(to <= 1)
        return;
    if(from == to){
        int flag = IsPrint(perm,to);
        if(flag==1){
            for(int i=0;i<to;i++)
                printf("%c",perm[i]);
        }
        printf("\n");
    }
    else{
        for(int j=from;j<to;j++){
            swap(perm[j],perm[from]);
            CalAllPer(perm,from+1,to);//递归
            swap(perm[j],perm[from]);
        }
    }
}
int main(){
    char a[]="abelc";
    CalAllPer(a,0,5);
    return 0;
}