Google        youtube          psv       สพม.11

บทที่ 1 พื้นฐานโครงสร้างข้อมูล

ตอนที่ 1

1.อธิบายกระบวนการพัฒนาซอฟแวร์ประกอบด้วยขั้นตอนอะไรบ้าง

ตอบ         1. การแยกแยะและวิเคราะห์ปัญหา ขั้นแรกเป็นการแก้ไขปัญหาโดยการวิเคราะห์และแยกแยะ สิ่งแรกที่พิจารณา คือ Output หลังจากพิจารณา Output แล้วต่อมาก็ต้องพิจาณา Input

2.การอกแบบระบบ เนื่องจากระบบคอมพิวเตอร์ไม่สามารถที่จะเข้าใจแก้ไขปัญหาบางอย่างได้จึงต้องมีวิธีที่จะแก้ไขปัญหาโดยออกแบบระบบ

2.ในการเชื่อมต่อโปรแกรมต้องมีลักษณะโครงสร้างที่ดีซึ่งต้องมีการพิจารณาจากเรื่องใดบ้าง

ตอบ         1. การเขียนโปรแกรมควรเป็นแบบบนลงล่าง

2.ใช้โครงสร้างควบคุมการทำงาน

3. ควรใช้ตัวแปรที่เป็นแบบโลคอล

4. ควรใช้ตัวแปรที่เป็นพารามิเตอร์

5. ตัวแปรคงที่

6. ควรมีการจัดพื้นที่หรือบรรทัดว่าง เพื่ออ่านได้สะดวก

 3.อธิบายความหมายของโครงสร้างข้อมูลเป็นอย่างไร

ตอบ  การกำหนดรูปแบบที่ใช้สื่อความหมายของข้อมูลข่าวสารให้คอมพิวเตอร์กับผู้ใช้งานเข้าใจตรงกัน

 4.อธิบายลักษณะการเก็บข้อมูลที่เป็นเลขจำนวนเต็มในระบบคอมพิวเตอร์เป็นอย่างไร

ตอบ  เป็นการนำบิตหลาย ๆ บิตมาเรียงกันเพื่อกำหนดเป็นเลขจำนวนเต็ม ซึ่งได้เป็นระบบเลขฐานสอง โดยแต่ละบิตมีความหมายเป็นเลขยกกำลังสอง

5. หาค่าเลขจำนวนเต็มจากรูปแบบของบิตสตริงจำนวน 16 บิตในแต่ละข้อต่อไปนี้โดยบิตซ้ายสุดเป็นบิตสัญลักษณ์กำหนดค่าบวกหรือลบ

ตอบ(a)0100000001000000 = 16448

(b) 0110111001101111 = 28270

(c)1011111111111110 = -16382

(d) 1100000000000001 = -16384

(e)1001100110011001 = -16384

(f)1010101010101010 = -10922

6.จากข้อ 5(a) และ (b) จงแปลงบิตสตริงเป็นตัวอักษร โดยกำหนดให้ 8 บิตเป็นตัวหนึ่งอักษรในรหัสเอสกี

ตอบ         (a)0100000001000000 = dd

(b) 0110111001101111 = w6

7.จงหาค่าเลขฐานสองจำนวน 16 บิตจากเลขจำนวนจริงในแต่ละข้อต่อไปนี้ โดย 11 บิต ทางซ้ายเป็นเมนทิสสาและ 5 บิต ทางขวาเป็นเอ็กโพเนนท์

ตอบ(a)0.625

 8.อธิบายโครงสร้างข้อมูลเรียบง่ายคืออะไร และมีประเภทอะไรบ้าง

ตอบ  คือ จะมีสมาชิกที่เป็นโครงสร้างข้อมูลอื่นเป็นส่วนประกอบ มีรูปแบบง่ายๆ ไม่ซับซ้อน

9.อธิบายโครงสร้างข้อมูลเชิงเส้นกับโครงสร้างข้อมูลไม่เป็นเชิงเส้นมีความแตกต่างกันอย่างไร

ตอบโครงสร้างข้อมูลเชิงเส้น ประกอบด้วยสมาชิกที่เป็นโครงสร้างข้อมูลอื่นจัดเรียงต่อกันเป็นแนวเชิงเส้น

โครงสร้างข้อมูลไม่เป็นเชิงเส้น ประกอบด้วยสมาชิกที่เป็นโครงสร้างข้อมูลอื่นจัดเรียงกันในรูปแบบไบนารี่

10. อธิบายโครงสร้างข้อมูลซับซ้อนคืออะไร และมีประเภทใดบ้าง

ตอบ  คือจะมีสมาชิกที่เป็นส่วนประกอบ มีรูปแบบซับซ้อนกัน ได้แก่เชิงเส้นและไม่เชิงเส้น <สแตก, คิว, ลิ้งลิสต์ และ ไบนารี่, Nอาร์เรย์>

11. รวบรวมโครงสร้างข้อมูลชนิดต่างๆ ที่มีให้มาใช้งานในภาษาซี และมีรูปแบบการใช้งานอย่างไร

ตอบ1. โครงสร้างข้อมูลเบื้องต้น เป็นชนิดข้อมูลที่ไม่มีโครงสร้างข้อมูลอื่นมาเป็นส่วนประกอบ

2. โครงสร้างข้อมูลเรียบง่าย มีรูปแบบง่ายๆไม่ซับซ้อน

3. โครงสร้างข้อมูลเชิงเส้น เป็นโครงสร้างที่มีความซับซ้อนมากขึ้น

4. โครงสร้างข้อมูลไม่เป็นเชิงเส้น เป็นโครงสร้างที่มีความซับซ้อนเช่นกัน

5. โครงสร้างการจัดการแฟ้มข้อมูล เป็นโครงสร้างสำหรับนำข้อมูลเก็บไว้ในหน่วยความจำสำรอง

ตอนที่ 2

1.System Design

ตอบ  การออกแบบระบบ

2.Data Structure

ตอบ  โครงสร้างข้อมูล ใช้ควบคุมและจัดการกับข้อมูลของปัญหานั้นๆ

3.Amount of work done

ตอบ  ระยะเวลาการทำงาน

4.Control Structure

ตอบ  เป็นโครงสร้างที่ใช้ควบคุมการทำงาน

5.Binary Number System

ตอบ  ระบบเลขฐานสอง

6.Floating-point Number

ตอบ  เป็นรูปแบบตัวเลขที่มีเลขทศนิยม

7.Primitive Data Structure

ตอบ  โครงสร้างข้อมูลเบื้องต้น เป็นชนิดที่ไม่มีโครงสร้างข้อมูลอื่นมาเป็นส่วนประกอบ

8.Build-in Type

ตอบ  สร้างมาให้ใช้ด้วยภาษานั้นๆ


9.User-defind Type

ตอบ  ชนิดข้อมูลผู้ใช้กำหนด

 10. Abstract Data Structure

ตอบ  โครงสร้างข้อมูลนามธรรม

 

บทที่ 2โครงสร้างข้อมูลอาร์เรย์

ตอนที่ 1

1.อธิบายลักษณะของอาร์เรย์หนึ่งมิติเป็นอย่างไร และมีการใช้งานอย่างไร

ตอบ  เป็นตารางที่มีเพียงแถวเดียว การใช้งานจะใช้อ้างไปยังตำแหน่งของแต่ละสมาชิกในอาร์เรย์ซึ่งมีค่าเป็นลำดับ

2.อธิบายลักษณะของอาร์เรย์สองมิติเป็นอย่างไร และมีการใช้งานอย่างไร

ตอบ  เป็นตารางที่มีทั้งแถวและคอลัมน์ การใช้งาน นิยมใช้กับการวนลูปที่ซ้อนกัน 2 ลูป

3.อธิบายเหตุใดจึงต้องมีการกำหนดให้อาร์เรย์สามารถมีได้หลายมิติ

ตอบ  เพราะมีการสร้างอาร์เรย์อาจเป็น 3 มิติ 4 มิติ หรือมากกว่านั้นเรียกว่า อาร์เรย์หลายมิติหรือ N- มิติ ดัชนีและช่วงจำนวนสมาชิกก็จะเพิ่มมากขึ้นตามจำนวนมิติอาร์เรย์

4.ยกตัวอย่างลักษณะการใช้อาร์เรย์ในภาษาซีและภาษาปาสคาลเป็นอย่างไร

