Data Structures Past Paper (Arabic) PDF
Document Details
Uploaded by FirmerTellurium
SENA
Tags
Summary
This document contains examples and questions on different types of hashing techniques, including linear probing, quadratic probing, and double hashing, with calculations shown step-by-step in detail.
Full Transcript
## Sec 3 ### 2. Open Addressing, closed hashing: #### (a) linear Probing: * `key+1)% length` Collision لو Øصل ex. | 38 | 19 | 8 | 79 | 10 | |---|---|---|---|---| | 38%10 = 8 | 19%10 = 9 | 8%10 = 8 | 79%10 = 9 | 10%10 = 0 | | | | G<sub>8%10=8</sub> | G<sub>9%10=9</sub> | G<sub>10%10=0</sub> | | |...
## Sec 3 ### 2. Open Addressing, closed hashing: #### (a) linear Probing: * `key+1)% length` Collision لو Øصل ex. | 38 | 19 | 8 | 79 | 10 | |---|---|---|---|---| | 38%10 = 8 | 19%10 = 9 | 8%10 = 8 | 79%10 = 9 | 10%10 = 0 | | | | G<sub>8%10=8</sub> | G<sub>9%10=9</sub> | G<sub>10%10=0</sub> | | | | | | G<sub>11%10=1</sub> | | | | | | G<sub>12%10=2</sub> | | | | G<sub>9%10=9</sub> | G<sub>80%10=0</sub> | G<sub>81%10=1</sub> | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 8 | 9 | | 8 | 79 | 10 | | | | | | 38 | 19 | #### (b) Quadratic Probing: * `(key+i²) % size` Collision لو Øصل ex. | 89 | 18 | 49 | 58 | 79 | |---|---|---|---|---| | 89%10 = 9 | 18%10 = 8 | 49%10 = 9 | 58%10 = 8 | 79%10 = 9 | | | | | G<sub>59%10=9</sub> | | | | | | G<sub>62%10=2</sub> | | | | | G<sub>50%10=0</sub> | | G<sub>83%10=3</sub> | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | 49 | 58 | 79 | | | | 18 | 89 | ex. | 2 | 15 | 7 | 10 | 31 | 26 | 44 | 57 | |---|---|---|---|---|---|---|---| | 2%13 = 2 | 15%13 = 2 | 7%13 = 7 | 10%13 = 10 | 31%13 = 5 | 26%13 = 0 | 44%13 = 5 | 57%13 = 5 | | 2 | | 7 | | 5 | | 5 | 5 | | | G<sub>16%13=3</sub> | | | | | G<sub>45%13=6</sub> | G<sub>61%13=7</sub> | | | | | | | | | G<sub>60%13=8</sub> | #### (c) double hashing: * `h(key) = key % T` , `T=10` size , تبلوم عندی fonc 2 * `g(key) = 1+[(key/+) % (T-1)]` ## / / ## 13 28 33 147 43 | 13 | 28 | 33 | 147 | 43 | |---|---|---|---|---| | 13%10 = 3 | 28%10 = 8 | 33%10 = 3 | 147%10 = 7 | 43%10 = 3 | | | | | (7) | | | | | (3) | | G<sub>1+[(43/10)%9]</sub> | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | | | | 13 | 33 | 43 | 47 | 28 | ## Q7-11 mid 2021 **h(k) = k% to** * `S=23,42,34,46,33` * dala wahada - `linear` ## (4) Possible order keys have been Inserted ? منØرب الإختيارات * `46,42,34,52,23,33` * `42,52,34,23,46,33` - linear $\times$ * `42,52,34,46,23,33` - quadrati $\times$ * `34,42,23,52,33,46` - linear $\times$ * `42,23,34, 52,33,46` - quadratic $\times$ * `46, 34, 42, 23, 52, 33` * `42,23,34,52,46,33` - linear $\times$ ## (8) type of hash - closed hashing, open addressing ## (9) 11 collisions-quadratic ## (10) Index of key = 66. * `66%10 = 6` , `70%10 = 0` ## (11) load factor = 1/1 = 0.7
