东北大学计算机专业研究生入学考试2001年真题
发布时间
阅读量：
阅读量
/*---------------------------------数据结构部分---------------------------------*/
/*二.设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法:(要求用最少的时间和最小的空间)
(1)确定在序列中比正整数x大的数有几个(相同的数只计算一次，如序列(20，20，17，16，15，15，11，10，8，7，7，5，4)中比10大的数有5个)；
(2)在单链表中将比正整数x小的数按递减次序排列；
(3)在单链表中将比正整数x大的偶数从单链表中删除；*/
void exam(Linklist La,int,x)
{
p = La->next;
q = p; //p为工作指针,q指最小元素
int k = 0;
pre = la;
la->next = NULL;
while( p && p->data < x)
{ //比x小的数递减
r = p->next;
p->next = La->next;
La->next = p;
p = r ; //置逆
}
q->next = p;
pre = q; //重新链接
while(p->data = x)
{ // 考察等于x的情况
pre = p;
p = p->next;
}
while(p)
{ // k为计数器
k++;
x = p->data; //避免重复计算
if(x%2 == 0)
{ //删除偶数
while(p->data == x)
{ // 考察等于x的情况
u=p ;
p=p->next;
free(u);
}
pre->next=p;
}
else// 处理奇数
{
while(p->data == x)
{
pre->next = p;
pre = p;
p = p->next;
}
}
}
}
/*三.设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。
对于满二叉树，已知任一遍历序列可唯一确定一棵二叉树，即可将任一遍历序列转换为另一遍历序列。*/
void pretopost(ElemType pre[],ElemType post[],int L1,int H1,int L2,int H2)//H1为主段，L1为序列位置
{
if(H1>L1)
{
post[ H2]=pre[L1]; // 根结点
half=(H1-L1)/2;
pretopost(pre ,post, L1+1, L1+half, L2+half-1);
pretopost(pre, post, L1+half+1 ,H1, L2+half, H2-1)
} //if
} // preropost
/*四.2.写出后序线索二叉树的非递归遍历算法。*/
void PreorderTraverse_Thr(BiThrTree T)// T指向头结点，T的左链指向根结点.
{
p=T→lchild;
while(p!=T)
{
printf(p->data);
if(p->rtag == 0)
p = p->rchild;
else
p = p->lchild;
} // while
} //PreorderTraverse_Thr
/*五.在有向图G中，如果r到G的每个结点都有路径可达，则称结点r为G的根结点，编写一个算法完成下列功能：
(1) 建立有向图G的邻接表存储结构：
(2) 判断有向图G是否有根，若有，则打印出所有根结点的值。*/
(1)void CreatALG(ALGraph &G)
{
// 建立有向图的邻接表存储结构
int i;
ArcNode *p;
scanf(&G->vexnum, &G->arcnum);
for(i = 0;i < G->vexnum;i++)
{
scanf((&G->ver[ i ].data);
G->ver[ i ].firstarc = NULL;
} //for
for(i = 0; i < G->arcnum; i++)
{
scanf(&v1,&v2);
j = Locatevex(G,v1);
k = Locatevex(G,v2); // 确定v1,v2在G中位置
p = (ArcNode)malloc(sizeof(ArcNode));
p->adjvex = k;
p->next = G.ver[ j ].firstarc;
G.ver[ j ].Firstarc = p;
} //for
} //CreatALG
(2)void DfsTraverse(ALGraph G)
{
//利用深度优先搜索，判断有向图G是否有根结点。
int visited[maxsige],count; //count为记录结构的顶点数。
for(v = 0;v < G.vexnum; v++)
{
for(v = 0;v < G.vexnum ; v++)
visited[ v ] = 0;
count = 0;
DFS(G,v) ;
if(count == G.vexnum)
printf(G.ver[ v ].data);
} //for
} //DfsTraverse
void DFS(ALGraph G,int v)
{
//从第v个顶点出发递归地深度优先遍历图G
visited[ v ] = 1;
count++;
for(p = G.vertices[ v ].firstarc; p; p = p->nextarc)
{
w = p->adjvex;
if(!visited[ w ])
} //for
} // DFS
/*六.对下面的关键字集(30，15，21，40，25，26，36，37)，若查找表的装填因子为0.8，采用线性探测再散列解决冲突，做：
(1)设计哈希函数；
(2)画出哈希表；
(3)计算查找成功和查找失败的平均查找长度；
(4)写出将哈希表中某个数据元素删除的算法；*/
(4)将删除后的空间置标记为'EMPTY'
Void HSDelete(HashTable &H,KeyType key)
{
// 删除哈希素中等于key的关键字，用线性探测再散列解决冲突
i = H(key ); // 取得哈希地址
if(H[ i ]==Null)
exit(1);
if(H[ i ]==key)
{
e = H [ i ];
H[ i ] = EMPTY;
} //if
else
{
di=1;
j=(H(key)+di)%m; // m 为表长
while(H[ j ]&&j != i)
{
di=di+1;
j=((H(key)+di)%m;
} //while
if(H[ j ] == Null)
exist(1);
else if(j = i)
exist(1);
else if(H[ j ] == key)
{
e=H[ j ];
H[ j ]=EMPTY;
}
} //else
} //HSDelete
/*----------------------------------C语言部分------------------------------*/
/*三.编写一个函数，求字符串a和b的最长公共子串。（不能使用字符串标准函数）*/
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define M 100
char* LCS(char left[],char right[])
{
int lenLeft = strlen(left),lenRight = strlen(right);
int start,end = 0,len = 0,i,j,k;//start公共子串的起始点，end公共子串的终止点，len公共子串的长度
char *c, *p;
c = (char *)malloc(lenRight);
for(i = 0;i < lenLeft;i++)//串1从前向后比较
{
for(j = lenRight-1;j >= 0;j--)//串2从后向前比较
{
if(left[i] == right[j])
{
if(i == 0||j == 0)
c[j] = 1;
else
c[j] = c[j-1]+1;
}
else
c[j] = 0;
if(c[j] > len)
{
len = c[j];
end = j;
}
}
}
start = end-len+1;
p = (char*)malloc(len+1);//数组p记录最长公共子串
for(i = start; i <= end;i++)
{
p[i-start] = right[i];
}
p[len] = '\0';
return p;
}
void main()
{
char str1[M],str2[M];
printf("请输入字符串1:");
gets(str1);
printf("请输入字符串2:");
gets(str2);
printf("公共子串为:");
printf("%s\n",LCS(str1,str2));
}
/*四.编写一个函数，将数组a按每行的最大值从小到大对数组的行进行排序*/
#define MAXSIZE 10
void changeRow(int i, int j, int a[][MAXSIZE], int n)
{
if(i == j)
return;
for(int k = 0; k < n; k++)
{
int temp;
temp = a[i][k];
a[i][k] = a[j][k];
a[j][k] = temp;
}
}
void Sort(int a[][MAXSIZE], int m, int n)
{
int MaxKey[MAXSIZE];
int i,j;
for(i = 0; i < m; i++)
{
iMax = a[i][0];
for(j = 1; j < n; j++)
{
if(a[i][j] > iMax)
{
iMax = a[i][j];
}
}
MaxKey[i] = iMax;
}
for(i = 0; i < m; i++)//用选择排序，每次找最大的
{
iMax = MaxKey[0];
k = 0;
for(j = 0; j < m-i; j++)
{
if(iMax < MaxKey[j])
{
iMax = MaxKey[j];
k = j;
}
}
changeRow(k, m-i-1, a, n);
temp = MaxKey[m-i-1];
MaxKey[m-i-1] = MaxKey[k];
MaxKey[k] = temp;
}
}
/*五.编写一个递归函数，判断两棵二叉树是否相似。如果两棵二叉树s和t相似，那么或者它们的左右子树都相似，或者s和t都为空。*/
int IsEqual(BiTree s, BiTree t)
{
if((!s)&&(!t))
return 1;
else
{
if((s)&&(!t))
return 0;
if((!s)&&(t))
return 0;
if(IsEqual(s->lchild, t->lchild))
{
if(IsEqual(s->rchild, t->rchild))
return 1;
else
return 0;
}
else
return 0;
}
}
/*六.一个英文文本文件，仅由英文字母、空格、逗号、句号和换行符组成，文本中的句子由句号分割。
1.编写一个函数char *getsen(FILE *fp),用于从文本中读取句子。函数返回的是指向一个句子的指针；
2.编写一个程序，当输入一个英文单词，如run时，判断该单词是否在这个文件中。若文件中有这个词，则将包含该单词的所有句子，输出到以该单词命名的.TXT文件中，如run.txt文件。*/
/*七.接上题，要求用单向链表结构实现：
1.对上题所生成的文件，如run.txt进行统计，统计文件中包含的单词总数、不同单词的数量以及每个单词的词频（即单词出现的次数）；
2.编写一个函数，对单词按词频进行降序排序；
3.输出最后的统计结果*/全部评论 (0)
还没有任何评论哟~