alpsahin/tubitak-olimpiyat-dataset-v2 huggingface dataset:
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 20

Size verilen basit yönsüz bir çizge için aşağıdakilerden hangisi doğru olabilir?

Şıklar:
A) Çizgede 20 düğüm, 16 kenar ve 3 bağlı bileşen vardır. | B) Çizgede 6 düğüm, 11 kenar ve en az 2 bağlı bileşen vardır. | C) Çizgede 7 düğüm, 10 kenar ve en az 3 bağlı bileşen vardır. | D) Çizgede 5 düğüm, 10 kenar ve 10 döngü vardır. | E) Çizgede 8 düğüm ve 8 kenar vardır ve hiç döngü yoktur.

Cevap: C Çizgede 7 düğüm, 10 kenar ve en az 3 bağlı bileşen vardır.

Çözüm:
20 düğümlü bir çizgede 16 kenar varsa en az 4 bağlı bileşen olmak zorundadır. Bu yüzden cevap A şıkkı olamaz. 5 düğümlü bir bağlı bileşende en fazla 10 kenar olabilir. Bu yüzden 6 düğümlü bir çizgede 11 kenar var ise çizge bağlıdır. Dolayısıyla cevap B şıkkı olamaz. 5 düğümlü bir çizgede 10 kenar var ise çizge tam (complete) çizgedir ve dolayısıyla 16 döngü olmalıdır. O yüzden cevap D şıkkı olamaz. Bir çizgede 8 düğüm ve 8 kenar var ise döngü olmak zorundadır. Bu yüzden cevap E şıkkı olamaz. 7 düğümlü bir çizgenin 2 tane izole düğümü olur ve geri kalan 5 düğümün her ikilisi arasında bir kenar olursa C şıkkında verilen şartlar sağlanmış olur. Bu yüzden
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 21

## [21-22 soruları için açıklama]
Çizge boyama probleminde amaç en az sayıda renk kullanarak verilen bir çizgenin düğümlerini, komşu iki düğüm farklı renklerde olacak şekilde boyamaktır. Örneğin, 4 düğüm ve 4 kenardan oluşan ve bir kare şeklinde çizebileceğimiz bir çizgeyi boyamak için 2 renk gereklidir. Ama 4 düğüm ve 5 kenardan oluşan bir çizgeyi boyamak için 3 renk gereklidir.

---

10 düğüm ve 21 kenara sahip bir çizgeyi boyamak için en fazla kaç renk gerekebilir?

Şıklar:
A) 6 | B) 7 | C) 8 | D) 9 | E) 10

Cevap: B 7

Çözüm:
En fazla renk gerekecek durum çizgenin 7 düğümlü bir klik ve 3 izole düğümden oluştuğunda gerçekleşir. Bu durumda 7 renk gerekmektedir.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 22

## [21-22 soruları için açıklama]
Çizge boyama probleminde amaç en az sayıda renk kullanarak verilen bir çizgenin düğümlerini, komşu iki düğüm farklı renklerde olacak şekilde boyamaktır. Örneğin, 4 düğüm ve 4 kenardan oluşan ve bir kare şeklinde çizebileceğimiz bir çizgeyi boyamak için 2 renk gereklidir. Ama 4 düğüm ve 5 kenardan oluşan bir çizgeyi boyamak için 3 renk gereklidir.

---

10 düğüm ve 21 kenara sahip bir çizgevi boyamak için en az kaç renk gerekebilir?

Şıklar:
A) 2 | B) 3 | C) 4 | D) 5 | E) 6

Cevap: A 2

Çözüm:
5 düğüm bir tarafta diğer 5 düğüm diğer tarafta olacak şekilde bir ikili (bipartite) çizge düşünün. Bu çizgeye en fazla 25 kenar yerleştirilebilir ve bize soruda kenar sayısı 21 olarak verilmiş. Her ikili çizge 2 renkle boyanabileceği için
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 23

6 kişilik bir grupta iki arkadaş yan yana oturmak istememektedir. Bu durumda 6 arkadaş 6 kişilik bir koltuğa kaç farklı şekilde oturabilir?

