数据结构与历年真题

北京师范大学08年考研程序设计与数据结构试题

考研_考试大 [ 2008/11/17 ] 来源：北京师范大学

一、简答题（20分）

1.数据类型和抽象数据类型的含义 2.算法的特性与算法的时间复杂度

3.快速排序方法最好和最坏的情况是什么？简要分析说明 4.栈、队列的共同点与不同点，说明其属于线形表的原因 二、方法选择（20分）

1.一棵二叉排序树中各结点不相同，欲得到一个由大到小的结点值递减序列，你认为采用什么方法能得到要求的结果？

2.设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序，基数排序，快速排序，堆排序，插入排序），那种方法最好，为什么？

三、（40分，每题8分）

1.已知一个循环单链表la，av是可利用栈的头指针，请用３个赋值语句，完成将整个循环链表释放的功能。（即将表整个归还到可用的栈空间） 2.给出求N阶hanoi塔的函数定义如下：Hanoi （ int n，char x，char y ，char z ）

{ if （ n= =1） move （ x ，1，z） Else{ hanoi（ n-1， x，z，y）； Move（x，n，z）；

Hanoi（n-1，y，x，z）； } }

写出执行hanoi（3，a，b，c）时递归函数的实在参变量变化，以及move的搬运过程。

3.已知关键字序列为：（75，33，52，41，12，88，66，27），哈希表长为10，哈希函数为：H（K）＝KMOD7，解决冲突用线性探测再散列法，要求构造哈希表，求出等概率下查找成功查找长度。

4.已知一棵二叉树，中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。 5.给定权值｛8，12，4，5，26，16，9｝，构造一个哈夫曼树，并计算其带权路径长度。

四、编写程序（15分）

建立线形表，（a1，a2，a3…。，an）的单链表存储，并实现其就地逆置为（an， ，an-1…a2.，a1）。 五、编写程序（10分）

在中序线索树中，要找出Ｘ结点的前驱结点，请写出相关函数定义。 Ltag Lc Data Rtag Rc 六、编写算法（20分）

已知有N个结点的无向图，采用邻接表结构存储，要求对每个连通子图中一个生成树中的各条边逐层输出，边的输出格式为（ki，kj）。 七、编写算法（25分）

1.写出建立二叉树，二叉链表存储结构的算法。（10分）

2.已知二叉树采用二叉链表方式存放，要求对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，左孩子编号小于右孩子编号。给出在二叉树中结点的数据域部分填写，实现如上要求编号的非递归算法。（10分）

3.已知二叉树采用二叉链表方式存放，给出判定它是否为一。

大连理工大学2008年考研数据结构试题

考研_考试大 [ 2008/11/3 ] 来源：考研教育网

一、选择题

1. 线性表的 ———— 运算中，顺序存储结构比例链式存储结构好。 A. 插入 B .删除

C .按号查找

D .按元素值查找

2.此程序的复杂度为 ————

for（int i=0 ； i

3 .在待排数据已基本有序的情况下， ———— 效率最高。 A . 直接选择排序 B . 直接插入排序 C . 快速排序 D . 归并排序

4 . n 个英文单词，每个单词长度基本相等，为 m ，当 n>>50，m<5 时，时间复杂度最佳的为 ———— ： A . 快速排序 B .归并排序 C .基数排序 D.直接插入排序

5 .顺序查找长度为 n 的顺序表，查找成功的平均检索长度为 ———— ： A . n B . n/2

C.（n-1）/2 D . （n+1）/2

6 .一颗二叉树，头序序列为 ABCDEFG ，中序序列为 CBDAEGF ，后序为 ————

A . CDBGFEA B . CDBFGEA C . CDBAGFE D . BCDAGFE

7 .一颗度为 3 的树，度为 3 的节点为三个，度为 2 的节点为 1 个，度为 1 的节点 1 个，度为 0 的节点 ———— 个（考试大）。 A . 6 B . 7 C . 8 D . 9

8 .m 阶 B— 树中，某一节点插入一个新关键字引起破裂，则该节点原有关键字 ———— 个。 A.|—m/2—| B.|—m/2—|-1 C.m D.m-1

