二、 编写算法题


1.编写算法判断字符串表示的出栈入栈序列是否合法，其中A代表入栈，D代表出栈，仅有这两个字符构成。栈初始为空，例如“ADAADDDD”为非法序列，“ADAADDAD”为合法序列。
（1）算法思想
（2）算法实现
2.编写算法判断采用二叉链表结构储存的的两颗二叉树是否相等
（1）算法思想
（2）算法实现
3.编写算法判断采用邻接表储存的无向图中，是否存在从顶点U到V且长度为K的简单路径。
（1）算法思想
（2）算法实现
 
 
 
 
 
 
 
 
 
 
 
 
 
东北大学2019考研题
C语言
一、简答题
1.若定义int a[10];int *p=a;请写出3种求数组a第i个元素的方式。
2.如果想通过一个函数获得多个返回值，请写出至少2种实现方法，并举例说明
3.举例说明结构体和共用体的区别。
二、综合题：请写出运行结果
1.
#include <stdio.h>
void f(int a)
{
    int i;
    if(a!=0)
    {
        f(a-1);
        for(i=1;i<=a;i++)
            printf("%d",a);
        printf("\n");
    }
}
int main()
{
    f(3);
    return 0;
}
2.
#include <stdio.h>
int main()
{
    int s,i,j,a[5][3],total=14;
    for(int m=0;m<5;m++)
        for(int n=0;n<3;n++)
        {
            a[m][n]=total;
            total--;
        }
    for(i=0;i<5;i++)
    {
        s=0;
        for(j=0;j<3;j++)
        {
            if(i*j%5==3)
                break;
            else
                s=s+a[i][j];
        }
        printf("%d\n",s);
    }
    return 0;
}
3.
#include<stdio.h>
void fun(char *s)
{
    int i;
    for(i=0;*(s+i)!='\0';i++)
        if(*(s+i+2)>='A'&&(s+i)<='z')
            if(*(s+i+2)!='\0')
                *(s+i)=*(s+i+2);
            else
                *(s+i)='z';
}
int main()
{
    char str[]="AgeefAI";
    fun(str);
    puts(str);
    return 0;
}
4.
#include <stdio.h>
int a=30,b=50;
void func(int *p1,int *p2)
{
    p1=&a;
    *p2=b;
}
int main()
{
    int i=1,b=5;
    for(i=1;i<5;i++)
    {
        func(&i,&b);
        printf("%d,%d\n",i,b);
    }
    return 0;
}
三、编程题
1.一个数的平方的层次等于该数自身的自然数被称为自守数，例如5*5=25，25*25=625，9376*9376=87909376。求10000以内的所有自守数。
2.编写一个函数int judgeM(int a[N][N])，判断给定的函数矩阵a[N][N]是否符合上三角矩阵条件。其中N代表N*N矩阵。如果符合上三角矩阵条件返回1，否则返回0。角矩阵的主对角线下方的元素都为0。
3.个人金库消费记录按如下结构体定义：
struct Consume{
 int id; //流水号
 unsigned pid; //消费项目标号，每个消费项目编号唯一
 char p[100]; //消费项目名称
 float cost; //消费项目金额
};
请编写函数void maxCost(struct Consume record[N]),统计在给定的消费记录struct Consume record[N]中消费金额最多的消费项目，输出消费项目名称和对应项目的总消费金额，
需要注意的是，每个项目可能发生多次消费行为，每次消费行为会形成一个消费记录。
数据结构
一、简答题
1.有一个二叉树按层次顺序放在一维数组中，如下图：
（1）写出该树的后序遍历序列
（2）画出该树的后序线索二叉树
 

 
2.带权无向图的邻接矩阵如下图所示。画出该邻接表和用Prim算法生成最小树的过程。 
∞ 1 1 ∞ ∞ ∞
1 ∞ 1 2 ∞ ∞
1 1 ∞ ∞ 3 ∞
∞ 2 ∞ ∞ 1 1
∞ ∞ 3 1 ∞ 1
∞ ∞ ∞ 1 1 ∞

3.给出一组关键字T={24,19,32,43,38,13,22,20,6,18},写出下列算法从小到大排序的第一趟结束时的序列。
（1）希尔排序（增量为5）
（2）堆排序（先建成一个堆，然后以堆顶取下一个元素后，将堆减量一项）
4.写出关键字序列{503，087，061，512，098，897，275，653，426}建立一颗平衡二叉树排序的过程，并写出调整平衡时的旋转类型，写出在多概率情况下查找成功和查找失败的平均查找长度。
二、编写算法
1.给定一个单链表存储的互异整数数列，编写算法，求出所有的递增和递减序列的数目，例如数列7，2，6，9，8，3，5，2，1，可分为（7，2）（2，6，9）（9，8，3）（3，5），（5，2，1）共5个数列子数列，结果为5。
（1）算法思想
（2）算法实现
2.二叉树中值为x的结点不少于1个，采用二叉链表存储，编写算法，打印值为x的结点的所有祖先。
（1）算法思想
（2）算法实现
3.判断一个以邻接表为存储结构的无向图G是否连通，若连通，返回1。否则，返回0.
（1）算法思想
（2）算法实现