cs3460_ch9_shortest_path 美国高校《数据结构》(Data Structure)ppt课件,共9章,英文版

本文由ＦＵＫＡ２０１０贡献 ｐｄｆ文档可能在ＷＡＰ端浏览体验不佳。

建议您优先选择ＴＸＴ，或下载源文件到本机查看。

内容简介 《数据结构》（Ｃ　语言版）的第　１　章综述数据、数据结构和抽象数据类型等基本概念；第　２　章　至第　７　章从抽象数据类型的角度，分别讨论线性表、栈、队列、串、数组、广义表、树和二叉　树以及图等基本类型的数据结构及其应用；第　８　章综合介绍操作系统和编译程序中涉及的动态　存储管理的基本技术；第　９　章至第　１１　章讨论查找和排序，除了介绍各种实现方法之外，并着重　从时间上进行定性或定量的分析和比较；第　１２　章介绍常用的文件结构。

　《数据结构》　（Ｃ　语言版）的前半部分从抽象数据类型的角度讨论各种基本类型的数据结构及其　应用；后半部分主要讨论查找和排序的各种实现方法及其综合分析比较。

其内容和章节编排　１９９２　年　４　月出版的《数据结构》（第二版）基本一致，但在本书中更突出了抽象数据类型的概　念。

全书采用类　Ｃ　语言作为数据结构和算法的描述语言。

市场价：　￥　３０．００　卓越价：　￥　２２．５０　此商品可以享受免费送货 编辑推荐 《数据结构》（Ｃ　语言版）是为“数据结构”课程编写的教材，也可作为学习数据结构及其算法的　Ｃ　程序设计的参数教材。

　本书的前半部分从抽象数据类型的角度讨论各种基本类型的数据结构及其应用；　后半部分主要讨　论查找和排序的各种实现方法及其综合分析比较。

其内容和章节编排　１９９２　年　４　月出版的《数　据结构》（第二版）基本一致，但在本书中更突出了抽象数据类型的概念。

全书采用类　Ｃ　语言　作为数据结构和算法的描述语言。

　本书概念表述严谨，逻辑推理严密，语言精炼，用词达意，并有配套出版的《数据结构题集》　（Ｃ　语言版），便于教学，又便于自学。

　本书后附有光盘。

光盘内容可在　ＤＯＳ　环境下运行的以类　Ｃ　语言描述的“数据结构算法动态模拟　辅助教学软件，以及在　Ｗｉｎｄｏｗｓ　环境下运行的以类　ＰＡＳＣＡＬ　或类　Ｃ　两种语言描述的“数据结　构算法动态模拟辅助教学软件”。