ตอบ  

 

 

 

 

 

5.ถ้าต้องการเก็บข้อมูลในแต่ละข้อต่อไปนี้โดยใช้เป็นอาร์เรย์จะต้องกำหนดการประกาศขึ้นมาใช้งานในภาษาซีอย่างไร

(a) เกรดที่ได้ของ นศ. จำนวน  50 คน

ตอบ

 

(b) เกรดที่ได้ในแต่ละวิชาเรียนจำนวน 6 วิชา ของ นศ. จำนวน 30 คน

ตอบ

 

(c) ยอดขายของสินค้า 10 ชนิด ของแต่ละเดือนใน 1 ปี

ตอบ

 

(d) จำนวนเงินซื้อสินค้าของลูกค้าจำนวน 5 คน จากแต่ละสินค้า 10 ชนิด ในแต่ละเดือน

ตอบ

 

 6.อธิบายการจัดเก็บอาร์เรย์ในหน่วยความจำแบบลำดับแถวสำคัญมีลักษณะอย่างไร

ตอบ เก็บสมาชิกทุกตัวของแถวแรกก่อนจากนั้นเก็บแถวที่สองและสามไปเรื่อยๆ

7.สมมุติให้ชนิดข้อมูล Integer มีขนาด 2 ไบต์ ชนิดข้อมูล Char มีขนาด 1 ไบต์ และชนิข้อมูล Real ขนาด 4 ไบต์ จงบอกขนดพื้นที่หน่วยความจำของอาร์เรย์ในแต่ละข้อต่อไปนี้มีจำนวนกี่ไบต์

(a) Array[1:10] of Real

ตอบ 40 ไบต์

(b) Array[-5:5] of char

ตอบ 5 ไบต์

(c) Array [0:4,0:6] of Integer

ตอบ 32,128 ไบต์

(d) Array [0:3,1:2,0:6] of Integer

ตอบ 164,128 ไบต์

 

8.ถ้ากำหนดอาร์เรย์ A[0:5,1:8] โดยมีตำแหน่ง Address เริ่มต้นที่ 2000 และแต่ละสมาชิกเป็น 6 ไบต์

(a) จงหาตำแหน่งแอดเดรสของสมาชิก A[3,5] เมื่อเก็บแบบลำดับแถวสำคัญและแบบลำดับคอลัมน์สำคัญ

ตอบ  สูตร B+(I-L1)*(U2-1+1)*s+(J-1)*s

2000+(3-1)*(8-1+1)*6+(5-1)*6

2000+2*8*6+4*6

2000+186+4

2576

สูตร B+(J-1)*(U1-L1+1)*s+(I-L1)*s

2000+(5-1)*(5-1+1)*6+(3-1)*6

2000+4*5*6+2*6

2000+720+2

2156

(b)  จงหาตำแหน่งแอดเดรสของสมาชิก A[6,2] เมื่อเก็บแบบลำดับแถวสำคัญ

ตอบ  สูตร B+(I-L1)*(U2-1+1)*s+(J-1)*s

2000+(6-1)*(8-1+1)*6+(2-1)*6

2000+5*8*6+1*6

2000+240+6

2246

(c)จงหาตำแหน่งแอดเดรสของสมาชิก A[2,6] เมื่อเก็บแบบลำดับคอลัมน์สำคัญ

ตอบ  สูตร B+(J-1)*(U1-L1+1)*s+(I-L1)*s

2000+(6-1)*(6-1+1)*6+(2-1)*6

2000+5*6*6+1*6

2000+180+6

2186


 

9.จากตัวอย่างโปรแกรมต่อไปนี้มีการแสดงผลข้อมูลในแบบลำดับแถวสำคัญ

 for(i=0;i<5;i++){

 for(j=0;j<8;j++)

printf(“\n”);

}

ถ้าต้องการเปลี่ยนเป็นการแสดงผลข้อมูลในแบบลำดับคอลัมน์สำคัญจะต้องเขียนโปรแกรมเป็นอย่างไร

ตอบ

 

 

 

10. เขียนโปรแกรมเพื่อเก็บค่าการแปลงอุณภูมิจากองศาเซลเซียสไปเป็นองศาฟาเรนไฮต์โดยใช้อาร์เรย์เก็บค่าที่ได้และมีสมาการแปลงค่าดังนี้

Celsius=5.0/9.0 (fahrenhiet-32)

หลังจากคำนวรหาค่าเสร็จให้แสดงผลในรูปแบบตารางเปรียบเทียบค่าระหว่างเซลเซียสและฟาเรนไฮต์ดังต่อไปนี้

ตอบ  ต้องกลับสูตรก่อน

Celsius*9/5 +32= Fahrenheit

 

 


 

11. บ. แห่งหนึ่งมีการจ่ายค่าคอมมิชชั่นให้กับพนักงานชายโดยพนักงานแต่ละได้รับเงินเดือน 3,500 บาท รวมกับ 9% ของยอดขาย เช่น พนักงานคนหนึ่งมียอดขาย =30,000 บาท จะได้รับเงิน 3,500 + 9 % ของ 30,000 หรือ 6,200 บาท จงเขียนโปรแกรมเพื่อคำนวณหาว่ามีพนักงานขายกี่คนที่ได้รับเงินเดือนในแต่ละช่วงที่กำหนดไว้ดังนี้

1) 3500 – 44995) 7500 – 8499

2) 4500 – 54996) 8500 – 9499

3) 5500 – 64997) 9500 และมากกว่า

4) 6500 – 7499

ตอบ 

 

 

 

 

 

 

ตอนที่ 2

1.Array

ตอบ  อาร์เรย์ โครงสร้างข้อมูลอาร์เรย์

2.Random Access

ตอบ  การใช้งานอาร์เรย์เป็นการเข้าถึงแบบสุ่ม

3.Upper Bound

ตอบ  ค่าที่น้อยสุดและขอบเขตบน

4.Vector

ตอบ  ตารางที่มีเพียงแถวเดียว

5.Matrix

ตอบ  เป็นชื่อของอาร์เรย์ 2 มิติ

6.Two-dimension Away

ตอบ  อาร์เรย์ 2 มิติ

7.Multi- dimension Away

ตอบ  อาร์เรย์หลายมิติ

8.Base Location

ตอบ  ตำแหน่งเริ่มต้น

9.Row – major Order

ตอบลำดับแถวสำคัญ

10. Programming language

ตอบ  ภาษาเขียนโปรแกรม

 

 

บทที่ 3 โครงสร้างข้อมูลสตริงและเรคคอร์ด

ตอนที่ 1

1.โครงสร้างข้อมูลสตริงมีชุดปฏิบัติการพื้นฐานอะไรบ้าง และมีขั้นตอนการทำงานอย่างไร

ตอบ  – ความยาวสตริง เป็นการบอกให้ทราบว่าสตริงตัวนั้นมีตัวอักษรหรือความยาวเท่าไหร่ จะกำหนดเป็นฟังก์ชัน Length

– รวมสตริง เป็นการนำ 2 สตริงมารวมกันเป็นสตริงเดียว โดยนำตัวอักษรทั้งหมดของสตริงตัวหลังไปต่อท้ายสตริงตัวแรก

– สตริงย่อย เป็นการคัดลอกตัวอักษรที่อยู่ติดกันบางส่วนของสตริงตัวที่สอง ให้กับสตริงตัวแรกขั้นตอนการทำงาน จะรับค่าเป็นข้อความเข้ามาทางคีย์บอร์ดและนำออกแสดงผลในรูปแบบต่างๆ

2.จงสร้างชุดปฏิบัติการเพื่อแปลงตัวอักษรทุกตัวให้เป็นอักษรตัวเล็กยกเว้นตัวอักษรตัวแรกให้เป็นตัวอักษรตัวใหญ่

ตอบ 

 

 

 

 

 

3.จงสร้างชุดปฏิบัติการเพื่อเปรียบเทียบสองข้อความว่ามีตัวอักษรและลำดับเหมือนกันหรือไม่ ถ้าเหมือนกันให้ส่งค่ากลับมาเป็น 1 ถ้าไม่เป็นให้ส่งกลับเป็น 0

ตอบ 

 

 

4.จงรวบรวมชุดปฏิบัติการทั้งหมดในภาษาซีที่ใช้จัดเก็บโครงสร้างข้อมูลสตริง

ตอบ  1. อาร์เรย์ มีโครงสร้างข้อมูล char

