2017年辽宁工业大学电子与信息工程学院917数据结构考研题库
● 摘要
一、填空题
1． 从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____，_____和_____。B+树适用于组织_____的索引结构，m
阶个关键码。
【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；
2． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
3． 以下是用类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:
第 2 页，共 49 页
树每个结点至多有_____个儿子，除
根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____
t->Lchild!=null: t->Lchild:
p->Rchild=head:head->Lchild=p
4． 建立索引文件的目的是_____。
【答案】提高查找速度
5． 有向图G=（V ，E ）, 其中V （G ）=[0, 1，2，3，4, 5}, 用
【答案】50; 4
6． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。
【答案】
【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。
7． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
【答案】（1）（2）
链表未到尾就一直进行
将当前结点作为头结点后的第一元素结点插入
8． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。
【答案】要加“虚结点”。
设编号为
和
的结点在顺序存储中的下标为
和
。
9． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关, 即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
，
则结点
和
在同一层上的条件是
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
第 3 页，共 49 页
10．在循环队列中，队列长度为n ，存储位置从0到，
【答案】
编号，以rear 指示实际的队尾元素，现
要在此队列中插入一个新元素，新元素的位置是（ ）。
二、算法设计题
11．已知无向图采用邻接表存储方式，试写出删除边（i ，j ）的算法。
【答案】算法如下：
//在用邻接表方式存储的无向图g 中，刪除边（i , j ）
//删顶点i 的边结点（i , j ）pre 是前驱指针
释
放空间
//
//释
放空间
//沿链表继续査找
12．已知两个线性表A , B 均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设，并同样以元素值的递增有序的单链表形计算法求出A 与B 的交集C ，要求C 另开辟存储空间。式存储。
【答案】算法如下：
第 4 页，共 49 页
沿链表继续查找
//删顶点j 的边结点（j , i ）
相关内容
相关标签