E.|—m/2—| F.|—m/2—|-1

9 .两个长度为 n 的递增有序表，合并成一个长度为 2n 的递增有序表，最少需要进行关键字比较 ———— 次。 A . 1 B . n-1 C . n D . 2n

10 .有向图 G， n 个顶点，邻接矩阵存储于二维数组中，顶点 i 的度为 ———— .

A.（i=0 n-1）∑A[i][j] B.（j=0 n-1）∑A[i][j]

C.（i=0 n-1）∑A[i][j]+（j=0 n-1）∑A[i][j] D.（j=0 n-1）∑（A[i][j]+A[j][i]） 二、问答题

1. （ 6 ） n 阶对称阵（ aij ） n × n ，采用压缩存储存放于一维数组 F[m] 中，从 F[0] 开始存储，给出矩阵的压缩存储方式及任一矩阵元素 aij （ 0<=i，j<=n-1 ）的地址计算公式，并求算 m . 2. （ 5 ）顺序队列如何解决假溢出问题。 3. （ 8 ）已知一组关键字（ 10 ， 26 ， 14 ， 25 ， 17 ， 36 ， 37 ， 44 ， 27 ， 34 ， 60 ）设哈希函数 H （ x ） =x ，表长 m=13 ，请写出用线性探测法处理冲突构造所得的哈希表。并求出在等概率情况下，查找成功时的平均检索长度。

4. （ 6 ）给定一个由 n 个关键字不同的记录构成的序列，你能否用比 2n-3 少的比较次数找出 n 个元素中的最大值和最小值？如果有，请描述你的方法。最快需要多少次比较？（无需写算法） 三 、用类 C 语言完成设计

1.（ 15 ）什么是堆？设计算法判定给定的存于数组 r[] 中的 n 个数据是

否为堆。

2.（ 15 ）设 u 、 v 是有向图的两个顶点，设计算法判读有向图中是否存在从顶点 u 到 v 的长度为 k 的简单路径。要求给出图的存储形式及其类型定义。

3. （ 10 ）设二叉树以二叉链表形式存放。一颗二叉树的繁茂程度定义为各层节点数的最大值与树的高度的乘积。试设计一个高效算法，求二叉树的繁茂程度。

2007年电子科技大学计算机专业基础试题

考研_考试大 [ 2007/12/9 ] 保存本文 第一部分 数据结构 （共 75分） 一、单项选择题（每题 2分，共10分）

1．表头表尾均为空表的广义表是（ ）。

① （） ② （（）） ③ （（），（）） ④ （（（）））

2. 对 下列 4个序列,以第一个关键字为基础进行用快速排序算法进行排序，在第一趟过程中移动记录次数最多的是 ( ) ① 92，96，100，110，42，35，30，88 ② 92，96，88，42，30，35，110，100 ③ 100，96，92，35，30，110，88，42 ④ 42，30，35，92，100，96，88，110

3． 实现图的广度优先搜索算法时，使用的数据结构是 （ ） ① 栈 ② 队列

③ 十字链表 ④ 三元组

4．在有向图G的邻接矩阵中，顶点Vi 的度是 （ ）。 ① 邻接矩阵中第 i行元素之和 ② 邻接矩阵中第 i列元素之和

③ 邻接矩阵中第 i行和第i列元素之和

④ 邻接矩阵中第 i行元素之和与第i列元素之和的最大值 5．能有效缩短关键路径长度的方法是（ ） ① 缩短任意一个活动的持续时间

② 缩短关键路径上任意一个关键活动的持续时间

③ 缩短多条关键路径上共有的任意一个关键活动的持续时间 ④ 缩短所有关键路径上共有的任意一个关键活动的持续时间

二、填空题（每空 2分，共 8 分）

1． 由一棵二叉树的后序序列和 可唯一确定这棵二叉树。 2． 二叉树结点数 n与边数e的关系为 。

3． 在各种查找算法中，平均查找长度与关键字个数 n无关的方法是 。 4． 若希望得到树高较矮的生成树，则采用图的 遍历算法。