2. การค้นหาตัวอักษรบางส่วนในสตริง

3. การแทรกตัวอักษรบางส่วนในสตริง

4. การลบข้อความบางส่วนออกจากสตริง

5.การเก็บข้อมูลโดยใช้โครงสร้างข้อมูลสตริงจะมีลักษณะรูปแบบและความหมายที่แตกต่างกัน เช่น ชื่อ  นามสกุล จงยกตัวอย่างลักษณะรูปแบบของข้อมูลมา 5 แบบที่ใช้ในโครงสร้างข้อมูลสตริงในการเก็บค่าและเหตุใด

ตอบ 

 

6. โครงสร้างข้อมูลเรคคอร์ดเพื่อจัดเก็บข้อมูลต่อไปนี้ และกำหนดชนิดข้อมูลตามความเหมาะสม

ตอบ  อาร์เรย์ประกอบด้วยสมาชิกทุกตัวมีโครงสร้างข้อมูลชนิดเดียวกันส่วนเรคคอร์ดประกอบด้วยสมาชิกแต่ละตัวที่สามารถมีโครงสร้างข้อมูลชนิดใดก็ได้ไม่จำเป็นต้องเหมือนกัน

 

7.จงออกแบบโครงสร้างข้อมูลเรคคอร์ดเพื่อจัดเก็บข้อมูลดังต่อไปนี้ และกำหนดชนิดข้อมูลตามความเหมาะสม

A รายการสมุดโทรศัพท์

B รายละเอียดของรถยนต์ เช่นผู้ผลิต รุ่นสี

C รายละเอียดของหนังสือในห้องสมุดที่อยู่บนบัตรค้นหา เช่น ชื่อหนังสือ ชื่อผู้เขียน สำนักพิมพ์

D รายละเอียดของทีมฟุตบอลในลีก เช่น ชื่อทีม จำนวนที่แพ้ที่ชนะ

ตอบ  A) Strict Phone {

Char Name [80];

Char Phone [80];

Char Address [80];

};

B) Strict Auto {

Char  Agent Name [80];

Char Model [80];

Char Curler [80];

};

C) Strict Library {

Char  Book Name [80];

Char Writer Name [80];

Char Pin [80];

};

D) Strict Football {

Char  Team Name [80];

Char Pea;

Char china ;

};


 

8.จงออกแบบโครงสร้างข้อมูลเรคคอร์ดเมื่อต้องการเติมข้อมูลนักศึกษาประกอบด้วยรหัสนักศึกษาชื่อและนามสกุล ที่อยู่ เกรดเฉลี่ย (GPA) และเขียนโปรแกรมเพื่อใช้เก็บข้อมูล

ตอบ  Strut Student{

intID_std

char  Name [80];

char Address [80];

float GPA;

};

โปรแกรมเขียนได้ดังนี้

 

 

 

9.จงออกแบบโครงสร้างข้อมูลเรคคอร์ดเมื่อต้องการเก็บข้อมูลการลงทะเบียนของนักศึกษาประกอบด้วยรหัสนักศึกษา รหัสวิชา เกรดที่ได้ และเขียนเป็นโปรแกรมเพื่อใช้เก็บข้อมูล

struct Registration {

intId_std;

Char subject [80];

float Grade;

};

ตอบ  เขียนโปรแกรมได้ดังนี้

 

 

 

ตอนที่ 2

1.Character

ตอบ ตัวอักษรและสัญลักษณ์

2.String Length

ตอบ ความยาวสตริง

3.string Length

ตอบ  ความยาวสตริง

 

4.string Concatenation

ตอบ  ระเบียบที่เป็นโครงสร้างข้อมูล

5.fiord

ตอบ  เป็นสมาชิกในเรคคอร์ดเรียกว่าเขตข้อมูล

6.Qualification

ตอบ  แสดงคุณสมบัติ

7.stunt

ตอบ  โครงสร้างข้อมูลเรคคอร์ด ตามด้วยชื่อโครงสร้างข้อมูลตามด้วยชื่อสมาชิกแต่ละตัวพร้อมกำหนดโครงสร้างข้อมูลให้แต่ละตัว

8.Database

ตอบ  เรคคอร์ดหลายๆเรคคอร์ดท่เก็บข้อมูลที่มีลักษณะเดียวกันเป็นจำนวนมากๆ

 

 

แบบฝึกหัดบทที่ 4

1.โครงสร้างข้อมูลสแตกมีชุดปฏิบัติการอะไรบ้าง และมีขั้นตอนการทำงานอย่างไร

ตอบ1.Creategtack

2.Push (Value stack)

3.Popstack

2.จงแสดงภาพขั้นตอนการเก็บค่าลงในสแตกเมื่อมีการใช้ชุดปฏิบัติการ Push และ Pop ตามลำดับต่อไปนี้

ตอบ  a.สร้างสแตก s

 

 

 

 

 

 

3.ถ้าให้ s เป็นสแตกที่เติมค่าเป็นตัวเลขได้ไม่เกิน 5 ค่า หากมีการทำงานตามลำดับในแต่ละข้อต่อไปนี้ สแตกจะมีลักษณะเป็นอย่างไรและมีข้อผิดพลาดเกิดขึ้นอย่างไรหรือไม่

ตอบ ไม่มี

 

 

 

 

 

 

 

 

 

 

 

 

4.จงเขียนอัลกอริทึมโดยใช้สแตกเพื่อทำการแสดงตัวเลขที่มีเครื่องหมายจุลภาคแทรกระหว่างเลขสามหลัก เช่น 123456 แสดงเป็น 1,2,3,4,567

ตอบ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

บทที่ 5  โครงสร้างข้อมูลคิว

ตอนที่ 1

1.โครงสร้างข้อมูลคิวมีชุดปฏิบัติการอะไรบ้าง  และมีขั้นตอนการทำงานอย่างไร

ตอบ  1.CreateQueue()  ใช้สร้างคิวใหม่ขึ้นมาใช้งาน

2.Insert(value,queue)  ใช้เพิ่มค่าใหม่เก็บลงในคิวที่ใช้งานอยู่

3.Remove (queue)  ใช้ดึงค่าออกจากคิวที่ใช้งานอยู่และส่งค่า

4.isEmpty (queue)  ใช้ตรวจสอบว่าคิวที่ใช้งานอยู่ว่างหรือไม่

การทำงานของคิว  เมื่อมีค่าส่งมาเก็บเป็นตัวแรกก็จะอยู่ส่วนหน้า  ค่าถัดมาก็จะต่อท้ายไปเรื่อยๆ  จนตัวสุดท้ายคือ ส่วนหลัง  หากมีการดึงค่าออกมาใช้  ค่าที่อยู่ส่วนหน้า  จะถูกดึงออกมาก่อน  ลักษณะที่ได้จึงเป็นลำดับการใช้งานทั่วไปและ เรียกว่า เข้าก่อนออกก่อน

2. จงแสดงภาพขั้นตอนการเก็บค่าลงในคิวเมื่อมีการใช้ชุดปฏิบัติการ Insert และ Remove ตามลำดับต่อไปนี้

Insert(‘A’) , Insert(‘B’) , Insert(‘C’) , Remove(),

Insert(‘D’) , Remove() , Remove() , Insert(‘E’) , Insert(‘F’)

ตอบ

– เริ่มต้นสร้างคิว Q ขึ้นมาทำงาน CreateQueue(G) ได้เป็นคิวว่างไม่มีสมาชิก  โดยตัวชี้ส่วนหน้าและท้ายยังไม่มีค่า

 

-นำค่า A เข้ามาเก็บเป็นตัวแรกโดยใช้ Insert(A)  ได้คิว Q=[A] ตัวชี้ Front=A,Rear=A

A

-นำค่า B เข้ามาเก็บเป็นตัวแรกโดยใช้ Insert(B)  ได้คิว Q=[A,B] ตัวชี้ Front=A,Rear=B

A B

-นำค่า C เข้ามาเก็บเป็นตัวแรกโดยใช้ Insert(C)  ได้คิว Q=[A,B,C] ตัวชี้ Front=A,Rear=C

ABC

-ต้องการดึงค่าออกมาโดยใช้ Remove()  ได้คิว Q=[B,C] ตัวชี้ Front=B,Rear=C

BC

-นำค่า D เข้ามาเก็บเป็นตัวแรกโดยใช้ Insert(D)  ได้คิว Q=[B,C,D] ตัวชี้ Front=B,Rear=D