《数据结构与算法分析》（C++第二版）【美】Clifford A.Shaffer著课后习题答案二5Binary Trees5.1 Consider a non-full binary tree. By definition, this tree must have some internalnode X with only one non-empty child. If we modify the tree to removeX, replacing it with its child, the modified tree will have a higher fraction ofnon-empty nodes since one non-empty node and one empty node have been removed.5.2 Use as the base case the tree of one leaf node. The number of degree-2 nodesis 0, and the number of leaves is 1. Thus, the theorem holds.For the induction hypothesis, assume the theorem is true for any tree withn − 1 nodes.For the induction step, consider a tree T with n nodes. Remove from the treeany leaf node, and call the resulting tree T. By the induction hypothesis, Thas one more leaf node than it has nodes of degree 2.Now, restore the leaf node that was removed to form T. There are twopossible cases.(1) If this leaf node is the only child of its parent in T, then the number ofnodes of degree 2 has not changed, nor has the number of leaf nodes. Thus,the theorem holds.(2) If this leaf node is the child of a node in T with degree 2, then that nodehas degree 1 in T. Thus, by restoring the leaf node we are adding one newleaf node and one new node of degree 2. Thus, the theorem holds.By mathematical induction, the theorem is correct.32335.3 Base Case: For the tree of one leaf node, I = 0, E = 0, n = 0, so thetheorem holds.Induction Hypothesis: The theorem holds for the full binary tree containingn internal nodes.Induction Step: Take an arbitrary tree (call it T) of n internal nodes. Selectsome internal node x from T that has two leaves, and remove those twoleaves. Call the resulting tree T’. Tree T’ is full and has n−1 internal nodes,so by the Induction Hypothesis E = I + 2(n − 1).Call the depth of node x as d. Restore the two children of x, each at leveld+1. We have nowadded d to I since x is now once again an internal node.We have now added 2(d + 1) − d = d + 2 to E since we added the two leafnodes, but lost the contribution of x to E. Thus, if before the addition we had E = I + 2(n − 1) (by the induction hypothesis), then after the addition we have E + d = I + d + 2 + 2(n − 1) or E = I + 2n which is correct. Thus,by the principle of mathematical induction, the theorem is correct.5.4 (a) template <class Elem>void inorder(BinNode<Elem>* subroot) {if (subroot == NULL) return; // Empty, do nothingpreorder(subroot->left());visit(subroot); // Perform desired actionpreorder(subroot->right());}(b) template <class Elem>void postorder(BinNode<Elem>* subroot) {if (subroot == NULL) return; // Empty, do nothingpreorder(subroot->left());preorder(subroot->right());visit(subroot); // Perform desired action}5.5 The key is to search both subtrees, as necessary.template <class Key, class Elem, class KEComp>bool search(BinNode<Elem>* subroot, Key K);if (subroot == NULL) return false;if (subroot->value() == K) return true;if (search(subroot->right())) return true;return search(subroot->left());}34 Chap. 5 Binary Trees5.6 The key is to use a queue to store subtrees to be processed.template <class Elem>void level(BinNode<Elem>* subroot) {AQueue<BinNode<Elem>*> Q;Q.enqueue(subroot);while(!Q.isEmpty()) {BinNode<Elem>* temp;Q.dequeue(temp);if(temp != NULL) {Print(temp);Q.enqueue(temp->left());Q.enqueue(temp->right());}}}5.7 template <class Elem>int height(BinNode<Elem>* subroot) {if (subroot == NULL) return 0; // Empty subtreereturn 1 + max(height(subroot->left()),height(subroot->right()));}5.8 template <class Elem>int count(BinNode<Elem>* subroot) {if (subroot == NULL) return 0; // Empty subtreeif (subroot->isLeaf()) return 1; // A leafreturn 1 + count(subroot->left()) +count(subroot->right());}5.9 (a) Since every node stores 4 bytes of data and 12 bytes of pointers, the overhead fraction is 12/16 = 75%.(b) Since every node stores 16 bytes of data and 8 bytes of pointers, the overhead fraction is 8/24 ≈ 33%.(c) Leaf nodes store 8 bytes of data and 4 bytes of pointers; internal nodesstore 8 bytes of data and 12 bytes of pointers. Since the nodes havedifferent sizes, the total space needed for internal nodes is not the sameas for leaf nodes. Students must be careful to do the calculation correctly,taking the weighting into account. The correct formula looks asfollows, given that there are x internal nodes and x leaf nodes.4x + 12x12x + 20x= 16/32 = 50%.(d) Leaf nodes store 4 bytes of data; internal nodes store 4 bytes of pointers. The formula looks as follows, given that there are x internal nodes and35x leaf nodes:4x4x + 4x= 4/8 = 50%.5.10 If equal valued nodes were allowed to appear in either subtree, then during a search for all nodes of a given value, whenever we encounter a node of that value the search would be required to search in both directions.5.11 This tree is identical to the tree of Figure 5.20(a), except that a node with value 5 will be added as the right child of the node with value 2.5.12 This tree is identical to the tree of Figure 5.20(b), except that the value 24 replaces the value 7, and the leaf node that originally contained 24 is removed from the tree.5.13 template <class Key, class Elem, class KEComp>int smallcount(BinNode<Elem>* root, Key K);if (root == NULL) return 0;if (KEComp.gt(root->value(), K))return smallcount(root->leftchild(), K);elsereturn smallcount(root->leftchild(), K) +smallcount(root->rightchild(), K) + 1;5.14 template <class Key, class Elem, class KEComp>void printRange(BinNode<Elem>* root, int low,int high) {if (root == NULL) return;if (KEComp.lt(high, root->val()) // all to leftprintRange(root->left(), low, high);else if (KEComp.gt(low, root->val())) // all to rightprintRange(root->right(), low, high);else { // Must process both childrenprintRange(root->left(), low, high);PRINT(root->value());printRange(root->right(), low, high);}}5.15 The minimum number of elements is contained in the heap with a single node at depth h − 1, for a total of 2h−1 nodes.The maximum number of elements is contained in the heap that has completely filled up level h − 1, for a total of 2h − 1 nodes.5.16 The largest element could be at any leaf node.5.17 The corresponding array will be in the following order (equivalent to level order for the heap):12 9 10 5 4 1 8 7 3 236 Chap. 5 Binary Trees5.18 (a) The array will take on the following order:6 5 3 4 2 1The value 7 will be at the end of the array.(b) The array will take on the following order:7 4 6 3 2 1The value 5 will be at the end of the array.5.19 // Min-heap classtemplate <class Elem, class Comp> class minheap {private:Elem* Heap; // Pointer to the heap arrayint size; // Maximum size of the heapint n; // # of elements now in the heapvoid siftdown(int); // Put element in correct placepublic:minheap(Elem* h, int num, int max) // Constructor{ Heap = h; n = num; size = max; buildHeap(); }int heapsize() const // Return current size{ return n; }bool isLeaf(int pos) const // TRUE if pos a leaf{ return (pos >= n/2) && (pos < n); }int leftchild(int pos) const{ return 2*pos + 1; } // Return leftchild posint rightchild(int pos) const{ return 2*pos + 2; } // Return rightchild posint parent(int pos) const // Return parent position { return (pos-1)/2; }bool insert(const Elem&); // Insert value into heap bool removemin(Elem&); // Remove maximum value bool remove(int, Elem&); // Remove from given pos void buildHeap() // Heapify contents{ for (int i=n/2-1; i>=0; i--) siftdown(i); }};template <class Elem, class Comp>void minheap<Elem, Comp>::siftdown(int pos) { while (!isLeaf(pos)) { // Stop if pos is a leafint j = leftchild(pos); int rc = rightchild(pos);if ((rc < n) && Comp::gt(Heap[j], Heap[rc]))j = rc; // Set j to lesser child’s valueif (!Comp::gt(Heap[pos], Heap[j])) return; // Done37swap(Heap, pos, j);pos = j; // Move down}}template <class Elem, class Comp>bool minheap<Elem, Comp>::insert(const Elem& val) { if (n >= size) return false; // Heap is fullint curr = n++;Heap[curr] = val; // Start at end of heap// Now sift up until curr’s parent < currwhile ((curr!=0) &&(Comp::lt(Heap[curr], Heap[parent(curr)]))) {swap(Heap, curr, parent(curr));curr = parent(curr);}return true;}template <class Elem, class Comp>bool minheap<Elem, Comp>::removemin(Elem& it) { if (n == 0) return false; // Heap is emptyswap(Heap, 0, --n); // Swap max with last valueif (n != 0) siftdown(0); // Siftdown new root valit = Heap[n]; // Return deleted valuereturn true;}38 Chap. 5 Binary Trees// Remove value at specified positiontemplate <class Elem, class Comp>bool minheap<Elem, Comp>::remove(int pos, Elem& it) {if ((pos < 0) || (pos >= n)) return false; // Bad posswap(Heap, pos, --n); // Swap with last valuewhile ((pos != 0) &&(Comp::lt(Heap[pos], Heap[parent(pos)])))swap(Heap, pos, parent(pos)); // Push up if largesiftdown(pos); // Push down if small keyit = Heap[n];return true;}5.20 Note that this summation is similar to Equation 2.5. To solve the summation requires the shifting technique from Chapter 14, so this problem may be too advanced for many students at this time. Note that 2f(n) − f(n) = f(n),but also that:2f(n) − f(n) = n(24+48+616+ ··· +2(log n − 1)n) −n(14+28+316+ ··· +log n − 1n)logn−1i=112i− log n − 1n)= n(1 − 1n− log n − 1n)= n − log n.5.21 Here are the final codes, rather than a picture.l 00h 010i 011e 1000f 1001j 101d 11000a 1100100b 1100101c 110011g 1101k 11139The average code length is 3.234455.22 The set of sixteen characters with equal weight will create a Huffman coding tree that is complete with 16 leaf nodes all at depth 4. Thus, the average code length will be 4 bits. This is identical to the fixed length code. Thus, in this situation, the Huffman coding tree saves no space (and costs no space).5.23 (a) By the prefix property, there can be no character with codes 0, 00, or 001x where “x” stands for any binary string.(b) There must be at least one code with each form 1x, 01x, 000x where“x” could be any binary string (including the empty string).5.24 (a) Q and Z are at level 5, so any string of length n containing only Q’s and Z’s requires 5n bits.(b) O and E are at level 2, so any string of length n containing only O’s and E’s requires 2n bits.(c) The weighted average is5 ∗ 5 + 10 ∗ 4 + 35 ∗ 3 + 50 ∗ 2100bits per character5.25 This is a straightforward modification.// Build a Huffman tree from minheap h1template <class Elem>HuffTree<Elem>*buildHuff(minheap<HuffTree<Elem>*,HHCompare<Elem> >* hl) {HuffTree<Elem> *temp1, *temp2, *temp3;while(h1->heapsize() > 1) { // While at least 2 itemshl->removemin(temp1); // Pull first two treeshl->removemin(temp2); // off the heaptemp3 = new HuffTree<Elem>(temp1, temp2);hl->insert(temp3); // Put the new tree back on listdelete temp1; // Must delete the remnantsdelete temp2; // of the trees we created}return temp3;}6General Trees6.1 The following algorithm is linear on the size of the two trees. // Return TRUE iff t1 and t2 are roots of identical// general treestemplate <class Elem>bool Compare(GTNode<Elem>* t1, GTNode<Elem>* t2) { GTNode<Elem> *c1, *c2;if (((t1 == NULL) && (t2 != NULL)) ||((t2 == NULL) && (t1 != NULL)))return false;if ((t1 == NULL) && (t2 == NULL)) return true;if (t1->val() != t2->val()) return false;c1 = t1->leftmost_child();c2 = t2->leftmost_child();while(!((c1 == NULL) && (c2 == NULL))) {if (!Compare(c1, c2)) return false;if (c1 != NULL) c1 = c1->right_sibling();if (c2 != NULL) c2 = c2->right_sibling();}}6.2 The following algorithm is Θ(n2).// Return true iff t1 and t2 are roots of identical// binary treestemplate <class Elem>bool Compare2(BinNode<Elem>* t1, BinNode<Elem* t2) { BinNode<Elem> *c1, *c2;if (((t1 == NULL) && (t2 != NULL)) ||((t2 == NULL) && (t1 != NULL)))return false;if ((t1 == NULL) && (t2 == NULL)) return true;4041if (t1->val() != t2->val()) return false;if (Compare2(t1->leftchild(), t2->leftchild())if (Compare2(t1->rightchild(), t2->rightchild())return true;if (Compare2(t1->leftchild(), t2->rightchild())if (Compare2(t1->rightchild(), t2->leftchild))return true;return false;}6.3 template <class Elem> // Print, postorder traversalvoid postprint(GTNode<Elem>* subroot) {for (GTNode<Elem>* temp = subroot->leftmost_child();temp != NULL; temp = temp->right_sibling())postprint(temp);if (subroot->isLeaf()) cout << "Leaf: ";else cout << "Internal: ";cout << subroot->value() << "\n";}6.4 template <class Elem> // Count the number of nodesint gencount(GTNode<Elem>* subroot) {if (subroot == NULL) return 0int count = 1;GTNode<Elem>* temp = rt->leftmost_child();while (temp != NULL) {count += gencount(temp);temp = temp->right_sibling();}return count;}6.5 The Weighted Union Rule requires that when two parent-pointer trees are merged, the smaller one’s root becomes a child of the larger one’s root. Thus, we need to keep track of the number of nodes in a tree. To do so, modify the node array to store an integer value with each node. Initially, each node isin its own tree, so the weights for each node begin as 1. Whenever we wishto merge two trees, check the weights of the roots to determine which has more nodes. Then, add to the weight of the final root the weight of the new subtree.6.60 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15-1 0 0 0 0 0 0 6 0 0 0 9 0 0 12 06.7 The resulting tree should have the following structure:42 Chap. 6 General TreesNode 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Parent 4 4 4 4 -1 4 4 0 0 4 9 9 9 12 9 -16.8 For eight nodes labeled 0 through 7, use the following series of equivalences: (0, 1) (2, 3) (4, 5) (6, 7) (4 6) (0, 2) (4 0)This requires checking fourteen parent pointers (two for each equivalence),but none are actually followed since these are all roots. It is possible todouble the number of parent pointers checked by choosing direct children ofroots in each case.6.9 For the “lists of Children” representation, every node stores a data value and a pointer to its list of children. Further, every child (every node except the root)has a record associated with it containing an index and a pointer. Indicatingthe size of the data value as D, the size of a pointer as P and the size of anindex as I, the overhead fraction is3P + ID + 3P + I.For the “Left Child/Right Sibling” representation, every node stores three pointers and a data value, for an overhead fraction of3PD + 3P.The first linked representation of Section 6.3.3 stores with each node a datavalue and a size field (denoted by S). Each child (every node except the root)also has a pointer pointing to it. The overhead fraction is thusS + PD + S + Pmaking it quite efficient.The second linked representation of Section 6.3.3 stores with each node adata value and a pointer to the list of children. Each child (every node exceptthe root) has two additional pointers associated with it to indicate its placeon the parent’s linked list. Thus, the overhead fraction is3PD + 3P.6.10 template <class Elem>BinNode<Elem>* convert(GTNode<Elem>* genroot) {if (genroot == NULL) return NULL;43GTNode<Elem>* gtemp = genroot->leftmost_child();btemp = new BinNode(genroot->val(), convert(gtemp),convert(genroot->right_sibling()));}6.11 • Parent(r) = (r − 1)/k if 0 < r < n.• Ith child(r) = kr + I if kr +I < n.• Left sibling(r) = r − 1 if r mod k = 1 0 < r < n.• Right sibling(r) = r + 1 if r mod k = 0 and r + 1 < n.6.12 (a) The overhead fraction is4(k + 1)4 + 4(k + 1).(b) The overhead fraction is4k16 + 4k.(c) The overhead fraction is4(k + 2)16 + 4(k + 2).(d) The overhead fraction is2k2k + 4.6.13 Base Case: The number of leaves in a non-empty tree of 0 internal nodes is (K − 1)0 + 1 = 1. Thus, the theorem is correct in the base case.Induction Hypothesis: Assume that the theorem is correct for any full Karytree containing n internal nodes.Induction Step: Add K children to an arbitrary leaf node of the tree withn internal nodes. This new tree now has 1 more internal node, and K − 1more leaf nodes, so theorem still holds. Thus, the theorem is correct, by the principle of Mathematical Induction.6.14 (a) CA/BG///FEDD///H/I//(b) CA/BG/FED/H/I6.15 X|P-----| | |C Q R---| |V M44 Chap. 6 General Trees6.16 (a) // Use a helper function with a pass-by-reference// variable to indicate current position in the// node list.template <class Elem>BinNode<Elem>* convert(char* inlist) {int curr = 0;return converthelp(inlist, curr);}// As converthelp processes the node list, curr is// incremented appropriately.template <class Elem>BinNode<Elem>* converthelp(char* inlist,int& curr) {if (inlist[curr] == ’/’) {curr++;return NULL;}BinNode<Elem>* temp = new BinNode(inlist[curr++], NULL, NULL);temp->left = converthelp(inlist, curr);temp->right = converthelp(inlist, curr);return temp;}(b) // Use a helper function with a pass-by-reference // variable to indicate current position in the// node list.template <class Elem>BinNode<Elem>* convert(char* inlist) {int curr = 0;return converthelp(inlist, curr);}// As converthelp processes the node list, curr is// incremented appropriately.template <class Elem>BinNode<Elem>* converthelp(char* inlist,int& curr) {if (inlist[curr] == ’/’) {curr++;return NULL;}BinNode<Elem>* temp =new BinNode<Elem>(inlist[curr++], NULL, NULL);if (inlist[curr] == ’\’’) return temp;45curr++ // Eat the internal node mark.temp->left = converthelp(inlist, curr);temp->right = converthelp(inlist, curr);return temp;}(c) // Use a helper function with a pass-by-reference// variable to indicate current position in the// node list.template <class Elem>GTNode<Elem>* convert(char* inlist) {int curr = 0;return converthelp(inlist, curr);}// As converthelp processes the node list, curr is// incremented appropriately.template <class Elem>GTNode<Elem>* converthelp(char* inlist,int& curr) {if (inlist[curr] == ’)’) {curr++;return NULL;}GTNode<Elem>* temp =new GTNode<Elem>(inlist[curr++]);if (curr == ’)’) {temp->insert_first(NULL);return temp;}temp->insert_first(converthelp(inlist, curr));while (curr != ’)’)temp->insert_next(converthelp(inlist, curr));curr++;return temp;}6.17 The Huffman tree is a full binary tree. To decode, we do not need to know the weights of nodes, only the letter values stored in the leaf nodes. Thus, we can use a coding much like that of Equation 6.2, storing only a bit mark for internal nodes, and a bit mark and letter value for leaf nodes.7Internal Sorting7.1 Base Case: For the list of one element, the double loop is not executed and the list is not processed. Thus, the list of one element remains unaltered and is sorted.Induction Hypothesis: Assume that the list of n elements is sorted correctlyby Insertion Sort.Induction Step: The list of n + 1 elements is processed by first sorting thetop n elements. By the induction hypothesis, this is done correctly. The final pass of the outer for loop will process the last element (call it X). This isdone by the inner for loop, which moves X up the list until a value smallerthan that of X is encountered. At this point, X has been properly insertedinto the sorted list, leaving the entire collection of n + 1 elements correctly sorted. Thus, by the principle of Mathematical Induction, the theorem is correct.7.2 void StackSort(AStack<int>& IN) {AStack<int> Temp1, Temp2;while (!IN.isEmpty()) // Transfer to another stackTemp1.push(IN.pop());IN.push(Temp1.pop()); // Put back one elementwhile (!Temp1.isEmpty()) { // Process rest of elemswhile (IN.top() > Temp1.top()) // Find elem’s placeTemp2.push(IN.pop());IN.push(Temp1.pop()); // Put the element inwhile (!Temp2.isEmpty()) // Put the rest backIN.push(Temp2.pop());}}46477.3 The revised algorithm will work correctly, and its asymptotic complexity will remain Θ(n2). However, it will do about twice as many comparisons, since it will compare adjacent elements within the portion of the list already knownto be sorted. These additional comparisons are unproductive.7.4 While binary search will find the proper place to locate the next element, it will still be necessary to move the intervening elements down one position in the array. This requires the same number of operations as a sequential search. However, it does reduce the number of element/element comparisons, and may be somewhat faster by a constant factor since shifting several elements may be more efficient than an equal number of swap operations.7.5 (a) template <class Elem, class Comp>void selsort(Elem A[], int n) { // Selection Sortfor (int i=0; i<n-1; i++) { // Select i’th recordint lowindex = i; // Remember its indexfor (int j=n-1; j>i; j--) // Find least valueif (Comp::lt(A[j], A[lowindex]))lowindex = j; // Put it in placeif (i != lowindex) // Add check for exerciseswap(A, i, lowindex);}}(b) There is unlikely to be much improvement; more likely the algorithmwill slow down. This is because the time spent checking (n times) isunlikely to save enough swaps to make up.(c) Try it and see!7.6 • Insertion Sort is stable. A swap is done only if the lower element’svalue is LESS.• Bubble Sort is stable. A swap is done only if the lower element’s valueis LESS.• Selection Sort is NOT stable. The new low value is set only if it isactually less than the previous one, but the direction of the search isfrom the bottom of the array. The algorithm will be stable if “less than”in the check becomes “less than or equal to” for selecting the low key position.• Shell Sort is NOT stable. The sublist sorts are done independently, andit is quite possible to swap an element in one sublist ahead of its equalvalue in another sublist. Once they are in the same sublist, they willretain this (incorrect) relationship.• Quick-sort is NOT stable. After selecting the pivot, it is swapped withthe last element. This action can easily put equal records out of place.48 Chap. 7 Internal Sorting• Conceptually (in particular, the linked list version) Mergesort is stable.The array implementations are NOT stable, since, given that the sublistsare stable, the merge operation will pick the element from the lower listbefore the upper list if they are equal. This is easily modified to replace“less than” with “less than or equal to.”• Heapsort is NOT stable. Elements in separate sides of the heap are processed independently, and could easily become out of relative order.• Binsort is stable. Equal values that come later are appended to the list.• Radix Sort is stable. While the processing is from bottom to top, thebins are also filled from bottom to top, preserving relative order.7.7 In the worst case, the stack can store n records. This can be cut to log n in the worst case by putting the larger partition on FIRST, followed by the smaller. Thus, the smaller will be processed first, cutting the size of the next stacked partition by at least half.7.8 Here is how I derived a permutation that will give the desired (worst-case) behavior:a b c 0 d e f g First, put 0 in pivot index (0+7/2),assign labels to the other positionsa b c g d e f 0 First swap0 b c g d e f a End of first partition pass0 b c g 1 e f a Set d = 1, it is in pivot index (1+7/2)0 b c g a e f 1 First swap0 1 c g a e f b End of partition pass0 1 c g 2 e f b Set a = 2, it is in pivot index (2+7/2)0 1 c g b e f 2 First swap0 1 2 g b e f c End of partition pass0 1 2 g b 3 f c Set e = 3, it is in pivot index (3+7/2)0 1 2 g b c f 3 First swap0 1 2 3 b c f g End of partition pass0 1 2 3 b 4 f g Set c = 4, it is in pivot index (4+7/2)0 1 2 3 b g f 4 First swap0 1 2 3 4 g f b End of partition pass0 1 2 3 4 g 5 b Set f = 5, it is in pivot index (5+7/2)0 1 2 3 4 g b 5 First swap0 1 2 3 4 5 b g End of partition pass0 1 2 3 4 5 6 g Set b = 6, it is in pivot index (6+7/2)0 1 2 3 4 5 g 6 First swap0 1 2 3 4 5 6 g End of parition pass0 1 2 3 4 5 6 7 Set g = 7.Plugging the variable assignments into the original permutation yields:492 6 4 0 13 5 77.9 (a) Each call to qsort costs Θ(i log i). Thus, the total cost isni=1i log i = Θ(n2 log n).(b) Each call to qsort costs Θ(n log n) for length(L) = n, so the totalcost is Θ(n2 log n).7.10 All that we need to do is redefine the comparison test to use strcmp. The quicksort algorithm itself need not change. This is the advantage of paramerizing the comparator.7.11 For n = 1000, n2 = 1, 000, 000, n1.5 = 1000 ∗√1000 ≈ 32, 000, andn log n ≈ 10, 000. So, the constant factor for Shellsort can be anything less than about 32 times that of Insertion Sort for Shellsort to be faster. The constant factor for Shellsort can be anything less than about 100 times thatof Insertion Sort for Quicksort to be faster.7.12 (a) The worst case occurs when all of the sublists are of size 1, except for one list of size i − k + 1. If this happens on each call to SPLITk, thenthe total cost of the algorithm will be Θ(n2).(b) In the average case, the lists are split into k sublists of roughly equal length. Thus, the total cost is Θ(n logk n).7.13 (This question comes from Rawlins.) Assume that all nuts and all bolts havea partner. We use two arrays N[1..n] and B[1..n] to represent nuts and bolts. Algorithm 1Using merge-sort to solve this problem.First, split the input into n/2 sub-lists such that each sub-list contains twonuts and two bolts. Then sort each sub-lists. We could well come up with apair of nuts that are both smaller than either of a pair of bolts. In that case,all you can know is something like:N1, N2。

数据结构概述数据结构是计算机存储、组织数据的方式。

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。

数据结构往往同高效的检索算法和索引技术有关。

目录[隐藏][编辑本段]基本简介数据结构在计算机科学界至今没有标准的定义。

个人根据各自的理解的不同而有不同的表述方法：Sartaj Sahni在他的《数据结构、算法与应用》一书中称：“数据结构是数据对例的数据元素之间的各种联系。

这些联系可以通过定义相关的函数来给出。

”他将数据对象（data object）定义为“一个数据对象是实例或值的集合”。

Clifford A.Shaffer在《数据结构与算法分析》一书中的定义是：“数据结构是ADT （抽象数据类型 Abstract Data Type）的物理实现。

”Lobert L.Kruse在《数据结构与程序设计》一书中，将一个数据结构的设计过程分成抽象层、数据结构层和实现层。

其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。

[编辑本段]重要意义一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的。

对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。

在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。

许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。

许多时候，确定了数据结构后，算法就容易得到了。

有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。

不论哪种情况，选择合适的数据结构都是非常重要的。

选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。

数据结构基本英语词汇数据抽象data abstraction数据元素data element数据对象data object数据项data item数据类型data type抽象数据类型abstract data type逻辑结构logical structure物理结构phyical structure线性结构linear structure非线性结构nonlinear structure基本数据类型atomic data type固定聚合数据类型fixed-aggregate data type可变聚合数据类型variable-aggregate data type 线性表linear list栈stack队列queue串string数组array树tree图grabh查找，线索searching更新updating排序（分类) sorting插入insertion删除deletion前趋predecessor后继successor直接前趋immediate predecessor直接后继immediate successor双端列表deque(double-ended queue) 循环队列cirular queue指针pointer先进先出表（队列）first-in first-out list后进先出表（队列）last-in first-out list栈底bottom栈定top压入push弹出pop队头front队尾rear上溢overflow下溢underflow数组array矩阵matrix多维数组multi-dimentional array以行为主的顺序分配row major order以列为主的顺序分配column major order 三角矩阵truangular matrix对称矩阵symmetric matrix稀疏矩阵sparse matrix转置矩阵transposed matrix链表linked list线性链表linear linked list单链表single linked list多重链表multilinked list循环链表circular linked list双向链表doubly linked list十字链表orthogonal list广义表generalized list链link指针域pointer field链域link field头结点head node头指针head pointer尾指针tail pointer串string空白（空格）串blank string空串（零串）null string子串substring树tree子树subtree森林forest根root叶子leaf结点node深度depth层次level双亲parents孩子children兄弟brother祖先ancestor子孙descentdant二叉树binary tree平衡二叉树banlanced binary tree 满二叉树full binary tree完全二叉树complete binary tree遍历二叉树traversing binary tree二叉排序树binary sort tree二叉查找树binary search tree线索二叉树threaded binary tree哈夫曼树Huffman tree有序数ordered tree无序数unordered tree判定树decision tree双链树doubly linked tree数字查找树digital search tree树的遍历traversal of tree先序遍历preorder traversal中序遍历inorder traversal后序遍历postorder traversal图graph子图subgraph有向图digraph(directed graph)无向图undigraph(undirected graph) 完全图complete graph连通图connected graph非连通图unconnected graph强连通图strongly connected graph 弱连通图weakly connected graph 加权图weighted graph有向无环图directed acyclic graph 稀疏图spares graph稠密图dense graph重连通图biconnected graph二部图bipartite graph边edge顶点vertex弧arc路径path回路（环）cycle弧头head弧尾tail源点source终点destination汇点sink权weight连接点articulation point初始结点initial node终端结点terminal node相邻边adjacent edge相邻顶点adjacent vertex关联边incident edge入度indegree出度outdegree最短路径shortest path有序对ordered pair无序对unordered pair简单路径simple path简单回路simple cycle连通分量connected component 邻接矩阵adjacency matrix邻接表adjacency list邻接多重表adjacency multilist 遍历图traversing graph生成树spanning tree最小（代价）生成树minimum(cost)spanning tree生成森林spanning forest拓扑排序topological sort偏序partical order拓扑有序topological orderAOV网activity on vertex networkAOE网activity on edge network关键路径critical path匹配matching最大匹配maximum matching增广路径augmenting path增广路径图augmenting path graph查找searching线性查找（顺序查找）linear search (sequential search) 二分查找binary search分块查找block search散列查找hash search平均查找长度average search length散列表hash table散列函数hash funticion直接定址法immediately allocating method数字分析法digital analysis method平方取中法mid-square method折叠法folding method除法division method随机数法random number method排序sort内部排序internal sort外部排序external sort插入排序insertion sort随小增量排序diminishing increment sort选择排序selection sort堆排序heap sort快速排序quick sort归并排序merge sort基数排序radix sort外部排序external sort平衡归并排序balance merging sort二路平衡归并排序balance two-way merging sort 多步归并排序ployphase merging sort置换选择排序replacement selection sort文件file主文件master file顺序文件sequential file索引文件indexed file索引顺序文件indexed sequential file索引非顺序文件indexed non-sequential file直接存取文件direct access file多重链表文件multilist file倒排文件inverted file一. 旅游概述China's catagory A travel agency 一类社China's category B travel agency 二类社China's category C travel agency 三类社Clothes,bearing and appearance 服装仪表guidebook 旅游指南guild practice 导游实践international tourism 国际导游itinerary 旅行计划,节目local guide 地陪,地方导游local tourist organization 地方旅游组织low season 淡季minimum tour price 最低旅游价格multilingual guide 会多种语言的导游national guide 全陪,全程导游national tourist organization 全国旅游组织off-peak season 淡季off season 淡季on season 旺季peak season 旺季professional （staff）旅游专业人员programme 节目receiving country 旅游接待国regional tourist organization 区域旅游组织season-high 旺季season-low 淡季selling season 旺季shoulder period/season 平季sightseeing 游览slack season 淡季state-list famous historical and culture cities 国家级历史文化名城tour arrangement 旅游安排tour brochure 旅游小册子tour catalog 旅游团目录tour code number 旅游代号编码tour escort/conductor/director 旅游团陪同tour leader 领队,团长tour operation 旅游业务tour route 旅游路线tour talker 自动导游磁带机tourism 旅游业,旅游tourism activities 旅游活动tourism circles 旅游界touring 游览touring club 旅游俱乐部tourist 游客tourist association 旅游协会tourist authority/office 旅游局tourist council 旅游委员会tourist destination 旅游目的地tourist destination area 旅游目的地地区tourist destination country 旅游目的国tourist map 旅游地图tourist organization 旅游组织tourist periodical 旅游周刊tourist spots 旅游点tourist trade 旅游界travel 旅行travel business 旅游业务travel expert 旅游专家travel industry 旅游业travel journalist 旅游记者travel press 旅游报纸travel publication 旅游出版物travelling 旅游travelling expense 旅费travel-see tourism 旅游（美）travel trade 旅游业travel writer 旅游作家trip 旅行World Tourism Day 世界旅游日World Tourism Organization 世界旅游组织Tourist Administration 旅游局China's National Tourism Administration 中国旅游局……Provincial Tourism Administration ……省旅游局……Autonomous Region To urism Administration 自治区旅游局……Municipal Tourism Administration 市旅游局……Autonomous Perfecture Tourism Administration 自治州旅游局……County Tourism Administration 县旅游局二. 饭店种类inn 旅馆,饭店lodge 小旅馆tavern 酒店caravansary 马车店,大旅馆hostel 招待所hotel 饭店,酒店motel（=motor hotel）汽车饭店（旅店）budget hotel 廉价旅馆economy hotel（one-star hotel）一星级饭店some comfort hotel（two-star hotel）二星级饭店average hotel（three -star hotel）三星级饭店high comfort hotel（four -star hotel）四星级饭店deluxe hotel（five-star hotel）五星级饭店三. 客房种类（1）single room 单人房（一张单人床）double room 双人房（二张单人床）double double 双人房（二张双人床）big single room大床房（一张双人大床）tripe room 三人房（三张单人床）（2）economy room（ER）经济间standard room（SR）标准间superior room（UR）高级套房standard suit（ss）套间deluxe room（DR）豪华间presidential suit（PS）总统套房（3）studio room 工作室型客房（设沙发床或躺椅）multi-functional room 多功能客房combined type rooms 组合客房四. 饭店计价方式（1）European plan（EP）欧式计价（只计房租,不包括餐饮等费用）（2）American plan（AP）美式计价（计算房租并包括每日三餐费用在内）（3）modified American plan 修正美式计价（计算房租且包括两餐费/早餐,午餐,晚餐中选两餐）（4）continental plan（CP）欧陆式计价（计算房租且包括欧陆式早餐餐费）（5）Bermuda plan（BP）百慕大计价（计算房租,包括美式早餐餐费）五. 常用旅游英语词汇standard rate 标准价en-suite 套房family suite 家庭套房twin room you 带两张单人床的房间double room 带一张双人床的房间advance deposit 定金reservation 订房间registration 登记rate sheets 房价表tariff 价目表cancellation 取消预定imperial suite 皇室套房presidential suite 总统套房suite deluxe 高级套房junior suite 简单套房mini suite 小型套房honeymoon suite 蜜月套房penthouse suite 楼顶套房unmade room 未清扫房on change 待清扫房valuables 贵重品porter 行李员luggage/baggage 行李registered/checked luggage 托运行李light luggage 轻便行李baggage elevator 行李电梯baggage receipt 行李收据trolley 手推车storage room 行李仓briefcase 公文包suit bag 衣服袋travelling bag 旅行袋shoulder bag 背包trunk 大衣箱suitcase 小提箱name tag 标有姓名的标签regular flight 正常航班non-scheduled flight 非正常航班international flight 国际航班domestic flight 国内航班flight number 航班号airport 机场airline operation 航空业务alternate airfield 备用机场landing field 停机坪international terminal 国际航班候机楼domestic terminal 国内航班候机楼control tower 控制台jetway 登机道air-bridge 旅客桥visitors terrace 迎送平台concourse 中央大厅loading bridge 候机室至飞机的连接通路airline coach service 汽车服务shuttle bus 机场内来往班车一. 旅游概述China's catagory A travel agency 一类社China's category B travel agency 二类社China's category C travel agency 三类社Clothes,bearing and appearance 服装仪表guidebook 旅游指南guild practice 导游实践international tourism 国际导游itinerary 旅行计划,节目local guide 地陪,地方导游local tourist organization 地方旅游组织low season 淡季minimum tour price 最低旅游价格multilingual guide 会多种语言的导游national guide 全陪,全程导游national tourist organization 全国旅游组织off-peak season 淡季off season 淡季on season 旺季peak season 旺季professional (staff) 旅游专业人员programme 节目receiving country 旅游接待国regional tourist organization 区域旅游组织season-high 旺季season-low 淡季selling season 旺季shoulder period/season 平季sightseeing 游览slack season 淡季state-list famous historical and culture cities 国家级历史文化名城tour arrangement 旅游安排tour brochure 旅游小册子tour catalog 旅游团目录tour code number 旅游代号编码tour escort/conductor/director 旅游团陪同tour leader 领队,团长tour operation 旅游业务tour route 旅游路线tour talker 自动导游磁带机tourism 旅游业,旅游tourism activities 旅游活动tourism circles 旅游界touring 游览touring club 旅游俱乐部tourist 游客tourist association 旅游协会tourist authority/office 旅游局tourist council 旅游委员会tourist destination 旅游目的地tourist destination area 旅游目的地地区tourist destination country 旅游目的国tourist map 旅游地图tourist organization 旅游组织tourist periodical 旅游周刊tourist spots 旅游点tourist trade 旅游界travel 旅行travel business 旅游业务travel expert 旅游专家travel industry 旅游业travel journalist 旅游记者travel press 旅游报纸travel publication 旅游出版物travelling 旅游travelling expense 旅费travel-see tourism 旅游(美)travel trade 旅游业travel writer 旅游作家trip 旅行World Tourism Day 世界旅游日World Tourism Organization 世界旅游组织Tourist Administration 旅游局China's National Tourism Administration 中国旅游局...Provincial Tourism Administration ...省旅游局...Autonomous Region Tourism Administration 自治区旅游局...Municipal Tourism Administration 市旅游局...Autonomous Perfecture Tourism Administration 自治州旅游局...County Tourism Administration 县旅游局二. 饭店种类inn 旅馆,饭店lodge 小旅馆tavern 酒店caravansary 马车店,大旅馆hostel 招待所hotel 饭店,酒店motel(=motor hotel)汽车饭店(旅店)budget hotel 廉价旅馆economy hotel(one-star hotel)一星级饭店some comfort hotel(two-star hotel)二星级饭店average hotel(three -star hotel)三星级饭店high comfort hotel(four -star hotel)四星级饭店deluxe hotel(five-star hotel)五星级饭店三. 客房种类(1)single room 单人房(一张单人床)double room 双人房(二张单人床)double double 双人房(二张双人床)big single room大床房(一张双人大床)tripe room 三人房(三张单人床)(2)economy room(ER) 经济间standard room(SR) 标准间superior room(UR) 高级套房standard suit(ss) 套间deluxe room(DR) 豪华间presidential suit(PS) 总统套房(3)studio room 工作室型客房(设沙发床或躺椅)multi-functional room 多功能客房combined type rooms 组合客房四. 饭店计价方式(1)European plan(EP) 欧式计价(只计房租,不包括餐饮等费用)(2)American plan(AP) 美式计价(计算房租并包括每日三餐费用在内)(3)modified American plan 修正美式计价(计算房租且包括两餐费/早餐,午餐,晚餐中选两餐)(4)continental plan(CP) 欧陆式计价(计算房租且包括欧陆式早餐餐费)(5)Bermuda plan(BP) 百慕大计价(计算房租,包括美式早餐餐费)五. 常用旅游英语词汇standard rate 标准价en-suite 套房family suite 家庭套房twin room you 带两张单人床的房间double room 带一张双人床的房间advance deposit 定金reservation 订房间registration 登记rate sheets 房价表tariff 价目表cancellation 取消预定imperial suite 皇室套房presidential suite 总统套房suite deluxe 高级套房junior suite 简单套房mini suite 小型套房honeymoon suite 蜜月套房penthouse suite 楼顶套房unmade room 未清扫房on change 待清扫房valuables 贵重品porter 行李员luggage/baggage 行李registered/checked luggage 托运行李light luggage 轻便行李baggage elevator 行李电梯baggage receipt 行李收据trolley 手推车storage room 行李仓briefcase 公文包suit bag 衣服袋travelling bag 旅行袋shoulder bag 背包trunk 大衣箱suitcase 小提箱name tag 标有姓名的标签regular flight 正常航班non-scheduled flight 非正常航班international flight 国际航班domestic flight 国内航班flight number 航班号airport 机场airline operation 航空业务alternate airfield 备用机场landing field 停机坪international terminal 国际航班候机楼domestic terminal 国内航班候机楼control tower 控制台jetway 登机道air-bridge 旅客桥visitors terrace 迎送平台concourse 中央大厅loading bridge 候机室至飞机的连接通路airline coach service 汽车服务shuttle bus 机场内来往班车advance deposit 定金air-bridge 旅客桥airline coach service 汽车服务airline operation 航空业务airport 机场alternate airfield 备用机场American plan（AP）美式计价（计算房租并包括每日三餐费用在内）Autonomous Perfecture Tourism Administration 自治州旅游局Autonomous Region Tourism Administration 自治区旅游局average hotel（three -star hotel）三星级饭店baggage elevator 行李电梯baggage receipt 行李收据Bermuda plan（BP）百慕大计价（计算房租,包括美式早餐餐费）big single room大床房（一张双人大床）briefcase 公文包budget hotel 廉价旅馆cancellation 取消预定caravansary 马车店,大旅馆China's catagory A travel agency 一类社China's category B travel agency 二类社China's category C travel agency 三类社China's National Tourism Administration 中国旅游局Clothes,bearing and appearance 服装仪表combined type rooms 组合客房concourse 中央大厅continental plan（CP）欧陆式计价（计算房租且包括欧陆式早餐餐费）control tower 控制台County Tourism Administration 县旅游局deluxe hotel（five-star hotel）五星级饭店deluxe room（DR）豪华间domestic flight 国内航班domestic terminal 国内航班候机楼double double 双人房（二张双人床）double room 带一张双人床的房间double room 双人房（二张单人床）economy hotel（one-star hotel）一星级饭店economy room（ER）经济间European plan（EP）欧式计价（只计房租,不包括餐饮等费用）family suite 家庭套房flight number 航班号guidebook 旅游指南guild practice 导游实践high comfort hotel（four -star hotel）四星级饭店honeymoon suite 蜜月套房hostel 招待所hotel 饭店,酒店imperial suite 皇室套房inn 旅馆,饭店international flight 国际航班international terminal 国际航班候机楼international tourism 国际导游itinerary 旅行计划,节目jetway 登机道junior suite 简单套房landing field 停机坪light luggage 轻便行李loading bridge 候机室至飞机的连接通路local guide 地陪,地方导游local tourist organization 地方旅游组织lodge 小旅馆low season 淡季luggage/baggage 行李mini suite 小型套房minimum tour price 最低旅游价格modified American plan 修正美式计价（计算房租且包括两餐费/早餐,午餐,晚餐中选两餐）motel（=motor hotel）汽车饭店（旅店）multi-functional room 多功能客房multilingual guide 会多种语言的导游Municipal Tourism Administration 市旅游局name tag 标有姓名的标签national guide 全陪,全程导游national tourist organization 全国旅游组织non-scheduled flight 非正常航班off season 淡季off-peak season 淡季on change 待清扫房on season 旺季peak season 旺季penthouse suite 楼顶套房porter 行李员presidential suit（PS）总统套房presidential suite 总统套房professional （staff）旅游专业人员programme 节目Provincial Tourism Administration ……省旅游局rate sheets 房价表receiving country 旅游接待国regional tourist organization 区域旅游组织registered/checked luggage 托运行李registration 登记regular flight 正常航班reservation 订房间season-high 旺季season-low 淡季selling season 旺季shoulder bag 背包shoulder period/season 平季shuttle bus 机场内来往班车sightseeing 游览single room 单人房（一张单人床）slack season 淡季some comfort hotel（two-star hotel）二星级饭店standard rate 标准价en-suite 套房standard room（SR）标准间standard suit（ss）套间state-list famous historical and culture cities 国家级历史文化名城storage room 行李仓studio room 工作室型客房（设沙发床或躺椅）suit bag 衣服袋suitcase 小提箱suite deluxe 高级套房superior room（UR）高级套房tariff 价目表tavern 酒店tour arrangement 旅游安排tour brochure 旅游小册子tour catalog 旅游团目录tour code number 旅游代号编码tour escort/conductor/director 旅游团陪同tour leader 领队,团长tour operation 旅游业务tour route 旅游路线tour talker 自动导游磁带机touring club 旅游俱乐部touring 游览tourism activities 旅游活动tourism circles 旅游界tourism 旅游业,旅游Tourist Administration 旅游局tourist association 旅游协会tourist authority/office 旅游局tourist council 旅游委员会tourist destination area 旅游目的地地区tourist destination country 旅游目的国tourist destination 旅游目的地tourist map 旅游地图tourist organization 旅游组织tourist periodical 旅游周刊tourist spots 旅游点tourist trade 旅游界tourist 游客travel business 旅游业务travel expert 旅游专家travel industry 旅游业travel journalist 旅游记者travel press 旅游报纸travel publication 旅游出版物travel trade 旅游业travel writer 旅游作家travel 旅行travelling bag 旅行袋travelling expense 旅费travelling 旅游travel-see tourism 旅游（美）trip 旅行tripe room 三人房（三张单人床）trolley 手推车trunk 大衣箱twin room you 带两张单人床的房间unmade room 未清扫房valuables 贵重品visitors terrace 迎送平台World Tourism Day 世界旅游日World Tourism Organization 世界旅游组织。

