第7章 排序 习题参考答案

FOXPRO基础及应用第7章作业一、单选题（每小题4.35分，共100.05分，得分 100.05 分）1、视图设计器中包括的选卡有_______。

A、更新条件、筛选、字段B、更新条件、排序依据、显示C、显示、排序依据、分组依据D、联接、显示、排序依据你的回答： A (√) 参考答案：A2、参照完整性规则不包括______。

A、更新规则B、查询规则C、删除规则D、插入规则你的回答： B (√) 参考答案：B3、要显示"参照完整性"，可以________。

A、从"数据库设计器"快捷菜单中选择"编辑参照完整性"选项B、其它选项都可以C、选择"数据库"菜单中的"编辑参照完整性"选项D、在数据库设计器中双击两个表之间的关系按钮，然后在"编辑关系"对话框中选择"参照完整性"按钮你的回答： B (√) 参考答案：B4、下列关于视图和查询的叙述中，错误的是________。

A、可以把视图当作数据库的一个定制的虚拟表B、视图被分为本地视图和远程视图两大类C、可以把查询的结果保存到一个新的数据表中D、对查询结果和视图数据的修改都会影响数据源你的回答： D (√) 参考答案：D5、查询设计器和视图设计器的主要不同表现在于________。

A、查询设计器没有"更新条件"选项卡，有"查询去向"选项B、查询设计器有"更新条件"选项卡，没有"查询去向"选项C、视图设计器没有"更新条件"选项卡，有"查询去向"选项D、视图设计器有"更新条件"选项卡，也有"查询去向"选项你的回答： A (√) 参考答案：A6、下面有关对视图的描述正确的是______。

第7章习题及参考答案7.1 命名下列化合物。

OH OHOHO CH 3CH 3PhCHCH 2CH 2CH 3OHC 2H 5OCH 2CH 2O C 2H 5(7)(8)(9)(10)CH 3OHNO 2OCH 2OHCH 3OCH 2CH 3CH 3CH 3H O HO CH 3(11)(12)(13)(14)解：(1) 4-丙基-4-庚醇 (2) 2-甲基-3-戊炔-2-醇(3) 3-氯-2-溴-1-丁醇 (4) (E )-2,3-二甲基-4-溴-2-戊烯-1-醇 (5) (2R ，3R )-3-甲基-4-戊烯-2-醇 (6) (E )-2-丁烯-1，4-二醇 (7) 4-环戊烯-1，3-二醇 (8) 3-甲基-5-甲氧基苯酚 (9) 1-苯基-1-丁醇 (10) 乙二醇二乙醚 (11) 2-硝基-1-萘酚 (12) 4-甲氧基环己基甲醇 (13) 1,2-环氧丁烷 (14) (2S ，3R )-2，3-二甲氧基丁烷7.2 写出下列化合物的结构式。

(1) 3,3-二甲基环戊醇 (2) 肉桂醇(3) 环戊基叔丁基醚 (4) 3-环己烯基异丙基醚 (5) 顺-1,2-环己二醇 (6) 2,3-二巯基-1-丙醇 (7) 4-丁基-1,3-苯二酚 (8) 二苯并-18-冠-6 解：CH CHCH 2OHOHC H 3CH 3(1)(2)OOC(CH 3)3CH(CH 3)2(3)(4)SHSHOH OHCH 2CH CHOH(5)(6)OHOHC(CH 3)3O OOOO O (7)(8)7.3 将下列化合物按沸点降低的顺序排列成序。

（1）丙三醇，乙二醇二甲醚，乙二醇，乙二醇单甲醚 （2）3-己醇，正己醇，正辛醇，2-甲基-2-戊醇解：（1）丙三醇＞乙二醇＞乙二醇单甲醚＞乙二醇二甲醚 （2）正辛醇＞正己醇＞3-己醇＞2-甲基-2-戊醇7.4 将下列各组化合物按与卢卡斯试剂作用的速率快慢排列成序。

数据结构（C语言版）（第2版）课后习题答案数据结构（C语言版）（第2版）课后习题答案目录第1章绪论1 第2章线性表5 第3章栈和队列13 第4章串、数组和广义表26 第5章树和二叉树33 第6章图43 第7章查找54 第8章排序65 第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，±1，±2，。

}，字母字符数据对象是集合C={‘A’，‘B’，。

，‘Z’，‘a’，‘b’，。

，‘z’}，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

第7章练习P165作业布置：P1651、21．已知文法A→aAd | aAb |ε，判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。

解：拓广文法为G'，增加产生式S'→A若产生式排序为：0 S'→A 1 A→aAd 2 A→aAb 3 A→ε由产生式知：从在I0、I2中：A→•aAd和A→•aAb为移进项目，A→•为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。

