发布时间 : 星期五 文章自考数据结构历年试题及答案更新完毕开始阅读
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;
4) Q->front == ( Q->front + 1 ) % MAXQSIZE; 5) if( Q->rear == Q->front ) tag = 0; 31.1)ABDECF
2)先根遍历BT
32.1)3,3,3,1,1,1,2,2,2 swap()调用6次
2)将f[]中的元素，所有值为x的放在y前，其他的放在所有y后。 33.1) ( low + high ) / 2
2) low = mid + 1
// while循环结束时，low = high + 1 3) r >= low 4) r[ low ] = x 五、算法设计题 34.
void f35( LinkList h, LinkList *h1, LinkList *h2 ) {
LinkList pre = h, p = h->next, ph2; *h1 = h;
*h2 = malloc( sizeof( struct PNode ) ); *h2->next = *h2; ph2 = *h2; while( p != h ){
if( (p->exp) % 2 ){//奇次项保留 pre = p; p = pre->next; }
else{//偶次项插入*h2
pre->next = p->next;//偶次项脱离h ph2->next = p; //尾插入*h2 p->next = *h2; ph2 = p; p = pre->next; } } }
全国2005年10月高等教育自学考试
数据结构试题