प्रौद्योगिकी साझेदारी

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

लेखक मुखपृष्ठ: झी गुयुन् ज़ीउतः बहिः आगच्छति

1. बहुविकल्पप्रश्नाः: मूलभूतसंकल्पनानां मूलभूतक्रियाणां च परीक्षणं कुर्वन्तु
2. रिक्तस्थानानि पूरयन्तु: मूलसंकल्पनानां विवरणानां च अवगमनं सुदृढं कुर्वन्तु
3. लघु उत्तर प्रश्न: सैद्धान्तिकज्ञानस्य निपुणतायाः परीक्षणं कुर्वन्तु
4. प्रोग्रामिंग प्रश्न: वास्तविकप्रोग्रामिंगक्षमतायाः तथा आँकडासंरचना अनुप्रयोगस्य परीक्षणं कुर्वन्तु
5. 

डेटा संरचना अनुकरण आयतन

1. बहुविकल्पप्रश्नाः (प्रत्येकं 2 अंकाः, कुलम् 20 अंकाः)

1. सरणीयां तत्त्वस्य निवेशनस्य समयजटिलता () भवति ।
   अ० ओ(१) ९.
   ख. ओ(न) ९.
   सी. ओ(लोग् न) ९.
   D. ओ(न^2) .

2. heap sort इत्यस्मिन् अधिकतमं heap इत्यस्य निर्माणस्य समयजटिलता () भवति ।
   अ० ओ(न) २.
   B. ओ(न लॉग न) .
   सी. ओ(लोग् न) ९.
   D. ओ(न^2) .

3. रक्तकृष्णवृक्षः () इति प्रकारः ।
   उ. सम्पूर्णः द्विचक्रीयवृक्षः
   ख. संतुलितः द्विचक्रीयवृक्षः
   ग. मिन्-राशिः
   D. अधिकतमराशिः

4. hash tables विषये निम्नलिखितवाक्येषु कः अशुद्धः () ।
   उ. हैश-सारणीयाः लुकअप-समय-जटिलता O(1) अस्ति ।
   B. हैश सारणीयाः सम्मिलनसमयजटिलता O(1) अस्ति ।
   C. हैश टेबल्स् विग्रहाणां समाधानं कर्तुं शक्नुवन्ति
   D. हैश सारणीयाः अन्वेषणसमयजटिलता O(1) भवितुमर्हति ।

5. आलेख-अन्तरगमने गभीरता-प्रथम-अन्वेषणस्य (DFS) तथा विस्तार-प्रथम-अन्वेषणस्य (BFS) समय-जटिलता क्रमशः () भवति ।
   उ. ओ(वि + ई) तथा ओ(वि) २.
   B. O(V^2) तथा O(V) .
   ग. ओ(व + ई) तथा ओ(व + ई) .
   D. O(V) तथा O(V^2) .

6. एकदिशालिङ्कितसूचीं विपर्ययितुं समयजटिलता () भवति ।
   अ० ओ(१) ९.
   ख. ओ(न) ९.
   सी. ओ(लोग् न) ९.
   D. ओ(न^2) .

7. द्विचक्रीय-अन्वेषण-वृक्षे नोड्-विलोपनस्य दुष्टतम-समय-जटिलता () भवति ।
   अ० ओ(१) ९.
   ख. ओ(न) ९.
   सी. ओ(लोग् न) ९.
   D. ओ(न लॉग न) .

8. निम्नलिखित क्रमाङ्कन-अल्गोरिदम्-मध्ये कस्य O(n log n)() इत्यस्य औसतसमयजटिलता अस्ति ।
   उ. बुदबुदा क्रमेण
   B. शीघ्रं क्रमणं कुर्वन्तु
   ग. सम्मिलन क्रमबद्धता
   D. चयनक्रमणम्

9. द्विचक्रीयवृक्षे नोडस्य डिग्री () भवति ।
   उ. अस्य नोडस्य बालग्रन्थिसङ्ख्या
   ख. नोडस्य गभीरता
   ग. नोडस्य ऊर्ध्वता
   D. नोडस्य स्तरः

10. ख-वृक्षस्य ब+-वृक्षस्य च मुख्यः अन्तरः () अस्ति ।
    A. B वृक्षस्य सर्वे नोड्स् दत्तांशं संगृह्णन्ति, यदा तु B+ वृक्षस्य केवलं लीफ् नोड् दत्तांशं संगृह्णन्ति ।
    B. B-वृक्षः B+ वृक्षात् अधिकं सन्तुलितः भवति
    ग. B-वृक्षस्य सम्मिलन-विलोपन-क्रियाः सरलतराः सन्ति
    D. B+ वृक्षस्य अन्वेषणदक्षता न्यूना भवति

