《数据结构习题》由会员分享，可在线阅读，更多相关《数据结构习题（6页珍藏版）》请在金锄头文库上搜索。
1、树和二叉树习题（39）1请编写一种鉴别给定二叉树与否为二叉排序树的算法，设二叉树用 llink-rlink 法存储。 2 假设 K1，Kn 是 n 个核心词，试解答： (1) 试用二叉查找树的插入算法建立一棵二叉查找树，即当核心词的插入顺序为 K1，K2，Kn 时，用算法建立一棵以LLINK / RLINK 链接表达的二叉查找树。 (2) 设计一种算法，打印出该二叉查找树的嵌套括号表达构造。例如，K1=B，K2=A，K3=D，K4=C，K5=E，则用二叉查找树的插入算法建立的二叉查找树为：该二叉查找树的嵌套括号表达构造为：B（A，D（C，E） ） 3 写出在二叉排序树中删除一种结点的算法，使删
2、除后仍为二叉排序树。设删除结点由指针 p 所指，其双亲结点由指针 f 所指，并假设被删除结点是其双亲结点的右孩子。用类 PASCAL（或 C）语言将上述算法写为过程形式。 4. 已知二叉树排序树中某结点指针 p,其双亲结点指针为 fp,p 为 fp 的左孩子，试编写算法，删除 p 所指结点。 5二叉排序树采用二叉链表存储。写一种算法，删除结点值是 X 的结点。规定删除该结点后,此树仍然是一棵二叉排序树，并且高度没有增长（注：可不考虑被删除的结点是根的状况） 。 6. 设记录 R1,R2,Rn 按核心字值从小到大顺序存储在数组 r1.n中,在rn+1处设立一种监督哨,其核心字值为+; 试写一查找
3、给定核心字 k 的算法;并画出此查找过程的鉴定树,求出在等概率状况下查找成功时的平均查找长度。 7设计算法以求解编号为i和j的两个结点的近来的公共祖先结点的编号。 8元素集合已存入整型数组 A1.n中， 试写出依次取 A 中各值 Ai(1=i=2 的树，树中的每个结点中不是涉及一种或几种核心字，而是只具有构成核心字的符号。编写一种在键（TIRE）树 T 上查找核心字等于给定值 KEY 的记录的算法。若查找成功，返回指向该记录的指针；否则返回空指针。 11写出从哈希表中删除核心字为 K 的一种记录的算法，设哈希函数为 H，解决冲突的措施为链地址法。12编写一用链接表（LINKED LIST）解决
4、冲突的哈希表插入函数。 13在用除余法作为散列函数、线性探测解决冲突的散列表中，写一删除核心字的算法，规定将所有可此前移的元素前移去填充被删除的空位，以保证探测序列不致于断裂。 14设排序二叉树中结点的构造为下述三个域构成: data: 给出结点数据的值；left: 给出本结点的左儿子结点的地址；right: 给出本结点的右儿子结点的地址 设 data 域为正整数，该二叉树树根结点地址为 T。 现给出一种正整数 x。请编写非递归程序，实现将 data 域的值不不小于等于 x 的结点所有删除掉。 15已知二叉树 T 的结点形式为(llink, data,count,rlink,),在树中查找值为
5、 X 的结点，若找到，则记数（count）加 1；否则，作为一种新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。 16假设一棵平衡二叉树的每个结点都标明了平衡因子 b,试设计一种算法，求平衡二叉树的高度。 17设从键盘输入一种整数的序列：n,a1,a2，an,其中 n 表达持续输入整数的个数。（1）试编写一程序按整数值建立一种二叉排序树 18.设二叉排序树的各元素值均不相似，采用二叉链表作为存储构造，试分别设计递归和非递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。 19 在单链表中， 每个结点具有 5 个正整型的数据元素若 （最后一种结点的数据元素不满 5 个， 以
6、值 0 充） ，试编写一算法查找值为 n（n0）的数据元素所在的结点指针以及在该结点中的序号，若链表中不存在该数据元素则返回空指针。 20编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的鉴定树。假设每次查找时的给定值为随机值，又查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的核心字个数的盼望值。 21. 在二叉排序树的构造中，有些数据元素值也许是相似的 ，设计一种算法实现按递增有序打印结点的数据域，规定相似的数据元素仅输出一种，算法还应能报出最后被滤掉，而未输出的数据元素个数，对如图所示的二叉排序树，输出为：10，12，13，15，18，21，27，35，42滤
7、掉 3 个元素。22已知二叉排序树采用二叉链表存储构造，根结点的指针为 T，链结点的构造为（lchild,data,rchild） ，其中lchild、 rchild 分别指向该结点左、 右孩子的指针 （当孩子结点不存在时， 相应指针域为 null） ,data域寄存结点的数据信息。请写出递归算法，从小到大输出二叉排序树中所有数据值=x 的结点的数据。规定先找到第一种满足条件的结点后再依次输出其她满足条件的结点。 23. 已知某哈希表 HT 的装填因子不不小于 1，哈希函数 H(key)为核心字的第一种字母在字母表中的序号。 （1） 解决冲突的措施为线性探测开放地址法。编写一种按第一种字母的顺
8、序输出哈希表中所有核心字的程序。 （2）解决冲突的措施为链地址法。编写一种计算在等概率状况下查找不成功的平均查找长度的算法。注意，此算法中规定不能用公式直接求解计算。 24有一种 100*100 的稀疏矩阵，其中 1%的元素为非零元素，现规定用哈希表作存储构造。 （1）请你设计一种哈希表 （2）请写一种对你所设计的哈希表中给定行值和列值存取矩阵元素的算法；并对你的算法所需时间和用一维数组（每个分量寄存一种非零元素的行值，列值，和元素值）作存储构造时存取元素的算法（注：此算法不需要写出，仅需阐明存取的措施和所用时间）进行比较。 25将一组数据元素按哈希函数 H（key）散列到哈希表 HT（0:m
9、）中，用线性探测法解决冲突（H（key）+1、H（key）+2、H（key）-1） ，假设空单元用 EMPTY 表达，删除操作是将哈希表中结点标志位从 INUSE标记为 DELETED，试写出该散列表的查找、插入和删除三个基本操作算法。 26. 设给定核心字输入序列为（100，90，120，60，78，35，42，31，15）用散列法散列 0-10 的地址区间。规定设计一合理的散列函数；冲突时用链表法解决，写出散列算法，并构造出散列表，在等概率查找状况下查找成功的平均查找长度是多少？ 类似本题的此外论述有： (1) 已知输入核心字序列为（100,90,120,60,78,35,42,31,15
10、）地址区间为。设计一种哈希表函数把上述核心字散到中，画出散列表（冲突用线性探测法） ；写出查找算法，计算在等概率状况下查找成功的平均查找长度。 27. 已知顺序表中有 m个记录，表中记录不依核心字有序排列，编写算法为该顺序表建立一种有序的索引表，索引表中的每一项含记录的核心字和该记录在顺序表中的序号，规定算法的时间复杂度在最佳的状况下能达到O(m).28设计算法以输出二叉树中先序序列的前k（k0）个结点的值。29设计算法按中序顺序依次输出各结点的值及其相应的序号。例如，下图中的二叉树的输出成果是(C,1) (B,2) (E,3) (D,4) (F,5) (A,6) (H,7) (J,8) (I
11、,9) (G,10)。 30设计算法以输出每个结点到根结点之间的途径上的所有结点的值。31设计算法将一棵以二叉链表形式存储的二叉树转换为顺序存储形式存储到数组An中，并将其中没有寄存结点值的数组元素设立为NULL。32设计算法将一棵以顺序存储方式存储在数组A中的二叉树转换为二叉链表形式。33分别设计出先序、中序和后序遍历二叉树的非递归算法。34分别讨论先序、中序和后序线索化二叉树中前驱和后继的求解。35设计一种遍历先序线索二叉树的非递归算法，规定不许用栈。36设计算法将值为x的结点作为右子树的（后序序列的）第一种结点的左孩子插入到后序线索二叉树中。37分别设计出先序、中序和后序线索化算法。27
12、设计算法以实现将以二叉链表形式存储的树（森林）转换为相应的双亲表达形式。28已知树（森林）的高度为4，所相应的二叉树的先序序列为ABCDE，请构造出所有满足这一条件的树或森林。 29设计算法将一种以孩子链表形式表达的森林转换为二叉链表形式。30设计算法按先序顺序输出森林中每个结点的值及其相应的层次数。31设计算法以求解森林的高度。32设计算法以输出森林中的所有叶子结点的值。33设计算法逐级输出森林中的所有结点的值。 34设计算法将森林中的结点以广义表的形式输出。例如，下图中的森林的输出成果为： (A,(B,(E,(K),F,G),(C,(H,I),(D,(J) , (L,(M,N), (O,(P) 35设计一种程序以对文献进行压缩，计算其压缩比例，然后对所压缩的文献进行还原。36设计算法以产生哈夫曼树中各叶子结点的哈夫曼编码。37. 以二叉链表为存储构造，分别写出求二叉树结点总数及叶子总数的算法。38. 以二叉链表为存储构造，编写算法对二叉树进行层次遍历（提示：应使用队列来保存各层的结点。）39.写出二叉树的按层遍历算法
