- 搜标题
- 搜题干
- 搜选项
问答题
已知二叉树排序树中某结点指针p，其双亲结点指针为fp，p为fp的左孩子。试编写算法，删除p所指结点。
答案：
正确答案：本题用被删结点右子树中最小值(中序遍历第一个)结点代替被删结点。 void Delete(BSTree bst...
你可能感兴趣的试题
问答题
请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink—rlink法存储。
答案：
正确答案：根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全...
问答题
某个任务的数据模型可以抽象为给定的k个集合：S 1 ，S 2 ，…，S k 。其中S i (1≤i≤k中的元素个数不定。在处理数据过程中将会涉及元素的查找和新元素的插入两种操作，查找和插入时用一个二元组(i，x)来规定一个元素，i是集合的序号，x是元素值。设计一种恰当的数据结构来存储这k个集合的元素，并能高效地实现所要求的查找和插入操作。 (1)构造数据结构，并且说明选择的理由。 (2)若一组数据模型为S 1 ={10．2，1．7，4．8，16．2}，S 2 ={1．7，8．4，0．5}，S 3 ={4．8，4．2，3．6，2．7，5．1，3．9}，待插入的元素二元组为(2，11．2)和(1，5．3)，按你的设计思想画出插入元素前后的数据结构状态。
答案：
正确答案：借助于分块查找思想，在建立数据顺序表的同时，建立一索引表。数据表中按k个集合分块(元素个数不一定相等)，索引表...
问答题
假设K 1 ,…，K n 是n个关键词，试解答： (1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K 1 ，K 2 ，…，K n 时，用算法建立一棵以LLINK—RIJNK链接表示的二叉查找树。 (2)设计一个算法，打印出该二叉查找树的嵌套括号表示结构。假定该二叉查找树的嵌套括号表示结构为B(A，D(C，E))。
答案：
正确答案：(1)非递归建立二叉排序树，在二叉排序树上插入的结点都是叶子结点。 typedef struet node{ ...
问答题
写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。设删除结点由指针p所指，其双亲结点由指针f所指，并假设被删除结点是其双亲结点的右孩子。描述上述算法。
答案：
正确答案：void Delete(BSTree t，P){ ／／在二叉排序树t中，删除f所指结点的右孩子(由P所指向) ...
问答题
已知二叉树排序树中某结点指针p，其双亲结点指针为fp，p为fp的左孩子。试编写算法，删除p所指结点。
答案：
正确答案：本题用被删结点右子树中最小值(中序遍历第一个)结点代替被删结点。 void Delete(BSTree bst...
问答题
二叉排序树采用二叉链表存储。写一个算法，删除结点值是X的结点。要求删除该结点后，此树仍然是一棵二叉排序树，并且高度没有增长(注意：可不考虑被删除的结点是根的情况)。
答案：
正确答案：在二叉排序树上删除结点，首先要查找该结点。查找成功后，若该结点无左子树，则可直接将其右子树的根结点接到其双亲结...
问答题
设记录R 1 ，R 2 ，…，R n 按关键字值从小到大顺序存储在数组r[1．．n]中，在r[n+1]处设立一个监督哨，其关键字值为+∞。试写一查找给定关键字k的算法，并画出此查找过程的判定树，求出在等概率情况下查找成功时的平均查找长度。
答案：
正确答案：intSearch(rectype r[]，int n，keytype k){ ／／在n个关键字从小到大排列的...
问答题
键树(Trie)，又称数字查找树，它是一棵度大于等于2的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。请用类C语言或类PASCAL语言编写一个在键树T上查找关键字等于给定值KEy的记录的算法。若查找成功，返回指向该记录的指针；否则返回空指针。
答案：
正确答案：在Trie树上查找给定值KEY的过程如下：沿和给定值相应的指针向下，直至叶子结点，若叶子中的关键字和KEY相等...
问答题
写出从哈希表中删除关键字为K的一个记录的算法。设哈希函数为H，解决冲突的方法为链地址法。
答案：
正确答案：用链地址法解决冲突的哈希表是一个指针数组，数组分量均是指向单链表的指针，(第i个)单链表结点有两个域，一个是哈...
问答题
用C语言或PASCAL编写一用链接表(Linked List)解决冲突的哈希表插入函数。
答案：
正确答案：本题仍用上面已定义的存储结构。首先计算关键字K的哈希地址，若该哈希地址的头指针为空，则直接插入；否则，先在该链...
问答题
在用除余法作为散列函数线性探测解决冲突的散列表中，写一删除关键字的算法，要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不至于断裂。
答案：
正确答案：首先计算关键字的散列地址，若该地址为空，则空操作；若该地址有关键字，但与给定值不等，则用解决冲突的方法去查找给...
问答题
设排序二叉树中结点的结构由三个域构成：数据域data，指向左儿子结点的指针域left，指向右儿子结点的指针域right。设data域为正整数，该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序，实现将data域的值小于等于x的结点全部删除。
答案：
正确答案：利用二叉排序树的性质，从根结点开始查找，若根结点的值小于等于x，则根结点及其左子树均应删除，然后以右子树的根结...
问答题
已知二叉树T的结点形式为(llink，data，count，rlink)，在树中查找值为X的结点，若找到，则记数(count)加1；否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。
答案：
正确答案：typedef struct node{ datatype data； int count； struct n...
问答题
假设一棵平衡二叉树的每个结点都标明了平衡因子b，试设计一个算法，求平衡二叉树的高度。
答案：
正确答案：因为二叉树各结点已标明了平衡因子b，故从根结点开始记树的层次。根结点的层次为1，每下一层，层次加1，直到层数最...
问答题
设从键盘输入一个整数的序列：n，a 1 ，a 2 ，…，a n ，其中n表示连续输入整数的个数。 (1)试编写一程序按整数值建立一个二叉排序树。 (2)在(1)的基础上将此二叉树上的各整数按降序写入一磁盘文件中。
答案：
正确答案：二叉排序树的建立问题前面第3题的(1)中已介绍，此处不再赘述。将二叉排序树上的各整数按降序写入磁盘，要对二叉排...
问答题
设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空、右子树非空的结点的数据域的值。
答案：
正确答案：(1)递归算法 void DecPrint(BSTree t){ ／／递减序输出二叉排序树t中所有左子树为空、...
问答题
在单链表中，每个结点含有5个正整型的数据元素(若最后一个结点的数据元素不满5个，以值0充)，试编写一算法查找值为n(n＞0)的数据元素所在的结点指针以及在该结点中的序号，若链表中不存在该数据元素则返回空指针。
答案：
正确答案：这是一个在单链表中查找结点，在结点内查找给定值的过程，先定义存储结构。 typedef struct node...
问答题
编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，且查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。
答案：
正确答案：int Search(rectype R[]，int n，K){ ／／在具有n个元素的有序表R中，顺序查找值为...
