http:^^www.cs.washington.edu^education^courses^373^96a^midterm-topics.html
来自「This data set contains WWW-pages collect」· HTML 代码 · 共 83 行
HTML
83 行
Date: Tue, 10 Dec 1996 16:48:51 GMTServer: NCSA/1.4.2Content-type: text/html<HTML><HEAD><TITLE>CSE 373 Midterm topics</TITLE></HEAD><BODY><H1>CSE 373 Midterm topics</H1>The midterm examination on Wednesday, October 30 will coverthe following topics. Nearly all of these are covered inthe text in the associated chapters.<p><pre>Chapter 1 Abstract data type. Data structure. Encapsulation.Chapter 2 Sets: notation, standard operations, Cartesian product. Linear order (also called total order). Permutations, factorial, Stirling's formula. Generating random permutations in C++ (e.g., see p22). Boolean variables, floor and ceiling, modulus operator. Logarithms and their properties. Recursion, recursive factorial in C++, recursive Towers of Hanoi. Summations and recurrences, sum of first n integers. Sum of first n squares, Fibonacci sequence. Proof by contradiction. Proof by induction. Chapter 3 Running time formulations in terms of input size n and constants: e.g., T(n) = cn. Largest value sequential search in C++ (e.g., see p43). Constant, linear, quadratic, cubic and exponential running times. Big-Oh, big-Omega, and big-Theta definitions, notations. Simplifying big-Oh expressions. Calculating running times of programs. Binary search. Ordering functions by their growth rates.Chapter 4 Lists and the ADT on p81. Comparison of array and pointer implementations of lists. Freelists, doubly linked lists. Stack ADT, Queue ADT.Chapter 5 Binary tree, depth, height, full binary tree, complete binary tree. Full binary tree theorem. Binary tree node ADT (e.g., see p126). Preorder, inorder, and postorder traversal. Space requirements for pointer-based impl. of binary trees. Array implementation for complete binary trees. Huffman trees, encoding and decoding with Huffman trees. Prefix property of codes, efficiency of a Huffman code. Binary search tree property. Searching for an element in a BST (the find and findhelp methods). Insertion and deletion in a BST. Heap data structure and its use in implementing the priority queue. Siftdown and Buildheap operations. Time required to build the heap.Chapter 6 Parent pointer implementation of general trees. Implementation of FIND and UNION operations. Path compression.Chapter 7 Terminology for graphs. Comparison of adjacency matrix and adjacently list implementations.</pre></BODY>Last updated 25 October 1996 by S. Tanimoto</HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?