Skip to main content

DATA STRUCTURES – Q & A

Define Abstract Data Type (ADT).

Abstract data type is a collection of value definitions and the operations on those values.

    • Value definitions
    • Operator definitions

Define a sequence.

A sequence is an ordered set of elements.

S=<s0,s1,s2…….sn-1>

Write short notes on structures in C.

A basic data structure in C is called as the structure. A Structure is a group of items in which each item is identified by its own identifier.

Example:

struct nametype

{

char first[10];

int roll;

}sname, ename;

What is the difference between a structure and union in C.

  1. Same memory is used for all the members of union. At any time only one member can be accessed.
  2. Individual memory is used for structure members.

Define a Stack.

A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end called the top of the stack.

It is also called as Last In First Out (LIFO).

What are the primitive operations that are performed on a Stack?

The primitive operations are

Push- inserting an element at the top of the stack

Push(s,i);

Pop – removing an element at the top of the stack

i=pop(s);

How do you implement the Stack definition in C. Use array implementation?

#define STACKSIZE

struct stack

{

int top;

int items[STACKSIZE];

};

Write the steps for implementing the pop operation.

    • If the stack is empty, print a warning message and halt execution
    • Remove the top element from the stack.
    • Return this element to the calling program

What is recursive definition?

An object in terms of simpler case of itself is called recursive definition.

Examples:

· To find the factorial of a given number

· To print the Fibonacci series.

Define a queue.

A queue is a ordered collection of items from which itesm may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end (called the rear of the queue). It is also called as First in First out (FIFO).

How the queue is represented in C?

#define MAXQUEUE 100

struct queue

{

int items[MAXQUEUE];

int front, rear;

}q;

Define priority queue. What are the types of Priority queue?

The priority queue is a data structure in which the intrinsic ordering of the elements does determine the results. There are two types

· ascending priority queue

is a collection of items into which items can be inserted arbitrarily and from which only the smallest item can be removed.

· descending priority queue

What is the purpose of header node?

Sometimes it is desirable to keep an extra node at the front of the list. Such a node does not represent an item in the list and is called the header node or a list header.

How to create and delete a dynamic variable in C?

malloc() is a function helpful for creating a dynamic variable.

free() is a function helpful for deleting a dynamic variable.

How to create a node of a singly linked list using dynamic variables?

struct node

{

int info;

struct node *next;

};

typedef struct node *NODEPTR;

16. How to create a node of a Doubly linked list using dynamic variables?

struct node

{

int info;

struct node *next, *previous;

};

typedef struct node *NODEPTR;

17. Define a binary tree.

A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. One subset is the left and one subset of the right and the third subset is the root of the tree.

18. What is a strictly binary tree?

If every non leaf node in a binary tree has nonempty left and right subtrees, the tree is named as the strictly binary tree.

19. Define traversal in tree and what is the different type of traversals in tree?

To pass through the tree, enumerating each of its nodes once.

Three types of traversals

    • preorder traversal
      • visit the root
      • Traverse the left subtree in preorder.
      • Traverse the right subtree in preorder
    • inorder traversal
      • Traverse the left subtree in preorder.
      • visit the root
      • Traverse the right subtree in preorder
    • postorder traversal
      • Traverse the left subtree in preorder.
      • Traverse the right subtree in preorder
      • visit the root

20. How the binary tree node is represented dynamically?

struct nodetype

{

int info;

struct nodetype *left;

struct nodetype *right;

};

21. What are called leaf nodes?

The nodes which don’t have any sons are called as leaf nodes.

22. What are called internal and external nodes?

The leaf nodes are called as external nodes and the non leaf nodes are called as internal nodes.

23. Define O notation.

To capture the concept of one function becoming proportional to another as it grows, a notation is which is called as O notation.

24. Define a graph.

A graph consists of a set of nodes (or vertices) and set of arcs (or edges).

25. Define weighted graph.

A number is associated with each arc of a graph is called a weighted graph. The number associated with the arc is called the weight.

26. Define minimum spanning tree.

Given a connected weighted graph G, it is often desired to create a spanning tree T for G such that the sum of the weights of the tree edges in T is as small as possible. Such a tree is called minimum spanning tree.

27. Define Depth First Traversal.

Visits the successors of a visited node before visiting any of its brothers.

In DFT, each visited node is placed in the stack

28. Define Breadth First Traversal.

Visits all successors of a visited node before visiting any successors of any of those successors.

In BFT, each visited node is placed on the queue.

29. What are called Dynamic data structures?

Structures which grow or shrink as the data they hold changes.

Example: Lists

30. Define Binary Search.

