数据结构和算法|集2-yiteyi-C++库

在GATE CS考试中提出了以下问题。

null

1、考虑下面定义的函数f。

                     struct                               item                   
                     {                   
                                         int                               data;                   
                                         struct                               item * next;                   
                     };                   
                             
                     int                               f(                               struct                               item *p)                   
                     {                   
                                         return                               (                   
                                         (p == NULL) ||                   
                                         (p->next == NULL) ||                   
                                         (( P->data <= p->next->data) && f(p->next))                   
                                         );                   
                     }                   

对于给定的链表p，函数f返回1当且仅当（GATE CS 2003） a）列表为空或只有一个元素 b）列表中的元素按数据值的非降序排序 c）列表中的元素按数据值的非递增顺序排序 d）并非列表中的所有元素都具有相同的数据值。

答复（b）函数f（）的工作原理如下 1）如果链表为空，则返回1 2）否则，如果链表只有一个元素，则返回1 3）否则，如果node->data小于等于node->next->data，并且相同的值适用于列表的其余部分，则返回1 4）否则返回0

2、考虑在标记二叉树上由以下对遍历获得的标签序列。这些对中的哪一对唯一地标识了一棵树（GATE CS 2004）？ i）前序和后序 ii）按顺序和按顺序 iii）前序和有序 iv）级别顺序和后期顺序

a）（i）仅限 b）（二）、（三） c）（iii）仅限 d）（iv）仅限

答复（b）请看这张贴解释。

3.以下数字按给定顺序插入到空的二叉搜索树中：10、1、3、5、15、12、16。二叉搜索树的高度是多少（高度是叶节点到根的最大距离）？（门CS 2004） a）二, b）三, c）四, d）六,

答复（b）构造的二叉搜索树将。。

                    10
                  /     
                 1       15
                       /  
                  3    12   16
                    
                     5

4.需要一个数据结构来存储一组整数，以便在（logn）时间内完成以下每个操作，其中n是集合中的元素数。

o Deletion of the smallest element o Insertion of an element if it is not already present in the set

以下哪种数据结构可用于此目的？

（a）可以使用堆，但不能使用平衡的二进制搜索树（b）可以使用平衡二叉搜索树，但不能使用堆（c）平衡二叉搜索树和堆都可以使用（d）既不能使用平衡二叉搜索树，也不能使用堆

答复（b） A. 自平衡二叉搜索树包含n个项允许在O（logn）最坏情况下查找、插入和删除一个项。由于它是一个自平衡的BST，我们可以很容易地找到O（logn）时间内的最小元素，它总是最左边的元素（参见在二叉搜索树中找到具有最小值的节点 ).

自从堆是一个平衡的二叉树（或几乎完全的二叉树），堆的插入复杂度为O（logn）。此外，在min堆中获得最小复杂性是O（logn），因为删除根节点会导致调用希皮菲（从数组中删除第一个元素后）以维护heap tree属性。但堆不能用于上述目的，正如问题所说的那样——如果元素还不存在，请插入它。对于堆，我们无法在O（logn）中确定元素是否存在。感谢游戏提供了正确的解决方案。

5.循环链表用于表示队列。单个变量p用于访问队列。p应该指向哪个节点，以便在固定时间内执行入队和出队操作？（大门2004）

a）后节点 b）前节点 c）用一个指针是不可能的 d）靠近前面的节点

答复（a）答案不是“（b）front node”，因为我们不能在O（1）中从前面得到后面，但是如果p是后面的，我们可以在O（1）中实现排队和退队，因为从后面我们可以在O（1）中得到前面。下面是示例函数。请注意，这些函数只是示例，不起作用。缺少处理基本情况的代码。

                     /* p is pointer to address of rear (double pointer).  This function adds new                   
                                         node after rear and updates rear which is *p to point to new node  */                   
                     void                               enQueue(                               struct                               node **p,                               struct                               node *new_node)                   
                     {                   
                                         /* Missing code to handle base cases like *p is NULL */                   
                             
                                         new_node->next = (*p)->next;                   
                                         (*p)->next = new_node;                   
                                         (*p) = new_node                               /* new is now rear */                   
                                         /* Note that p is again front and  p->next is rear */                   
                                         }                   
                             
                     /* p is pointer to rear. This function removes the front element and                   
                                         returns the new front */                   
                     struct                               node *deQueue(                               struct                               node *p)                   
                     {                   
                                         /* Missing code to handle base cases like p is NULL,                   
                                         p->next is NULL,...  etc */                   
                             
                                         struct                               node *temp = p->next->next;                   
                                         p->next = p->next->next;                   
                                         return                               temp;                   
                                         /* Note that p is again front and  p->next is rear */                   
                     }                   

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章