2022年2022年数据结构练习题

1、精选学习资料 - - - 欢迎下载数据结构练习题习题 1绪论1.1 单项选择题1. 数据结构为一门讨论非数值运算的程序设计问题中、 数据元素的.数据信息在运算机中的以及一组相关的运算等的课程； a 操作对象运算方法规律结构数据映象 a 储备结构关系运算算法2. 数据结构dsdata struct可以被形式地定义为ds=（ d, r）,其中 d 为的有限集合, r 为 d上的有限集合； a 算法数据元素数据操作数据对象 a 操作映象储备关系3. 在数据结构中,从规律上可以把数据结构分成；a动态结构和静态结构紧凑结构和非紧凑结构线性结构和非线性结构内部结构和外部结构4. 算法分析的目的为,算法分析

2、的两个主要方面为； a.找出数据结构的合理性b.讨论算法中的输入和输出的关系分析算法的效率以求改进d.分析算法的易懂性和文档性空间复杂性和时间复杂性b.正确性和简明性c. a.c. 可读性和文档性d.数据复杂性和程序复杂性5. 运算机算法指的为,它必具备输入.输出和等五个特性；a.运算方法b.排序方法c. 解决问题的有限运算序列d.调度方法 a.可行性.可移植性和可扩充性b.可行性.确定性和有穷性c.确定性.有穷性和稳固性d.易读性.稳固性和安全性1.2 填空题（将正确的答案填在相应的空中）1. 数据规律结构包括.和三种类型,树形结构和图形结构合称为；2. 在线性结构中,第一个结点前驱结点,其

3、余每个结点有且只有个前驱结点；最终一个结点后续结点,其余每个结点有且只有个后续结点；3. 在树形结构中,树根结点没有结点,其余每个结点有且只有个直接前驱结点,叶子结点没有结点,其余每个结点的直接后续结点可以；4. 在图形结构中,每个结点的前驱结点数和后续结点数可以；5. 线性结构中元素之间存在关系,树形结构中元素之间存在关系,图形结构中元素之间存在关系；6.算法的五个重要特性为、 、_ 、 、 _ ；7. 分析下面算法（程序段）,给出最大语句频度,该算法的时间复杂度为 ；for i=0;i<n;i+ for j=0;j<n; j+aij=0;8. 分析下面算法（程序段）,给出最大语

4、句频度,该算法的时间复杂度为；for i=0;i<n;i+ for j=0; j<i; j+aij=0;9. 分析下面算法（程序段）,给出最大语句频度,该算法的时间复杂度为；s=0;for i=0;i<n;i+ for j=0;j<n;j+for k=0;k<n;k+ s=s+bijk; sum=s;10. 分析下面算法（程序段）给出最大语句频度,该算法的时间复杂度为 ；i=s=0;精品学习资料精选学习资料 - - - 欢迎下载while s<n i+;s+=i;/s=s+i11. 分析下面算法（程序段）给出最大语句频度,该算法的时间复杂度为 ；i=1;wh

5、ile i<=n i=i*2;1.3 算法设计题1. 试写一算法 、 自大到小依次输出次序读入的三个数x、y 和 z 的值 .2. 试写一算法 、 求出 n 个数据中的最大值；写出最大语句频度,该算法的时间复杂度；习题答案1.11. c 、 a2. b、d3. c4. c、 a5. c、b1.21.线性结构.树形结构.图形结构,非线性结构2. 没有. 1.没有. 13. 前驱. 1.后续.任意多个4. 任意多个5. 一对一.一对多.多对多6. 有穷性.确定性.可行性.输入.输出227. 最大语句频度：n, 时间复杂度： . o n28. 最大语句频度：n n+1/2, 时间复杂度：. o

