డేటా స్ట్రక్చర్స్ (Data Structures)

గుర్తుంచుకోవాల్సినవి

• డేటా స్ట్రక్చర్ అంటే డేటాను నిల్వ చేసి, క్రమబద్ధీకరించే విధానం; దీనివల్ల వెతకడం, చేర్చడం, తొలగించడం వంటి ఆపరేషన్లు సమర్థవంతంగా జరుగుతాయి. మీకు ఎక్కువగా అవసరమయ్యే ఆపరేషన్లను బట్టి ఎంచుకోండి.
• స్టాక్ LIFO, క్యూ FIFO. బైనరీ సెర్చ్‌కు క్రమబద్ధమైన డేటా అవసరం, దీనికి O(log n) సమయం పడుతుంది; లీనియర్ సెర్చ్‌కు O(n) పడుతుంది.
• ట్రీ, గ్రాఫ్ నిర్మాణాలు క్రమానుగత శ్రేణిని, నెట్‌వర్క్‌లను సూచిస్తాయి. ట్రావర్సల్ క్రమాలను, నోడ్ సంఖ్య నియమాలను, ప్రామాణిక సార్టింగ్ పద్ధతుల టైమ్ కాంప్లెక్సిటీని తెలుసుకోండి.

ప్రాథమిక వర్గీకరణ

అబ్స్ట్రాక్ట్ డేటా టైప్ (ADT): డేటా, ఆపరేషన్ల వివరణ; దీనిని ఎలా కోడ్ చేయాలో చెప్పదు. స్టాక్, క్యూ, లిస్ట్ ADTలు.

అరేలు (Arrays)

• అరే ఒకే రకమైన మూలకాలను ఆనుకుని ఉన్న మెమరీలో నిల్వ చేస్తుంది; ఇండెక్స్ ద్వారా పొందుతారు.
• అడ్రస్ ఫార్ములా (ఏక కోణ): A[i] అడ్రస్ = Base + (i − LB) × w; ఇక్కడ LB అంటే లోయర్ బౌండ్ (C లో 0), w అంటే ఒక మూలకం పరిమాణం.
• ఉదాహరణ: Base = 1000, w = 4, A[5]: అడ్రస్ = 1000 + 5 × 4 = 1020.
• ద్వి కోణ అరే, రో-మేజర్: A[i][j] అడ్రస్ = Base + (i × n + j) × w; ఇక్కడ n అంటే నిలువు వరుసల సంఖ్య.
• కాలమ్-మేజర్: అడ్రస్ = Base + (j × m + i) × w; ఇక్కడ m అంటే అడ్డు వరుసల సంఖ్య.
• యాక్సెస్ O(1). మధ్యలో చేర్చడానికి లేదా తొలగించడానికి మూలకాలను జరపాలి, కాబట్టి అది O(n).
• m అడ్డు వరుసలు, n నిలువు వరుసలు ఉన్న మ్యాట్రిక్స్‌లో మూలకాల సంఖ్య m × n.

లింక్డ్ లిస్ట్‌లు

• లింక్డ్ లిస్ట్ అనేది నోడ్‌ల గొలుసు. ప్రతి నోడ్‌లో డేటా, తరువాతి నోడ్‌కు పాయింటర్ ఉంటాయి.
• సింగిల్లీ లింక్డ్: ఒక పాయింటర్ (next). డబుల్లీ లింక్డ్: రెండు పాయింటర్లు (previous, next). సర్క్యులర్: చివరి నోడ్ మొదటి నోడ్‌కు తిరిగి సూచిస్తుంది.
• హెడ్ వద్ద చేర్చడం O(1). వెతకడం O(n); రాండమ్ యాక్సెస్ ఉండదు.
• మొదటి నోడ్‌ను హెడ్ (head) సూచిస్తుంది. సింగిల్లీ లింక్డ్ లిస్ట్‌లో చివరి నోడ్ next పాయింటర్ NULL.
• అరేతో పోల్చితే: లింక్డ్ లిస్ట్ సులభంగా పెరుగుతుంది, చేర్చడం చౌక, కానీ పాయింటర్ల కోసం అదనపు మెమరీ వాడుతుంది, నేరుగా ఇండెక్స్ యాక్సెస్ ఉండదు.

స్టాక్ (Stack)

