数据结构错题.doc
《数据结构错题.doc》由会员分享,可在线阅读,更多相关《数据结构错题.doc(8页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、如有侵权,请联系网站删除,仅供学习与交流数据结构错题【精品文档】第 8 页一、图【1】各边权值不同的无向连通图的最小生成树是唯一的【2】当各边上的权值( 均相等 )时,BFS算法可用来解决单源最短路径问题解析:当权值相同,则最短路径问题转化为求边数最少的问题,BFS可以保证求得源点到汇点的最少边数【3】无向图:若V(G)中任意两个不同的顶点vi和vj都连通(即有路径),则称G为连通图。无向图G的极大连通子图称为G的最强连通分量有向图:有向图G中,若对于V(G)中任意两个不同的顶点vi和vj,都存在从vi到vj以及从vj到vi的路径,则称G是强连通图。有向图的极大强连通子图称为G的强连通分量。【
2、4】无向图存储:邻接矩阵、邻接表、多重邻接表有向图存储:邻接矩阵、邻接表、十字链表【5】若有向图不存在回路,即使不用访问标志位同一结点也不会被访问两次()解析:错误。如果一个点的入度大于1的话,就有可能被多次访问【6】有向图是否有环的判定算法,主要有深度优先和拓扑排序两种方法。【7】一个AOV网应该是一个有向无环图 ,即不应该带有回路,因为若带有回路,则回路上的所有活动都无法进行。既然AOV网是一个有向无环图,则其必然存在拓扑序列。【8】关键路径:1)顶点表示事件,弧表示活动 2)如果顶点A-B有弧,如果让弧表示为L,则A为L的弧尾,B为L的弧头,即有箭头的那一端叫头。【9】若无向图G = (
3、V.E)中含7个顶点,则保证图G在任何情况下都是连通的,则需要的边数最少是()解析:任何情况都连通的最少边数表示边分布最浪费的最少边情况,取点数减一的完全图6*5/2=15再加一条边得结果16【10】AOE网的定义:在带权有向图中若以顶点表示事件,有向边表示活动,边上的权值表示该活动持续的时间,这样的图简称为AOE网。从定义上来看,很容易看出两种网的不同,AOV网的活动以顶点表示,而AOE网的活动以有向边来表示,AOV网的有向边仅仅表示活动的先后次序。纵观这两种网图,其实它们总体网络结构是一样的,仅仅是活动所表示的方式不同,因此可以猜想从AOV网转换成AOE网应该是可行的。AOV网不能有环。A
4、OE网一定是有向无环图【11】关键活动延期完成,必将延期整个工程完成时间。如果有多条关键路径,此时延期的关键活动所在路径成为关键路径,其他原关键路径变为非关键路径。关键活动提前完成,不一定使整个工程提前完成。因为关键路径可能不唯一,一条路径上的关键活动提前,只能使这条路径变为非关键路径,其他关键路径不受影响。【12】图G的拓扑序列唯一,则其弧数必为n-1(其中n为G的顶点数)解析:错误。有向图的邻接矩阵上三角全为1即可达到拓扑唯一,那么边数为n(n-1)/2【13】无向图的邻接矩阵可用一维数组存储。解析:正确。习惯上无向图的邻接矩阵一般用二维数组存储,这样使用方便。当然,任意二维数组都是可以用
5、一维数组存储的,只是用起来不方便。【14】既使有向无环图的拓扑序列唯一,也不能唯一确定该图。解析:正确。如果顶点有多个直接后继,排序结果通常不唯一,所以拓扑排序的结果唯一的情况是,每个顶点有唯一的前驱后继关系。【15】用相邻矩阵法存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小与图中结点的个数有关,而与图的边数无关。这种说法( 正确 )【16】设G是一个具有6个顶点,11条边的图,其每个顶点的度为3或4,则图G是什么图?(A)A、G是平面图; B、G不连通; C、G为偶图(也称二部图); D、G不是哈密顿图。【17】p个顶点p条边的连通图中至少有多少个生成树?解析:3个。p个顶点p
6、条边的连通图中至少有多少个生成树,连通图相当于在树上多加了一条边,所以其中必然会有一个回路,生成树的数量应该等于回路的边数,如果不考虑重边和自环的情况最小的回路必然是3。【18】完全偶图(也称完全二部图) 既是欧拉图又是哈密顿图的充分必要条件是下列哪一个?m=n且m与n都是偶数;二、树【1】不含任何结点的空树( 是一棵树也是一棵二叉树 )。【2】如果T1是由有序树T转换而来的二叉树,那么T中结点的前序就是T1中结点的前序,T中结点的后序就是T1中结点的中序【3】树中的结点和图中的顶点就是指数据结构中的数据元素解析:对。数据元素是数据的基本单位。在计算机中作为一个整体考虑和处理。在有些情况下,数
7、据元素也称为元素、记录等,数据元素用于完整的描述一个对象,如图中的顶点。数据项是组成数据元素的、有独立含义的、不可分割的最小单位。如学生基本信息中的学号、姓名、性别等都是数据项。【4】如果有N个节点用二叉树结构来存储,那么二叉树的最小深度是多少?解析:以2为底2N的对数,向下取整【5】二叉树在线索化后,仍不能有效求解的问题是()。解析:后序线索二叉树中求后序后继。后序线索二叉树的遍历仍需要借助栈,但其他二者却不需要。【6】设F是一个森林,B是由F变换得到的二叉树。若F中有n个非终端结点,则B中右指针域为空的结点有( n+1 )个【7】在线索化二叉树中,节点t没有左子树的充要条件是( t-lta
8、g=1 )【8】在中序线索二叉树中,每一非空的线索均指向其祖先结点()解析:中序遍历的顺序为:左、根、右,所以对于每一非空的线索,左子树结点的后继为根结点,右子树结点的前驱为根结点,再递归的执行上面的过程,可得非空线索均指向其祖先结点。【9】若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是( 11 )解析:性质4:在任意一棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则n0=n2+1证明:因为二叉树中所有结点的度数均不大于2,所以结点总数(记为n)=0度结点数(n0) + 1度结点数(n1) + 2度结点数(n2)。由此,得到等式一。(等式一) n=n0+
9、n1+n2另一方面,0度结点没有孩子,1度结点有一个孩子,2度结点有两个孩子,故二叉树中孩子结点总数是:n1+2n2。此外,只有根不是任何结点的孩子。故二叉树中的结点总数又可表示为等式二。(等式二) n=n1+2n2+1由(等式一)和(等式二)计算得到:n0=n2+1。原命题得证!三、数组【1】关于 int a10; 问下面哪些不可以表示 a1 的地址?A、a+sizeof(int) B、&a0+1 C、(int*)&a+1 D、(int*)(char*)&a+sizeof(int)解析:A 不正确, 在32位机器上相当于指针运算 a + 4【2】int a23 = 0;printf(%x %
10、x %xn, a0, a1, &a12);printf(%x %x %xn, a, a + 1, &a + 1);输出:1da6e790 1da6e79c 1da6e7a4 1da6e790 1da6e79c 1da6e7a8【3】下面有关数据结构的说法是正确的?A、数组和链表都可以随机访问 B、数组的插入和删除可以 O(1)C、哈希表没有办法做范围检查 D、以上说法都不正确解析:B。在数组的开头或结尾插入和删除 是O(1),但正常情况下为O(n)所以说数组的插入和删除复杂度可能是O(1)。【4】一个非空广义表的表尾()A、不能是子表 B、只能是子表 C、只能是原子 D、是原子或子表解析:B。
11、(1)数据结构对广义表的表头和表尾是这样定义的: 如果广义表LS=(a1,a2.an)非空,则 a1是LS的表头,其余元素组成的表(a2,a3,.an)是称为LS的表尾。根据定义,非空广义表的表头是一个元素,它可以是原子也可以是一个子表,表尾则必定是子表。例如:LS=(a,b),表头为a,表尾是(b)而不是b.另外:LS=(a)的表头为a,表尾为空表(). (2)非空广义表,除表头外,其余元素构成的表称为表尾,所以非空广义表尾一定是个表【5】在Java中,下列说法错误的有( BCD )A、数组是一种对象 B、数组属于一种原生类 C、int number = 31,23,33,43,35,63;
12、 D、数组的大小可以任意改变【6】广义表(a,b,c),d,e,f)的长度是4()解析:错误;长度:去掉一层括号剩下的是几部分。 深度:去掉几层括号可以到最后一部分。比如: 例如E(a,(a,b),(a,b),c)的长度和深度分别为1和4【7】对n个记录的线性表进行快速排序为减少算法的递归深度,以下叙述正确的是()A、每次分区后,先处理较短的部分 B每次分区后,先处理较长的部分C、与算法每次分区后的处理顺序无关 D、以上三者都不对解析:A;在快速排序中,需要使用递归来分别处理左右子段,递归深度可以理解为系统栈保存的深度,先处理短的分段再处理长的分段,可以减少时间复杂度;如果按长的递归优先的话,
13、那么短的递归会一直保存在栈中,直到长的处理完。短的优先的话,长的递归调用没有进行,他是作为一个整体保存在栈中的,所以递归栈中的保留的递归数据少一些。【8】若要删除 book 表中的所有数据,如下哪些语法是错误的?A、drop table book; B、truncate table book; C、delete from book; D、delelet *from book;解析:A: drop table book 是删除整个表,题目的潜在意思是删除表中的数据而并非删除整个表。因此A错。B: truncate table book 是删除表中的数据,删除速度比delete更快,无法撤回(回退
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构
限制150内