东北大学计算机-考研真题(2)本站小编 免费考研网/-02-08
二、 编写算法题
1.编写算法判断字符串表示的出栈入栈序列是否合法，其中A代表入栈，D代表出栈，仅有这两个字符构成。栈初始为空，例如“ADAADDDD”为非法序列，“ADAADDAD”为合法序列。
(1)算法思想
(2)算法实现
2.编写算法判断采用二叉链表结构储存的的两颗二叉树是否相等
(1)算法思想
(2)算法实现
3.编写算法判断采用邻接表储存的无向图中，是否存在从顶点U到V且长度为K的简单路径。
(1)算法思想
(2)算法实现
东北大学考研题
C语言
一、简答题
1.若定义int a[10];int *p=a;请写出3种求数组a第i个元素的方式。
2.如果想通过一个函数获得多个返回值，请写出至少2种实现方法，并举例说明
3.举例说明结构体和共用体的区别。
二、综合题：请写出运行结果
1.
#include
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
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
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
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)算法实现
