东北大学历年初试考研真题分享 - 图文

东北大学96考研题

一、（25分）每小题5分 1． 根据下图完成：

1） 画出该图的十字链表存储结构图。 2） 写出其拓扑排序的输出序列。 3） 写出图的强连通分量（支）。 4） 写出到的所有路径及简单路径。

2.给定8个权值集合（2，5，3，10，4，7，9，18）画出含有8个叶子结点的最佳三叉

归并树，并计算出

3.知含有8个结点的一棵二叉树，按先序、中序、后序进行遍历后，有些结点序号不清

楚如下图示。要求构造出一棵符合条件的二叉树。 先根序遍历 --- 2 3 --- 5 --- 7 8 中根序遍历 3 --- 4 1 --- 7 8 6 后根序遍历 --- 4 2 --- 6 5 1

4.根据给定的关键字集合（20，15，40，35，45，25，50，30，10）顺序输入 1） 构造一棵完全二叉树； 2） 画出整理好的一棵堆树；

3） 画出一棵输出一个排序记录后的二叉树； 4） 画出重新调整好的堆树。

5.下图给出的是一棵三阶B树，处理时每次只能读一个结点到内存。要求：

① 计算出由图中结构用计算机查找到关键字（35）的记录并将其删掉，需进行

多少次读/写才能完成？

② 画出删除关键字为（35）和关键字为（50）的记录后的三阶B树。

二、（10分）知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数

据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。 三、（12分）线性表(a1,a2,a3?an)中元素递增有序且按顺序存于计算机内。要求设计

一算法完成：

（1） 用最少的时间在表中查找数值为的元素。 （2） 若找到将其与后继元素位置交换。

（3） 若找不到将其插入表中并使表中元素仍递增有序。 四、（12分）设给定关键字输入序列为（100，90，120，60，78，35，42，31，15）用

散列法散列0——10的地址区间。要求设计一合理的散列函数；冲突时用链表法解决，写出散列算法，并构造出散列表在等概率查找情况下查找成功的平均查找长度是多少？ 五、（10分）设为t一棵二叉树的根结点地址指针，试设计一个非递归的算法完成把二

叉树中每个结点的左右孩子位置交换。 六、（14分）设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，

试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。 七、（15分）设t是一棵按后序遍历方式构成的线索二叉树的根结点指针，试设计一个

非递归的算法，把一个地址为x的新结点插到t树中，已知地址为y的结点有侧作为结点y的右孩子，并把插入后的二叉树仍为后序线索二叉树。

东北大学97考研题

一、（25分）按要求完成下题 1知 U=‘xyxyxyxxyxy’；t=‘xxy‘；

ASSIGN（S，U）；

ASSIGN（V，SUBSTR（S，INDEX（s，t），LEN（T）+1））； ASSIGN（m，‘ww’）

求REPLACE（S，V，m）= 2 知广义表A=（（（a）），（b），c，（a），（（（d，e）））） （1） 写出其一种存贮结构图； （2） 写出表的长度与深度；

（3） 用求头部，尾部的方式求出e。 3画出同时满足下列两条件的两棵相同的二叉树。 （1） 按先根序遍历二叉树顺序为ABCDE。 （2） 高度为5其对应的树（森林）的高度最大为4。 4下图为一棵二叉排序树完成：

（1） 写出平衡因子绝对值为2的结点； （2） 为何种类型的不平衡树；

（3） 画出调整好的平衡二叉树，写出相应的指针变化式。 5一个有向图的邻接表存贮如下

（1） 画出其邻接矩阵存贮； （2） 写出图的所有强连通分量；

（3） 写出顶点a到顶点I的全部简单路径。 二、断正误

（1） 二叉排序树查找总是比顺序查找速度快。

（2） 堆排序与快速排序相比堆比快速省时间。 K-2