Şıklar:
A) 120 | B) 240 | C) 480 | D) 500 | E) 720

Cevap: C 480

Çözüm:
Tüm durumlardan iki arkadaşın yan yana oturduğu durumların sayısını çıkartarak doğru sonuca ulaşabiliriz. Toplamda 6!=720 farklı oturma düzeni olacaktır. İki arkadaş yan yana oturduğu durumda 1 kişi olarak sayılabilir ve bu şekilde 5!=120 farklı oturma düzeni olacaktır. Ancak iki arkadaş da kendi aralarında 2!=2 şekilde oturabilir, o nedenle toplam sayı 120*2=240 farklı oturma düzeni olacaktır. Bu kümeyi toplam kümeden ayırırsak 720-240=480 farklı oturma düzeni edilmiş olacaktır.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 24

M E V S
E V S İ
V S İ M
Verilen şekle göre sol üst taraftan başlayıp sadece sağ veya aşağı yönlü bir adım atılarak MEVSİM yazısına erişmek istenmektedir. Kaç farklı şekilde MEVSİM yazılabilir?

Şıklar:
A) 4 | B) 6 | C) 10 | D) 12 | E) 20

Cevap: C 10

Çözüm:
Sadece sağ ve aşağı yönlü hareket olduğu için 3 kere aşağı ve 2 kere sağ hareketi yapılabilir durumdadır. Bunu hangi sırayla yaparsak yapalım MEVSİM kelimesine ulaşabilecektir. O nedenle toplam sayı 5!/3!2! ifadesiyle elde edilebilir. Doğru cevap 120/(6*2)=10 olacaktır.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 25

[25-27 soruları için açıklama]
Şartlı olasılık P(A|B) şeklinde ifade edilir ve B gerçekleştiği durumda A'nın gerçekleşme olasılığını verir. P(A|B) = P(A∩B) / P(B) olacak şekilde hesaplanır. Aynı biçimde P(B|A) = P(A∩B) / P(A) olacaktır.
<table><tr><td></td><td>Dışarı çıktı</td><td>Dışarı çıkmadı</td></tr><tr><td>Güneşli</td><td>3</td><td>2</td></tr><tr><td>Yağmurlu</td><td>4</td><td>0</td></tr><tr><td>Bulutlu</td><td>2</td><td>3</td></tr></table>
<table><tr><td></td><td>Dışarı çıktı</td><td>DİŞARİ ÇIKTADI</td></tr><tr><td>Nemli</td><td>3</td><td>4</td></tr><tr><td>Normal</td><td>6</td><td>1</td></tr></table>
Merve son 14 gün içinde hava durumuna göre kaç kere dışarı çıktığını yukarıdaki tabloda bir araya getirdi.
Aşağıdaki soruları bu tabloya göre çözümleyiniz.

---

Eldeki bilgilere göre Merve'nin dışarı çıktığı günlerde havanın güneşli olma ihtimali nedir?

Şıklar:
A) 3/5 | B) 3/9 | C) 5/14 | D) 3/14 | E) 2/3

Cevap: B 3/9

Çözüm:
Merve'nin dışarı çıktığı gün sayısı toplam 9'dur. Bu günler içinde sadece 3 gün güneşli olduğu için ihtimal değeri 3/9 olacaktır.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 26

[25-27 soruları için açıklama]
Şartlı olasılık P(A|B) şeklinde ifade edilir ve B gerçekleştiği durumda A'nın gerçekleşme olasılığını verir. P(A|B) = P(A∩B) / P(B) olacak şekilde hesaplanır. Aynı biçimde P(B|A) = P(A∩B) / P(A) olacaktır.
<table><tr><td></td><td>Dışarı çıktı</td><td>Dışarı çıkmadı</td></tr><tr><td>Güneşli</td><td>3</td><td>2</td></tr><tr><td>Yağmurlu</td><td>4</td><td>0</td></tr><tr><td>Bulutlu</td><td>2</td><td>3</td></tr></table>
<table><tr><td></td><td>Dışarı çıktı</td><td>DİŞARİ ÇIKTADI</td></tr><tr><td>Nemli</td><td>3</td><td>4</td></tr><tr><td>Normal</td><td>6</td><td>1</td></tr></table>
Merve son 14 gün içinde hava durumuna göre kaç kere dışarı çıktığını yukarıdaki tabloda bir araya getirdi.
Aşağıdaki soruları bu tabloya göre çözümleyiniz.