• LIFO (Last In, First Out). ఆపరేషన్లు: push (పైన చేర్చడం), pop (పై నుండి తొలగించడం), peek (పైన ఉన్నదాన్ని చూడటం).
• ఓవర్‌ఫ్లో: నిండిన స్టాక్‌లో push చేయడం. అండర్‌ఫ్లో: ఖాళీ స్టాక్ నుండి pop చేయడం.
• ఉపయోగాలు: ఫంక్షన్ కాల్స్ (కాల్ స్టాక్), అన్‌డూ ఆపరేషన్, ఎక్స్‌ప్రెషన్ మూల్యాంకనం, బ్రాకెట్ సరిపోల్చడం, డెప్త్-ఫస్ట్ సెర్చ్.
• ఎక్స్‌ప్రెషన్ రూపాలు: ఇన్‌ఫిక్స్ (A + B), ప్రిఫిక్స్ (+ A B), పోస్ట్‌ఫిక్స్ (A B +).
• మార్పిడి ఉదాహరణ: A + B × C పోస్ట్‌ఫిక్స్‌లో A B C × +. (A + B) × C పోస్ట్‌ఫిక్స్‌లో A B + C ×.
• పోస్ట్‌ఫిక్స్ మూల్యాంకనం: ఎడమ నుండి కుడికి చదవండి; ఆపరెండ్లను push చేయండి; ఆపరేటర్ వచ్చినప్పుడు రెండింటిని pop చేసి, అమలు చేసి, ఫలితాన్ని push చేయండి. 2 3 4 × + కోసం: 3 × 4 = 12, తరువాత 2 + 12 = 14.
• ఆపరేటర్ ప్రాధాన్యత (ఎక్కువ నుండి తక్కువకు): ^, తరువాత × మరియు ÷, తరువాత + మరియు −.

క్యూ (Queue)

• FIFO (First In, First Out). ఆపరేషన్లు: enqueue (వెనుక చేర్చడం), dequeue (ముందు నుండి తొలగించడం).
• రకాలు: సింపుల్ క్యూ, సర్క్యులర్ క్యూ, డబుల్-ఎండెడ్ క్యూ (డీక్యూ), ప్రయారిటీ క్యూ.
• సర్క్యులర్ క్యూ: రియర్ మొదటికి తిరిగి చేరుతుంది, కాబట్టి ఖాళీ అయిన స్థలం మళ్ళీ వాడబడుతుంది. తరువాతి రియర్ స్థానం = (rear + 1) mod size.
• ఉపయోగాలు: ప్రింటర్ జాబ్ క్యూ, CPU షెడ్యూలింగ్, బ్రెడ్త్-ఫస్ట్ సెర్చ్, కాల్ సెంటర్లు.
• సాధారణ అరేలో n పరిమాణం గల క్యూ, ముందు ఖాళీలు ఉన్నా నిండిపోయినట్లు కావచ్చు; సర్క్యులర్ క్యూ దీనిని పరిష్కరిస్తుంది.

ట్రీలు (Trees)

• ట్రీ అనేది ఒక రూట్ ఉన్న క్రమానుగత నిర్మాణం; ప్రతి నోడ్‌కు చైల్డ్‌లు ఉండవచ్చు. చైల్డ్ లేని నోడ్‌ను లీఫ్ అంటారు.
• పదాలు: డిగ్రీ (చైల్డ్‌ల సంఖ్య), లెవెల్ (రూట్ సంప్రదాయం ప్రకారం లెవెల్ 0 లేదా 1 వద్ద), ఎత్తు (రూట్ నుండి లీఫ్ వరకు పొడవైన మార్గం), లోతు (రూట్ నుండి దూరం).
• బైనరీ ట్రీ: ప్రతి నోడ్‌కు గరిష్ఠంగా రెండు చైల్డ్‌లు (ఎడమ, కుడి).
• వాస్తవాలు: n నోడ్‌లు ఉన్న బైనరీ ట్రీకి n − 1 ఎడ్జ్‌లు ఉంటాయి. h ఎత్తు (రూట్ ఎత్తు 0) గల బైనరీ ట్రీలో గరిష్ఠంగా 2^(h+1) − 1 నోడ్‌లు ఉంటాయి. L లెవెల్ (రూట్ లెవెల్ 0) వద్ద గరిష్ఠ నోడ్‌లు 2^L.
• ఫుల్ బైనరీ ట్రీ: ప్రతి నోడ్‌కు 0 లేదా 2 చైల్డ్‌లు. కంప్లీట్ బైనరీ ట్రీ: చివరి లెవెల్ తప్ప అన్ని లెవెల్‌లు నిండి ఉంటాయి; చివరిది ఎడమ నుండి కుడికి నిండుతుంది.
• బైనరీ సెర్చ్ ట్రీ (BST): ఎడమ సబ్‌ట్రీ విలువలు నోడ్ కంటే చిన్నవి; కుడి సబ్‌ట్రీ విలువలు పెద్దవి. BST ఇన్‌ఆర్డర్ ట్రావర్సల్ క్రమబద్ధమైన వరుసను ఇస్తుంది.
• ట్రావర్సల్స్: ఇన్‌ఆర్డర్ (Left, Root, Right), ప్రీఆర్డర్ (Root, Left, Right), పోస్ట్‌ఆర్డర్ (Left, Right, Root).
• ఉదాహరణ: 50, 30, 70, 20, 40లను BSTలో చేర్చండి. ఇన్‌ఆర్డర్: 20 30 40 50 70. ప్రీఆర్డర్: 50 30 20 40 70. పోస్ట్‌ఆర్డర్: 20 40 30 70 50.
• బ్యాలెన్స్‌డ్ ట్రీలు: AVL ట్రీ (ప్రతి నోడ్ రెండు సబ్‌ట్రీల ఎత్తు వ్యత్యాసం గరిష్ఠంగా 1).
• హీప్: కంప్లీట్ బైనరీ ట్రీ. మ్యాక్స్-హీప్‌లో ప్రతి పేరెంట్ దాని చైల్డ్‌ల కంటే పెద్దది లేదా సమానం. ఇండెక్స్ 1 నుండి మొదలయ్యే అరేలో, నోడ్ i యొక్క చైల్డ్‌లు 2i మరియు 2i + 1, దాని పేరెంట్ i/2 (పూర్ణాంక భాగహారం).