（3） 深度为k且具有n个结点的二叉树其编号最小的结点序号为┕2 ┙ +1。 （4） 在m阶B一树中每个结点上至少┌m/2┐有个关键字最多m有个关键字。 （5） 影响外排序的时间因素主要是内存与外设交换信息的总次数。 三、线性表（a1 a2ａ３。。。。。。ａｎ）按顺序存贮，且每个元素都是整数不相同，设计把所有奇数指到所有偶数前边的算法。（要求时间最少，辅助空间最少） （１５分） 四、１与Ｌ２分别为两单链表头结点，地址指针，且两表中数据结点的数据域均为一个字母。设计把Ｌ１中与Ｌ２中数据相同的连续结点顺序完全倒置的算法。例：

（１５分）

五、知输入关键字序列为（１００，９０，１２０，６０，７８，３５，４２，３１，１５） 址区向为０~１１。设计一个哈希表函数把上述关键字散到０~１１中画出散列表（冲突用线性探测法）；写出查找算法，计算在等概率情况下查找长度。 （１５分） 六、一棵高度Ｋ具有ｎ个结点的二叉树，按顺序方式存贮：

１）编写用先根遍历树中每个结点的递归算法；

２）编写将树中最大序号叶子结点的祖先结点全部打印输出的算法。 （２０分）。

东北大学98考研题

一．完成下列各小题（每小题10分，共计30分）。

1）知三个字符分别为s=?ab…abcaabcbca…a? s?=?caab?, s??=?bcb? 利用所学字符串基本运算的函数得到结果串为 s???=?caabcbca…aca…a? 要求写出得到上结果串S“‘所用的函数及执行算法。

2）知记录关键字集合为（53，17，19，61，98，75，79。63，49，46）要求散列到地址区间（100，101，102，103，104，105，106，107，108，109）内，若产生冲突用开型寻址法的线性探测法解决。要求写出选用的散列函数；形成的散列表；计算出查找成功时平均查找长度与查找不成功的平均查找长度。（设等概率情况） 2）知一棵3阶B-树如下图所示： 1） 画出查入(18)的3阶B-树计算读结点/写结点次数。 2） 画处在插入（18）后的3阶B-树中删除（78）后的3阶B-树并计算读/写次数。

二．知线性表（a1 a2 a3 …an）按顺序存于内存，每个元素都是整数，试设计用最少时间把

所有值为负数的元素移到全部正数元素前边的算法：（15分） 例：（x, -x, -x, x, x, -x …-x）变为（-x，-x, -x…x x x）