6、 n9. 最大语句频度：n3 , 时间复杂度： . o n3112210. 最大语句频度：n, 时间复杂度：. o n11. 最大语句频度：log 2n, 时间复杂度： . o log2n 习题 2线性表2.1 单项选择题1. 一个向量（即一批地址连续的储备单元）第一个元素的储备地址为100,每个元素的长度为2,就第 5 个元素的地址为 ；a. 110b. 108c. 100d. 1202. 线性表的次序储备结构为一种_ 的储备结构,而链式储备结构为一种_ 的储备结构；a随机存取b索引存取c 次序存取d 散列存取3. 线性表的规律次序与储备次序总为一样的,这种说法_ ；a. 正确b.不正确4.

7、 线性表如采纳链式储备结构时,要求内存中可用储备单元的地址_ ；a. 必需为连续的b.部分地址必需为连续的c.肯定为不连续的d.连续或不连续都可以5. 在以下的表达中,正确选项_ ；a. 线性表的次序储备结构优于链表储备结构b. 线性表的次序储备结构适用于频繁插入/ 删除数据元素的情形c. 线性表的链表储备结构适用于频繁插入/ 删除数据元素的情形d. 线性表的链表储备结构优于次序储备结构6. 每种数据结构都具备三个基本运算：插入.删除和查找,这种说法_ ；a. 正确b.不正确7. 不带头结点的单链表head 为空的判定条件为 ；a. head= =nullb. head->next= =

8、nullc. head->next= =headd. head.=null精品学习资料精选学习资料 - - - 欢迎下载8. 带头结点的单链表head 为空的判定条件为 ；a. head= =nullb. head->next= =nullc. head->next= =headd. head.=null9. 非空的循环单链表head 的尾结点（由p 所指向）满意 ；a. p->next= =nullb. p= =nullc. p->next= =headd. p= =head10. 在双向循环链表的p 所指结点之后插入s 所指结点的操作为 ；a. p->r

9、ight=s; s->left=p; p->right->left=s; s->right=p->right;b. p->right=s; p->right->left=s; s->left=p; s->right=p->right;c. s->left=p;s->right=p->right;p->right=s; p->right->left=s;d. s->left=p;s->right=p->right;p->right->left=s; p->ri

10、ght=s;11. 在一个单链表中,已知q 所指结点为p 所指结点的前驱结点,如在q 和 p 之间插入s 结点,就执行 ；a. s->next=p->next; p->next=s;b. p->next=s->next; s->next=p;b. q->next=s;s->next=p;c. p->next=s;s->next=q;12. 在一个单链表中,如p 所指结点不为最终结点,在p 之后插入s 所指结点,就执行 ；a. s->next=p; p->next=s;b. s->next=p->next; p-

11、>next=s;c. s->next=p->next; p=s;c. p->next=s; s->next=p;13. 在一个单链表中,如删除p 所指结点的后续结点,就执行 ；a. p->next= p->next->next；b. p= p->next; p->next= p->next->next；c. p->next= p->next;d. p= p->next->next；14. 从一个具有n 个结点的单链表中查找其值等于x 结点时,在查找胜利的情形下,需平均比较 个结点；a. nb. n/

12、2c. n-1/2d. n+1/215. 在一个具有n 个结点的有序单链表中插入一个新结点并仍旧有序的时间复杂度为 ；2a. o1b. onc. o nd. o nlog2 n16. 给定有 n 个元素的向量,建立一个有序单链表的时间复杂度为；2a. o1）b. onc. o nd. o n*log2n2.2 填空题（将正确的答案填在相应的空中）精品学习资料精选学习资料 - - - 欢迎下载1. 单链表可以做 的链接储备表示；2. 在双链表中,每个结点有两个指针域,一个指向 ,另一个指向；精品学习资料精选学习资料 - - - 欢迎下载3. 在一个单链表中p 所指结点之前插入一个s 值为 e 所

13、指结点时,可执行如下操作： q=head;while q->next.=p q=q->next;s= new node;s->data=e;q->next=;/填空s->next=;/填空4. 在一个单链表中删除p 所指结点的后继结点时,应执行以下操作： q= p->next;p->next= _ ;/填空delete;/填空5. 在一个单链表中p 所指结点之后插入一个s 所指结点时,应执行s->next= 和 p->next=的操作；精品学习资料精选学习资料 - - - 欢迎下载6. 对于一个具有n 个结点的单链表,在已知p 所指结点后插