---

Eldeki bilgilere göre Merve'nin dışarı çıkma ihtimali ile havanın güneşli olma ihtimali hangi seçenekte sıralı biçimde doğru verilmiştir?

Şıklar:
A) 3/9, 2/5 | B) 9/14, 5/14 | C) 5/14, 4/14 | D) 3/5, 4/14 | E) 3/9, 6/9

Cevap: B 9/14, 5/14

Çözüm:
Toplam 14 gün vardır ve Merve 9 gün dışarı çıkmıştır. Bu durumda Merve'nin dışarı çıkma ihtimali 9/14 olacaktır. Bu 14 gün içinde 5 gün güneşli olduğu için havanın güneşli olma ihtimali 5/14 olacaktır.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 28

[25-27 soruları için açıklama]
Şartlı olasılık P(A|B) şeklinde ifade edilir ve B gerçekleştiği durumda A'nın gerçekleşme olasılığını verir. P(A|B) = P(A∩B) / P(B) olacak şekilde hesaplanır. Aynı biçimde P(B|A) = P(A∩B) / P(A) olacaktır.
<table><tr><td></td><td>Dışarı çıktı</td><td>Dışarı çıkmadı</td></tr><tr><td>Güneşli</td><td>3</td><td>2</td></tr><tr><td>Yağmurlu</td><td>4</td><td>0</td></tr><tr><td>Bulutlu</td><td>2</td><td>3</td></tr></table>
<table><tr><td></td><td>Dışarı çıktı</td><td>DİŞARİ ÇIKTADI</td></tr><tr><td>Nemli</td><td>3</td><td>4</td></tr><tr><td>Normal</td><td>6</td><td>1</td></tr></table>
Merve son 14 gün içinde hava durumuna göre kaç kere dışarı çıktığını yukarıdaki tabloda bir araya getirdi.
Aşağıdaki soruları bu tabloya göre çözümleyiniz.

---
Çizgeler hakkında aşağıda verilenlerden hangileri doğrudur: 
I. Yönsüz bir çizgede derecesi tek olan düğümlerin sayısı çifttir 
II. Eğer bir çizgede tüm düğümlerin derecesi çift sayıda ise hangi düğümden başlarsak başlayalım 
elimizi kaldırmadan tün çizgeyi gezebiliriz 
III. Ağaç yapısı çizgelerin yönlü olması durumunda anılan özel isimdir

Şıklar:
A) Yalnız I 
B) Yalnız II 
C) I ve II 
D) II ve III 
E) I ve III

Cevap: A Yalnız I

Çözüm:
Yalnız I doğrudur. II çizge bağlı bir çizge olmadığında doğru olmayacaktır. III de hatalıdır. Ağaç yapısı çizgelerin özel halidir ancak seçenekte verilen bilgi doğru değildir.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 29

[GÖRSEL]
Resimdeki gibi bir çizge eğer komşuluk listesi şeklinde gösterilecek olursa aşağıdakilerden hangisi doğrudur?

Şıklar:
A) A → C | B) B → A, C, D | C) C → A, D | D) D → B, C, D | E) A → A, B, C

Cevap: C C → A, D

Çözüm:
Komşuluk listesi ile gösterimde her bir düğüm liste şeklinde kendisinden gidilebilecek düğümleri tutmaktadır. Bu durumda; C-A ve C-D bağlantıları C’den çıkan tüm bağlantıları doğru bir şekilde gösterebildiği için C → A, D seçeneği doğru olacaktır.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 30

