2013半期考试-数据结构与算法.ppt

Mid-term Exam（周四上午） 1. (5分)什么是数据的逻辑结构？数据的逻辑结构可以分为哪几类？ 2. (5分)证明：在具有n(n=1)个结点的m叉树中，有n(m-1)+1个指针是空的。 3. (5分) In the linked list implementation, the current pointer points to the previous element of the logical current node, not point to the logical current node. Why? 4. (10分) Determine Θ for the following code fragments in the average case. (1) a=0; for(k=1; kn-1; k++) for(j=n; j=k; j--) a += k; (2) sum = 0; for (i=1; i=n; i++) for (j=1; j=n; j*=2) sum++; 5. (10分) Suppose you have a binary tree whose data fields are single characters. When the data fields of the nodes are output: (1) in inorder： the output is DGBAHEICFJ (2) in postorder: the output is GDBHIEJFCA Draw the binary tree showing the data in each node, and show the steps used to arrive at the result. 6. (10分)若一个由2000个字符组成的文件中只有8种字符{a, b, c, d, e, f, g, h}，以相对频率{12, 7, 11, 17, 21, 4, 9, 19}出现，要求： 给出各字符的Huffman编码，并计算该文件的编码长度；计算每个字符的平均编码长度。 7. (10分) Show the heap that results from deleting the minimum value from the following min-heap. 13 27 38 49 65 76 50 97 后面3题是算法设计题。要求： （1）尽量用代码实现，语言不限，要有必要的注释； （2）实在不会写代码，也可以用伪代码实现，要求逻辑清晰，无歧义； 8. (15分)算法设计题： Write a function to merge two linked lists. Elements in input lists have been sorted from lowest to highest. The output list should be sorted from highest to lowest. Your algorithm should run in linear time on the length of the output list. 9. (15分)算法设计题： Write a recursive function named smallcount that, given the pointer to the root of a BST and a key K, returns the number of nodes having key values less than or equal to K. Function smallcount should visit as few nodes in the BST as possible. 10. (15分)算法设计题： The class of binary tree node is given below. class BinNodePtr{ public: char val; //value BinNodePtr* lc; //left child BinNodePtr* rc; //right child } BinNodePtr root; // root node You are to write a method elementAtLevel(int theLevel) which ret