Data Structures and Algorithm Analysis in C++, 4th edition — Mark Allen Weiss — Complete Test Bank (Ch. 1-12)

TEST BANK
Data Structures and Algorithm Analysis in C++ | 4th edition


by Mark A. Weiss
ST
U
D
YL
AB

, Table of Content
Chapter 1 Programming: A General Overview

Chapter 2 Algorithm Analysis

Chapter 3 Lists, Stacks, and Queues

Chapter 4 Trees

Chapter 5 Hashing

Chapter 6 Priority Queues (Heaps)
Chapter 7 Sorting

Chapter 8 The Disjoint Sets Class

Chapter 9 Graph Algorithms
ST
Chapter 10 Algorithm Design Techniques

Chapter 11 Amortized Analysis

Chapter 12 Advanced Data Structures and Implementation
U
D
YL
AB

, KLJHGFDSA



CHAPTER 1


Introduction
1.1
/*
Exercise 1.1 All Chapters Included
Selection of integers with k = N/2
select1 => sorting and selecting
select2 => keeping top k
*/ All Answers Included
#include <iostream>
ST
#include <ctime>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
U
void sort(vector<int> & vec)
{ // bubble sort ascending
bool sorted = false;
D
while (!sorted)
{
sorted = true;
for (auto i = 1; i < vec.size(); i++)
YL
{
if (vec[i-1]> vec[i])
{
swap(vec[i],vec[i-1]);
sorted = false;
}
}
AB
}
}

void sortDec(vector<int> & vec)
{ // bubble sort descending
bool sorted = false;
while (!sorted)
{
sorted = true;
for (auto i = 1; i < vec.size(); i++)
{
if (vec[i-1]< vec[i])
{
swap(vec[i],vec[i-1]);
sorted = false;
}
}
}
}




kjhgfdsa

, KLJHGFDSA



int select1(vector<int> nums)
{
int k = (nums.size()+1)/2;
sort(nums);
return nums[k];
}


int select2(const vector<int> &nums)
{
int k = nums.size()/2;
vector<int> topK(nums.begin(), nums.begin() + k);

sortDec(topK);
for (auto i = k; i < nums.size(); i++)
ST
{
if (nums[i] > topK[k-1])
{
for (auto j = k-2; j >=0 ; j--)
if (nums[i] < topK[j])
{topK[j+1] = nums[i]; break;}
else
topK[j+1] = topK[j];
U
if (topK[0] < nums[i])
topK[0] = nums[i];
}
}
D
return topK[k-1];
}

int main()
YL
{
vector<int> nums;
int selected;
time_t start, end;

srand(time(NULL));
AB
for (auto numInts = 1000; numInts<=10000; numInts+=1000)
// sizes 1,000, 2,000, 3,000, ...10,000
{
nums.resize(numInts);

start = time(NULL);
for (auto i = 0; i < 10; i++) // run 10 times
{
for (auto j = 0; j < numInts; j++)
nums[j] = rand()%(2*numInts);
selected = select1(nums); // or selected = select2(nums);
}
end = time(NULL);
cout<<numInts<<"\t"<<difftime(end,start)<<endl;
}
return 0;
}




kjhgfdsa