14、入一个新结点的时间复杂度为；在给定值为x 的结点后插入一个新结点的时间复杂度为；2.3 算法设计题 :1. 设次序表va 中的数据元数递增有序；试写一算法,将x 插入到次序表的适当位置上,以保持该表的有序性；status insert_sqlistsqlist &va、int xifva.length+1>maxsize return error; va.length+;fori=va.length-1;va.elemi>x&&i>=0;i- va.elemi+1=va.elemi;va.elemi+1=x; return ok;精品学习资料精选学习资

15、料 - - - 欢迎下载2. 试写一算法,实现次序表的就地逆置,即利用原表的储备空间将线性表（a1、 a 2、 . a n）逆置为 a n、 a n- 1、 .、 a 1 ；void reverseint a、 int sizeint i、j、tmp;fori=0、 j=size-1; i<j; i+、j-tmp=ai; ai=aj; aj=tmp;3. 已知线性表中的元素以值递增有序排列,并以单链表作储备结构；试写一算法,删除表中全部大于x 且小于 y 的元素（如表中存在这样的元素）同时释放被删除结点空间；void dellinklist l、elemtype a、elemtype b

16、p= l;q=p->next;whileq.=l && q->data<ap=q;q=q->next;whileq.=l && q->data<br=q;q=q->next; freer;ifp.=qp->next=q;4. 试写一算法,实现单链表的就地逆置 要求在原链表上进行 ； void conversenodeptr lnodeptr p、q;p=l->next; q=p->next;l->next=null;whilep/*对于当前结点p,用头插法将结点p 插入到头结点之后*/p->

17、next=l->next;l->next=p;p=q;q=q->next;习题答案2.11. b2. a、 c3. b4. d5. c6. a7. a8. b9. c10. d11.b12.b13.a14.d15.b16.c2.21.线性结表2.前驱结点.后继结点3. s、 p4. q->next、 q精品学习资料精选学习资料 - - - 欢迎下载5. p->next、 s6.o 1 、 o n习题 3 栈和队列3.1 单项选择题1. 一个栈的入栈序列a,b, c , d, e,就栈的不行能的输出序列为 ；a. edcbab. decbac. dceabd. ab

18、cde2. 如已知一个栈的入栈序列为1, 2, 3, n,其输出序列为p1, p2,p3, pn,如 p1=n,就 pi为 ；a. ib. n=ic. n-i+1d.不确定3. 栈结构通常采纳的两种储备结构为 ；a. 次序储备结构和链式储备结构b. 散列方式和索引方式c. 链表储备结构和数组d. 线性储备结构和非线性储备结构4. 判定一个次序栈st（最多元素为m0）为空的条件为 ；a. top .=0b. top= =0c. top .=m0d. top= =m0-15. 判定一个次序栈st（最多元素为m0）为栈满的条件为 ；a. top！ =0b. top= =0c. top！ =m0d.

19、top= =m0-16. 栈的特点为 ,队列的特点为 ；a.先进先出b.先进后出7. 向一个栈顶指针为hs的链栈中插入一个s 所指结点时,就执行 ； 不带空的头结点a. hs next=s;b. s next= hs next; hs next=s;c. s next= hs; hs=s;d. s next= hs; hs= hs next;精品学习资料精选学习资料 - - - 欢迎下载8. 从一个栈顶指针为hs的链栈中删除一个结点时,用x 储存被删结点的值,就执行 a. x=hs; hs= hs next;b. x=hs data;c. hs= hs next; x=hs data;d. x

20、=hs data; hs= hs next;9. 一个队列的数据入列序列为1, 2, 3, 4,就队列的出队时输出序列为 ；a. 4, 3, 2,1b. 1,2, 3, 4c. 1, 4, 3,2d. 3, 2, 4,110. 判定一个循环队列qu（最多元素为m0）为空的条件为 ；a. rear - front= =m0b. rear-front-1= =m0c. front= = reard. front= = rear+111. 判定一个循环队列qu（最多元素为m0、 m0= =maxsize-1）为满队列的条件为 ；a. rear- front+ maxsize% maxsize = =

