南京师范大学2006年硕士研究生数据结构真题
一.填空
1.设有一个文件有100个记录,按分块查找法查找记录,如分成10块,每块10个记录,用顺序查找法查找索引表和块内记录,则平均查找长度为____.
2.顺序存储和链式存储相比,其主要优点是____.
3.设一棵Huffman树有5个结点,权值分别为4,12,13,15,56,则根节点的权值是____.
4.稀疏矩阵的压缩存储方法是____.
5.如果二叉树中只有度为0和度为2的结点,设根的高度为1,节点总数为h,则此二叉树的最大高度为____.
6.设源串s=\"babababaaba\",模式串p=\"babaa\",按照KMP算法进行模式匹配,当\"S1S2S3S4\"=\"P1P2P3P4\",而S!=P5时,S应与____比较.
7.对表长分别为m,n的有序表进行归并,比较次数最少需要____次.
8.设某二叉树的后序和中序排列为ABCDE,则它的前序排列为____.
9.下列函数的功能是实现两个字符串的比较,试根据字符串比较运算的定义,完善该函数.
int strcmp(chars[],chars[])
{
int i;
for(i=0;s&&t;i++)
if(s!=t)____;
____;
}
10.设有说明int a[10][10],则*(*(a+i)+j)的含义____.
11.C语言中,break语句使用在____语句中.
12.设有说明int a=1234 b=5678,执行下列语句后a=____.
a=a^b;b=b^a;a=a^b
13.设有typedef struct node{int data;struct node *next;}node;则该语句的功能____.
14.设有说明int a=10;则执行语句a+=a-=a*a后,a的值为____.
二.改错
程序功能:输入一行字符,统计单词个数.
#include\"stdio.h\"
main()
{
char string[81]
int i,num,flag=0;
scanf(\"%s\",string);
for(i=0;string!=\'\\n\';i++)
if(string=\'\')flag=0;
if(flag==0)
{
flag=1;num++;
}
printf(\"num=%d\\n\",num);
}
三.读程序写结果
void problem(int n,char x,char y,char z)
{
if(n==1)
printf(\"%c->%c\\n\",x,z)
else
{
problem(n-1,x,z,y);
printf(\"%c->%c\\n\",x,z);
problem(n-1,y,x,z);
}
}
main()
{
int n=3;
problem(n,\"A\",\"B\",\"C\");
}
四.举例说明什么是B树?什么是B+树?它们之间有何区别?(10分)
五.你知道哪些排序算法?试比较它们的性能,并任选其中一种举例说明具体排序过程.(15分)
六.试编写一个实现文件拷贝的完整C程序.源文件名和目标文件名由用户输入.(15分)
七.假设Hash表长为m,Hash函数为H(x),用线性探测法处理冲突,试编写算法,输入一组关键字构建Hash表.(15分)
八.设二叉树采用二叉链表存储,试编写对二叉树进行层次遍历的算法.(15分)
九.试编写算法,建立有向图的邻接表.(15分)
[ 本帖最后由 简聆溪 于 2007-4-26 03:55 PM 编辑 ] |
[复制链接]
收藏
点赞!
反对!
楼主