Question

describe five data structures . What are the fundamental operations for eachdata structure?E.g., the fundamental operations...

describe five data structures . What are the fundamental operations for eachdata structure?E.g., the fundamental operations of a stack are push and pop. Do not selection the stack, queue, double ended queue, singly linked list, or doubly linked list.There are hundreds of different data structures.

Homework Answers

Answer #1

Arrays:- It is one of the most rudimentary data structure of all. It is the one that is taught for beginners who start to learn about any programming language or any data structures course. Maybe, it's this level of simplicity of arrays that a lot of peoples many times ignore how powerful it can become. Just for the sake of completeness let's start from the beginning.

An array is a linear data structure that contains data items of a similar type.

The greatest advantage it has over a lot of other data structures is that it has constant access time for the element at any index in the array, we just need to know where it is kept. Insertion is a bit complicated actually, if we are not keeping any order to our data elements then we can simply add a new element to the end of the array but if we are then first we have to shift all the elements of the array - starting from where the insertion is going to happen to the end of the array - one step forward, to make a place for new insertion.

Arrays are used in the implementation of many other data structures like heaps, binary trees, binary search trees, Hashing tables, & so on.

Using binary Search trees we can make the complexity of search O(log n). BST (binary search trees) which can be implemented using an array also eliminate the O(n) complexity problem of insertion we were having with arrays. Using Hashing we can make the average complexity of search to O(1) which is constant complexity. But just think of being able to find a record in constant time from a data set of which contains data in order of millions of records.

So array when used with the right technique can be very useful.

Trees:- A tree is another great data structure. It is just as simple as the name suggests. Here we have a root, which can have a lot of children, which can further have children until we reach a point where a node does not have any more children. Such a node is called a leaf node. In general, each node in a tree can have n children.

In more formal words, a tree data structure can be defined recursively as a collection of nodes, where each node is a data structure consisting of a value, together with a list of references to nodes, with the constraints that no reference is duplicated, and none points to root.

This is a generic definition of a tree, but we generally use that can have only 2 children, like a binary tree, BST, AVL trees, etc. These are used specifically because they eliminate some problems that other versions of a tree might have had in past.

For eg., Binary trees are not good for searching, to search we have to search the entire tree, then came BST which provided an ordering to the elements of the tree, and in the best case the searching of an element could be performed in O(log n) time. But in the worst case the complexity of searching was still O(n) (case of skewed trees), so remove that there came AVL trees, which even in the worst cast have the complexity of O(log n) for searching, & so on.

Similar to this there are a lot of versions of trees that are used for various applications. Some of them are XOR trees, red-black trees, splay trees, B trees, B+ trees, & so on.

What can a data structure like a tree be used for? Well, actually there a lot of application of tree data structure which can be used to show child-parent relationships. For eg.:- if a university offers a lot of courses, then we can find prerequisites for a course easily using a tree. B+ trees are widely used in the file storage systems used in our computers because they can search millions of records within a short period of time, and so on.

The insertion & deletion of elements in a tree is implementation-specific.

Graphs:- A Graph is also a good one. You see in trees we could only have had parent child relationships, i.e. a parent node could only be connected to it's child. It cannot then be connected to the children of it's child. But a graph lets us do that. Now, why would we wanna do that? This is because so that we could establish a direct relationship between the two nodes, as simple as that. The graph is a data structure that is used a lot today.

We see maps on our phones that are nothing just graph containing nodes that are separated from each other by the weight(distance between the nodes) of their edges (the lines connecting two nodes).

The graphs can also be used in representing relationships and determine possible relationships in social networking applications. For eg.:- On Facebook, you might have seen peoples you may know section, where it suggests a list of people that you might know. It does so with the help of a graph data structure. What it does (at least I like to think it works this way for a reason of explanation) is it sees the list of your contacts on FB that you communicate more fluently with, and then it sees who they talk to more fluently, & then it suggests you those people thinking that you might know those people (This is just a simple explanation, in reality, it will be using very complex and a lot of such conditions to find the peoples you might know).

The insertion and deletion operations in Graph also are representation specific. There are many methods to represent graphs, three of them are adjacency list, adjacency matrix & adjacency set.

Bloom Filter:- It is a probabilistic data structure that was designed to check whether an element is present in a set. That is it can tell about absence for sure but it cannot tell about its presence. I know sounds strange (at least that was my first reaction). Let's see a bit more closely.

How it works is quite simple actually, it starts off with an array that contains a lot of bits initialized to 0. To store a data value, we simply apply k different hash functions & treat the resulting k values as indices in the array, & we set each of the k array elements to 1. We repeat this for every element we encounter.

(Still don't understand just bear a little more with me, we're almost there).

Now suppose that we have a number and we want to check whether it is present in the set or not. What to do?

Simply apply the k hash functions & look up the indicated array elements.

  • If anyone of them is 0 we can be 100% sure that we have never encountered the element before - if we had, the bit would have been stored to 1.
  • However even if all of them are 1, we still can't conclude that we have seen the element before because all of the bits could have been set by the k hash functions applied to multiple other elements that we have inserted before. All we can say is that it is likely that we may have encountered the element.

It is crucial to understand that an element once added to the bloom filter cannot be removed. Since if we try to set a bit to 0 then it would be wrong since another no. might also have set it to 1.

I know after hearing this you would say what the heck? Why would anyone use such a dumb data structure like ever in their life, but it has its applications. The applications of bloom filters are:- Weak password detection, cybersecurity like virus scanning, wallet synchronization in Bitcoin, safe browsing in Google Chrome. Not so dumb after all huh.