B CD

-ต้องการดึงค่าออกมาโดยใช้ Remove()  ได้คิว Q=[C,D] ตัวชี้ Front=C,Rear=D

CD

-ต้องการดึงค่าออกมาโดยใช้ Remove()  ได้คิว Q=[D] ตัวชี้ Front=D,Rear=D

D

-นำค่า E,F เข้ามาเก็บเป็นตัวแรกโดยใช้ Insert(E) , Insert(E) ได้คิว Q=[D,E,F] ตัวชี้ Front=D,Rear=F

DE F

3.จงอธิบายลักษณะความแตกต่างระหว่างโครงสร้างข้อมูลคิวกับโครงสร้างข้อมูลสแตกเป็นอย่างไร

ตอบ  -โครงสร้างข้อมูลคิว  มีข้อกำหนดให้ชุดปฏิบัติการสามารถเพิ่มค่าแทรกเข้าไปในตอนท้ายของรายการเพียงด้านเดียว  เรียกว่า ส่วนหลัง  และลบค่าในตอนต้นของรายการเพียงด้านเดียว เรียกว่า  ส่วนหน้า

– โครงสร้างข้อมูลสแตก  มีข้อกำหนดให้ชุดปฏิบัติการ  สามารถเพิ่มและลบรายการเพียงด้านเดียว  ซึ่งเป็นด้านบนสุดของสแตก  เรียกว่า  ตัวชี้สแตก

4.จากปัญหาการสลับตู้รถไฟในรูปที่ 5.2 ถ้ากำหนดตู้รถไฟเป็น A , B , C ตามลำดับ  อยากทราบว่าการสลับตู้รถไฟมีได้กี่รูปแบบที่เป็นไปได้จากทุกรูปแบบทั้งหมดในการสลับ(Permutation) และมีแบบใดบ้าง

ตอบ  มีรูปแบบเดียว  คือ เข้าก่อนออกก่อนหรือเข้าก่อนได้บริการก่อน

5.ถ้าให้ Q เป็นคิวที่เก็บค่าเป็นตัวอักษรได้ไม่เกิน 5 ค่า  หากมีการทำงานตามลำดับในแต่ละข้อต่อไปนี้  คิวจะมีลักษณะเป็นอย่างไรและมีข้อผิดพลาดเกินขึ้นอย่างไรหรือไม่

a)  Insert(‘A’,Q);

Insert(‘B’,Q);

Insert(‘C’,Q);

ch=Remove(Q);

Insert(‘ch’,Q);

 

a)  ch= ‘M’;

