Vanithakiotcsehome.files.wordpress.com



EC8393 – FUNDAMENTALS OF DATA STRUCTURES IN CQUESTION BANKUNIT-11. What is character set?? The C Character set consists of upper and lower case alphabets, digits, special character and white spaces. The alphabet and digits are together called the alphanumeric characters.??Alphabets:??????????? A,B,C,D,E………………………X,Y,Z??????????? a,b,c,d,e………………………..x,y,z??Digits:???????? ?? 0,1,2,3,4,5,6,7,8,9??Special Character??? +? *& ^ % $ # @ ! ~ `? --? = > < .\ , : ;2. What is an identifier?? Identifiers are names that are given to various program elements such as variables, functions and arrays. Identifier consists of letters and digits, in any order, except that the first character must be a letter. Both upper and lower case letters are permitted though common usage favours the use of lower letters. The underscore is treated as a letter. Eg: ?int amount; double totalbalance;Here amount and totalbalance are identifiers. 3. What are keywords? Give example.?????? Keywords have fixed meaning and these meaning cannot be changed. These keywords can be used only for their intended purpose, they cannot be used as programmer-defined identifiers.???????????The following are examples of few keywords are predefined by Cauto?????? double????? ?????int??????? ?????struct?break??????? else???????????? if? ????????????switchcase????????? enum???????? ?do????? ???????while4. What is meant by declaration???Declaration is to represent a variable??Only variable name and its data type is represented in declaration.Eg: int a;5. Define global declaration?The variables that are used in more than one function throughout the program are called global variables and declared in outside of all the function that is before the main() function. Eg: int a=4; main() { printf(“%d”,a); }6. Define the term variable and constant.Variable:????????? A variable is a data name that is used to store a value. A variable may take different values at different times. A variable can be chosen by the programmer in a meaningful way. So as to reflect its function or nature in the program.Eg: int a1; Here a1 is a variable of integer type.city??? ???????????????college???? a1Total_mark????? Name?????? AvgConstant:? A constant is a value that does not change during the program execution. A constant used in C does not occupy memory.Eg: int a=10; float b=2.5; char a=’c’;Here 10, 2.5,’c’ is a constant.7. What are register variable???Variables are used as a local variable.??May be stored in register if possible.??Default initial value is garbage value.8. What is a character constant?A character constant is a single character, enclosed within the pair of single quotation mark. Eg: ‘x’ , ‘5’9. What is string constant??????????????????????? A string constant is a sequence of character enclosed in double quotes. The characters may be letters, numbers, special characters and blank space.Eg:? “Hello”, ”1987”, “WELL DONE”, “?.....!”, “5+3”, “X”10. What is an escape sequence??????? Some combinations of characters have the special functions such as \n, \t and \b. They are called as escape sequence.11. What is symbolic constant (pre-processor constant)???Names given to value that cannot be changed.??Implemented with the??#define?program directive??????????????????????Eg: #define N 300??Note that pre-processor statement begin with a # symbol, and semicolon before the program is actually compiled.??In general, pre-processor constant are written in ‘UPPER CASE’.12. Define Datatype and its types.Data types?are declarations for?memory locations?or?variables?that determine the characteristics of the data that may be stored and the methods.Types:Basic data typeschar, int, float, double, voidDerived data types-Array, pointer, functionUser-defined data typesstructure, union, enumeration13. Define the term pointer data type.?????????????????????? A pointer is a variable that represent the location (rather than the value) of a data item, such as a variable or an array element. It is a variable that holds a memory address. This address is the location of another variable or an array element in memory.Eg:?int *p; char *p;14. List the four types of type modifiers.???????short???????long???????signed???????unsigned15. What is an expression in C language?Expression is defined as a combination of operand and operator to obtain some computation. Operands represent variable or values and the operator tells hat operation is to be performed. Eg: c=a+b;Here c=a+b is an meaningful expression.16. What is an Operator and Operand?An operator is a symbol that specifies an operation to be performed on operands. Eg: *,+,-,/ are called arithmetic operators.The data items that operators act upon are called operands.Eg: a+b; In this statement a and b are called operands.17. What is an unary operator? Give example.??????????? The operators that act upon a single operand to produce a new value is known as unary operator.Eg: minus operator(-) ,Increment operator (++),Decrement operator(--), !, &, ~ b=-a; b=++a; b=~a;18. List out the operator types???????????? In C operator can be classified into various categories based on their utility and action, a list operator types are given below???Arithmetic operators???Relational operators???Logical operators???Bitwise operators???Assignment operators???Increment operators???Conditional operators???Comma operators???Other operators19. What is Relational Operator in C????? The relational operators are used to compare arithmetic, logical and character expressions. Each of these operator compares their left hand side with their right hand side. The whole expression involving the relational operator then evaluates to an integer. It evaluates to zero if the condition is false, and one if it is trueOperatorMeaning<?Less than>?Greater than<=Less than or equal to>=Greater than or equal to==Equal to!=Not equal toEg: c=a<b;c=a!=b;20. What are logical operators??????? A logical operator is used to compare or evaluate logical and relational expressions. There three logical in C language. They areOperatorMeaning&&AND||OR!NOTEg: a=(a==b)&&(c>b);d=(a>b)||(a>c);21. What are bitwise operators?????????????????? The bitwise operator performs the operation on bits (i.e, bit by bit). Using the bitwise operators we can set/ reset/ check any bit in the value of the variable. OperatorMeaning&|^<<?>>?Bitwise ANDBitwise ORBitwise XORShift leftShift right Eg: a&b a|b a^b22. What is the purpose of conditional operator????? The conditional operator consists of two symbols the question mark (?) and the colon (:). The conditional expression of the form?????? Syntax: variable =?exp1?exp2:exp3;????????????????????????????????????????????????????????????? ??????????????conditional expression?where exp1 is test expression, exp2 is expression or constant or variable, exp3 is expression or constant or variable.Eg: b=(A > 100 ?? ?0 ?: ?1);23. What is purpose of comma operator?A set of expression separated by commas is a valid construct in the C language. Eg:? int i,j;??????????? The comma operator also used to link the related expression together. A comma linked list of expression is evaluated left to right and the value of right-most expression is the value of the combined expressions.24. Discuss the types of I/O statements available in C. Unformatted I/O functions a) getchar()b) putchar() c) gets()d) puts()e) getch()f) getche()Formatted I/O functionsa) scanf()b) printf()25. Specify the use of printf( ) and scanf( ) functions.??The scanf() function can be used to enter any combination of data, like single character, string, integer and float values. The general format of the scanf() function is scanf(“format specifier “, &arg1,&arg2,……………..,&argn);where format specifier string contains certain required formatting information, and arg1, arg2….argn are arguments that represent the individual input data item. Eg: scanf(“%d%d”,&a,&b);??It is used for formatted output to standard output device,( screen) . The format specification contains string and the data to be output, as the arguments(parameter) to the printf() function.Syntax: printf(“message format specifier”,var1,var2,..varn);Eg: printf(“a=%d,b=%d”,a,b);26. What is the purpose of getchar() function?? It returns a character just entered from the standard input unit that is keyboard. The entered character can be either assigned to a character variable or enclosed to the computer screen.Syntax: getchar(variable_name);27. What is use of gets( ) function????? The gets( ) function is used to accept a string.Syntax: gets(variable_name);28. What is the purpose of putchar( ) function??????????????????????? The putchar( ) function display one character on the display monitor. The character to be displayed is of type char??????????????????????????????????Syntax:? putchar(variable);29. Give the syntax of if-else statement.The if-else statement performs one of the two possible actions. The general format isif(test expression)? {???? true-statement block;?? }else? {???? false-statement block;?? }next statement.30. Write the syntax for switch() statement.switch(expression)? {????? case value-1:?????????????????????????????? Block-1;?????????????????????????????? Block-2;????? ………….?? ???………….????? default:??????????????????????????????? default block;?????????????????????????????? break;??? }statement-x;31. Mention the use of ‘break’ and ‘continue’ statements.??The break statement is used to terminate the loop containing it.??The continue statement does not terminate the entire loop but is used to terminate the current iteration of the loop. Syntax: break; continue;32. What is a looping??????? A looping is a process to do a job repeatedly with possible different data at each time. The statements executed each time constitute the loop body, and each pass is called iteration. A condition must be present to terminate the loop.33. Write the syntax of while statement in C.?????????????????????????????? The general format of the while statement iswhile(test_condition){??? Body of the loop;?}34. Specify the syntax used for ‘for’ statement.???? The for loop is entry controlled loop the provides a more concise loop control structure. The general format of the loop isfor(intilialization;testcondition;increment/decrement){???? Body of the loop;?}Eg: for(i=1;i<=10;i++)35. Write a note on do-while statement.??????????? In the do statement, the program proceeds to execute the body of the loop first. At the end of the loop the test condition is evaluated. If the condition is true, the program continues to execute the body of the loop. This process continues as long as the condition is true.do{??? Statement;?}while(test_condition);36. Difference between while and do-while.whiledo-whileIn ‘while’ loop the controlling function appears at the start of the loop.In 'do-while' loop the controlling condition appears at the end of the loop.The iterations do not occur if, the condition at the first iteration ,appears false.The iteration occurs at least once even if the condition is false at the first iteration.37. Define an array.??Array is the collection of elements.??Collection of the elements of the same data type.??All elements are stored in the contiguous memory locations.Syntax: data_type array_name[array_size];Eg: int data[100];38. How to declare multidimensional array????? Two dimensional array follows row major order storage representation. The elements are stored in row by row in the subsequent memory locations.Syntax: data_type array_name[i][j]; Eg: float x[3][4];Here i represent the rows, j represent the column.39. What is a string?? A string is a sequence of characters ending with NULL. It can be treated as a one-dimensional array of character terminated by a NULL character.Eg: char a[10]=”success”; char a[10]={‘s’,’u’,’c’,’c’,’e’,’s’,’s’};40. Distinguish between high level Language and low level language.LOW LEVELHIGH LEVELLow level language (LLL) is machine readable form of program.High level language will be in human readable form.LLL are difficult to write and compile.HLL are easy to write and compile.LLL are compact and require less memory space.HLL uses compilers and interpreters which requires large memory space.Eg: Assembly Language , Machine code, Compiler?Eg: C, C++, Java, BASIC FORTRAN, and Pascal, Python, Visual BasicPART-BDescribe the structure of a C program with an example. What is a two dimensional array explain its initialization.Describe the various types of operators in ‘C’ language along with its priority.4. List and explain the various data types in C.5. Explain about the various decision making and branching statements.6. Write short notes on the following: (a) ‘for’ loop (b) ‘while’ loop (c) ‘do while’ loop7. Analyze the various String functions with example.8. Develop a C program for the following: i) To find the area and circumference of the circle. ii) To find the sum of 100 integers.9. i) Write a C program to find whether the given is leap year or not. ii) Write a C program to find whether the given number is palindrome or not.10. Write a C program to perform the matrix operations.11. Write a C program To check whether a number is prime or not.12. Write a C program to search an element from the array.13. Explain the various types of constants with example.14. Describe the Unformatted I/O and formatted functions.UNIT-II1. What are function??????? A function is a set of statement to perform a specific task.2. Write the general form of structure of C functions.??????????? A C program basically has the following formo???pre-processor commandso???type definitionso???function prototypeo???variable declarationo???function body3. What are automatic variable????????????Variables that used as a local variable inside any function. This is the default one. Initial value of variable is garbage value without initialization. Auto keyword is used to declare automatic variable.Eg: auto int a=20;4. Specify the role of static variables.??If you declare within a function, It retains the value between function call.??If it is declare a for a function name. It will be visible from other files if the function declaration is as static.??Static are global variables. By default we can use the global variables from outside files if it is static global. Syntax: static data_type var_name = var_value;Eg: static int a=10;5. Define scope of variables.?????????????????????? Scope refers to the visibility of variables of it is declared outside of any function declaration, it is a global variable. If it is declared inside of any function declaration, it is a local variable.6. Mention the two categories of function.????????Library function????????User – Defined function7. What are library functions?The function that are predefined and supplied along with the compiler are known as built in functions. They are also known as library function.Eg: #include<file_name.h>8. What are user-defined fuctions?User-defined functions are defined by the user at the time of writing a program.Eg: addNumbers()9. What are function prototypes?A function declaration is also called as function prototype consists of four parts.??Function type(return type)??Function name??Parameter list??Terminating semicolonSyntax: returnType functionName(type1 argument1, type2 argument2,...);10. Define actual parameters.?????? Actual parameters are used for passing values or address from the calling function to a function being called.Eg:void main()6369981861986362701854200{Actual parameterint n;display(n);}void display(int p){ }11.?What are formal arguments??????? The formal parameters are used to collect values or address from the calling function to a function being called.13144501822450Eg: int factorial(int n)1314450660400{ Formal parameter (Here n is the formal argument)????// write logic here} 12. Define Pass-by-reference.The method of passing arguments by address is also known as call by reference. In this method, the addresses of the actual arguments are passed to the formal parameters of the function. If the arguments are passed by reference, the changes made in the values pointed to by the formal parameters in the called function are reflected back to the calling function.13. Define Pass-by-value.Pass by value or Call by value is the method where copies of the value of the variables are passed to the function to do specific operation to return the result. The actual values of the variable remains unchanged as changes are made to the copied values of the variables.14. Define the term recursion.???? A function may call another function. When a function calls itself, it is referred to as recursive call the process is known as recursion. C provides very good facilities for recursion.15.?What is recursive function? Give an example.Recursive function is a function which contains a call to itself.Eg:?????? int factorial(int n)?????? {?????????? if(n==0)????????????? return(1);?????????? else????????????? return(n*factorial(n-1));?????? }16. What are the advantages of functions????It reduces the complexity in a program by reducing the code.???Functions are easily understandable ?and execution is faster.???It also reduces the time to run a program.???It’s easy to find-out the errors due to the blocks made as function definition outside the main function.17. Define pointer.A pointer is a variable whose value is the address of another variable, i.e., direct address of the memory location. Like any variable or constant, you must declare a pointer before using it to store any variable address. Eg: int *p;18. How to declare pointer variable??????? A pointer declaration consists of a base type, an *, and the variable name. The general form for declaring a pointer variable is???????????data_type *var_name;Eg:?int? *p;19. Write the advantages of pointer.Pointer is used in the following cases.??It is used to access array elements.??It is used for dynamic memory allocation.??It is used in call by reference.??It is used in data structure like trees, graph, etc.20. What is a structure? Structure constitutes a super data type which represents several different data types in a single unit. A structure can be initialized if it is static or global.Syntax:struct [structure tag] {member definition;member definition;---member definition;}[one or more structure variables];Eg:struct books {char title[50];char author[50];char subject[100];int book_id;} book;21. Define nested structure.Structure within Structure: Nested StructureStructure written inside another structure is called as nesting of two structures.Nested Structures are allowed in C Programming Language.We can write one Structure inside another structure as member of another structure. Structure within structure in C using normal variable and also pointer variable.Eg: struct?address???{?? char?city[20];??int?pin;??char?phone[14];??};??struct?employee??{??char?name[20];???struct?address?add;??};??22. What is a union?Union is a collection of heterogeneous data type but it uses efficient memory utilization technique by allocating enough memory to hold the largest member. Here a single area of memory contains values of different types at different time. A union can never be initialized.Syntax:union[union tag] {member definition;member definition;…member definition;} [one or more union variables];Eg:union data {int i;float f;char str[20];} data;23. What are the differences between structures and union?StructureUnionStructure keyword is used to define the structure type.Structure keyword is used to define the union type.Memory is allocated for each member.Memory is allocated as per largest member.Each member have the own independent memory.All field share the same memory allocation.We can any member any timeWe can access only one field at a time.Altering the value of the member does not affect the value of the other member.Altering the value of the member affect the value of the other member.Flexible array is supported by the structure.Flexible array is not supported by the union.24. What are the differences between structures and arrays?StructureArraystruct keyword is used.No keyword.Structure is the collection of heterogeneous data.Array is collection of homogeneous data.Elements of structure will be accessed by . operator.Elements of array will be accessed using index stating from 0 to n-1.e.g. struct student{int roll;char name[10];}s;e.g. int a[5]={10,45,67,43,23};25. What is the difference between function definition and function declaration?Function definitionFunction DeclarationIt has function header and function body.It has only function header ending with semicolon.A function can only be defined onceIt can be declared many times.A function but cannot be defined within the body of some other function.It can be declared within the body of some other functionThe function definition serves as a function declaration if it is present before the function call.The function declaration cannot be served as a function declaration.e.g. void example(){….}e.g. void example();PART-B1. Write in detail about function declaration, function definition and function call. 2. Explain in detail about Pass by Value and Pass by reference. 3. Explain in detail about recursive function with example program. 4. Explain about structures and union in detail. 5. Write a C program using structures to prepare the students mark statement. 6. Write a C program using unions to prepare the employee pay roll of a company. 7. Write a C program to find the factorial of a given number. UNIT – IIILINEAR DATA STRUCTURESDefine data structures? A data structure is a mathematical or logical way of organizing data in the memory that consider not only the items stored but also the relationship to each other and also it is characterized by accessing functions.Give few examples for data structures? Stacks, Queue, Linked list, Trees, graphsWhat is meant by an abstract data type (ADT)? An ADT is a set of operation. A useful tool for specifying the logical properties of a data type is the abstract data type. ADT refers to the basic mathematical concept that defines the data type.Ex. Objects such as list, set and graph along their operations can be viewed as ADT's.What is meant by list ADT? List ADT is a sequential storage structure. General list of the form a1, a2, a3.…., an and the size of the list is 'n'. Any element in the list at the position i is defined to be ai, ai+1 the successor of ai and ai-1 is the predecessor of ai. What are the two parts of ADT?? Value definition? Operator definitionDefine Polynomial ADT.A polynomial object is a homogeneous ordered list of pairs <exponent, coefficient>, where each coefficient is unique. Operations include returning the degree, extracting the coefficient for a given exponent, addition, multiplication, evaluation for a given input.What is an array? Array may be defined abstractly as a finite ordered set of homogenous elements. Finite means there is a specific number of elements in the array.What are the two basic operations that access an array? Extraction operation is a function that accepts an array, a , an index, i, and returns an element of the array. Storing operation accepts an array, a , an index i , and an element x.Give some examples for linear data structures? ? Stack ? QueueWhat is a Stack? (Nov/Dec 2010)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. The other name of stack is Last-in -First-out list.Name two applications of stack?Stack is used to explain the processing of subroutine calls and their returns.Recursive procedures and evaluation of expressions can be implemented using stack.What are the two operations of Stack? (Nov/Dec 2010) ? PUSH ? POPWhat is a Queue? A Queue is an ordered collection of items from which items may be deleted at one end called the front of the queue and into which terms may be inserted atthe other end called rear of the queue.Queue is called as first–in-First- Out (FIFO).What are the various operations performed on the Queue?CREATEQ (Q) – Create Q as an empty QueueADDQ (I, Q) – adds the element I to the rear of a queue and returns the new queue.DELETEQ (Q) – remove the front element from the queue Q and returns the new queue.FRONT (Q) – returns the front element of QWhat is Dequeue? (Nov/Dec 2009)Dequeue is a double-ended queue. It is an?abstract data type?that generalizes a?queue, for which elements can be added to or removed from either the front (head) or back (tail).?It is also often called a?head-tail linked list to a specific?data structure. The differs from the queue abstract data type or First-In-First-Out List (FIFO), where elements can only be added to one end and removed from the other. What is a Priority Queue? A Queue in which we are able to insert items or remove items from any position based on some priority is after referred to as a priority Queue.Ascending and descending priority queue are the two types of Priority queue.What are the applications of priority queues??The selection problem?Event simulationWhat are the different ways to implement list? ? Simple array implementation of list ? Linked list implementation of listWhat are the advantages in the array implementation of list?a) Print list operation can be carried out at the linear timeb) Find Kth operation takes a constant time What is a linked list? Linked list is a kind of series of data structures, which are not necessarily adjacent in memory. Each structure contains the element and a pointer to a record containing its successor.21. What is a doubly linked list? In a simple linked list, there will be one pointer named as 'NEXT POINTER' to point the next element, where as in a doubly linked list, there will be two pointers one to point the next element and the other to point the previous element location. 22. Define circularly linked list.Circular Linked List?is a Linked list?in which the first element points to the last element and the last element points to the first element. Both Singly Linked List?and Doubly?Linked List?can be made into a?circular linked list.What is the advantage of using doubly linked list over singly linked list? (Apr/May 2011)Insertion and deletion is easy. Two way traversing is possible What are the postfix and prefix forms of the expression? (Nov/Dec 2011) A+B*(C-D)/(P-R) Postfix form: ABCD-*PR-/+ Prefix form: +A/*B-CD-PRPART B 1.(i)Explain the insertion and deletion operation in Stacks (ii)Describe the various applications of stack 2. Describe Queue and its operation with suitable example.3. Explain about Linked list , its Types ,insertion and deletion routines with suitable example. 4. (i)Write about Linked list implementation of Stacks (ii) Explain the array implementation of Stacks5. Write routines for evaluating an infix expression. (16) (JUN 06) UNIT – IVNON-LINEAR DATA STRUCTURES1. Define non-linear data structure? Data structure which is capable of expressing more complex relationship than that of physical adjacency is called non-linear data structure.Eg: Tree,Graph2. Define tree.A?tree?is a?data structure?where a node can zero or more children. Each node contains a value.?3. What is a Binary tree? (Nov/Dec 2011)A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children. The first subset contains a single element called the root of the tree. The other two subsets are themselves binary trees called the left and right sub trees.4. What are the applications of binary tree? Binary tree is used in data processing. a. File index schemes b. Hierarchical database management system5. What are the two methods of binary tree implementation? Two methods to implement a binary tree are,a. Linear representation.b. Linked representation6. Define a full binary tree? Define a complete binary tree? A full binary tree is a tree in which all the leaves are on the same level and every non-leaf node has exactly two children.?A complete binary tree is a tree in which every non-leaf node has exactly two children not necessarily to be on the same level.7. Define a right-skewed binary tree?A right-skewed binary tree is a tree, which has only right child nodes.8. State the properties of a binary tree??The maximum number of nodes on level n of a binary tree is 2 n-1, where n≥1.?The maximum number of nodes in a binary tree of height n is 2 n-1, where n≥1.?For any non-empty tree, n l =nd +1 where n l is the number of leaf nodes and nd is the number of nodes of degree 2.9. What is meant by traversing? What are the different types of traversing? Traversing a tree means processing it in such a way, that each node is visited only once.The different types of traversing area. Pre-order traversal- (root-left-right) yields prefix form of expression.b. In-order traversal- (left-root-right) yields infix form of expression.c. Post-order traversal- (left-right-root) yields postfix form of expression.10. What is meant by binary tree traversal? What are the different binary tree traversal techniques available?Traversing a binary tree means moving through all the nodes in the binary tree, visiting each node in the tree only once. The different traversal techniques are,Preorder traversalIn order traversalPost order traversalLevel order traversalDefine Binary Search tree.A binary search tree (BST), also known as an ordered binary tree, is a node-based data structure in which each node has no more than two child nodes. Each child must either be a leaf node or the root of another binary search tree. The left sub-tree contains only nodes with keys less than the parent node; the right sub-tree contains only nodes with keys greater than the parent node.State the properties of binary search tree. (Nov/Dec 2010)Binary Search Tree?is a node-based binary tree data structure which has the following properties:The left subtree of a node contains only nodes with keys lesser than the node’s key.The right subtree of a node contains only nodes with keys greater than the node’s key.The left and right subtree each must also be a binary search tree.13. When does a binary tree become a binary search tree? (Apr/May 2011)Binary tree is a tree data structure in which each node has at most two child nodes. A binary search tree (BST) is based on binary tree, but with the following additional properties: The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees.14. Define Graph? A graph G consist of a non-empty set V which is a set of nodes of the graph, a set E which is the set of edges of the graph, and a mapping from the set for edge E to a set of pairs of elements of V. It can also be represented as G= (V, E).Name the different ways of representing a graph?a. Adjacency matrixb. Adjacency listWhat are the two traversal strategies used in traversing a graph?a. Breadth first searchb. Depth first searchWhat is an acyclic graph? What is a simple graph? A simple graph is a graph, which does not have more than one edge between a pair of nodes. A simple graph which does not have any cycles is called an acyclic graph.What is a directed graph? What is an undirected graph? A graph in which every edge is directed is called a directed graph. A graph in which every edge is undirected is called a undirected graph.19. What is a weighted graph? A graph in which weights are assigned to every edge is called a weighted graph.20. Define degree of the node? Define leaves?The total number of sub-trees attached to that node is called the degree of the node. Leaves are the terminal nodes of the tree. The nodes with degree 0 are always the leaves. Define outdegree of a graph? (Nov/Dec 2011) In a directed graph, for any node v, the number of edges which have v as their initial node is called the out degree of the node v. 110960931029ABC0ABCOutdegree of Node A - 2 Node B - 0 Node C - 11202076636999ABC00ABC22. Define indegree of a graph? In a directed graph, for any node v, the number of edges which have v as their terminal node is called the in degree of the node v. Indegree of Node A - 0 Node B - 2 Node C - 123. Define path in a graph? What is a simple path? The path in a graph is the route taken to reach terminal node from a starting node. A path in a graph is said to be simple if the edges are distinct. e.g Source : node bDestination: node c24. What is an undirected acyclic graph? When every edge in an acyclic graph is undirected, it is called an undirected acyclic graph. It is also called as undirected forest.25. What is a minimum spanning tree? (Apr/May 2011) A?minimum spanning tree?(MST) or?minimum?weight spanning tree?is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum?possible total edge weight.?26. What is a minimum cost spanning tree? If we have connected undirected graph with a weight (or cost) associated with each edge. The cost of a spanning tree would be the sum of the costs of its edges. It is a spanning tree that has the lowest cost.27. When does a graph become tree? (Nov/Dec 2009)A graph can be a tree if it is acyclic. That is, if there is one and only one route from any node to any other node. A tree is a special kind of graph follow a particular set of rules. A graph can be a tree if is connected. That is, if each of the nodes is connected with a link to at least one other node. If a node is not connected to some other node, then the assembly is not a tree.28. What is meant by an adjacency matrix? (Nov/Dec 2010)An?adjacency matrix?is a?matrix?which describes a?graph?by representing which?vertices?are adjacent to which other?vertices. Specifically, the adjacency matrix of a?finite?graph?G?on?n?vertices is the?n × n?matrix where the non-diagonal entry?aij?is the number of edges from vertex?i?to vertex?j, and the diagonal entry?aii, depending on the convention, is either once or twice the number of edges (loops) from vertex?i?to itself. 29. Explain Breadth First Search and Depth-First search.Breadth-first-search?(BFS) is an?algorithm?for traversing or searching tree or graph?data structures. It starts at the?tree root?, sometimes referred to as a 'search key', and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.DFS and BFS are common methods of graph traversal, which is the process of visiting every vertex of a graph.BFS: 1 3 2 6 5 4 7 DFS:1 3 6 5 7 2 4PART-B1.Convert the expression ((A + B) * C - (D - E) ^ (F + G)) to equivalent Prefix and postfix notations. ( MAY 2010)2.Discuss the different methods of traversing a binary tree with algorithm3.Write a non-recursive and recursive algorithm for in order tree traversal4. Explain how arithmetic expressions are manipulated using binary trees. Illustrate with example. 5. Define a BST. Write a routine to insert a node into a BST. (8) (Nov 06)6. Examine any one of the graph traversal algorithms with an example. (Apr 19)UNIT V SORTING AND SEARCHING1. How does binary search works? A binary search or half-interval search algorithm is a type of searching algorithm which starts with the middle of a sorted list, and see whether that's greater than or less than the value we're looking for, which determines whether the value is in the first or second half of the list. Jump to the half way through the sub list, and compare again etc. A binary search is a dichotomic divide and conquer search algorithm.2. What is linear search? What are its applications?Linear search or sequential search is the simplest search algorithm; It is a method for finding a particular value in a list that consists of checking every one of its elements, one at a time and in sequence, until the desired one is found. This results in O(n) performance on a given list of size n. Linear search is usually very simple to implement, and is practical when the list has only a few elements, or when performing a single search in an unordered list.3. Compare linear search and binary search.Linear SearchBinary SearchThe elements are in random orderThe elements are in sorted orderWorst case time complexity O(n)Worst case time complexity O(log2N?)Access is slowAccess is fasterSingle and multi-dimensional array is usedOnly single dimensional array is usedIt can be implemented on Array and linked listIt cannot be directly implemented on linked listNot an efficient method to be used if there is a large listEfficient for large inputs 4. List some of the reasons for choosing linear search over binary search.? The list is unsorted, small and is only to be searched once ? The list will need sorting following the search operation (due to say an insertion), since the resorting will dominate the time complexity of the overall task ? The data structure is not random access (like a linked-list) ? There is no knowledge of the data that could aid searching5. What is the best case, worst case & average case performance of binary search algorithm. Worst case performanceO(log n) Best case performanceO(1) Average case performanceO(log n) Worst case space complexityO(1)6. Why binary search algorithm does not work on an unsorted array?The binary search algorithm works by successively halving the array and determining in which half the desired result lies. In order for that to work the array must be sorted otherwise choosing the halfway point would be meaningless because it would not tell you in which half if the array the result is located.7. List some of the disadvantages of binary search.Binary search interact poorly with memory hierarchyIt employs recursive approach and so requires more stack space.Programming binary search algorithm is very difficult and error prone.8. What is meant by sorting? (Nov/Dec 2010) Ordering the data in an increasing or decreasing fashion according to some relationship among the data item is called sorting.9. What are the two main classifications of sorting based on the source of data? a. Internal sorting b. External sorting10. What is meant by internal sorting? Internal sorting is a process of sorting the data in the main memory.Eg: Insertion sort, quick sort, heap sort, radix sort 11. What is meant by external sorting?We can use an external sort when the collection of data cannot fit in the computer’s main memory all at once but must reside in secondary storage such as on a disk.Eg: Quicksort,mergesort12. List some of the sorting algorithms.There are many sorting algorithms, such as:Selection Sort Insertion SortBubble SortMerge SortQuick Sort13. What are the various factors to be considered in deciding a sorting algorithm? a. Programming time b. Execution time of the program c. Memory needed for program environment14. What is insertion sort? How many passes are required for the elements to be sorted? It is the most common sorting technique used by card players. Insertion sort consist of N-1 passes. For pass P=1 through N-1, insertion sort ensures that the elements in positions 0 through P-1 are in sorted order. It makes use of the fact that element in position 0 through P-1 are already known to be in sorted order.15. Write the function in C for insertion sort ? Void insertionsort(elementtype A[ ] , int N) { int j, p; elementtype tmp; for(p=1 ; p <N ;p++ ) { tmp = a[ p] ; for ( j=p ; j>0 && a [ j -1 ] >tmp ;j--) a [ j ]=a [j-1 ] ; a [ j ] = tmp ; } }16. What is the best case ,worst case & average case running time for insertion sort.Running time depends on not only the size of the array but also the contents of the array Best case O(n) Worst case O(n^2) Average case O(n^2)17. What is divide and conquer strategy? Name the sorting algorithms that work on divide and conquer approach?In divide and conquer strategy the given problem is divided into smaller problems and solved recursively. The conquering phase consists of patching together the answers. The algorithms that work on divide and conquer approach are, 1. Quick sort. 2. Merge sort18. How merge sort algorithm works?Merge sort is a fine example for recursive algorithm. Merge sort algorithm is one of two important divide-and-conquer sorting algorithms..Divides the list into halves, Sort each halve separately, and Then merge the sorted halves into one sorted array.The worst case and average case running times of merge sort are O (n * log2n )19. How quick sort algorithm works?Quick sort is based on divide and conquer approach. It works as follows.1. Divide: Partition the list.To partition the list, we first choose some element from the list for which we hope about half the elements will come before and half after. Call this element the pivot. Then we partition the elements so that all those with values less than the pivot come in one sublist and all those with greater values come in another.?2. Recursion: Recursively sort the sublists separately.?3. Conquer: Put the sorted sublists together. 20. Mention some methods for choosing the pivot element in quick sort? 1. Choosing first element 2. Generate random number 3. Median of three21. What is the best case ,worst case & average case running time for quick sort. Best case O (n log n) Worst case O (n^2) Average case O (n log n)22. Differentiate between merge sort and quick sort? Merge sort Quick sort 1. Divide and conquer strategy Divide and conquer strategy 2. Partition by position Partition by value23. What are the three cases that arise during the left to right scan in quick sort? 1. I and j cross each other 2. I and j do not cross each other 3. I and j points the same position24. Which is the fastest sorting algorithm in practice? What is the average and worst case running time of it? (Apr/May 2011)The fastest algorithm is the Quick sort algorithm Average case: o (N log N) ; Worst case: o (N2)Define Hash Table.A hash table ( hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.Define overflow handling.When new data is to be inserted into the data structure but there is no available space i.e. free storage list is empty this situation is called overflow. Several methods of handling overflow: Avoidance, Handling, Propagation PART B1. Sort the following values using quick sort and calculate the time and space complexity. 65 70 75 80 60 55 50 45 Illustrate each step of sorting process (DEC 2013)2. Explain how divide and conquer technique is applied to merge sort (MAY 2013)30,10,49,34,69,12,96,53,2,43,803. Explain binary search technique with example.4. Describe the concept of quick sort with example.5. (i)Write a ‘C’ program to implement binary search and compute its complexity. (8) (ii) Compare the worst case and best case time complexity of various sorting techniques.(DEC 2009)6. Analyze the functionality of hash tables and hashing functions in storing and retrieving data efficiently.7.Apply bubble sort and selection sort algorithms to sort a given set of nmbers. ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download