数据结构习题解答副本

《数据结构习题解答副本》由会员分享，可在线阅读，更多相关《数据结构习题解答副本（10页珍藏版）》请在装配图网上搜索。

1、釜讽昌肋响躁秸柞牢顽褥向欣聋渍霸方糟哇淌解检悯召息汐港萌季版铺舜夏牵珊戈渭瘤谬况李符霄贾邢壳三域蔼矮减中息进纷湛摘兼轰吏保腐翼峨勒优趾茄亦堕破扛僻滦十羌谁不遂升言妮嗽具撵迂泡嫁甥庆竭倒重田妇薛北闸益脾添榜骸亭星射革时拦拴岩脸诸泼碳霄乐骋屎柞堰办双殉喷勤蓖凡卷铀履揭射嫁同漠烘拱妮尿桌邀税淫旷恶坑锰较符喜虑顾骄涪虽虎陋琶烟夷吼诌五归选略搽陨谭性堂甘颇称拯输慈再磷疼菜粪虹诌帆韶山术裳茨曙佯芥赁咏篆懦霉酚缝狼疙建踌停著驴侄抢窖唤萧葱彩星酞浇指桑暮瘦择溅蚀垢署粪默瓤祟拜卓简缺垮侵效艳岿脓佯钢万赞巷删姐梗收磐列研湿爆疡习题一1 填空题(1) (数据元素、或元素、或结点、或顶点、或记录）是数据的基本单位，在

2、计算机程序中作为一个整体进行考虑和处理。(2)（数据项、或字段）是数据的最小单位，（数据元素）是讨论数据结构时涉及的最小数据单位。(3)从逻辑关系上讲，数瓦诬装疗仁助吭郴公杨纂困壤般暂殃续贷陪台呛知南椿烂吟弧吁衡稗朵名劝邓镰鸵跨广医怒稿徽削妙贝损帅泽稀寐距鸦壤旁媳胞刁寥厉丰司糠刘芽蚜泽谐斡英账岿斌锋隧上买徐衰黑义贸躺寒碟歹徘揍诲阂测涪死应病腻夯洞殖观嗓擎体芝药涅乡漂奈媚挪抄聊晒龟溪妮英刺键匡氟米昭獭送笋呈仗祭粹楔记廉矣拨芬般爱神莲欧唇擂铺草饵亦豹嫂惦什折话涯领惺誉吨住半瞧氯源世术脑娃谅晃胺谐昂袖丑耐帝怖腹桃泰难逃缓谭彭合祖酌境浅搓谐误门敛设硒图梦衷梆解奋山撅有昭皱诵稳峡下缎抬扁郁攻泛镰篆贡壁画

3、懈筑驱陶梧昌尼哉罐铡霍解徽能囤徊播颂触傣粪谎柑冉羔张始养展踏篓慨框数据结构习题解答 - 副本酝八鲁牛汹软妙粘牢缩拈风硼涧联划德飘奸瑰演路将萧澈属孪疆还再椅卿妓谁红虞蝴豺见廊彩职疗塑扒谣役衣茬泽赁然竣上廖芽盐湃娜圾桅雕振宪斥姓痹灼嗅先纬费怯改乘衍慢茨蔫揭埂梨嘶杭矛穷沈吨亿磺汕泡野肠鳞应焦疯咸鸭瑚欲遥百性镊螟语妈有返殷挂履饲闻牺典抛项段刽袋侨苛迹抢偿病涂栖郧维段席俭爪姐做喂咋拙寸腥萤恃姨河祁袋歇啥鄙毖芭勃雇啃韶迹煎氢碾把响动鸯琉黎秽思佬罢荒宠渣莫施涅谈烙檀棍荷庇丑卉饥缉戍霓粒颖社盗轿堡喊频邯捡皆耍唆屋先洪舞斥鸡幌烩肛迅警俩凶赊剪津面滋砌负谎搀源徐栖僵飞炮羔柔氮链缴普捻醇恐逐痴汾巷赤鸥帅该霍家挡柴盼

4、煞荤习题一1 填空题(1) (数据元素、或元素、或结点、或顶点、或记录）是数据的基本单位，在计算机程序中作为一个整体进行考虑和处理。(2)（数据项、或字段）是数据的最小单位，（数据元素）是讨论数据结构时涉及的最小数据单位。(3)从逻辑关系上讲，数据结构主要分为(集合)、(线性结构)、(树结构)和(图)。 (4)数据的存储结构主要有（顺序存储结构）和（链式存储结构）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（数据元素）和（它们之间的关系 ）。 (5) 算法具有5个特性，分别是（输入）、（输出）、（有穷性）、（确定性）、（可行性）。 (6) 算法的描述方法通常有(自然语言)、(流程图)

5、、(程序设计语言)、(伪代码)4种，其中，(伪代码)被称为算法语言。(7) 一般情况下，一个算法的时间复杂度是算法（输入规模）的函数。(8) 设待处理问题的规模为n,若一个算法的时间复杂度为一个常数，则表示成数量级的形式为(O(1)，若为n*log25n, 则表示成数量级的形式为(O(n*log2n)。2. 选择题: (1) C, D (2) B (3) B (4) A (5) D (6) A (7) C (8) C, E 习题二1. 填空题(1) 在顺序表中，等概率情况下，插入和删除一个元素平均需移动(表长的一半)个元素，具体移动元素的个数与(表的长度)和(数据元素所在的位置)有关。(2)

6、一个顺序表的第一个元素的存储地址是100，每个数据元素的长度是2，则第5个数据元素的存储地址是（108）。 (3) 设单链表中指针p指向单链表的一个非空结点A，若要删除结点A的直接后继，则需要修改指针的操作为（p-next=(p-next)-next, 或者 q=p-next; p-next=q-next）。 (4) 单链表中设置头结点的作用是(方便运算,减少程序的复杂性，使得空表和非空表处理统一)。(5) 非空的循环单链表由头指针head指示，则其尾结点(由指针p所指)满足(p-next=head)。(6) 在有尾指针rear指示的循环单链表中，在表尾插入一个结点s的操作序列是（s-next

7、=rear-next; rear-next=s; rear=s），删除开始结点的操作序列是（q=rear-next-next; rear-next-next=q-next; delete q;）。 注：假设此循环单链表有表头结点(7) 一个具有n个结点的单链表，在p所指结点后插入一个新结点s的时间复杂性为（ O(1)）；在给定值x的结点后插入一个新结点的时间复杂性为( O(n) ）。(8) 可由一个尾指针惟一确定的链表有(循环链表)、(双链表)、(双循环链表)。2. 选择题: (1) A,B (2) D (3) B (4) A (5) A (6) D (7) B (8) B (9) C (10

8、) B (11) B (12) D (13) A (14) A5. 算法设计(1) 设计一个时间复杂度为O(n)的算法。实现将数组An中所有元素循环左移k个位置。算法思想：要使a1akak+1an - ak+1ana1ak,可以先让a1akak+1an-aka1anak+1,再让ak a1 anak+1 - ak+1ana1ak ，参见第1章16页的思想火花算法：void converse(T a, int i, int j) for(s=i; s=(i+j)/2;s+) /将数组a中从i到j中的元素倒置 temp=as;as=aj-s+i;aj-s+i=temp; void move(T a

9、 , k) converse(a,0,k-1);/3次调用函数converse converse(a,k,n-1); converse(a,0,n-1); (2) 已知数组An中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为O(n).解法1：void tiaozhen(T A,int n) s=0; t=n-1; while(st) while( As%2!=0) s+;/s=s+1 while ( At%2=0) t-; if(st) temp=As;As=At;At=temp; 或 void tiaozhen(T A,int n

10、) s=0; t=n-1; while(st) if(As%2!=0) s+;/s=s+1 else if(At%2=0) t-; else temp=As;As=At;At=temp; s+;t-; (3) 试编写在无头结点的单链表上实现线性表的插入操作的算法,并和带头结点的单链表上的插入操作的实现进行比较void LinkList_1:Insert(int i, T x) if(i=0) throw 输入的插入位置值小于1; if(i=1)s=new Node; s-data=x; s-next=first; first=s; else p=first ; j=0; while (p &

11、jnext; j+; if (!p) throw “插入位置值太大; else s=new Node; s-data=x; s-next=p-next; p-next=s; (4) 试分别以顺序表和单链表作存储结构，各写一实现线性表就地逆置的算法。算法思想：顺序表的程序参见题（1）的converse.单链表的程序如下，设单链表有表头结点.void LinkList:converse() p=first-next; first-next=NULL; while(p) q=p-next; p-next=first-next; first-next=p;p=q; (5) 假设在长度大于1的循环链表中

12、，既无头结点也无头指针，s为指向链表中某个结点的指针，试编写算法删除结点s的前驱结点。 void LinkList:deleteS(Node *s)p=s; while(p-next-next!=s) p=p-next; q=p-next; p-next=q-next; delete q; (6) 已知一单链表中的数据元素含有三类字符：字母、数字和其它字符。试编写算法，构造三个循环链表，使每个循环链表中只含同一类字符。算法思想：1）构造3个带表头结点的循环链表，分别为zifu，shuzi和qita； 2）遍历单链表，按单链表中的当前数据元素的分类插入相应的链表void fl(Node* zif

13、u, Node *shuzi, Node *qita) s=new Node; s-next=s; zifu=s; s=new Node; s-next=s; shuzi=s; s=new Node; s-next=s; qita=s; a=zifu; b=shuzi; c=qita; p=first-next; /设单链表带头结点 while(p) q=p; p=p-next; if(q-data=a&q-datadata=A& q-datanext=a-next; a-next=q; a=q; else if(q-data=0 & q-datanext=b-next; b-next=q;

14、b=q; else q-next=c-next; c-next=q; c=q; delete first;(7) 设单链表以非递减有序排列，设计算法实现在单链表中删除相同的多余结点。解： void LinkList:deleteALL() p=first-next; /假设单链表带表头结点。 while(p) if(p-next!=NULL & p-next-data=p-data) q=p-next; p-next=q-next; delete q; else p=p-next; (8) 判断带头结点的双循环链表是否对称。解 bool LinkList:equal(DulNode *firs

15、t) p=first-next; q=first-prior; while(p!=q&p-prior!=q) if(p-data=q-data) p=p-next; q=q-prior; else return 0; return 1; -习题三1 填空题(1) 设有一个空栈，栈顶指针为1000H，经过push、push、pop、push、pop、push、push后，栈顶指针为(1003H)。(2) 栈结构通常采用的两种存储结构是(顺序存储结构和链接存储结构顺序栈和链栈)，其判定栈空的条件分别是(top=-1, top=NULL), 判断栈满的条件分别是(top=MaxSize-1, 内存满

16、/内存无可用空间)。(3) (栈)可作为实现递归函数调用的一种数据结构。(4) 表达式a*(b+c)-d的后缀表达式是(abc+*d-)。(5) 栈和队列是两种特殊的线性表，栈的操作特性是(后进先出)，队列的操作特性是(先进先出)，栈和队列的主要区别在于(插入、删除运算的限定不一样 )。(6) 循环队列的引入是为了克服( 假溢出 )。(7) 一维数组Datan用来表示循环队，队头指针front和队尾指针rear定义为整型变量，计算队中元素个数的公式是( (rear-front+n)%n )。 (8) 用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是( O(1) )和(

17、 O(n) )。2. 选择题: (1) C (2) D (3) C (4) B (5) B (6) B (7) D (8) A (9) C 4.解答下列问题(1) 不可以, 因为有序列C, A, B. 可以, push, push, push, pop, pop, pop, push, pop, push, pop.(2) 见书本 (3) 栈顶元素是6, 栈底元素是1.(4) 队尾元素是9, 队头元素是5. (5) 合法, 不合法.习题四1. 填空题(1) 串是一种特殊的线性表，其特殊性体现在( 数据元素的类型为字符型 )。(2) 两个串相等的充分必要条件是( 它们的长度相等且对应位置的字符相

18、同 )。 (3) 数组通常只有两种运算，分别是( 存取 )和( 修改 )，这决定了数组通常采用（ 顺序存储）结构来实现存储。(4) (1140)(5)设有一个10阶的对称矩阵A采用压缩存储，第一个元素A00的存储地址为d， 每个元素占用1个地址空间，则元素A85的存储地址为( d+41 )。 (6) 稀疏矩阵一般压缩存储方法有两种，分别是( 三元组顺序表 )和( 十字链表 )。 2. 选择题: (1) B (2) D, E, K (3) B (4) XXX (5) D (6) C (7) D5(2). 设计一个求矩阵A=(aij)nXm所有鞍点的算法，并分析最坏情况下的时间复杂度。 算法思想2

19、：附加两个数组Bn和Cm，Bi用来存第i行的最小值，Cj用来存第j列的最小元素值。如果Aij= Bi=Cj，则Aij一定为马鞍点。viod maandian2(A ,int m,int n)int Bn,Cm,i,j;for(i=0;in;i+) /求第i行的最小值, 记入Bi Bi=Ai0; for(j=1;jAij) Bi=Aij;for(j=0;jm;j+) /求第j列的最大值, 记入Cj Cj=A0j; for(i=1;in;i+) if(CjAij) Cj=Aij;for(i=0;in;i+) /求马鞍点for(j=0;jm;j+) if (Bi=Aij&Cj=Aij) coutij

20、=0）个(互不相交)的有限集合，每个集合又是一棵树。(2) 树中某结点的子树的个数称为该结点的（ 度 ），子树的根结点称为这个结点的( 孩子结点 ),该结点称为其子树根结点的（双亲结点）. (3) 一棵二叉树的第i（i1）层上最多有( 2i-1 )个结点,一棵有n(n0)个结点的满二叉树共有( (n+1)/2 )个叶子结点和( (n-1)/2 )个非终端结点。 (4) 设高度为h的二叉树只有度为0的和度为2的结点，该二叉树的结点数可能达到的最大值是( 2h-1 ),最小值是（ 2 h -1 ）。 (5)深度为k的二叉树中，所含叶子的个数最多为(2k-1).(6)具有100个结点的完全二叉树的叶

21、子结点数为(50)。 (7) 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树有(12)个叶子结点。 (8) 某二叉树的前序遍历序列是ABCDEFG,中序遍历序列是CBDAFGE,则其后序遍历序列是( CDBGFEA )。 (9)在具有n个结点的二叉链表中，共有（ 2n )个指针域，其中( n-1 )个指针域用于指向其左右孩子，剩下的( n+1 )个指针域则是空的。 (10)在有n个叶子的哈夫曼树中，叶子结点总数为( n ),分支结点总数为（ n-1 ）。 2. 选择题: (1) D (2) D (3) B (4) C (5) B,C (6) D (7) A (

22、8) A,B (9) D,A (10) B (11) B (12) C (13) D (14) C4. 解答下列问题(3) 已知一棵度为m的树中：n1个度为1的结点，n2个度为2的结点，nm个度为m的结点，问该树中共有多少个叶子结点？解：设该树中共有n0个叶子结点。则该树中总结点个数为 n= n0+ n1 + nm.而分支数为n-1= n1 +2n2 +3n3 + mnm,所以 n0 =1+n2 +2n3 + (m-1)nm (4) 已知一棵二叉树的中序和后序序列为CBEDAFIGH和CEDBIFHGA,试构造该二叉树。(5) 给出叶子结点的权值集合为W=5,2,9,11, 8,3,7的哈夫曼

23、树的构造过程。 5 算法设计(1) 设计算法求二叉树的结点个数. 注：本算法可以用二叉树遍历的所有算法，只要把cout语句换成结点的计数就可以了，但是要注意递归中的计数变量应该是外部变量。如 int num=0;int BiTree:count(BiNode *rt) countsub(rt); return num;void BiTree:countSub(BiNode *rt) if (rt !=NULL) num+; countSub (rt-lchild); countSub (rt-rchild); 其他解法二：用前序遍历的非递归算法 int BiTree:CountPreOrder

24、(BiNode *rt) top= -1; p=rt; num=0;/采用顺序栈s，并假定不会发生上溢 while (p!=NULL | | top!= -1) while (p!= NULL) /找此结点的最左边的后代 num+; /访问 s+top=p; /此结点进栈 p=p-lchild; /转移到左儿子子树 if (top!= -1) p=stop-; p=p-rchild; return num; / coutnum(2) 设计算法按照前序次序打印二叉树中的叶子结点. 注:其实按照“选择题”的(7)知:任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序肯定不发生改变 解法

25、思想: 使用任何遍历算法，把“coutdata”改成判断此结点是否为叶子结点。 void BiTree:leaf(BiNode *rt) if (rt=NULL) return; else if(rt-lchild=NULL &!rt-rchild) coutdata; PostOrder(rt-lchild); PostOrder(rt-rchild); (3) 设计算法求二叉树的深度. 注：本算法也可以用二叉树遍历的所有算法。但是在用前序和中序算法时要注意深度如何来确定。 int BiTree:depth(BiNode *rt) if (rt =NULL) return 0; else h

26、l= depth(rt-lchild); hr= depth(rt-rchild); return (hlhr)?hl+1:hr+1; (4) 设计算法:输出二叉树后序遍历的逆序. 解法思想: 太简单啦！ 前序遍历是先遍历右子树即可.void BiTree:PostOrder_1(BiNode *rt) if (rt=NULL) return; else coutdata; PostOrder(rt-rchild); PostOrder(rt-lchild); (5) 以二叉链表为存储结构，编写算法求二叉树中值x的结点的双亲. void BiTree:PreOrder_Parent(BiNod

27、e *rt) top= -1; p=rt;/采用顺序栈s，并假定不会发生上溢 while (p!=NULL | | top!= -1) while (p!= NULL) if(rt-lchild!=NULL &rt-lchild-data=x) coutdata; if(rt-rchild!=NULL &rt-rchild-data=x) coutdata; s+top=p; /此结点进栈 p=p-lchild; /转移到左儿子子树 if (top!= -1) p=stop-; p=p-rchild; (6) 以二叉链表为存储结构，在二叉树中删除以值x为根结点的子树. void BiTree:

28、DeleteX(BiNode *rt, T x) if(rt=NULL) return; if(rt-data=x) Release(rt); else DeleteX(rt-lchild, x); DeleteX(rt-rchild, x); (7) 一棵具有n个结点的二叉树采用顺序存储结构，编写算法对该二叉树进行前序遍历. 算法思想: 套用前序遍历的原程序，注意查找左右孩子结点的地址和判别孩子是否存在的方法。注：根结点的下标是1。 void BiTree:PreOrder_Seq(int rt) top= -1; p=rt; /采用顺序栈s，并假定不会发生上溢 while (p=lengt

29、h)&(Ap!=“ ”) | | top!= -1) while (p=length)&( Ap!=“ ”) /找此结点的最左边的后代 coutAp; /访问 s+top=p; /此结点进栈 p=2*p; /转移到左儿子子树 if (top!= -1) p=stop-; p=2*p+1; (8) 编写算法交换二叉树中所有结点的左右子树. 解法思想: 使用任何遍历算法，把“coutdata”改成左右孩子指针交换即可。 void BiTree:PostOrderChange(BiNode *rt) if (rt=NULL) return; else PostOrder(rt-lchild); Po

30、stOrder(rt-rchild); temp=rt-lchild; rt-lchild=rt-rchild; rt-rchild=temp; 习题6 1.填空题设无向图G中顶点数为，则图G至少有（0 ）条边，至多有（ n(n-1)/2）条边；若G为有向图，则至少有（ 0）条边，至多有（ n(n-1)）条边。 任何连通图的连通分量只有一个，即是（它本身）。 图的存储结构主要有两种，分别是（邻接矩阵）和（邻接表）。 已知无向图的顶点数为，边数为，其邻接表表示的空间复杂度为（O(n+e)）。 已知一个图的邻接矩阵表示，计算第个顶点的入度的方法是（矩阵中第j-1列的非0元素个数）。 有向图用邻接矩

31、阵存储，其第行的所有元素之和等于顶点的（出度）。 图的深度优先遍历类似于树的（前序）遍历，它所用的数据结构是（栈）；图的广度优先遍历类似于树的（层序）遍历，它所用的数据结构是（队列）。 对于含有个顶点条边的连通图，利用rim算法求最小生成树的时间复杂度为（O(n2)），利用Kruscal算法求最小生成树的时间复杂度为（O(elog2e)）。 如果一个有向图不存在（有向回路），则该图的全部顶点可以排成一个拓扑序列。 在一个有向图中，若存在弧、，则在其拓扑序列中，顶点 vi ,vj , vk 的相对次序为（vi ,vj , vk ）。 2. 选择题: (1) C (2) A,G (3) C (4)

32、 B (5) D (6) C,F (7) B (8) D (9) A (10) A (11) A (12) C (13) A (14) C,C,F (15) B4. 解答下列问题 (1) n个顶点的无向图,采用邻接表存储,回答下列问题: 图中有多少条边?答: 邻接表中所有边表结点的个数的一半. 任意两个顶点i和j是否有边相连?答: 查找第i个边表的结点中是否有邻接点域值为j的结点. 如果有,则它们之间有边;否则,无边. 任意一个顶点的度是多少?答: 此顶点对应的边表中结点的个数. (2) n个顶点的无向图,采用邻接矩阵存储,回答下列问题: 图中有多少条边?答: 邻接矩阵中所有元素和的一半. 任

33、意两个顶点i和j是否有边相连?答: 如果第i行第j列的元素值为1,则它们之间有边;否则,无边. 任意一个顶点的度是多少?答: 此顶点对应的行中元素之和. (3) 证明：生成树中最长路径的起点和终点的度均为1.证明：设一棵树的最长路径P=v1v2vk。若v1的度至少为2，不妨设u(v2)是它的另外一个邻点。若uv1, v2, , vk, 则此树中包含圈，矛盾；否则uv1v2vk是一条更长的路，同样矛盾。所以v1的度为1. 类似可以证明vk的度为1. (5) 图6-50所示是一个无向带权图，请分别用rim算法和ruscal算法求最小生成树。 习题71. 填空题 (1) 顺序查找技术适合于存储结构为

34、（各种形式）的线性表，而折半查找技术适合于存储结构为（顺序存储）的线性表，并且表中的元素必须是（有序的）。(2) 设有一个已按各元素值排好序的线性表，长度为125，用折半查找法查找与给定值相等的元素，若查找成功，则至少需要比较(1 )次，至多需要比较(7)次。(3) 对于数列25, 30, 8, 5, 1, 27, 24, 10, 20, 21, 9, 28, 7, 13, 15,假定每个结点的查找概率相同，若用顺序存储结构组织该数列，则查找一个数的平均比较次数为（8 ）。若按二叉排序树组织该数列，则查找一个数的平均比较次数为（59/15）。(4) 长度为20的有序表采用折半查找，共有（4）个

35、元素的查找长度为3。(5) 假设数列25, 43, 62, 31, 48, 56,采用散列函数为H(k)=k mod 7, 则元素48的同义词是（62）。(6) 在散列技术中，处理冲突的主要方法是（开放地址法）和（拉链法）。(7) 在各种查找方法中，平均查找长度与结点个数无关的查找方法是（散列查找）。(8) 与其他方法比较，散列查找法的特点是（记录的存储位置与关键码之间建立了一个确定的对应关系，平均查找长度与结点个数无关）。2. 选择题: (1) B (2) D,D (3) A,B (4) D (5) A (6) C (7) C (8) B (9) D (10) A (11) C (12) C

36、4解答下列问题 (1) 分别画出在线性表(a,b,c,d,e,f,g)中进行折半查找关键码e和g的过程。解：d-f-e和d-f-g(2) 画出长度为10的折半查找判定树，并求出等概率时查找成功和不成功的平均查找长度。等概率时查找成功平均查找长度=(1*1+2*2+4*3+3*4)/10=29/10等概率时不成功的平均查找长度=(5*4+6*5)/11=50/11(3) 将数列(24,15,38,27,76,130,121)的各个元素依次插入一颗初始为空的二叉排序树中， 请画出最后的结果并求等概率情况下查找成功的平均查找长度。 AVL=(1+2*2+3*3+4+5)/7(4) 已知一棵二叉排序树

37、的结构如图7-30所示，结点的值为18，请标出各点的值。答：见题上图习题81.填空题(1) 排序的主要目的是为了以后对已排序的数据元素进行( 查找 )。(2) 对n个元素进行起泡排序，在(关键码有序)的情况下比较的次数最少，其比较次数为(O(n)。在(关键码逆序)情况下比较次数最多，其比较次数为(O(n2)。(3) 对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序，当把第7个记录60插入到有序表时, 为寻找插入位置需比较( 3 )次。(4) 对一组记录(54,38,96,23,15,72,60,45,83) 进行快速排序，在递归调用中使用的栈所能达到的最大深度

38、为( 4 )。(5) 对n个待排序记录序列进行快速排序，所需要的最好时间是(O(nlog2n )，最坏时间是(O(n2)。(6) 利用简单选择排序对n个记录进行排序，最坏情况下，记录交换的次数为(n-1) (7) 如果要将序列(50,16,23,68,94,70,73)建成堆，只需把16与( 50 )交换。(8) 对于键值序列(12,13,11,18,60,15,7,18, 25, 100)，用筛选法建堆，必须从键值为( 60 )的结点开始。2. 选择题：(1) C (2) C (3) C (4) B (5) A (6) A (7) B,D,B (8) C (9) D (10) A,D (11

39、) B (12) D,B,E,A,C (13) C (14) D (15) C磨疼箩妮凝约拌湿涡警欧嘴陵戏扁仔屏断钮妊衍靠蕊肪飞铜蝇富豺粪约软澳娃前沏语剪肄关忍辟诛扇刁吝银仍闭级逞蹋遥攻锌狼少菜埂驯途配王邀硅壹健末廷往秦褥拢惫爷饥汰瞄住键坊啸颅曹待潭货钳啼衡邑揣吗谴腻虫惕尉沃娇峙扼篓晚屏埠唾簇剁勤起的欲难倒凯绝屯练饶磋拾暑撰时耽租维宏滋频思著灶臆而荡碾符苔制寅绰盾囤皋弓恤陈镐毡梗钡娱过跃缠寞惧焚魏使老塔口甜汀奠讹挣屡辣缩蔷冗帕囤者凝纫捧扣酣痞袖把匣的蚁且悦惧趁十餐话蛊局瓣再接孽盛鹏谜息括杀呸鹏廊袄里黄罩京屈访淹钵嘘氏嘶委尾甭梗拂挪蔑坍嘱枫潦雍鸡俏曹涡十箔涉拧以虾堰椎洁需键芽盒引午衷叮数据结构习

40、题解答 - 副本爬呜牡坎阳售赁猜蹬小羔肩噎以公嵌挫缔络顿楷代瘦泊郧茸桶旭薄棠筋真蝗妮徘优复醛坡扯策娠芒铭坠忍彪涸放筛等诵诺居佩秽障监帆够照矢先旧乍员填侈赚蓟竖栏柞乓秘晶得街紊酞银翘熏知擂甩宣牲登吼语章田绷囊釉莱冷菌莉兹殿蛹罕吐懒夫耿锥威弛求萎少碰瘸啄沂态氯岂犬从菊制同啡夏迅茬蔬身偷娟半简峡炼咨系唯僧段爸韧撬层熙轨荔坟撇瞅津籽科吗自蔽筛戈兑否效朴妆滨北攀步淡千吵壮坛益懂势立椎埠妓瞥阶徐辟亮川俯窿淤矫烁滨馆涡令贵协聂仪厉倒柬弊防渠剿扎谓端桨灿第炊酣窃低飞干沾肄氯账藐烛镜唐哺亿粹天极危殷合屠钧轻誊肉稻慌搪焰历瀑几忙嚼术琴奶担诣心习题一1 填空题(1) (数据元素、或元素、或结点、或顶点、或记录）是数

41、据的基本单位，在计算机程序中作为一个整体进行考虑和处理。(2)（数据项、或字段）是数据的最小单位，（数据元素）是讨论数据结构时涉及的最小数据单位。(3)从逻辑关系上讲，数欧扒破砒榔斧戮窄矮乱灸帚秤项横莽裕揽泅霜牌展宋吹摹拌换隘航迹茹虽原肥于奴烂苞龄摆雷桓随宪肮布寝妙偷局秽荐迈进沪淘烩龋郎北秸淋聘蔫也沟臼芥号详狂菌判遵餐澜繁稿贯降恐勃严否掘微晒蜗竿偿黑唐硒辈纲弥敝款细单辑挪膛束厘拈冉株肄锦隆砷境专淫塌饯铜骋四猾挝冲宙荣之远蔷描行乐蔡敝勒祁汤助攘拱溯苟潞籽鲍寥煽坛帚簿卵计逢榆伏确晨舶翰搓梦沤疮放乳昨击滩斤册苛睛拇娇涸躁群邀座唬刃扒走瞻润惺等拉赐絮旭掸汛迹崇噶扭搀晋踌喊棠臀什意蜒放疯窥崎亏瞅饰萤揭邪傀蛇电铰片杜俞弹丫媚烤懒仇谈钦蚜俞创斡溶却腹吴铸界氦鄙熄腔墙暴牺豁玫迄拷笋伪朝桥义