for(i=0; i<3; i++) {

Insert(ch,Q);

Insert(ch+1,Q);

ch=Remove(Q);

 

 

 

 

 

 

 

ตอบ

 

6.จงเขียนโปรแกรมสร้างคิว Q ที่เก็บค่าตัวเลขได้สูงสุด 5 ค่า  พร้อมกับชุดปฏิบัติการต่าง ๆ  และทดสอบการใช้งาน

ตอบ

 

7.จงอธิบายคิววงกลมมีลักษณะและการใช้งานเป็นอย่างไร

ตอบ  มีลักษณะเป็นเชิงเส้นรูปวงแหวน

การใช้งาน

-อัลกอริทึมการเพิ่มค่าเก็บลงในคิว

1.กำหนดค่าให้กับ nuwRear เท่ากับ (Rear+1) mod  maxSize

2.ถ้าค่าของ newRear  ไม่เท่ากับค่าของ Front ทำดังนี้

2.1 ทำการนำค่าเก็บลงในคิวยังตำแหน่งที่ Rear+1

2.2 กำหนดค่าของ Rear ให้เท่ากับค่าของ newRear ไม่เช่นนั้น  จะแจ้งกลับมาว่าคิวว่าง

-อัลกอริทึมการดึงค่าออกจากคิว

1.ถ้าคิวไม่ว่าง  ทำดังนี้

1.1 ทำการดึงค่าที่อยู่ในคิวยังตำแหน่งที่ Front ออกมาให้

1.2 เพิ่มค่าให้กับ  Front  เท่ากับ (Front r+1) mod  maxSize  ไม่เช่นนั้น  จะแจ้งกลับมาว่าคิวว่าง

8.จงอธิบายคิวลำดับความสำคัญมีลักษณะและการใช้งานเป็นอย่างไร

ตอบ  ได้มีการจัดลำดับ  2 แบบ คือ  ให้ความสำคัญจากค่าน้อยไปหาค่ามาก  และจากค่ามากไปหาค่าน้อย  โดยส่วนใหญ่จะใช้ค่ามากกว่าในการเพิ่มสมาชิกเข้ามาในคิวไปจำเป็นต้องเข้ามาตามลำดับ  แต่การนำออกจะต้องตามลำดับ  ดังนั้น  การลบสมาชิกจากคิวจะมีการทำงาน 2 เรื่อง  คือ  หาสมาชิกที่สำคัญมากสุด  ต้องเข้าไปเรียกใช้งานสมาชิกทุกตัว  และเมื่อลบสมาชิกออกจากคิวในช่วงกลาง  จะต้องมีการขยับสมาชิกตัวถัดไปมาอยู่แทน

9.จากข้อ 2 หากใช้คิวลำดับความสำคัญจะมีขั้นตอนการเก็บค่าเป็นอย่างไร

ตอบ

ตอนที่ 2

1.Rear

ตอบ  ส่วนหลัง

2.Queuing  Theory

ตอบ  การนำหลักการของคิวมาใช้

3.First-In-First-Out

ตอบ  เข้าก่อนออกก่อน

4.Queue  Overflow

ตอบ  การล้นของข้อมูลในคิว

5.Modulo

ตอบ  การหารเหลือเศษ

6.Priority  Queue

ตอบ  คิวลำดับความสำคัญ

7.Descending

ตอบ  จากค่ามากไปหาค่าน้อย

8.Job Control Block

ตอบ  คิวลำดับความสำคัญเป็นตัวควบคุมงาน

 

บทที่ 6 โครงสร้างข้อมูลลิงค์ลิสต์

ตอนที่ 1

1.ชุดปฏิบัติการของลิงค์ลิสต์มีอะไรบ้าง และมีขั้นตอนการทำงานอย่างไร

ตอบ1.Node(p) ส่งโหนดที่ถูกชี้ด้วยต้วแปรพอยเตอร์ P กลับมาให้

2.Info (P) ส่งค่าในส่วนเก็บข้อมูลของโหนดที่ถูกชี้ด้วยตัวแปรพอยเตอร์ p กลับมาให้

3.Next(P) ส่งพอยเตอร์ในส่วนขอบการเชื่อมต่อโหนดที่ถูกชี้ด้วยตัวแปรพอยเตอร์ P กลับมาให้

2.จงอธิบายและแสดงลำดับขั้นตอนารเพิ่มโหนดใหม่ไว้ที่ท้ายของลิ้งค์ลิสต์

ตอบ1.สร้างโหนดใหม่โดยให้ New ชี้ไปยัง Node ใหม่ :Next(New)=Null

2.Info (New)=Data เช่นให้เท่ากับ 5

3.P= ชี้ไปยัง Node สุดท้าย

3.จงอธิบายและแสดงลำดับขั้นตอนการลบโหนดออกจากลิ้งค์ลิสต์

ตอบ1. P=first คือ P มาชี้ที่ Node แรก

2.First=Net(First) ให้ First ไปชี้ที่ Node ที่ 2

3.Free(P) ทำการลบ Node ที่ P ชี้อยู่

4.จงอธิบายลิงค์ลิสต์วงกลมมีลักษณะและการใช้งานเป็นอย่างไร

ตอบ วิธารที่ทำให้สามารถวิ่งจากโหนดหนึ่งไปยังอีกโหนดอื่น ๆ ได้ในลิ้งค์ลิสต์โดยให้ตัวชี้ของโหนดสุดท้ายชื่อในค่า Null ที่ให้ชี้กลับไปยังโหนด แรกแทน

การใช้งาน

มีการเพิ่มหัวรายการเข้ามาในตอนต้นหรือท้ายลิ้งค์ลิสต์วงกลมการวิ่งไปแต่ละโหนดจะทราบได้ว่าจุดสิ้นสุดอยู่ตรงไหนโดยใช้โหนดหัวรายการ

5.จงอธิบายลิ้งลิสต์สองทางมีลักษณะและการใช้งานเป็นอย่างไร

ตอบ เป็นลิ้งค์ลิสต์ที่มีตัวชี้สองทางทั้งซ้ายและขวา การทำงานของลิ้งค์ลิสต์อาจต้องวิ่งไปยังโหนดต่างๆ ในลิ้งค์ลิสต์โดยการถอยหลังกลับไปยังโหนดก่อนหน้าหรือลบแต่โหนด

6.จงสร้างลิ้งค์ลิสต์ทางเดียวทำหน้าที่เป็นสแตกพร้อมชุดปฏิบัติการ และมีลำดับขั้นการทำงานดังนี้

Push(‘X’), Push(‘L’), Push(‘R’), Pop(), Push(‘A’), Pop(), Pop(),

Push(‘Q’)

 

ตอบ

 

 

 

 

 

 

 

7.การใช้ลิ้งค์ลิสต์เป็นสแตกและคิวจะแตกต่างจากการใช้อาร์เรย์อย่างไร

ตอบ โครงสร้างข้อมูลกับอาร์เรย์ จำกัดค่ายของสมาชิกที่ใส่ลงและจำกัดชนิดของข้อมูลส่วนโครงสร้างข้อมูลแบบลิงค์ลิสต์ที่เป็นสแตกและคิวจำนวนสมาชิกที่ใส่ลงไปไม่จำกัดจำนวน

8.จงเขียนชุดปฏิบัติการเพื่อนับจำนวนโหนดที่มีลิ้งค์ลิสต์

ตอบ

 

9.จงเขียนชุดปฏิบัติการเพื่อรวมสองลิ้งค์ลิสต์คือ A , B  ไว้ที่ลิ้งลิสต์ คือ C โดยมีการสลับโหนดเป็นดังนี้

A={X1,X2,X3,..,Xn}และ {Y1 ,Y2 ,Y3,.., Yn}จะได้

C={X1,Y1,X2,Y2,X3,Y3,.., Xn, Yn}

ตอบ

ตอนที่ 2

1.Non-sequenial

ตอบ รูปแบบไฟล์เรียงตามลำดับ

2.Node

ตอบ  สมาชิกแต่ละตัว

3.Homogenous

ตอบ ชนิดเดียวกัน

4.Sequential Search

ตอบ  การค้นหาเรียงตามลำดับ

5.Memory Address

ตอบ ตำแหน่งแอดเดรสในหน่วยความจำ

6.Predecessor

ตอบ โหนดส่วนหน้า

7.Singly Linked List

ตอบ  ลิ้งค์ลิสต์ทางเดียว

8.Head Node

ตอบ โหนดหัวรายการ

9.Josephus Problem

ตอบ  ปัญหาโจเซฟ

10.Symmetrically Liked List

ตอบ ลิ้งค์ลิสต์สมมาตร

11.Circular Doubly Linked List

ตอบ  ลิ้งค์ลิสต์ 2 ทางวงกลม

 

บทที่ 7 รีเคอร์ซีฟ

ตอนที่ 1 อธิบาย

ข้อ 1 จงยกตัวอย่างฟังก์ชันที่ทำงานแบบรีเคอร์ซีฟ และลำดับการทำงานเป็นอย่างไร

ตอบpower() ลำดับการทำงาน จะเริ่มเรียกตัวเองก่อน แล้วทำงานลงไปเรื่อยๆจนถึงกรณีพื้นฐาน จากนั้นถอยหลังกลับขึ้นมาตามทางเดิม

ข้อ 2 จากตารางที่ 7.5 เป็นตัวอย่างโปรแกรมการย้ายแผ่นจานจากเสา A ไปเก็บไว้ที่เสา B ในตอนสุดท้าย หากต้องการย้ายไว้ที่เสา C ในตอนสุดท้ายจะต้องแก้ไขโปรแกรมดังกล่าวอย่างไรและลำดับการย้ายแผ่นจานจะเป็นอย่างไร

ตอบ

 

 

ข้อ 3 จงอธิบายรีเคอร์ซิฟโดยอ้อมมีลักษณะเป็นอย่างไร มีแบบใดบ้างและแตกต่างกันอย่างไร

ตอบ มีการเรียกฟังก์ชันอื่นมาทำงานและเป็นการเรียกแบบลูกโซ่ที่ย้อนกลับมาเรียกฟังก์ชันแรก ซึ่งจะมี 2 ประเภท ได้แก่

  1. รีเคอร์ซิฟสองฝ่าย ซึ่งจะมีสองฟังก์ชันที่ต่างเรียกฟังก์ชันตรงข้ามมาทำงาน
  2. รีเคอร์ซิฟอ้อมทั่วไป มีหลายฟังก์ชันเรียกต่อกับโดยฟังก์ชันสุดท้ายเรียกย้อนกลับมายังฟังก์ชันแรก

ข้อ 4 จงแสดงลำดับขั้นตอนี่เกิดขึ้นเมื่อมีการเรียกฟังก์ชันรีเคอร์ซิฟขึ้นมาทำงาน

ตอบ การทำงานในคอมพิวเตอร์จะคอยดูเส้นทางการทำงานของโปรแกรมหรือโปรแกรมย่อยที่ถูกเรียกขึ้นมาทำงาน ดังนั้นก่อนโปรแกรมจะเริ่มทำงานจะมีการบันทึกเก็บข้อมูลข่าวสารเดิม ที่กำลังใช้งานอยู่ เมื่อจะนำกลับมาใช้ต่อไปหลังจากที่โปรแกรมทำงานสิ้นสุด โดยคอมพิวเตอร์มักจะจัดสรรพื้นที่หน่วยความจำ เมื่อมีโปรแกรมย่อยหนึ่งถูกขัดจังหวะจากโปรแกรมย่อยอื่น ก็จะมีการเก็บค่าของตัวแปรพารามิเตอร์ แอดเดรสถอยแล้ว และค่าอื่นๆของโปรแกรมที่ถูกขัดจังหวะหลังจากที่โปรแกรมย่อยทำงานเสร็จที่จะนำค่าต่างๆก่อนถูกขัดจังหวะกลับมาใช้งานต่อไป

ข้อที่ 5จงอธิบายแอดติเวชั่นแรคคอร์ดคืออะไรมีความสำคัญอย่างไรต่อฟังก์ชั่นรีเคอร์ซิฟ

ตอบ คือ การเก็บข้อมูลข่าวสาร มีความสำคัญคือ เก็บข้อมูลข่าวสารหรือค่าอื่นๆของโปรแกรมที่ถูกขัดจังหวะ เมื่อโปรแกรมย่อยทำงานเสร็จก็จะนำค่าต่างๆที่ก่อนที่จะถูกขัดจังหวะกลับมาใช้งานต่อไป


 

 ข้อที่  6พิจารณาจากฟังก์ชันรีเคอร์ซีฟต่อไปนี้

 

ข้อ 7. จากฟังก์ชันรีเคอร์ซีฟในข้อ 6 หากเปลี่ยนคำสั่งการเรียกฟังก์ชันRecur (ch-1);เป็นRecur (ch+1); แทนผลลัพธ์ได้จะเปลี่ยนไปจากเดิมเป็ฯอย่างไร

ตอบ

 


 

ข้อ 8 พิจารณาจากฟังก์ชันรีเคอร์ซีฟต่อไปนี้

 

ตอนที่ 2

  1. 1.      Recursive Function

ตอบฟังก์ชันรีเคอร์ซิฟ

  1. 2.      Base Class

ตอบกรณีพื้นฐาน

  1. 3.      Recursive Call

ตอบเรียกตัวเอง

  1. 4.      Backtracking

ตอบการถอยกลับไปตามทางเดิน

  1. 5.      Recursive Tree

ตอบทรีรีเคอร์ซิฟ

  1. 6.      Indirect Recursive

ตอบรีเคอร์ซิโดยอ้อม

  1. 7.      Mutual Recursion

ตอบรีเคอร์ซิฟสองฝ่าย

  1. 8.      Prototype

ตอบล่วงหน้า

9.Permutation

ตอบการสับเปลี่ยนลำดับ

  1. 10.  Activation Record

ตอบการเก็บข้อมูลข่าวสาร

 

บทที่ 8 เรื่อง อัลกอริทึม

ตอนที่ 1

อธิบาย (หมายถึง การให้รายละเอียดเพิ่มเติม ขยายความ ถ้ามีตัวอย่างให้ยกตัวอย่างประกอบ) ตอบแบบสั้น

1.การตรวจสอบความถูกต้องของอัลกอริทึมเพื่ออะไร และมีการตรวจสอบอย่างไร

ตอบ  เพื่อทดสอบกับข้อมูลที่หลากหลายยังไม่มีประสิทธิภาพเพียงพอเนื่องจากการทดสอบแสดงให้ทราบถึงข้อผิดพลาดที่ปรากฏอยู่เท่านั้น แต่ข้อผิดพลาดที่ไม่ปรากฏอยู่เท่านั้น แต่ข้อผิดพลาดที่ไม่ปรากฏจะไม่สามารถทราบได้ จึงนำการตรวจสอบแบบการอนุมาน ( Deductive) มาใช้เพื่อรับประกันว่าผลลัพธ์มีความถูกต้อง

2.การวัดผลประสิทธิภาพการทำงานของอัลกอริทึมมีแบบใดบ้าง

ตอบ  แบบแรก คือ การขอใช้พื้นที่ว่าง

แบบที่สอง คือ ประสิทธิภาพเวลา

3.ปัจจัยที่มีผลกระทบต่อประสิทธิภาพการทำงานของอัลกอริทึมมีแบบใดบ้าง

ตอบ  1.ขนาดข้อมูลที่รับเข้ามา

2.ชนิดของเครื่องคอมพิวเตอร์

3.คุณภาพซอร์สโค้ดและคอมไพเลอร์

4.กาวัดผลประสิทธิภาพการทำงานโดยพิจารณาจากการจัดการข้อมูลมีลักษณะการวัดผลอย่างไร

ตอบ  วัดประสิทธิภาพของอัลกอริทึมในกรณีแย่ที่สุด

5.การวัดผลประสิทธิภาพการทำงานโดยใช้เวลา จะมีวิธีใดบ้าง

ตอบ  1.การคำนวณเชิงซ้อน

2.การจัดเรียงลำดับข้อมูล

6.จงอธิบายความหมายของเครื่องหมายบิ๊กโอ  เครื่องหมายโอเมก้า  และเครื่องหมายเตตตะ

ตอบ  เครื่องหมาย บิ๊กโอ จะหมายถึงเวลาการทำงานของ f (n) น้อยกว่าหรือเท่ากับ g (n) และได้ว่า g (n) เป็นขอบเขตด้านบนของ f (n)

เครื่องหมายโอเมก้า จะหมายถึง เวลาการทำงานของ f (n) มากกว่าหรือเท่ากับ g (n) และได้ว่า g (n)เป็นขอบเขตด้านล่างของ f (n)

เครื่องหมายเตตตะ จะหมายถึง เวลาการทำงานของ f (n) เท่ากับ g (n)

7.จงอธิบายบิ๊กโอของฟังก์ชันยกกำลังสองมีลักษณะเป็นอย่างไร

ตอบ  มีลักษณะก็ คือ หากต้องการให้เป็นเครื่องหมายบิ๊กโอต้องมีการแยก ออกเป็นหน่วย ๆ จากนั้นก็จะใช้หน่วยที่มากที่สุดเป็นลักษณะเชิงซ้อน

8.จากบางส่วนของอัลกอริทึมที่เขียนด้วยภาษาซีเป็นการบวกค่าของแมตทริก จงแสดงจำนวนการทำงานของแต่ละประโยคและบิ๊กโอเป็นอย่างไรในกรณีแย่ที่สุด

for ( i = 0; i < n; i++);

for( j = 0; j < n; j++);

C [ i ] [ j ] = A[ i ] [ j ] + B[ i ] [ j ];

ตอบ

9.จากบางส่วนของอัลกอริทึมที่เขียนด้วยภาษาซีเป็นการคูณกันของแมตทริก จงแสดงจำนวนการทำงานของแต่ละประโยคและมีบิ๊กโอเป็นอย่างไรในกรณีแย่ที่สุด

for ( i = 0; i < n; i++);

for( j = 0; j < n; j++) {

C [ i ] [ j ] = 0;

for ( k = 0; k < n; k++)

C [ i ] [ j ] = C [ i ] [ j ] + A[ i ] [ k ] + B[ k ] [ j ];

}

ตอบ

10. จากบางส่วนของอัลกอริทึมที่เขียนด้วยภาษาซีเป็นการจัดเรียงลำดับข้อมูลแบบบับเบิลจงแสดงจำนวนการทำงานของแต่ละประโยคและมีบิ๊กโอเป็นอย่างไรในกรณีแย่ที่สุด

for ( i = o;  i < n – i;  i ++)

for (j  = i;  j  < n – l; j ++)

if ( x [ j ]  > x [ j + l ] ){

temp = x [ j ];

x [ j + l = temp];

}

ตอบ

 

ตอนที่ 2

อธิบายคำศัพท์ ( หมายถึง การแปลคำศัพท์ ขยายความ อธิบายเพิ่มเติม ถ้ามีตัวอย่างให้ยกประกอบ ) ตอบแบบสั้น

1.Input  Assertion

ตอบ  ข้อมูลที่จะรับเข้ามาใช้งาน

2.Postcondition

ตอบ  เงื่อนไขตอนท้าย

3.Intermediate  Assertion

ตอบ  การวินิจฉัยตอนกลาง

4.Loop  Invariant

ตอบ  การวนลูปสม่ำเสมอ

5.Sentinel–controlled  Loop

ตอบ  ตัวควบคุมจบการวนลูป

6.Euclid ’s Algorithm

ตอบ  อัลกอริทึมของยูคลิด

 

7.Greatest  Common  Divisor

ตอบ  เป็นค่าสูงสุดที่สามารถนำไปหารค่าสองค่าได้ลงตัว

8.Time  Efficiency

ตอบ  ประสิทธิภาพเวลา

9.Worst  Case

ตอบ  กรณีแย่ที่สุด

10.Step  Count

ตอบ นับขั้นตอน

11.Asymptotic  Complexity

ตอบ  อัตราการเติบโตที่ไม่สิ้นสุด

12. Exponential Function

ตอบ  ฟังชันก์เอ็กโปเนนเชียล

 

บทที่ 9 โครงสร้างข้อมูลทรี

1.จงอธิบายลักษณะโครงสร้างเชิงแตกต่างจากโครงสร้างไม่เป็นเส้นอย่างไร

ตอบ  โครงสร้างเชิงเส้นจะมีสมาชิกตัวถัดไปเพียงตัวเดียว  แต่โครงสร้างเชิงเส้น  จะมีสมาชิกตัวถัดไปหลายตัวโดยการแตกสาขา

2.จงอธิบายการสร้างไบนารีทรีโดยใช้อาร์เรย์เป็นอย่างไร

ตอบ  การสร้างไบนารี่ทรีโดยใช้อาร์เรย์  จะได้ทรีที่มีจำนวนโหนดแน่นอน  ตามขนาดของอาร์เรย์

3.ชุดปฏิบัตการของไบนารี่ทรีโดยใช้ลิ้งลิสต์มีอะไรบ้าง

ตอบInfo(p)  เป็นการส่งค่าที่เก็บอยู่ในโหนดที่  p  ชี้กลับมาให้

Left(p)  เป็นการส่งโหนดลูกด้านซ้ายของโหนดที่  p  ชี้กลับมาให้

Right(p) เป็นการส่งโหนดลูกด้านขวาของโหนดที่  p  ชี้กลับมาให้

Father(p)  เป็นการส่งโหนดพ่อของโหนดที่  p ชี้กลับมาให้

4.จงอธิบายการวิ่งตามเส้นทางในไบนารี่ทรีแบบพรี

ตอบมีลักษณะการวิ่งในแนวลึกก่อน (Depth-first Order) มีอัลกิริทึมการทำงานในตาราง

 

 

 

 

 

 

 

 

5.จงอธิบายการวิ่งตามเส้นทางใน ทรีแบบโพสต์-ออเดอร์เป็นอย่างไร

 

ตอบ  มีอัลกิริทึมการทำงานดังในตาราง

 

 

 

6.ในการวิ่งตามเส้นทางในทรีเมื่อผ่านโหนดไปแล้วไม่สามารถวิ่งถอยหลังกลับไปยังโหนดเหล่านั้นได้  ถ้าต้องการวิ่งถอยหลังกลับไปยังโหนดที่ผ่านมาได้ท่านคิดว่ามีวิธีการอย่างไรนำมาใช้

(วิธีเหล่านี้เรียกว่า  Baktarcking)

ตอบ

 

 

7.พิจารณาจากไบนารี่ทรีต่อไปนี้

 

จงแสดงลำดับโหนดของทรีเมื่อมีการวิ่งตามเส้นทางในแบบพรี-ออเดอร์,  แบบอิน-ออเดอร์

และแบบโพสต์-ออเดอร์

ตอบ

 

 

8. จงอธิบายยลักษณะไบนารี่เสิร์ชทรีเป็นอย่างไร

ตอบ ไบนารี่เสิร์ชทรี (Binary Search Tree, BST) เป็นไบนารี่ทรีที่รวบรวมค่าของ N เรคคอร์ดซึ่งเป็นคีย์  (Key) ตั้งแต่  K1 , K2 ,…….Kn โดยแต่ละโหนด Ri  จะมี  Ki เพียงคีย์เดียวสำหรับ i=1,2,….,N คีย์เป็นค่าสร้างความแตกต่าง (Identifier)  ให้แต่ละโหนด

 

9. จากตัวอักษรในแต่ละข้อต่อไปนี้  เมื่อนำมาใส่ตามลำดับดังกล่าวจะเป็นไบนารีเสิร์ชทรีลักษณะอย่างไร

(a) A, C, R, E, S(b) R, A, C, E, S

(c) C, A, R, E, S(d) C, O, R, N, F, L, A, K, E, S

ตอบ

 

 

 

 

 

10.  พิจารณาจากไบนารีทรีต่อไปนี้

 

 

จงสร้างไบนารีทรีขึ้นใหม่มีลักษณะเป็นอย่างไรหลังจากมีการทำงานในแต่ละข้อต่อนี้

(a)  เพิ่ม  7(b)  เพิ่ม  7, 1, 55, 29  และ  19

(c)  ลบ  8(d)  ลบ  8, 37  และ  62

(e) เพิ่ม 7,  ลบ  8,  เพิ่ม  59,  ลบ  60,  เพิ่ม  92,  ลบ  50

ตอบ

 

ตอนที่  2  อธิบายศัพท์

1.Nonlinear Data  Structure

 ตอบ  โครงสร้างข้อมูลไม่เป็นเชิงเส้น

2.Branching  Structure

ตอบ  โครงสร้างข้อมูลแตกสาขา

3.General  Tree

ตอบ  ลักษณะพิเศษของทรีทั่วไป

4.In-degree

ตอบ  จำนวนเอจหรือกิ่งเข้ามาหรือดีกรีเข้า

5.Parent  Node

ตอบ  โหนดพ่อ

6.Leaves  Node

ตอบ  โหนดปลาย

7.Complete  Binary  tree

ตอบ  ไบนารี่ทรีสมบูรณ์

 

8.Tree  Traversal

ตอบ  การวิ่งตามเส้นในทางทรี

9.Depth-first  Order

ตอบ การวิ่งในแนวลึกก่อน

10.Binary Search  Tree

ตอบ  ไบนารี่เสิร์ชทรี

11.Inorder  Predecessor

ตอบ  ค่าที่มากที่สุดในทรีย่อยด้านซ้าย

12.Successor  Node

ตอบ  โหนดซัดเซอร์เซส  มาแทนในโหนดที่ต้องการลบ

 

บทที่ 10 โครงส้รางข้อมูลกราฟ

ตอนที่ 1 อธิบาย

1.จงอธิบายความแตกต่างระหว่าง กราฟทั่วไปกับมัลติกราฟ เป็นอย่างไร

ตอบ กราฟทั่วไปจะเป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้นแต่กราฟแบบมัลติลิสต์ ในโครงสร้างกราฟประกอบด้วยสองส่วยคือ ได้เร็กทอรี่ของโหนดและเซ็ตลิ้งค์สิสต์ของเอจ

 

2 .จงอธิบายลักษณะของกราฟทิศทางเป็นอย่างไร

ตอบลักษณะเฉพาะที่พิ่มเข้ามาในโครงสร้างข้อมุลกราฟทั่วไปได้เป็นกราฟทิศทาง ซ่งใช้หัวลูกศรกำหนดิศทางให้ต่เอจในกราฟ  กราฟทิศทางจะมีดีกรีเข้า เป็นจำนวนเอจที่ชี้เข้ามาสิ้สสุดทีโหนดและมีดีกรีออก เป็จำนวนเอจที่ชี้ออกจากโหนด ดีกรีของโหนดในโหนดหนึ่ง

 

3.จงอธิบายการสร้างกราฟโดยใช้แมตทริกติดกันเป็นอย่างไร

ตอบ ให้กราฟ G มีเซ็ตของโหหนดเป็น VG และเซ็ตของเอจเป็น EG โดยกราฟมีออเดอร์เท่ากับ N ซึ่ง N > = 1แนวทางหนึ่งในการกำหนดเป็นกราฟโดยใช้แมตทริกติดกัน เป็นอาร์เรย์ N-ต่อ –N เมื่อห้เป็นอาร์เรย์ A จะได้ว่า

 

 

A(I , j)={

 

 

หมายความว่า  หากมีเอจที่เชื่อมต่อกันระหว่างโหนด I กับ j  ก็จะได้ A(I,j)=1ไม่เช่นนั้นมีค่าเป็น 0

 

4.จากกราฟทิศทาง ทั้งสองภาพต่อไปนี้จงสร้างภาพต่อไปนี้  จงสร้างอาร์เรย์ในรูปแบบแมตทริกติดกัน

 

 

ตอบ

 

 

12345 1 2 3 4
10111111 1 0 1

21110021 1 1 0

31001030 1 1 1

41101141 0 1 1

 

 

 

5.จากอาร์เรย์ในรูแบบแมตทริกติดกันทั้งสองภาพต่อไปนี้ จงสร้างเป็นกราฟทิศทาง

 

ตอบ

 

 

 

 

 

6.จากกราฟทิศทางในข้อ 4 จงสร้างกราฟแบบไดเร็คทรอรีโหนด

ตอบ

 

 

7 จงอธิบายการวิ่งตามเส้นทางในกราฟตามแนวลึกก่อนเป็นอย่างไร

ตอบ  ขณะที่การวิ่งตามเส้นทางในแนวกว้างก่อนมีการวิ่งผ่านโหนดเป็นระดับต่อระดับ แต่การวิ่งตรามเส้นทางในแนวลึกก่อน หรือการค้นหาตามแนวลึกก่อน จะเริ่มจากโหนดแรกวิ่งผ่านตามเส้นทางเพื่อไปยังโหนดสุดท้ายซึ่งไม่สามารถวิ่งต่อไปได้อีก จากนั้นถอยกลับเพื่อวิ่งผ่านต่อไปยังเส้นทางอื่นที่อยู่ติดกันในโหนดก่อนหน้านี้และวิ่งจนครอบทุกโหนดในกราฟ

 

8.จากกราฟทิศทางต่อไปนี้ จงหาลำดับของโหนดจากการวิ่งผ่านในแต่ละข้อต่อไปนี้ (การ เลือกแต่ละครั้งอาจมีทางเลือกมากกว่าหนึ่งเส้นทาง)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

a) วิ่งตามทางแนวกว้างก่อนโดยเริ่มต้นที่โหนด  A

b)วิ่งตามทางแนวกว้างก่อนโดยเริ่มต้นที่โหนด  F

