四川大学数据结构复习

2022年四川大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A.NB.2N-1C.2ND.N-12、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。

A.插入B.选择C.希尔D.二路归并3、以下数据结构中，（）是非线性数据结构。

A.树B.字符串C.队D.栈4、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l5、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。

A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s6、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。

下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ7、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508、每个结点的度或者为0或者为2的二叉树称为正则二叉树。

n个结点的正则二叉树中有（）个叶子。

A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/29、有关二叉树下列说法正确的是（）。

A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为210、对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（）。

软件学院数据结构与算法复习提纲（2012秋季学期）1、Data structures and algorithms概念：type, simple type, composite type, aggregate type, data type, ADT, data structure, problems, function, algorithms, programs2、Mathematical preliminaries概念：set, recursion3、Algorithm Analysis概念：asymptotic algorithm analysis, growth rate, best/worst/average case, upper/lower bound, space/time tradeoff, big-Oh/big-Omega/Theta notation4、list概念：list, array-based list, linked list, ordered/unordered list, singly/doubly linked list, array, stack, queue算法：基于list/stack/queue的算法5、binary trees概念：BST, Huffman tree, full/complete binary tree, height/depth of a binary tree，full binary tree的性质，priority queue应用题：BST中的插入/删除，Huffman树的构造，heap的构造，基于遍历序列还原二叉树算法：基于二叉树遍历的各种算法，BST上的操作6、general trees概念：traversal，Equivalence classes，K-ary tree应用题：树的存储表示看懂：traversal/UNION/FIND几个操作的实现思想7、internal sorting概念：各种排序算法的best/worst/average case时间复杂度，stable sorting algorithm应用题：shellsort/bubble sort/quicksort/heapsort/的排序过程8、File processing and external sorting概念：track/sector/cluster, Golden Rule of File Processing, logical/physical file, buffer, organization of buffer pool, Locality of Reference, external sorting, run9、Searching概念：hashing, properties of hash function, collision, Open hashing, Separate chaining, Closed hashing, Probe function, load factor应用题：hash表的构造（基于不同的冲突解决方式）10、indexing概念：entry-sequenced file, indexing, primary/secondary key, Linear indexing, 2-3 tree, B-tree, B+Tree应用题：2-3 tree/B-tree/B+Tree中的insert/delete操作11、graph概念：path, cycle, connected component, Adjacent list/matrix, BFS, DFS, topological sort, DAG, MST应用题：shortest path(Dijkstra/Floyd算法)的构造，MST(Prim/Kruskal算法)的构造。

一.单选题（共44题,52.8分）1采用开放定址法处理散列表的冲突时,其平均查找长度( )。

•A、低于链接法处理冲突•B、高于链接法处理冲突•C、与链接法处理冲突相同•D、高于二分查找正确答案：B 我的答案：B得分：1.2分答案解析：2在二叉树结点的先序序列、中序序列和后序序列中,所有叶子结点的先后顺序( )。

•A、都不相同•B、完全相同•C、先序和中序相同,而与后序不同•D、中序和后序相同,而与先序不同正确答案：B 我的答案：B得分：1.2分答案解析：3对一个算法的评价,不包括如下( )方面的内容。

•A、健壮性和可读性•B、并行性•C、正确性•D、时空复杂度正确答案：B 我的答案：B得分：1.2分答案解析：4对于关键字序列(7,34,77,25,64,49,20,14)进行散列存储时,若选用H(K)=K%7作为散列函数,则散列地址为0的元素有( )个。

•A、1•B、2•C、3•D、4正确答案：D 我的答案：得分：0.0分答案解析：5该二叉树有( )个叶子。

•A、3•B、2•C、5•D、4正确答案：A 我的答案：A得分：1.2分答案解析：6从二叉搜索树中查找一个元素时,其时间复杂度大致为( )。

•A、O(n)•B、O(1)•C、O(log2n)•D、O(n2)正确答案：C 我的答案：C得分：1.2分答案解析：7数据的基本单位是( )。

•A、数据项•B、数据类型•C、数据元素•D、数据变量正确答案：A 我的答案：A得分：1.2分答案解析：8设有6个结点的无向图,该图至少应有( )条边才能确保是一个连通图。

•A、5•B、6•C、7•D、8正确答案：A 我的答案：A得分：1.2分答案解析：9对n个记录进行堆排序,所需要的辅助存储空间为( )。

•A、O(1og2n)•B、O(n)•C、O(1)•D、O(n2)正确答案：C 我的答案：C得分：1.2分答案解析：10设有一个二维数组A[m][n],假设A[0][0]存放位置在644,A[2][2]存放位置在676,每个元素占一个空间,则A[3][3]存放位置在( )。

四川大学期末考试试题（2007-2008学年第1学期）课程号：课程名称：数据结构与算法分析（A卷）任课教师：适用专业年级：06级软件工程学号：姓名：（1）An algorithm must be or do all of the following EXCEPT:a) correctb) composed of concrete stepsc) ambiguousd) composed of a finite number of steps（2）For set P, the notation |P| indicatesa) The number of elements in P. b) The inverse of P.c) The powerset of P. d) None of the above.（3）Pick the quadratic growth rate.a) 5n b) 20 log nc) 2n^2 d) 2^n（4）For set P, the notation |P| indicatesa) The number of elements in P.b) The inverse of P.c) The powerset of P.d) None of the above.（5）Huffman coding provides the optimal coding when:a) The messages are in English.b) The messages are binary numbers.c) The frequency of occurrence for a letter is independent of its context within the message.d) Never.（6）A sorting algorithm is stable if it:a) Works for all inputs.b) Does not change the relative ordering of records with identical key values.c) Always sorts in the same amount of time (within a constant factor) for a given input size. （7）Here is a series of C++ statements using the list ADT in the book.L1.append(10);L1.append(20);L1.append(15);If these statements are applied to an empty list, the result will looklike:a) < 10 20 15 >b) < | 10 20 15 >c) < 10 20 15 | >d) < 15 20 10 >e) < | 15 20 10 >f) < 15 20 10 | >（8）An entry-sequenced file stores records sorted by:a) Primary key value. b) Secondary key value.c) Order of arrival. d) Frequency of access.（9）Breadth-first search is best implemented using:a) A stack or recursion. b) A queue.c) A tree.（10）A recurrence relation is often used to model programs witha) for loops. b) branch control like "if" statements.c) recursive calls. d) None of the above.2．（10 scores）Assume a list has the following configuration:<| 6, 28, 16, 8, 9>Write a series of C++ statements using the List ADT as follows to delete the element with value 16.// List abstract classtemplate <class Elem> class List {public:// Reinitialize the list. The client is responsible for// reclaiming the storage used by the list elements. virtual void clear() = 0;// Insert an element at the front of the right partition.// Return true if successful, false if the list is full. virtual bool insert(const Elem&) = 0;// Append an element at the end of the right partition.// Return true if successful, false if the list is full. virtual bool append(const Elem&) = 0;// Remove the first element of right partition. Return// true if successful, false if right partition is empty.// The element removed is returned in the parameter. virtual bool remove(Elem&) = 0;// Place fence at list start, making left partition empty virtual void setStart() = 0;// Place fence at list end, making right partition empty virtual void setEnd() = 0;// Move fence one step left; no change if already at start virtual void prev() = 0;// Move fence one step right; no change if already at end virtual void next() = 0;// Return length of left partitionvirtual int leftLength() const = 0;// Return length of right partitionvirtual int rightLength() const = 0;// If pos or more elements are in the list, set the size// of left partition to pos and return true. Otherwise,// do nothing and return false.virtual bool setPos(int pos) = 0;// Return in first parameter the first element of the// right partition. Return true if successful, false// if the right partition is empty.virtual bool getV alue(Elem&) const = 0;// Print the contents of the listvirtual void print() const = 0;};3．（10 scores）Build the Huffman coding tree and determine the codes for the following set of letters and weights:a e i o u.1 3 5 7 84．（15 scores）Show the max-heap that results from running buildHeap on the following values stored in an array:10 5 12 3 2 1 8 7 9 45．（15 scores）When implementation Insertion Sort, a binary search could be used to locate the position within the first i – 1 elememts of the array into which element i should be inserted. How would this affect the number of comparisons required? How would using such a binary search affect the asymptotic running time for Insertion Sort?6．（15 scores）// Binary tree node abstract classtemplate <class Elem> class BinNode {public:// Return the node's elementvirtual Elem& val() = 0;// Set the node's elementvirtual void setV al(const Elem&) = 0;// Return the node's left childvirtual BinNode* left() const = 0;// Set the node's left childvirtual void setLeft(BinNode*) = 0;// Return the node's right childvirtual BinNode* right() const = 0;// Set the node's right childvirtual void setRight(BinNode*) = 0;// Return true iff the node is a leafvirtual bool isLeaf() = 0;};Write a recursive function that returns the height of a binary true..7．（15 scores）List the order in which the edges of the following graph are visited when running Prim’s MST algorithm starting3at V ertex 3. Show the final MST.。

