07级期末考试试题(final).doc

《数据结构》试题答案（开卷） A卷 （电信系本科2007级 2009年1月） 姓名 班级 题 号 一 二 三 总分 题 分 40 30 30 100 得 分 一、回答下列问题 (每题4分，共40分) 1．以下与数据的存储结构无关的术语是（ ）。 A．循环队列 B. 链表 C. 哈希表 D. 栈 2．将下列函数，按它们在n→∝时的无穷大阶数，从小到大排序。 n, n-n3+0.7n5, nlogn, 2n/2, n3, 100logn, n1/2+logn, n! 3．对于一个具有n个结点的二叉树来说，若采用非递归中序遍历算法，试分析在什么情况下其辅助空间最大？什么情况下其辅助空间最小？ 4．现有一序列含有10000个元素，其中只有少量元素无序，且它们距离正确位置不远；如果以比较和移动次数作为度量，那末将其排序最好采用什么方法？为什么？ 5．在一个具有n个顶点的有向图中，所有顶点的出度之和为m，二、综合题（每题10分，共30分） 1. 执行完下列语句段后，i值为多少？（7分） int i ; i =f(f(1)); int f(int x) { if (x0) return( x* f(x-1)); else return(2); } 2．设线性表L=（21，-7，-8，19，0，-11，34，30，-10），写出执行f(L)后的L状态，并简述算法f的功能。（7分） void f (SeqList L) { int i, j; for (i=j=0;iL-length; i++) if(L-data[i]=0){ if(i!=j) L-data[j]=L-data[i]; j++； } L-length=j; } 3．给定8个字符（A，B，C，D，E，F，G, H），对应的权值分别为（5，3，2，9，11，7, 19, 5），画出Huffman树，列出Huffman编码并求平均码长。（8分） 4．已知哈希函数为H（key）= key MOD 13,冲突处理函数为 Hi = (H(key)+di) MOD 15 (di=1,2,5…)，将下列序列5，18，2，6，16，11，31，24，13，8填入表长为15的Hash表中。（8分） 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 13 2 16 5 18 6 8 31 11 24 三、 算法设计题（每题10分，共30分） 1．设有n 个整数组成的序列，每个整数为－10、1之一。编写一个时间复杂度为On)的算法，使该序列次序排好。 （1）下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO （2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）（10分） 3．给定一个二叉树T，设计一个算法求给定结点P的父结点。（10分） 附加题：设计伪c算法以求解从集合{1..n}中选取k（k=n）个元素的所有组合。例如，从集合{1..4}中选取2个元素的所有组合的输出结果为：1 2，1 3，1 4，2 3， 2 4，3 4。（10分） 你一定要坚强，即使受过伤，流过泪，也能咬牙走下去。因为，人生，就是你一个人的人生。 ============================================================================== 命运如同手中的掌纹，无论多曲折，终掌握在自己手中 ============================================================== 得 分 得 分 得 分