Symbol Table:- Now I know you probably have guessed a lot just by listening to the name but still let me try to explain. So the Symbol table is a table of symbols with their values (you might have heard it as key-value pairs). It is as simple as that. Since childhood, we all have used a dictionary. It is just like that. It is a data structure that is used widely by language translators, such as compilers or interpreters, where each unique word (identifier - the key we were talking about) in a program's source code (nothing fancy just the code we write) is associated with information relating to its declaration or appearance in the source (the value for our key). It is just a table.

We can implement symbol tables in many ways such as using Hashing, unordered or ordered array implementation, ordered or unordered linked list implementation, BST implementation, and so on. Now for each, we know how to perform insertion and deletion so the complexity of these operations will depend on the complexity of insertion & deletion of data structure which is used for its implementation.

Hope this helps. If you like the answer please upvote. If you have any queries or suggestions regarding the answers please leave them in the comments section so I can update and improve the answer. Thank you

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
In five sentences describe the following: a) how you would implement a stack using an array,...
In five sentences describe the following: a) how you would implement a stack using an array, including the push and pop operation b) how you could implement a queue using a linked list, including what type of linked list would be best, the enqueue and dequeue operations
JAVA *** All data structures, including array operations, queues, stacks, linked lists, trees, etc need to...
JAVA *** All data structures, including array operations, queues, stacks, linked lists, trees, etc need to be implemented by you. Write a menu driven program that implements the following doubly linked list operations : INSERT (at the beginning) INSERT_ALPHA (in alphabetical order) DELETE (Identify by contents, i.e. "John", not #3) COUNT CLEAR
1. Which of the following statements is FALSE? a. A transformer operation changes the object (e.g....
1. Which of the following statements is FALSE? a. A transformer operation changes the object (e.g. list.add(element) changes the list by adding an element) b. An observer operation may also modify the object (e.g. list.isFull( ) may increase the size of the list if no more elements can be added) c. An observer operation returns information about an object (e.g. list.size() returns the number of elements in the list) d. A transformer operation may or may not return a value....
   vi. Assume that a linked list stores the data, 20, 11, 13, 19, 12, 14...
   vi. Assume that a linked list stores the data, 20, 11, 13, 19, 12, 14 in that order. Assume that Node head references the first item in the list. What is the result to the linked list of       the following instructions? Assume that newNode          is a Node, already constructed. newNode.data = 1;                         newNode.next = head.next;                         head = newNode;       a. The value 1 is inserted into the linked list before 20       b. The...
Describe a software application that would require a graph data structure in its implementation. Explain what...
Describe a software application that would require a graph data structure in its implementation. Explain what the vertices and edges of the graph would represent. Would the graph be undirected or directed? Would it be weighted or unweighted? Decide which type of representation would be best for this application, an adjacency matrix, an adjacency list using an array of linked lists or a fully linked representation. Explain your reasoning.
Assume that your machine has a built-in data structure that inserts an item into a priorityqueue...
Assume that your machine has a built-in data structure that inserts an item into a priorityqueue in one step. There is no charge to remove an item. It has both a min-priority queue anda max-priority queue available. You can access the largest element for one comparison step ina max-priority queue, and similarly you can access the smallest element for one comparisonstep in a min-priority queue. This machine can sort a list in linear time: Insert all of the elements into...
Data Structures using C++ Consider the classes QueueADT and ArrayQueueType: QueueADT: #ifndef QUEUEADT_H #define QUEUEADT_H template...
Data Structures using C++ Consider the classes QueueADT and ArrayQueueType: QueueADT: #ifndef QUEUEADT_H #define QUEUEADT_H template <class ItemType> class QueueADT { public:        // Action responsibilities        virtual void resetQueue() = 0;           // Reset the queue to an empty queue.           // Post: Queue is empty.        virtual void add(const ItemType& newItem) = 0;           // Function to add newItem to the queue.           // Pre: The queue exists and is not full.          ...
I've posted this question like 3 times now and I can't seem to find someone that...
I've posted this question like 3 times now and I can't seem to find someone that is able to answer it. Please can someone help me code this? Thank you!! Programming Project #4 – Programmer Jones and the Temple of Gloom Part 1 The stack data structure plays a pivotal role in the design of computer games. Any algorithm that requires the user to retrace their steps is a perfect candidate for using a stack. In this simple game you...
1. What are the 5 major components of a hard disk drive (10pts)? Describe the basic...
1. What are the 5 major components of a hard disk drive (10pts)? Describe the basic function of each component (10pts). 2. Give two examples of memory that are commonly used for large scale and permanent data storage in system administration (4pts). What are the three commonly used storage access methods in system administration (6pts)? 3. Assuming there are 35 SSDs, how many different types of RAID 50 can be built using all 35 SSD? Draw the layout of each...
What tools could AA leaders have used to increase their awareness of internal and external issues?...
What tools could AA leaders have used to increase their awareness of internal and external issues? ???ALASKA AIRLINES: NAVIGATING CHANGE In the autumn of 2007, Alaska Airlines executives adjourned at the end of a long and stressful day in the midst of a multi-day strategic planning session. Most headed outside to relax, unwind and enjoy a bonfire on the shore of Semiahmoo Spit, outside the meeting venue in Blaine, a seaport town in northwest Washington state. Meanwhile, several members of...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT