VAR 

   a:byte; 

   b:integer; 

BEGIN 

   a:=100; 

   b:=-100; 

END.

1. **+ab+cd

2. *abc*+defa^^+*

3. *((((a*x)+b)*x)+c)/x

1. *abc*+def*+*

2. *ab+*cd-

3. *^/ab/cd

1. Elemen a[7,8], dari vektor a yang dideklarasikan secara column-major order oleh: VAR a : ARRAY[1..20 , 1..10) OF word;
2. Elemen b[-10,1], dari vektor b yang dideklarasikan secara row-major order oleh: VAR b : ARRAY[-13..1 , -5..4) OF single;

• 1 bit sign, 0 untuk positif dan 1 untuk negatif
• 11 bit exponen (radix), yang dibias dengan +3FF
• 52 bit mantissa
• Dua nibble terakhir dibaca terlebih dahulu sebelum nibble pertama. Demikian pula untuk setiap pasangan word (seperti single precision), yaitu word terakhir dibaca dahulu; kemudian untuk setiap pasangan byte, byte terakhir juga dibaca terlebih dahulu. Catatan: 1 Nibble = 2 Word. 

Berapa nilai double precision (dalam desimal) yang ditunjukkan oleh urutan byte berikut:

(00 00 00 00 00 DB A0 0C)₁₆

Sebagai contoh, jika str='123&*O#O*&321' atau str='ST#TS', hasilnya akan true, sebaliknya jika str='a2qd#dq3a', hasilnya akan false.

1. Apakah kondisi yang menyebabkan Stack 1 kosong (empty)? Kapan pula Stack 2 kosong?
2. Apakah kondisi yang menyebabkan Stack 1 penuh (full)? Kapan pula Stack 2 penuh?
3. Untuk DualStack yang dideklarasikan dengan:

CONST

   MaxDualStackSize = 100;

TYPE

   StackNo = 1..2;

   InfoType = byte; {user defined data type}

   DualStack = RECORD

                 top1, top2 : word;

                 StackStorage : ARRAY[1..MaxDualStackSize]

                             OF InfoType;

               END;

 

Tulislah 3 (tiga) rutin di bawah ini:

Procedure Initialize(VAR StackName: DualStack);

{untuk inisialisasi DualStack bernama StackName}

 

Procedure Push(VAR StackName: DualStack; No: StackNo; Data: InfoType);

{untuk push Data ke dalam DualStack bernama StackName, nomor No}

 

Function Pop(VAR StackName: DualStack; No: StackNo) : InfoType;

{untuk pop/mendapatkan data dari DualStack bernama StackName, nomor No}

4. Tulis sebuah program untuk membaca 25 bilangan bulat positif (byte), dan memasukkan seluruh elemen ini ke dalam DualStack, semua yang gasal ke dalam stack 1, dan yang genap ke dalam stack 2, dengan memanfaatkan ketiga subprogram yang telah dibuat pada soal (d).

Dalam Turbo Basic single precision menggunakan ukuran 4 byte (1 sign bit; 8 exponent bit; 23 mantissa bit), dengan exponen bias 7F (hexadecimal). Tentukan urutan 4 byte hexadecimal dalam memory komputer yang menyajikan single precision -97,75.

Konversikan ekspresi infix berikut menjadi dua notasi lainnya (prefix dan sufix/postfix): 

1. ((A+B)*C-(D-E))^(F+G)

2. A*B+(C/(D-E))^(F-G)

TYPE 

   a = RECORD 

          b:boolean; 

          c:char; 

          d:string[5]; 

          e:word; 

       END;

VAR 

   f : ARRAY[1..2, -3..4, -5..6, 78..90, 11..12]

       OF a;

Jika data array tersebut diletakkan pada alamat memori awal L0 = 1500 (desimal), tentukanlah alamat awal field berikut (dalam desimal):

1. d[0,7].Tunjangan, bila digunakan Row-Major Order.

2. d[0,9].Golongan, bila digunakan Column-Major Order.

Tulis procedure Balik_Queue(Q:Queue); yang berguna untuk membalik susunan elemen dalam queue Q dengan menggunakan bantuan sebuah stack S. Diasumsikan procedure dan function untuk operasi berikut sudah disediakan (tinggal dipakai saja), yaitu: 

