数据结构第四、五、六、七章作业答案

《数据结构第四、五、六、七章作业答案》由会员分享，可在线阅读，更多相关《数据结构第四、五、六、七章作业答案（28页珍藏版）》请在装配图网上搜索。

1、第四、五章 一、填空题1. 不包含任何字符（长度为0）的串 称为空串； 由一个或多个空格（仅由空格符）组成的串 称为空白串。2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 , “/”的位置为 3 。3. 子串的定位运算称为串的模式匹配； 被匹配的主串 称为目标串， 子串 称为模式。4、串的存储方式有顺序存储、堆分配存储和块链存储5、有一个二维数组A0:8,1:5,每个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素A0,1的地址是100，若按行主顺序存储，则A3,5的地址是176 和 A5,3的地址是208 。若按列存储，则A7,1 的地

2、址是128 ，A2,4的地址是216 。6、设数组a160, 170的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a32,58的存储地址为 8950 。7、 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标 、 列下标 和 元素值 。8、二维数组A1020采用列序为主方式存储，每个元素占10个存储单元，且A00的存储地址是2000，则A612的地址是32609、已知二维数组A2010采用行序为主方式存储,每个元素占2个存储单元,并且A105的存储地址是1000,则A189的存储地址是 1168 10、已知二维数组A10

3、20采用行序为主方式存储，每个元素占2个存储单元,并且A00的存储地址是1024, 则A618的地址是1300 11、两个串相等的充分必要条件是长度相等、对应位置的字符相同。12、二维数组A1020采用列序为主方式存储，每个元素占一个存储单元，并且A00的存储地址是200，则A612的地址是 200+（12*10+6）= 326 。二、单选题1、串是一种特殊的线性表，其特殊性体现在（ B ）可以顺序存储 数据元素是一个字符 可以链式存储 数据元素可以是多个字符2、设有两个串p和q，求q在p中首次出现的位置的运算称作（ B ） 连接 模式匹配 求子串 求串长3.设串s1=ABCDEFG，s2=P

4、QRST，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2), subs(s1, len(s2), 2)的结果串是（ D ）BCDEF BCDEFG BCPQRST BCDEFEF4.假设有60行70列的二维数组a160, 170以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a32,58的存储地址为（ A ）。（无第0行第0列元素）16902 16904 14454 答案A, B, C均不对5、下面关于串的的叙

5、述中，（ B ）是不正确的。A、串是字符的有限序列 B、空串是由空格构成的串C、模式匹配是串的一种重要运算 D、串既可以采用顺序存储，也可以采链式存储6. 设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B 1, n(n-1)/2 中，对下三角部分中任一元素ai,j(ij), 在一维数组B中下标k的值是( B )A、i(i-1)/2+j-1 B、i(i-1)/2+j C、i(i+1)/2+j-1 D、i(i+1)/2+j7. 有一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体

6、积是 A 个字节。假设存储数组元素A1,0的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是 B 。若按行存储，则A2,4的第一个字节的地址是 C 。若按列存储，则A5,7的第一个字节的地址是 D 。供选择的答案：AD：12 66 72 96 114 120 156 234 276 282 （11）283 （12）288答案：ABCD=12, 10, 3, 98、以下关于广义表的叙述中,正确的是（ A）A) 广义表是由0个或多个单元素或子表构成的有限序列B) 广义表至少有一个元素是子表C) 广义表不能递归定义 D) 广义表不能为空表9、设A是n*n的对称矩阵，将A的对角线及

7、对角线上方的元素以列为主的次序存放在一维数组B1.n(n+1)/2中，对上述任一元素aij(1i，jn，且ij)在B中的位置为(B )。A. i(i-l)/2+j B. j(j-l)/2+i C. j(j-l)/2+i-1 D. i(i-l)/2+j-110. 设An，n是对称矩阵，将其下三角（包括对角线）以行序存储到一维数组Tn（n+1）/2中，则:任意一个上三角元素aij所对应Tk的下标k是（B ）。A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+111、常对数组进行的两种基本操作是（C）。A建立与删除B索引和修改C查找和修改D查

8、找与索引12、就一般情况而言，当（ C ）时，按行存储的AI，J地址与按列存储的AJ，I地址相等。 A行与列的上界相同 B. 行与列的下界相同 C. 行与列的上、下界都相同 D. 行的元素个数与列的元素个数相同13、二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要（D）个字节；M的第8列和第5行共占（B）个字节。A90B180C240D540A108B114C54D6014、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要

9、的单元数是（C）。A80B100C240D27015、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A85的起始地址为（C）ASA+141BSA+144CSA+222DSA+22516、设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C）AO(n)BO(log2n)CO(1)DO(n2)17、三、判断题1、（ ）子串是主串中任意个连续字符组成的序列。2、（ ）广义表( a ), b), c ) 的表头是( a ), b)，表尾是( c )。3、（ ）数组元素的下标值越大，存取时间越长4、

10、数组是线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ ）（ ）设有两个串p和q，求q在p中首次出现的位置的运算称作求子串。（ ）二维数组是其数据元素为线性表的线性表。6、( )若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置。7、( )若一个广义表的表头为空表，则此广义表亦为空表。8、 ( )用一维数组存储二叉树时，总是以前序遍历存储节点。9、采用堆分配存储串时，串仍以一组地址连续的存储单元存储，但存储空间是在程序执行过程中由动态分配而得到。（ ）四、问答题1、已知n阶下三角矩阵A（即当ij时，有aij=0），按照压缩存储的思

11、想，可以将其主对角线以下所有元素(包括主对角线上元素 )依次存放于一维数组B中，请写出从第一列开始采用列序为主序分配方式时在B中确定元素aij的存放位置的公式。答：n阶下三角矩阵元素Aij（1=i,j=j）。第1列有n个元素，第j列有n-j+1个元素，第1列到第j-1列是等腰梯形，元素数为(n+(n-j+2)(j-1)/2，而aij在第j列上的位置是为i-j+1。所以n阶下三角矩阵A按列存储，其元素aij在一维数组B中的存储位置k与i和j的关系为：k=(n+(n-(j-1)+1)(j-1)/2+(i-j+1)=(2n-j)(j-1)/2+i五、算法设计1、输入一个字符串，内有数字和非数字字符，

12、如：ak123x456 17960?302gef4563，将其中连续的数字作为一个整体，依次存放到一数组中，例如123放入0,456放入1，。编程统计其共有多少个整数，并输出这些数。参考答案int CountInt（）/ 从键盘输入字符串，连续的数字字符算作一个整数，统计其中整数的个数。int i=0，a； / 整数存储到数组a，i记整数个数scanf（“c”，&ch）；/ 从左到右读入字符串while（ch!=#） /#是字符串结束标记if（isdigit（ch）/ 是数字字符num=； / 数初始化while（isdigit（ch）& ch!=#）/ 拼数num=num10+ch-；sca

13、nf（“c”，&ch）； ai=num；i+；if（ch!=#）scanf（“%c”，&ch）； / 若拼数中输入了#，则不再输入 / 结束while（ch！#）printf（“共有%d个整数，它们是：”i）；for（j=；j0) sj+=stki- /将第偶数个字符逆序填入原字符数组3、请编写完整的程序。如果矩阵A中存在这样的一个元素Ai,j满足条件:Ai,j是第i行中值最小的元素,且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A的所有马鞍点。 int m=10, n=10;void Saddle(int Amn) /A是m*n的矩阵,本算法求矩阵A中的马鞍

14、点.int maxn=0, /max数组存放各列最大值元素的行号,初始化为行号0;minm=0, /min数组存放各行最小值元素的列号,初始化为列号0;i, j; for(i=0;im;i+) /选各行最小值元素和各列最大值元素.for(j=0;jn;j+) if(AmaxjjAij) mini=j; /修改第i行最小元素的列号. for (i=0;ilchild=null & p-rchlid=null。10、N个结点的二叉树采用二叉链表存放，共有空链域个数为n+111、深度为6（根层次为1）的二叉树至多有26 1个结点。12、平衡二叉树中某一结点左子树的深度减去右子树的深度称为该结点的_平

15、衡因子_。三、选择题 1某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为（C）A）3 B）2 C）4 D）52二叉树是非线性数据结构，所以（ C ）。、它不能用顺序存储结构存储; 、它不能用链式存储结构存储; 、顺序存储结构和链式存储结构都能存储; 、顺序存储结构和链式存储结构都不能使用 3.具有n(n0)个结点的完全二叉树的深度为（ C ）。() log2(n) () log2(n) () log2(n) +1 () log2(n)+14把一棵树转换为二叉树后，这棵二叉树的形态是（ A ）。（）唯一的 （）有多种（）有多种，但根

16、结点都没有左孩子 （）有多种，但根结点都没有右孩子5. 下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（D）。A二叉排序树 B哈夫曼树 CAVL树 D堆6线索二叉树是一种（C ）结构。A 逻辑 B 逻辑和存储 C 物理 D线性7、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为（ A） A、98 B、99 C、50 D、488、设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（D）A）M1 B）M1

17、+M2 C）M3 D）M2+M39、将一棵有100个结点的完全二叉树从根开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为（C） A、48B、49C、50D、5110、引入二叉线索树的目的是（A ）A、加快查找结点的前驱或后继的速度 B、为了能在二叉树中方便的进行插入与删除C、为了能方便的找到双亲 D、使二叉树的遍历结果唯一11若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B ）A9 B11 C15 D不确定 12 一棵树高为K的完全二叉树至少有（C ）个结点A2k 1 B. 2k-1 1 C. 2k-1 D. 2k13设森林F中

18、有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（D ）。AM1 BM1+M2 CM3 DM2+M314一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（B ）ACABDEFG BABCDEFG CDACEFBG DADCFEG15. 有关二叉树下列说法正确的是（B ）A二叉树的度为2 B一棵二叉树的度可以小于2C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为216. 一个具有1025个结点的二叉树的高h为（C ）A11 B10 C11至1025之间 D10至1024之间17一棵二叉树高度为h,所有

19、结点的度或为0，或为2，则这棵二叉树最少有( B)结点A2h B2h-1 C2h+1 Dh+1 18对于有n 个结点的二叉树, 其高度为（D ）Anlog2n Blog2n Clog2n|+1 D不确定19. 一棵具有 n个结点的完全二叉树的树高度（深度）是（A ）Alogn+1 Blogn+1 Clogn Dlogn-120. 已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（D ）。 Aacbed Bdecab Cdeabc Dcedba 21若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用(C )遍历方法最合适。A前序 B中序

20、 C后序 D按层次22在下列存储形式中，哪一个不是树的存储形式？（D ）A双亲表示法 B孩子链表表示法 C孩子兄弟表示法 D顺序存储表示法23在下列关于二叉树的叙述中，正确的是（D ）只有一个结点的二叉树度为0;二叉树的度为2； 二叉树的左右子树可任意交换;深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A B C D24若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为(C ) A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点25在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（B ）A都不相同B

21、完全相同 C先序和中序相同，而与后序不同D中序和后序相同，而与先序不同26在线索化二叉树中，t所指结点没有右子树的充要条件是（ ）。A、t-Rtag=1 B、t-Rchild=NULLC、t-Rtag=1且t-Rchild=NULL D、以上都不对27、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（B）。A2hB2h-1C2h+1Dh+128、如右图所示二叉树的中序遍历序列是（B）。AabcdgefBdfebagcCdbaefcgDdefbagc29、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的先序遍历序列是（A）。AcedbaBc

22、dbaeCcabedDcabde30、设a和b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是（D）。Aa是b的左孩子Bb是a的右孩子Ca是b左子树上结点或b是a右子树上结点D以上三项均可31、假定在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（C）个。A45B15C16D3132、某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，则其后序遍历序列是（A）。AgdbehfcaBabcdefghCgdbaefchDghbcdefa按照二叉树的定义，具有3个结点的二叉树有（D）种。A2B3C4D533、树的基本遍历策略可分为先根遍历和后根遍历

23、；二叉树的遍历策略分为先序、中序和后序遍历。这里把由树转化得到的二叉树叫做这棵树对应的二叉树。以下结论（）是正确的。A树的先根遍历序列与其对应的二叉树的先序遍历序列相同B树的后根遍历序列与其对应的二叉树的后序遍历序列相同C树的先根遍历序列与其对应的二叉树的中序遍历序列相同D以上都不对34、如下图所示的4棵二叉树，（C）不是完全二叉树。35、设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（B）个空指针域。A2m-1B2mC2m+1D4m 36、二叉树的第k层的结点数最多为（ D ）A2k-1B2K+1C2K-1D2K-137、设某棵二叉树中有2000个结点，则该二

24、叉树的最小高度为（ C ）。A9B10C11D1238、一棵有n个结点的树，在把它转换成对应的二叉树后，该二叉树根结点的左子树上共有（ B ）个结点。An-2Bn-1Cn+1Dn+239、对于一棵深度为4的三叉树，最多有（ C ）个结点。A30B36C40D5440、设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（B ）。(A) 3(B) 4(C) 5(D) 1四、简答题 1.给定二叉树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树B。解：方法是：由前序先确定root，由中序可确定

25、root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。2、已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。解：3、给定权值8，12，4，5，26，16，9，构造一棵带权路径长度最短的二叉树，并计算其带权路径长度。解：或： WPL=83+44+54+162+93+123+262 =207注：哈夫曼树的左右子树可以互换。4. （把如图所示的树转化成二叉树。答：注意全部兄弟之间都要连线（包括度为2的兄弟）,并注意原有连线结点一律归

26、入左子树，新添连线结点一律归入右子树。 A B E C K F H D L G I M J5、画出和下列二叉树相应的森林。答：注意根右边的子树肯定是森林，而孩子结点的右子树均为兄弟。6、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。解：哈夫曼编码先将概率放大100倍，以方便构造哈夫曼树。 w=7,19,2,6,32,3,21,10，按哈夫曼规则：【（2,3），6, (7,10)】, 19, 21, 32 0 1 0 1 0 119 21 32 0 10 1 0 17

27、10 6 0 12 3 （100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3WPL2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61五、算法设计题1.编写递归算法，计算二叉树中叶子结点的数目。解：思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。DLR(liuyu *root) /*中序遍历 递归函数*/if(root!=NULL) if(root-lchild=NULL)&(root-rchild=NULL)su

28、m+; printf(%dn,root-data); DLR(root-lchild); DLR(root-rchild); return(0);2.写出求二叉树深度的算法，先定义二叉树的抽象数据类型。解： int depth(liuyu*root) /*统计层数*/int d,p; /*注意每一层的局部变量d,p都是各自独立的*/p=0;if(root=NULL)return(p); /*找到叶子之后才开始统计*/else d=depth(root-lchild);if(dp) p=d; /*向上回朔时，要挑出左右子树中的相对大的那个深度值*/d=depth(root-rchild);if(

29、dp)p=d;p=p+1;return(p);3、已知一棵二叉树按顺序方式存储在数组A1.n中。设计算法，求出下标分别为i和j的两个结点的最近的公共祖先结点的值。解：void Ancestor(ElemType A,int n,i,j)/二叉树顺序存储在数组A1.n中，本算法求下标分别为i和j的结点的最近公共祖先结点的值。 while(i!=j)if(ij) i=i/2; /下标为i的结点的双亲结点的下标else j=j/2; /下标为j的结点的双亲结点的下标printf(“所查结点的最近公共祖先的下标是%d，值是%d”,i,Ai);/设元素类型整型。/ Ancestor4.编写按层次顺序（同

30、一层自左至右）遍历二叉树的算法。解：思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。这是一个循环算法，用while语句不断循环，直到队空之后自然退出该函数。技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，以此产生了按层次输出的效果。void LayerOrder(Bitree T)/层序遍历二叉树 InitQueue(Q); /建立工作队列 EnQueue(Q,T); while(!QueueEmpty(Q) DeQueue(Q,p); visit(p); if(p-lchild) EnQueue(Q,p-lc

31、hild); if(p-rchild) EnQueue(Q,p-rchild); /LayerOrder 5.编写算法判别给定二叉树是否为完全二叉树。答：int IsFull_Bitree(Bitree T)/判断二叉树是否完全二叉树,是则返回1,否则返回0 InitQueue(Q); flag=0; EnQueue(Q,T); /建立工作队列 while(!QueueEmpty(Q) DeQueue(Q,p); if(!p) flag=1; else if(flag) return 0; else EnQueue(Q,p-lchild); EnQueue(Q,p-rchild); /不管孩子

32、是否为空,都入队列 /while return 1; /IsFull_Bitree 6、试设计算法计算一棵给定二叉树上所有结点数目。假设二叉树的存储结构描述如下： typedef struct BiTNodeTElemType data; struct BiTNode *lchild;*rchild; /*左右孩子指针*/BiTNode,*BiTree；解：int CountNode(BinTree bt) if (bt=Null) return(0);else num1=CountNode(root-lchild);num2=CountNode(root-rchild); return(nu

33、m1+num2+1); 7、计算二叉树上单分支结点数目。假设二叉树的存储结构描述如下： typedef struct BiTNodeTElemType data; struct BiTNode *lchild;*rchild; /*左右孩子指针*/ BiTNode,*BiTree；解：FUNC nodes1(t:bitre):integer; if t=Null then nodes1:=0 else if (t-lchild= Null) and (t-rchild= Null) then nodes1:=0else if (t-lchild= Null) or (t-rchild= Nul

34、l)then nodes1:=1+nodes1(t-lchild)+nodes1(t-rchild) else nodes1:=nodes1(t-lchild)+nodes1(t-rchild) ENDF;8、利用栈的基本操作写出先序遍历二叉树的非递归算法题目分析 先序遍历二叉树的非递归算法，要求进栈元素少，意味着空指针不进栈。void PreOrder(Bitree bt)/对二叉数bt进行非递归遍历int top=0; Bitree s; /top是栈s的栈顶指针，栈中元素是树结点指针，栈容量足够大 while(bt!=null | top0)while(bt!=null)printf(b

35、t-data); /访问根结点 if(bt-rchlid) s+top=bt-rchild; /若有右子女，则右子女进栈 bt=bt-lchild; if (top0) bt=stop-;第七章 图一、单选题 （ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。 A1/2 B. 1 C. 2 D. 4 2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。 A1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有 条边。 A14 B. 28 C. 56 D. 112 （ A ）一个n个顶点的连通无向图，其边的个数至少为（ ）。An-

36、1 Bn Cn+1 Dnlogn； （ C ）5. 有8个结点的有向完全图有 条边。 A14 B. 28 C. 56 D. 112 （ B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。A栈 B. 队列 C. 树 D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。A栈 B. 队列 C. 树 D. 图 8. 下面关于求关键路径的说法不正确的是（C ）。 A求关键路径是以拓扑排序为基础的 B一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D关

37、键活动一定位于关键路径上9. 已知图的邻接矩阵如下，根据算法思想，则从顶点0出发，按深度优先遍历的结点序列是（ D ）A 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 3 4 2 5 610、设数据结构A=(D，R)，其中D=1，2，3，4，R=r，r=，则数据结构A是（ C ）。(A) 线性结构(B) 树型结构 (C) 图型结构(D) 集合（ C ）11. 已知图的邻接矩阵同上题9，根据算法，则从顶点0出发，按广度优先遍历的结点序列是A 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6

38、5 D. 0 1 2 3 4 5 612. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（ D ）A0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3（ A ）13. 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是A0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2（ A ）14. 深度优先遍历类似于二叉树的A先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（ D ）15. 广度优先遍历类似于二叉树的A先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（ D ）1

39、6、下面结构中最适于表示稀疏无向图的是。A邻接矩阵 B逆邻接表 C十字链表 D邻接表（ B ）17、下列哪一种图的邻接矩阵是对称矩阵？A有向图 B无向图 CAOV网 DAOE网18、在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( ) Ae B2e Cn2e Dn22e19、下列关于无向连通图特性的叙述中，正确的是（A）I所有顶点的度之和为偶数II.边数大于顶点个数减1III.至少有一个顶点的度为1A.只有IB.只有IIC.I和IID.I和III20、假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是( ) AO(n) BO(e) CO(n

40、+e) DO(n*e)21、无向图G=(V,E),其中：V=a,b,c,d,e,f, E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b22、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（D ）。 AG中有弧 BG中有一条从Vi到Vj的路径CG中没有弧 DG中有一条从Vj到Vi的路径23、下面哪一方法可以判断出一个有向图是否有环（回路）( B)A深度优先遍历 B. 拓扑排序

41、 C. 求最短路径 D. 求关键路径24、下列关于AOE网的叙述中，不正确的是（B ）。A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成，那么整个工程将会提前完成C所有的关键活动提前完成，那么整个工程将会提前完成D某些关键活动提前完成，那么整个工程将会提前完成25、设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ D ）。(A) n，e(B) e，n(C) 2n，e(D) n，2e二、填空题1. 图有 邻接矩阵 、邻接表 、十字链表、邻接多重表等存储结构，其中邻接矩阵 、邻接表既用于存储有向图，也用于存储无向图。遍历图 深度优先遍历、 广

42、度优先遍历 等方法。2. 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 出度 。3. 拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。4. n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为O(n2)，若采用邻接表存储，则空间复杂度为O(n+e)。5. n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 O(n2) ；若采用邻接表存储，该算法的时间复杂度为O(n+e)。6. 设有一稀疏图G，则G采用 邻接表 存储较省空间，设有一稠密图G，则G采用邻接矩阵存储较省空间。7. 用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度递增

43、的次序来得到最短路径的。8. n个顶点的连通无向图，其边的条数至少为_ n-1_。若用n表示图中顶点数目，则有_ n(n-1)/2_条边的无向图成为完全图。9. 具有8个顶点的有向完全图有 56条弧。具有10个顶点的无向图，边的总数最多为_ 45_。10. 在无向图G的邻接矩阵A中，若Aij等于1，则Aji等于 1 。11. G是一个非连通无向图，共有28条边，则该图至少有_9_个顶点。12. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需_队列存放被访问的结点以实现遍历。13. 一无向图G（V，E），其中V（G）=1,2,3,4,5,6,7，E（G）=（1,2）,(1

44、,3），（2,4），（2,5），（3,6），（3,7），（6,7）（5,1）,对该图从顶点3开始进行遍历，去掉遍历中未走过的边，得一生成树G(V，E）,V（G）=V（G），E（G）=（1,3），（3,6），（7,3），（1,2），（1,5），（2,4），则采用的遍历方法是_广度优先遍历_14. 在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_度_；对于有向图来说等于该顶点的_出度_。15. 已知一无向图G=（V，E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点a开始遍历图，得到的序列为ab

45、ecd，则采用的是_深度优先遍历方法。三、判断题1、(r )在拓朴序列中，如果结点Vi排在结点Vj的前面，则一定存在从Vi到Vj的路径。2、( )用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。3、( )拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。4（ ）采用邻接表存储的图的深度优先遍历算法类似二叉树的按层次遍历算法。5、( )若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在。6在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（ ）7. 有e条边的无向图，在邻接表中有e个结点。（ ）8. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（ ）9强连通图的各顶点间均可达。（ ）10连通分量指的是有向图中的极大连通子图。（ ）11任何有向图的