（精华版）国家开放大学电大《数据结构》网络课形考网考作业及答案100%通过考试说明：2020年秋期电大把该网络课纳入到“国开平台”进行考核，该课程共有4个形考任务，针对该门课程，本人汇总了该科所有的题，形成一个完整的标准题库，并且以后会不断更新，对考生的复习、作业和考试起着非常重要的作用，会给您节省大量的时间。

做考题时，利用本文档中的查找工具，把考题中的关键字输到查找工具的查找内容框内，就可迅速查找到该题答案。

本文库还有其他网核及教学考一体化答案，敬请查看。

课程总成绩=形成性考核X50% +终结性考试X 50%形考任务1一、单项选择题（每小题3分，共60分）题目1把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）o选择一项：D.物理结构题目2下列说法中，不正确的是（）o选择一项：C.数据项可由若干个数据元素构成题目3一个存储结点存储一个（）。

选择一项：C.数据元素题目4数据结构中，与所使用的计算机无关的是数据的（）。

选择一项：C.逻辑结构题目5在线性表的顺序结构中，以下说法正确的是（）o选择一项：D.逻辑上相邻的元素在物理位置上也相邻题目6对链表，以下叙述中正确的是（）o选择一项：C.不能随机访问任一结点题目7下列的叙述中，不属于算法特性的是（)o选择一项：C.可读性题目8算法的时间复杂度与（）有关。

选择一项：D.算法本身题目9的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动设有一个长度为n元素个数为（）0选择一项：C. n-i+1题目10设有一个长度为的顺序表，要删除第i个元素移动元素的个数为（）on选择一项：C. n-i题目11在一个单链表中，P、q分别指向表中两个相邻的结点，且q所指结点是P所指结点的直接后继，现要删除q所指结点, 可用语句（）。

选择一项：A.p->next=q->next题目12在一个单链表中P所指结点之后插入一个s所指的结点时，可执行（）。

I Single Choice(10 points)1. ( )For the following program fragment the running time(Big-Oh) is .i = 0;s = 0;while(s <( 5*n*n + 2)){ i++;s = s + i;}a. O(n)b. O(n2)c. O(n1/2)d. O(n3)2. ( )Which is non-linear data structure_____.a. queueb.stackc. treed. sequence list3.( )The worst-time for removing an element from a sequence list (Big-Oh) is .a. O(1)b. O(n)c. O(n2)d. O(n3)4.( )In a circular queue we can distinguish(区分) empty queues from full queues by .a. using a gap in the arrayb. incrementing queue positions by 2 instead of 1c.keeping a count of the number of elementsd. a and c5.( )A recursive function can cause an infinite sequence of function calls if .a.the problem size is halved at each stepb.the termination condition is missingc.no useful incremental computation is done in each stepd.the problem size is positive6．( )The full binary tree with height 4 has nodes.a. 15b. 16c.31d.327. ( )Searching in an unsorted list can be made faster by using .a.binary searchb. a sentinel（哨兵）at the end of the listc.linked list to store the elementsd. a and c8.（）Suppose there are 3 edges in an undirected graph G, If we represent graph G with a adjacency matrix, How many “1”s are there in the matrix?a. 3b. 6c. 1d. 99. ( ) Construct a Huffman tree by four leaf whose weights are 9, 2, 5, 7 respectively. The weighted path length is___________.a. 29b. 37c. 46d.4410. Consider the following weighted graph.Consider Dijkstra’s algorithm on this graph to find the shortest paths with s as a starting vertex. Which are the first four vertices extracted from the priority queue by the algorithm (listed in the order they are extracted) ?a. s, y, t, xb. s, y, x, zc. s, t, y, xd. s, y, x, tFig. 111. Here is an array of ten integers:5 3 8 9 1 7 0 26 4Suppose we partition this array using quicksort's partition function and using 5 for the pivot. Which shows the array after partition finishes:a. 5 3 4 2 1 0 7 9 6 8b. 0 3 4 2 1 5 7 9 6 8c. 3 1 0 2 4 5 8 9 6 7d. 3 1 0 2 4 5 8 9 7 6e. None of the aboveII Fill in Blank (10 points)1. For the following program fragment the running time(Big-Oh) is .for ( int i = 0; i < n; i++ )for ( int j = 0; j < =i; j++)s; //s为某种基本操作2. We store a 4×4 symmetric matrix A into an array B with row major order, Store the lower triangle only. the index of element a[2][3] in B is .3．We can use 3 vector type to store value and of non-zero elements in a sparse matrix.4. A______________ is a list where removal and addition occur at the same end . Frequently knowna LIFO (Last-In-First-Out) structure.5.T( n ) = 2T( n/2 )+ cn, T(n) = T( n-1)+cn, T( n ) = O(___________)6. There is a binary tree whose elements are characters. Preorder list of the binary tree is “ABECDFGHIJ” and inorder list of the binary tree is “EBCDAFHIGJ”. Postorder traversal sequence of the binary tree is .7．There are leaf nodes in a full binary tree with n nodes.8．When the input has been sorted ,the running time of insertion sort(Big-Oh) is .9．We sort the sequence（43，02，80，48，26，57，15，73，21，24，66）with shell sort for increment 3, the result is ______ _ .10、In a circular queue, “front” and “rear” are the front pointer and rear pointer respectively. Queue size is “maxsize”. When insert an element in the queue, rear = _________11. A ____________________________________________ is an example of a search tree which is multiway (allows more than two children).12. A tree in which every node is no smaller than its children is termed______________________.III Application of Algorithms（35 points）1.Graph G shown in Fig 2 is a directed graph, please describe G with adjacency matrix and write the orders of breadth first traversal and depth first traversal.Fig.22．The sequence of input keys is shown below:19，1，23，14，55，20，84，27，68，11，10，17A fixed table size of 19 and a hash function H(key)=key%13，with linear probing(线性探测), fill the table below and compute the average length of successful search.3. Show the results of inserting 53,17,78,09,45,65,87 each , one at a time, in a initially empty max heap（大根堆）4. write the sequence of preorder,postorder traversals and add inorder threads in the tree.Fig. 35. Build a Huffman tree and determine Huffman code when the probability distribution(概率分布) over the 8 alphabets ( c1, c2, c3, c4, c5, c6, c7, c8 ) is (0.05, 0.25, 0.03, 0.06, 0.10, 0.11, 0.36, 0.046. Graph G shown in Fig 4 is a directed graph, please describe G with adjacency list and write topological ordering.Fig. 4IV Fill in blank of algorithms.（15）1．Here is single source shortest path algorithm Dijkstra. Fill in blank of the algorithm.class Graph {//图的类定义private:float Edge[NumVertices][NumVertices];float dist[NumVertices];//最短路径长度数组int path[NumVertices];//最短路径数组int S[NumVertices];//最短路径顶点集public:void ShortestPath ( int, int );int choose ( int );};void Graph :: ShortestPath ( int n, int v ){//在具有n 个顶点的带权有向图中, 各边上权值由Edge[i][j]给出。

附录习题参考答案习题1参考答案1.1.选择题(1). A. (2). A. (3). A. (4). B.,C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.)A.1.2.填空题(1). 数据关系(2). 逻辑结构物理结构(3). 线性数据结构树型结构图结构(4). 顺序存储链式存储索引存储散列表（Hash）存储(5). 变量的取值范围操作的类别(6). 数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系(7). 关系网状结构树结构(8). 空间复杂度和时间复杂度(9). 空间时间(10). Ο(n)1.3 名词解释如下：数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。

数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。

数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。

数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。

数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。

数据类型：是指变量的取值范围和所能够进行的操作的总和。

算法：是对特定问题求解步骤的一种描述，是指令的有限序列。

1.4 语句的时间复杂度为：(1) Ο(n2)(2) Ο(n2)(3) Ο(n2)(4) Ο(n-1)(5) Ο(n3)1.5 参考程序：main(){int X,Y,Z；scanf(“%d, %d, %d”,&X,&Y,Z)；if (X>=Y)if(X>=Z)if (Y>=Z){ printf(“%d, %d, %d”,X,Y,Z);}else{ printf(“%d, %d, %d”,X,Z,Y);}else{ printf(“%d, %d, %d”,Z,X,Y);}elseif(Z>=X)if (Y>=Z){ printf(“%d, %d, %d”,Y,Z,X);}else{ printf(“%d, %d, %d”,Z,Y,X);}else{ printf(“%d, %d, %d”,Y,X,Z);}}1.6 参考程序：main(){int i,n;float x,a[],p;printf(“\nn=”);scanf(“%f”,&n);printf(“\nx=”);scanf(“%f”,&x);for(i=0;i<=n;i++)scanf(“%f ”,&a[i]);p=a[0];for(i=1;i<=n;i++){ p=p+a[i]*x;x=x*x;}printf(“%f”,p)’}习题2参考答案2.1选择题(1). C. (2). B. (3). B. (4). B. 5. D. 6. B. 7. B. 8. A. 9. A. 10. D.2.2.填空题(1). 有限序列(2). 顺序存储和链式存储(3). Ｏ(n) O(n)(4). n-i+1 n-i(5). 链式(6). 数据指针(7). 前驱后继(8). Ο(1) Ο(n)(9). s->next=p->next; p->next=s ;(10). s->next2.3. 解题思路：将顺序表A中的元素输入数组a，若数组a中元素个数为n,将下标为0，1,2,…,（n-1）/2的元素依次与下标为n,n-1,…, （n-1）/2的元素交换，输出数组a的元素。