21、m0b. rear-front-1= =m0c. front= =reard. front= = rear+1； 不带空的头结点精品学习资料精选学习资料 - - - 欢迎下载12. 循环队列用数组a0 ,m-1 存放其元素值, 已知其头尾指针分别为front和 rear ,就当前队列中的元素个数为 ；a. rear-front+m%mb. rear-front+1 c.rear-front-1d. rear-front13. 栈和队列的共同点为 ；a.都为先进后出b.都为先进先出c.只答应在端点处插入和删除元素d.没有共同点3.2 填空题（将正确的答案填在相应的空中）精品学习资料精选学习资料

22、- - - 欢迎下载1. 向量.栈和队列都为 结构,可以在向量的 位置插入和删除元素；对于栈只能在队列只能在 插入元素和 删除元素；2. 向一个长度为n 的向量的第i 个元素（ 1i n+1）之前插入一个元素时,需向后移动3. 向一个长度为n 的向量中删除第i 个元素（ 1 i n）时,需向前移动 个元素； 插入和删除元素；对于 个元素；精品学习资料精选学习资料 - - - 欢迎下载4. 在具有 n 个单元的循环队列中,队满时共有 个元素；习题答案1. c2. c3. a4. b5.d6. ba7.c8. b9. c 10. c11. a12. a13.c3.13.21.线性.任何.栈顶.队尾

23、.队首2. n-i+13. n-i 4. n-1习题 6树和二叉树6.1 单项选择题1. 由于二叉树中每个结点的度最大为2,所以二叉树为一种特别的树,这种说法 ；a. 正确b.错误2. 假定在一棵二叉树中,双分支结点数为15,单分支结点数为30个,就叶子结点数为个；a 15 b 16c 17d 47精品学习资料精选学习资料 - - - 欢迎下载3. 依据二叉树的定义,具有3 个结点的不同外形的二叉树有a. 3b. 4c. 5d. 6 种；精品学习资料精选学习资料 - - - 欢迎下载4. 依据二叉树的定义,具有3 个不同数据结点的不同的二叉树有 种；a. 5b. 6c. 30d. 325. 深

24、度为 5 的二叉树至多有 个结点；a. 16b. 32c. 31d. 106. 设高度为h 的二叉树上只有度为0 和度为 2 的结点,就此类二叉树中所包含的结点数至少为_；a. 2hb. 2h-1c. 2h+1d. h+17. 对一个满二叉树,m个树叶, n 个结点,深度为h,就 ；ha. n=h+mb. h+m=2nc. m=h-1d. n=2-18. 任何一棵二叉树的叶结点在先序.中序和后序遍历序列中的相对次序 ；a. 不发生转变b.发生转变c.不能确定d.以上都不对9. 假如某二叉树的前根次序遍历结果为stuwv ,中序遍历为uwtvs ,那么该二叉树的后序为 ；a. uwvtsb. v

25、wutsc. wuvtsd. wutsv10. 二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法 ；a.正确b.错误11. 某二叉树的前序遍历结点拜访次序为abdgcefh ,中序遍历的结点拜访次序为dgbaechf ,就其后序遍历的结点拜访次序为 ；a. bdgcefhab. gdbecfhac. bdgaechfd. gdbehfca12. 在一非空二叉树的中序遍历序列中,根结点的右边 ；a.只有右子树上的全部结点b.只有右子树上的部分结点c.只有左子树上的部分结点d.只有左子树上的全部结点13. 如图 6.1 所示二叉树的中序遍历序列为 ；a. abcdgefb. d

26、febagcc. dbaefcgd. defbagc精品学习资料精选学习资料 - - - 欢迎下载abcdge图 6.1f14.一 棵abcdef gh二叉树如图6.2 所示,其中序遍历的序列为 ；a精品学习资料精选学习资料 - - - 欢迎下载abcdefgha. 图 6.2abdgcefhb.dgbaechfc.gdbehfcad.精品学习资料精选学习资料 - - - 欢迎下载15设 a、b 为一棵二叉树上的两个结点,在中序遍历时,a 在 b 前的条件为；aa 在 b 的右方b a 在 b 的左方ca 为 b 的祖先d a 为 b 的子孙16. 已知某二叉树的后序遍历序列为dabec ,中

27、序遍历序列为debac,它的前序遍历序列为 ；a.acbedb. decabc. deabcd. cedba17. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构,正确方案为二叉树采纳 储备结构；a. 二叉链表b.广义表储备结构c.三叉链表d.次序储备结构18. 如图 6.3 所示的 4 棵二叉树, 不为完全二叉树；精品学习资料精选学习资料 - - - 欢迎下载abcd图 6.320.b.21.错误22.a.正确23.24.在线索化二叉树中,t 所指结点没有左子树的充要条件为 ；a. t left=nullb. t ltag=1c. t ltag=1且t left=nulld.以上都不对二

28、叉树按某种次序线索化后,任一结点均有指向其前驱和后续的线索,这种说法 ；a.正确二叉树为二叉排序树的充分必要条件为其任一结点的值均大于其左孩子的值.小于其右孩子的值；这种说法 ；b. 错误具有五层结点的二叉平稳树至少有 个结点；a. 10b. 12c. 15d. 17树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历.中序遍历和后序遍历；这里,我们把由树转化得到的二叉树叫做这棵数对应的二叉树；结论 为正确的；a. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同b. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同c.树的先根遍历序列与其对应的二叉树的中序遍历序列

29、相同d.以上都不对25. 树最适合用来表示 ；a. 有序数据元素b.无序数据元素c. 元素之间具有分支层次关系的数据d.元素之间无联系的数据6.2 填空题（将正确的答案填在相应的空中）精品学习资料精选学习资料 - - - 欢迎下载1. 有一棵树如图6.5 所示,回答下面的问题： 这棵树的根结点为 ； 这棵树的叶子结点为 ； 结点 k3 的度为 ； 这棵树的度为 ； 这棵树的深度为 ； 结点 k3 的子女为 ； 结点 k3 的父结点为 k12kkk3k4 k56精品学习资料精选学习资料 - - - 欢迎下载2. 指出树和二叉树的三个主要差别 . . ； ；图 6.5一棵树k7精品学习资料精选学习

30、资料 - - - 欢迎下载3. 从概念上讲,树与二叉树为两种不同的数据结构,将树转化为二叉树的基本目的为 _；4. 一棵二叉树的结点数据采纳次序储备结构,储备于数组t 中, 如图 6.6 所示, 就该二叉树的链接表示形式为 ；5. 深度为 k 的完全二叉树至少有 个结点；至多有 个结点,如按自上而下,从左到右次序给结点编号（从1 开始）,就编号最小的叶子结点的编号为 ；89101112131415161718192021cjlhb1234567eafdg图 6.6一棵二叉树的次序储备数组t6. 在一棵二叉树中,度为零的结点的个数为n 0,度为 2 的结点的个数为n2,就有 n0 = ；7. 一

31、棵二叉树的第i （ i 1）层最多有 个结点；一棵有n（ n>0）个结点的满二叉树共有 个叶子和 个非终端结点；8. 结点最少的树为 ,结点最少的二叉树为 ；精品学习资料精选学习资料 - - - 欢迎下载9. 现有按中序遍历二叉树的结果为abc,问有 种不同外形的二叉树可以得到这一遍历结果,这些二叉树分别为 ；10. 由如图 6.7 所示的二叉树,回答以下问题： 其中序遍历序列为 ；精品学习资料精选学习资料 - - - 欢迎下载 其前序遍历序列为 ； 其后序遍历序列为 ；abcdef精品学习资料精选学习资料 - - - 欢迎下载h精品学习资料精选学习资料 - - - 欢迎下载6.3 简答

32、题1. 依据二叉树的定义,具有三个结点的二叉树有5 种不同的外形,请将它们分别画出；i图 6.7 一棵二叉树精品学习资料精选学习资料 - - - 欢迎下载2. 假设一棵二叉树的先序序列为ebadcfhgik和j请画出该树；3. 由如图 6.7 所示的二叉树,回答以下问题：（ 1）画出该二叉树的中序线索二叉树；（ 2）画出该二叉树的后序线索二叉树；中序序列为abcdefghij；ka精品学习资料精选学习资料 - - - 欢迎下载（ 3）画出该二叉树对应的森林；bcd4. 已知一棵树如图6.8 所示, 转化为一棵二叉树,表示为 ；efg图 6.8 一棵树5. 以数据集 4 , 5, 6, 7,10

33、, 12,18 为结点权值,画出构造huffman 树的每一步图示,运算其带权路径长度为；6. 一棵含有n 个结点的k 叉树 、 可能达到的最大深度和最小深度各为多少.7. 证明 : 一棵满 k 叉树上的叶子结点数n 0 和非叶子结点数n1 之间满意以下关系: n0 =k-1n1 +16.4 算法设计题1. 编写按层次次序（同一层自左至右）遍历二叉树的算法；2试编写算法,对一棵二叉树、 统计叶子的个数；3试编写算法,对一棵二叉树根结点不变,将左.右子树进行交换,树中每个结点的左.右子树进行交换；7. 假设用于通讯的电文仅有八个字母a、b、c、d、e、f、g、h组成,字母在电文中显现的频率分别为

34、0.07、0.19、0.02、0.06、 0.32、 0.03、 0.21、 0.10；试为这八个字母设计哈夫曼编码；使用 0-7 的二进制表示形式为另一种编码方案；对于上述实例,比较两种方案的优缺点；8. 试编写算法,对一棵以孩子- 兄弟链表表示的树统计叶子的个数；假设一棵二叉树的先序序列为ebadcfhgikj和中 序序列为abcdefghij；k 请画出该树；习题答案6.11. b2. b3. c4. c5. c6. a7. d8. a9. c 10. a11. d2. a13. b14. b15. b 16. d 17. c18. c19. b20. b 21. b22. b23. b

35、 24. a 25. c6.21. k1 k2、k5、k7、k4 2 3 4 k5、k6 k12. 树的结点个数至少为1 不同教材规定不同 ,而二叉树的结点个数可以为0；精品学习资料精选学习资料 - - - 欢迎下载树中结点的最大度数没有限制,而二叉树结点的最e树的结点无左.右之分,而二叉树的结点有左.右af大度数为2； 之分；精品学习资料精选学习资料 - - - 欢迎下载3. 树可采纳孩子 - 兄弟链表（二叉链表）做储备结构,目的并利用二叉树的已有算法解精品学习资料精选学习资料 - - - 欢迎下载决树的有关问题；4. 如图 6.9 所示k-1kk-25. 2. 2-1. 2+16. n2+

36、1dgcjlh精品学习资料精选学习资料 - - - 欢迎下载7. 2i-12 logn+1-1log22n+1 1b精品学习资料精选学习资料 - - - 欢迎下载28. 只有一个结点的树；空的二叉树9. 5；如图 6.10 所示图 6.9精品学习资料精选学习资料 - - - 欢迎下载ccaabbabcac abcb图 6.10 树形 5 种10. dgbaechif. abdgcefhi. gdbeihfca.6.31. 5种、图 6.112. 二叉树如图6.12 所示；e图 6.11 树 形 5 种bfadh3. 中序线索二叉树如图6.13 （左）所示；后序线索二叉树如图6.13（右） 所示

37、；精品学习资料精选学习资料 - - - 欢迎下载该二叉树转换后的的森林如图6.14 所示；cgi精品学习资料精选学习资料 - - - 欢迎下载aak精品学习资料精选学习资料 - - - 欢迎下载bcdefbcnulldefa cjf图 6.12b ehi精品学习资料精选学习资料 - - - 欢迎下载4. 图 6.8 的树转化为一棵二叉树如下,图6.15d ：jjhjha精品学习资料精选学习资料 - - - 欢迎下载nullii图 6.14b对应的森林c精品学习资料精选学习资料 - - - 欢迎下载6.13图8.18中序和后序线索树图edig图6.15一棵树的孩子兄弟表5. 画出构造huffma