[30-32 soruları için açıklama]
Matrisler bilgisayar alanında çok fazla kullanılmaktadır. 3x2 bir matris \(A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \\ 5 & 6 \end{bmatrix}\) şeklinde ifade edilebilir.
Verilen matrisin 1. satır-1. sütununda 1 değeri ve 3. satır-1. sütununda 5 değeri bulunmaktadır. Matrisleri bir tam sayı ile çarpmak istediğimizde tüm elemanları verilen tam sayı ile çarpmamız gerekmektedir. Bundan daha zor olan işlem ise verilen iki matrisi birbiriyle çarpmaktır. Bunun için bazı şartların uygun olması gerekmektedir. mx2 boyutlarında bir matris ancak 2xn boyutlarında bir matris ile çarpılabilir. Yani ilk matrisin sütun sayısı ile ikinci matrisin satır sayısının aynı olması gerekmektedir. Elde edilen matris de mxn boyutlarında olacaktır. Elimizde iki adet matris verilmiş olsun;
\[A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \\ 4 & 6 \end{bmatrix} \text{ ve } B = \begin{bmatrix} 3 & 4 \\ 5 & 6 \end{bmatrix} \text{ bu durumda } A \times B = \begin{bmatrix} c_{11} & c_{12} \\ c_{21} & c_{22} \\ c_{31} & c_{32} \end{bmatrix} \text{ olacaktır}\]
A matrisinin ilk satırı B matrisinin ilk sütunundaki değerlerle sırayla çarpılıp \(c_{11}\) değeri (\(c_{11} = 1 * 3 + 2 * 5 = 13\)), A matrisinin ilk satırı B matrisinin ikinci sütunu ile çarpılıp \(c_{12}(c_{12} = 1 * 4 + 2 * 6 = 16)\) değeri elde edilecektir. Aynı şekilde A matrisinin ikinci satırı B matrisinin ilk sütunu ile çarpılıp \(c_{21}\) değeri, A matrisinin ikinci satırı B matrisinin ikinci sütunu ile çarpılıp \(C_{22}\) değeri elde edilecektir. Aynı işlem diğer satırlar için de tekrarlanmalıdır.

---

\[\begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix} \cdot \begin{pmatrix} 4 & 5 \\ 6 & 5 \\ 4 & 6 \end{pmatrix}\]
Verilen matris çarpımı için doğru sonuç aşağıdakilerden hangisidir?

Şıklar:
A) \(\begin{bmatrix} 28 & 33 \\ 28 & 31 \\ 28 & 33 \end{bmatrix}\) | B) \(\begin{bmatrix} 33 & 28 \\ 22 & 19 \end{bmatrix}\) | C) \(\begin{bmatrix} 19 & 22 & 18 \\ 22 & 22 & 17 \end{bmatrix}\) | D) \(\begin{bmatrix} 28 & 33 \\ 28 & 31 \end{bmatrix}\) | E) \(\begin{bmatrix} 22 & 22 & 17 \\ 19 & 22 & 18 \end{bmatrix}\)

Cevap: D \(\begin{bmatrix} 28 & 33 \\ 28 & 31 \end{bmatrix}\)

Çözüm:
İşlem çıktısı “Yani ilk matrisin sütun sayısı ile ikinci matrisin satir sayısının aynı olması gerekmektedir.” bilgisinde de verildiği gibi 2x2 matris olarak elde edilecektir. Birinci matrisin ilk satırı olan [1 2 3] değerleri ikinci matrisin ilk sütunu olan [4 6 4] değerleriyle çarplıp toplanacaktır. \(4 + 12 + 12=28\) sol üst köşedeki ilk eleman olacaktır. Diğer elemanlar da benzer şekilde hesaplanabilir ancak verilen her iki şartı da sağlayan tek seçenek D şıkkıdır.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 32