三．已知L为链表的头结地址，表中共有m(m>3)个结点，从表中第i个结点(1

m个结点构成一个循环部分链表，设计将这部分循环链表所有结点顺序完全倒置的算法。（15分）

四．设有字母、数字共m个混合传输从甲站到乙站存储，字母、数字的个数不知，且不相等，希望从乙站输出时将字母与数字分开且字母保持原输入顺序，而数字与输入倒序， 要求在任何时刻只要已存元素个数之和小于M便能存储，试设计能满足上述要求的存储结构，并设计完成上述功能的算法，即乙接收甲传输及从乙输出的算法。（20分）

五．一棵高度为K且有n个结点的二叉排序树，同时又是一棵完全二叉树存于向量t中，试

设计删除树中序号为i且具有左右孩子的一个结点，而不使存储量增加保证仍为二叉排序树（不一定是完全二叉树）的算法。（20分）

六、假设一个有向图g已经以右图所示的逆邻接表形式存储在内存中，

要求：（1）写出逆邻接表的存储结构定义（3分）

（2）用文字写出在逆邻接表上实现拓扑排序的基本思想（3分） （3）写出在逆邻接表上实现拓扑排序的算法 （15分）。

东北大学2003年攻读硕士学位研究生试题 考试科目：C语言程序设计与数据结构

数据结构部分

一、（20分）简要回答下列问题 1．（7分）对于有n个顶点的无向图和有向图，采用邻接矩阵表示，如何判断以下问题：图中有多少条边？任意两个顶点i和j之间是否有边相连？任意一个顶点的度是多少？ 2．（8分）判别下列序列是否为堆（小根堆或大根堆），若不是，则将其调整为堆： （1）（100，86，48，73，35，39，42，57，66，21） （2）（12，70，33，65，24，56，48，92，86，33） （3）（05，23，20，35，28，38，29，61，56，76，40，100） 3．（5分）设A和B均为下三角矩阵，每一个都有n行n列。因此在下三角区域中各有n(n+1)/2个无素。另设有一个二维数组C，它有n行n +1列。试设计一个方案，将两个矩阵A和B中的下三角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元素aij和B的矩阵元素bij在C中的存放位置下标的公式。 二、（15分）已知f为单链表的表头指针，链表中存储的都是整型数据，试设计算法将此链表的结点按照递增次序进行就地排序。 三、（20）给出中序线索二叉树的结点结构，试编写在不使用栈和递归的情况下先序遍历中序线索二叉树的算法。 四、（20）设关键字是一个由26个小写字母组成的字符串，哈希表的长度为26。试编写算法，建立哈希表，并以第一个字符的字典顺序输出哈希表中的所有关键字。设哈希函数为 hash(x)=x中的第一个字符在字典顺序中的序号，采用线性探测再散列法来解决冲突。（假设函数f(x)能够计算出x中的第一个字符在字典顺序中的序号。）

C语言程序设计部分

一、回答下列问题（10分，每小题5分，答案写在答卷纸上） 1．下面定义是否正确，为什么？

void(*f(int no))();

写出指向函数 LRESULT MyProc();函数指针的定义，并利用该指针调用函数MyProc。 2.简述C语言中，参数处理的方式。

二、写出下列程序的运行结果（20分，每小题5分，答案写在答卷纸上） 1．

int main()｛

char strlist[3][5]=｛’\\0’｝;

strcpy(strlist[1],”write--”); strcpy(strlist[2],”here”);

printf(“%s/%s/%s”,strlist[0], strlist[1],strlist[2]);

｝ 2.

int main(){

int k; char c;

for(k=1,c=’A’;c＜’F’;k++＝｛ switch(++c)｛

case’A’: k++;break; case’B’: k*=2;break; case’C’: k-;

case’D’: k%=3;continue; default: k+=2; case’E’: k/=2; case’F’: k++; ｝ k++; ｝

printf(“%d”,k); ｝ 3.

void f(int *p, int *a)｛

*p=10; p=a; *p=100;

｝

int main()｛

int x=0,*p,a[3]=｛1,2,3｝; p=&x; f(p,a);

printf(“%d-%d-%d-%d”,x , *p, a[0], a[1]); ｝ 4.

int main()｛

float score[4]=｛｛60,47,80,26｝,｛65,59,67,90｝,｛43,78,90,56｝｝; float *search(float(*pointer)[4],int *pn); float *p;

int i, k=0,flag=1;

for(i=0;i＜3;i++,k=0,flag=1＝{

while((p=search(score+i, &k)==*(score+i)){

if(flag){printf(“\\nNo.%d scores:”,i);flag=0;} printf(“} %5.1f”,k+1, *(p+k));

k++

} }

}

float *search(float(*pointer)[4],int *pn){

int i; float *pt;

pt=*(pointer+1); for(i=*pn;i＜4;i++＝

if(*(*pointer+i)＜60＝{

*pn=i; return *pointer; }

return pt; } 三、（10分）已知2000年1月1日为星期六，编程求任意给定年元月1日的星期。 四、（17）今有一英汉词典文件EC.txt (文件大小超过1MB)，每一词条格式如下：

#词条[[%i词性[%z汉译！]??]??] 例如book词条如下：

#book%i n%z 书！%z 支票！%z 帐簿！%i，vt%z预定！%z登记姓名！ 编程完成

(1) 对词典建立索引文件，每间隔10kb，抽取一词条，当不是完整词条时，抽取不超过10kb的最大间隔的词条。索引文件格式为

词条 词条在文件中的位置

其中，词条为50bytes, 位置长整数占8bytes。该功能用函数CreateIndex完成。

（2）根据索引大小，将建立的索引内容装入一连续缓冲区。该功能用函数LoadIndex完成。 五、（18分）用回溯算法，编写函数fill(int num,int n),用0到num-1的数填充n×n的矩阵，要求填充的数不能重复，各行元素之和相同，各列元素之和也相同，输出所有可能的填充结果。

东北大学

2004年攻读硕士学位研究生试题

C语言程序设计部分

一、（20分，每小题5分）写出下列程序的运行结果（不必抄题，标明题号，答案另答在答卷纸上）

1．Int f(int *x int y) { if (*x

else y+=*x; return(*x+y); }

void main()

{ int a[3]={5,3,8}, *p=a; *p=f(&a[1],a[2]); *p+=f(&a[1],a[2]);

printf(“%d%d%d\\n”,a[0],a[1],a[2]); }

2. int main(intargc, char *argv[])

{FILE *fp1, *fp2; Int c;

If((fp1=fopen(argv[1], “r”))==NULL)

{ printf(“Cannot open %s\\n”,argv[1]); return(1); }

if((fp2=fopen(argv[2], “a”))==NULL)

{ printf(“Cannot open %s\\n”,argv[2]); return(1); }

c=fseek(fp2,0L,2);

while ((c=fgetc(fp1))!=EOF) fputc(c,fp2); fclose(fp1); fclose(fp2); }

3. void main() { int a[10], *p;

for (p=a; p<(a+10); p++) scanf(“%d”,p); for(; p<(a+10);p++) printf(“%d”,*p); }

4.void main() { int I=9,j=0;

char str[3]=”*#”, ch=str[0]; do

{ printf(“%c”,ch);

if(I%5==0) j++;

}while ((ch=str[j])||I--); }

}

二、10分（不必抄题，标明题号，答案另答在答卷纸上） 1．（5分）下面函数声明中有语法错误的是：

A）int f(float (*p)[],int n); B) int f(float *p[], int n); C) int f(float p[], int n); D) int f(float p[ ][ ], int n );

2. (5分) 分析下面的程序有没有错误，如果没有错误，写出程序运行的结果；如果有错误，指出存在的错误，并说明怎样改正。

Void main() {

char str[5][20]={“Follow me ”,”BASIC”,”Great Wall”,”FORTRAN”,”Computer design”}; char *name[5],**p; int I; p=name;

for (I=0; I<5; I++) *p++=str+I;

for (I=0;I<5; I++) if (strchr(name[i], ? ?)) printf(“%s\\n”,name[I]); } 三、（15分）设有算术表达式，其中包含有大括号“{}”、中括号“[ ]”、小括号“（）”，试编写一个递归函数，判断表达式中的括号是否匹配。 四、（15分）设有一个整数序列，有n个整数（0

例如： 输入序列为：5，3，5，7，8，3，5，10，6 则输出为： 序列一 5，3，7，8，10，6 编号一 2，1，4，5，6，3 五、（15分）设有两个有序单链表，一为升序，一为降序。试编写程序，将这两个链表合并为一个有序链表。

数据结构部分

一、完成下列问题（20分） 1、（6分）对下面的关键字集{30，15，21，40，25，26，36，37，10，20}，写出快速排序的每趟结果和最终结果 2、（6分）已知有一个10个顶点的连通图，顶点编号为1至10，其边的关系集合表示为{（1，2），（1，3），（1，8），（2，4），（3，9），（3，10），（5，7），（6，7），（7，8），（8，9）}，试画出该连通图及以顶点①为根的深度优先生成树。 3、（8分）已知二叉树的存储结构为二叉链表，LinkList和BiTree为已定义的指针类型，ListNode为已定义的结点类型，阅读下面算法并回答：

LinkList L=NULL;

void inorder_list (BiTree T){

本文来源：https://www.bwwdw.com/article/6bqp.html