38、n 树如图 6.16 所示,运算其带权路径长度为；6. 一棵含有n 个结点的k 叉树 、 可能达到的最大深度h=n-k+1,最小深度各为 : logk n+1；623725191813121096745图 6.16huffman 树精品学习资料精选学习资料 - - - 欢迎下载习题 7图7.1 单项选择题1在一个图中,全部顶点的度数之和等于全部边数的 倍；a. 1/2b. 1c. 2d. 42任何一个无向连通图的最小生成树；a. 只有一棵b. 有一棵或多棵c. 肯定有多棵d. 可能不存在 3在一个有向图中,全部顶点的入度之和等于全部顶点的出度之和的 倍；a. 1/2b. 1c. 2d. 44一

39、个有n 个顶点的无向图最多有 条边；a. nb. nn-1c. nn-1/2d. 2n5具有 4 个顶点的无向完全图有 条边；a. 6b. 12c. 16d. 20精品学习资料精选学习资料 - - - 欢迎下载6具有 6 个顶点的无向图至少应有 a. 5b. 6c. 7d. 8 条边才能确保为一个连通图；精品学习资料精选学习资料 - - - 欢迎下载7在一个具有n 个顶点的无向图中,要连通全部顶点至少需要a. nb. n+1c. n-1d. n/2 条边；精品学习资料精选学习资料 - - - 欢迎下载228对于一个具有n 个顶点的无向图,如采纳邻接矩阵表示,就该矩阵的大小为 ；a. nb. n

40、-1c. n-1d. n9对于一个具有n 个顶点和e 条边的无向图,如采纳邻接表表示,就表头向量的大小为_ ；全部邻接表中的接点总 数 为 _ ； a. nb. n+1c. n-1d. n+e a. e/2b. ec.2ed. n+e10已知一个图如图7.1 所示,如从顶点a 动身按深度搜寻法进行遍历,就可能得到的一种顶点序列为 ；按宽度搜寻法进行遍历,就可能得到的一种顶点序列为 ； a. a、b、e、c、d、fb. e、c、f、e、b、dc. a、e、b、c、f、dd. a、e、d、f、c、b精品学习资料精选学习资料 - - - 欢迎下载 a. a、b、c、e、d、fb. a、b、c、e、f

41、、dc. a、e、b、c、f、dd. a、c、f、d、e、ba精品学习资料精选学习资料 - - - 欢迎下载becdf图 7.1一个无向图11已知一有向图的邻接表储备结构如图7.2 所示；13223454 524图 7.2一个有向图的邻接表储备结构 依据有向图的深度优先遍历算法,从顶点v1 动身,所得到的顶点序列为 ；a. v1、v2、v3、v5、v4b. v1、v2、v3、v4、v5精品学习资料精选学习资料 - - - 欢迎下载c. v1、v3、v4、v5、v2d. v1、v4、v3、v5、v2 依据有向图的宽度优先遍历算法,从顶点v1 动身,所得到的顶点序列为 ；a. v1、v2、v3、v

42、4、v5b. v1、v3、v2、v4、v5c. v1、v2、v3、v5、v4d. v1、v4、v3、v5、v2 12采纳邻接表储备的图的深度优先遍历算法类似于二叉树的 ；a. 先序遍历b.中序遍历c.后序遍历d.按层遍历13采纳邻接表储备的图的宽度优先遍历算法类似于二叉树的 ；a.先序遍历b.中序遍历c.后序遍历d.按层遍历14判定一个有向图为否存在回路除了可以利用拓扑排序方法外,仍可以利用 ；a.求关键路径的方法b.求最短路径的dijkstra方法c.宽度优先遍历算法d.深度优先遍历算法15关键路径为大事结点网络中；a. 从源点到汇点的最长路径b.从源点到汇点的最短路径c. 最长的回路d.最

