数据结构复习题习题全六章含答案

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