北京师大教育技术考研数据结构年答案.doc

PAGE 1 2006年北京师范大学 教育技术系研究生入学考试试题参考答案 翻译题：由于近年来该题型已被取消，故复习中不用细看，如有兴趣，请参阅严蔚敏版《数据机构》附录A 简答题 基本运算：插入，删除，遍历等 度量算法效率方法：事前分析法，事后统计法（详请参阅课本第一章1.4） 线性结构中的数据元素之间存在一个对一个的关系；树形结构中中的数据元素之间存在一个对多个的关系（详请参阅课本第一章1.2） （1）循环队列：为充分利用向量空间，克服"假溢出"现象，人们将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列 （2）十字链表：用链表模拟矩阵的行，然后，再构造代表列的链表，将每一行中的元素节点插入到对应的列中去。十字链表的逻辑结构就像是一个围棋盘，而非零元就好像是在棋盘上放的棋子，总共占的空间就是，确定那些线的表头节点和那些棋子代表的非零元节点。最后，我们用一个指针指向这个棋盘，这个指针就代表了这个稀疏矩阵。 （3）线索二叉树：为保存在遍历过程中得到的信息，人们将二叉树节点设置成如下结构 lchild ltag data rtag rchild 以这种节点结构构成的二叉链表作为二叉树的存储结构，叫做线索二叉树。 （4）索引顺序文件：主文件按主关键字有序的文件称索引顺序文件。在索引顺序文件中，可对一组记录建立一个索引项。这种索引表称为稀疏索引。 4. 访问标志数组的作用：便于在算法中区分顶点是否已被访问过。用深度优先搜索可以完成拓扑排序。 5. 哈希表设计过程：要想直接找到需要的记录，必须在记录的存储位置和它的关键字之间建立一确定的对应关系，称这个对应关系f为哈希函数，按这个思想建立的表为哈希表。 哈希函数构造原则：减少冲突、均匀性 构造哈希函数的方法：直接定址、数字分析、平方取中、折叠、除留余数、随机数 6. 串的存储密度=串值所占的存储值/实际分配的存储值 三、 1、正确。（可能有多个最小生成树） 2、错误。（经计算错误） 3、错误。（应为第j行第i列） 4、正确。（参阅第十章） 四、 1、y[n][n] y[n-1][m-1]+y[n-1][m] y[n][m] 2、无向完全图 完全图 3、以自己为先决条件 死循环 死锁 4、 排序方法 平均时间 最还情况 辅助空间 稳定性 希尔排序 O（nlogn） O（nlogn） O（1） 不稳定 冒泡排序 O（n2） O（n2） O（1） 稳定 堆排序 O（nlogn） O（nlogn） O（1） 不稳定 归并排序 O（nlogn） O（nlogn） O（1） 稳定 5、j++ ‘\’ j++ S[i] 五、 1、 2、参阅课本P173-176 Kruskal算法 C代码 　　/* Kruskal.c 　　Copyright (c) 2002, 2006 by ctu_85 　　All Rights Reserved. 　　*/ 　　/* I am sorry to say that the situation of unconnected graph is not concerned */ 　　#include "stdio.h" 　　#define maxver 10 　　#define maxright 100 　　int G[maxver][maxver],record=0,touched[maxver][maxver]; 　　int circle=0; 　　int FindCircle(int,int,int,int); 　　int main() 　　{ 　　int path[maxver][2],used[maxver][maxver]; 　　int i,j,k,t,min=maxright,exsit=0; 　　int v1,v2,num,temp,status=0; 　　restart: 　　printf("Please enter the number of vertex(s) in the graph:\n"); 　　scanf("%d",&num); 　　if(num>maxver||num<0) 　　{ 　　printf("Error!Please reinput!\n"); 　　goto restart; 　　} 　　for(j=0;j<num;j++) 　　for(k=0;k<num;k++) 　　{ 　　if(j==k) 　　{ 　　G[j][k]=maxright; 　　used[j][k]=1; 　　touched[j][k]=0; 　　} 　　else 　　if(j<k) 　　{ 　　re: 　　printf("Please input the r