## GUJARAT TECHNOLOGICAL UNIVERSITY ## DIPLOMA IN ENGINEERING - SEMESTER - III EXAMINATION - WINTER 2025 Subject Code: DI03000021 Date: 06-12-2025 Subject Name: Data Structures Time: 10:30 AM TO 01:00 PM Instructions: 1. Attempt all questions. 2. Make Suitable assumptions wherever necessary. 3. Figures to the right indicate full marks. 4. Use of simple calculators and non-programmable scientific calculators are permitted. 5. English version is authentic. GLYPH<c=7,font=/QDCAAA+Lohit-Gujarati> GLYPH<c=7,font=/QDCAAA+Lohit-Gujarati> | | | | Marks | |-----|-------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|---------| | Q.1 | (a) | Define data structure. Explain types of data structure. | 03 | | | ( અ ) | ડે ટા GLYPHટ GLYPHચરની GLYPH યાGLYPHયા આપો. ડે ટા GLYPHટ GLYPHચરના GLYPHકારો સમGLYPHવો. | ૦૩ | | | (b) | Write an algorithm for deletion operation on one dimensional array. | 04 | | | ( બ ) | વન ડાઈમેનશન એરે પર િડલીશન ઓપરેશન માટે એ#ગો%રધમ લખો | ૦૪ | | | (c) | Define an Algorithm, space complexity and time complexity. Explain characteristics of an algorithm. | 07 | | | ( ક ) | એ#ગો%રધમ , GLYPHપેસ કો)*લે,ટી અને ટાઈમ કો)*લે,ટી ની GLYPH યાGLYPHયા આપો. એ#ગો%રધમના લ,ણો સમGLYPHવો. | ૦૭ | | | | OR | | | | (c) | Explain binary search on one dimensional array using example. | 07 | | | ( ક ) | વન ડાઈમેનશન એરે પર બાઇનરી સચ0 ઉદાહરણ સાથે સમGLYPHવો. | ૦૭ | | Q.2 | (a) | What is a circular queue? State its advantage over a simple queue. | 03 | | | ( અ ) | Circular Queue શું છે ? Simple Queue ની તુલનામાં તેનું ફાયદો શું છે ? | ૦૩ | | | (b) | Convert the Infix expression ( A + B ) * C + D into Prefix and Postfix forms. | 04 | | | ( બ ) | Infix expression (A+B) ∗ C+D ને Prefix અને Postfix ફોમ0માં બદલો. | ૦૪ | | | (c) | Write algorithms for PUSH and POP operations on stack. | 07 | | | ( ક ) | Stack પર PUSH અને POP operations માટે Algorithm લખો. | ૦૭ | | | | OR | | | | (a) | Write difference between stack and queue. | 03 | | | ( અ ) | Stack અને queue વ:ચે નો તફાવત લખો. | ૦૩ | | | (b) | Write an algorithm for insertion and deletion operations on queue data structure. | 04 | | | ( બ ) | Queue data structure માં insertion and deletion ઓપરેશન માટે ના અલગો%રધમ લખો. | ૦૪ | Total Marks: 70 | (c) | Convert the given infix expression into postfix expression using stack. M - N / O + P * Q - R + S * T / U | 07 | |------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------| | ( ક ) આપેલ ઇ;ફીGLYPHસ એGLYPHસGLYPHેશન ને stack ની મદદ M - N / O + P * Q - R + S * T / U | થી પોGLYPHટિફGLYPHસ એGLYPHસGLYPHેશન માં ફે રવો. ૦૭ | | | (a) | Explain singly linked list and doubly linked list node structure with figure. | 03 | | ( અ ) | singly linked list અને doubly linked list ના નોડ નુ GLYPHટGLYPHચર આ<ુ￵ત સાથે સમGLYPHવો. | ૦૩ | | (b) Write an algorithm to insert new node at the last position of singly linked list. | | 04 | | ( બ ) | singly linked list ની અંત માં નવો નોડ insert કરવા માટે નો અલગો%રધમ લખો. | ૦૪ | | (c) | Write algorithms to delete last node of the singly linked list and first node of singly linked list. | 07 | | ( ક ) singly linked list ની શ>આત નો તેમજ | છે@ો નોડ delete કરવા માટે ના અલગો%રધમ લખો. | ૦૭ | | (a) Write advantages of Dynamic memory allocation. | | 03 | | ( અ ) | Dynamic memory allocation ના ફાયદા ઓ લખો. | ૦૩ | | (b) | Write difference between singly linked list and doubly linked list. | 04 | | ( બ ) | Singly linked list અને doubly linked list વ:ચે નો તફાવત લખો. | ૦૪ | | (c) | Write an algorithm to search a particular element from singly linked list. Write an algorithm to count number nodes in singly linked list. | 07 | | ( ક ) | Singly linked list માંથી કોઇક particular element શોધવા માટે નો અલગો%રધમ લખો. Singly linked list માં ટોટલ કે ટલા નોડ છે તે count કરવા માટે નો અલગો%રધમ લખો. | ૦૭ | | (a) | Define BST, Directed tree and leaf node. | 03 | | ( અ ) | BST, Directed tree અને leaf node ની GLYPH યાGLYPHયા લખો. | ૦૩ | | (b) | Write short note on application of trees. | 04 | | ( બ ) | Application of trees પર ટૂં કી નBધ લખો. | ૦૪ | | (c) | Draw BST for 15 (root), 25, 7, 9, 50, 35, 30, 45. Insert 5 and 40 in that tree then delete 25 from tree and redraw it for each operation. | 07 | | ( ક ) 15 (root), 25, 7, 9, 50, 35, 30, 45 માટે BST દોરો. તેમજ તેજ BST માં 5 અને 40 Insert | કરો અને 25 delete કરો. દરેક ઓપરેશન પછી tree ફરી થી draw કરો. | ૦૭ | | | OR | | | (a) | Define subtree, height and depth of tree. | 03 | | ( અ ) | Subtree, height and depth of tree માટે ની GLYPH યાGLYPHયા લખો | ૦૩ | | (b) | Write algorithms for post order and preorder tree traversal. | 04 | | ( બ ) | Tree માં post order તેમજ preorder traversal માટે નો અલગો%રધમ લખો. | ૦૪ | | (c) | Create BST for following data 15, 10, 20, 8, 12, 17, 25, 6, 11. Write post order and preorder traversal sequence for constructed tree. | 07 | | | ( ક ) | 15, 10, 20, 8, 12, 17, 25, 6, 11 આપેલ ડે ટા થી BST બનાવી ને તેના પર થી post order અને preorder traversal સGLYPHGLYPHનસ લખો. | ૦૭ | |-----|---------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------| | Q.5 | (a) | Write an algorithm for selection sort. | 03 | | | ( અ ) | Selection sort માટે નો અલગો%રધમ લખો. | ૦૩ | | | (b) | Explain any two hash function methods. | 04 | | | ( બ ) | ગમે તે બે hash function method સમGLYPHવો. | ૦૪ | | | (c) | Give trace of quick sort algorithm using following data. 45, 12, 78, 34, 56, 89, 23, 67, 90, 11 | 07 | | | ( ક ) | 45, 12, 78, 34, 56, 89, 23, 67, 90, 11 આપેલ ડે ટા ને quick sort મેથડ થી સોટ0 કરવા માટે ના દરેક GLYPHટેપ લખો. | ૦૭ | | | | OR | | | | (a) | Write an algorithm for Insertion sort. | 03 | | | ( અ ) | Insertion sort માટે નો અલગો%રધમ લખો. | ૦૩ | | | (b) | Explain radix sort with the help of sorting given data 87, 3, 45, 1234, 678, 90, 3456, 2345. | 04 | | | ( બ ) | Radix sort ને આપેલ ડે ટા 87, 3, 45, 1234, 678, 90, 3456, 2345 સોટ0 કરી ને સમGLYPHવો | ૦૪ | | | (c) | Sort the given data using selection sort. 29, 64, 12, 8, 51, 37, 73, 19, 42 | 07 | | | ( ક ) | આપેલ ડે ટા ને selection sort ની મદદ થી સોટ0 કરો. 29, 64, 12, 8, 51, 37, 73, 19, 42 | ૦૭ |