数据结构试卷和答案.doc

姓名 班级 数据结构试题参考答案 （开卷）（电信系本科2001级 2002年12月）一、回答下列问题 (每题4分，共36分)1. 某完全二叉树共有15381个结点，请问其树叶有多少个？答：n2=n/2=15381/2=7691(个)2. 假设有二维数组A79，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，末尾元素A68的第一个字节地址为多少？若按列存储时，元素A47的第一个字节地址为多少？答： 末尾元素A68的第一个字节地址1000（7行9列1）6B1000626=1372 按列存储时，元素A47的第一个字节地址1000（7列7行4）6B1000536=13183. 在KMP算法中，已知模式串为ADABBADADA ，请写出模式串的nextj函数值。答：根据 0 当j1时next j max k |1kj 且T1Tk-1=Tj-(k-1) Tj-1 1 其他情况1 2 3 4 5 6 7 8 9 100 1 1 2 1 1 2 3 4 3A D A B B A D A D A对应模式串的next j 演示程序亦验证了结果：nextj=01121123434. 已知一棵二叉树的前序序列和中序序列分别为：ABDEGCFH和DBGEACHF，则该二叉树的后序序列是什么？ 答：法1：先画树而得后序序列； AB CD E F G H A(DBGE) (CHF) B C 结论：D G E B H F C AD (GE) (HF)E F G H法2：直接推出后序序列 step1: (DBGE) (CHF) Astep2: D(GE)B (HF) C Astep3: DGEB HF C A5. 请证明：用二叉链表法（Lchild-Rchild）存储包含n个结点的二叉树，必有n+1个指针域为空。答：因为：用二叉链表存储包含n个结点的二叉树，结点共有2n个链域；又因为：二叉树中除根结点外，每一个结点有且仅有一个双亲，这就意味着只有n-1个结点的链域存放指向非空子女结点的指针（换句话说，有后继孩子链接的指针仅n-1个）；所以，空指针数目全部指针数2n所有非空指针数(n-1)=所有空指针数n1，证毕。6. 设二叉排序树中关键字互不相同，则其中最小元素必无左孩子，最大元素必无右孩子。此命题是否正确？最大元素和最小元素一定是叶子吗？一个新的结点总是插在二叉排序树的某叶子上吗？ 请解释理由。答： 设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。此命题正确。解释：假设最小元为min，若最小元min有左孩子min，根据二叉排序树的定义应该有：min min,与min是最小元矛盾，由此可反证出最小元必无左孩子；同理可反证出最大元必无右孩子。 最大元和最小元不一定是叶子；解释：虽然最小元必无左孩子，最大元必无右孩子，但最小元可有右孩子，最大元可有左孩子。如下图A和B所示。所以最大元和最小元不一定是叶子。 一个新的结点不一定总是插在二叉排序树的某叶子上。解释：例如给定关键字A,B,C，以B、A、C的次序插入一空的二叉排序树中，过程如下图C所示。当再插入C时，C作为B的右孩子，插入后如图D所示，但此时B已有左孩子A，元矛盾，由此可反证出最小元必无左孩子；同理可反证出最大元必无右孩子。7. 假设一有序表中有23个元素，现进行折半查找，则平均查找长度是多少？答：显然，平均查找长度O（log2n）next;while(p!=head)r=p-next;p-next=q;q=p;p=r; p-next=q;head=q;法1的核心部分为：q=head;p=head-next;while(p!=q)r=p-next;p-next=head;head=p; p=r;q-next=head;2. 定义二叉树的宽度为二叉树一层中结点个数的最大值，试编写一算法求二叉树的宽度。（9分）解：要用层次遍历以及队列来处理，并一定要设立一个宽度计数器和一个temp，在统计完每一层的结点个数之后就要与计数器中前一层的值比较，保留大值。 可参见严题集【6.52】 。参考程序如下：typedef struct BTNode node; int layer; int layer; BTNRecord; /包含结点所在层次的记录类型 int FanMao(Bitree T) /求一棵二叉树的繁茂度 int countd; /count数组存放每一层的结点数 InitQueue(Q); /Q的元素为BTNRecord类型 EnQueue(Q,T, 0); while(!QueueEmpty(Q) DeQueue(Q,r); countr.layer+; if(r.node-lchild) EnQueue(Q,r.node-lchild, r.layer+1); if(r.node-rchild) EnQueue(Q,r.node-rchild, r.layer+1); /利用层序遍历来统计各层的结点数 h=r.layer; /最后一个队列元素所在层就是树的高度 for(maxn=count0, i=1; h counti; i+) if(countimaxn) maxn=counti; /求层最大结点数 return (h*maxn); /FanMao 分析: 如果不允许使用辅助数组，就必须在遍历的同时求出层最大结点数，形式上会复杂一些。3. 试用C或类C语言编写一个算法： （A、B两题任选其一， 9分）A. 统计二叉树的总结点数和叶子结点数。 B. 对于一个有10000个记录的线性表，希望用尽可能快的速度挑选出前10个最小的记录。解：A容易，将遍历函数中Visit()细化即可，设立两个计数器，一个每次都，一个是遇见叶子才。 或者，可参考【严题集6.42】编写递归算法（计算二叉树中叶子结点的数目）。至于总结点数就更容易添加了。思路：用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其用sum2计数。至于总结点数，无论是否叶子都累计到sum中即可。法一：核心部分为： 初始化：sum=sum2=0;DLR(liuyu *root) /中序遍历的递归函数if(root!=NULL) if(root-lchild=NULL)&(root-rchild=NULL)sum2+; /统计叶子结点数sum+; /统计总结点数 DLR(root-lchild); DLR(root-rchild); return(0);B稍难，用冒泡排序加标志会在有序的情况下很快；但用锦标赛排序会在一般情况下更有优势，快得多。冒泡是O（n2）,锦标赛是O（n+9log2n）解：用冒泡排序的核心算法：法2的设计思路为： 完全仿照锦标赛程序或堆排序求最小值用了n-1次；但求后9个次小值时，只需比较log2n次；最好、最坏和平均情况相同：都是(n-1)+9log2n次。法1的核心部分为：for(i=1; i=10; i+ )tag=1;while(tag= =1)tag=0;for(j=1; j=10000-1; j+)if(ajlchild&flag) Is_BSTree(T-lchild); if(T-datadata; if(T-rchild&flag) Is_BSTree(T-rchild); return flag; /Is_BSTree 在已经生成的中序线索二叉树中，求给定元素p的直接后继。B 注意：即使是已生成的线索二叉树，除了叶子结点的后继很明确外，还要考虑非叶子结点的后继如何求的问题。中序线索二叉树非叶子结点的后继，应该是p的右子树之最左结点。 可参考教材P134算法6.5，但程序要修改。Status InOrderrTraverse_Thr(BiThrTree T, Status(*Visit)(TelemType e)/T指向头结点，头结点的左链lchild指向根结点，可参见线索化算法。/中序遍历二叉线索树T的非递归算法，对每个数据元素调用函数Visit。P=T-lchild; /p指向根结点while(p!=T) /空树或遍历结束时，p= =T先用遍历的办法找到指定结点p；再根据不同情况返回它的后继；while(p-Rtag=Link)p=p-rchild; /(如果p结点的右指针不是线索,应当找其后继，应该是p的右子树之最左结点!)if(!Visit(p-data)