Aof Panel

Soru 1

Verilen çizgede enine arama algoritması uygulanıyor ve birden fazla komuşusu olan düğümler için alfabetik olarak önce küçük olan ziaret ediliyor. Numaralandırımış bağlantıların ziyaret sırasına göre küçükten büyüğe sıralanışı aşağıdakilerin hangisinde doğru olarak verilmiştir?

Soru 2

Verilen çizgede enine arama algoritması uygulanıyor. Ziyaret edilen düğümler aşağıdakilerden hangisinde doğru sırada verilmiştir?

Soru 3

Verilen çizgede, başlangıç düğümü S olacak şekilde, önce enine arama algoritması, sonrasında ise önce derinliğine arama algoritması uygulanacak ve birden fazla komşusu olan düğümlerde ziyaret sırası alfabetik olarak küçükten büyüğe olarak gerçekleştirilecektir. Her iki arama algoritması ziyaret edilme sırasına göre karşılaştırıldığında, hangi düğümlerin ziyaret edilme sırası değişmemektedir?

Soru 4

Verilen çizgede, başlangıç noktası S olacak şekilde
enine arama algoritması çalıştırılacak, bir düğümün birden
fazla komşusu varsa, bu komşular alfabetik olarak küçükten
büyüğe doğru ziyaret edilecektir. Buna göre çizgedeki
düğümlerin ziyaret edilme sırası aşağıdakilerden hangisinde doğru olarak verilmiştir?

Soru 5

Verilen çizgede, başlangıç noktası S olacak şekilde
önce derinliğine arama algoritması çalıştırılacak, bir düğümün birden
fazla komşusu varsa, bu komşular alfabetik olarak küçükten
büyüğe doğru ziyaret edilecektir. Buna göre çizgedeki
düğümlerin ziyaret edilme sırası aşağıdakilerden hangisinde doğru olarak verilmiştir?

Soru 6

Verilen çizgede, başlangıç noktası S olacak şekilde
önce derinliğine arama algoritması çalıştırılacak, bir düğümün birden
fazla komşusu varsa, bu komşular alfabetik olarak küçükten
büyüğe doğru ziyaret edilecektir. Buna göre çizgedeki
düğümlerin ziyaret edilme sırası aşağıdakilerden hangisinde doğru olarak verilmiştir?

Soru 7

Verilen çizgede, başlangıç noktası S olacak şekilde
enine arama algoritması çalıştırılacak, bir düğümün birden
fazla komşusu varsa, bu komşular alfabetik olarak küçükten
büyüğe doğru ziyaret edilecektir. Buna göre çizgedeki
düğümlerin ziyaret edilme sırası aşağıdakilerden hangisinde doğru olarak verilmiştir?

Soru 8

Çizgelere ilişkin olarak yukarıda yer alan ifadelerden hangileri doğrudur?

Çözüm Açıklaması

Çizge (graph), düğümlerle bu düğümleri birbirine bağlayan kenarlardan oluşan ve ağ görünümünde olan bir tür veri yapısıdır. Temel olarak birbirleriyle ilişkili verileri temsil etmek için kullanılırlar. Çizgelerin ulaşım, bilgisayar ağları, elektrik devreleri, sosyal ağlar gibi günlük hayattaki birçok alanda uygulamaları mevcuttur. Örneğin, bir sosyal ağ uygulamasını göz önüne aldığımızda, burada kullanıcılar ve kullanıcılar arasında arkadaşlık ilişkilerinden bahsedebiliriz. Her bir kullanıcı ayrı bir düğüm noktası olarak ele alındığında, bazı düğümler diğer düğümlerle bağlantılı durumda olacaktır. Herhangi bir çizgenin içerdiği düğümler, özel arama algoritmalarıyla bir noktadan başlanarak belirli sırada ziyaret edilebilmekte ve listelenebilmektedir. Çizgeler üzerinde bu işlemin yapılabilmesi için temel olarak enine arama (breadth-first search) ve önce derinliğine arama (depth-first search) algoritmaları mevcuttur. Bunun yanısıra, çizgelerin içerdiği düğüm noktaları arasındaki en kısa mesafelerin hesaplanması da söz konusu olabilir. Örneğin, bir şehirden başka bir şehire araçla en hızlı şekilde ulaşılmak istenildiğini varsayalım. Bu durumda, ilgili haritadaki tüm şehirler birer düğüm noktası olur ve belli düğüm noktaları arasında bağlantılar bulunur. Bu konuda uygun çözümlere ulaşmak için çeşitli “en kısa yol bulma” algoritmaları mevcuttur. Ünitemizde, bu tipte en yaygın algoritmalardan birisi olan Dijkstra en kısa yol algoritması anlatılmaktadır. Bu algoritma, çizgenin içerisindeki herhangi bir düğüm noktasından diğer tüm düğüm noktalarına olan en kısa mesafeleri hesaplamak ve bu mesafelerin elde edilmesi için izlenecek yolları belirlemek için kullanılır. Ünitemizin ilerleyen bölümlerinde, öncelikle çizgelerle ilgili temel kavramlar ve şu ana kadar bahsedilen algoritmalar örnekler yardımıyla detaylı olarak açıklanacaktır. Ayrıca, ilgili bölümlerde algoritmaların C program kodu ile nasıl ifade edildikleri gösterilecektir.

