发布时间 : 星期二 文章数据结构复习题习题全六章含答案更新完毕开始阅读
int n = 0; LNode * p = HL; while ( p != NULL ) {
if ( p->data == x ) n++; p = p->next; }
return n; }
第三章 稀疏矩阵和广义表
一、单选题
1. A 2. B 二、填空题
1. 行号、列号、元素值 2. 行号、列号 3. 引用 (或指针) 4. 等于 5. 4 、5 6. 列号、行号 7. 单、表 8. 括号 9. 3
10. 元素值、子表指针 11. true、NULL
三、应用题 1
．
(1)
( (1,2,4),(2,4,-3),(2,7,1),(3,1,8),(4,4,5),(5,2,-7),(5,6,2),(6,4,6) ) (2) (3)
1 2 2 3 4 5 5 6 2 4 7 1 4 2 6 4 4 -3 1 8 5 -7 2 6 ((1,3,8),(2,1,4),(2,5,-7),(4,2,-3),(4,4,5), (4,6,6),(6,5, 2),(7,2,1)) 2． (1) A：
(2) B：长
长度：1 深度：2 1 2 2 4 4 4 6 7 3 1 5 2 4 6 5 2 8 4 -7 -3 5 6 2 1 度：3 深度：1
(3) C：长度：2 深度：3 (4) D：长度：2 深度：2 (5) E：长度：3 深度：3 (6) F：长度：1 深度：4
第四章 栈和队列
一、单选题
1. A 2. B 3. C 4. A 5. B 6. B 7. D 8. D 二、填空题
1.队尾、队首
2. 后进先出(LIFO)、先进先出(FIFO) 3.栈顶指针、存储 4.栈顶元素、栈顶指针
5.front = = rear 、(rear+1)%QueueMaxSize = = front 6. –1 、StackMaxSize-1
7. 栈空、空队、队列只有一个元素
8. 新结点的指针域、栈顶指针 9.指针域、栈顶指针 10. 队尾指针、存储 11.
top = = 0
12. p->next = HS 、HS = p 13. HS = HS->next
14. ( front = = rear ) && ( front <>NULL ) 15. 3 4 25 6 15 + - / 8 * + 16. (24+8)*3/(4*(10-7)) 、8 三、应用题
12 15 5 30 18 四、编程题
递归算法：
long Fib( int n ) {
if ( n==1 || n=2 ) // 终止递归条件 return 1; else
return Fib(n-1)+Fib(n-2); }
非递归算法：
long Fib( int n ) {
int a , b , c; // c代表当前项，a和b分别代表当前项前面的第2
项和第1项
a = b = 1;
if ( n == 1 || n == 2 ) return 1; else
for ( int i = 3 ; i<=n ; i++ ) { c = a+b; // 求当前项 a = b; // 产生第2项 b = c; // 产生第1项 }
return c; // 返回所求的第n项 }
递归算法的时间复杂度为 O(2n)，空间复杂度为 O(n)；非递归算法的时间复杂度为 O(n)，空间复杂度为 O(1)。
第五章 树和二叉树
一、 填空题
1. n-1 2. 5 、 50 3. 6 4. 31、21 5. 10、4、3 6. 2、1、1、6 7. B、I和J