• Procedure InsertQueue(data,queue);

• Procedure DeleteQueue(data,queue);
• Function EmptyQueue(queue): boolean;
• Procedure InitStack(stack);
• Procedure Push(data, stack);
• Function Pop(stack);
• Function EmptyStack(stack): boolean;

Tulis Procedure DeleteNode(Head:PtrList; X:Infotype; Terhapus: boolean); yang berfungsi untuk menghapus semua node yang berisi info X dalam Circulair Single Linked Linear List yang dialamati oleh variabel Head. Variabel Terhapus akan true jika dan hanya jika list asal tidak empty dan minimal terdapat sebuah X dalam list asal.

Tulislah algoritma atau program Pascal yang recursive untuk:

1. Mencetak dalam urutan terbalik semua info / data dari sebuah single linked linear list.

2. Mengubah info dari semua node pada sebuah binary tree integer dengan ketentuan berikut:

Jika info dari sebuah node berisi bilangan genap, maka info ini tidak berubah. Jika info dari sebuah node berisi bilangan gasal, info dikalikan dua.

Tulislah function Evaluasi_Polinomial(P:Polinomial; X:real) : real; yang berguna untuk mendapatkan nilai sebuah polinomial P dengan harga X yang ditentukan. Sebagai contoh untuk P yang menyajikan polinomial 5x^4-2x^3+10x-100 dan X=2, fungsi ini akan menghasilkan nilai 5*2^4-2*2^3+10*2-100 = 5*16-2*8+10*2-100 = -16. Tulis lebih dahulu deklarasi type linked list untuk menyajikan polinomial.

Inorder successor biasa digunakan pada procedure untuk penghapusan sebuah node dari sebuah binary search tree. Kali ini perhatikanlah bahwa penghapusan sebuah node dari sebuah binary tree dapat dilakukan dengan memperhatikan (mendapatkan terlebih dahulu) inorder predecessor-nya.

1. Tulislah fungsi untuk mendapatkan inorder predecessor dari sebuah node dalam sebuah binary search tree.

Bantuan: Input dan Output fungsi ini masing-masing adalah sebuah pointer type Binary Search Tree yang digunakan; sedangkan parameter input adalah pointer ke node n, dimana n^.right menunjuk node yang akan dicari inorder predecessor-nya.

2. Jelaskan semua kasus yang mungkin terjadi pada procedure penghapusan ini. Jika diperlukan sertakan gambar untuk mempertajam penjelasan anda.

3. Tulis sebuah procedure recursive melalui algoritma atau program Pascal untuk menghapus sebuah node dari sebuah binary tree dengan menggunakan fungsi pada soal (a) dan memperhatikan semua kasus pada soal (b).

Gambarkan:

1. Binary Search Tree yang dihasilkan dari urutan pengisian data berikut: 20, 16, 30, 60, 80, 40, 10, 25, 27, 15, 13, 14, 12, 48, 35, 38

2. Tuliskan penyajian jawaban (a) dengan menggunakan diagram venn.

3. Kumpulan poket yang dihasilkan dan kemudian list baru hasil penggabungan poket pada iterasi pertama saja dari pengurutan data berikut dengan menggunakan radix sort: 90, 100, 109, 1, 105, 5, 50, 2, 20, 21, 12, 9, 99, 9, 95

4. Sparse matriks untuk:

5. General Tree yang disajikan dengan nested parentheses berikut ini: 

   ( 20 ( 30 (70 80 (77 88 (88) 99 77 ) ) 40 (95) 50 11 33) )

6. Penyajian general tree pada soal (e) dengan menggunakan binary tree.

Binary Increment. Perhatikanlah deklarasi sebuah singly linked linear list berikut ini:

TYPE

   PtrBiner = ^Biner

   biner = RECORD

      bit : 0..1;

      link : PtrBiner;

   END;

Seluruh node linked list menyajikan sebuah bilangan biner b1b2.....bn, dimana bi hanya mungkin berisi 0 atau 1. Jika singly linked linear list bertipe PtrBiner -- yang field 'bit' di dalamnya merupakan rangkaian b1b2.....bn -- digunakan untuk menyajikan sebuah bilangan biner, tulislah sebuah Procedure Increment(VAR BilBiner : PtrBiner); yang berguna untuk menambah satu bilangan biner yang alamatnya ditunjukkan dengan BilBiner. Catatan: Recursive akan sangat membantu.

