《2017年南京财经大学信息工程学院826数据结构考研强化模拟题.doc》由会员分享，可在线阅读，更多相关《2017年南京财经大学信息工程学院826数据结构考研强化模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年南京财经大学信息工程学院826数据结构考研强化模拟题一、算法设计题1 在一棵以二叉链表表示的二叉树上，试写出按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目的算法。【答案】算法如下：int Level（BiTree bt） /层次遍历二叉树，并统计度为1的结点的个数 int num=C; /num统计度为1的结点的个数if （bt ）Queuelnit（Q ）; Queueln（Q , bt ）; /Q是以二叉树结点指针为元素德 队列 while （!QueueEmpty （Q ）p=Queueout（Q ）; printf （p-data）; /出队访问结点 /非空右子女入
2、队 /返回度为1的结点的个数 2 有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。【答案】算法如下： 3 设计算法将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中（注：按层从上到下，由左到右）。【答案】算法如下：typedef struc DiTree data ; int num ; tnode / num 是结点在一维数组中的编号tnodc Qmaxsize; /队列，容量足够大void BiToSeqtBiTree t, ELemType seq/本算法将二叉树的二叉链表存储结构转换为顺序存储结构se
3、q int front=0, rear:=0; tnode q; Bitree p; if （!t ） exit （0）;for （i=1; idata; /存入顺序存储结构 if （p-lchild）tq.data=p-lchild; tq.num=2*i; Q+rear/左子女入队 if （p-rchild）tq.data=p-rchild; tq.num=2*i+1; Q+rear=tq; /右子女入队 4 已知L 为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符、数字字符或其他字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个
4、表中只含同一类字符（要求用最少的时间和最少的空间）。【答案】算法如下： 5 给出以十字链表作存储结构，建立图的算法，输入（i ，j ，v ） ，其中I , j 为顶点号，v 为权值。【答案】算法如下： /建立有向图的十字链表存储结构/假定权值为整型 /建立顶点向量 /当输入i , j 、v 之一为0时，结朿算法运行 /申请结点/弧结点中杈值域 /算法结束 6 已知一棵高度为K 具有n 个结点的二叉树，按顺序方式存储。（1）编写用前序遍历树中每个结点的非递归算法；（2）编写将树中最大序号叶结点的祖先结点全部打印输出的算法。 【答案】（1）算法如下: /全局变量void PreOrder（Elem
5、Type bt, i ）/递归遍历以顺序方式存储的二叉树bt , i 是根结点下标初始调用时为1） int top=0, s; /top是栈s 的栈顶指针, 栈容置足够大 while （i0） while（i0） i=stop-）; /取出栈顶元素 /while /结朿PreOrder （2）算法如下：void Ancesstor（ElemType bt（l ） /打印最大序号叶结点的全部祖先 c=m;While （btc=0 c-; /找最大序号叶结点，该结点存储时在最后 f=c/2;/c的双亲结点fwhile （f!=0） /从结点c 的双亲结点直到根结点，路径上所有结点均为祖先结点 pr
6、intf（btf; f=f/2; /逆序输出，最老的祖先最后输出 /结朿 7 写出算法，求出中序线索二叉树中给定值为X 的结点之后继结点，返回该后继结点的指针。线索树中结点结构为：（ltag ，lc ，data ，rC ，rtag ）。其中，data 存放结点的值；lc 、rc 为指向左、右孩子或该结点前驱、 后继的指针，ltag 、rtag 为标志域，若值为0，则lc 、rc 为指向左、右孩子的指针；若值为1，则lc 、rc 为指向其 前驱、后继结点的指针。【答案】算法如下： /先在带头结点的中序线索二叉树T 中査找给定值为x 的结点，假定值为x 的结点存在 /设P 指向二叉树的根结点 一、算法设计题考研试题