三、判断题（用√表示对，用×表示错。每题 2分，共 12 分）

1． 循环队列中不存在队列满的问题。（ ）

2． 将一个新结点插入到二叉排序树中，该结点一定成为叶结点。（ ） 3． 用单链表示的有序表可以使用折半查找方法来提高查找速度。（ ） 4． 若有向图中每个顶点的入度和出度均为 1，则该有向图必有回路。（ ） 5． 已知二叉排序树的先序序列，能唯一确定该二叉排序树。（ ）

6． 交换完全二叉树所有结点的左右子树，得到的二叉树仍是完全二叉树。（ ）

四、简答题（每题 6分，共 30 分）

1．若一个有向图的邻接矩阵中主对角线以下的元素均为0，则该图一定不存在回路。该说法是否正确？为什么？

2． 在完全二叉树中，设结点数为 n，

（ 1）如何断定该完全二叉树中度为1的结点数n1?

（ 2）给定结点x的编号m，又如何根据该编号断定x是否为叶结点？ 3． 当查找表有既能较快查找又能适应动态变化的需求时，选用什么查找方法最适合？并简述其理由。

4． 在某个通信系统中，报文的字符集为 a,b,c,d,e,f,g,h八种，其出现频率分别为6，28,8,9,13,22,4和1,试为各字符设计二进制编码，使得报文编码长度最短。给出各字符的二进制编码和报文编码长度。

5． 设 L是不带头结点单链表的头指针，P是指向链表中某个结点的指针，该结点既不是第一个结点，也不是最后一个结点，S是指向待插入新结点的指针，用下面 ① -- ⑦选项完成 A、B功能。

A. 在P所指结点前面插入 S所指结点的语句序列是（ ）； B. 在第一个结点前面插入 S所指结点的语句序列是（ ）； ① P↑.next ：=S； ② Q:= P； ③ L:= S； ④ P:= L；

⑤ WHILE ( P↑.next <> Q ) DO P：= P↑.next； ⑥ S↑.next：= P↑.next； ⑦ S↑.next：= L↑.next；

五、算法题（共 15 分）

1． 设p,q分别指向两个不带头结点的单循环链表中的某个结点，试编写一个算法，用O(1)时间将这两个单链表合并为一个，并令p指向p和q两者data域值较小的结点。（5分） PROC xyz( p, q )；

{ p,q分别指向两个不带头结点的单循环链表中的某个结点,结点结构为数据域data和指针域next} ENDP；

2． 设二叉树采用二叉链表存储，结点结构为 lchild、data和rchild，试编写输出二叉树中从根结点到每个叶结点的路径的算法。设二叉树最长路径结点个数小于m，可以使用队列S[1：m]，初始时S.rear=S.front=1。（10分） PROC RootToLeaf(bt：bitreptr )；

{ bt为二叉树根指针，S[1：m]为队列, 初始时S.rear=S.front=1}

ENDP；{ RootToLeaf }