Shuffle-merge dari dua buah list X₁, X₂, ..... X_n dan Y₁, Y₂, ..... Y_m adalah:

X = X₁, Y₁, X₂, Y₂, ..... X_n, Y_n, Y_n+1, Y_n+2, ..... Y_m ; jika n<m

atau

X = X₁, Y₁, X₂, Y₂, ..... X_m, Y_m, Y_m+1, Y_m+2, ..... Y_m ; jika n>m

Tulislah Procedure ShuffleMerge(VAR X : ListType; Y : ListType); untuk melakukan shuffle merge dua buah list yang head nodenya ditunjukkan oleh X dan Y. Namun demikian perhatikan bahwa hasil penggabungan disimpan ke dalam list X. Tidak menjadi masalah apabila isi list Y akan rusak / kosong. Dalam hal ini penggabungan dilakukan dengan menyisipkan elemen-elemen Y1, Y2, ...... ke tempat yang sesuai (antara X1 dan X2, antara X2 dan X3, dan seterusnya), tanpa mengalokasikan sebuah elemenpun dengan perintah New (termasuk tidak diijinkan menggunakan procedure InsertFirstList atau InsertLastList).

637250569987999999786549876342589776543981234567 (Bil1)
              9012348756589129876543212345678999 (Bil2)
------------------------------------------------ +
637250569988009012135306465462466319756326913566 (Hasil)
    

Dengan memanfaatkan sejumlah operasi queue tulis program Pascal untuk memeriksa sebaris karakter yang dimasukkan melalui keyboard. Data input diasumsikan terdiri dari 2 bagian yang dipisahkan oleh sebuah colon (:). Sebagai output, algoritma ini akan mencetak keterangan:

• 'NO COLON' jika tak ada colon pada data input

• 'LEFT' jika bagian kiri (sebelum colon) lebih panjang daripada bagian kanan

• 'RIGHT' jika bagian kiri (sebelum colon) lebih pendek daripada bagian kanan

• 'SAME' jika bagian kiri dan kanan sama panjangnya

Catatan:

• Sama atau tidaknya isi bagian kiri dan isi bagian kanan tidak perlu diperiksa.

• Operasi-operasi dasar queue dianggap telah disediakan, namun demikian tulislah kembali header function/procedure-nya.

Contoh:

Pools untuk Garbage Memory Management. Bila sebuah vektor yang menyajikan singly linked linear list L telah berisi data-data berikut:

First=5, Pools=0, MaxSize=6

Tulislah:

1. PROCEDURE insert(X,Pred,L,Ok,): untuk menyisipkan X setelah data pada alamat fisik Pred dari list L, Ok=TRUE jika operasi berhasil dilakukan.

2. PROCEDURE delete(Pred,L,Ok): untuk menghapus data dari list L yang alamatnya ditunjukkan oleh Pred, Ok=TRUE jika operasi berhasil dilakukan.

Gambarlah penyajian list dalam bentuk diagram:

1. untuk tabel di atas.

2. keadaan tabel di atas, setelah urutan proses: delete(5,L,Ok); delete(2,L,Ok); insert('Titus',1,L,Ok); delete(4,L,Ok); jika metode yang dipakai adalah pembentukan pools segera setelah sebuah elemen dihapus.

TYPE

   ListPointer = ^ListNode;

   ListNode = RECORD

      link : ListPointer;

      CASE tag : BOOLEAN OF

          FALSE : (data : CHAR);

          TRUE : (dlink: ListPointer);

      END;

Perhatikan bahwa deklarasi di atas memungkinkan untuk menyajikan sebuah generalized list. Kemudian perhatikanlah function berikut ini:

FUNCTION mystery(p : ListPointer) : ListPointer;

VAR

   q : ListPointer;

BEGIN

   q := NIL;

   IF p <> NIL THEN

   BEGIN

      new(q);

      q^.tag := p^.tag;

      IF NOT p^.tag 

         THEN q^.data := p^.data

         ELSE q^.dlink := mystery(p^.dlink);

      q^.link := mystery(p^.link);

   END;

   mystery := q;

END; {of mystery}

Apakah tujuan function mystery di atas? Jelaskan dengan singkat.

