Filetype PDF | Posted on 01 Feb 2023 | 3 years ago
Authentication
digital resources
422x Filetype PDF File size 1.61 MB Source: autonomous.anits.edu.in
Hall Ticket No: Question Paper Code :
ANIL NEERUKONDA INSTITUTE OF TECHNOLOGY & SCIENCES
(AUTONOMOUS)
II/IV B. Tech I- Semester Regular Examinations Oct - 2016
(Regulations: R15)
Data Structures & Algorithms
(CSE)
Time: 3 hours Max Marks: 60
Answer ONE Question from each Unit
All Questions Carry Equal Marks
All parts of the question must be answered in one place only
UNIT-I
1. (a) Define Data structure. List different operations performed on Data Structures. (2M)
(b) Identify the types of Data Structures suitable for the following scenarios
Scenario 1:Representing the list of Names of 10 students in a class
Scenario 2:Representing the following items
items: emp name, emp address, emp sal, emp age, dependants
emp: employee
note:
Group itemsElementary items
emp nameemp sal
emp address emp age
dependents
Scenario 3: A college bus moving between different routes in working days is as follows:
Route1(R1), Route2(R2), Route3(R3), Route4(R4), Route5(R5),
Represent the way through which the college bus moves between different stops
listedabove using an appropriate data structure.
(10M)
(OR)
2. (a) Define an algorithm. List out and discuss the sequence of steps needed to design and analyze
an algorithm in not more than four sentences each. (6M)
(b) Inspect, why do we need an Asymptotic notation. Explain the differentAsymptotic notations
with definition and example. (6M)
UNIT-II
3. (a)Prefix sum of a list X[N] is defined as the Sequence s of n elements, with sk = x1 + ... + xk. For
example, x = [1, 4, 3, 5, 6, 7, 0, 1] , s = [1, 5, 8, 13, 19, 26, 26, 27]
Write a program to compute the prefix sum of an array of integers and compute its time
complexity. (6M)
(b) You are given a set of n types of rectangular 3-D boxes, where the ith box has height
h(i),width w(i) and depth d(i) (all real numbers). You want to create a stack of boxes which
is as tall as possible, but you can only stack a box on top of another box, If the dimensions of
MODEL PAPER 1
the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher
box. Of course, you can rotate a box so that any side functions as its base. It is also allowable
to use multiple instances of the same type of box. (6M)
(OR)
4. (a) Explain operations of a stack with an example. (6M)
(b)Explain how an infix expression can be converted to a post fix expression with an example.
(6M)
UNIT-III
5 (a) Explain ADT of a queuewith an example. Implement queue using C. (8M)
(b)Explain Applications of a queue. (4M)
(OR)
6. (a) Explain and implement a single linked list with an example. (6M)
(b) What is a priority queue? Implement using a linked list. (6M)
UNIT-IV
7. (a) What is a binary tree give short notes on types of binary trees. (4M)
(b) Explain a Binary Search Tree(BST) with an example. (8M)
(OR)
8. (a) Explain hashing, hash table and a function. Explain with a example. (4M)
(b)Compare and analyse sequential search, binary search and interpolation search.Explain the
complexity of search algorithm. (4M)
(c) Explain selection sort with an example. Give its complexity. (4M)
UNIT-V
9. (a) What is a graph? Explain how graphs are represented. (6M)
(b) What is a spanning tree? Explain how minimal spanning trees are constructed with an
example. (6M)
(OR)
10.Explain in brief how shortest path iscalculated using Dijkstra’s algorithm. (12M)
******
MODEL PAPER 2
Hall Ticket No: Question Paper Code :
ANIL NEERUKONDA INSTITUTE OF TECHNOLOGY & SCIENCES
(AUTONOMOUS)
II/IV B. Tech I- Semester Regular Examinations Oct – 2016
(Regulations: R15)
Digital Logic Design
(Common for CSE and IT)
Time: 3 hours Max Marks: 60
Answer ONE Question from each Unit
All Questions Carry Equal Marks
All parts of the question must be answered in one place only
UNIT-I
1. (a) Perform the following arithmetic operations using 8-bit registers. Use binary signed
1’s complement notation, indicate overflow/underflow, if any (i) 29+ (-49) (ii) 27 -101
(iii) -28 + (-100) (iv) 68 + (-75). (8M)
(b). Design a full adder using two half adders and logic gates along with the logic
equations (4M)
(OR)
2. (a).Determine the logic required to decode the binary number 1011 by producing a
HIGH level on the output. (2M)
(b) Design a full subtractor and implement it using NAND gates. Explain its operation
with the help of a truth table. (4M)
(c). Simplify the following expressions: (6M)
(i)AB + A(B+C) + B(B+C)
Ì… Ì… Ì… Ì… Ì… Ì… Ì…
(ii)ABC + ABC + ABC + ABC + ABC
Ì… Ì…
(iii)ABC(BD+CDE) + AC
UNIT-II
3. (a). Minimize the following function in SOP form using k-map
F(A,B,C,D)= âˆ‘í µí±š(1,2,3,8,9,10,11,14)+ âˆ‘í µí±‘(7,15). (4M)
(b) Realize the above obtained Boolean function by using NOR gates. (4M)
(c) Draw the logic diagram of a 2- to- 4 line decoder using NAND gates and active
Low enable input and write a HDL module for the same. (4M)
MODEL PAPER 1
(OR)
4 (a) Use Karnaugh map, to realize the following POS expression,
Ì… Ì… Ì… Ì… Ì… Ì…
(A+B+C) (A+B+C) (A+B+C)(A+B+C) (A+B+C) (4M)
(b) Implement the resultant expression using NAND gates. (4M)
(c) Draw the logic diagram of a 2-to-4 line decoder with only NOR gates. Include
an enable input. (4M)
UNIT-III
5. (a) Realize an edge triggered J-K flip-flop with SET and RESET inputs using
NAND gates and explain its operation with truth table and waveforms. (6M)
(b) Show how a BCD ripple counter can be implemented. (6M)
(OR)
6. (a) Convert clock R-S flip-flop (FF) into
(i) JK F-F (ii) D-F-F (iii) T- F-F & Give the truth table for each. (6M)
(b) Explain different types of shift registers with neat diagrams. (6M)
UNIT-IV
7. (a) Write short notes about Races & Hazards. (6M)
(b) State Reduction & Assignment Problem. (6M)
(OR)
8. (a) State Reduction & Assignment Problem. (5M)
(b) Design a synchronous counter that goes through the sequence 2,6,1,7,5,4 and
repeat. Use JK flip. (7M)
UNIT-V
9 (a) Design a ROM size to realize the following logic functions 5 * 32 line decoder
& implement it. (6M)
(b) Draw a PLA circuit to implement the following functions and develop the
programming table.
F1 = A’B + AC’ + A’BC’
F2 = (AC + AB + BC)’ (6M)
(Or)
10. (a) Write short note on types of ROMs. What is the use of EEPROM? (4M)
(b) Design a PLA to realize the following functions show the internal connection
F (a,b,c,d,e)=a’b’d’ +a’cd’+a’bcde’; (8M)
1
F (a,b,c,d,e)=a’bc + b’cd’e;
2
F (a,b,c,d,e)=a’b’d’+b’cd’e +a’bcd.
3
***
MODEL PAPER 2
no reviews yet
Please Login to review.
