下载文档原格式
第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）。
【北京邮电大学2000 二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。
(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】4．一个算法应该是（）。
【中山大学 1998 二、1（2分）】A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C.5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类。
【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。
【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n) B．O(n) C．O(n2) D．O(log2n)12．程序段 FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中 n为正整数，则最后一行的语句频度在最坏情况下是（）A. O（n）B. O(nlogn)C. O(n3)D. O(n2)【南京理工大学1998一、1(2分)】13．以下哪个数据结构不是多型数据类型（）【中山大学 1999 一、3（1分）】A．栈 B．广义表 C．有向图 D．字符串14．以下数据结构中，（）是非线性数据结构【中山大学 1999 一、4】A．树 B．字符串 C．队 D．栈15. 下列数据中，（）是非线性数据结构。
一、单项选择题（本大题共71小题，每小题2分，共142分）1、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（）。
（）A．{38，46，79，56，40，84}B．{38，79，56，46，40，84}C．{40，38，46，56，79，84}D．{38，46，56，79，40，84}标准答案：C2、广义表（（a）,a）的表头是（）。
（）A．aB．bC．(a)D．((a))标准答案：C3、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是（）。
（）A．80B．100C．240D．270标准答案：C4、在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（）。
（）A．HL=p；p->next=HL；B．p->next=HL；HL=p；C．p->next=HL；p=HL；D．p->next=HL->next；HL->next=p；标准答案：B5、一个具有n个顶点的无向完全图的边数为（）。
（）A．(n+1)/2B．n(n-1)/2C．n(n-1)D．n(n+1)标准答案：B6、如果待排序序列中两个数据元素具有相同的值，在排序后它们的位置发生颠倒，则称该排序是不稳定的。
下列选项中，（）就是不稳定的排序方法。
（）A．起泡排序B．归并排序C．直接插入法排序D．简单选择排序标准答案：D7、按照二叉树的定义，具有3个结点的二叉树有（）种。
（）A．3B．4C．5D．6标准答案：C8、设有1000个元素，用二分法查找时，最大比较次数是（）。
（）A．1B．7C．10D．25标准答案：C9、树适合用来表示（）。
（）A．有序数据元素B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据标准答案：C10、设有两个串p和q，求p在q中首次出现的位置的运算称作（）。
数据结构复习题一、选择题1.数据结构被形式地定义为<D,R>,其中D是的有限集。
A 算法B 数据元素C 数据操作D 逻辑结构2.数据结构被形式地定义为<D,R>,其中R是的有限集.A 操作B 映像C 存储D 关系3．在数据结构的讨论中把数据结构从逻辑上分为（）。
A 内部结构与外部结构B 静态结构与动态结构C 线性结构与非线性结构D 紧凑结构与非紧凑结构4．链表表示线性表的优点是（）A、便于随机存取B、花费的存储空间比顺序表少C、便于插入与删除5．用单链表表示的链式队列的队头在链表的（）位置。
A.链头B.链尾C.链中6．线性表是具有n个（）的有限序列（n≠0)A.表元素B.字符C.数据元素D.数据项7．采用线性链表表示一个向量时，要求占用的存储空间地址（）。
A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 可连续可不连续8.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动______个元素。
A.8B.63.5C.63D.79．若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用______________存储方式最节省运算时间。
A单链表 B双链表C 单循环链表 D带头结点的双循环链表10.链表不具有的特点是____________.A可随机访问任一元素 B插入删除不需要移动元素C不必事先估计存储空间 D所需空间与线性表长度成正比11.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。
A. O(n)B. O(log2n)C. O(1)D. O(n2)12.带头结点的单链表first为空的判定条件是：A. first == NULL;B. first->next == NULL;C. first->next == first;D. first != NULL;13.在一个单链表中，若删除p所指结点的后续结点，则执行____。
（完整版）数据结构复习题（附答案）⼀、算法设计题（每题15分，共60分）答题要求：①⽤⾃然语⾔说明所采⽤算法的思想；②给出每个算法所需的数据结构定义，并做必要说明；③写出对应的算法程序，并做必要的注释。
1、有⼀个带头结点的单链表，每个结点包括两个域，⼀个是整型域info，另⼀个是指向下⼀个结点的指针域next。
假设单链表已建⽴，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留⼀个。
3、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个⼈按顺时针⽅向围坐成⼀圈，现从第s个⼈开始按顺时针⽅向报数，数到第m个⼈出列，然后从出列的下⼀个⼈重新开始报数，数到第m的⼈⼜出列，…，如此重复直到所有的⼈全部出列为⽌。
现要求采⽤循环链表结构设计⼀个算法，模拟此过程。
4、编程实现单链表的就地逆置。
23．在数组 A[1..n]中有n个数据，试建⽴⼀个带有头结点的循环链表，头指针为h，要求链中数据从⼩到⼤排列，重复的数据在链中只保存⼀个.5、设计⼀个尽可能的⾼效算法输出单链表的倒数第K个元素。
3、假设以I和O分别表⽰⼊栈和出栈操作。
栈的初态和终态均为空，⼊栈和出栈的操作序列可表⽰为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为⾮法序列。
（15分）（1）下⾯所⽰的序列中哪些是合法的？A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO（2）通过对（1）的分析，写出⼀个算法，判定所给的操作序列是否合法。
若合法，返回true，否则返回false（假定被判定的操作序列已存⼊⼀维数组中）。
5、设从键盘输⼊⼀整数的序列：a1, a2, a3，…，an,试编写算法实现：⽤栈结构存储输⼊的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。
算法应对异常情况（⼊栈满等）给出相应的信息。
设有⼀个背包可以放⼊的物品重量为S，现有n件物品，重量分别为W1，W2，...，W n。
第一章复习题1.简述顺序存储结构与链式存储结构在表示数据元素之间关系上的主要区别。
答：在顺序结构中，逻辑关系上相邻的两个元素在物理位置上也相邻。
而链式存储结构中，数据元素之间关系是由结点中指针指示的。
2.数据结构是一门……的学科。
3.在数据结构中，从逻辑上可以把数据结构分成〔 C 〕。
A、动态结构与静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、部结构和外部结构4.编写一个函数，用不多于3n/2的平均比拟次数，在一个数组中找出最大和最小值元素。
void maxmin(int a[],int n){max=min=a[0];for(i=1;i<n;i++){if(a[i]>max) max=a[i];else if(a[i]<min) min=a[i];}printf(“max=%d, min=%d〞,max, min);}第二章复习题1．下述哪一条是顺序存储结构的优点？〔 A 〕A．存储密度大 B．插入运算方便C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的表达中，错误的选项是哪一个？〔 B 〕A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进展插入和删除操作。
C．线性表采用存储，不必占用一片连续的存储单元。
D．线性表采用存储，便于插入和删除操作。
3．线性表是具有n个〔 C 〕的有限序列〔n>=0〕。
A．表元素 B．字符 C．数据元素 D．数据项4．假设某线性表最常用的操作是存取任一指定序号的元素和在最后进展插入和删除运算，那么利用〔 A 〕存储方式最节省时间。
A．顺序表 B．单循环链表C．带头结点的双循环链表 D．双链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，那么采用〔 D 〕存储方式最节省运算时间。
A．单链表 B．仅有头指针的单循环链表C．双链表 D．仅有尾指针的单循环链表6．假设某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。
数据结构复习题1一、选择题1. 以下四类基本的逻辑结构反映了四类基本的数据组织形式，解释错误的是 ( ) A 、集合中任何两个结点之间都有逻辑关系但组织形式松散 B 、线性结构中结点按逻辑关系依次排列形成一条"锁链"C 、树形结构具有分支、层次特性，其形态有点像自然界中的树D 、图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接2. 若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( ) A 、顺序存储结构 B 、链式存储结构 C 、索引存储结构 D 、散列存储结构3. 在长度为n 的顺序表的第i (1≤i ≤n+1)个位置上插入一个元素，元素的移动次数为( ) A 、n-i+1 B 、n-i C 、i D 、i-14. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )A 、顺序表B 、用头指针表示的单循环链表C 、用尾指针表示的单循环链表D 、单链表5. 一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是（ ）A 、e d c b aB 、d e c b aC 、d c e a bD 、a b c d e6. 已知图1如右所示，若从顶点A 出发按深度优先搜索进行遍历，则可能得到的顶点序列为（ ） A 、 A ，B ，E ，C ，D ，F B 、 A ，C ，F ，E ，B ，DC 、 A ，E ，B ，C ，F ，DD 、 A ，E ，D ，F ，C ，B7. n 个顶点的有向图中含有向边的数目最多为 ( )A 、n-1B 、nC 、n(n-1)/2D 、n(n-1) 8. 若一个栈的输入顺序是1，2，…，n ，输出序列的第一个元素是n ，则第i （1≤i ≤n ）个输出元素是（ ）A 、n-iB 、n-i-1C 、i+1D 、n -i+1 9. 已给图2，（ ）是该图的正确的拓扑排序序列A 、1，2，3，4，5B 、1，3，2，4，5C 、1，2，4，3，5D 、1，2，3，5，4 10. 为查找某一特定单词在文本中出现的位置，可应用的串运算是( )A 、插入B 、删除C 、串联接D 、子串定位二、填空题A BC D E F 图1 1 2 34 5 图21.存储结构是逻辑结构的__________实现。
第一章一、单项选择题1. 数据结构是指（）。
A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。
A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构3. 树形结构是数据元素之间存在一种（）。
A.一对一关系B.多对多关系C.多对一关系D.一对多关系4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。
for(i=1; i<=n; i++)for(j=i; j<=n; j++)x++;A.O(1)B.O( )C.O(n)D.O( )5. 算法分析的目的是（1），算法分析的两个主要方面是（2）。
A.找出数据结构的合理性B.研究算法中的输入和输出关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性（2） A.空间复杂度和时间复杂度 B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性6. 计算机算法指的是（1），它具备输入，输出和（2）等五个特性。
（1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法（2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性C.确定性，有穷性和稳定性D.易读性，稳定性和安全性7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。
A.低 B.高 C.相同 D.不好说8. 数据结构作为一门独立的课程出现是在（）年。
A.1946B.1953C.1964D.19689. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。
A.正确B.错误C.前半句对，后半句错D.前半句错，后半句对10. 计算机内部数据处理的基本单位是（）。
A.数据B.数据元素C.数据项D.数据库二、填空题1. 数据结构按逻辑结构可分为两大类，分别是______________和_________________。
数据结构复习题库一、填空题（24分，每空1分）1.1绪论1、数据中指输入到计算机中并能被计算机程序处理的符号的总称。
2、数据对象是具有相同性质的数据元素的集合，它是数据的子集。
3、数据结构：带结构的数据元素的集合；是指数据以及相互之间的联系，主要描述数据及其关系在计算机内如何表示、存取和处理。
4、数据的逻辑结构是指数据元素之间逻辑关系的整体，它与数据的存储结构无关，是独立于计算机的。
数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它是依赖于计算机语言的。
5、数据结构在计算机意义下，包含三个方面的内容：（1）数据元素之间的逻辑关系；是指数据及其相互之间的关系,它是根据人们解决实际问题的需要和问题本身所含数据之间的内在联系而抽象出来的；（2）数据的存储方式；（3）数据的运算。
6、数据的逻辑结构可归结为以下四类: 线性结构、树形结构、图状结构、集合结构7、数据的存储方式可归结为以下四类: 1）顺序存储2）链接存储3）索引存储4）散列存储。
8、抽象数据类型(Abstract Data Type 简称ADT)：是指一个数学模型以及定义在此数学模型上的一组操作。
抽象数据类型可以定义一个完整的数据结构。
算法9、数据结构是指数据及其相互之间的____联系____。
当结点之间存在M对N（M：N）的联系时，称这种结构为图（或图结构）。
10、算法的五个重要特性是指(1)有穷性、(2)确定性：(3)可行性、(4)输入、(5)输出；其中有穷性是指：执行有限步后能够在有限时间内(合理)结束；确定性是指：每一步都应确切地、无二义性地定义；(3)可行性：每条指令可以执行且有正确的结果。
11、评价一个算法的好坏主要依据：1正确性2、可读性3、健壮性4、高效率与低存储量需求。
12、算法效率的衡量方法有：事后统计法和事前分析估算法；事前估算法主要考虑：（1）算法选用的策略、（2）、问题的规模。
13、算法时间复杂度是算法中基本运算重复执行次数多少的量度。
数据结构复习题题集错误！未指定书签。
1.选择题1.1. 图中有关路径的定义是A).由顶点和相邻顶点序偶构成的边所形成的序列B).由不同顶点所形成的序列C).由不同边所形成的序列D).上述定义都不是答案：A分析：本题考查图的相关知识，根据图的有关路径定义可知，图中有关路径的定义是由顶点和相邻顶点序偶构成的边所形成的序列。
知识点：图的定义与术语难度：易1.2. 设无向图的顶点个数为n，则该图最多有（）条边A).n-1B).n(n-1)/2C).n(n+1)/2D).n2答案：B分析：本题考查图的相关知识，根据无向图的定义可知，无向图的顶点个数为n，则该图最多有n(n-1)/2条边。
知识点：图的定义与术语难度：中1.3. 一个n个顶点的连通无向图，其边的个数至少为（）A).n-1B).nC).n+1D).nlogn答案：A分析：本题考查图的相关知识，根据连通无向图的定义可知，一个n个顶点的连通无向图，其边的个数至少为n-1。
知识点：图的定义与术语难度：中1.4. 要连通具有n个顶点的有向图，至少需要（）条边A).n-lB).nC).n+lD).2n答案：B分析：本题考查图的相关知识，根据连通有向图的定义可知，要连通具有n个顶点的有向图，至少需要n条边。
知识点：图的定义与术语难度：易1.5. n个结点的完全有向图含有边的数目为A).n*nB).n（n＋１）C).n／2D).n*（n－l）答案：D分析：本题考查图的相关知识，根据完全有向图的定义可知，n个结点的完全有向图含有边的数目为n*（n－l）。
知识点：图的定义与术语难度：中1.6. 一个有n个结点的图，最少有（）个连通分量A).0B). 1C).n-1D).n答案：B分析：本题考查图的相关知识，根据连通分量的定义可知，一个有n个结点的图，最少有1个连通分量。
知识点：图的定义与术语难度：中1.7. 一个有n个结点的图，最多有（）个连通分量A).0B). 1C).n-1D).n答案：D分析：本题考查图的相关知识，根据连通分量的定义可知，一个有n个结点的图，最多有n个连通分量。
知识点：图的定义与术语难度：易1.8. 在一个无向图中，所有顶点的度数之和等于所有边数（）倍A).1/2B). 1C). 2D). 4答案：C分析：本题考查图的相关知识，根据无向图的定义可知，在无向图中所有顶点的度数之和等于所有边数2倍。
知识点：图的定义与术语难度：中1.9. 在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍A).1/2B). 1C). 2D). 4答案：B分析：本题考查图的相关知识，根据有向图的定义可知，在有向图中所有顶点的入度之和等于所有顶点出度之和的1倍。
知识点：图的定义与术语难度：中1.10. 用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( )A). 5B). 6C).8D).9答案：A分析：本题考查图的相关知识，根据无环图的定义可知，至少需要顶点的数目为5。
知识点：图的定义与术语难度：难1.11. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )A).逆拓扑有序B).拓扑有序C).无序的D).不能确定答案：A分析：本题考查图的相关知识，根据DFS遍历算法的定义可知，DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是逆拓扑有序的。
知识点：图的遍历难度：难1.12. 下面结构中最适于表示稀疏无向图的是A).邻接矩阵B).逆邻接表C).邻接多重表D).十字链表答案：C分析：本题考查图的相关知识，根据稀疏无向图的定义可知，邻接多重表最适于表示稀疏无向图。
知识点：图的存储结构难度：易1.13. 下面结构中适于表示稀疏有向图的是(多选)A). 邻接矩阵B). 逆邻接表C). 十字链表D). 邻接表答案：BCD分析：本题考查图的相关知识，根据稀疏有向图的定义可知，适于表示稀疏有向图的是逆邻接表、十字链表、邻接表。
知识点：图的存储结构难度：易1.14. 下列哪一种图的邻接矩阵是对称矩阵A). 有向图B). 无向图C). AOV 网D). AOE 网答案：C分析：本题考查图的相关知识，根据AOV 网的定义可知，AOV 网的邻接矩阵是对称矩阵。
知识点：图的存储结构难度：中此题建议去掉，无向图的邻接矩阵也是对称矩阵，关于主对角线对称。
1.15. 从邻接阵矩⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=010101010A 可以看出，该图共有（ ）个顶点A). 9B). 3C). 6D). 1答案：B分析：本题考查图的相关知识，根据邻接矩阵的定义可知，从邻接阵矩可以看出，该图共有3个顶点。
知识点：图的存储结构难度：中1.16. 从邻接阵矩⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=010101010A 可以看出，如果是有向图该图共有（ ）条弧A). 5B). 4C). 3D). 2答案：B分析：本题考查图的相关知识，根据邻接矩阵的定义可知，从邻接阵矩可以看出，如果是有向图该图共有4条弧。
知识点：图的存储结构难度：难难度：中此题是对图存储结构的考查，难度不大1.17. 从邻接阵矩⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=010101010A 可以看出，如果是无向图，则共有（ ）条边A). 5B). 4C). 3D). 2答案：D分析：本题考查图的相关知识，根据邻接矩阵的定义可知，从邻接阵矩可以看出，如果是无向图，则共有2条边。
知识点：图的存储结构难度：中1.18. 当一个有N 个顶点的图用邻接矩阵A 表示时，顶点Vi 的度是A). ∑=n i j i A 1],[B). []∑=n 1j j ,i AC). ∑=n i i j A 1],[ D). ∑=n i j i A 1],[+ []∑=n1j i ,j A答案：B分析：本题考查图的相关知识，根据邻接矩阵的定义可知，当一个有N 个顶点的图用邻接矩阵A 表示时，顶点Vi 的度是B 答案。
知识点：图的存储结构难度：难此题建议去掉，未指明是有向图还是无向图 1.19. 用相邻矩阵A 表示图，判定任意两个顶点Vi 和Vj 之间是否有长度为m 的路径相连，则只要检查（ ）的第i 行第j 列的元素是否为零即可A). BB). AC). CD). D答案：B分析：本题考查图的相关知识，判定任意两个顶点Vi 和Vj 之间是否有长度为m 的路径相连，则只要检查第i 行第j 列的元素是否为零即可。
知识点：图的存储结构难度：中1.20. 下列说法不正确的是A).图的遍历是从给定的源点出发每一个顶点仅被访问一次B).图的深度遍历不适用于有向图C).遍历的基本算法有两种：深度遍历和广度遍历D).图的深度遍历是一个递归过程答案：B分析：本题考查图的相关知识，根据有向图遍历的定义可得，图的深度遍历适用于有向图，B选项错误。
知识点：图的遍历难度：易1.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)}，对该图进行深度优先遍历，得到的顶点序列正确的是A).a,b,e,c,d,fB).a,c,f,e,b,dC).a,e,b,c,f,dD).a,e,d,f,c,b答案：D分析：本题考查图的相关知识，根据图进行深度优先遍历的定义可得，得到的顶点序列a,e,d,f,c,b。
知识点：图的遍历难度：难1.22. 下面哪一方法可以判断出一个有向图是否有环（回路）A).深度优先遍历B).拓扑排序C).求最短路径D).求关键路径答案：AB分析：本题考查图的相关知识，根据图进行深度优先遍历的定义可得，深度优先遍历、拓扑排序都可以判断出一个有向图是否有环。
知识点：图的遍历难度：易1.23. 在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为A).O(n)B).O(n+e)C).O(n2)D).O(n3)答案：B分析：本题考查图的相关知识，根据Prim 算法的定义可得，求最小生成树的Prim 算法的时间复杂度为O(n+e)。
知识点：生成树难度：中答案：C分析：本题考查图的相关知识，根据Prim 算法的定义可得，求最小生成树的Prim 算法的时间复杂度为O(n2)。
知识点：生成树难度：中1.24. 以下说法正确的是A).求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义B).利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3) ；（图用邻接矩阵表示）C).Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路D).ABC都是错的答案：D分析：本题考查图的相关知识，根据Prim 算法的定义可得，求最小生成树的Prim 算法的时间复杂度为O(n+e)，ABC选项都是错误的。
知识点：生成树难度：难此题建议去掉，分析与答案完全不相符1.25. 当各边上的权值( )时，BFS算法可用来解决单源最短路径问题A).均相等B).均互不相等C).不一定相等D).无要求答案：A分析：本题考查图的相关知识，根据BFS算法的定义可得，当各边上的权值均相等时，BFS 算法可用来解决单源最短路径问题。
知识点：最短路径难度：中1.26. 求解最短路径的Floyd算法的时间复杂度为A).O（n）B).O（n+c）C).O（n*n）D).O（n*n*n）答案：D分析：本题考查图的相关知识，根据Floyd算法的定义可得，求解最短路径的Floyd算法的时间复杂度为O（n*n*n）。
知识点：最短路径难度：易1.27. 已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是A).V1,V3,V4,V6,V2,V5,V7B).V1,V3,V2,V6,V4,V5,V7C).V1,V3,V4,V5,V2,V6,V7D).V1,V2,V5,V3,V4,V6,V7答案：A分析：本题考查图的相关知识，根据拓扑排序的定义可得，G的拓扑序列是V1,V3,V4,V6,V2,V5,V7。
知识点：拓扑排序难度：难1.28. 若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列A).存在B).不存在C).不能确定D).可能存在答案：A分析：本题考查图的相关知识，根据拓扑排序的定义可得，若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列存在。