గ్రాఫ్‌లు (Graphs)

• గ్రాఫ్‌లో వెర్టెక్స్‌లు (నోడ్‌లు), ఎడ్జ్‌లు (లింకులు) ఉంటాయి. ఎడ్జ్‌లు డైరెక్టెడ్ లేదా అన్‌డైరెక్టెడ్, వెయిటెడ్ లేదా అన్‌వెయిటెడ్ కావచ్చు.
• ప్రాతినిధ్యం: అడ్జసెన్సీ మ్యాట్రిక్స్ (n × n అరే; n² స్థలం అవసరం), అడ్జసెన్సీ లిస్ట్ (స్పార్స్ గ్రాఫ్‌లకు తక్కువ స్థలం).
• ట్రావర్సల్: BFS క్యూను వాడుతుంది; DFS స్టాక్‌ను (లేదా రికర్షన్) వాడుతుంది.
• n వెర్టెక్స్‌లు గల సాధారణ అన్‌డైరెక్టెడ్ గ్రాఫ్‌లో గరిష్ఠ ఎడ్జ్‌లు = n(n − 1)/2. ఉదాహరణ: n = 5 అయితే 10.
• స్పానింగ్ ట్రీ: అన్ని వెర్టెక్స్‌లను n − 1 ఎడ్జ్‌లతో, సైకిల్ లేకుండా కలిపే సబ్‌గ్రాఫ్. మినిమం స్పానింగ్ ట్రీ అల్గారిథమ్‌లు: ప్రిమ్ (Prim), క్రుస్కల్ (Kruskal). అతి తక్కువ మార్గం అల్గారిథమ్: డైక్స్ట్రా (Dijkstra).

హ్యాషింగ్ (Hashing)

• హ్యాష్ టేబుల్ ఇండెక్స్‌ను ఇచ్చే హ్యాష్ ఫంక్షన్ ద్వారా కీలను నిల్వ చేస్తుంది. సగటు వెతుకుదల సమయం O(1).
• కొలిజన్: రెండు కీలు ఒకే ఇండెక్స్‌ను ఇవ్వడం. పరిష్కారం: చైనింగ్ (ప్రతి స్లాట్ వద్ద ఒక లిస్ట్), ఓపెన్ అడ్రెస్సింగ్ (లీనియర్ ప్రోబింగ్, క్వాడ్రాటిక్ ప్రోబింగ్, డబుల్ హ్యాషింగ్).
• ఉదాహరణ: హ్యాష్ ఫంక్షన్ key mod 10; కీలు 25 మరియు 35 రెండూ ఇండెక్స్ 5కు మ్యాప్ అవుతాయి (కొలిజన్).

వెతకడం మరియు క్రమబద్ధీకరణ

బైనరీ సెర్చ్ ఉదాహరణ: క్రమబద్ధమైన 1000 అంశాలకు గరిష్ఠ పోలికలు సుమారు log2(1000) ≈ 10 (ఎందుకంటే 2^10 = 1024). క్రమబద్ధమైన 64 అంశాలకు, అధమ సందర్భం log2(64) + 1 = 7 పోలికలు.

కాంప్లెక్సిటీ (Complexity)

• టైమ్ కాంప్లెక్సిటీ ఇన్‌పుట్ పరిమాణం n పెరిగేకొద్దీ దశలను లెక్కిస్తుంది; స్పేస్ కాంప్లెక్సిటీ మెమరీని లెక్కిస్తుంది.
• వృద్ధి క్రమం (చిన్న నుండి పెద్దకు): O(1), O(log n), O(n), O(n log n), O(n²), O(2^n).
• Big-O ఎగువ హద్దు (అధమ సందర్భం), Omega దిగువ హద్దు, Theta కచ్చితమైన హద్దు.

పరీక్షలో పొరపాట్లు

