33.已知整形数组L［1..8］中的元素依次为（9，8，5，7，6，3，2，1），阅读下列函数，并写出执行函数调用 sort(L, 8)时，对L进行的头两趟（pass分别为0和1）处理结果。 Void sort (int R[],int n) {
int pass = 0, k, exchange, x; do {
k=pass%2+1; exchange = 0; while (k if (R[k]>R[k+1]) { x = R[k]; R[k] = R[k+1]; R[k+1] = x; exchange =1; } K+=2 } pass ++; }while (exchange = = 1|| pass <=1); } 第一趟（pass = 0）: 8 9 5 7 3 6 1 2 第二趟（pass = 1）: 8 5 9 3 7 1 6 2 五、算法设计题（本大题共10分） 34．已知二叉排序树中结点的关键字为整数，设计递归算法按递增有序性输出树中所有大于或等于给定值x的结点，并以函数的参数返回输出的结点个数。假设以二叉链表为存储结构，其结点结构为： void find( BT * root, int x, int * count ) { if( !root ) return; if( root->key >= x ){//因为是排序树,只有当key>=x时，才需要查找其左子树 if( root-> lchild ) find( root->lchild, x , count ); (*count)++; printf(\root->key ); } if( root-> rchild ) find( root->rchild, x, count ); } 全国2004年10月卷答案 一、单项选择题 DABAC CCBDA ABABD // 5.可以简单的计算，空域为3->7，总共5个，对长则为21 - 5 = 16 7.c//BDBABDABDAB BDA 123失败，比较3次 BDBABDABDAB BDA 1失败，比较1次 BDBABDABDAB BDA 12失败，比较2次 BDBABDABDAB BDA 1失败，比较1次 BDBABDABDAB BDA 123成功，比较3次 10.d A / B / | \\ C D F | E 二、填空题 16.（一组）运算 17. 直接前驱 18. SXSSXXSSXSSXXX 19. 模式匹配 20. 5n - 6 共计10次 N+2N-2+2N-4=5N-6 // n阶5对角阵 // 1 1 1 0 0 ............ // 1 1 1 1 0 ............ // 1 1 1 1 1 0 .......... // 0 1 1 1 1 1 0......... // 0 0 1 1 1 1 1 0 ...... // ....0 1 1 1 1 1 0 .... // ...................... // ...................... 21. 50 // 63 < 100 < 127, 最下一层叶子数:100 - 63 = 37 // 倒数第2层叶子数:32 - [ 37 / 2 ] = 13 []向上取整 22. 径？ 23. 待排关键字（记录）？ 24. 有序的？ 25. ? // 一些概念题，因为没书，很久没接触了，可能不准确。 三、解答题 略 28划分后左边:(55) (28) (73) (91) (37) 右边:（64），（19），（82），（46） 第一次Merge之后:(28,55)(73) (91) (37) 右边:（64），（19），（82），（46) 第二次Merge之后:(28,55)(73,91) (37) 右边:（64），（19），（82），（46) 第三次Merge之后:(28,55,73,91)(37) 右边:（64），（19），（82），（46) 第四次Merge之后:(28,37,55,73,91) 右边:（64），（19），（82），（46) 第五次Merge之后:(28,37,55,73,91) 右边:（19,64），（82), (46) 所以.....28，37，55，73，91，19，64，82，46 四、算法阅读题 30. 1) p = pre->next; 或 p = L->next; // p指向第一个结点 2) p->next = Lc->next; // 数据大于c的p结点插入Lc链表表头 3) p = pre->next; 或 p = p->next; // 下一个结点 31.此题有误，... if ((i=!t)!=0) ... 应该是 ... if( ( i = !i ) != 0 ) ... 1) 1,3,5,7,6,4,2 2) 堆栈S中的元素依次出栈，奇数次序的入栈T,偶数次序的入队Q 32.图G的邻接矩阵不对称，因此，是有向图 1) 5 2) 计算有向图G中的端点i（第i+1个端点)的度，包括出度和入度 3) O(n) 33. 此题明显有错误if( low > high )应为if( low < high ) 因为if(){...}里有while( low < high ) 1) -8, -3, -2, -1, 4, 2, 5, 7 ：-8 -3 2 -1 -2 4 5 7 2) 将数组R中的前n个数调整为所有负数在前，所有整数在后 五、算法设计题 34. 看原型，应该是要使用递归了,题目很傻地把解法都告诉我们了。 f34(BinTree T,int level,int *lmin,int *lmax) { if(T){ if( T->lchild == NULL && T->rchild == NULL ){ if( *lmin == 0 || level < *lmin ) *lmin = level; if( level > *lmax ) *lmax = level; return; } if( T->lchild ) f34( T->lchild, level + 1, lmin, lmax ); if( T->rchlid ) f34( T->rchild, level + 1, lmin, lmax ); } } 2005.1全国卷答案(18号更新) 一、单项选择题 BDBBB ADDCA CBACC 二、填空题 16. O(n) 17. p->next && p->next->next == NULL 18. 41 19. 0? 20. 1100 + 2 * ( 4*6*7 + 3*7 + 2 ) = 1482 21. CBDA 22. n - 1 23. 3 // 56前面，比56大的数的个数 + 1 24. 表结点的个数 25. lgn 三、解答题 26. 1) ( ((a),((b),c)) ) 27. [方法1,liangliangzai] b个非叶子节点,有k*b个孩子, 加上根节点,节点总数: k*b + 1 节点总数 = 非叶节点 + 叶节点 = a + b 得 a = ( k - 1 )b + 1 [方法2] 设满k叉树的高度为n,则: 叶子结点数 a = k^( n - 1 ) 非叶结点数 b = 1 + k + k^2 ... + k^(n-2) = [ k^(n-1) - 1 ] / ( k - 1 ) => b = ( a - 1 ) / ( k - 1 ) => a = ( k -1 )b + 1 28 . 最短路径长度 已确定点集 最短路径直接前趋 . b c d e f b c d e f . 20 60 * 10 65 ( a ) a a * a a . 20 60 * - 30 ( a e ) a a * a e . - 50 * - 30 ( a e b ) a b * a e . - 45 110 - - ( a e b f ) a f f a e . - - 85 - - ( a e b f c ) a f c a e . - - - - - ( a e b f c d ) a f c a e 所以 a -> b 20 a,b . a -> e 10 a,e . a -> f 30 a,e,f . a -> c 45 a,e,f,c . a -> d 85 a,e,f,c,d 29 48 70 33 92 24 56 12 65 48 70 56 92 24 33 12 65 48 92 56 70 24 33 12 65 92 70 56 65 24 33 12 48 四、算法阅读题 30.1) Q->rear == Q->front && tag == 1; 2) if( Q->rear == Q->front ) tag = 1; 3) Q->rear == Q->front && tag == 0;