数据结构》习题集答案
第一章绪论（1-1）
一、选择题：
1、B、D 2 、A、B 3 、4 4 、C、A 5 、C 6 、D
7、A 8 、A 9 、D 10 、1 11 、2 12 、A、D 13 、3 二、填空题
1、数据元素数据元素间关系
2、集合线性结构树形结构图状结构或网状结构。
3、数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或
称“邻接关系” 。
4、表示（又称映像）。
5、（1）逻辑特性（2）在计算机内部如何表示和实现（3）数学特性。
6、算法的时间复杂度和空间复杂度。
7、（1）逻辑结构（2）物理结构（3）操作（运算）（4）算法。
绪论（1-2）
一、选择题：
1、B 2 、C 3 、C，B 4 、B 5 、C
6、D 7 、B 8 、O(sqrt(n))
二、填空题
1、（1）有穷性( 2)确定性（3）可行性。
2、( 1 ) n+12) n ( 3) n(n+3)/2 (4) n(n+1)/2 。
3、1+ (1+2++ (1+2+3) + …+ (1+2+…+n) =n(n+1)( n+2)/6 O(n 3)
4、O(n)
5、n(n-1)/2
第二章线性表（1-1 ）
、选择题：
1、B 2 、B 3 、A 4 、B 5 、C
6、A 7 、D 8 、D 9 、D 10 、B，C
11、C 12 、C
二、填空题
1 、顺序
2、（ n-1 ）/2
3、n-i+1
第二章 线性表( 1-2 )
一、选择题：
1、C 2 、 B 3
、B 4
、C
5 、A
6 、C
7、B
8 、A 9 、D
10 、 B 11
、C 12 、 B 13 、A
二、填空题
1、 py->next=px->next; px->next=py
2、主要是使插入和删除等操作统一，在第一个元素之前插入 元素 和删除第一个结点不必另
作判断。另外，不论链表是否为空，链表指针不变。 3、O(1) ，O(n)
4、单链表，多重链表， (动态)链表，静态链表
5、 f->next=p->next; f->prior=p; p->next->prior=f; p->next=f;
6、指针
7、物理上相邻 指针
8、 4 2
9、从任一结点出发都可访问到链表中每一个元素。 10、 u=p->next; p->next=u->next; free(u); 11、 L->next->next==L 12、 p->next!=null
13、 L->next==L && L->prior==L 14、 s->next=p->next;p->next=s;
第3章 栈和队列 (1-1)
、选择题：
1、 B 2 、①B , ②A ,③B ,④D,⑤C 3
、 B 4 6、 C 7 、B 8 、 D 9
、C 10 、 B
11
、B 12 、B
13 、 D
二
、填空题
1
、 操作受限(或限定仅在表尾进行插入和删除操作)
后进先出
2、
栈
3、 23 100CH
4、 (1) 满 (2) 空 (3)n (4) 栈底 (5) 两栈顶指针相邻(即值之差的绝对值为 1)
5、S x SSx S xx
6、 data[++top]=x ；
注：表达式中的点 (.) 表示将数隔开， 如 23.12.3 是三
个数)
7、 23.12.3*2-4/34.5*7/++108.9/+
8、栈
第3章栈和队列(3-2)
一、选择题：
1、D 2 、A 3 、D 4 、B 5 、B，D
6、C 7 、B 8 、C 9 、①B,②A,③C,④C,⑤F 10 、C 11、C 12 、A
、填空题
1、假溢出时大量移动数据元素。
2、队
3、先进先出
4、牺牲一个存储单元设标记
5、sq.front=(sq.front+1)%(M+1)
(sq.rear+1)%(M+1)==sq.front
第四章串
一、选择题：
1、B 2 、E 3 、C 4 、B 5 、B
二、填空题
1、(1) 由空格字符( ASCII 值32)所组成的字符串(2) 空格个数
2、字符3 、任意个连续的字符组成的子序列4 、5
5、(1) 模式匹配(2) 模式串
6、(1) 其数据元素都是字符
(2) 顺序存储
(3) 和链式存储
(4) 串的长度相等且两串中对应位置的字符也相等
7、两串的长度相等且两串中对应位置的字符也相等。
、' xyxyxywwy '
第五章数组与广义表
、选择题：
1、B 2 、L，J ，，C 3 、B 4 、B 5 、A
6、H
，C，
E，
A，F 7 、E，A，B 8 、B 9 、A 10 、B
11、B 12 、A 13 、D 14 、C 15 、D
16 、F 17 、C 18 、C,B 19 、C 20 、A
二、填空题1顺序存储结构8
2、( 1) 9572 (2) 1228
3、( 1) 9174 (2) 8788
4、1100
5、(1)270 (2)27 (3)2204
6、i(i-1)/2+j (1<=i,j<=n)
7、(1)n(n+1)/2 (2)i(i+1)/2 ( 或j(j+1)/2) (3)i(i-1)/2+j (4)j(j-1)/2+i (1<=i,j<=n)
8、33 (k=i(i-1)/2+j) (1<=i,j<=n)
9、93
10、i(i-1)/2+j
11、线性表
12、 (1) () (2) (()) (3) 2 (4) 2
13、head (head (tail (tail (head (tail (tail (A)))))))
14、(1) 5 (2) 3
15、head(head(tail(LS)))
16、head(tail(tail(head(tail(head(A))))))
17、head(tail(head(tail(H))))
18、(x,y,z)
19、(d,e)
第六章树和二叉树(1-1)、选择题:
1、D 2 、C 3 、D 4 、D 5 、B 6、B 7 、B 8 、C 9 、C 10 、B 11、D 12 、A 13 、A 14 、C 15 、C 16、D 17 、C 18 、B 19 、C 20 、D
21、D
二、填空题
1、(1)根结点⑵左子树⑶右子树
2、(1)双亲链表表示法(2)孩子链表表示法(3)孩子兄弟表示法
3、p->lchild==null && p->rchlid==null
4、(1) ++a*b3*4-cd (2)18
5、9
6、12
k 1k
7、(1)2 - (2)2 -1
8、(1)2 H-1 (2)2 H-1 (3)H= llj og 2N +1
第六章树和二叉树(1-2)、选择题：
1、C 2 、B 3 、A 4 、C 5 、B 6、A 7 、D 8 、B 9 、B 10 、C
11、B 12 、B 13 、F，B 14 、C 15 、C
二、填空题
1、(1) 先序( 2)中序
2、(1)EACBDGF ( 2)2
3、任何结点至多只有右子女的二叉树。
4、(1)a (2) dbe (3) hfcg
5、(1) .D.G.B.A.E.H.C.F. (2) ...GD.B...HE..FCA
6、DGEBFCA
7、(1)5 ( 2)略
8、先序
9、先序中序
10、双亲的右子树中最左下的叶子结点
第六章树和二叉树(1-3)、选择题：
1、A 2 、 D 3
、D 4 、D 5 、D
6、D 7 B 8 、C 9 、A 10 、C
11、C 12 、C 13 、A 14 、B 15 、B
、填空题
1、(1) n1-1 (2)n2+n3
2、21
3、(1) FEGHDCB (2)BEF (该二叉树转换成森林，含三棵树，其第一棵树的先根次序是
BEF)
4、二叉树
5、2
6、(1)1 (2)yA.lchild (3)0 (4)x (5)1 (6) y (7)x( 编者注：本题按中序线索化)
7、带权路径长度最小的二叉树，又称最优二叉树
8、69
9、(1)6 (2)261
10、(1)80 (2)001 (不唯一)
11 、2n0-1
第七章图(1-1)
、选择题：
1、A 2 、 B 3 、A 4 、B 5 、D
6、1B，2D 7 、1B
，2C 8 、B 9 、1B，2B，3D
10、B 11 、C 12 、 D 13 、D
14、1C，2C 15 、A 16 、D
、填空题
1、N-1
2、1，0
3、v1v2v3v6v5v4 ，v1v2v5v4v3v6
4、有n 个顶点，n-1 条边的无向连通图
5、有向图的极大强连通子图
6、生成树
7、45
8、n(n-1)/2
9、 ( d1+d2+…dn) 12
10、9
11、n
12、2(n-1)
13、N-1
14、n
15、n
16、3
17、2( N-1 )
18、度出度
19、第I 列非零元素个数
20、n 2e
21、深度优先
22、广度优先遍历
23、队列
24、因未给出存储结构，答案不唯一。本题按邻接表存储结构，邻接点按字典序排列。
第七章图(1-2)
一、选择题：
1、A 2 、1C，2BDE 3 、1C，2A，3B，4A
4、A 5 、B 6 、D 7 、A 8 、C
9、B
二、填空题
1 、普里姆( prim )算法和克鲁斯卡尔( Kruskal )算法
2、克鲁斯卡尔
3、边稠密边稀疏
4、(1 ) (V , V)边上的权值都大的数(2) 1负值
5、不存在环
6、递增负值
3)为负边
2
7、O（n ）
8、50,经过中间顶点④
9、（1 ）活动（2）活动间的优先关系（3）事件（4）活动边上的权代表活动持续
时间
10、关键路径
11、（1）某项活动以自己为先决条件（2）荒谬（3）死循环
12、（1 ）零（2）Vk度减1,若V k入度己减到零，则V顶点入栈（3）环
第九章查找
—
、选择题：
—
1、A 2 、( 1) D, (2) C 3、D 4 、、D 5 、C
6、C 7 、D 8 、B 9 、、D 10 、B
11 、(1) C, (2) C 12 、(1) C, (2)D, (3)G, (4) H 13 、(1)B , (2)A
、填空题
1、n n+1
2、4
3、6,9,11,12
4、5
5、1,3,6,8,11,13,16,19
6、5,96
7、2,4,3
8、（1）哈希函数⑵ 解决冲突的方法（3）选择好的哈希函数
⑷处理冲突的方法（5）均匀⑹简单
9、AVL树（高度平衡树，高度平衡的二叉排序树），或为空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于1。
10、小于等于表长的最大素数或不包含小于20的质因子的合数
11、|[10g 2"」+1
第九章查找
、选择题：
1、C 2 、C 3 、B 4 、B 5 、D
6、C 7 、A,C 8 、D 9 、D 10 、C
11、D 12 、(1) D, (2) C 13 、C
、填空题
1、k(k+1)/2
2、(1) 顺序存储或链式存储(2) 顺序存储且有序(3) 块内顺序存储，块间有序(4) 散列存储
3、结点的左子树的高度减去结点的右子树的高度