数据结构实验指导书东华大学计算机科学与技术学院2009年9月目录前言 (1)一、概述 (1)二、实验步骤 (2)三、实验报告规范 (5)四、算法书写规范 (6)五、参考书目 (9)实验〇顺序表与链表 (10)实验〇实验报告示例 (12)实验一线性表 (25)实验报告示例：集合的并、交和差运算 (28)实验二栈和队列 (42)实验报告示例：迷宫问题 (45)实验三树和二叉树 (57)实验四图 (60)实验五查找 (63)实验六排序 (65)实验七综合设计性实验——航班信息的查询与检索 (67)前言一、概述上机实验是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。

通常，实验题中的问题比平时的习题复杂得多，也更接近实际。

实验着眼于原理与应用的结合点，使读者学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。

平时的练习较偏重于如何编写功能单一的“小”算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。

此外，还有很重要的一点是：机器是比任何教师都严厉的检查者。

为了达到上述目的，本指导书安排了七个主实验单元（其中除实验0作为预备练习，训练数组和链表的编程方法和编程技巧），其它各单元的训练重点在于基本的数据结构，而不强调面面俱到。

各实验单元与教科书的各章只具有粗略的对应关系，一个实验题常常涉及几部分教学内容。

在每个实验单元中安排有难度不等的实验题，经验表明，如果某题的难度略高于自己过去所对付过的最难题目的难度，则选择此题能够带来最大的收益。

切忌过分追求难题或者容易的题目。

一些实验题采取了统一的格式（其余的实验题由于比较简单，没有这么详细列出来，读者可举一反三），由问题描述、基本要求、测试数据、实现提示和选做内容五个部分组成。

数据结构基础及深入及考试复习资料习题及实验参考答案见附录结论1、数据的逻辑结构是指数据元素之间的逻辑关系。

即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。

它依赖于计算机。

存储结构可分为4大类：顺序、链式、索引、散列3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。

它由基本的数据类型构成，并包括一组相关的服务（或称操作）。

它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。

4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。

5、在数据结构中，从逻辑上可以把数据结构分成（ C ）A、动态结构和表态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构6、算法的时间复杂度取决于（ A ）A、问题的规模B、待处理数据的初态C、问题的规模和待处理数据的初态线性表1、线性表的存储结构包括顺序存储结构和链式存储结构两种。

2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ E ），删除一个元素需要移动的元素的个数为（ A ）。

A、(n-1)/2B、nC、n+1D、n-1E、n/2F、(n+1)/2G、(n-2)/23、“线性表的逻辑顺序与存储顺序总是一致的。

”这个结论是（ B ）A、正确的B、错误的C、不一定，与具体的结构有关4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ D ）A、必须是连续的B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以5、带头结点的单链表为空的判定条件是（ B ）A、head==NULLB、head->next==NULLC、head->next=headD、head!=NULL6、不带头结点的单链表head为空的判定条件是（ A ）A、head==NULLB、head->next==NULLC、head->next=headD、head!=NULL7、非空的循环单链表head的尾结点P满足（ C ）A、p->next==NULLB、p==NULLC、p->next==headD、p==head8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B ）A、O(1)B、O(n)C、O(n2)D、O(nlog2n)9、在一个单链表中，若删除p所指结点的后继结点，则执行（ A ）A、p->next=p->next->next;B、p=p->next;p->next=p->next->next;C、p->next=p->next;D、p= p->next->next;10、在一个单链表中，若在p所指结点之后插入s所指结点，则执行（ B ）A、s->next=p;p->next=s;B、s->next=p->next;p->next=s;C、s->next=p->next;p=s;D、p->next=s;s->next=p;11、在一个单链表中，已知q是p的前趋结点，若在q和p之间插入结点s，则执行（C ）A、s->next=p->next;p->next=s;B、p->next=s->next;s->next=p;C、q->next=s;s->next=p;D、p->next=s;s->next=q;12、在线性结构中，第一个结点没有前趋结点，其余每个结点有且只有 1 个前趋结点。