1. Gambarlah terlebih dahulu General Tree yang menyajikan silsilah keluarga di atas.

2. Gambarlah Binary Tree yang menyajikan general tree di atas.

3. Tunjukkan urutan node yang dikunjungi, jika pada Binary Tree tersebut dilakukan traversal secara: Inorder, Preorder dan Postorder.

1. Gambarlah general tree yang menyajikan ekspresi aritmatika berikut: (a + b + c)*e - f(g,h,i,j) + k / log(m) ^ n

2. Gambarlah tiga buah linked list, yang masing-masing adalah keadaan ketika pass ke-1, ke-2, dan ke-3 berakhir untuk pengurutan data berikut dengan Radix Sort: 909, 78, 89, 79, 9, 7, 97, 87, 777, 77, 99, 98, 798, 897, 888. Anda tidak perlu memperhatikan ataupun menggambar susunan pocketnya.

3. Gambarlah Binary Search Tree yang dibentuk dengan mengisikan bilangan berikut secara urut: 50, 46, 43, 80, 90, 75, 49, 48, 77, 76

4. Sajikan tree pada soal (c) dengan Nested Parentheses (Kurung Bersarang).

5. Sajikan tree pada soal (c) dengan Diagram Venn.

Breadth First Search (BFS) adalah salah satu traversal pada Binary Tree, yang dilakukan dengan melakukan penelusuran tree mulai dari level 1 (root) sampai ke level terbawah, dimana dalam setiap level melakukan penelusuran mulai dari node kiri ke node kanan. Kunci: penyelesaian BFS adalah penggunaan struktur data Queue.

Bila rutin operasi queue berikut sudah disediakan (tinggal dipakai saja), yaitu:

Tulislah procedure BFS(BTree); yang berguna untuk melakukan kunjungan -- dan sekaligus mencetak isi informasi setiap node yang dikunjungi ke layar komputer -- terhadap seluruh node dalam binary tree BTree secara BFS.

28, 45, 87, 20, 14, 40, 46, 91, 22, 29

Gambarlah diagram pohon setelah pengisian data di atas selesai dilakukan. Perhatikan bahwa jika biasanya digunakan lingkaran kecil untuk menunjukkan sebuah node, untuk jawaban soal ini, gantikan dengan bentuk kotak kecil, yang field-fieldnya terbagi seperti gambar ini:

LFlag dan RFlag adalah boolean, yang jika TRUE=Thread Link dan jika FALSE=Structural Link. Pada gambar anda, seluruh garis dengan mata panah keluar dari LPtr dan RPtr; sedangkan LFlag, Info, dan RFlag harus diganti dengan nilai-nilai boolean (T/F) dan numerik, sesuai dengan data yang diisikan.

Gambarlah diagram pohon sebelum penghapusan dilakukan (Hati-hati. Jika salah, semua jawaban untuk soal berikut juga akan salah). Jika penghapusan dilakukan untuk node yang berisi 22, hitunglah:

1. Berapa kali pemanggilan Procedure Delete (recursive) dilakukan? Hati-hati dalam menjawabnya, hitung baik-baik, dan pemanggilan procedure dari program / algoritma utama tidak dihitung.
2. Berapa kali segmen program/algoritma pencarian successive inorder dari suatu node dilakukan? Dan node mana (sebutkan isi infonya) saja yang mencari successive inordernya?
3. Berapa kali penggantian isi field info dilakukan? Sebutkan pasangan-pasangan info dari node yang diganti dan node penggantinya.

TYPE

   DataType = Word;

   Tree = ^Node;

   Node = RECORD

            Info : DataType;

            Left, Right : Tree;

          END;

Tulislah program Pascal atau sub algoritma fungsi untuk:

1. Memeriksa apakah pointer Ptr menunjuk kepada suatu node leaf. (Jika Leaf=True). FUNCTION IsLeaf(Ptr: Tree): Boolean;
2. Menghitung nilai total jumlah field Info dari semua node pada sebuah binary tree Root. FUNCTION Sum(Root: Tree): LongInt;
3. Memeriksa apakah binary tree Root adalah complete binary tree. (Jika Complete=True). FUNCTION IsComplete(Root: Tree): Boolean;

FUNCTION DeleteAllLeaf(VAR Root : Tree);