• 1. LIFO మరియు FIFO: స్టాక్ LIFO, క్యూ FIFO.
• 2. BST ఇన్‌ఆర్డర్ క్రమబద్ధంగా ఉంటుంది; ప్రీఆర్డర్, పోస్ట్‌ఆర్డర్ ఉండవు.
• 3. బైనరీ సెర్చ్‌కు క్రమబద్ధమైన డేటా అవసరం; లీనియర్ సెర్చ్‌కు అవసరం లేదు.
• 4. BFS క్యూను వాడుతుంది; DFS స్టాక్‌ను వాడుతుంది.
• 5. ఓవర్‌ఫ్లో మరియు అండర్‌ఫ్లో: ఓవర్‌ఫ్లో అంటే నిండిన స్టాక్‌లో push చేయడం; అండర్‌ఫ్లో అంటే ఖాళీ స్టాక్ నుండి pop చేయడం.
• 6. క్విక్ సార్ట్ అధమ సందర్భం O(n²), మెర్జ్ సార్ట్ అధమ సందర్భం O(n log n).
• 7. అరేకు O(1) యాక్సెస్; లింక్డ్ లిస్ట్‌కు O(n) యాక్సెస్.
• 8. ట్రీలో ఎడ్జ్‌లు = n − 1; గ్రాఫ్‌కు ఎక్కువ ఎడ్జ్‌లు ఉండవచ్చు.

ఒక్క వాక్య సమాచారాలు

• 1. స్టాక్ LIFO నియమాన్ని అనుసరిస్తుంది.
• 2. క్యూ FIFO నియమాన్ని అనుసరిస్తుంది.
• 3. ట్రీ రూట్‌కు పేరెంట్ ఉండదు.
• 4. లీఫ్‌కు చైల్డ్‌లు ఉండవు.
• 5. బైనరీ సెర్చ్ O(log n) సమయం తీసుకుంటుంది.
• 6. లీనియర్ సెర్చ్ O(n) సమయం తీసుకుంటుంది.
• 7. BST ఇన్‌ఆర్డర్ ట్రావర్సల్ క్రమబద్ధమైన వరుసను ఇస్తుంది.
• 8. n నోడ్‌లు ఉన్న ట్రీకి n − 1 ఎడ్జ్‌లు ఉంటాయి.
• 9. BFS క్యూను వాడుతుంది.
• 10. హ్యాష్ కొలిజన్ అంటే రెండు కీలు ఒకే ఇండెక్స్‌కు మ్యాప్ కావడం.
• 11. A + B పోస్ట్‌ఫిక్స్ A B +.
• 12. మెర్జ్ సార్ట్ అన్ని సందర్భాలలో O(n log n) తీసుకుంటుంది.

సాధన ప్రశ్నలు

1. ఏ డేటా నిర్మాణం LIFO సూత్రాన్ని అనుసరిస్తుంది?

   1. క్యూ (Queue)
   2. బైనరీ ట్రీ
   3. స్టాక్ (Stack)
   4. అరే (Array)
   సమాధానం

   C. స్టాక్ (Stack)

   Which data structure follows the LIFO principle?

   1. Queue
   2. Binary tree
   3. Stack
   4. Array

2. ఏ డేటా నిర్మాణం FIFO సూత్రాన్ని అనుసరిస్తుంది?

   1. గ్రాఫ్
   2. బైనరీ ట్రీ
   3. స్టాక్
   4. క్యూ (Queue)
   సమాధానం

   D. క్యూ (Queue)

   Which data structure follows the FIFO principle?

   1. Graph
   2. Binary tree
   3. Stack
   4. Queue

3. వీటిలో నాన్-లీనియర్ డేటా నిర్మాణం ఏది?

   1. అరే
   2. ట్రీ (Tree)
   3. క్యూ
   4. స్టాక్
   సమాధానం

   B. ట్రీ (Tree)

   Which of these is a non-linear data structure?

   1. Array
   2. Tree
   3. Queue
   4. Stack

4. నిండి ఉన్న స్టాక్‌లో ఎలిమెంట్‌ను చేర్చడాన్ని ఏమంటారు?

   1. ఓవర్‌ఫ్లో (Overflow)
   2. ట్రావర్సల్
   3. అండర్‌ఫ్లో
   4. హాషింగ్
   సమాధానం

   A. ఓవర్‌ఫ్లో (Overflow)

   Inserting an element into a full stack is called

   1. Overflow
   2. Traversal
   3. Underflow
   4. Hashing

5. ఖాళీ స్టాక్ నుంచి ఎలిమెంట్‌ను తొలగించడాన్ని ఏమంటారు?

   1. కొలిజన్
   2. అండర్‌ఫ్లో (Underflow)
   3. రొటేషన్
   4. ఓవర్‌ఫ్లో
   సమాధానం

   B. అండర్‌ఫ్లో (Underflow)

   Removing an element from an empty stack is called

   1. Collision
   2. Underflow
   3. Rotation
   4. Overflow

6. బైనరీ సెర్చ్ ట్రీ యొక్క ఏ ట్రావర్సల్ కీలను క్రమబద్ధంగా (sorted) ఇస్తుంది?

   1. ఇన్‌ఆర్డర్ (Inorder)
   2. రివర్స్ చేసిన లెవల్ ఆర్డర్
   3. పోస్ట్‌ఆర్డర్
   4. ప్రీఆర్డర్
   సమాధానం

   A. ఇన్‌ఆర్డర్ (Inorder)

   Which traversal of a binary search tree gives the keys in sorted order?

   1. Inorder
   2. Level order reversed
   3. Postorder
   4. Preorder

