1 حل اسئلة الخوارزميات قسم الحاسوب الجامعة المستنصرية نموذج رقم
Q1: Choose the correct answer. 10 marks
1. What is the time complexity of the following fun(int n) function?
int fun(int n)
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = i; j > 0; j--)
count = count + 1;
return count;
}
(a) O(n log n)
(b) O(n2)
(c) O(n)
(d) O(n3)
(e) None of the above
2. Which of the following is the most efficient sorting technique?
(a) Heap sort (b) Selection sort (c) Bubble sort (d) Shell sort (e) All the above
3. In shell sort algorithm, the initial gap number for comparison is computed by?
(a) Divide the sum of the given list by 2 (b) Starts always from 4 (c) Divide the number of list
elements by 2 (d) All of the above. (e) None of the above
4. A graph can be represented by which of the following?
(a) Matrices (b) Linked list (c) Both (d) Stack (e)None of the above
5. Dijkstra’s algorithm is based on?
(a) Divide and conquer paradigm (b) Dynamic programming (c) Greedy Approach
(d) Backtracking paradigm (e) None of the above
6. In a Max heap the largest key is at
(a) The root (b) a leaf (c) a node (d) None of the above (e) All of the above
7. Which of the following case does not exist in the complexity theory?
(a) Best case (b) Worst case (c) Average case (d) Null case (e) All of the above
8. If f (n) =3 * log n +7n +3, then the time complexity of f(n) is?
(a) O(n) (b)O(log n) (c) (1) (d) ) (log n) (e) All of the above
9. In graph theory, starting from one node and ending to the same node is called?
(a) a direct graph (b) a cycle (c)a weight (d) edges (e) None of the above
10. The adjacency list is used to represent?
(a) a list (b) an array (c)a graph (d) a linked list (e) a stack
Q2: Apply Heap sort algorithm to sort the following list [25, 67, 56, 32, 12, 96, 82, 44]
Sol//
لتطبيق خوارزمية Heap Sort لفرز القائمة المحددة [25، 67، 56، 32، 12، 96، 82، 44]، اتبع الخطوات التالية:
1. إنشاء الحد الأقصى للكومة: تحويل القائمة المحددة إلى الحد الأقصى للكومة.
2. Heapify: قم بإزالة الحد الأقصى للعنصر من الكومة بشكل متكرر ثم قم ببناء الكومة مرة أخرى حتى يتم فرز جميع العناصر.
وإليك العملية خطوة بخطوة:
1. قم ببناء الحد الأقصى للكومة من القائمة المحددة.
2. قم بتبديل الجذر (العنصر الأقصى) بالعنصر الأخير وتقليل حجم الكومة بمقدار 1.
3. قم بتجميع العنصر الجذر مرة أخرى للحفاظ على خاصية الحد الأقصى للكومة.
4. كرر الخطوتين 2 و3 حتى يصبح حجم الكومة 1.
لننفذ هذه الخطوات:
1. القائمة الأولية: [25، 67، 56، 32، 12، 96، 82، 44]
2. إنشاء الحد الأقصى للكومة: تحويل القائمة إلى الحد الأقصى للكومة.
3. القائمة المصنفة: استخرج العناصر من الكومة القصوى.
وإليكم القائمة مرتبة:
1. الحد الأقصى للكومة الأولية: [96، 67، 82، 44، 12، 56، 25، 32]
2. بعد التكرار الأول: [82، 67، 56، 44، 12، 32، 25]، 96
3. بعد التكرار الثاني: [67، 44، 56، 25، 12، 32]، 82، 96
4. بعد التكرار الثالث: [56، 44، 32، 25، 12]، 67، 82، 96
5. بعد التكرار الرابع: [44، 25، 32، 12]، 56، 67، 82، 96
6. بعد التكرار الخامس: [32، 25، 12]، 44، 56، 67، 82، 96
7. بعد التكرار السادس: [25، 12]، 32، 44، 56، 67، 82، 96
8. بعد التكرار السابع: [12]، 25، 32، 44، 56، 67، 82، 96
إذن فالقائمة المرتبة هي: [12، 25، 32، 44، 56، 67، 82، 96]
using System;
class Program
{
static void Main(string[] args)
{
int[] A = { 70, 10, 120, 20, 130, 15, 50, 99, 120, 45 };
int[] oddLocations = GetOddLocations(A);
QuickSort(oddLocations, 0, oddLocations.Length - 1);
Console.WriteLine("Sorted array of odd locations:");
PrintArray(oddLocations);
}
static int[] GetOddLocations(int[] array)
{
int size = (array.Length + 1) / 2;
int[] result = new int[size];
int j = 0;
for (int i = 1; i < array.Length; i += 2)
{
result[j++] = array[i];
}
return result;
}
static void QuickSort(int[] array, int low, int high)
{
if (low < high)
{
int pi = Partition(array, low, high);
QuickSort(array, low, pi - 1);
QuickSort(array, pi + 1, high);
}
}
static int Partition(int[] array, int low, int high)
{
int pivot = array[high];
int i = low - 1;
for (int j = low; j < high; j++)
{
if (array[j] < pivot)
{
i++;
Swap(ref array[i], ref array[j]);
}
}
Swap(ref array[i + 1], ref array[high]);
return i + 1;
}
static void Swap(ref int a, ref int b)
{
int temp = a;
a = b;
b = temp;
}
static void PrintArray(int[] array)
{
foreach (int num in array)
{
Console.Write(num + " ");
}
Console.WriteLine();
}
}
using System;
class Program
{
static void Main(string[] args)
{
int[] A = { 70, 10, 120, 20, 130, 15, 50, 99, 120, 45 };
int[] evenLocations = GetEvenLocations(A);
SelectionSort(evenLocations);
Console.WriteLine("Sorted array of even locations:");
PrintArray(evenLocations);
int index = BinarySearch(evenLocations, 50, 0, evenLocations.Length - 1);
if (index != -1)
{
Console.WriteLine($"Element 50 found at index: {index}");
}
else
{
Console.WriteLine("Element 50 not found in the array.");
}
}
static int[] GetEvenLocations(int[] array)
{
int size = array.Length / 2;
int[] result = new int[size];
int j = 0;
for (int i = 0; i < array.Length; i += 2)
{
result[j++] = array[i];
}
return result;
}
static void SelectionSort(int[] array)
{
for (int i = 0; i < array.Length - 1; i++)
{
int minIndex = i;
for (int j = i + 1; j < array.Length; j++)
{
if (array[j] < array[minIndex])
{
minIndex = j;
}
}
if (minIndex != i)
{
Swap(ref array[i], ref array[minIndex]);
}
}
}
static int BinarySearch(int[] array, int target, int low, int high)
{
if (low <= high)
{
int mid = low + (high - low) / 2;
if (array[mid] == target)
{
return mid;
}
else if (array[mid] < target)
{
return BinarySearch(array, target, mid + 1, high);
}
else
{
return BinarySearch(array, target, low, mid - 1);
}
}
return -1;
}
static void Swap(ref int a, ref int b)
{
int temp = a;
a = b;
b = temp;
}
static void PrintArray(int[] array)
{
foreach (int num in array)
{
Console.Write(num + " ");
}
Console.WriteLine();
}
}