《数据结构》习题集答案

1、数据结构习题集答案 绪论（ 1-1） 一、选择题： 1、B、D 2、A、B 3、 4 4、C、A5、C6、D 7、 A8、 A9、 D 二、填空题 10、 1 11、 2 12、 A 、 D 13、3 1、数据元素数据元素间关系 2、集合 线性结构 树形结构 图状结构或网状结构。 3、数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关 联方式或称 “邻接关系 ”。 4、表示（又称映像） 。 5、（ 1）逻辑特性 （2）在计算机内部如何表示和实现（3）数学特性。 6、算法的时间复杂度和空间复杂度。 7、（ 1）逻辑结构（ 2）物理结构（ 3）操作（运算） （4）算法。

2、绪论（ 1-2） 一、选择题： 1、B 6、D 二、填空题 1 ）有穷性 1 ） n+1 1+ （ 1+2+ 0（n） n（n-1）/2 1、 2、 3、 4、 5、 2、C 7、B （2） 2）n 1+2+3） 3、C，B 8、 O(sqrt(n) 4、B 5、C 确定性 （ 3）可行性。 （3）n（n+3）/2（ 4） n（n+1）/2 。 + + （1+2+ +n） =n（n+1）（ n+2）/60（n3） 矚慫润厲钐瘗睞枥庑赖賃軔朧。 线性表（ 1-1 ） 一、选择题： 1、B 2、B 6、A 11、C 二、填空题 1 、顺序 2、（ n-1 ） /2 3、n-i+1 第二章 线性表（

3、 1-2） 一、选择题： 7、D 12、C 3、 8、 4、 9、 5、C 10、B，C 1、C 2、B 3、 4、 7、B 測樅。 二、填空题 8、 A9、 10、 5、 11、C 12、B 6、C 13、 A 聞創沟燴鐺險爱氇谴净祸 py-next=px-next; px-next=py 主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另 作判断。另外，不论链表是否为空，链表指针不变。 O（1），O（n） 单链表，多重链表， （动态）链表，静态链表 5、f-next=p-next; f-prior=p; p-next-prior=f; p-next=f;残骛楼諍锩

4、瀨濟溆塹籟婭骒東。 6、指针 7、物理上相邻指针 8、42 9、从任一结点出发都可访问到链表中每一个元素。 10、u=p-next; p-next=u-next; free(u); 11、L-next-next=L 12、p-next!=null 13、L-next=L p-next=s; 栈和队列 (1-1) 一、选择题： 1、 B2、B,A，B，D，C3、B4、D 5、D酽锕极 額閉镇桧猪訣锥顧荭钯。 6、C7、 B8、D9、C 10、B 11、 B12、 B13、D 二、填空题 1 、操作受限(或限定仅在表尾进行插入和删除操作)后进先出 2、栈 3、23100CH 4、 (1) 满 (2

5、) 空 (3)n (4) 栈底 (5)两栈顶指针相邻(即值之差的绝对值为1 ) 5、SXSSXSXX 6、data+top=x ； 7、23.12.3*2-4/34.5*7/+108.9/+ (注：表达式中的点 (.)表示将数隔开,如 23.12.3 是三 彈贸摄 尔霁毙攬砖卤庑诒尔肤。 个数) 8、栈 第 3 章 栈和队列 (3-2) 一、选择题： 1、 D2、 A3、 D 6、 C7、 B8、 C 箧飆鐸怼类蒋薔點鉍杂。 11、 C12、 A 二、填空题 1 、假溢出时大量移动数据元素。 2、队 3、先进先出 4、 牺牲一个存储单元设标记 5、sq.front=(sq.front+1)%(

6、M+1) ； (sq.rear+1)%(M+1)=sq.front ； 第四章 串 一、选择题： 1、 B2、 E3、 C 二、填空题 4、 B 5、 B, D 9、B，A，C,C,F 10、C謀养抟 4、 B 5、 B 1、(1) 由空格字符( ASCII 值 32)所组成的字符串(2)空格个数 2、字符3、任意个连续的字符组成的子序列4、 5 5、(1)模式匹配(2)模式串 6、(1)其数据元素都是字符 (2) 顺序存储 (3) 和链式存储 (4) 串的长度相等且两串中对应位置的字符也相等 7、两串的长度相等且两串中对应位置的字符也相等。 8 、 xyxyxywwy 第五章 数组与广义表

7、一、选择题： 1、B2、 L，J， C，I，C 3、 B 4、B 5、A 厦礴恳蹒骈時盡继價骚 卺癩龔。 6、H，C，E，A，F 7、E， A，B 8、B 9、A 10 、B 茕桢广鳓鯡选块网羈 泪镀齐鈞。 11、B12、 A 13、D 14 、C 15、D 16、 F17、C 18、C,B 19、 C 20、A 二、填空题 1、顺序存储结构 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)