7. బైనరీ సెర్చ్‌ను దేనిపై మాత్రమే అమలు చేయగలం?

   1. క్రమం లేని డేటా
   2. లింక్డ్ లిస్ట్‌లపై మాత్రమే
   3. గ్రాఫ్‌లు
   4. క్రమబద్ధమైన డేటా
   సమాధానం

   D. క్రమబద్ధమైన డేటా

   Binary search can be applied only on

   1. Unsorted data
   2. Linked lists only
   3. Graphs
   4. Sorted data

8. బైనరీ సెర్చ్ యొక్క వరస్ట్ కేస్ టైమ్ కాంప్లెక్సిటీ

   1. O(n)
   2. O(n log n)
   3. O(log n)
   4. O(1)
   సమాధానం

   C. O(log n)

   The time complexity of binary search in the worst case is

   1. O(n)
   2. O(n log n)
   3. O(log n)
   4. O(1)

9. లీనియర్ సెర్చ్ యొక్క వరస్ట్ కేస్ టైమ్ కాంప్లెక్సిటీ

   1. O(1)
   2. O(log n)
   3. O(n)
   4. O(n²)
   సమాధానం

   C. O(n)

   The time complexity of linear search in the worst case is

   1. O(1)
   2. O(log n)
   3. O(n)
   4. O(n²)

10. గ్రాఫ్‌లో బ్రెడ్త్-ఫస్ట్ సెర్చ్ (BFS) ఉపయోగించేది

    1. క్యూ
    2. స్టాక్
    3. హాష్ టేబుల్
    4. హీప్
    సమాధానం

    A. క్యూ

    Breadth-first search of a graph uses a

    1. Queue
    2. Stack
    3. Hash table
    4. Heap

11. గ్రాఫ్‌లో డెప్త్-ఫస్ట్ సెర్చ్ (DFS) ఉపయోగించేది

    1. ప్రయారిటీ క్యూ
    2. స్టాక్
    3. క్యూ
    4. స్ట్రింగ్‌ల అరే
    సమాధానం

    B. స్టాక్

    Depth-first search of a graph uses a

    1. Priority queue
    2. Stack
    3. Queue
    4. Array of strings

12. హాష్ కొలిజన్ ఎప్పుడు ఏర్పడుతుంది?

    1. కీని తొలగించినప్పుడు
    2. కీ దొరకనప్పుడు
    3. టేబుల్ ఖాళీగా ఉన్నప్పుడు
    4. రెండు కీలు ఒకే ఇండెక్స్‌కు మ్యాప్ అయినప్పుడు
    సమాధానం

    D. రెండు కీలు ఒకే ఇండెక్స్‌కు మ్యాప్ అయినప్పుడు

    A hash collision occurs when

    1. A key is deleted
    2. A key is not found
    3. The table is empty
    4. Two keys map to the same index

13. లింక్డ్ లిస్ట్‌లోని మొదటి నోడ్‌ను సూచించేది

    1. టెయిల్ (Tail)
    2. లీఫ్
    3. హెడ్ (Head)
    4. రూట్
    సమాధానం

    C. హెడ్ (Head)

    The first node of a linked list is pointed to by the

    1. Tail
    2. Leaf
    3. Head
    4. Root

14. చివరి నోడ్ తిరిగి మొదటి నోడ్‌ను సూచించే లింక్డ్ లిస్ట్ ఏది?

    1. సర్క్యులర్ లింక్డ్ లిస్ట్
    2. NULL తో ముగిసే హెడర్ లిస్ట్
    3. సింగిల్లీ లింక్డ్ లిస్ట్
    4. డబులీ లింక్డ్ లిస్ట్
    సమాధానం

    A. సర్క్యులర్ లింక్డ్ లిస్ట్

    Which linked list has a last node that points back to the first node?

    1. Circular linked list
    2. Header list with NULL end
    3. Singly linked list
    4. Doubly linked list

15. ట్రీలో పిల్లలు (children) లేని నోడ్‌ను ఏమంటారు?

    1. సిబ్లింగ్
    2. రూట్
    3. పేరెంట్
    4. లీఫ్ (Leaf)
    సమాధానం

    D. లీఫ్ (Leaf)

    A node with no children in a tree is called a

    1. Sibling
    2. Root
    3. Parent
    4. Leaf

16. బేస్ అడ్రస్ 1000, ఒక్కో ఎలిమెంట్‌కు 4 బైట్లు ఉన్న ఏక-పరిమాణ అరేలో A[5] అడ్రస్ (ఇండెక్స్ 0 నుంచి) ఎంత?

    1. 1005
    2. 1020
    3. 1024
    4. 1016
    సమాధానం

    B. 1020

    The address of A[5] in a one-dimensional array with base address 1000 and 4 bytes per element (index from 0) is

    1. 1005
    2. 1020
    3. 1024
    4. 1016

17. బేస్ 2000, ఒక్కో ఎలిమెంట్‌కు 2 బైట్లు ఉన్న అరేలో A[10] అడ్రస్ (ఇండెక్స్ 0 నుంచి) ఎంత?

    1. 2020
    2. 2012
    3. 2010
    4. 2022
    సమాధానం

    A. 2020

    The address of A[10] in an array with base 2000 and 2 bytes per element (index from 0) is

    1. 2020
    2. 2012
    3. 2010
    4. 2022