Bu bilgilerden de anlaşıldığı gibi doğru cevap E’dir. Çizgelere ilişkin olarak seçeneklerde yer alan ifadelerin tümü doğrudur.

Soru 9

Çizgelere ilişkin olarak seçeneklerde yer alan ifadelerden hangileri doğrudur?

Soru 10

Çizgelere ilişkin olarak seçeneklerde yer alan ifadelerden hangileri doğrudur?

Soru 11

Çizgelere ilişkin olarak seçeneklerde yer alan ifadelerden hangileri doğrudur?

Soru 12

Çizgelerde enine arama algoritmasına ilişkin olarak seçeneklerde yer alan ifadelerden hangileri doğrudur?

Soru 13

Çizgelerde enine arama ve önce derinliğine arama algoritmalarında ilişkin olarak seçeneklerde yer alan ifadelerden hangileri doğrudur?

Soru 14

Dijktra algoritmasına ilişkin olarak seçeneklerde yer alan ifadelerden hangileri doğrudur?

Soru 15

Dijkstra algoritmasına ilişkin olarak yukarıdaki seçeneklerde yer alan ifadelerden hangisi/hangileri doğrudur?

Soru 16

Çizge üzerinde enine arama algoritmasının C program kodu ile ifade edilişine ilişkin olarak seçeneklerde yer alan ifadelerden hangileri doğrudur?

Çözüm Açıklaması

Enine arama algoritmasının çalışma mantığının anlatıldığı Örnek 8.1’de (Sayfa 154, 155 ve 156) çizge ve kuyruk veri yapısı için kullanılan değişken ve fonksiyonlar bulunmaktadır. Öncelikle, kuyruk veri yapısı kuyruk isimli bir değişken kullanılarak gerçekleştirilmektedir. Şekil 8.4 ve 8.5’te (Sayfa 152 ve 153) görülen kuyruğa ekleme, çıkarma işlemleri için kuyruga_ekle ve kuyruktan_cikar gibi fonksiyonlar bulunmaktadır. Bir diğer fonksiyon olan kuyruk_bos ise kuyruğun içerisinde eleman kalıp kalmadığını kontrol etmek için kullanılmaktadır. Kodların devamında ise çizge için kullanılan fonksiyonlar bulunmaktadır. Örneğin, ilk başta çizgenin oluşturulması sırasında dugum_ekle ve yonsuz_kenarbaglantisi_ekle fonksiyonları kullanılmaktadır. Kodlarda enine arama algoritmasının çalışması sırasında kullanılmak üzere dugum_ goruntule ve ziyaretedilmeyen_komsuyu_getir fonksiyonları yer almaktadır. Enine arama algoritması, program kodu içerisinde enine_arama_algoritmasi fonksiyonu sayesinde gerçekleştirilmektedir. Bu fonksiyon, çalışmaya en baştaki düğümün ziyaret edilmesi ve kuyruk veri yapısı içerisine kuyruga_ekle fonksiyonu ile eklenmesiyle başlamaktadır. Daha sonra, while döngüsü içerisindeki kod bloğu çalışmakta ve kuyrukta eleman bulunduğu sürece, kuyruktan_cikar fonksiyonu vasıtasıyla üzerinde işlem yapılacak düğüm kuyruktan çıkarılarak belirlenmektedir. Üzerinde işlem yapılan düğümün tüm ziyaret edilmemiş komşuları ziyaretedilmeyen_komsuyu_getir fonksiyonu yardımıyla tespit edilmekte ve kuyruğa eklenerek “ziyaret edildi” olarak işaretlenmektedir. Bu düğümler aynı zamanda dugum_goruntule fonksiyonu yardımıyla ekrana yazdırılmaktadır. Kuyruk veri yapısı içerisindeki tüm düğümler çıkarıldığında, kuyruk_bos() fonksiyonunun yardımıyla while döngüsü sonlanır ve enine arama algoritmasının çalışması tamamlanır.