_______________________________ 少年易学老难成，一寸光阴不可轻-百度文库一Chapter 1 Data Structures and Algorithms: Instructor's CD questions1.The primary purpose of most computer programs isa)to perform a mathematical calculation.*b) to store and retrieve information.c)to sort a collection of records.d)all of the above.e)none of the above.2.An integer is aa)) simple typeb)aggregate typec)composite typed)a and be)none of the above3.A payroll records is aa)simple typeb)aggregate typec)composite type*d) a and b e) none of the above4.Which of the following should NOT be viewed as an ADT?a)listb)integerc)array*d) none of the above5.A mathematical function is most like a*a) Problemb)Algorithmc)Program6.An algorithm must be or do all of the following EXCEPT:a)correctb)composed of concrete steps*c) ambiguousd)composed of a finite number of stepse)terminate7.A solution is efficient ifa.it solves a problem within the require resource constraints.b.it solves a problem within human reaction time.1_______________________________ 少年易学老难成，一寸光阴不可轻-百度文库_______ c.it solves a problem faster than other known solutions.d.a and b.*e. a and c.f. b and c.8.An array isa)A contiguous block of memory locations where each memory location storesa fixed-length data item.b)An ADT composed of a homogeneous collection of data items, each data item identified by a particular number.c)a set of integer values.*d) a and b.e)a and c.f)b and c.9.Order the following steps to selecting a data structure to solve a problem.(1)Determine the basic operations to be supported.(2)Quantify the resource constraints for each operation.(3)Select the data structure that best meets these requirements.(4)Analyze the problem to determine the resource constraints that anysolution must meet.a)(1, 2, 3, 4)b)(2, 3, 1, 4)c)(2, 1, 3, 4)*d) (1, 2, 4, 3)e) (1, 4, 3, 2)10.Searching for all those records in a database with key value between 10 and 100 is known as:a) An exact match query.*b) A range query.c)A sequential search.d)A binary search.Chapter 2 Mathematical Preliminaries: Instructor's CD questions1.A set has the following properties:a)May have duplicates, element have a position.b)May have duplicates, elements do not have a position.c)May not have duplicates, elements have a position.*d) May not have duplicates, elements do not have a position._______________________________ 少年易学老难成，一寸光阴不可轻-百度文库2.A sequence has the following properties:a)) May have duplicates, element have a position.b)May have duplicates, elements do not have a position.c)May not have duplicates, elements have a position.d)May not have duplicates, elements do not have a position.3.For set F, the notation |P| indicatesa)) The number of elements in Pb)The inverse of Pc)The powerset of F.d)None of the above.4.Assume that P contains n elements. The number of sets in the powerset of P isa)nb)n A2*c) 2A nd)2A n - 1e) 2A n + 15.If a sequence has n values, then the number of permutations for that sequence will bea)nb)n A2c)n A2 - 1d)2A n*e) n!6.If R is a binary relation over set S, then R is reflexive if*a) aRa for all a in S.b)whenever aRb, then bRa, for all a, b in S.c)whenever aRb and bRa, then a = b, for all a, b in S.d)whenever aRb and aRc, then aRc, for all a, b, c in S.7.If R is a binary relation over set S, then R is transitive ifa)aRa for all a in S.b)whenever aRb, then bRa, for all a, b in S.c)whenever aRb and bRa, then a = b, for all a, b in S.*d) whenever aRb and aRc, then aRc, for all a, b, c in S.8.R is an equivalence relation on set S if it isa)) reflexive, symmetric, transitive.b)reflexive, antisymmetric, transitive.c)symmetric, transitive.少年易学老难成，一寸光阴不可轻-百度文库d)antisymmetric, transitive.e)irreflexive, symmetric, transitive.f)irreflexive, antisymmetric, transitive.9.For the powerset of integers, the subset operation defines *a) a partial order.b)a total order.c)a transitive order.d)none of the above.10.log nm is equal toa) n + m*b) log n + log mc)m log nd)log n - log m11.A close-form solution isa) an analysis for a program.*b) an equation that directly computes the value of a summation.c) a complete solution for a problem.12.Mathematical induction is most likea) iteration.*b) recursion.c)branching.d)divide and conquer.13.A recurrence relation is often used to model programs witha)for loops.b)branch control like "if" statements.*c) recursive calls.d) function calls.14.Which of the following is not a good proof technique.a) proof by contradiction.*b) proof by example.c) proof by mathematical induction.15.We can use mathematical induction to:a) Find a closed-form solution for a summation.*b) Verify a proposed closed-form solution for a summation.c) Both find and verify a closed-form solution for a summation._______________________________ 少年易学老难成，一寸光阴不可轻-百度文库一Chapter 3 Algorithm Analysis: Instructor's CD questions1.A growth rate applies to:a)the time taken by an algorithm in the average case.b)the time taken by an algorithm as the input size grows.c)the space taken by an algorithm in the average case.d)the space taken by an algorithm as the input size grows.e)any resource you wish to measure for an algorithm in the average case.*f) any resource you wish to measure for an algorithm as the input size grows.2.Pick the growth rate that corresponds to the most efficient algorithm as n gets large:a) 5n*b) 20 log nc)2nA2d)2A n3.Pick the growth rate that corresponds to the most efficient algorithm when n =4.a)5nb)20 log nc)2nA2*d)2A n4.Pick the quadratic growth rate.a)5nb)20 log n*c) 2nA2d) 2An5.Asymptotic analysis refers to:a) The cost of an algorithm in its best, worst, or average case.*b) The growth in cost of an algorithm as the input size grows towards infinity.c)The size of a data structure.d)The cost of an algorithm for small input sizes6.For an air traffic control system, the most important metric is:a)The best-case upper bound.b)The average-case upper bound.c)) The worst-case upper bound.d)The best-case lower bound._______________________________ 少年易学老难成，一寸光阴不可轻-百度文库__________e)The average-case lower bound.f)The worst-case lower bound.7.When we wish to describe the upper bound for a problem we use:a)) The upper bound of the best algorithm we know.b)The lower bound of the best algorithm we know.c)We can't talk about the upper bound of a problem because there can alwaysbe an arbitrarily slow algorithm.8.When we describe the lower bound for a problem we use:a)The upper bound for the best algorithm we know.b)the lower bound for the best algorithm we know.c)The smallest upper bound that we can prove for the best algorithm that could possibly exist.*d) The greatest lower bound that we can prove for the best algorithm that could possibly exist.9.When the upper and lower bounds for an algorithm are the same, we use:a)big-Oh notation.b)big-Omega notation.*c) Theta notation.d)asymptotic analysis.e)Average case analysis.f)Worst case analysis.10. When performing asymptotic analysis, we can ignore constants and low order terms because:*a) We are measuring the growth rate as the input size gets large.b)We are only interested in small input sizes.c)We are studying the worst case behavior.d)We only need an approximation.11.The best case for an algorithm refers to:a) The smallest possible input size.*b) The specific input instance of a given size that gives the lowest cost.c)The largest possible input size that meets the required growth rate.d)The specific input instance of a given size that gives the greatest cost.12.For any algorithm:a)) The upper and lower bounds always meet, but we might not know what they are.少年易学老难成，一寸光阴不可轻-百度文库b)The upper and lower bounds might or might not meet.c)We can always determine the upper bound, but might not be able to determine the lower bound.d)We can always determine the lower bound, but might not be able to determine the upper bound.13.If an algorithm is Theta(f(n)) in the average case, then it is: a) Omega(f(n)) in the best case.*b) Omega(f(n)) in the worst case.c) O(f(n)) in the worst case.14.For the purpose of performing algorithm analysis, an important property ofa basic operation is that:a)It be fast.b)It be slow enough to measure.c)Its cost does depend on the value of its operands.*d) Its cost does not depend on the value of its operands.15.For sequential search,a) The best, average, and worst cases are asymptotically the same.*b) The best case is asymptotically better than the average and worst cases.c)The best and average cases are asymptotically better than the worst case.d)The best case is asymptotically better than the average case, and the average case is asymptotically better than the worst case.Chapter 4 Lists, Stacks and Queues: Instructor's CD questions1.An ordered list is one in which:a) The element values are in sorted order.*b) Each element a position within the list.2.An ordered list is most like a:a)set.b)bag.c)) sequence.3.As compared to the linked list implementation for lists, the array-based listimplementation requires:a)More spaceb)Less space*c) More or less space depending on how many elements are in the list._______________________________ 少年易学老难成，一寸光阴不可轻-百度文库4.Here is a series of C++ statements using the list ADT in the book.L1.append(10);L1.append(20);L1.append(15);If these statements are applied to an empty list, the result will look like:a)< 10 20 15 >*b) < | 10 20 15 >c)< 10 20 15 | >d)< 15 20 10 >e)< | 15 20 10 >f)< 15 20 10 | >5.When comparing the array-based and linked implementations, the array-based implementation has:a)) faster direct access to elements by position, but slower insert/delete from the current position.b)slower direct access to elements by position, but faster insert/delete from the current position.c)both faster direct access to elements by position, and faster insert/delete from the current position.d)both slower direct access to elements by position, and slower insert/delete from the current position.6.For a list of length n, the linked-list implementation's prev function requiresworst-case time:a)O(1).b)O(log n).*c) O(n).d) O(n A2).7.Finding the element in an array-based list with a given key value requiresworst case time:a)O(1).b)O(log n).*c) O(n).d) O(n A2).8.In the linked-list implementation presented in the book, a header node isused:*a) To simplify special cases._______________________________ 少年易学老难成，一寸光阴不可轻-百度文库一b)Because the insert and delete routines won't work correctly without it.c)Because there would be no other way to make the current pointer indicatethe first element on the list.9.When a pointer requires 4 bytes and a data element requires 4 bytes, thelinked list implementation requires less space than the array-based list implementation when the array would be:a)less than 1/4 full.b)less than 1/3 full.*c) less than half full.d)less than 第full.e)less than 34 fullf)never.10.When a pointer requires 4 bytes and a data element requires 12 bytes, thelinked list implementation requires less space than the array-based list implementation when the array would be:a)) less than 1/4 full.b)less than 1/3 full.c)less than half full.d)less than 2/3 full.e)less than 34 fullf)never.11.When we say that a list implementation enforces homogeneity, we meanthat:a) All list elements have the same size.*b) All list elements have the same type.c) All list elements appear in sort order.12.When comparing the doubly and singly linked list implementations, we findthat the doubly linked list implementation*a) Saves time on some operations at the expense of additional space.b)Saves neither time nor space, but is easier to implement.c)Saves neither time nor space, and is also harder to implement.13. We use a comparator function in the Dictionary class ADT:a)to simplify implementation.*b) to increase the opportunity for code reuse.c) to improve asymptotic efficiency of some functions.14.All operations on a stack can be implemented in constant time except:少年易学老难成，一寸光阴不可轻-百度文库a) Pushb)Popc)The implementor's choice of push or pop (they cannot both be implementedin constant time).*d) None of the above.15.Recursion is generally implemented usinga) A sorted list.*b) A stack.c) A queue.Chapter 5 Binary Trees: Instructor's CD questions1.The height of a binary tree is:a)The height of the deepest node.b)The depth of the deepest node.*c) One more than the depth of the deepest node.2.A full binary tree is one in which:*a) Every internal node has two non-empty children.b) all of the levels, except possibly the bottom level, are filled.3.The relationship between a full and a complete binary tree is:a)Every complete binary tree is full.b)Every full binary tree is complete.*c) None of the above.4.The Full Binary Tree Theorem states that:a)) The number of leaves in a non-empty full binary tree is one more than the number of internal nodes.b)The number of leaves in a non-empty full binary tree is one less than the number of internal nodes.c)The number of leaves in a non-empty full binary tree is one half of the number of internal nodes.d)The number of internal nodes in a non-empty full binary tree is one half of the number of leaves.5.The correct traversal to use on a BST to visit the nodes in sorted order is:a) Preorder traversal.*b) Inorder traversal.c) Postorder traversal.6. When every node of a full binary tree stores a 4-byte data field,10少年易学老难成，一寸光阴不可轻-百度文库two 4-byte child pointers, and a 4-byte parent pointer, theoverhead fraction is approximately:a)one quarter.b)one third.c)one half.d)two thirds.*e) three quarters.f) none of the above.7.When every node of a full binary tree stores an 8-byte data field and two 4-byte child pointers, the overhead fraction is approximately:a)one quarter.b)one third.*c) one half.d)two thirds.e)three quarters.f)none of the above.8.When every node of a full binary tree stores a 4-byte data field and theinternal nodes store two 4-byte child pointers, the overhead fraction is approximately:a)one quarter.b)one third.*c) one half.d)two thirds.e)three quarters.f)none of the above.9.If a node is at position r in the array implementation for a complete binarytree, then its parent is at:a)) (r - 1)/2 if r > 0b)2r + 1 if (2r + 1) < nc)2r + 2 if (2r + 2) < nd)r - 1 if r is evene)r + 1 if r is odd.10.If a node is at position r in the array implementation for a complete binarytree, then its right child is at:a)(r - 1)/2 if r > 0b)2r + 1 if (2r + 1) < n*c) 2r + 2 if (2r + 2) < nd)r - 1 if r is evene)r + 1 if r is odd.11_______________________________ 少年易学老难成，一寸光阴不可轻-百度文库—11.Assume a BST is implemented so that all nodes in the left subtree of agiven node have values less than that node, and all nodes in the rightsubtree have values greater than or equal to that node. Whenimplementing the delete routine, we must select as its replacement:a) The greatest value from the left subtree.*b) The least value from the right subtree.c) Either of the above.12.Which of the following is a true statement:a)In a BST, the left child of any node is less than the right child, and in a heap, the left child of any node is less than the right child.*b) In a BST, the left child of any node is less than the right child, but in a heap, the left child of any node could be less than or greater than the right child.c)In a BST, the left child of any node could be less or greater than the right child, but in a heap, the left child of any node must be less than the right child.d)In both a BST and a heap, the left child of any node could be either less than or greater than the right child.13.When implementing heaps and BSTs, which is the best answer?a)The time to build a BST of n nodes is O(n log n), and the time to build a heap of n nodes is O(n log n).b)The time to build a BST of n nodes is O(n), and the time to build a heap of n nodes is O(n log n).*c) The time to build a BST of n nodes is O(n log n), and the time to build a heap of n nodes is O(n).d) The time to build a BST of n nodes is O(n), and the time to build a heap of n nodes is O(n).14.The Huffman coding tree works best when the frequencies for letters area) Roughly the same for all letters.*b) Skewed so that there is a great difference in relative frequencies for various letters.15.Huffman coding provides the optimal coding when:a)The messages are in English.b)The messages are binary numbers.*c) The frequency of occurrence for a letter is independent of its context within the message.d) Never.12_______________________________ 少年易学老难成，一寸光阴不可轻-百度文库一Chapter 6 Binary Trees: Instructor's CD questions1.The primary ADT access functions used to traverse a general tree are: a) left child and right siblingb) left child and right child*c) leftmost child and right siblingd) leftmost child and next child2.The tree traversal that makes the least sense for a general treeis:a) preorder traversal*b) inorder traversalc) postorder traversal3.The primary access function used to navigate the general tree when performing UNION/FIND is:a)left childb)leftmost childc)right childd)right sibling*e) parent4.When using the weighted union rule for merging disjoint sets, the maximum depth for any node in a tree of size n will be:a) nearly constant*b) log nc)nd)n log ne)n A25.We use the parent pointer representation for general trees to solve which problem?a)Shortest pathsb)General tree traversal*c) Equivalence classesd) Exact-match query6. When using path compression along with the weighted union rule for merging disjoint sets, the average cost for any UNION or FIND operation in a tree of size n will be:*a) nearly constantb)log nc)nd)n log n13_______________________________ 少年易学老难成，一寸光阴不可轻-百度文库一7.The most space efficient representation for general trees will typically be:a) List of children*b) Left-child/right siblingc) A K-ary tree.8.The easiest way to represent a general tree is to:a) convert to a list.*b) convert to a binary tree.c) convert to a graph.9.As K gets bigger, the ratio of internal nodes to leaf nodes:a)) Gets smaller.b)Stays the same.c)Gets bigger.d)Cannot be determined, since it depends on the particular configuration of the tree.10.A sequential tree representation is best used for:*a) Archiving the tree to disk.b)Use in dynamic in-memory applications.c)Encryption algorithms.d)It is never better than a dynamic representation.Chapter 7 Internal Sorting: Instructor's CD questions1.A sorting algorithm is stable if it:a) Works for all inputs.*b) Does not change the relative ordering of records with identical key values.c) Always sorts in the same amount of time (within a constant factor) for a given input size.2.Which sorting algorithm does not have any practical use?a) Insertion sort.*b) Bubble sort.c)Quicksort.d)Radix Sort.e)a and b.3.When sorting n records, Insertion sort has best-case cost:a)O(log n).14_______________________________ 少年易学老难成，一寸光阴不可轻-百度文库*b) O(n).c)O(n log n).e)O(n!)f)None of the above.4.When sorting n records, Insertion sort has worst-case cost:a)O(log n).b)O(n).c)O(n log n).*d) O(n A2)e)O(n!)f)None of the above.5.When sorting n records, Quicksort has worst-case cost:a)O(log n).b)O(n).c)O(n log n).*d) O(n A2)e)O(n!)f)None of the above.6.When sorting n records, Quicksort has average-case cost:a)O(log n).b)O(n).c)) O(n log n).d)O(n A2)e)O(n!)f)None of the above.7.When sorting n records, Mergesort has worst-case cost:a)O(log n).b)O(n).*c) O(n log n).d)O(n A2)e)O(n!)f)None of the above.8.When sorting n records, Radix sort has worst-case cost:a)O(log n).b)O(n).c)O(n log n).d)O(n A2)e)O(n!)15少年易学老难成，一寸光阴不可轻-百度文库*f) None of the above.9.When sorting n records with distinct keys, Radix sort has a lower bound of:a)Omega(log n).b)Omega(n).*c) Omega(n log n).d)Omega(n A2)e)Omega(n!)f)None of the above.10.Any sort that can only swap adjacent records as an average case lower bound of:a)Omega(log n).b)Omega(n).c)Omega(n log n).*d) Omega(n A2)e)Omega(n!)f)None of the above.11.The number of permutations of size n is:a)O(log n).b)O(n).c)O(n log n).d)O(n A2)*e) O(n!)f)None of the above.12.When sorting n records, Selection sort will perform how many swaps in the worst case?a) O(log n).*b) O(n).c)O(n log n).d)O(n A2)e)O(n!)f)None of the above.13.Shellsort takes advantage of the best-case behavior of which sort?*a) Insertion sortb)Bubble sortc)Selection sortd)Shellsorte)Quicksortf)Radix sort16_______________________________ 少年易学老难成，一寸光阴不可轻-百度文库_______________14.A poor result from which step causes the worst-case behavior for Quicksort?*a) Selecting the pivotb)Partitioning the listc)The recursive call15.In the worst case, the very best that a sorting algorithm can do when sorting n records is:a)O(log n).b)O(n).*c) O(n log n).d)O(n A2)e)O(n!)f)None of the above.Chapter 8 File Processing and External Sorting: Instructor's CD questions1.As compared to the time required to access one unit of data frommain memory, accessing one unit of data from disk is:a)10 times faster.b)1000 times faster.c)1,000,000 time faster.d)10 times slower.e)1000 times slower.*f) 1,000,000 times slower.2.The most effective way to reduce the time required by a disk-based program is to:a) Improve the basic operations.*b) Minimize the number of disk accesses.c)Eliminate the recursive calls.d)Reduce main memory use.3.The basic unit of I/O when accessing a disk drive is:a)A byte.*b) A sector.c)A cluster.d)A track.e)An extent.4.The basic unit for disk allocation under DOS or Windows is:a)A byte.b)A sector.*c) A cluster.17少年易学老难成，一寸光阴不可轻-百度文库d) A track.e) An extent.5.The most time-consuming part of a random access to disk is usually: *a) The seek.b)The rotational delay.c)The time for the data to move under the I/O head.6.The simplest and most commonly used buffer pool replacement strategy is:a)First in/First out.b)Least Frequently Used.*c) Least Recently Used.7.The C++ programmer's view of a disk file is most like:a)) An array.b)A list.c)A tree.d)A heap.8.In external sorting, a run is:a)) A sorted sub-section for a list of records.b)One pass through a file being sorted.c)The external sorting process itself.9.The sorting algorithm used as a model for most external sorting algorithms is:a)Insertion sort.b)Quicksort.*c) Mergesort.d) Radix Sort.10.Assume that we wish to sort ten million records each 10 bytes long (for a total file size of 100MB of space). We have working memory of size 1MB, broken into 1024 1K blocks. Using replacement selection and multiway merging, we can expect to sort this file using how many passes through the file?a)About 26 or 27 (that is, log n).b)About 10.c)4.*d) 2.Chapter 9 Searching: Instructor's CD questions18少年易学老难成，一寸光阴不可轻-百度文库1.Which is generally more expensive?a) A successful search.*b) An unsuccessful search.2.When properly implemented, which search method is generally the most efficient for exact-match queries?a)Sequential search.b)Binary search.c)Dictionary search.d)Search in self-organizing lists*e) Hashing3.Self-organizing lists attempt to keep the list sorted by:a) value*b) frequency of record accessc) size of record4.The 80/20 rule indicates that:a) 80% of searches in typical databases are successful and 20% are not.*b) 80% of the searches in typical databases are to 20% of the records.c) 80% of records in typical databases are of value, 20% are not.5.Which of the following is often implemented using a self-organizing list? *a) Buffer pool.b)Linked list.c)Priority queue.6.A hash function must:a)) Return a valid position within the hash table.b)Give equal probability for selecting an slot in the hash table.c)Return an empty slot in the hash table.7.A good hash function will:a)Use the high-order bits of the key value.b)Use the middle bits of the key value.c)Use the low-order bits of the key value.*d) Make use of all bits in the key value.8.A collision resolution technique that places all records directlyinto the hash table is called:a)Open hashing.b)Separate chaining.*c) Closed hashing.d) Probe function.19少年易学老难成，一寸光阴不可轻-百度文库9.Hashing is most appropriate for:a)In-memory applications.b)Disk-based applications.*c) Either in-memory or disk-based applications.10.Hashing is most appropriate for:a)) Range queries.b)Exact-match queries.c)Minimum/maximium value queries.11.In hashing, the operation that will likely require more record accesses is: *a) insertb) deleteChapter 10 Indexing: Instructor's CD questions1.An entry-sequenced file stores records sorted by:a)Primary key value.b)Secondary key value.*c) Order of arrival.d) Frequency of access.2.Indexing is:a) Random access to an array.*b) The process of associating a key with the location of a corresponding data record.c) Using a hash table.3.The primary key is:a)) A unique identifier for a record.b)The main search key used by users of the database.c)The first key in the index.4.Linear indexing is good for all EXCEPT:a)Range queries.b)Exact match queries.*c) Insertion/Deletion.d)In-memory applications.e)Disk-based applications.5.An inverted list provides access to a data record from its:a) Primary key.20______________________________ 少年易学老难成，一寸光阴不可轻-百度文库*b) Secondary key.c) Search key.6.ISAM degrades over time because:a) Delete operations empty out some cylinders.*b) Insert operations cause some cylinders to overflow.c) Searches disrupt the data structure.7.Tree indexing methods are meant to overcome what deficiency in hashing? *a) Inability to handle range queries.。