A technique for searching an ordered list in which we first check the middle item and - based on that comparison - "discard" half the data. The same procedure is then applied to the remaining half until a match is found or there are no more items left.

31. What are the advantages of linked lists?

· Overflow can never occur unless the memory is actually full.

· Insertions and deletions are easier than for contiguous (array) lists.

· With large records, moving pointers is easier and faster than moving the items th

emselves.

32. What are the disadvantages of linked lists?

· The pointers require extra space.

· Linked lists do not allow random access.

· Time must be spent traversing and changing the pointers.

· Programming is typically trickier with pointers.

33. Define Binary Search Trees.

A binary search tree is a binary tree where each node contains a key such that:

· All keys in the left subtree lesser than the key in the root.

· All keys in the right subtree greater the key in the root.

· The left and right subtrees of the root are again binary search trees.

34. What is the difference Data types vs. Data Structures?

· A data type is a well-defined collection of data with a well-defined set of operations on it.

· A data structure is an actual implementation of a particular abstract data type.

Comments

  1. sir your website is very useful sir.sir i want to know linked list in data structure sir.i cannot understand that concept sir.Thank you sir.

    ReplyDelete

Post a Comment

Popular posts from this blog

Installing ns-3.34 in Ubuntu 20.04

This post shows how to install ns 3.34 in Ubuntu 20.04 LTS Prerequisites: Fresh installation of Ubuntu Version 20.04 LTS  ns3.34 can be downloaded from here Follow the video link for complete step by step instructions on the installation.  This version fixes the compilation issues of vanet-routing-compare.cc (bug in ns3.33)  Issue the following commands after opening a terminal  $ sudo apt update $ sudo apt install g++ python3 python3-dev python-dev pkg-config sqlite3 python3-setuptools git qt5-default gir1.2-goocanvas-2.0 python3-gi python3-gi-cairo python3-pygraphviz gir1.2-gtk-3.0 ipython3 openmpi-bin openmpi-common openmpi-doc libopenmpi-dev autoconf cvs bzr unrar openmpi-bin openmpi-common openmpi-doc libopenmpi-dev tcpdump wireshark libxml2 libxml2-dev Unzip or untar the ns-allinone-3.34.tar.bz2 in the home folder (in my case its /home/pradeepkumar) $ cd ns-allinone-3.34/ $ ./build.py --enable-examples --enable-tests  Once the installation is completed, you may get an output show

Installation of ns3 in Windows 10 and Windows 11 OS using WSL (Windows Subsystem for Linux)

This post shows how to install ns-3.33 in Windows 10 through WSL (Windows Subsystem for Linux) This posts works for Windows 11 also (I have tested it on a Windows 11 ISO and it works the Same way as mentioned in the following post.) This post will work for ns-3.3x version. Prerequisites : Install Windows Subsystem for Linux with GUI: Please refer the following video  System Information: OS used: Windows 10 and WSL (Ubuntu 20.04) GUI: XServer for Windows NS3 Version: ns-3.33 See the following complete video on how to install ns3 in Windows 10 Step 0 : Open XLaunch Step 1 :  Open WSL using PowerShell and open it as Administrator Command:/  wsl $ xfce4-session The GUI of Ubuntu Opens within Windows 10 OS. Step 2 : Download ns3 from nsnam.org website through Mozilla Firefox browser Step 3: Open a Terminal  $ sudo apt update $ sudo apt install build-essential autoconf automake libxmu-dev python3-pygraphviz cvs mercurial bzr git cmake p7zip-full python3-matplotlib python-tk python3-dev qt5-q

Installing NS-3.32 in Ubuntu 20.04

This is about installing ns version 3.32 in Ubuntu 20.04 LTS. #ns3 #ns3 .32 #networksimulation The commands used in the video are given here. $] sudo apt update $] sudo apt install build-essential autoconf automake libxmu-dev python3-pygraphviz cvs mercurial bzr git cmake p7zip-full python3-matplotlib python-tk python3-dev qt5-qmake qt5-default gnuplot-x11 wireshark Download the ns-allinone-3.32.tar.bz2 package from nsnam.org and copy it to /home/ folder See the full video for detailed instructions Extract it either in GUI or using command $] tar jxvf ns-allinone-3.32.tar.bz2 $] cd ns-allinone-3.32/ $] ./build.py --enable-examples --enable-tests The above command will take some time to install all the packages  You can see the output as shown below ns3 To check whether ns3 installed successfully, use the following commands. $] cd ns-3.32/ $] ./waf --run hello-simulator You should get the output as Hello Simulator $] ./waf --run first This is the example from the ns-3.32/exa