? 南京林业大学2003年C程序设计考研试题 考研 推荐给好友 收藏本页 2006/11/21 保存本文 一. 选择题(40分) 1..当c的值不为0时，在下列选项中能正确将c的值赋给变量a、b的是______ A c=b=a； B (a=c)‖(b=c)； C (a=c)&&(b=c)； D a=c=b； 2.在C语言中，不正 确的int类型的常数是________ A 32768 B 0 C 037 D 0xAF 3.以下程序的输出结果是________ main( ) { int a= -1，b=1，k； if((++a<0)&& ! (b-- <=0)) printf(\，a，b)； else printf(\，b，a)；} A -1 1 B 0 1 C 1 0 D 0 0 4.在C语言类型中,int ,char, short等类型的长度是_________ A.固定的 B.由用户自己定义 C.任意的 D.与机器字长有关 5.设a=1,b=2,c=3,d=4,则表达式:a A 4 B 3 C 2 D 1 6. 下列说法错误的是______________ A.结构体变量可以被整体赋值. B. 可以取结构体变量的地址 C. 可以取结构体变量成员的地址 D. 结构体类型的成员可以定义成该结构体类型的指针类型 7.设有如下定义：int x=l，y=-1；，则语句：printf(\，(x--&++y))；的输出结果是____ A 1 B 0 C -1 D 2 8. . 设有程序段: t=6;a=7;b=8; if(a=b)t=a;,这段程序执行后,t的结果是______ A. 6 B.7 C.8 D.0 9.下列描述中不正确的是________ A)字符型数组中可以存放字符串 B)可以对字符型数组进行整体输入、输出 C)可以对整型数组进行整体输入、输出 D)不能在赋值语句中通过赋值运算符\对字符型数组进行整体赋值 10.若a为二维数组,它有m列,则a[i][j]在数组中的位置是_________ A. i*m+j B. j*m+i C. i*m+j-1 D. i*m+j+1 11. 下列语句中符合C语言语法的赋值语句是__________ A a=7+b+c=a+7; B a=7+b++=a+7; C ) a=7+b,b++,a+7 D a=7+b,c=a+7; 12. 若a为二维数组,则a[1][3]等价于_________ A. *((a+1)+3) B. *(a[1]+3) C. (*(a+1)+3) D. &a[1]+3 13.下面程序段不是死循环的是_____________ A. int j=100; while(1){j=j0+1;if(j>100)break;} B. for( ; ; ); C. int k=0; do{ ++k;}while(k>=0); D. int s=36; while(s);--s; 14.下列表达式中,错误的是______. A.2>1 ? a:b B.i+++j C.4.0%2.0 D.x*=y+8 15.a,b为整数且b!=0,则表达式(a/b)*b+a%b的值为______的值. A.a B.b C.a被b除的余数部分 Da被b除商的整数部分 16.若以数组元素作为函数的实参,则实参向形参传送的是______. A.数组元素的地址 B.数组元素的值 C.数组的首地址 B.数组名 17.设有如下的共用体定义: union data {int i; long b; float f;}a; 则a所占的内存单元为______个字节. A.4 B.6 C.8 D.10 18.语句:printf(\，(a=2)&&(b= -2)；的输出结果是________ A 无输出 B 结果不确定 C -1 D 1 19.下列选项中不是C语言main函数正确表达形式的是________？ A.main(int argc,char *argv[]); B.main(ac,av) int ac;char **av; B.main(c,v) int c;char *v[]; D.main(argc,argv) int argc;char argv[]; 20.执行for(j=1;j++<4;);语句后变量j的值是_________ A. 3 B. 4 C. 5 D.不定 二.填充(20分) 1. C语言的数据类型中,构造类型包括:数组,__________和__________. 2.设x,y,z,t均为int型变量,则执行以下语句后,t的值为_________ x=y=z=1; t=++x||++y&&++z; 3.C语言的运算符要确定的两个方面分别是__________和__________. 4. 在函数内使用static是_________,在函数外使用static是________。 5.对于语句:scanf(\若输入123456,则a和b的值分别为_______和_______. 6.?设有二维数组 int?a[2][2],*p;,则a[I][j]三种其他表示是______________, ____________,___________。 7.字符串的长度是_________________，它的存储空间大小是_______。 8.静态变量赋初值是________赋值，动态变量赋初值是___________赋值。 9.链表中每个结点至少应包括二个部分,它们是__________和__________. 10.用数组名作函数参数时,形参和实参的结合是采用__________,?因为数组名是 数组的__________. 三.程序分析题(20分) 1. 阅读下面程序，给出输出结果。 main( ) { int i, j, k; for(i=1; i<10; i++) { printf(“\\n”); if(i<=5) {for(j=1; j<=i; j++) { for(k=1;k<=5-i;k++) printf(“ ”); printf(“* “); } else for (j=1; j<=10-i;j++) {for(k=1;k<=i-5;k++) printf(“ ”); printf(“* ”);}}} 2. 阅读下面程序，指出函数所实现的功能。 void ins(char s[ ], int start, char t[ ]) { int m, n,i,k; n=0;m=0; for(i=0;s[i]!=?\\0?;i++) m++; for(i=0;t[i]!=?\\0?;i++) n++; for(k=1 ; k for(k=start;k s[k]=t[k-start]; s[m+n]=?\\0?; } 3. 阅读下面程序，指出下面程序所完成的功能 void st(char *a [ ],int n ) { int i,j,k; char *m; for(i=1; i { m=a[i]; k=i; for (j=i+1; j<=n; j++) if (strcmp(a[k],a[j])>0), k=j;) m=a[i]; a[i]=a[k]; a[k]=m; } for(i=1; i<=n; i++) printf(“%s”, a[i]);} 4.分析以下程序: #include “string.h”; main() {char c,string[81]; int i,a=0,b=0; gets(string); for(i=0;(c=string[i])!=?\\0?;i++) if (c==? ?)a=0; else if (a==0) {a=1;b++;} printf(\ } 该程序的作用是_________________.若输入:a b c,则程序运行后,?输出结果为______, 且c的值为______,a的值为______. 5. 阅读下面程序，指出函数所实现的功能。 void lnsort(int L[ ],int n) {int i,j; for( i=2;i<=n;i++) {L[0]=L[i]; j=i-1; while(L[0] {L[j+1]=L[j]; j--; } L[j+1]=L[0]; } } 四.完成下列程序(20分) 1. 下面程序是查找学生的成绩，完成该程序。 main( ) { void search (float (*p) [3], int i ); float score [4][3]={{75,78,82},{66,72,77},{85,90,81},{74,89,68}}; while (1) { scanf (“%d” &i ); if(___1____)break; search(_____2_______);}} void search (float (*p)[3],int i ) { int k; print (“The score of No %d are \\n”,i ); for(_____3_______) printf( “%5.2f”,_____4_________);} 2. 已知两个线性表的元素按非递减排列，合并两表得到一新表，仍然是按 非递减排列，两个线性表以-1为结束标志。以函数来完成该操作，函数如下， 完成所缺语句。

void LL(int la[ ], int lb[ ], int lc[ ] ) // la,lb是已知二表// { int pa, pb, pc; pa=0 ; pb=0;pc=0; if (la[pa] else {________6__________} while(_______7___________) { if (la[pa]<=lb[pb]) { lc[pc]=la[pa]; __8___; __9___;} else {____10_________}} while (_____11________) ____12___; while (____13________) ____14______; } 3.在一数组里装数取数，从数组中所装的数的最后一项的下一个空单元装数， 从数组中所装的数的最後一个取数，取数后该单元成空单元，如果取数已到数 组空，-1表示未取到，以下是对数组的一次取数操作，函数值是所取的值，完成该 函数。 define MAX 100 int pop ( int s[ ] ,int top ) { if (___15______) return (-1); top = ___16________; return (____17_______) ;} 4.在 n 行 n 列的矩阵中,每行都有最大的数,本程序求这 n 个最大数中的最小一个 [程序1.2] #include〈stdio.h〉 #define N 100 int a[N][N]; void main() { int row ,col ,max ,min ,n; /*输入合法 n (〈100 〉,和输入 n×n 个整数到数组 a 的代码略*/ for ( row = 0;row < n;row++) { for ( max = a[row][0],col = l ;col < n;col++) if (__18_) max = a[row][col]; if (__19__) min = max; else if(__20__) min = max; } printf (\ } 五. 编程题(50分) 1. 有函数f(x)=cos(x)可展开成：f(0)+f?(0)x/1!+f”(0)x /2!+… 编写函数程序求cos(x)，使误差小于0.0000001。 2. 有一个链表，输出所有结点的数值，确定该链表的长度，并将链表的头结点 与尾结点连接.编写完成这样操作的函数。这里的结点定义为 typedef struct node {int data ; struct node * next ; } Node ; 3.将一个整数a左循环移位n次,求位移后的这个数.写出子函数 4.写函数,将一个十进制数转换成一个十六进制数,并输出. 5. 如果有n个棋子，甲、乙两方轮流取棋子,每方至少取一个棋子,最多取m个棋子 谁最后取剩下的一个棋子,谁就输,如果甲方先取,请给出甲方赢的算法.(写出函数) 中国人民公安大学2005年硕士研究生入学考试

试题(数据结构)

请将所有答案标明题号，写在答题本上，试题纸上请勿答题。严禁在答题纸密 封线以外留下姓名、考号等任何标记，否则该卷无效。 一、 名词解释(每小题5分，共30分)

1. 描述线性表中三个概念的区别：头指针、头结点、首元结点(第1个元素结点 )。 2. 数据结构 3. 二叉排序树 4. 关键路径 5. 稀疏矩阵

6. 连通图

二、 单项/多项选择题(每空3分，共30分)

1. 具有N个结点的二叉树的二叉链表结构中，指针域为NULL的数目应为( )； A) N B) 2N

C) N+1； D) 2N+1

2. 假定有T1、T2、T3、T4、T5五个元素进栈，进栈次序为T1T2T3T4T5，不可能 的出栈序列有( )；

A)T1T2T3T4T5 B)T5T4T3T2T1 C)T1T2T5T3T4 D)T3T2T4T5 T1

E)T3T5T2T4 T1 F)T2T4 T3T5 T1

3. 表达式(15-3)*6/3*(20+6)的逆波兰式，正确的是( )； A)15 3 6 3 20 6-*/*+ B)15 3-6 *3/20 6+* C)15 3 - 6 3 20 6+*/* D)15 3-6 3*20 6+*/

4. 下列各函数是按照增长率由大至小的顺序排列的是( )；

A) B) C) D)

5. 已知L是带表头结点的单链表，其P结点既不是首结点(第一结点)，也不是尾 结点： 1) 删除P结点的直接后继结点的语句序列是( )；

2) 删除P结点的语句序列是( )； 3) 删除首结点的语句序列是( )； 4) 删除尾结点的语句序列是( )； A) P=P→next ; B) P→next=P ;

C) P→next=P→next→next ; D) P=P→next→next ;

E) while P !=NULL { P=P→next ;}

F) while P→next !=NULL { P=P→next ;} G) while P→next !=Q {P=P→next ;} H) while P→next→next !=Q { P=P→next ;} I) Q=NULL ; J) Q=P ;

K) Q=P→next ; L) P=L ;

M) L=L→next ;

N) free(Q);

6. N个结点的集合，利用二叉排序树查找方法的平均查找长度(ASL)的计算公式 为( )； A)N+1 B)log2N

C)(N+1)/2 D)1+4 log2N

7. 对下列关键字序列按照起泡排序算法进行排序，则两趟排序后的结果可能为 ( )。

(Kay, Eva, Amy, Roy, Dot, Jon, Kim, Boy) A)(Amy, Eva, Dot, Jon, Kay, Boy, Kim, Roy) B)(Amy, Boy, Dot, Eva, Jon, Kay, Kim, Roy) C)(Eva, Amy, Kay, Dot, Jon, Kim, Boy, Roy)

D)(Eva, Amy, Dot, Roy, Jon, Boy, Kim, Kay) 三、 填空题(每题2分，共20分)

1. 在顺序存储结构的线性表中，插入或删除一个元素需要平均移动 【1】 元 素，具体移动元素个数与 【2】 有关。

2. 假设二维数组A[6][8]，每个元素用相邻的4个字节存储，存储器按字节编址 ，已知A的开始存储位置为100，则数组的存储容量为【 3】 字节；按列优先顺序存储 的元素A[2][5]的第一个字节的地址为 【4】 。

3. 一棵深度为5，18个结点的完全二叉树，编号为10的结点的右儿子的编号 【 5】 ，其双亲结点的编号为 【6】 。

4. 在一棵有14个结点的完全二叉树中，所含叶子结点的数目为 【7】 个。

5. 对稀疏矩阵的压缩存储，一般包括三元组表和 【8】 两种基本方法。如图 (A)所示的稀疏矩阵，试给出它所对应的三元组线性表 【9】 ； 6. 如图(B)所示的有向图，该图有 【10】 个强连通分量。 四、 简答题(每题8分，共40分)