18. A[i][j] అరేను రో-వైజ్‌గా నిల్వ చేశారు; బేస్ 1000, 5 కాలమ్‌లు, ఒక్కో ఎలిమెంట్‌కు 4 బైట్లు. A[2][3] అడ్రస్

    1. 1056
    2. 1060
    3. 1048
    4. 1052
    సమాధానం

    D. 1052

    An array A[i][j] is stored row-wise with base 1000, 5 columns and 4 bytes per element. The address of A[2][3] is

    1. 1056
    2. 1060
    3. 1048
    4. 1052

19. ఒక అరేను కాలమ్-వైజ్‌గా నిల్వ చేశారు; బేస్ 100, 3 రోలు, ఒక్కో ఎలిమెంట్‌కు 2 బైట్లు. A[1][2] అడ్రస్

    1. 116
    2. 108
    3. 114
    4. 112
    సమాధానం

    C. 114

    An array is stored column-wise with base 100, 3 rows and 2 bytes per element. The address of A[1][2] is

    1. 116
    2. 108
    3. 114
    4. 112

20. పోస్ట్‌ఫిక్స్ వ్యక్తీకరణ 5 6 2 + * 12 4 / - విలువ

    1. 43
    2. 37
    3. 35
    4. 40
    సమాధానం

    B. 37

    The value of the postfix expression 5 6 2 + * 12 4 / - is

    1. 43
    2. 37
    3. 35
    4. 40

21. (A + B) * C యొక్క పోస్ట్‌ఫిక్స్ రూపం

    1. A B C + *
    2. * + A B C
    3. A + B C *
    4. A B + C *
    సమాధానం

    D. A B + C *

    The postfix form of (A + B) * C is

    1. A B C + *
    2. * + A B C
    3. A + B C *
    4. A B + C *

22. ఎత్తు 3 (రూట్ ఎత్తు 0) ఉన్న బైనరీ ట్రీలో గరిష్ఠ నోడ్ల సంఖ్య

    1. 8
    2. 7
    3. 15
    4. 16
    సమాధానం

    C. 15

    The maximum number of nodes in a binary tree of height 3 (root at height 0) is

    1. 8
    2. 7
    3. 15
    4. 16

23. బైనరీ ట్రీలో లెవల్ 4 (రూట్ లెవల్ 0) వద్ద గరిష్ఠ నోడ్ల సంఖ్య

    1. 16
    2. 8
    3. 15
    4. 32
    సమాధానం

    A. 16

    The maximum number of nodes at level 4 of a binary tree (root at level 0) is

    1. 16
    2. 8
    3. 15
    4. 32

24. ఒక బైనరీ ట్రీలో 20 నోడ్లు ఉన్నాయి. దానికి ఎన్ని ఎడ్జ్‌లు ఉంటాయి?

    1. 18
    2. 19
    3. 21
    4. 20
    సమాధానం

    B. 19

    A binary tree has 20 nodes. How many edges does it have?

    1. 18
    2. 19
    3. 21
    4. 20

25. 1023 ఎలిమెంట్లు ఉన్న క్రమబద్ధమైన అరేలో బైనరీ సెర్చ్ ద్వారా కీని కనుగొనడానికి గరిష్ఠ పోలికల సంఖ్య

    1. 512
    2. 10
    3. 9
    4. 11
    సమాధానం

    B. 10

    The maximum number of comparisons to find a key in a sorted array of 1023 elements by binary search is

    1. 512
    2. 10
    3. 9
    4. 11

26. 6 వెర్టెక్స్‌లు ఉన్న సాధారణ అన్‌డైరెక్టెడ్ గ్రాఫ్‌లో గరిష్ఠ ఎడ్జ్‌ల సంఖ్య

    1. 36
    2. 12
    3. 30
    4. 15
    సమాధానం

    D. 15

    The maximum number of edges in a simple undirected graph with 6 vertices is

    1. 36
    2. 12
    3. 30
    4. 15

27. సైజు 8 ఉన్న సర్క్యులర్ క్యూలో రియర్ స్థానం 7 వద్ద ఉంది. తదుపరి రియర్ స్థానం

    1. 7
    2. 8
    3. 1
    4. 0
    సమాధానం

    D. 0

    A circular queue has size 8 and the rear is at position 7. The next rear position is

    1. 7
    2. 8
    3. 1
    4. 0

28. హాష్ ఫంక్షన్ key mod 7 తో, కీ 50 ఏ ఇండెక్స్ వద్ద నిల్వ అవుతుంది?

    1. 0
    2. 6
    3. 7
    4. 1
    సమాధానం

    D. 1

    With the hash function key mod 7, the key 50 is stored at index

    1. 0
    2. 6
    3. 7
    4. 1