c)วิ่งตามทางแนวลึกก่อนโดยเริ่มต้นที่โหนด  A

d)วิ่งตามทางแนวลึกก่อนโดยเริ่มต้นที่โหนด  F

ตอบ (a)

(b)

(c)

(d)

9. จงเขียนโปรแกรมวิ่งตามเส้นทางตามแนวลึกก่อนในกราฟทิศทางโดยใช้อาร์เรย์แบบแมตทริกติดกัน

ตอบ

 

 

10 .จากกราฟทิศทางในข้อ 8 จงหาเส้นทางที่สั้นที่สุดในแต่ละขอต่อไปนี้

(a) เส้นทางที่สั้นที่สุดจากโหนด A ไป  E

(b)เส้นทางที่สั้นที่สุดจากโหนด A ไป  H

(c)เส้นทางที่สั้นที่สุดจากโหนด G ไป  C

(d)เส้นทางที่สั้นที่สุดจากโหนด  J ไป  A

 

ตอบ (a)  A=>D=>C=>F=>J=>K=>I=>G=>H=>E

(b)A=>D=>C=>F=>J=>K=>I=>G=>H

(c)G=>H=>E=>C

(d)J=>K=>I=>G=>H=>A

ตอนที่  2 อธิบายคำศัพท์

1.Edge