1. 对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元 素的初始序列。现假设n=7，试问在最好的情况下需进行多少次比较？请说明理由。 2. 试证明：具有n个结点的二叉树的最小深度为 。 3. 在串操作中，执行以下函数会产生怎样的输出结果？ void demonstrate(){

StrAssign(s, ?THIS IS A BOOK?);

Replace(s, SubString(s, 3, 7), ?ESE ARE?); StrAssign(t, Concat(s, ?S?));

StrAssign(u, ?XYXYXYXYXYXY?); StrAssign(v, SubString(u, 6, 3));

StrAssign(w, ?W?);

printf(?t=?, t, ?v=?, v, ?u=?, Replace(u, v, w));

} //demonstrate

4. 判别下面的一个序列是否为堆。如果不是，则把它调整为堆，画出生成堆的 调整过程(要求记录交换次数最少，且堆顶元素为最小值)。 (12，70，48，86，24，56，30，92，65，38) 5. 试列出如图(C)中全部可能的拓扑有序序列。 图 (C)

五、 综合设计题(每题15分，共30分)

1. 试利用Dijkstra算法求图(D)中从顶点a到其他各顶点间的最短路径，写出执 行算法过程中各步的状态。

图 (D)

2. 假设用于通信的电文只使用A，B，C，D，E，F这六个字母组成，字母在电文 中出现的频率依次为4，2，6，8，3，2。按照要求完成如下任务：

1)试为这6个字母设计哈夫曼编码和等长二进制编码方案，给出两种编码的对照 表。 2)求出这两种编码的带权路径长度WPL，比较两种方案的优缺点。 3)给出哈夫曼树的逻辑结构。 转贴于：考研_考试大

? 历年真题:1997-2008年数学真题及答案 http://www.examda.com/Kaoyan/math/zhenti/20071219/171713265.html

? 历年真题：1997-2007年数学真题及答案（部分） 序列 年份 试题 2008年全国硕士研究生入学考试数学(1)试题 1 2008年 2008年全国硕士研究生入学考试数学(2)试题 2008年全国硕士研究生入学考试数学(3)试题 2008年全国硕士研究生入学考试数学(4)试题 2007年全国硕士研究生入学考试数学(1)试卷 2 2007 2007年全国硕士研究生入学考试数学(2)试卷 2007年全国硕士研究生入学考试数学(3)试卷 2007年全国硕士研究生入学考试数学(4)试卷 2006年全国硕士研究生入学考试数学(1)试卷 3 2006 2006年全国硕士研究生入学考试数学(2)试卷 2006年全国硕士研究生入学考试数学(3)试卷 2006年全国硕士研究生入学考试数学(4)试卷 2005年全国硕士研究生入学考试数学(1)试卷 4 2005 2005年全国硕士研究生入学考试数学(2)试卷 2005年全国硕士研究生入学考试数学(3)试卷 2005年全国硕士研究生入学考试数学(4)试卷 2002年全国硕士研究生入学考试数学(1)试卷 2002年全国硕士研究生入学考试数学(2)试卷 5 2002 2002年全国硕士研究生入学考试数学(3)试卷 2002年全国硕士研究生入学考试数学(4)试卷 2001年全国硕士研究生入学考试数学(1)试卷 2001年全国硕士研究生入学考试数学(2)试卷 6 2001 2001年全国硕士研究生入学考试数学(3)试卷 2001年全国硕士研究生入学考试数学(4)试卷 2000年全国硕士研究生入学考试数学(1)试卷 7 2000 2000年全国硕士研究生入学考试数学(2)试卷 2000年全国硕士研究生入学考试数学(3)试卷 2000年全国硕士研究生入学考试数学(4)试卷 1999年全国硕士研究生入学考试数学(1)试卷 8 1999 1999年全国硕士研究生入学考试数学(2)试卷 1999年全国硕士研究生入学考试数学(3)试卷 1999年全国硕士研究生入学考试数学(4)试卷 1998年全国硕士研究生入学考试数学(1)试卷 9 1998 1998年全国硕士研究生入学考试数学(2)试卷 1998年全国硕士研究生入学考试数学(3)试卷 1997年全国硕士研究生入学考试数学(1)试卷 1997年全国硕士研究生入学考试数学(2)试卷 10 1997 1997年全国硕士研究生入学考试数学(3)试卷 1997年全国硕士研究生入学考试数学(4)试卷