29. 1, 2, 3 పుష్ చేయండి; పాప్; 4 పుష్; పాప్; పాప్. ఇప్పుడు స్టాక్ పైన ఏ ఎలిమెంట్ ఉంది?

    1. 2
    2. 3
    3. 1
    4. 4
    సమాధానం

    C. 1

    Push 1, 2, 3; pop; push 4; pop; pop. Which element is now on top of the stack?

    1. 2
    2. 3
    3. 1
    4. 4

30. 5, 6, 7 ఎన్‌క్యూ చేయండి; డీక్యూ; 8 ఎన్‌క్యూ. ముందు (front) భాగంలో ఏ ఎలిమెంట్ ఉంది?

    1. 6
    2. 5
    3. 8
    4. 7
    సమాధానం

    A. 6

    Enqueue 5, 6, 7; dequeue; enqueue 8. Which element is at the front?

    1. 6
    2. 5
    3. 8
    4. 7

31. ఒక గ్రాఫ్‌లో 8 వెర్టెక్స్‌లు ఉన్నాయి. దాని స్పానింగ్ ట్రీకి ఎన్ని ఎడ్జ్‌లు ఉంటాయి?

    1. 6
    2. 7
    3. 8
    4. 9
    సమాధానం

    B. 7

    A graph has 8 vertices. How many edges does its spanning tree have?

    1. 6
    2. 7
    3. 8
    4. 9

32. 10 వెర్టెక్స్‌లు ఉన్న గ్రాఫ్ అడ్జసెన్సీ మ్యాట్రిక్స్‌లో ఎన్ని ఎంట్రీలు ఉంటాయి?

    1. 20
    2. 10
    3. 100
    4. 45
    సమాధానం

    C. 100

    An adjacency matrix for a graph with 10 vertices has how many entries?

    1. 20
    2. 10
    3. 100
    4. 45

33. వరస్ట్ కేస్ టైమ్ O(n²), సగటు టైమ్ O(n log n) ఉన్న సార్టింగ్ పద్ధతి ఏది?

    1. క్విక్ సార్ట్
    2. మెర్జ్ సార్ట్
    3. సెలక్షన్ సార్ట్
    4. హీప్ సార్ట్
    సమాధానం

    A. క్విక్ సార్ట్

    Which sorting method has a worst-case time of O(n²) but average time of O(n log n)?

    1. Quick sort
    2. Merge sort
    3. Selection sort
    4. Heap sort

34. ఎల్లప్పుడూ O(n log n) సమయం తీసుకుని అదనపు స్థలం అవసరమయ్యే సార్టింగ్ పద్ధతి ఏది?

    1. సెలక్షన్ సార్ట్
    2. మెర్జ్ సార్ట్
    3. బబుల్ సార్ట్
    4. ఇన్సర్షన్ సార్ట్
    సమాధానం

    B. మెర్జ్ సార్ట్

    Which sorting method always takes O(n log n) time and needs extra space?

    1. Selection sort
    2. Merge sort
    3. Bubble sort
    4. Insertion sort

35. ఈ క్రింది ప్రకటనలను పరిశీలించండి. 1. స్టాక్ LIFO నియమాన్ని అనుసరిస్తుంది. 2. క్యూ LIFO నియమాన్ని అనుసరిస్తుంది. ఏవి సరైనవి?

    1. 1 మాత్రమే
    2. 2 మాత్రమే
    3. 1 మరియు 2 రెండూ
    4. 1 లేదా 2 కాదు
    సమాధానం

    A. 1 మాత్రమే

    Consider the statements. 1. A stack follows the LIFO rule. 2. A queue follows the LIFO rule. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2

36. బైనరీ సెర్చ్‌పై ఈ క్రింది ప్రకటనలను పరిశీలించండి. 1. దీనికి క్రమబద్ధమైన డేటా అవసరం. 2. ఇది O(log n) సమయం తీసుకుంటుంది. ఏవి సరైనవి?

    1. 1 మాత్రమే
    2. 2 మాత్రమే
    3. 1 మరియు 2 రెండూ
    4. 1 లేదా 2 కాదు
    సమాధానం

    C. 1 మరియు 2 రెండూ

    Consider the statements about binary search. 1. It needs sorted data. 2. It takes O(log n) time. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2

37. అరేలు, లింక్డ్ లిస్ట్‌లపై ఈ క్రింది ప్రకటనలను పరిశీలించండి. 1. అరే ఇండెక్స్ ద్వారా ఎలిమెంట్‌కు నేరుగా ప్రాప్యత ఇస్తుంది. 2. లింక్డ్ లిస్ట్ ఇండెక్స్ ద్వారా నేరుగా ప్రాప్యత ఇస్తుంది. ఏవి సరైనవి?

    1. 1 మాత్రమే
    2. 2 మాత్రమే
    3. 1 మరియు 2 రెండూ
    4. 1 లేదా 2 కాదు
    సమాధానం

    A. 1 మాత్రమే

    Consider the statements about arrays and linked lists. 1. An array gives direct access to an element by index. 2. A linked list gives direct access by index. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2

