Veri Yapısı Makalesi (1)
1. Çoktan seçmeli sorular (soru başına 2 puan, toplamda 20 puan)
1. Yığınların ve kuyrukların ortak özellikleri ( ).
A. Yalnızca uç noktada eleman ekleme ve silinmesine izin verilir
B. Hepsi ilk girer, son çıkar
C. Her şey ilk girer, ilk çıkar
D. Ortak bir nokta yoktur
2. Bağlantılı şekilde saklanan kuyruk ekleme işlemi ( ) yapılırken eklenir .
A. Sadece baş göstergesi değiştirilmiştir B. Baş ve kuyruk işaretçileri değiştirilmelidir
C. Yalnızca kuyruk işaretçisi D. Baş ve kuyruk işaretçilerinin değiştirilmesi gerekebilir
3. Aşağıdaki veri yapılarından hangisi doğrusal olmayan yapıdır? ( )
A. Kuyruk B. Yığın C. Doğrusal tablo D. İkili ağaç
4. Eğer iki boyutlu bir dizi A[m][n] varsayarsak, A[0][0] 644 (10) ile A[2][2] 676 (10)'da depolanıyorsa, her eleman bir alan kaplayır, A[3][3][3][3](10) burada depolanır? Dipnot (10), bunun ondalık cinsinden ifade edildiğini belirtir.
A.688 B.678 C.692 D.696
5. Ağaçlar en iyi şekilde ( ).
A. Sıralanmış veri elemanları B. Sıralanmamış veri öğeleri
C. Elemanlar arasında dallanan hiyerarşik ilişkilere sahip veri D. Elemanlar arasında bağlantı olmayan veri
6. İkili ağacın k. katmanındaki maksimum düğüm sayısı ( ).
A.2k-1 B.2K+1 C.2K-1 D. 2k-1
7. Eğer tek boyutlu bir dizi A[19]'da saklanan 18 elemanlık sıralı bir tablo varsa, ilk eleman A[1]'e yerleştirilir ve şimdi ikili arama yapılır, o zaman karşılaştırma dizisinin A[3]'ü bulmak için alt indeksi ( ) olur
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. n kayıt dosyasını hızlıca sıralayın ve gereken yardımcı depolama alanı yaklaşık olarak aynıdır
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. Hash depolama için doğrusal tablolar (7, 34, 55, 25, 64, 46, 20, 10) için, eğer H(K)=K %9 hash fonksiyonu olarak seçilirse, ( ) öğe 1 hash adresine sahiptir.
A.1 B.2 C.3 D.4
10. 6 düğümlü yönlendirilmedik bir grafik ve graf bağlı bir graf sağlamak için en az ( ) kenarlara sahip olmalıdır.
A.5 B.6 C.7 D.8
2. Boşlukları doldurun (her boşluk başına 1 puan, toplamda 26 puan)
1. Algoritmanın kalitesi genellikle dört açıdan değerlendirilir: _________, _________, _________ ve _________.
2. Bir algoritmanın zaman karmaşıklığı (n3+n2log2n+14n)/n2'dir ve büyüklük mertebesi ________ olarak ifade edilir.
3. Bir ağacın genelleştirilmiş tablosunun A(C,D(E,F,G),H(I,J) olarak temsil edildiği varsayıldığında, ağaçtaki düğüm sayısı __________, ağacın derinliği ___________ ve ağacın derecesi _________.
4. 9 2 3 +- 10 2 / - ekinin değeri __________. Orta formüle (3+4X)-2Y/3 eki formülü _______________________________.
5. Bir ikili ağaç bağlı bir listeyle birlikte saklanıyorsa, her düğümün veri alanına ek olarak sol çocuk ve sağ çocuğa iki işaretçisi bulunur. Bu depolama yapısında, n düğümlü ikili ağacın toplamda ________ işaretçi alanı vardır; bunlardan ________ işaretçi alanı adresleri saklarken, ________________ işaretçi boş işaretçidir.
6. N köşeli ve E-bar kenarlı yönlendirilmiş graf ile yönlendirilmedik grafik için, karşılık gelen bitişik tabloda sırasıyla _______ ve ________ kenar düğümü bulunur.
7. AOV ağı ___________________ bir grafiktir.
8. N köşeli yönlendirilmedik tam grafikte ________ kenar bulunurken, n köşeli yönlendirilmiş tam grafikte ________ kenar vardır.
9. Doğrusal bir tablonun (12,23,74,55,63,40) olduğu varsayarsak, aynı kalan elemanlar Anahtar %4 koşuluna göre alt tablo olursa, elde edilen dört alt tablo ____________________________, ___________________, _______________________ ve __________________________'dir.
10. B_ ağacına eleman ekleme sürecinde, ağacın kök düğümü nihayet bölünürse, yeni ağacın yüksekliği orijinal ağacın yüksekliğinden ___________.
11. Heyp sıralama sürecinde, herhangi bir dal düğümünün elenmesinin zaman karmaşıklığı ________ ve tüm yığın sıralama sürecinin zaman karmaşıklığı ________.
12. Hızlı sıralama, yığın ve birleştirme sıralamasında _________ sıralama kararlıdır.
Veri Yapısı Makalesi (2)
1. Çoktan seçmeli sorular (24 puan)
1. Aşağıdaki doğrusal tablo tanımı yanlıştır ().
(A) Doğrusal tablolar sıralı olarak depolanır ve bitişik bir depolama alanı kaplamalıdır
(B) Doğrusal tablolar zincirlidir ve sürekli bir depolama alanı kaplamaz
(C) Lineer tablolar, ekleme ve silme işlemlerini kolaylaştırmak için zincirli depolama ile uygulanır
(d) Lineer tablolar, ekleme ve silme işlemlerini kolaylaştırmak için ardışık depolama ile uygulanır
2. Huffman ağacındaki toplam yaprak düğüm sayısı m olduğunu varsayalım ve depolama yapısı olarak ikili bağlantılı bir liste kullanılırsa, Huffman ağacında toplam ( ) boş işaretçi alanı vardır.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. Eğer ardışık döngü kuyruğu Q[0:M-1]'in baş ve kuyruk işaretçileri sırasıyla F ve R ise, baş göstericisi F her zaman baş elemanın önceki konumuna işaret eder ve kuyruk işaretçisi R her zaman kuyruk elemanının mevcut konumuna işaret ederse, döngü kuyruğundaki eleman sayısı ( ).
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. Eğer bir ikili ağacın orta dereceli geçiş dizisi ABCD ve önceki dizi geçiş dizisi CABD ise, ikili ağacı sonraki sırayla dolaşarak elde edilen dizi ().
(A) BADC (B) BCDA (C) CDAB (D) CBDA
5. Tamamen yönlendirilmemiş bir grafikte n köşe olduğunu varsayalalım, o zaman tamamen yönlendirilmemiş grafikte ( ) kenarlar vardır.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Diyelim ki bir ikili ağaçta 2000 düğüm var, o zaman ikili ağacın minimum yüksekliği ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Bir yönlendirilmiş grafikte n köşe varsayalım ki, o zaman yönlendirilmiş grafiğe karşılık gelen bitişik tabloda ( ) başlık düğümleri vardır.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Bir dizi başlangıç kayıt anahtar kelime dizisini (5, 2, 6, 3, 8) belirleyin ve ilk kayıt anahtar kelimesi 5'e dayalı hızlı sıralamanın sonucu ( ).
(A) 2,3,5,8,6 (B) 3,2,5,8,6
(C) 3,2,5,6,8 (D) 2,3,6,5,8
2. Boşlukları doldur (24 puan)
1. HASH arama teknolojisini etkili şekilde uygulamak için çözülmesi gereken iki sorun ____________________ ve __________________________.
2. Aşağıdaki program segmentinin fonksiyonu, x verisini yığına aktarır ve doğru ifadenin altını çizimde doldurmasını gerektirir.
typedefstruct {int s[100]; int top; } sqstack;
void push(sqstack&stack,int x)
{
if (stack.top==m-1) printf ("taşmak");
else {____________________; _________________; }
}
3. Orta sırada ikili sıralama ağacını geçerek elde edilen dizi, ___________ bir dizidir (sıralı veya sırasız olarak doldurulmuş).
4. Hızlı sıralamanın en kötü zaman karmaşıklığı ___________ ve ortalama zaman karmaşıklığı __________.
5. Eğer ikili ağaçta derecesi 0 olan düğümlerin sayısı N0 ve derecesi 1 olan düğüm sayısı N1 ise, ikili ağaçta derecesi 2 olan düğümlerin sayısı _________'tir; Eğer ikili bağlantılı bir liste ikili ağacın depolama yapısı olarak kullanılırsa, ikili ağaçta _______ boş işaretçi alanı vardır.
6. Belirli bir yönsüz grafikteki köşe ve kenar sayısının sırasıyla n ve e olduğunu ve tüm köşelerin derecelerinin toplamı d olduğunu, o zaman e = _______ olduğunu varsayalım.
7. Eğer ilk kayıt anahtar kelime dizisi (55, 63, 44, 38, 75, 80, 31, 56) ise, eleme yöntemiyle belirlenen ilk yığın ___________________________'dir.
8. Yönlendirilmiş bir grafın bitişik tablo depolama yapısının şu olduğu bilinmektedir: Vertex 1'den itibaren DFS geçişinin çıkış dizisi şöyledir:
, BFS dönüşümünün çıkış dizisi şöyledir:
Veri Yapısı Makalesi (3)
1. Çoktan seçmeli sorular (her soru 1 puan, toplamda 20 puan)
1. Bir veri yapısının ikili formu A=(D,R),D={01,02,03,04,05,06,07,08,09}, R={r},r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>} şeklinde ifade edilirse, veri yapısı A ( ).
(A) Doğrusal yapı (B) Ağaç yapısı (C) Fiziksel yapı (D) Grafiksel yapı
2. Aşağıdaki programın zaman kompleksi ()
for(i=1,s=0; i<=n; i++) {t=1;for(j=1;j<=i; j++) t=t*j; s=s+t; }
(A) O(n) (B) O(n2) (C) O(n3) (D) O(n4)
3. Tek bir bağlantılı listede işaret değişkeni p'yi düğüm A'ya işaret edecek şekilde ayarlayın; eğer tek bir bağlantılı listedeki düğüm A'yı silerseniz, işaretçinin işlem dizisini () olarak değiştirmelisiniz.
(A) q=p->next; p->data=q->data; p->next=q->next; free(q);
(B) q=p->next; q->data=p->data; p->next=q->next; free(q);
(C) q=p->next; p->next=q->next; free(q);
(D) q=p->next; p->data=q->data; free(q);
4. Sıralanacak n kayıt anahtar kelimesi varsa, ( ) yığın sıralamasında yardımcı kayıt birimleri gereklidir.
(A) 1 (B) n (C) nlog2n (D) n2
5. Eğer ilk anahtar kelime kaydı anahtar kelimeleri (20, 15, 14, 18, 21, 36, 40, 10) ise, kıyaslama olarak 20 ile kaydedilen hızlı sıralama sonrası sonuç ( ).
(A) 10,15,14,18,20,36,40,21
(B) 10,15,14,18,20,40,36,21
(C) 10,15,14,20,18,40,36,2l
(D) 15,10,14,18,20,36,40,21
6. İkili sıralama ağacında n düğüm varsa varsa, ikili sıralama ağacındaki ortalama arama uzunluğu ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Yönsüz grafik G'de n köşe e kenarı varsa varsayalım, o zaman ilgili bitişik tablodaki başlık düğümleri ve tablo düğümlerinin sayısı ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Güçlü bağlantı grafında n köşe varsayalım ki, güçlü bağlantı grafında en az ( ) kenar vardır.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. Sıralanması gereken 5000 kayıt anahtar kelimesi vardır; en küçük 10 kayıt anahtar kelimesini seçmek için en hızlı yöntemi kullanmanız gerekiyorsa, bu amacı gerçekleştirmek için aşağıdaki ( ) yöntemini kullanabilirsiniz.
(A) Hızlı sıralama (B) Yığın sıralaması (C) Birleştirme sıralaması (D) Sıralamayı ekle
10. Aşağıdaki dört tür ( ) en büyük mekânsal karmaşıklığa sahiptir.
(A) Ekleme sıralaması (B) Köpüklü sıralama (C) Yığın sıralaması (D) Birleştirme sıralaması
2. Boşlukları doldurun (her boşluk başına 1 puan, toplamda 20 puan)
1. Verilerin fiziksel yapısı esas olarak iki durumu içerir: _____________ ve ______________.
2. Tam bir ikili ağaçta 500 düğüm varsa, ikili ağacın derinliği __________'tir; Tam ikili ağacın depolama yapısı olarak ikili bağlı liste kullanırsanız, ___________ boş işaretçi alanı vardır.
3. Giriş dizisi 1, 2, 3 ise, yığının etkisinden sonra ___________ farklı çıkış dizisi elde edilebilir.
4. Eğer bitişik matris A[n][n] graf G için depolama yapısı olarak kullanılırsa, bitişik matrisindeki i satırındaki tüm elemanların toplamı, i köşesinin ________'ine eşittir ve i sütunundaki tüm elemanların toplamı i köşesinin ________'ine eşittir.
5. Huffman ağacında n düğüm varsa, Huffman ağacında 1 dereceye sahip ________ düğüm vardır.
6. Eğer yönsel graf G'de yön kenarları olan n köşe e varsa ve dereceye giren tüm köşelerin toplamı d ise, e ile d arasındaki ilişki _________'dir.
7. __________ ikili sıralama ağacındaki düğümleri dolaşırken, doldurulmuş, orta veya arka anahtar kelimelerin kademeli bir dizisi elde edilebilir.
8. Eğer arama tablosunda 100 eleman varsa, veri öğesi X'i bulmak için ikili arama yöntemini kullanırsanız, veri öğesi X'in arama tablosunda olup olmadığını belirlemek için ________ kez karşılaştırmanız gerekir.
9. İster ardışık depolama yapısına sahip bir yığın ister zincir depolama yapısına sahip bir yığın olsun, yığın içi ve dış yığın işlemlerinin zaman karmaşıklığı ____________.
10. N düğümden başlayarak yukarıdan aşağıya ve soldan sağa sıralanmış şekilde numaralandırılan tam bir ikili ağaç, i. düğümün ana düğümü ____________ numaralandırılır ve sağ çocuk düğümün numarası ___________ olur.
11. Kaydedilen anahtar kelimelerin başlangıç seti (72, 73, 71, 23, 94, 16, 5) ise, kayıt anahtar kelimesi 72'ye dayalı hızlı bir sıralamanın sonucu ___________________________'dir.
12. Eğer yönsel grafikte G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>} şeklinde bir yönlendirilmiş kenar kümesi varsa, grafiğin topolojik dizisi ____________________'dir.
13. Aşağıdaki algoritma, anahtar kelimeyi x değeriyle ardışık hash listesinde uygular, lütfen altçizgiye doğru ifadeyi doldurun.
struct record{int key; Diğerlerinde int edilir; };
inthashsqsearch(struct record hashtable[ ],int k)
{
inti,j; j=i=k % p;
while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; eğer (i==j) return(-1); }
eğer (_______________________ ) return(j); else return(-1);
}
14. Aşağıdaki algoritma, ikili sıralama ağacında anahtar değer k'yi uygular, lütfen alt çizgiye doğru ifadeyi doldurun.
typedefstruct node{int key; struct düğümü *lchild; struct düğümü *rchild; }bitree;
bitree *bstsearch(bitree *t, int k)
{
eğer (t==0) return(0); else (t!=0)
if (t->key==k)_____________; else if (t->anahtar>k) t=t->lchild; else_____________;
}
Veri yapısı test kağıdı (1) Cevaba bakın
1. Çoktan seçmeli sorular (soru başına 2 puan, toplamda 20 puan)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Boşlukları doldurun (her boşluk başına 1 puan, toplamda 26 puan)
1. Doğruluk, okunabilirlik, dayanıklılık ve yüksek verimlilik
2.O(n)
3.9 3 3
4.-1 3 4 X * + 2 Y * 3 / -
5.2n n-1 n+1
6.e 2e
7. Yönlü ve devre dışı
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. 1 ekle
11.O(log2n) O(nlog2n)
12. Konsolidasyon
Diğer test sorularının cevapları şu şekilde görülebilir:
Turistler, bu gönderinin gizli içeriğini görmek isterseniz lütfen Yanıt
|
Yayınlandı 25.11.2014 12:46:30
|
|
|
Yayınlandı 30.12.2014 00:10:55
|