? 历年真题：1990-2007年英语真题及答案汇总 考研 推荐给好友 收藏本页 2007/12/19 保存本文 为了帮助考生更好地复习，考试大2008考研站特别搜集整理了1990年-2007年的考研英语试题及参考答案，供考生查询使用。由于各方面情况的不断调整与变化，考试大所提供的所有考试信息仅供参考，敬请考生以权威部门公布的正式信息为准。 历年真题：1990-2007年英语真题及答案 序列 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 试题 2007年硕士研究生入学统一考试英语试题 2006年硕士研究生入学统一考试英语试题 2005年全国硕士研究生入学考试英语试题 2004年全国硕士研究生入学考试英语试题 2003年全国硕士研究生入学考试英语试题 2002年全国硕士研究生入学考试英语试题 2001年全国硕士研究生入学考试英语试题 2000年全国硕士研究生入学考试英语试题 1999年全国硕士研究生入学考试英语试题 1988年全国硕士研究生入学考试英语试题 1997年全国硕士研究生入学考试英语试题 1996年全国硕士研究生入学考试英语试题 1995年全国硕士研究生入学考试英语试题 1994年全国硕士研究生入学考试英语试题 1993年全国硕士研究生入学考试英语试题 1992年全国硕士研究生入学考试英语试题 1991年全国硕士研究生入学考试英语试题 1990年全国硕士研究生入学考试英语试题 ? 历年真题：1994-2008年政治真题及答案 考研 推荐给好友 收藏本页 2007/12/19 保存本文 为了帮助考生更好地复习，考试大2008考研站特别搜集整理了1994年-2008年的考研政治试题及参考答案，供考生查询使用。由于各方面情况的不断调整与变化，考试大所提供的考试信息仅供参考，敬请考生以权威部门公布的正式信息为准。 历年真题：1994-2008年政治真题及答案 序列 1 年份 试题 2008 2008年全国硕士研究生入学考试政治试题及参考答案 2007年全国硕士研究生入学考试政治试题及参考答案 2006年全国硕士研究生入学考试政治试题及参考答案 2005年全国硕士研究生入学考试政治试题及参考答案 2004年全国硕士研究生入学考试政治试题及参考答案 2003年全国硕士研究生入学考试政治试题及参考答案 2002年全国硕士研究生入学考试政治试题及答案(文科) 2002年全国硕士研究生入学考试政治试题及答案(理科) 2001年全国硕士研究生入学考试政治试题及答案(文科) 2001年全国硕士研究生入学考试政治试题及答案(理科) 2000年全国硕士研究生入学考试政治试题及答案(文科) 2000年全国硕士研究生入学考试政治试题及答案(理科) 1999年全国硕士研究生入学考试政治试题及答案(文科) 1999年全国硕士研究生入学考试政治试题及答案(理科) 1998年全国硕士研究生入学考试政治试题及答案(文科) 1998年全国硕士研究生入学考试政治试题及答案(理科) 1997年全国硕士研究生入学考试政治试题及答案(理科) 1996年全国硕士研究生入学考试政治试题及答案(文科) 2 2007 3 2006 4 2005 5 2004 6 2003 7 2002 8 2001 9 2000 10 1999 11 1998 12 1997 13 1996 1996年全国硕士研究生入学考试政治试题及答案(理科) 1995年全国硕士研究生入学考试政治试题及答案(文科) 1995年全国硕士研究生入学考试政治试题及答案(理科) 1994年全国硕士研究生入学考试政治试题及答案(文科) 1994年全国硕士研究生入学考试政治试题及答案(理科) 14 1995 15 1994

本文来源：https://www.bwwdw.com/article/5rev.html