[30-32 soruları için açıklama]
Matrisler bilgisayar alanında çok fazla kullanılmaktadır. 3x2 bir matris \(A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \\ 5 & 6 \end{bmatrix}\) şeklinde ifade edilebilir.
Verilen matrisin 1. satır-1. sütununda 1 değeri ve 3. satır-1. sütununda 5 değeri bulunmaktadır. Matrisleri bir tam sayı ile çarpmak istediğimizde tüm elemanları verilen tam sayı ile çarpmamız gerekmektedir. Bundan daha zor olan işlem ise verilen iki matrisi birbiriyle çarpmaktır. Bunun için bazı şartların uygun olması gerekmektedir. mx2 boyutlarında bir matris ancak 2xn boyutlarında bir matris ile çarpılabilir. Yani ilk matrisin sütun sayısı ile ikinci matrisin satır sayısının aynı olması gerekmektedir. Elde edilen matris de mxn boyutlarında olacaktır. Elimizde iki adet matris verilmiş olsun;
\[A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \\ 4 & 6 \end{bmatrix} \text{ ve } B = \begin{bmatrix} 3 & 4 \\ 5 & 6 \end{bmatrix} \text{ bu durumda } A \times B = \begin{bmatrix} c_{11} & c_{12} \\ c_{21} & c_{22} \\ c_{31} & c_{32} \end{bmatrix} \text{ olacaktır}\]
A matrisinin ilk satırı B matrisinin ilk sütunundaki değerlerle sırayla çarpılıp \(c_{11}\) değeri (\(c_{11} = 1 * 3 + 2 * 5 = 13\)), A matrisinin ilk satırı B matrisinin ikinci sütunu ile çarpılıp \(c_{12}(c_{12} = 1 * 4 + 2 * 6 = 16)\) değeri elde edilecektir. Aynı şekilde A matrisinin ikinci satırı B matrisinin ilk sütunu ile çarpılıp \(c_{21}\) değeri, A matrisinin ikinci satırı B matrisinin ikinci sütunu ile çarpılıp \(C_{22}\) değeri elde edilecektir. Aynı işlem diğer satırlar için de tekrarlanmalıdır.

---

Verilen çizge için 3 adımda gidilebilecek yol sayıları hakkında aşağıdakilerden hangisi yanlıştır?

Şıklar:
A) \begin{bmatrix}
28 & 31 \\
28 & 33
\end{bmatrix}

B)
\begin{bmatrix}
33 & 28 \\
22 & 19
\end{bmatrix}

C)
\begin{bmatrix}
19 & 22 & 18 \\
22 & 22 & 17
\end{bmatrix}

D)
\begin{bmatrix}
28 & 33 \\
28 & 31
\end{bmatrix}

E)
\begin{bmatrix}
22 & 22 & 17 \\
19 & 22 & 18
\end{bmatrix}

Cevap: D \begin{bmatrix}
28 & 33 \\
28 & 31
\end{bmatrix}

Çözüm:
Bir önceki soruda bulunan A \times A matrisi A ile tekrar çarpılarak 3 adımda gidilebilen yol sayısı hesaplanmış olacaktır. Verilen işlem adımları uygulandığında elde edilecek sonuç:A \times A \times A = \begin{bmatrix}
2 & 1 & 0 & 1 \\
2 & 2 & 1 & 1 \\
1 & 1 & 1 & 1 \\
1 & 0 & 1 & 1
\end{bmatrix}
olacaktır. Bu durumda verilen seçenekler arasından yanlış olan D seçeneğinde verilen bilgidir. C’den gidilebilecek yol sayısı toplamda 4 olmalıdır.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 33