2. रिक्तं पूरयितुं प्रश्नाः (प्रत्येकं 3 अंकाः, कुलम् 15 अंकाः)

1. n नोड्स् युक्तस्य सम्पूर्णस्य द्विचक्रीयवृक्षस्य ऊर्ध्वता ______ भवति ।
2. द्रुतक्रमणस्य औसतसमयजटिलता ______ भवति ।
3. लिङ्क्ड् सूचीयां kth तत्त्वस्य अन्वेषणस्य समयजटिलता ______ भवति ।
4. आलेखस्य समीपतामात्रिकप्रतिपादनस्य स्थानजटिलता ______ भवति ।
5. हफमैन् वृक्षे भारितमार्गदीर्घता ______ इति गण्यते ।

3. लघु उत्तरप्रश्नाः (प्रत्येकं १० अंकाः, कुलम् ३० अंकाः)

1. रक्तकृष्णवृक्षाणां गुणाः संक्षेपेण वर्णयन्तु, रक्तकृष्णवृक्षाः कथं संतुलनं धारयन्ति इति व्याख्यातव्यम् ।
2. गतिशीलसरणयः, लिङ्क्ड् सूचीः च मध्ये अन्तरं व्याख्यातव्यम्, तेषां लाभाः, हानिः, अनुप्रयोगपरिदृश्यानि च चर्चां कुर्वन्तु ।
3. हैश टेबल् इत्यस्य सिद्धान्तान् वर्णयन्तु तथा च टकरावस्य निवारणं कथं करणीयम् इति व्याख्यातव्यम् ।

4. प्रोग्रामिंग् प्रश्नाः (प्रत्येकं १५ अंकाः, कुलम् ३५ अंकाः)

1. कृपया एकं कार्यं कार्यान्वितं कृत्वा निर्धारयितुं शक्यते यत् लिङ्क् कृता सूची palindrome लिङ्क् कृता सूची अस्ति वा इति ।

   def is_palindrome(head):
       # 请在这里编写代码
   1
   2

2. कृपया द्विचक्रीय अन्वेषणवृक्षे सम्मिलनक्रिया कार्यान्वितुं कोडं लिखन्तु ।

   class TreeNode:
       def __init__(self, key):
           self.left = None
           self.right = None
           self.val = key
   
   def insert(root, key):
       # 请在这里编写代码
   1
   2
   3
   4
   5
   6
   7
   8

3. एकं आलेखं दत्तं, यत् समीपता-मात्रिकायाः ​​प्रतिनिधित्वं भवति, व्यापकता-प्रथम-अन्वेषणं (BFS) कार्यान्वयन्तु ।

   def bfs(graph, start):
       # 请在这里编写代码
   1
   2

उत्तरम्‌

1. बहुविकल्पप्रश्नाः

1. ख
2. एकः
3. ख
4. घ
5. ग
6. ख
7. ख
8. ख
9. एकः
10. एकः

2. रिक्तस्थानानि पूरयन्तु

1. log(n+1) गोल अधः
2. ओ(न लॉग न) २.
3. इत्युपरि)
4. ओ(वि^२) ९.
5. सर्वेषां पत्रग्रन्थिनां भारितमार्गदीर्घतायाः योगः

3. लघु उत्तरप्रश्नाः

1. रक्तकृष्णवृक्षगुणाः：

   • गुणः १: प्रत्येकं नोड् रक्तं कृष्णं वा भवति ।
   • गुणः २ : मूलग्रन्थिः कृष्णवर्णीयः अस्ति ।
   • गुणः ३ : प्रत्येकं पत्रग्रन्थिः (NIL नोड्) कृष्णवर्णीयः भवति ।
   • गुणः ४: यदि कश्चन नोडः रक्तः भवति तर्हि तस्य बालग्रन्थिद्वयं कृष्णवर्णीयं भवति (अर्थात् प्रत्येकं पत्रात् मूलपर्यन्तं सर्वेषु मार्गेषु द्वौ क्रमिकौ रक्तग्रन्थौ न भवितुमर्हति)।
   • गुणः ५ : कस्यापि नोडतः तस्य प्रत्येकं पत्रं यावत् सर्वेषु सरलमार्गेषु कृष्णा नोड्स् समानसङ्ख्याः सन्ति ।

   रक्तकृष्णवृक्षाः कथं संतुलनं धारयन्ति：

   • सम्मिलन-विलोपन-क्रियाणां अनन्तरं रक्त-कृष्ण-वृक्षस्य गुणाः परिभ्रमणं पुनः रङ्गं च कृत्वा निर्वाहिताः भवन्ति, तस्मात् वृक्षस्य ऊर्ध्वता सर्वदा O(log n) परिधिमध्ये एव तिष्ठति इति सुनिश्चितं भवति