8、/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,jlchild=null & p-rchlid=null 4、(1) +a*b3*4-cd (2)18 5、9 6、12 7、(1)2k-1 (2)2k-1 8、(1)2H-1 (2)2H-1 (3)H=? log2N? +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、

9、 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、 D3、 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

10、 (2)n2+n3 2、21 3、(1) FEGHDCB (2)BEF (该二叉树转换成森林，含三棵树，其第一棵树的先根次序 是 BEF) 籟丛妈羥为贍偾蛏练淨槠挞曉。 4、二叉树 5、2 6、 (1)1(2)yTchild(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，2C8、B9、1B ， 2

11、B， 3D 10、B 11、C 12、D 13、D 14、 1C，2C15、A16、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、因未给出存储结构，答案不唯一。本题按邻接表存

12、储结构，邻接点按字典序排列。 第七章图(1-2) 一、选择题： 1、A 2、 1 C，2BDE3 、 1C，2A，3B，4A 4、A5、 B 6、 D 7、 A8、 C 渗釤呛俨匀谔鱉 调硯錦鋇絨钞。 9、B 二、填空题 1 、普里姆( prim )算法和克鲁斯卡尔( Kruskal )算法 2、克鲁斯卡尔 3、边稠密边稀疏 4、(1)( Vi，Vj )边上的权值 都大的数(2) 1 负值 ( 3)为负边铙誅卧 泻噦圣骋贶頂廡缝勵罴。 5、不存在环 6、递增 负值 7、O(n2) 8、50,经过中间顶点 9、 (1)活动 ( 2)活动间的优先关系 ( 3)事件 ( 4)活动边上的权代表活动持续

13、 时间 10、关键路径 11、(1)某项活动以自己为先决条件 ( 2)荒谬 (3)死循环 12、(1)零 (2)Vk 度减 1，若 Vk 入度己减到零，则 Vk 顶点入栈(3)环 查找 一、选择题： 1、 A 2、(1)D，(2)C3、 D4、 D5、 C 6、 C 7、 D8、 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)

14、哈希函数 (2)解决冲突的方法 (3)选择好的哈希函数 (4)处理冲突的方法 (5)均匀 (6)简单 9、AVL 树(高度平衡树，高度平衡的二叉排序树) ，或为空二叉树，或二叉树中任意结点 左子树高度与右子树高度差的绝对值小于等于1。贓熱俣阃歲匱阊邺镓騷鯛汉鼉。 10、小于等于表长的最大素数或不包含小于 20 的质因子的合数 11、? log 2n+1 第九章 查找 一、选择题： 1、 C2、 C 3、 B4、 B 5、 D 6、 C 7、 A,C 8、 D 9、 D 11、 D 12、 (1)D，(2)C 13、 C 二、填空题 10、 C 1、 k(k+1)/2 2、 (1 )顺序存储或链

15、式存储(2)顺序存储且有序(3)块内顺序存储，块间有序(4) 散列存储 3、结点的左子树的高度减去结点的右子树的高度 4、(1)顺序表 (2)树表(3)哈希表 (4)开放定址方法 (5) 链地址方法 (6)再哈希 (7) 建立公共溢出区 5、直接定址法 6、37/12 7、主关键字 8、左子树右子树 9、插入删除 10、(1)126 (2)64 第十章 排序 一、选择题： 1、 D2、 D 3、D 4、B 5、B 6、 B 7 、C ,E 8、A 9、C10、C，D,F 11、 (1) D,C (2)A，D， F (3)B (4)A ， C， FB，D， E12、C，D 蒌鍥铃氈淚跻馱釣 。 14 、B,D 15、D D 17 、C 18、A 19、 A20、 C 21、 C 22、 B 23、 C 24、C 25、A 26、 C 27、 D 28、 C 29、B 30、C,B 31、 D 32、 D 33、 A 34、D 35、A 36、 A 37、 A 38、 C 39、B 40、C 41、 C 42、 B 43、 A 44、B 45、A 46、 C 47、 B ,D 48、 D 49、D 50、 D 51、 C52、 E,G53、 B54、 C 55、