[33-35 soruları için açıklama]
Elif insanların konuşurken birçok kelimeyi tekrar ettiğini fark edince söylenen bir kelimenin daha önce geçmediğini bulan bir yapı kurmaya verir. Ancak geçmişte kullanılan kelimeleri kaydedip karşılaştırma işlemi yaparak karar vermesinin çok fazla işlem ve hafıza gerektirdiğini görür. Bunun üzerine aşağıda verilen algoritmayı geliştirmeye karar verir.
- Elif 14 boyutunda hepsinin ilk değeri 0 olan bir liste oluşturur. Bu listenin her bir elemanı bir biti temsil etmektedir
- Elif farklı özet(hash) fonksiyonları ile kendisine gelen bir kelimenin yeni değerlerini hesaplar. Özet fonksiyonları verilen bir girdiden belirli bir uzunlukta çıktı üreten tek yönlü özel bir fonksiyondur
- Özet fonksiyonu neticesinde çıkan sonucun mod 14 değeri hesaplanır ve listenin o elemanı 1 olarak değiştirilir
Bu sayede Elif kendisine gelen bir kelimenin özet fonksiyonlarını alır ve eğer listedeki pozisyonlardan birisi 0 olarak işaretlenmişse bu kelimenin daha önce geçmediğine karar verir.
Elif bu işlem için Türkçe alfabesinde yer alan harflerin sayı karşılıklarını kullanacaktır. A harfinin değeri 1 ve Z harfinin değeri 29 olacaktır. Büyük/küçük harf ayrımı bulunmamaktadır. Elif iki farklı özet fonksiyonu tanımlamıştır:
H1() fonksiyonu : verilen kelimede yer alan harflerin sayısal değerlerinin toplamı
H2() fonksiyonu : verilen kelimede yer alan harflerin sayı sal değerlerinin çarpımının mod 29 değeri

---

Başlangıç durumunda ilk eklenen kelime “evet” olursa listenin son hali nasıl olacaktır?

Şıklar:
A) <table><tr><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0</td><td>0<td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td></td></tr></table> | B) <table><tr><td>0</td><td>1</td><td>2</td><td>3</td><td>1</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td></tr></table> | C) <table><tr><td>0</td><td>1</td><td>2</td><td>3</td><td>2</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td></td><td>0</td><td>0</td><td>1</td><td>0</td></tr></table> | E) <table><tr><td>0</td><td>1</td><td>2</td><td>3</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td></tr></table>

Cevap: B <table><tr><td>0</td><td>1</td><td>2</td><td>3</td><td>1</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td></tr></table>

Çözüm:
Harflerin sayı değerleri şu şekildedir: e:6, v:27, e:6, t:24. Bu durumda H1(evet)=63 ve H2(evet)=12 olacaktır. Bu değerlerin mod 14 karşılıkları 7 ve 12 olacaktır. Bu durumda
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 34

[33-35 soruları için açıklama]
Elif insanların konuşurken birçok kelimeyi tekrar ettiğini fark edince söylenen bir kelimenin daha önce geçmediğini bulan bir yapı kurmaya verir. Ancak geçmişte kullanılan kelimeleri kaydedip karşılaştırma işlemi yaparak karar vermesinin çok fazla işlem ve hafıza gerektirdiğini görür. Bunun üzerine aşağıda verilen algoritmayı geliştirmeye karar verir.
- Elif 14 boyutunda hepsinin ilk değeri 0 olan bir liste oluşturur. Bu listenin her bir elemanı bir biti temsil etmektedir
- Elif farklı özet(hash) fonksiyonları ile kendisine gelen bir kelimenin yeni değerlerini hesaplar. Özet fonksiyonları verilen bir girdiden belirli bir uzunlukta çıktı üreten tek yönlü özel bir fonksiyondur
- Özet fonksiyonu neticesinde çıkan sonucun mod 14 değeri hesaplanır ve listenin o elemanı 1 olarak değiştirilir
Bu sayede Elif kendisine gelen bir kelimenin özet fonksiyonlarını alır ve eğer listedeki pozisyonlardan birisi 0 olarak işaretlenmişse bu kelimenin daha önce geçmediğine karar verir.
Elif bu işlem için Türkçe alfabesinde yer alan harflerin sayı karşılıklarını kullanacaktır. A harfinin değeri 1 ve Z harfinin değeri 29 olacaktır. Büyük/küçük harf ayrımı bulunmamaktadır. Elif iki farklı özet fonksiyonu tanımlamıştır:
H1() fonksiyonu : verilen kelimede yer alan harflerin sayısal değerlerinin toplamı
H2() fonksiyonu : verilen kelimede yer alan harflerin sayı sal değerlerinin çarpımının mod 29 değeri

---