2. डायनामिक एरे तथा लिङ्क्ड् लिस्ट् इत्येतयोः मध्ये अन्तरम्：

   • गतिशीलसरणयः (यथा पायथन् मध्ये सूचीः): स्मृतिः निरन्तरं भवति, अनुक्रमणिकाद्वारा तत्त्वानि शीघ्रं प्राप्तुं शक्यन्ते, सम्मिलन-विलोपन-क्रियासु चलतत्त्वानां आवश्यकता भवति, समयजटिलता च O(n) भवति
   • लिङ्क्ड् सूची: स्मृतिः निरन्तरं न भवति तथा च सूचकानाम् (सन्दर्भाणां) माध्यमेन सम्बद्धा भवति सम्मिलन-विलोपन-क्रियाणां समयजटिलता O(1), परन्तु तत्त्वानां अन्वेषणस्य समयजटिलता O(n) भवति ।
   • लाभाः हानिः च：
     • गतिशीलसरणिका : लाभः अस्ति यत् यादृच्छिकप्रवेशः द्रुतगतिः भवति, परन्तु दोषः अस्ति यत् सम्मिलनं विलोपनं च मन्दं भवति, अतः विस्तारस्य आवश्यकता भवितुम् अर्हति ।
     • लिङ्क्ड् लिस्ट् : लाभः अस्ति यत् सम्मिलनं विलोपनं च द्रुतं भवति, परन्तु दोषः अस्ति यत् यादृच्छिकप्रवेशः मन्दः भवति तथा च अधिका स्मृतिः गृह्णाति (यतोहि सूचकानाम् संग्रहणं आवश्यकम्)
   • अनुप्रयोग परिदृश्य：
     • गतिशीलसरणयः तादृशानां परिदृश्यानां कृते उपयुक्ताः सन्ति यत्र तत्त्वानि बहुधा अभिगन्तुं आवश्यकं भवति तथा च आकारः बहुधा परिवर्तनं न भवति, यथा संग्रहणम् ।
     • लिङ्क्ड् सूचीः तादृशानां परिदृश्यानां कृते उपयुक्ताः सन्ति येषु तत्त्वानां नित्यं निवेशनं विलोपनं च आवश्यकं भवति, यथा कतारं, ढेरं च कार्यान्वितुं ।

3. हैश टेबलस्य सिद्धान्तः：

   • हैश-सारणीः हैश-कार्यस्य माध्यमेन अनुक्रमणिकास्थानानि सरणीं कर्तुं कुञ्जीनां नक्शाङ्कनं कुर्वन्ति, येन द्रुत-अन्वेषणं, सम्मिलनं, विलोपन-क्रियाः च सक्षमाः भवन्ति ।
   • विग्रहान् कथं सम्पादयितव्यम्：
     • मुक्तसङ्केतविधिः : द्वन्द्वस्य सन्दर्भे रेखीयपरिचयः, गौणपरिचयः इत्यादीनां पद्धतीनां उपयोगः अग्रिममुक्तस्थानं अन्वेष्टुं भवति ।
     • श्रृङ्खला-सङ्केत-विधिः : यदा विग्रहः भवति तदा समान-हैश-मूल्येन सह तत्त्वानि लिङ्क्-कृत-सूचौ संगृह्यन्ते ।

4. प्रोग्रामिंग् प्रश्नाः

1. लिङ्क् कृतसूची palindrome लिङ्क् कृता सूची अस्ति वा इति निर्धारयन्तु:

   class ListNode:
       def __init__(self, x):
           self.val = x
           self.next = None
   
   def is_palindrome(head):
       # 使用快慢指针找到链表中点
       slow = fast = head
       while fast and fast.next:
           slow = slow.next
           fast = fast.next.next
       
       # 反转后半部分链表
       prev = None
       while slow:
           temp = slow.next
           slow.next = prev
           prev = slow
           slow = temp
       
       # 比较前半部分和后半部分
       left, right = head, prev
       while right:
           if left.val != right.val:
               return False
           left = left.next
           right = right.next
       return True
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28

2. द्विचक्रीय अन्वेषणवृक्षे सम्मिलनक्रिया : १.

   class TreeNode:
       def __init__(self, key):
           self.left = None
           self.right = None
           self.val = key
   
   def insert(root, key):
       if root is None:
           return TreeNode(key)
       if key < root.val:
           root.left = insert(root.left, key)
       else:
           root.right = insert(root.right, key)
       return root
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14

3. व्यापकता प्रथम अन्वेषण (BFS): 1.1.

   from collections import deque
   
   def bfs(graph, start):
       visited = [False] * len(graph)
       queue = deque([start])
       visited[start] = True
       result = []
   
       while queue:
   
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10