ตอบ โหนดของกราฟและเส้น

2.Vertice

ตอบ เวอร์ทิค  โหนดของกราฟและเส้น

3.Connectd Graph

ตอบ กราฟต่อกัน

4.Acyclec

ตอบ กราฟที่ไม่มีเส้น

5.Out-degree

ตอบ ดีกรีเข้า

6.Wieghtc  Edge

ตอบ เอจมีน้ำหนัก

7.Graph Traversal

ตอบ การวิ่งตามเส้นทางในกราฟ

8.Breath-first Search

ตอบ การค้นหาตามแนวกว้างก่อน

9.Reachability

ตอบ กราฟสามารถวิ่งไปโหนดอื่น ๆ ได้หรือไม่

10.Shotest Path Algorithm 

ตอบ การหาแนวทางที่สั้นที่สุด

11.Dijkstra’s Algorithm

ตอบ อัลกอริทึมของ ดิจสตรา

12.Routing Problem

ตอบ การค้นหาเส้นทางที่สั้นที่สุด

 

บทที่ 11 การจัดเรียงลำดับข้อมูล

ตอนที่ 1 อธิบาย

1. จงอธิบายความแตกต่างระหว่างการเรียงลำดับภายในกับการเรียงลำดับภายนอกเป็นอย่างไร