川大软件数据结构选择题库Chapter 1 Data Structures and Algorithms: Instructor's CD questions1. The primary purpose of most computer programs isa) to perform a mathematical calculation.*b) to store and retrieve information.c) to sort a collection of records.d) all of the above.e) none of the above.2. An integer is a*a) simple typeb) aggregate typec) composite typed) a and be) none of the above3. A payroll records is aa) simple typeb) aggregate typec) composite type*d) a and be) none of the above4. Which of the following should NOT be viewed as an ADT?a) listb) integerc) array*d) none of the above5. A mathematical function is most like a*a) Problemb) Algorithmc) Program6. An algorithm must be or do all of the following EXCEPT:a) correctb) composed of concrete steps*c) ambiguousd) composed of a finite number of stepse) terminate7. A solution is efficient ifa. it solves a problem within the require resource constraints.b. it solves a problem within human reaction time.c. it solves a problem faster than other known solutions.d. a and b.*e. a and c.f. b and c.8. An array isa) A contiguous block of memory locations where each memory location stores a fixed-length data item.b) An ADT composed of a homogeneous collection of data items, each data item identified by a particular number.c) a set of integer values.*d) a and b.e) a and c.f) b and c.9. Order the following steps to selecting a data structure to solve a problem.(1) Determine the basic operations to be supported.(2) Quantify the resource constraints for each operation.(3) Select the data structure that best meets these requirements.(4) Analyze the problem to determine the resourceconstraints that anysolution must meet.a) (1, 2, 3, 4)b) (2, 3, 1, 4)c) (2, 1, 3, 4)*d) (1, 2, 4, 3)e) (1, 4, 3, 2)10. Searching for all those records in a database with key value between 10 and 100 is known as:a) An exact match query.*b) A range query.c) A sequential search.d) A binary search.Chapter 2 Mathematical Preliminaries: Instructor's CD questions1. A set has the following properties:a) May have duplicates, element have a position.b) May have duplicates, elements do not have a position.c) May not have duplicates, elements have a position.*d) May not have duplicates, elements do not have a position.2. A sequence has the following properties:*a) May have duplicates, element have a position.b) May have duplicates, elements do not have a position.c) May not have duplicates, elements have a position.d) May not have duplicates, elements do not have a position.3. For set P, the notation |P| indicates*a) The number of elements in P.b) The inverse of P.c) The powerset of P.d) None of the above.4. Assume that P contains n elements. The number of sets in the powerset of P isa) nb) n^2*c) 2^nd) 2^n - 1e) 2^n + 15. If a sequence has n values, then the number of permutations for that sequence will bea) nb) n^2c) n^2 - 1d) 2^n*e) n!6. If R is a binary relation over set S, then R is reflexive if*a) aRa for all a in S.b) whenever aRb, then bRa, for all a, b in S.c) whenever aRb and bRa, then a = b, for all a, b in S.d) whenever aRb and aRc, then aRc, for all a, b, c in S.7. If R is a binary relation over set S, then R is transitive ifa) aRa for all a in S.b) whenever aRb, then bRa, for all a, b in S.c) whenever aRb and bRa, then a = b, for all a, b in S.*d) whenever aRb and aRc, then aRc, for all a, b, c in S.8. R is an equivalence relation on set S if it is*a) reflexive, symmetric, transitive.b) reflexive, antisymmetric, transitive.c) symmetric, transitive.d) antisymmetric, transitive.e) irreflexive, symmetric, transitive.f) irreflexive, antisymmetric, transitive.9. For the powerset of integers, the subset operation defines*a) a partial order.b) a total order.c) a transitive order.d) none of the above.10. log nm is equal toa) n + m*b) log n + log mc) m log nd) log n - log m11. A close-form solution isa) an analysis for a program.*b) an equation that directly computes the value of a summation.c) a complete solution for a problem.12. Mathematical induction is most likea) iteration.*b) recursion.c) branching.d) divide and conquer.13. A recurrence relation is often used to model programs witha) for loops.b) branch control like "if" statements.*c) recursive calls.d) function calls.14. Which of the following is not a good proof technique.a) proof by contradiction.*b) proof by example.c) proof by mathematical induction.15. We can use mathematical induction to:a) Find a closed-form solution for a summation.*b) Verify a proposed closed-form solution for a summation.c) Both find and verify a closed-form solution for a summation.Chapter 3 Algorithm Analysis: Instructor's CD questions1. A growth rate applies to:a) the time taken by an algorithm in the average case.b) the time taken by an algorithm as the input size grows.c) the space taken by an algorithm in the average case.d) the space taken by an algorithm as the input size grows.e) any resource you wish to measure for an algorithm in the averagecase.*f) any resource you wish to measure for an algorithm as the input size grows.2. Pick the growth rate that corresponds to the most efficient algorithm as n gets large:a) 5n*b) 20 log nc) 2n^2d) 2^n3. Pick the growth rate that corresponds to the most efficient algorithm when n =4.a) 5nb) 20 log nc) 2n^2*d) 2^n4. Pick the quadratic growth rate.a) 5nb) 20 log n*c) 2n^2d) 2^n5. Asymptotic analysis refers to:a) The cost of an algorithm in its best, worst, or average case.*b) The growth in cost of an algorithm as the input size grows towards infinity.c) The size of a data structure.d) The cost of an algorithm for small input sizes6. For an air traffic control system, the most important metric is:a) The best-case upper bound.b) The average-case upper bound.*c) The worst-case upper bound.d) The best-case lower bound.e) The average-case lower bound.f) The worst-case lower bound.7. When we wish to describe the upper bound for a problem we use:*a) The upper bound of the best algorithm we know.b) The lower bound of the best algorithm we know.c) We can't talk about the upper bound of a problem because there canalways be an arbitrarily slow algorithm.8. When we describe the lower bound for a problem we use:a) The upper bound for the best algorithm we know.b) the lower bound for the best algorithm we know.c) The smallest upper bound that we can prove for the bestalgorithmthat could possibly exist.*d) The greatest lower bound that we can prove for the best algorithm that could possibly exist.9. When the upper and lower bounds for an algorithm are the same, we use:a) big-Oh notation.b) big-Omega notation.*c) Theta notation.d) asymptotic analysis.e) Average case analysis.f) Worst case analysis.10. When performing asymptotic analysis, we can ignore constants and low order terms because:*a) We are measuring the growth rate as the input size gets large.b) We are only interested in small input sizes.c) We are studying the worst case behavior.d) We only need an approximation.11. The best case for an algorithm refers to:a) The smallest possible input size.*b) The specific input instance of a given size that gives the lowest cost.c) The largest possible input size that meets the required growth rate.d) The specific input instance of a given size that gives the greatestcost.12. For any algorithm:*a) The upper and lower bounds always meet, but we mightnot know what they are.b) The upper and lower bounds might or might not meet.c) We can always determine the upper bound, but might not be able to determine the lower bound.d) We can always determine the lower bound, but might not be able to determine the upper bound.13. If an algorithm is Theta(f(n)) in the average case, then it is:a) Omega(f(n)) in the best case.*b) Omega(f(n)) in the worst case.c) O(f(n)) in the worst case.14. For the purpose of performing algorithm analysis, an important property of a basic operation is that:a) It be fast.b) It be slow enough to measure.c) Its cost does depend on the value of its operands.*d) Its cost does not depend on the value of its operands.15. For sequential search,a) The best, average, and worst cases are asymptotically the same.*b) The best case is asymptotically better than the average and worst cases.c) The best and average cases are asymptotically better than the worst case.d) The best case is asymptotically better than the average case, and the average case is asymptotically better than the worst case.Chapter 4 Lists, Stacks and Queues: Instructor's CD questions1. An ordered list is one in which:a) The element values are in sorted order.*b) Each element a position within the list.2. An ordered list is most like a:a) set.b) bag.*c) sequence.3. As compared to the linked list implementation for lists, thearray-based list implementation requires:a) More spaceb) Less space*c) More or less space depending on how many elements are in the list.4. Here is a series of C++ statements using the list ADT in the book.L1.append(10);L1.append(20);L1.append(15);If these statements are applied to an empty list, the result will look like:a) < 10 20 15 >*b) < | 10 20 15 >c) < 10 20 15 | >d) < 15 20 10 >e) < | 15 20 10 >f) < 15 20 10 | >5. When comparing the array-based and linked implementations, the array-based implementation has: *a) faster direct access to elements by position,but slower insert/delete from the current position.b) slower direct access to elements by position,but faster insert/delete from the current position.c) both faster direct access to elements by position, and faster insert/delete from the current position.d) both slower direct access to elements by position, and slower insert/delete from the current position.6. For a list of length n, the linked-list implementation's prevfunction requires worst-case time:a) O(1).b) O(log n).*c) O(n).d) O(n^2).7. Finding the element in an array-based list with a given key valuerequires worst case time:a) O(1).b) O(log n).*c) O(n).d) O(n^2).8. In the linked-list implementation presented in the book, a headernode is used:*a) To simplify special cases.b) Because the insert and delete routines won't work correctly withoutit.c) Because there would be no other way to make the current pointerindicate the first element on the list.9. When a pointer requires 4 bytes and a data element requires 4bytes, the linked list implementation requires less space thanthe array-based list implementation when the array would be:a) less than 1/4 full.b) less than 1/3 full.*c) less than half full.d) less than 2/3 full.e) less than 3/4 fullf) never.10. When a pointer requires 4 bytes and a data element requires 12bytes, the linked list implementation requires less space than the array-based list implementation when the array would be: *a) less than 1/4 full.b) less than 1/3 full.c) less than half full.d) less than 2/3 full.e) less than 3/4 fullf) never.11. When we say that a list implementation enforces homogeneity, wemean that:a) All list elements have the same size.*b) All list elements have the same type.c) All list elements appear in sort order.12. When comparing the doubly and singly linked list implementations,we find that the doubly linked list implementation*a) Saves time on some operations at the expense of additional space.b) Saves neither time nor space, but is easier to implement.c) Saves neither time nor space, and is also harder toimplement.13. We use a comparator function in the Dictionary class ADT:a) to simplify implementation.*b) to increase the opportunity for code reuse.c) to improve asymptotic efficiency of some functions.14. All operations on a stack can be implemented in constant timeexcept:a) Pushb) Popc) The implementor's choice of push or pop (they cannot both beimplemented in constant time).*d) None of the above.15. Recursion is generally implemented usinga) A sorted list.*b) A stack.c) A queue.Chapter 5 Binary Trees: Instructor's CD questions1. The height of a binary tree is:a) The height of the deepest node.b) The depth of the deepest node.*c) One more than the depth of the deepest node.2. A full binary tree is one in which:*a) Every internal node has two non-empty children.b) all of the levels, except possibly the bottom level, are filled.3. The relationship between a full and a complete binary tree is:a) Every complete binary tree is full.b) Every full binary tree is complete.*c) None of the above.4. The Full Binary Tree Theorem states that:*a) The number of leaves in a non-empty full binary tree is one more than the number of internal nodes.b) The number of leaves in a non-empty full binary tree is one less than the number of internal nodes.c) The number of leaves in a non-empty full binary tree is one half of the number of internal nodes.d) The number of internal nodes in a non-empty full binary tree is one half of the number of leaves.5. The correct traversal to use on a BST to visit the nodes in sortedorder is:a) Preorder traversal.*b) Inorder traversal.c) Postorder traversal.6. When every node of a full binary tree stores a 4-byte data field,two 4-byte child pointers, and a 4-byte parent pointer, the overhead fraction is approximately:a) one quarter.b) one third.c) one half.d) two thirds.*e) three quarters.f) none of the above.7. When every node of a full binary tree stores an 8-byte data field andtwo 4-byte child pointers, the overhead fraction is approximately:a) one quarter.b) one third.*c) one half.d) two thirds.e) three quarters.f) none of the above.8. When every node of a full binary tree stores a 4-byte data fieldand the internal nodes store two 4-byte child pointers, the overhead fraction is approximately:a) one quarter.b) one third.*c) one half.d) two thirds.e) three quarters.f) none of the above.9. If a node is at position r in the array implementation for acomplete binary tree, then its parent is at:*a) (r - 1)/2 if r > 0b) 2r + 1 if (2r + 1) < nc) 2r + 2 if (2r + 2) < nd) r - 1 if r is evene) r + 1 if r is odd.10. If a node is at position r in the array implementation for acomplete binary tree, then its right child is at:a) (r - 1)/2 if r > 0b) 2r + 1 if (2r + 1) < n*c) 2r + 2 if (2r + 2) < nd) r - 1 if r is evene) r + 1 if r is odd.11. Assume a BST is implemented so that all nodes in the left subtreeof a given node have values less than that node, and all nodes in the right subtree have values greater than or equal to that node.When implementing the delete routine, we must select as its replacement:a) The greatest value from the left subtree.*b) The least value from the right subtree.c) Either of the above.12. Which of the following is a true statement:a) In a BST, the left child of any node is less than the right child,and in a heap, the left child of any node is less than the right child.*b) In a BST, the left child of any node is less than the right child,but in a heap, the left child of any node could be less than or greater than the right child.c) In a BST, the left child of any node could be less or greater than the right child, but in a heap, the left child of any node must beless than the right child.d) In both a BST and a heap, the left child of any node could be either less than or greater than the right child.13. When implementing heaps and BSTs, which is the best answer?a) The time to build a BST of n nodes is O(n log n), and the time to build a heap of n nodes is O(n log n).b) The time to build a BST of n nodes is O(n), and the time tobuild a heap of n nodes is O(n log n).*c) The time to build a BST of n nodes is O(n log n), and the time to build a heap of n nodes is O(n).d) The time to build a BST of n nodes is O(n), and the time tobuild a heap of n nodes is O(n).14. The Huffman coding tree works best when the frequencies forletters area) Roughly the same for all letters.*b) Skewed so that there is a great difference in relative frequencies for various letters.15. Huffman coding provides the optimal coding when:a) The messages are in English.b) The messages are binary numbers.*c) The frequency of occurrence for a letter is independent of its context within the message.d) Never.Chapter 6 Binary Trees: Instructor's CD questions1. The primary ADT access functions used to traverse a general tree are:a) left child and right siblingb) left child and right child*c) leftmost child and right siblingd) leftmost child and next child2. The tree traversal that makes the least sense for a general treeis:a) preorder traversal*b) inorder traversalc) postorder traversal3. The primary access function used to navigate the general tree when performing UNION/FIND is:a) left childb) leftmost childc) right childd) right sibling*e) parent4. When using the weighted union rule for merging disjoint sets, the maximum depth for any node in a tree of size n will be:a) nearly constant*b) log nc) nd) n log ne) n^25. We use the parent pointer representation for general trees to solve which problem?a) Shortest pathsb) General tree traversal*c) Equivalence classesd) Exact-match query6. When using path compression along with the weighted union rule for merging disjoint sets, the average cost for any UNION or FIND operation in a tree of size n will be:*a) nearly constantb) log nc) nd) n log n7. The most space efficient representation for general trees will typically be:a) List of children*b) Left-child/right siblingc) A K-ary tree.8. The easiest way to represent a general tree is to:a) convert to a list.*b) convert to a binary tree.c) convert to a graph.9. As K gets bigger, the ratio of internal nodes to leaf nodes:*a) Gets smaller.b) Stays the same.c) Gets bigger.d) Cannot be determined, since it depends on the particular configuration of the tree.10. A sequential tree representation is best used for:*a) Archiving the tree to disk.b) Use in dynamic in-memory applications.c) Encryption algorithms.d) It is never better than a dynamic representation.Chapter 7 Internal Sorting: Instructor's CD questions1. A sorting algorithm is stable if it:a) Works for all inputs.*b) Does not change the relative ordering of records with identical key values.c) Always sorts in the same amount of time (within a constant factor) for a given input size.2. Which sorting algorithm does not have any practical use?a) Insertion sort.*b) Bubble sort.c) Quicksort.d) Radix Sort.e) a and b.3. When sorting n records, Insertion sort has best-case cost:a) O(log n).c) O(n log n).d) O(n^2)e) O(n!)f) None of the above.4. When sorting n records, Insertion sort has worst-case cost:a) O(log n).b) O(n).c) O(n log n).*d) O(n^2)e) O(n!)f) None of the above.5. When sorting n records, Quicksort has worst-case cost:a) O(log n).b) O(n).c) O(n log n).*d) O(n^2)e) O(n!)f) None of the above.6. When sorting n records, Quicksort has average-case cost:a) O(log n).b) O(n).*c) O(n log n).d) O(n^2)e) O(n!)f) None of the above.7. When sorting n records, Mergesort has worst-case cost:a) O(log n).*c) O(n log n).d) O(n^2)e) O(n!)f) None of the above.8. When sorting n records, Radix sort has worst-case cost:a) O(log n).b) O(n).c) O(n log n).d) O(n^2)e) O(n!)*f) None of the above.9. When sorting n records with distinct keys, Radix sort has a lower bound of:a) Omega(log n).b) Omega(n).*c) Omega(n log n).d) Omega(n^2)e) Omega(n!)f) None of the above.10. Any sort that can only swap adjacent records as an average case lower bound of:a) Omega(log n).b) Omega(n).c) Omega(n log n).*d) Omega(n^2)e) Omega(n!)f) None of the above.11. The number of permutations of size n is:a) O(log n).c) O(n log n).d) O(n^2)*e) O(n!)f) None of the above.12. When sorting n records, Selection sort will perform how many swaps in the worst case?a) O(log n).*b) O(n).c) O(n log n).d) O(n^2)e) O(n!)f) None of the above.13. Shellsort takes advantage of the best-case behavior of which sort? *a) Insertion sortb) Bubble sortc) Selection sortd) Shellsorte) Quicksortf) Radix sort14. A poor result from which step causes the worst-case behavior for Quicksort? *a) Selecting the pivotb) Partitioning the listc) The recursive call15. In the worst case, the very best that a sorting algorithm can dowhen sorting n records is:a) O(log n).b) O(n).*c) O(n log n).e) O(n!)f) None of the above.Chapter 8 File Processing and External Sorting: Instructor's CD questions1. As compared to the time required to access one unit of data frommain memory, accessing one unit of data from disk is:a) 10 times faster.b) 1000 times faster.c) 1,000,000 time faster.d) 10 times slower.e) 1000 times slower.*f) 1,000,000 times slower.2. The most effective way to reduce the time required by a disk-based program is to:a) Improve the basic operations.*b) Minimize the number of disk accesses.c) Eliminate the recursive calls.d) Reduce main memory use.3. The basic unit of I/O when accessing a disk drive is:a) A byte.*b) A sector.c) A cluster.d) A track.e) An extent.4. The basic unit for disk allocation under DOS or Windows is:a) A byte.b) A sector.*c) A cluster.d) A track.e) An extent.5. The most time-consuming part of a random access to disk is usually: *a) The seek.b) The rotational delay.c) The time for the data to move under the I/O head.6. The simplest and most commonly used buffer pool replacement strategy is:a) First in/First out.b) Least Frequently Used.*c) Least Recently Used.7. The C++ programmer's view of a disk file is most like:*a) An array.b) A list.c) A tree.d) A heap.8. In external sorting, a run is:*a) A sorted sub-section for a list of records.b) One pass through a file being sorted.c) The external sorting process itself.9. The sorting algorithm used as a model for most external sorting algorithms is:a) Insertion sort.b) Quicksort.*c) Mergesort.d) Radix Sort.10. Assume that we wish to sort ten million records each 10 bytes long (for a total file size of 100MB of space). We have working memory of size 1MB, broken into 1024 1K blocks. Usingreplacement selection and multiway merging, we can expect to sort this file using how many passes through the file?a) About 26 or 27 (that is, log n).b) About 10.c) 4.*d) 2.Chapter 9 Searching: Instructor's CD questions1. Which is generally more expensive?a) A successful search.*b) An unsuccessful search.2. When properly implemented, which search method is generally the most efficient for exact-match queries?a) Sequential search.b) Binary search.c) Dictionary search.d) Search in self-organizing lists*e) Hashing3. Self-organizing lists attempt to keep the list sorted by:a) value*b) frequency of record accessc) size of record4. The 80/20 rule indicates that:a) 80% of searches in typical databases are successful and 20% are not.*b) 80% of the searches in typical databases are to 20% of the records. c) 80% of records in typical databases are of value, 20% are not.5. Which of the following is often implemented using a self-organizing list? *a) Buffer pool.b) Linked list.c) Priority queue.6. A hash function must:*a) Return a valid position within the hash table.b) Give equal probability for selecting an slot in the hash table.c) Return an empty slot in the hash table.7. A good hash function will:a) Use the high-order bits of the key value.b) Use the middle bits of the key value.c) Use the low-order bits of the key value.*d) Make use of all bits in the key value.8. A collision resolution technique that places all records directlyinto the hash table is called:a) Open hashing.b) Separate chaining.*c) Closed hashing.d) Probe function.。

