2017年武汉轻工大学数学与计算机学院810数据结构考研题库
● 摘要
一、填空题
1． 阅读下列程序，指出其功能，并写出空格处应填上的语句。
【答案】
【解析】本题是在哈希表ht[]中插入值为的元素，如该元素已在哈希表中，报告出错。
2． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。
【答案】出度为0
【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最 后一个顶点的出度必定为零。
3． 从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____，_____和_____。B+树适用于组织_____的索引结构，m
阶个关键码。
【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；
4． 在哈希函数
中，P 值最好取_____。
树每个结点至多有_____个儿子，除
根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
5． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
置空链表，然后将原链表结点逐个插入到有序表中
当链表尚未到尾，p 为工作指针
查P 结点在链表中的插入位置，这时q 是工作指针
将P 结点链入链表中
是q 的前驱，u 是下个待插入结点的指针
【答案】（1）（2）（3）（4）（5）
6． 实现字符串拷贝的函数strcpy 为：
【答案】
7． 以下是用类C 语言写山的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶head 为双向循坏链表的头指针。 指针为top , P , t 为辅助指针，试填充算法中的空格，使算法完整。
void leafchain（BiTree Abt）
{p={BiTree）malloc （sizeof （BiTNode ））; If （!p ）{print£（“OVERFLOW\n”; exit （1）; } head=p; top=0;
if （bt ）
{top++; stack[top]=bt; while （top ）
{t=stack[top]; top--;
if （it->Lchild && !t->Rchild）{ （1） ; （2） ; （3） ; } else {if（ （4） ）{top++; stack[top]= （5） ; } if （ （6） ）{top++;
stack[top]= （5） ; }
} }
（8） ; （9） ; } } 【答案】
p->Rchild=t:t->Lchild=p:p=t: t->Rchild!=null:t->Rchild: p->Rchild=head:head->Lchild=p
8． 完善算法：求KMP 算法.next 数组。
t->Lchild!=null:
t->Lchild:
END ； 【答案】
9． 栈是_____的线性表，其运算遵循_____的原则。
；后进先出 【答案】操作受限（或限定仅在表尾进行插入和删除操作）
10．如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。
【答案】序查找效率一样为
11．设数组
数组中任一元素
均占内存48个二进制位，从首地址2000开始
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺
连续存放在主内存里，主内存字长为16位，那么
（1）存放该数组至少需要的单元数是_____；
（2）存放数组的第8列的所有元素至少需要的单元数_____； （3）数组按列存储时，元素【答案】270; 27; 2204 【解析】数组的元素个数为需要
第8列有9个元素，共占个单元。按列存储时，
因为每个元素占内存48个二进制位，即6个字节。故总
个单元数。
个字节，因此至少需要的起始地址为
个单元数。由题知，每个元素占3
个字节，因为主内存字长为16位，即2个字节，所以至少需要
的起始地址是_____。
相关内容
相关标签