Bu bilgilerden de anlaşıldığı gibi, doğru cevap E’dir. Çizge üzerinde enine arama algoritmasının C program kodu ile ifade edilişine ilişkin olarak seçeneklerde yer alan ifadelerin tümü doğrudur.

Soru 17

Çizge üzerinde önce derinliğine arama algoritmasının C program kodu ile ifade edilişine ilişkin olarak yukarıdaki seçeneklerde yer alan ifadelerden hangileri doğrudur?

Çözüm Açıklaması

Önce derinliğine arama algoritmasının çalışma mantığının anlatıldığı Örnek 8.2’de (Sayfa 159, 160 ve 161), çizge ve yığın veri yapısı için kullanılan değişken ve fonksiyonlar bulunmaktadır. Öncelikle, yığın veri yapısı yigin isimli bir değişken kullanılarak gerçekleştirilmektedir. Şekil 8.6’da (Sayfa 157) görülen yığına ekleme, çıkarma işlemleri için yigina_ekle ve yigindan_cikar gibi fonksiyonlar bulunmaktadır. Bir diğer fonksiyon olan yigin_bos ise yığının içerisinde eleman kalıp kalmadığını kontrol etmek için kullanılmaktadır. Daha sonrasında ise çizge için kullanılan fonksiyonlar bulunmaktadır. Örneğin, ilk başta çizgenin oluşturulması sırasında dugum_ekle ve yonsuz_kenarbaglantisi_ekle fonksiyonları kullanılmaktadır. Önce derinliğine arama algoritmasının çalışması sırasında kullanılmak üzere dugum_goruntule ve ziyaretedilmeyen_komsuyu_getir fonksiyonları yer almaktadır. Önce derinliğine arama algoritması, program kodlarındaki once_derinligine_ arama_algoritmasi fonksiyonu sayesinde gerçekleştirilmektedir. Bu fonksiyon, çalışmaya en baştaki düğümün ziyaret edilmesi ve yığın veri yapısı içerisine yigina_ekle fonksiyonu ile eklenmesiyle başlamaktadır. Daha sonra, while döngüsü içerisindeki kod bloğu çalışmakta ve kuyrukta eleman bulunduğu sürece yigindan_cikar fonksiyonu vasıtasıyla üzerinde işlem yapılacak düğüm, yığından çıkarılarak belirlenmektedir. Öncelikle üzerinde işlem yapılan düğümden başlanarak, belli bir yönde gidilebilen en uzak derinliğe kadar olan tüm ziyaret edilmemiş komşular ziyaret edilmektedir. Ziyaret edilmiş bu düğümler aynı zamanda dugum_goruntule fonksiyonu yardımıyla ekrana yazdırılmaktadır. Program koduna göre, ziyaretedilmeyen_komsuyu_getir fonksiyonunun döndürdüğü değer -1 olmadığı sürece ziyaret edilmemiş komşular bulunmaktadır. Bu fonksiyon -1 değeri döndürdüğünde ise artık yığından eleman çıkararak üst düğümlere doğru geri dönülmekte ve bu kez onların komşuları arasında ziyaret edilmemiş düğüm olup olmadığı incelenmektedir. Yığın veri yapısı içerisindeki tüm düğümler çıkarıldığında yigin_bos() fonksiyonunun yardımıyla while döngüsü sonlanmakta ve önce derinliğine arama algoritmasının çalışması tamamlanmaktadır.

Bu bilgilerden de anlaşıldığı gibi, doğru cevap E’dir. Çizge üzerinde önce derinliğine arama algoritmasının C program kodu ile ifade edilişine ilişkin olarak seçeneklerde yer alan ifadelerin tümü doğrudur.

Soru 18

“Düğümlerle bu düğümleri birbirine bağlayan kenarlardan oluşan ve ağ görünümünde olan bir tür veri yapısıdır.”

Aşağıdakilerden hangisi yukarıdaki tanıma aittir?

Soru 19

Aşağıdakilerin hangisinde çizgelerin uygulamaları mevcut değildir?

Soru 20

“Kenar bağlantılarının yönleri temsil eden oklarla gösterildiği çizgedir.”

Aşağıdakilerden hangisi yukarıdaki tanıma aittir?

ALGORİTMALAR VE PROGRAMLAMA - Deneme Sınavı - 4