四川大学期末考试试题（闭卷）（2009~2010学年第2学期）课程号： 311036030 课程名称：数据结构与算法（B卷）任课教师：孙界平杨秋辉张卫华适用专业年级：软件工程 2009级学号：姓名：考试须知四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行《四川大学考试工作管理办法》和《四川大学考场规则》。

有考试违纪作弊行为的，一律按照《四川大学学生考试违纪作弊处罚条例》进行处理。

四川大学各级各类考试的监考人员，必须严格执行《四川大学考试工作管理办法》、《四川大学考场规则》和《四川大学监考人员职责》。

有违反学校有关规定的，严格按照《四川大学教学事故认定及处理办法》进行处理。

题号一(30%) 二(10%) 三(15%) 四(20%) 五(25%) 卷面成绩得分阅卷时间注意事项：1. 请务必将本人所在学院、姓名、学号、任课教师姓名等信息准确填写在试题纸和添卷纸上；2. 请将答案全部填写在本试题纸上；3. 考试结束，请将试题纸、添卷纸和草稿纸一并交给监考老师。

一、单项选择题（本大题共15小题，每小题2分，共30分）提示：在每小题列评阅教师得分出的四个备选项中只有一个是符合题目要求的，请将其代码填写在答题纸上。

错选、多选或未选均无分。