43、短的回路16下面不正确的说法为；（ 1）在 aoe网中,减小一个关键活动上的权值后,整个工期也就相应减小；（ 2） aoe网工程工期为关键活动上的权之和；（ 3）在关键路径上的活动都为关键活动,而关键活动也必在关键路径上；a. （1）b. （2）c. （3）d. （ 1）.（ 2）17用 dfs遍历一个无环有向图,并在dfs算法退栈返回时打印出相应的顶点,就输出的顶点序列为；a. 逆拓朴有序的b. 拓朴有序的c. 无序的 18在图 7.3 所示的拓朴排列的结果序列为；a.125634b.516234c.123456d.52163419一个有n 个顶点的无向图连7通.3 有图向,图它所包含的连通

44、重量个数为；a.0b.1c.nd.n+120对于一个有向图,如一个顶点的入度为k1、 .出度为k2,就对应邻接表中该顶点单链表中的结点数为；a.k1b.k2c.k1-k2d.k1+k221对于一个有向图,如一个顶点的入度为k1、 .出度为k2,就对应逆邻接表中该顶点单链表中的结点数为；a.k1b.k2c.k1-k2d.k1+k27.2 填空题（将正确的答案填在相应饿空中）1 n 个顶点的连通图至少 条边；2在无权图 g的邻接矩阵a 中,如vi、vj或 vi、vj属于图g的边集合,就对应元素aij等于 ,否就等于 ；3在无向图g的邻接矩阵a 中,如 aij等于 1,就 aji 等于 ；精品学习资

45、料精选学习资料 - - - 欢迎下载4已知图g 的邻接表如图7.4所示,其从顶点v1 动身的深度有限搜寻序列为序列为 ； ,其从顶点v1 动身的宽度优先搜寻精品学习资料精选学习资料 - - - 欢迎下载精品学习资料精选学习资料 - - - 欢迎下载v1 v2 v3v4v5v6v2v5v4v3v5v6v4v6v3图 7.4图 g的邻接表精品学习资料精选学习资料 - - - 欢迎下载5已知一个有向图的邻接矩阵表示,运算第i 个结点的入度的方法为 ；6已知一个图的邻接矩阵表示,删除全部从第i 个结点动身的边的方法为 ；精品学习资料精选学习资料 - - - 欢迎下载7假如含n 个顶点的图形成一个环,就

46、它有棵生成树；8一个非连通无向图,共有28 条边,就该图至少有个顶点；9遍历图的过程实质上为；bfs 遍历图的时间复杂度为, dfs 遍历图的时间复杂度为,两者不同之处在于,反映在数据结构上的差别为；10一个图的表示法为唯独的,而表示法为不唯独的；11有向图中的结点前驱后继关系的特点为；12如无向图g的顶点度数最小值大于等于时, g至少有一条回路；13依据图的储备结构进行某种次序的遍历,得到的顶点序列为的；7.3 综合题1已知如图7.5 所示的有向图,请给出该图的:（ 1）每个顶点的入/ 出度；15（ 2）邻接距阵；（ 3）邻接表；（ 4）逆邻接表；6（ 5）强连通重量；243图 7；5 一个

47、有向图2请用克鲁斯卡尔和普里姆两种算法分别为图7.6 .图 7.7 构造最小生成树：精品学习资料精选学习资料 - - - 欢迎下载（ 1）a161115精品学习资料精选学习资料 - - - 欢迎下载b15c15d精品学习资料精选学习资料 - - - 欢迎下载1316e141221f精品学习资料精选学习资料 - - - 欢迎下载图 7.6精品学习资料精选学习资料 - - - 欢迎下载（ 2）62121216131524716592010354图 7.7精品学习资料精选学习资料 - - - 欢迎下载3试列出图7.8 中全部的拓扑排序序列；123456图 7.8精品学习资料精选学习资料 - - - 欢迎下载4请用图示说明图7.9 从顶点 a 到其余各顶点之间的最短路径；5bd36a232f35ce图 74.95已知 aoe网有 9 个结点： v1, v2,v3, v4,v5, v6, v7, v8, v9,其邻接矩阵如下：(1) 请画出该aoe图；(2) 运算完成整个方案需