2001年到2006年自考数据结构试题和答案 - 图文

☆自考乐园---心境随缘，诚与天下自考人共勉！！！ ☆自考乐园---分享快乐，你的快乐老家！！！☆自考乐园---引领成功，你的精神乐园！！！ ☆自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.........

7.c//BDBABDABDAB BDA

123失败，比较3次 BDBABDABDAB BDA

1失败，比较1次 BDBABDABDAB BDA

12失败，比较2次 BDBABDABDAB BDA

1失败，比较1次 BDBABDABDAB BDA

123成功，比较3次 共计10次 10.d

A / B / | \\ C D F | E 二、填空题 16.（一组）运算 17. 直接前驱 18. SXSSXXSSXSSXXX 19. 模式匹配 20. 5n - 6 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 ....

俱乐部名称：自考乐园;俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id，可以直接进入俱乐部）;俱乐部url地址：http://tieba.http://m.china-audit.com//club/5346389（您也可以通过此url进入俱乐部。）

☆自考乐园---心境随缘，诚与天下自考人共勉！！！ ☆自考乐园---分享快乐，你的快乐老家！！！☆自考乐园---引领成功，你的精神乐园！！！ ☆自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.........

// ...................... // ...................... 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个数调整为所有负数在前，所有整数在后

俱乐部名称：自考乐园;俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id，可以直接进入俱乐部）;俱乐部url地址：http://tieba.http://m.china-audit.com//club/5346389（您也可以通过此url进入俱乐部。）

☆自考乐园---心境随缘，诚与天下自考人共勉！！！ ☆自考乐园---分享快乐，你的快乐老家！！！☆自考乐园---引领成功，你的精神乐园！！！ ☆自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.........

五、算法设计题

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.

俱乐部名称：自考乐园;俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id，可以直接进入俱乐部）;俱乐部url地址：http://tieba.http://m.china-audit.com//club/5346389（您也可以通过此url进入俱乐部。）

☆自考乐园---心境随缘，诚与天下自考人共勉！！！ ☆自考乐园---分享快乐，你的快乐老家！！！☆自考乐园---引领成功，你的精神乐园！！！ ☆自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.........

[方法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;

4) Q->front == ( Q->front + 1 ) % MAXQSIZE; 5) if( Q->rear == Q->front ) tag = 0; 31.1)ABDECF

2)先根遍历BT

俱乐部名称：自考乐园;俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id，可以直接进入俱乐部）;俱乐部url地址：http://tieba.http://m.china-audit.com//club/5346389（您也可以通过此url进入俱乐部。）