1. A mathematical function is most like a ( A )(A) Problem(B) Algorithm(C) Program(D) Code2. A recurrence relation is often used to model programs with ( C )(A) for loops.(B) branch control like "if" statements.(C) recursive calls.(D) function calls.3. For an air traffic control system, the most important metric is: ( C )(A) The best-case upper bound.(B) The average-case upper bound.(C) The worst-case upper bound.(D) The best-case lower bound.4. For a list of length n, the linked-list implementation's prev() function requires worst-case time: ( C )(A) O(1).(B) O(log n).(C) O(n).(D) O(n2).5. Assume a BST is implemented so that all nodes in the left subtree of a given node have values less than that node, and all nodes in the right subtree have values greater than or equal to that node. When implementing the delete routine, we must select as its replacement: ( B )(A) The greatest value from the left subtree.(B) The least value from the right subtree.(C) Either of the above.(D) The root.6. The primary ADT access functions used to traverse a general tree are: ( C )(A) left child and right sibling(B) left child and right child(C) leftmost child and right sibling(D) leftmost child and next child7. A sorting algorithm is stable if it: ( B )(A) Works for all inputs.(B) Does not change the relative ordering of records with identical key values.(C) Always sorts in the same amount of time (within a constant factor) for a given input size.(D) Most efficient.8. When sorting n records, Quicksort has worst-case cost: ( D )(A) O(log n).(B) O(n).(C) O(n log n).(D) O(n2)9. The basic unit of I/O when accessing a disk drive is: ( B )(A) A byte.(B) A sector.(C) A cluster.(D) A track.10. The sorting algorithm used as a model for most external sorting algorithms is: ( C )(A) Insertion sort.(B) Quicksort.(C) Mergesort.(D) Radix Sort.11. Which of the following is often implemented using a self-organizing list? ( A )(A) Buffer pool.(B) Linked list.(C) Priority queue.(D) B-Tree12. An entry-sequenced file stores records sorted by: ( C )(A) Primary key value.(B) Secondary key value.(C) Order of arrival.(D) Frequency of access.13. The primary difference between a B-tree and a B+-tree is: ( A )(A) The B+-tree store records only at the leaf nodes.(B) The B+-tree has a higher branching factor.(C) The B+-tree is hight balanced.(D) The B+-tree is smaller.14. The goal of a topological sort is to: ( B )(A) Sort all of the graph vertices by value.(B) Sort all of the graph vertices so that each vertex is listed prior to any others that depend onit.(C) Sort all of the graph vertices by distance from the source vertex.(D) None of the above.15. Which is a good example of a greedy algorithm? ( B )(A) Floyd's all-pairs shortest path algorithm.(B) Prim's minimal-cost spanning tree algorithm.(C) Depth-first search.(D) T opological sorting.二、判断题（本大题共5小题，每小题2分，共10分）提示：正确打T，错误打F，评阅教师得分将其结果填写在答题纸上。

1、从逻辑上可以把数据结构分为（C）两大类。

A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2、以下数据结构中，哪一个是线性结构（ D）？A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串3、在下面的程序段中，对x的赋值语句的频度为（C）for (i=1;i<=n;i++)for (j=1;j<=n;i++)x=x+1;n) A． O(2n) B．O(n) C．O(n2) D．O(log24、下面关于线性表的叙述中，错误的是哪一个？（ B ）A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

5、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。

A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表6、静态链表中指针表示的是（ B）.A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址7、下面的叙述不正确的是（ BC）A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关8、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。

A. O(0)B. O(1)C. O(n)D. O(n2)9、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ B ）。

A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s;C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s;10、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ B ）A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL11、一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i （1<=i<=n）个元素是（ B）。