在I0、I2中：Follow(A)∩{a}= {d, b, #}∩{a}=φ所以在I0状态下面临输入符号为a时移进，为{d, b, #}时归约，为其他时报错。

因此在I0、I2中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。

下面是文法的2、若有定义二进制数的文法如下：S→L.L|LL→LB|BB→0|1（1）试为该文法构造LR分析表，并说明属哪类LR分析表。

（2）给出输入串101.110的分析过程。

答：（1）拓广文法为G′，增加产生式S′→S，若产生式排序为：0 S' →S 1 S →L.L 2 S →L 3 L →LB4 L →B5 B →06 B →1从S'→状态项目集经过符号到达的状态0 S'→•S S 1 S→•L.L L 2 S→•L L 2 L→•LB L 2 L→•B B 3 B→•0 0 4 B→•1 1 51 S'→S•2 S→L•.L . 6 S→L•L→L•B B 7 B→•0 0 4 B→•1 1 53 L→B•4 B→0•5 B→1•6 S→L.•L L 8 L→•LB L 8 L→•B B 3 B→•0 0 4 B→•1 1 57 L→LB•8 S→L.L•L→L•B B 7 B→•0 0 4 B→•1 1 5在I2中：B→•0和B→•1为移进项目，S→L•为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。

《数据结构（C语言版第2版）》（严蔚敏著）第七章练习题答案第7章查找1．选择题（1）对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）。

A．(n-1)/2B．n/2C．(n+1)/2D．n答案：C解释：总查找次数N=1+2+3+…+n=n(n+1)/2，则平均查找长度为N/n=(n+1)/2。

（2）适用于折半查找的表的存储方式及元素排列要求为（）。

A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序答案：D解释：折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

（3）如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用()查找法。

A．顺序查找B．折半查找C．分块查找D．哈希查找答案：C解释：分块查找的优点是：在表中插入和删除数据元素时，只要找到该元素对应的块，就可以在该块内进行插入和删除运算。

由于块内是无序的，故插入和删除比较容易，无需进行大量移动。

如果线性表既要快速查找又经常动态变化，则可采用分块查找。

（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。

若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败。

A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50答案：A解释：表中共10个元素，第一次取⎣(1+10)/2⎦=5，与第五个元素20比较，58大于20，再取⎣(6+10)/2⎦=8，与第八个元素70比较，依次类推再与30、50比较，最终查找失败。

（5）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。

A．3B．4C．5D．6答案：B解释：22个记录的有序表，其折半查找的判定树深度为⎣log222⎦+1=5，且该判定树不是满二叉树，即查找失败时至多比较5次，至少比较4次。

（6）折半搜索与二叉排序树的时间性能（）。

第七章图（参考答案）7．1（1）邻接矩阵中非零元素的个数的一半为无向图的边数；（2）A[i][j]= =0为顶点，I 和j无边，否则j和j有边相通；（3）任一顶点I的度是第I行非0元素的个数。

7．2（1）任一顶点间均有通路，故是强连通；（2）简单路径V4 V3 V1 V2;（3）0 1 ∞ 1∞ 0 1 ∞1 ∞ 0 ∞∞∞ 1 0邻接矩阵邻接表（2）从顶点4开始的DFS序列：V5,V3,V4,V6,V2,V1（3）从顶点4开始的BFS序列：V4,V5,V3,V6,V1,V27．4（1）①adjlisttp g; vtxptr i,j; //全程变量② void dfs(vtxptr x)//从顶点x开始深度优先遍历图g。

在遍历中若发现顶点j，则说明顶点i和j间有路径。

{ visited[x]=1; //置访问标记if (y= =j){ found=1;exit(0);}//有通路，退出else { p=g[x].firstarc;//找x的第一邻接点while (p!=null){ k=p->adjvex;if （!visited[k]）dfs(k);p=p->nextarc;//下一邻接点}}③ void connect_DFS (adjlisttp g)//基于图的深度优先遍历策略，本算法判断一邻接表为存储结构的图g种，是否存在顶点i //到顶点j的路径。

设 1<=i ,j<=n,i<>j.{ visited[1..n]=0;found=0;scanf (&i,&j);dfs (i);if (found) printf （” 顶点”,i,”和顶点”,j,”有路径”）；else printf （” 顶点”,i,”和顶点”,j,”无路径”）；}// void connect_DFS(2)宽度优先遍历全程变量，调用函数与（1）相同，下面仅写宽度优先遍历部分。

第七章图一、选择题1．图中有关路径的定义是（）。

【北方交通大学 2001 一、24 （2分）】A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列C．由不同边所形成的序列 D．上述定义都不是2．设无向图的顶点个数为n，则该图最多有（）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2【清华大学 1998 一、5 （2分）】【西安电子科技大 1998 一、6 （2分）】【北京航空航天大学 1999 一、7 （2分）】3．一个n个顶点的连通无向图，其边的个数至少为（）。

【浙江大学 1999 四、4 (4分)】A．n-1 B．n C．n+1 D．nlogn；4．要连通具有n个顶点的有向图，至少需要（）条边。

【北京航空航天大学 2000 一、6(2分）】A．n-l B．n C．n+l D．2n5．n个结点的完全有向图含有边的数目（）。

【中山大学 1998 二、9 （2分）】A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）6．一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。

A．0 B．1 C．n-1 D．n【北京邮电大学 2000 二、5 （20/8分）】7．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。

【哈尔滨工业大学 2001 二、3 （2分）】A．1/2 B．2 C．1 D．48．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( )。

【中山大学1999一、14】A．5 B．6 C．8 D．99．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。

A．逆拓扑有序 B．拓扑有序 C．无序的【中科院软件所1998】10．下面结构中最适于表示稀疏无向图的是（），适于表示稀疏有向图的是（）。

A．邻接矩阵 B．逆邻接表 C．邻接多重表 D．十字链表 E．邻接表【北京工业大学 2001 一、3 (2分)】11．下列哪一种图的邻接矩阵是对称矩阵？（）【北方交通大学 2001 一、11 （2分）】A．有向图 B．无向图 C．AOV网 D．AOE网12．从邻接阵矩可以看出，该图共有（①）个顶点；如果是有向图该图共有（②）条弧；如果是无向图，则共有（③）条边。

第六章图1、填空题一个有 n 个结点的无向图中,所有顶点的度数之和等于所有边数之和的 _2__倍。

一个有 n 个结点的强连通图,最多有 _n(n-1_/2__条边,最少有 ___n-1_ 条边。

在一个无向图中,所有顶点的度数之和等于所有边数之和的 __2____倍。

2、判断题1无向图的邻接矩阵一定是对称矩阵。

(√2有向图的邻接矩阵一定是对称矩阵。

(×3图的深度优先搜索路径是唯一的。

(×4图的广度优先搜索路径不是唯一的。

(√5一个图可能存在多棵最小生成树。

(√6无向图的邻接矩阵一定是对称的,有向图的邻接矩阵一定是不对称的。

(√7图的关键路径是指从源点到汇点的最短路径。

(×8用邻接矩阵法存储图,占用的存储空间数量只与图中边数有关,与结点个数无关。

(×9对一个图分别进行深度优先搜索和广度优先搜索,得到的结点序列一定是相同的。

(×10图的关键路径是指从源点到汇点的最长路径。

(√3、选择题1一个无向连通图的生成树是含有该连通图的全部顶点的 __A__。

A 、极小连通子图B 、极小子图C 、极大连通子图D 、极大子图 2具有 e 条边的有向图,它的邻接表中有 _D__个弧结点。

A 、 e-1B 、 2eC 、 2(e-1D 、 e3如果某图的邻接矩阵是对角线元素均为零的上三角矩阵,则此图是 __D__A 、无向图B 、完全图C 、强连通图D 、有向无环图4顶点个数为 n 的有向图最多有 __D_条弧。

A 、 n-1B 、 n(n-1/2C 、 n(n+1/2D 、 n(n-1应用题:1. 请给出图 1的所有最小生成树。

(10分图 1共两棵。

第一棵为:(5分错一条边扣 1分。

第二棵为:(5分错一条边扣 1分。

2. 请给出图 2的所有拓扑排序序列。

(16答案如下:仅有两个第一个:abcdefgh (错一个字符扣 1分第二个:abcdegfh (错一个字符扣 1分3、对于有向无环图(如图 3,写出它的所有不同的拓扑有序序列。

习题7 图7.1 单项选择题1．在一个图中，所有顶点的度数之和等于所有边数的____倍。

A. 1/2B. 1C. 2D. 42．任何一个无向连通图的最小生成树。

A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。

A. 1/2B. 1C. 2D. 44．一个有n个顶点的无向图最多有____条边。

A. nB. n(n-1)C. n(n-1)/2D. 2n5．具有4个顶点的无向完全图有____条边。

A. 6B. 12C. 16D. 206．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。

A. 5B. 6C. 7D. 87．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。

A. nB. n+1C. n-1D. n/28．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。

A. nB. (n-1)2C. n-1D. n29．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。

①A. n B. n+1 C. n-1 D. n+e②A. e/2 B. e C.2e D. n+e10．已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列为__②__。

①A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,bC. a,e,b,c,f,dD. a,c,f,d,e,b图 7.1 一个无向图11．已知一有向图的邻接表存储结构如图7.2所示。

⑴根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。

A. v1,v2,v3,v5,v4B. v1,v2,v3,v4,v5C. v1,v3,v4,v5,v2D. v1,v4,v3,v5,v2⑵根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。