KIET Group of Institutions Data Structures PDF

 Roll No. ----------------------------------- KIET Group of Institutions...

 Roll No. ----------------------------------- KIET Group of Institutions PUE-1 (2023-2024) ODD Semester Department: CSE/CS/CSIT/IT/CSE(AI)/CSE(AI&ML) Course: B. Tech. Year: 2nd Semester: 3rd Subject Name: Data Structures Subject Code: BCS301 Duration: 3 Hrs Max. Marks: 70 Note: Attempt all the questions of each section. Section-A (10X2=20) Q. No. Question Competitive Exam# CO BL/ KC* Compute the space complexity of an algorithm that uses two nested a 4 2/C loops, each loop is running n times. b Derive the index formula for a 3D array stored in column-major 1 3/C order with dimensions p, q, and r. c Construct a circular linked list with elements: 5  7  9  11, and 1 3/C perform deletion operation on first node. d Calculate the time complexity of an algorithm to find the sum of ‘n’ 4 3/P elements using Big Theta notation. e Compute multiplication of two single-variable polynomials: 1 3/C (P(x) = 3x^3 + 2x^2 - 5x + 7) and (Q(x) = 2x^2 - x + 1). 1. f Determine the number of elements in a sparse matrix representation in memory using 2D array with 6 rows and 5 columns having only 4 1 3/P non-zero elements in optimize manner. g Describe the process of deletion of a node in a doubly linked list. 1 2/C h Discuss any one linear and one non-linear data structure stating the 2 2/C application area where they will be used. i Compute the result of a Postfix expression: 5 3 2 ∗ + 2 3/P j With the help of an example, derive the relationship in the time- space trade-off for an algorithm that uses additional memory to 4 3/C decrease its runtime. Section-B (5X4=20) Competitive BL/ Q. No. Question CO Exam# KC* Apply the quick sort algorithm to sort the given array: AKTU201 [5, 2, 9, 1, 7, 6]. 9-20 2 OR 3 3/C Apply Radix sort algorithm to sort the given list of integers: AKTU [47, 23, 69, 101, 81, 16, 30]. 2021-22 Construct a binary tree using array representation and perform the AKTU201 operations of insertion, deletion, and searching by taking an example. 9-20 3 OR 2 3/P Apply the concept of binary trees to construct an expression tree for the Postfix expression: 3 4 + 5 × 6 −. Analyze when collision resolution techniques are applicable and how these are used in hashing. Apply linear probing to a set of given keys by taking an example. 4 OR 3 4/C Examine merits and demerits of Merge Sort. If two arrays of integers AKTU201 are given in ascending order, then develop an algorithm to merge 9-20 these arrays to form a third array sorted in ascending order. Demonstrate a queue using an array and perform enqueue and 5 2 3/P dequeue operations on it.  CO -Course Outcome generally refer to traits, knowledge, skill set that a student attains after completing the course successfully.  Bloom’s Level (BL) - Bloom’s taxonomy framework is planning and designing of assessment of student’s learning.  Knowledge Categories (KCs): F-Factual, C-Conceptual, P-Procedural, M-Metacognitive  Roll No. ----------------------------------- OR Demonstrate a priority queue using an array and perform enqueue and dequeue operations on priority queue. Analyze the time complexity of merge sort and heap sort algorithms for sorting an array of n elements. 6 OR 3 4/C Analyze the operations to search the elements 17 and 20 using sequential search on a given array: [12, 25, 8, 17, 33, 56, 29]. Section-C (5X6=30) Competitiv BL/ Q. No. Question CO e Exam# KC* Discover the way to find minimum numbers of steps for solving the AKTU Tower of Hanoi problem with n disks using recursion. 2021-22 OR 7 Derive algorithm for Push and Pop operations in a stack. Convert the 2 3/P following infix expression into its equivalent post expression using AKTU stack: 2019-20 A+(B*C-(D/E^F)*G)*H Suppose a 3D array is declared using A[1:10, 2:10, 1:15] Compute the following: (i) Find the length of each dimension and number of elements in A. (ii) Find Physical address of A[5,4,3]. Is it same for Row major 8 1 3/P order. OR Demonstrate the representation of polynomial of single variable AKTU using linked list. Write pseudo code to add two such polynomials 2021-22 represented by linked list. A hash function H defined as H(k)=k % 9 with linear probing is used to insert the keys 37, 38, 72, 48, 98, 11, 66 in to a table indexed from AKTU 0 to 8. Figure out the location of index 11. Also count the total 2020-21 number of collisions in this probing. 9 3 3/P OR Apply the merge sort algorithm to sort the following elements in AKTU ascending order. 13, 16, 10, 11, 4, 12, 6, 7. Also derive the time and 2021-22 space complexity of merge sort. Derive the step by step process for searching an element in a binary AKTU search tree. Analyze the complexity of searching an element in a 2021-22 BST. OR Compute the following: 10 (i) The keys 12, 17, 13, 2, 5, 43, 5 and 15 are inserted into an initially 2 3/P empty hash table of length 15 using open addressing with hash AKTU function h(k) = k mod 10 and linear probing. Draw the resultant 2021-22 optimized hash table. (ii) Describe the working difference between linear and quadratic probing techniques with suitable example. Analyze the performance of Double Ended Queue to insert an element and delete an element. OR 11 2 4/P Analyze the working of Insertion sort and Quick sort for the given input sequence “B, A, D, C, E”. Do you find any similarity in the algorithm, or both are different? Justify.  CO -Course Outcome generally refer to traits, knowledge, skill set that a student attains after completing the course successfully.  Bloom’s Level (BL) - Bloom’s taxonomy framework is planning and designing of assessment of student’s learning.  Knowledge Categories (KCs): F-Factual, C-Conceptual, P-Procedural, M-Metacognitive  Printed Page: 1 of 2 Subject Code: KCS302 0Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0 BTECH (SEM III) THEORY EXAMINATION 2021-22 COMPUTER ORGANIZATION AND ARCHITECTURE Time: 3 Hours Total Marks: 100 Note: Attempt all Sections. If you require any missing data, then choose suitably. SECTION A 1. Attempt all questions in brief. 2x10 = 20 Qno Questions CO (a) List and briefly define the main structural components of a computer. CO1 (b) Differentiate between horizontal and vertical microprogramming. CO3 (c) Represent the following conditional control statements by two register CO1 transfer statements with control functions. If(P=1) then (R1 R2) else if (Q=1) then (R1R3) (d) Design a 4-bit combinational incremental circuit using four full adder CO2 circuits. (e) Differentiate between Daisy chaining and centralized parallel CO5 arbitration. (f) What is the transfer rate of an eight-track magnetic tape whose speed is CO5 120 inches per second and whose density is 1600 bits per inch? (g) Register A holds the binary values 10011101.What is the register value CO2 after arithmetic shift right? Starting from the initial number 10011101, determine the register value after arithmetic shift left, and state whether there is an overflow. (h) What is an Associative memory? What are its advantages and CO4 disadvantages? (i) Differentiate between static RAM and Dynamic RAM. CO4 (j) What are the different types of instruction formats? CO3 SECTION B 2. Attempt any three of the following: 10x3 = 30 Qno Questions CO (a) A digital computer has a common bus system for 8 registers of 16 bit CO1 each. The bus is constructed using multiplexers. I. How many select input are there in each multiplexer? II. What is the size of multiplexers needed? III. How many multiplexers are there in the bus? (b) Explain destination-initiated transfer using handshaking method. CO5 (c) Explain 2-bit by 2-bit Array multiplier. Draw the flowchart for divide CO2 operation of two numbers in signed magnitude form. (d) A digital computer has a memory unit of 64K X 16 and a cache CO4 memory of 1K words. The cache uses direct mapping with a block size of four words. I. How many bits are there in the tag, index, block, and word fields of the address format? II. How many bits are there in each word of cache, and how they are divided into functions? Include a valid bit. III. How many blocks can the cache accommodate? (e) Explain with neat diagram, the address selection for control memory. CO3  Printed Page: 2 of 2 Subject Code: KCS302 0Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0 BTECH (SEM III) THEORY EXAMINATION 2021-22 COMPUTER ORGANIZATION AND ARCHITECTURE SECTION C 3. Attempt any one part of the following: 10x1 = 10 Qno Questions CO (a) A binary floating-point number has seven bits for a biased exponent. CO2 The constant used for the bias is 64. I. List the biased representation of all exponents from -64 to +63. II. Show that after addition of two biased exponents, it is necessary to subtract 64 in order to have a biased exponent’s sum. III. Show that after subtraction of two biased exponents, it is necessary to add 64 in order to have a biased exponent’s difference. (b) Show the multiplication process using Booth algorithm, when the CO2 following binary numbers, (+13) x (-15) are multiplied. 4. Attempt any one part of the following: 10x1 = 10 Qno Questions CO (a) Draw a diagram of a Bus system in which it uses 3 state buffers and a CO1 decoder instead of the multiplexers. (b) Explain in detail multiple bus organization with the help of a diagram. CO1 5. Attempt any one part of the following: 10x1 = 10 Qno Questions CO (a) The logical address space in a computer system consists of 128 CO4 segments. Each segment can have up to 32 pages of 4K words each. Physical memory consists of 4K blocks of 4K words each. Formulate the logical and physical address formats. (b) How is the Virtual address mapped into physical address? What are the CO4 different methods of writing into cache? 6. Attempt any one part of the following: 10x1 = 10 Qno Questions CO (a) Explain how the computer buses can be used to communicate with CO5 memory and I/O. Also draw the block diagram for CPU-IOP communication. (b) What are the different methods of asynchronous data transfer? Explain CO5 in detail. 7. Attempt any one part of the following: 10x1 = 10 Qno Questions CO (a) Write a program to evaluate arithmetic expression using stack CO3 organized computer with 0-address instructions. X = (A-B) * (((C - D * E) / F) / G) (b) List the differences between hardwired and micro programmed control CO3 in tabular format. Write the sequence of control steps for the following instruction for single bus architecture. R1  R2 * (R3)  Printed Page: 1 of 2 Subject Code: KCS302 0Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0 B TECH (SEM-III) THEORY EXAMINATION 2020-21 COMPUTER ORGANIZATION AND ARCHITECTURE Time: 3 Hours Total Marks: 100 Note: 1. Attempt all Sections. If require any missing data; then choose suitably. SECTION A 1. Attempt all questions in brief. 2 x 10 = 20 Q no. Question Marks CO a. Define the term Computer architecture and Computer organization. 2 1 b. What is mean by bus arbitration? List different types of bus arbitration. 2 1 c. Discuss biasing with reference to floating point representation. 2 2 d. What is restoring method in division algorithm? 2 2 e. Define micro operation and micro code. 2 3 f. Write short note on RISC. 2 3 g. Define hit ratio. 2 4 h. What do you mean by page fault? 2 4 i. Explain the term cycle stealing. 2 5 j. What do you mean by vector interrupt? Explain. 2 5 SECTION B 9 02 2. Attempt any three of the following: 3 x 10 = 30 98 Q no. Question Marks CO 0E 9. a. i. Draw a diagram of bus system using MUX which has four registers of size 4 bits 10 1 24 P2 each. 1. ii. Evaluate the arithmetic statement. _Q.2 X = A + B * [C * D + E * (F + G)] TU using a stack organized computer with zero address operation instructions. 25 b. Explain in detail the principle of carry look ahead adder and design 4-bit CLA adder. 10 2 |1 AK c. Draw the flowchart for instruction cycle with neat diagram and explain. 10 3 52 d. Discuss 2 D RAM and 2.5D RAM with suitable diagram. 10 4 e. Draw and explain the block diagram of typical DMA controller. 10 5 5: :0 SECTION C 14 3. Attempt any one part of the following: 1 Q no. Question Marks CO 02 a. An instruction is stored at location 400 with its address field at location 401.The 10 1 -2 address field has the value 500.A processor register R1 contains the number 200. Evaluate the effective address if the addressing mode of the instruction is (i) direct (ii) ar immediate (iii) relative (iv) register indirect (v) index with R1 as index register M 5- b. What do you mean by processor organization? Explain various types of processor 10 1 |1 organization. 4. Attempt any one part of the following: Q no. Question Marks CO a. Show the systemic multiplication process of (20) X (-19) using Booth’s algorithm 10 2 b. Explain IEEE standard for floating point representation. Represent the number (- 10 2 1460.125)10 in single precision and double precision format. 1|Page AKTU_QP20E029 | 15-Mar-2021 14:05:52 | 125.21.249.98  Printed Page: 2 of 2 Subject Code: KCS302 0Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0 5. Attempt any one part of the following: Q no. Question Marks CO a. What is a micro program sequencer? With block diagram, explain the working of 10 3 micro program sequencer. b. Differentiate between hardwired and micro programmed control unit. Explain each 10 3 component of hardwired control unit organization. 6. Attempt any one part of the following: Q no. Question Marks CO a. Calculate the page fault for a given string with the help of LRU & FIFO page 10 4 replacement algorithm, Size of frames = 4 and string 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 236 b. A computer uses RAM chips of 1024*1 capacity. 10 4 i) How many chips are needed & how should their address lines be connected to provide a memory capacity of 1024*8? ii) How many chips are needed to provide a memory capacity of 16 KB? 7. Attempt any one part of the following: Q no. Question 9 Marks CO 02 98 a. What do you mean by asynchronous data transfer? Explain strobe control and hand 10 5 0E shaking mechanism. 9. b. Discuss the different modes of data transfer. 10 5 24 P2 1. _Q.2 TU 25 |1 AK 52 5: :0 14 1 02 -2 ar M 5- |1 2|Page AKTU_QP20E029 | 15-Mar-2021 14:05:52 | 125.21.249.98 Printed Pages:02 Sub Code: KCS-302 Paper Id: 233647 Roll No. B. TECH. (SEM III) THEORY EXAMINATION 2022-23 COMPUTER ORGANIZATION AND ARCHITECTURE Time: 3 Hours Total Marks: 100 Note: Attempt all Sections. If require any missing data; then choose suitably. SECTION A 1. Attempt all questions in brief. 2 x 10 = 20 (a) List the steps involved in an instruction cycle. (b) How memory read and write operations are performed in computer system? (c) Define bus and memory transfer? (d) Define HIT and MISS ratio in memory with an example. (e) Define instruction cycle. (f) Differentiate between RISC and CISC. (g) List the difference between static RAM and dynamic RAM. (h) Define Virtual memory. (i) List down the functions performed by an Input/Output unit. (j) Why does the DMA get priority over CPU when both request memory transfer? SECTION B 2. Attempt any three of the following: 10x3=30 (a) Explain functional units of computer system in detail. (b) Explain IEEE-754 standard for floating point representation. Express (314.175) 10 in all the IEEE-754 models. (c) Explain the concept of pipelining and also explain types of pipelining. (d) Consider a cache consisting of 256 blocks of 16 words each for a total of 4096 words and assume that the main memory is addressable by a 16 bits address and it consists of 4K blocks. How many bits are there in each of TAG, SET, WORD field for 2-way set associative technique? (e) Define interrupt. Also discuss different types of interrupt. SECTION C 3. Attempt any one part of the following: 10x1=10 (a) Explain about stack organization used in processors. What do you understand by register stack? (b) What is an effective address? How it is calculated in different types of addressing modes? Explain. 4. Attempt any one part of the following: 10x1=10 (a) Describe the derivation procedure of look ahead carry adder by an example with the help of block diagram. (b) Show the systematic multiplication process of (-15) × (-16) using Booth’s Algorithm. 5. Attempt any one part of the following: 10x1=10 (a) Write a program to evaluate the arithmetic statement. P = ((X − 𝑌 + 𝑍) ∗ (A ^ B))/( C ^ D ∗ E) By using (i) Two address instructions (ii) One address instructions (iii) Zero address instructions (b) What are the differences between hardwired and micro-programmed control unit? 6. Attempt any one part of the following: 10x1=10 (a) Discuss the Memory Hierarchy in computer system with regard to Speed, Size and Cost. (b) Write a short notes on magnetic disk, magnetic tape and optical disk. 7. Attempt any one part of the following: 10x1=10 (a) With a neat schematic diagram, explain about DMA controller and its mode of data transfer. (b) Discuss the design of a typical input or output interface.