﻿ 代考算法和数据结构 COMP3506/750代写 - 数据结构代写, 算法代写

# 代考算法和数据结构 COMP3506/750代写

2022-09-08 09:35 星期四 所属： 数据结构代写 浏览：70 ## Semester Two Final Examinations, 2021

### Multiple Choice Questions (10 marks. Marks distributed equally for each question.)

1.An algorithm is O(n2). It takes 20 sec for a given dataset. If twice as much data is

used, then:

◯ A.It will take 40 sec.

◯ B.It will take 80 sec.

◯ C.It will take 400 sec.

◯ D.The time it will take depends on whether the new dataset is the same case as the initial dataset; average, best or worst case.  代考算法和数据结构

◯ E.None of the above.

2.Which of the following sorting algorithms has a possible worst-case running time of O(n2) where n is the number of elements to be sorted?

◯ A. Merge-sort.

◯ B.Quick-sort.

◯ C.Selection Sort.

◯ D.A and C.

◯ E.B and C.

3.An important property of a doubly linked list compared to a singly linked list is the ease of determining an item’s predecessor. Which of the following operations can use this property of a doubly linked list to the greatest advantage when compared with a singly linked list? (Assume that the lists have head references but not tail references.)

◯ A.Accessing an item.

◯ B.Adding an item at the front of the list.

◯ C.Deleting an item.

◯ D.Concatenating two lists.

◯ E.Copying a list.

### 4.Which of the following don’t affect the time complexity of bucket sort?  代考算法和数据结构

◯ A.The algorithm implemented for sorting individual buckets.

◯ B.The number of buckets used.

◯ C.The values to be sorted.

◯ D.None of the above.

◯ E.All of the above.

5.Which of the following data structures may be used to implement the Queue ADT such that it provides amortised constant running time for all operations?

◯ A.An array.

◯ B.A singly-linked list.

◯ C.A doubly-linked list.

◯ D.A circularly linked-list.

◯ E.All of the above. Semester Two Final Examinations, 2021

6.Which of the following is the number of heaps with different key/node arrangements that all include the four keys 1, 2, 3 and 4?

◯ A.2

◯ B.3

◯ C.4

◯ D.5

◯ E.None of the above.

7.After inserting the keys 12, 25, 2, 32, 65 into a red-black tree, the resulting red-black tree will have __ black nodes (Note: Null leaf nodes are not included.)

◯ A.1

◯ B.2

◯ C.3

◯ D.4

◯ E.None of the above.

### 8.Which of the following statements is correct, for a graph with n vertices and m edges?

◯ A.Topological sort can be applied to Directed Acyclic Graphs and can be implemented using BFS.

◯ B.Topological sort can be applied to Directed Acyclic Graphs and can be implemented using DFS.

◯ C.BFS can find the minimum number of edges between two vertices.

◯ D.A and C.  代考算法和数据结构

◯ E.All of the above.

9.To find the shortest paths to all other locations in a network from a given point,

which of the following algorithms are least applicable?

◯ A.Dijkstra’s.

◯ B.Floyd’s.

◯ C.Prim’s

◯ D.Kruskal’s

◯ E.B and C.

10.Which of the following is false about the string searching problem, where the pattern

has m characters, and the test has n characters?

◯ A.In many situations, the brute force string searching algorithm is sufficient.

◯ B.It is easy to code an implementation of brute force searching.

◯ C.The worst-case time complexity of brute force searching is O(m*n).

◯ D.None of the above.

◯ E.All of the above.Semester Two Final Examinations, 2021

### Short Answer Questions (40 marks. Marks as indicated.)  代考算法和数据结构

Note: Answer each question in the box provided.

11.State the big-O complexity of the following recursive function with a short explanation.(3 marks) 12.Is it possible for the amortised time complexity of an operation to be better than its worst case time complexity? In your answer describe what is meant by “amortised time complexity”. Illustrate your answer with an example. (4 marks)

13.Discuss the impact of choosing a pivot deterministically or randomly in quick sort. Hint: For “Deterministic”, discuss how “always picking the last element as pivot” will affect the worst-case time complexity. (4 marks)  代考算法和数据结构

14.We would like to sort 7 items, where each item is a 4-digit decimal number.

a) Briefly explain the maximum number of comparisons needed to sort these items with a radix sort. (2 marks)

b) What would be the Big-Omega complexity to sort these items using an insertion sort? (2 Marks)

15.Given a pointer to the last node (rightmost node in bottom layer) of a complete binary tree,describe how you would find its next adjacent node. That is, the next position where you could insert and maintain a complete binary tree. Explain how the computational complexity would differ between a linked list and an array-based representation.(6 marks)

#### 16.Draw the splay tree at each stage after the elements 1, 2, 3, and 4 are added to aninitially empty splay tree.(3 marks)

17.There is a cycle in a linked list if there exists a node in the list that can be reached again by continuously following the next pointer. An example of a cycle in a linked list is shown below.

Design an efficient algorithm in pseudo code to detect if there is a cycle in a list of n  nodes, using a Hash Table. Provide the space and time complexity of your algorithm.(5 marks)

18.Would it be possible to employ Breadth First Search to find topological sorting of vertices in a graph? If yes, write the algorithm in pseudo code, and explain it’s time complexity. If not, provide the reason. (5 marks)

19.Using Huffman’s algorithm, construct a Huffman tree that defines an optimal prefix code for the string “woolloomooloo”. Show the intermediate states of the priority queue.(6 marks) 