ตอบ    การจัดเรียงลำดับภายใน เป็นหลักการที่นำมาใช้เมื่อข้อมูลทั้งหมดที่รวบรวมไว้ มีขนาดที่เล็กเพียงพอที่จะเก็บไว้ และทำการเรียงลำดับภายในหน่วยความจำหลัก เวลาที่มักใช้ในการอ่านและเขียนเรคคอร์ดจะนำใช้พิจารณาถึงประสิทธิ์ภาพการเรียงลำดับข้อมูล แต่จะใช้เวลาในการเปรียบเทียบค่าของคีย์มาพิจารณา ส่วนการเรียงลำดับภายนอกเป็นหลักการที่นำมาใช้กับข้อมูลที่รวบรวมไว้เป็นจำนวนมากๆ ไม่สามารถเก็บไว้ในหน่วยความจำหลักได้หมดในคราวเดียวกัน แต่ต้องเก็บไว้ในหน่วยความจำหลักได้หมด ในคราวเดียวกัน แต่ต้องเก็บไว้ในหน่วยสำรอง

2. จงอธิบายการเรียงลำดับที่มีการเปรียบเทียบ O(n2) มีวิธีการแบบใดบ้าง

ตอบ1. การเรียงลำดับแบบดับเบิ้ล  (Bubble Sort)

2. การเรียงลำดับแบเลือก  (Selection Sort)

3. การเรียงลำดับแบแทรก  (Insertion Sort)

4. การเรียงลำดับแบบเชล์(Shell Sort)

3. จงอธิบายการเรียงลำดับที่ไม่มีการเปรียบเทียบมีวิธีแบบใดบ้าง

ตอบ    1. การเรียงลำดับแบบนับจำนวน(Countinq Sort)

2. การเรียงลำดับแบบเรดิกซ์(Radix Sort)

4. จากอาร์เรย์ x ที่มีค่าของสมาชิกเป็น 60, 50, 70, 10, 40, 20 ถ้าต้องการเรียงลำดับแบบบับเบิลจากค่ามากไปหาน้อย ค่าของสมาชิกจะเป็นอย่างไรในแต่ละรอบ จะต้องใช้การจัดเรียงลำดับกี่รอบ และมีการสลับตำแน่งกันทั้งหมดกี่ครั้ง

ตอบ

 

 

5. จากอาร์เรย์ x ที่มีค่าของสมาชิกเป็น 30, 50, 70, 10, 40, 60 ถ้าต้องการเรียงลำดับแบบเลือกจากค่ามากไปหาน้อย ค่าของสมาชิกจะเป็นอย่างไรในแต่ละรอบ จะต้องใช้การจัดเรียงลำดับกี่รอบ และมีการสลับตำแน่งกันทั้งหมดกี่ครั้ง

ตอบ

 

 

 

6. จงอธิบายและแสดงขั้นตอนการเรียงลำดับแบบเชลล์เป็นอย่างไร

ตอบการจัดเรียงลำดับแบบเซล์หรือจำนวนลำดับแบบจำนวนเพิ่มๆค่อยลดลง (Diminishing Incremeny Sort) จะใช้เรียงลำดับแบบแทรกกับกลุ่มย่อยของค่าตามลำดับ กลุ่มย่อยเหล่านี้จะถูกเลือกใช้ในทิศทางพยายามให้ค่าถูกเรียงมากสุดก่อนที่จะใช้ การเรียงลำดับแบบแทรก ก็จะได้เวลาการทำงานที่ใช้การเรียงลำดับแบบแทรกในแต่ละรอบเกือบเป็นเส้นตรง

7. จากอาร์เรย์ x ที่มีค่าของสมาชิกเป็น 45, 20, 50, 30, 80, 10, 60, 70, 40, 90 ถ้าต้องการเรียงลำดับแบบรวดเร็ว ค่าของสมาชิกจะเป็นอย่างไรในแต่ละรอบ

ตอบ

 

 

8. จากอาร์เรย์ x ที่มีค่าของสมาชิกเป็น 20, 15, 31, 10, 67, 50, 3, 49, 26 ถ้าต้องการเรียงลำดับแบบ

ฮีพ ค่าของสมาชิกจะเป็นอย่างไรในแต่ละรอบ

ตอบ

 

 

 

9.จากอาร์เรย์ x ที่มีค่าของสมาชิกเป็น 322, 715, 931, 250, 176, 845, 463, 192, 526 ถ้าต้องการเรียงลำดับแบบเรดิกซ์ ค่าของสมาชิกจะเป็นอย่างไรในแต่ละรอบ

ตอบ

 

 

 

10. จงอธิบายการเรียงลำดับและผสานแฟ้มข้อมูลเป็นอย่างไร

ตอบ

 

 

 

11. จงอธิบายและแสดงขั้นตอนการเรียงลำดับและผสานหลายขั้นตอนเป็นอย่างไร

ตอบ

 

 

 

 

12.จากอาร์เรย์ x มีค่าของสมาชิกเป็น 84, 19, 31, 25, 12, 53, 99, 68, 49, 77, 43, 30, 62, 11, 97, 80, 21, 37, 79, 55, 15, 58, 71, 23, 94, 66, 29, 63, 57, 81 จงเรียงลำดับและผสานแฟ้มข้อมูลโดยใช้การเรียงลำดับและผสานสมดุล ให้หนึ่งรันมี 3 เรคคอร์ดและมี 4 ม้วนเทป

ตอบ

 

 

 

 

 

ตอนที่ 2 อธิบายคำศัพท์

1. Internal Sorting

ตอบ การเรียงลำดับภายใน

2. Inplace Sorting

ตอบ พื้นที่หน่วยความจำของตนเอง

3. Stable Sort

ตอบ

4. Comparison Sort

ตอบ การเรียงลำดับมีการเปรียบเทียบ

5. Insertion Sort

ตอบ การเรียงลำดับแบบแทรก

6. Merge Sort

ตอบ การเรียงลำดับแบบผสมผสาน

7. Average Case

ตอบ กรณีเฉลี่ย

8. Binary Insertion Sort

ตอบ การเรียงลำดับแบบแทรกโดยแบ่งครึ่ง

9. Divide-and-Conquer

ตอบ วีธีการแบ่งและยึดรวมกัน

10. Logarithmic Time

ตอบ การทำงานที่ใช้เวลาเป็นลอกการิทึม

11. Tally Sort

ตอบ การเรียงลำดับแบบยอดรวมสูงสุด

12. Tournament Sort

ตอบ

13. Sort/Merge

ตอบ

14. M-way Natural Merge

ตอบ การผสมผสานธรรมดา M ทาง

15. Polyphase Merge

ตอบ การผสมผสานหลายขั้นตอน

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s