Birkaç kelime eklendikten sonra listenin son hali aşağıdaki gibiye verilen kelimelerden hangisi listede yoktur?

Şıklar:
A) baş | B) son | C) dün | D) hep | E) yek

Cevap: D hep

Çözüm:
Verilen her bir seçenek için h1 ve h2 fonksiyonlarının hesaplanması gerekmektedir: H1(baş)=12, H1(son)=1, H1(dün)=6, H1(hep)=8, H1(yek)=6; H2(baş)=3, H2(son)=4, H2(dün)=6, H2(hep)=11, H2(yek)=3. 8 numaralı eleman işaretlenmediği için
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 35

[33-35 soruları için açıklama]
Elif insanların konuşurken birçok kelimeyi tekrar ettiğini fark edince söylenen bir kelimenin daha önce geçmediğini bulan bir yapı kurmaya verir. Ancak geçmişte kullanılan kelimeleri kaydedip karşılaştırma işlemi yaparak karar vermesinin çok fazla işlem ve hafıza gerektirdiğini görür. Bunun üzerine aşağıda verilen algoritmayı geliştirmeye karar verir.
- Elif 14 boyutunda hepsinin ilk değeri 0 olan bir liste oluşturur. Bu listenin her bir elemanı bir biti temsil etmektedir
- Elif farklı özet(hash) fonksiyonları ile kendisine gelen bir kelimenin yeni değerlerini hesaplar. Özet fonksiyonları verilen bir girdiden belirli bir uzunlukta çıktı üreten tek yönlü özel bir fonksiyondur
- Özet fonksiyonu neticesinde çıkan sonucun mod 14 değeri hesaplanır ve listenin o elemanı 1 olarak değiştirilir
Bu sayede Elif kendisine gelen bir kelimenin özet fonksiyonlarını alır ve eğer listedeki pozisyonlardan birisi 0 olarak işaretlenmişse bu kelimenin daha önce geçmediğine karar verir.
Elif bu işlem için Türkçe alfabesinde yer alan harflerin sayı karşılıklarını kullanacaktır. A harfinin değeri 1 ve Z harfinin değeri 29 olacaktır. Büyük/küçük harf ayrımı bulunmamaktadır. Elif iki farklı özet fonksiyonu tanımlamıştır:
H1() fonksiyonu : verilen kelimede yer alan harflerin sayısal değerlerinin toplamı
H2() fonksiyonu : verilen kelimede yer alan harflerin sayı sal değerlerinin çarpımının mod 29 değeri

---

Elif'in geliştirdiği bu yöntemle alakalı aşağıda verilenlerden hangisi doğrudur
I. Elif'in yöntemi bir kelimenin daha önce geçmediğini kesin olarak bulabilir
II. Elif bu yöntemle bir kelimenin daha önce geçtiğini kesin olarak bulabilir
II. Bazı kelimeler sadece bir pozisyonu etkileyebilir

Şıklar:
A) Yalnız I | B) Yalnız II | C) I ve II | D) I ve III | E) II, III

Cevap: D I ve III

Çözüm:
Anlatılan yöntem daha önce geçen kelimelerin özet fonksiyon değerlerini listeye eklemektedir. Eğer özet fonksiyonun işaret ettiği liste elemanlarından birisi 0 ise bu durumda bu kelimenin daha önce geçmediği kesin olarak ifade edilebilmektedir. Ancak daha önce geçtiği konusunda kesin bir ifade kullanılamayacaktır.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 36

[36-50 soruları için açıklama]
- Soruları C programlama dili çerçevesinde cevaplayınız.
- Derleyici olarak gcc kullanıldığını varsayınız.
- Gerekli tüm başlık (header) dosyalarının verilen programa dahil edildiğini varsayınız.

---

Aşağıdaki program ekrana kaç tane ‘A’ karakteri yazar?
```c
int main()
{
char S[5] = "ABBA";
int i, j;
for (i=10; i; i=i-2)
for (j=i; j%3; j++)
printf("%c\n", S[j%4]);
}
```

Şıklar:
A) 0 | B) 3 | C) 9 | D) 15 | E) Program derleme hatası verir

