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
