《数据结构》课后习题答案(第2版).doc

第一章 1 填空题 （1）数据元素 （2）数据项 数据元素 （3）集合 线性结构 树结构 图结构 （4）顺序存储 链接存储 数据元素 数据元素之间的关系 （5）零或多个输入 一个或多个输出 有穷性 确定性 可行性 （6）自然语言 程序设计语言 流程图 伪代码 ，伪代码 （7）问题规模 （8）O(1) O(nlog2n) 2 选择题 （1）C D (2)B (3) B (4) A (5) D (6)A (7) C (8) C E 3 判断题 ×××√× 第二章 1 填空题 表长一半 表长 位置 108 p-next=(p-next)-next; 运算方便 p-next=head; s-next=rear-next rear-next=s; rear=s; q=rear-next-next; rear-next-next=q-next; delete q; O(1) O(n) 循环单链表 循环双链表 双链表 2 选择题 A B D B A A D B B C B B D A A 3 判断题 ××××× 第三章 1 填空题 1003H 顺序栈和链栈 top=-1或top==NULL top==数组长度或内存无可用空间 栈 abc+*d- 后进先出 先进先出 操作位置受限 假溢出 （rear-front+n）% n O(1) O(n) 2 选择题 C D C B B B D A C 3 判断题 ×√√×× 第四章 1 填空题 数据元素的类型是字符 长度相等且对应位置字符相等 存取 修改 顺序存储 1140 d+41 三元组顺序表 十字链表 2 选择题 B D E K B C D C D 3 判断题 ×√√×× 第五章 1 填空题 有且仅有一个 互不相交 度 孩子 双亲 2i-1 (n+1)/2 （n-1）/2 2h-1 2h-1 2k-1 50 12 CDBGFEA 2n n-1 n+1 n n-1 2 选择题 D D B C B C D A A B D A B B C D C 3 判断题 ×√×√× 第六章 1 填空题 0 n(n-1)/2 0 n(n-1) 自身 邻接矩阵 邻接表 O(n+e) 第j列所有元素之和 出度 前序 栈 层序 队列 O(n2) O(elog2e) 回路 vi vj vk 2 选择题 c A G C B D C F B D A A A C A C C F B 3 判断题 √√××××√× 第七章 1 填空题 顺序存储和链接存储 顺序存储 按照关键码有序 1 ，7 8，59/15 4 62 开放定址法 拉链法 散列查找 通过关键码计算记录的存储地址并进行一定的比较 2 选择题 B D B A D D A C C B D A C D 3 判断题 ××××× 第八章 1 填空题 查找 正序 n-1 反序 n(n-1)/2 3 3 O(nlog2n) O(n) n-1 50 60 2 选择题 C C C B A A B C B C D A D B D,B,E,A,C C,A,D,B,B,D,F C D 3 判断题 ×√××√