Cevap: B 3

Çözüm:
Program çalıştırıldığında ekrana 6 ayrı satırda sırasıyla B A A A B B basip sonra sonlanır. Yani
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 37

[36-50 soruları için açıklama]
- Soruları C programlama dili çerçevesinde cevaplayınız.
- Derleyici olarak gcc kullanıldığını varsayınız.
- Gerekli tüm başlık (header) dosyalarının verilen programa dahil edildiğini varsayınız.

---

Aşağıdaki program parçası ekrana kaç tane ‘A’ karakteri yazar?
```c
for (i=0; i<=N; i++)
for (j=i; j<=N; j++)
printf("A\N");
```

Şıklar:
A) \(N^2\) | B) \(N^2 + 2N + 1\) | C) \(\frac{N^2}{2} + \frac{N}{2}\) | D) \(\frac{N^2}{2} + \frac{3N}{2} + 1\) | E) \(N^3\)

Cevap: D \(\frac{N^2}{2} + \frac{3N}{2} + 1\)

Çözüm:
i döngüsü ilk kez çalıştığında yani i 0 iken, j döngüsü N+1 kez çalışacaktır. Daha sonra en son bir kez çalışana kadar her seferinde birer kez azalarak çalışacaktır. Bu durumda ekrana basılan A karakteri sayısı 1'den N+1'e kadar olan sayıların toplamıdır. Bu da (N+1)(N+2)/2'ye eşittir. Bu ifadenin açık hali D şıkkında verilmiştir. Yani
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 38

[36-50 soruları için açıklama]
- Soruları C programlama dili çerçevesinde cevaplayınız.
- Derleyici olarak gcc kullanıldığını varsayınız.
- Gerekli tüm başlık (header) dosyalarının verilen programa dahil edildiğini varsayınız.

---

Aşağıdaki programın çıktısı şıklardan hangisinde doğru olarak verilmiştir?
```c
int main() {
int b=5, c=6, d=7;
d = 2*b;
b = d;
c = 1+b/d;
d = d % c;
printf("%d\n", b/c+d-b/2);
}
```

Şıklar:
A) 0 | B) 1 | C) 2 | D) 3 | E) 4

Cevap: A 0

Çözüm:
c ve d değişkenlerinin ilk değerlerinden bağımsız olarak d, b'nin ilk değerin olan 5'in iki katına yani bir çift sayı olan 10'a eşitlenir. Daha sonra b de 10 olur. d ve b eşit olduğu için c'nin değeri 1+1 =2 olur. d bir çift sayı olduğu için mod 2 değeri 0 olduğundan d'nin son değeri 0 olur. b/c+d-b/2 ifadesi b'nin değerinden bağımsız olarak c 2 olduğu ve d de 0 olduğu için b/2 - b/2 yani 0 olur.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 39

[36-50 soruları için açıklama]
- Soruları C programlama dili çerçevesinde cevaplayınız.
- Derleyici olarak gcc kullanıldığını varsayınız.
- Gerekli tüm başlık (header) dosyalarının verilen programa dahil edildiğini varsayınız.

---

Aşağıdaki fonksiyonun amacı ne olabilir?
```c
int f(int n, int m) {
int i, r=1;
for (i = 0; i < m; i++)
{
r *= (n - i);
r /= (i + 1);
}
return r;
}
```

Şıklar:
A) n'nin m. kuvvetini hesaplamak | B) n'nin faktöriyelini hesaplamak | C) n'nin m'li kombinasyonunu hesaplamak | D) n faktöriyel ve m faktöriyelin çarpımını hesaplamak | E) Hiçbiri

Cevap: C n'nin m'li kombinasyonunu hesaplamak

Çözüm:
Bu fonksiyonda sırayla n'den başlayıp aşağıya doğru değerler çarpılmakta ve sonuç 1'den başlayıp m-1'e kadar olan değerlere bölünmektedir. Yani hesaplanan değer n!/(m!(n-m))'e eşittir. Bu da n'nin m'li kombinasyonunun formülüdür. Yani