38. ట్రీలపై ఈ క్రింది ప్రకటనలను పరిశీలించండి. 1. n నోడ్లు ఉన్న ట్రీకి n − 1 ఎడ్జ్‌లు ఉంటాయి. 2. లీఫ్‌కు రెండు చిల్డ్రన్ ఉంటాయి. ఏవి సరైనవి?

    1. 1 మాత్రమే
    2. 2 మాత్రమే
    3. 1 మరియు 2 రెండూ
    4. 1 లేదా 2 కాదు
    సమాధానం

    A. 1 మాత్రమే

    Consider the statements about trees. 1. A tree with n nodes has n − 1 edges. 2. A leaf has two children. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2

39. గ్రాఫ్ ట్రావర్సల్‌పై ఈ క్రింది ప్రకటనలను పరిశీలించండి. 1. BFS క్యూను ఉపయోగిస్తుంది. 2. DFS స్టాక్ లేదా రికర్షన్‌ను ఉపయోగిస్తుంది. ఏవి సరైనవి?

    1. 1 మాత్రమే
    2. 2 మాత్రమే
    3. 1 మరియు 2 రెండూ
    4. 1 లేదా 2 కాదు
    సమాధానం

    C. 1 మరియు 2 రెండూ

    Consider the statements about graph traversal. 1. BFS uses a queue. 2. DFS uses a stack or recursion. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2

40. బైనరీ సెర్చ్ ట్రీ ఇన్‌ఆర్డర్ ట్రావర్సల్‌పై ఈ క్రింది ప్రకటనలను పరిశీలించండి. 1. ఇది ఎడమ, రూట్, కుడి క్రమంలో సందర్శిస్తుంది. 2. ఇది కీలను అవరోహణ క్రమంలో ఇస్తుంది. ఏవి సరైనవి?

    1. 1 మాత్రమే
    2. 2 మాత్రమే
    3. 1 మరియు 2 రెండూ
    4. 1 లేదా 2 కాదు
    సమాధానం

    A. 1 మాత్రమే

    Consider the statements about the inorder traversal of a binary search tree. 1. It visits Left, Root, Right. 2. It gives the keys in descending order. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2

41. డేటా నిర్మాణాన్ని ఆపరేషన్‌తో జతపరచండి. A. స్టాక్ B. క్యూ C. బైనరీ సెర్చ్ D. హాషింగ్ 1. ఎన్‌క్యూ 2. పుష్ 3. సగం చేయడం (Halving) 4. కొలిజన్

    1. A-1, B-2, C-3, D-4
    2. A-2, B-1, C-4, D-3
    3. A-4, B-1, C-3, D-2
    4. A-2, B-1, C-3, D-4
    సమాధానం

    D. A-2, B-1, C-3, D-4

    Match the data structure with the operation. A. Stack B. Queue C. Binary search D. Hashing 1. Enqueue 2. Push 3. Halving 4. Collision

    1. A-1, B-2, C-3, D-4
    2. A-2, B-1, C-4, D-3
    3. A-4, B-1, C-3, D-2
    4. A-2, B-1, C-3, D-4

42. సార్ట్‌ను దాని వరస్ట్ కేస్ టైమ్‌తో జతపరచండి. A. బబుల్ సార్ట్ B. మెర్జ్ సార్ట్ C. క్విక్ సార్ట్ D. హీప్ సార్ట్ 1. O(n²) 2. O(n log n)

    1. A-1, B-1, C-2, D-2
    2. A-1, B-2, C-1, D-2
    3. A-2, B-1, C-2, D-1
    4. A-2, B-2, C-1, D-1
    సమాధానం

    B. A-1, B-2, C-1, D-2

    Match the sort with its worst-case time. A. Bubble sort B. Merge sort C. Quick sort D. Heap sort 1. O(n²) 2. O(n log n)

    1. A-1, B-1, C-2, D-2
    2. A-1, B-2, C-1, D-2
    3. A-2, B-1, C-2, D-1
    4. A-2, B-2, C-1, D-1

43. ఇండెక్స్ 1 నుంచి మొదలయ్యే అరేలో నిల్వ చేసిన హీప్‌లో, నోడ్ 5 యొక్క చిల్డ్రన్ ఏ స్థానాల్లో ఉంటారు?

    1. 9 మరియు 10
    2. 6 మరియు 7
    3. 5 మరియు 6
    4. 10 మరియు 11
    సమాధానం

    D. 10 మరియు 11

    In a heap stored in an array with index starting at 1, the children of node 5 are at positions

    1. 9 and 10
    2. 6 and 7
    3. 5 and 6
    4. 10 and 11

44. ఇండెక్స్ 1 నుంచి మొదలయ్యే అరేలో నిల్వ చేసిన హీప్‌లో, నోడ్ 9 యొక్క పేరెంట్ ఏ స్థానంలో ఉంటుంది?

    1. 3
    2. 5
    3. 9
    4. 4
    సమాధానం

    D. 4

    In a heap stored in an array with index starting at 1, the parent of node 9 is at position

    1. 3
    2. 5
    3. 9
    4. 4