数据结构练习题(含答案)

数据构造练习题习题1 绪论1.1 单选题1 数据构造是一门研究非数值计算的程序设计问题中,数据元素的 、数据信息在计算机中的 以及一组有关的运算等的课程。 A操作对象 B.计算措施 逻辑构造 D数据映象 A存储构造 关系 C运算 D.算法2.数据构造D(Dt Strt）可以被形式地定义为=（D，R),其中D是 的有限集合，R是D上的 有限集合。 .算法 .数据元素 数据操作 .数据对象 .操作 .映象 存储 .关系3在数据构造中，从逻辑上可以把数据构造提成 。A.动态构造和静态构造 紧凑构造和非紧凑构造 C线性构造和非线性构造 .内部构造和外部构造4. 算法分析的目的是 ，算法分析的两个重要方面是 。 A.找出数据构造的合理性 研究算法中的输入和输出的关系. 分析算法的效率以求改善 D. 分析算法的易懂性和文档性 A. 空间复杂性和时间复杂性 B.对的性和简要性C 可读性和文档性 D. 数据复杂性和程序复杂性5.计算机算法指的是 ,它必具有输入、输出和 等五个特性。 A 计算措施 . 排序措施 解决问题的有限运算序列 D.调度措施A. 可行性、可移植性和可扩大性 B. 可行性、拟定性和有穷性 C. 拟定性、有穷性和稳定性 D. 易读性、稳定性和安全性1.2 填空题(将对的的答案填在相应的空中)1. 数据逻辑构造涉及 、 和 三种类型,树形构造和图形构造合称为 。2. 在线性构造中,第一种结点 前驱结点,其他每个结点有且只有 个前驱结点；最后一种结点 后续结点,其他每个结点有且只有 个后续结点。3.在树形构造中,树根结点没有 结点，其他每个结点有且只有 个直接前驱结点，叶子结点没有 结点，其他每个结点的直接后续结点可以 。4. 在图形构造中，每个结点的前驱结点数和后续结点数可以 。5.线性构造中元素之间存在 关系，树形构造中元素之间存在 关系，图形构造中元素之间存在 关系。6 算法的五个重要特性是_ _ , _， _ _ ,_ _， _。7. 分析下面算法（程序段），给出最大语句频度 ，该算法的时间复杂度是_ _。for(i=0;n;+） or(=0;jn； j+) j=;8 分析下面算法（程序段),给出最大语句频度 ,该算法的时间复杂度是_ _。for(i0；i;i+) fo (j; ; j+)ij=0；9. 分析下面算法（程序段),给出最大语句频度 ，该算法的时间复杂度是 _。s=0;for (=0;i;i+) fr (j=0;jn;j+) for (k0;kext=ULC. head-next= head .hed！=UL.带头结点的单链表had为空的鉴定条件是_。A. hedNULL B. heaex =NULL head-net= =head . head!=NULL 非空的循环单链表hed的尾结点（由所指向）满足_。. p-next= NUL . = =ULLC. p-next= =head D. p= =ead 在双向循环链表的p所指结点之后插入所指结点的操作是_。A. p-rgt; -lef=; p-righ=； s-rigtpght；. p-ght=s; -rght-left=s； s-lft=p； sriht=p-right；C s-et=； s-riht=pright; -right=s； p-riht-lef=;D. s-et；s-rht=-right； -rih-les; prigh=; 11.在一种单链表中,已知q所指结点是所指结点的前驱结点，若在q和之间插入s结点，则执行_。A. s-next=pex; p-xt=s; B. next=-nex; -xt=p;B. qxt=； s-nx=p; C. -next=s; s-nx=q；12. 在一种单链表中，若p所指结点不是最后结点,在之后插入s所指结点,则执行_。A. -ext=p; p-nex=; B. -next=p-nt； p-t=s；C snt=p-next; p=s; C. p-et=s; s-next=p;13. 在一种单链表中，若删除所指结点的后续结点，则执行_。A.p-nex=p-nxt-nt;B. pp-ext; p-et= next-；. p-ex p-nex； p p-nxtnxt;4. 从一种具有个结点的单链表中查找其值等于x结点时,在查找成功的状况下,需平均比较_个结点。A n B. n/2 C. (n-)/2 D (n+）/2 15. 在一种具有n个结点的有序单链表中插入一种新结点并仍然有序的时间复杂度是 _。A.O(1) . O() C. O（n2) . (nlgn） .给定有n个元素的向量，建立一种有序单链表的时间复杂度是_ _。 O(1)） BO() C. O (n2) D. O (n*lg2n)2.2 填空题(将对的的答案填在相应的空中）1. 单链表可以做_ _的链接存储表达。2. 在双链表中,每个结点有两个指针域，一种指向_ _,另一种指向_。3.在一种单链表中p所指结点之前插入一种s(值为e)所指结点时,可执行如下操作:q=hd;wh (-ext!=) q=next;s= new Node; s-daa=；q-nex ; /填空s-nex= ; /填空4 在一种单链表中删除p所指结点的后继结点时,应执行如下操作:q= -et;-nt= _ _； /填空delete ; /填空5 在一种单链表中p所指结点之后插入一种s所指结点时,应执行s-next=_ _和p-ext=的操作。 6. 对于一种具有n个结点的单链表，在已知p所指结点后插入一种新结点的时间复杂度是_ _；在给定值为x的结点后插入一种新结点的时间复杂度是_ _。2.3 算法设计题:1.设顺序表中的数据元数递增有序。试写一算法,将x插入到顺序表的合适位置上，以保持该表的有序性。tatusnsrt_SqList（SqList &v，int x) if(v.leng+1maxsiz） retrn RROR; vaet+; for（i=a.lngth-1；eleix&i0;i-) va.li+=v.elei; va.elem+=x;rturn K； 2.试写一算法,实现顺序表的就地逆置，即运用原表的存储空间将线性表(1,2, n）逆置为(an, a，., a1)。void rerse(nt a, it ze) i ,j,m; fr(i=0, jize-1; inext; wil(q!L & q-aanext；whil(q!L & q-datab)r=;=q-next;e(); i(p!q)pnetq;4. 试写一算法，实现单链表的就地逆置（规定在原链表上进行)。oi cnverse(NODT L)NODEPT ,q; =L-next; q=pext; L-neNULL; wile（) / 对于目前结点p,用头插法将结点p插入到头结点之后 */ p-ext=Lext; L-ext=p; pq; qq-xt; 习题答案 2 1 2.A，C 3.B 4. D . C 6. A 7. 8B 9.C 1.D 1 .B 13.A 1.D 1. 16C .2 1. 线性结表 . 前驱结点、后继结点 . , p 4. q-ex, q 5. p-ext, 6. O(1) , O （n)习题3 栈和队列 单选题. 一种栈的入栈序列a,b,c,d，则栈的不也许的输出序列是_。 A. edcba B. decba C.dceab D. abcde2 若已知一种栈的入栈序列是1，2，3，,，其输出序列为p1，p2，p3,pn，若p1=n,则pi为_。 A B. i C. i D.不拟定3. 栈构造一般采用的两种存储构造是_。A. 顺序存储构造和链式存储构造B. 散列方式和索引方式C. 链表存储构造和数组D. 线性存储构造和非线性存储构造4 鉴定一种顺序栈ST(最多元素为0）为空的条件是_。A. op ！=0 B.top= =0 C top ！=m0 D. top= 0-15. 鉴定一种顺序栈ST(最多元素为0）为栈满的条件是_。top！=0 B. tp 0 C. o!0 D. to= =m-16. 栈的特点是_,队列的特点是_。 . 先进先出 B. 先进后出7. 向一种栈顶指针为HS的链栈中插入一种所指结点时，则执行_ _。(不带空的头结点)A. HSnexts;. snex= HSnext； HSnt=;C. xtH; HS=s;D. xt= HS； HS= HSnx;.从一种栈顶指针为HS的链栈中删除一种结点时,用x保存被删结点的值,则执行_ _。(不带空的头结点) . x=HS; S= HSnext; B. x=Sa;C. HS= Hnt; x=Sta; D. x=Sdta； HS= Hext；9. 一种队列的数据入列序列是1，3,，则队列的出队时输出序列是_ 。 A. ,3，2，1 .1,2，3,4 C. 1,4，3，2 D. 3,2，10. 鉴定一种循环队列Q（最多元素为m0)为空的条件是_。A ear - front=m0 B. rear-ont1= =m0C. ront= = rear D. front= ea+11.鉴定一种循环队列QU(最多元素为m, 0= =axsize)为满队列的条件是_。. (rear-front)+ Maxsie) Maxse = m0. rear-on-= =m0 C. frn= =re D. front= = rar11. 循环队列用数组A0,m1寄存其元素值，已知其头尾指针分别是font和rear,则目前队列中的元素个数是_。A. (rer-rn+m)%m B. ea-fnt+1C.rearfront a-o3.栈和队列的共同点是_。A. 都是先进后出 B 都是先进先出C. 只容许在端点处插入和删除元素 D 没有共同点.2 填空题（将对的的答案填在相应的空中）. 向量、栈和队列都是_构造，可以在向量的_位置插入和删除元素；对于栈只能在_插入和删除元素；对于队列只能在_插入元素和_删除元素。2.向一种长度为n的向量的第i个元素(i+1)之前插入一种元素时,需向后移动_个元素。3 向一种长度为n的向量中删除第i个元素（1in）时，需向前移动_个元素。4. 在具有n个单元的循环队列中,队满时共有_个元素。 习题答案3.1 1. C 2. 3. 4.B 5.D 7C . B 9. C 1. 1 A 12. A 13.C 3.2 1. 线性、任何、栈顶、队尾、队首 2 -+ 3. -i 1 习题6 树和二叉树6.1 单选题. 由于二叉树中每个结点的度最大为，因此二叉树是一种特殊的树,这种说法_。A. 对的 B. 错误2 假定在一棵二叉树中,双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。 A.15 6 C17 D73 按照二叉树的定义,具有3个结点的不同形状的二叉树有_种。A B. 4 C D 4. 按照二叉树的定义,具有3个不同数据结点的不同的二叉树有_种。A. 5 B 6 .30 D325 深度为的二叉树至多有_个结点。.1 . 32 C. 31 D. 16. 设高度为h的二叉树上只有度为0和度为的结点，则此类二叉树中所涉及的结点数至少为_ _。A 2h B. 2- C. h+1 D h17 对一种满二叉树,m个树叶，n个结点，深度为h,则_ 。A. n=h+ B.m=n C. m=1 2 18.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对顺序_。A.不发生变化 B.发生变化 C不能拟定 .以上都不对9. 如果某二叉树的前根顺序遍历成果为tv，中序遍历为uwtvs，那么该二叉树的后序为_。 A. uwvts .vut . wvts D. uv10 二叉树的前序遍历序列中，任意一种结点均处在其子女结点的前面，这种说法_。 A. 对的 B. 错误11. 某二叉树的前序遍历结点访问顺序是acefh,中序遍历的结点访问顺序是gbachf，则其后序遍历的结点访问顺序是_。A bdgha B. dbcf .dghf .gdbhfa12.在一非空二叉树的中序遍历序列中，根结点的右边_。A 只有右子树上的所有结点 B. 只有右子树上的部分结点C 只有左子树上的部分结点 D. 只有左子树上的所有结点3如图.1所示二叉树的中序遍历序列是_。. abcdgef . dfebac C aefc . efbagcgcefdbaagedbchf图6.2 图6 a14.一棵二叉树如图6.2所示，其中序遍历的序列为_ _。A. abdefh .dgehf C. gdehfc D. abcdeha15设a,b为一棵二叉树上的两个结点，在中序遍历时,在b前的条件是 。a在b的右方Ba在的左方C.是b的祖先.a是b的子孙1已知某二叉树的后序遍历序列是daec,中序遍历序列是dec,它的前序遍历序列是_。 A. acbd B.eab .db D. cdba17. 实现任意二叉树的后序遍历的非递归算法而不使用栈构造,最佳方案是二叉树采用_存储构造。A. 二叉链表 广义表存储构造 C. 三叉链表 顺序存储构造1. 如图6.3所示的4棵二叉树,_不是完全二叉树。(A) (B) (C) (D)图6.320. 在线索化二叉树中,t所指结点没有左子树的充要条件是_。A.tlef=NL B tag=1C. tlg=1且tet=NLL D. 以上都不对21 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法_。 . 对的 B 错误22.二叉树为二叉排序树的充足必要条件是其任一结点的值均不小于其左孩子的值、不不小于其右孩子的值。这种说法_。 A 对的 B. 错误2. 具有五层结点的二叉平衡树至少有_个结点。A.1 B1 C 5 24 树的基本遍历方略可分为先根遍历和后根遍历；二叉树的基本遍历方略可分为先序遍历、中序遍历和后序遍历。这里,我们把由树转化得到的二叉树叫做这棵数相应的二叉树。结论_是对的的。.树的先根遍历序列与其相应的二叉树的先序遍历序列相似B.树的后根遍历序列与其相应的二叉树的后序遍历序列相似C.树的先根遍历序列与其相应的二叉树的中序遍历序列相似D.以上都不对5. 树最适合用来表达_。A. 有序数据元素 B.无序数据元素. 元素之间具有分支层次关系的数据 元素之间无联系的数据. 填空题（将对的的答案填在相应的空中）1. 有一棵树如图6.5所示,回答下面的问题：k1 11kkkkkk21 4356 7这棵树的根结点是_; 这棵树的叶子结点是_； 结点k3的度是_;图6.5 一棵树 这棵树的度是_；这棵树的深度是_；结点k3的子女是_； 结点3的父结点是_ 2.指出树和二叉树的三个重要差别_、_、_。_；3. 从概念上讲，树与二叉树是两种不同的数据构造,将树转化为二叉树的基本目的是_ 。123456789101112131415161718192021eafdgcjlhb图6.6 一棵二叉树的顺序存储数组t4.一棵二叉树的结点数据采用顺序存储构造,存储于数组t中，如图6.6所示,则该二叉树的链接表达形式为_ _。 深度为k的完全二叉树至少有_个结点。至多有_个结点,若按自上而下，从左到右顺序给结点编号(从1开始),则编号最小的叶子结点的编号是_。6. 在一棵二叉树中,度为零的结点的个数为n 0，度为2的结点的个数为 ，则有n0=_。7. 一棵二叉树的第i(i1)层最多有_个结点;一棵有n（n0）个结点的满二叉树共有_个叶子和_个非终端结点。8. 结点至少的树为_，结点至少的二叉树为_。9. 既有按中序遍历二叉树的成果为b，问有_种不同形态的二叉树可以得到这一遍历成果，这些二叉树分别是_。0. 由如图6.所示的二叉树，回答如下问题：iaedbchHf图6.7 一棵二叉树i其中序遍历序列为_； 其前序遍历序列为_； 其后序遍历序列为_;63 简答题1.根据二叉树的定义,具有三个结点的二叉树有种不同的形态,请将它们分别画出。2. 假设一棵 二叉树的先序序列为EACFHGIJ和中序序列为ACDFGIJK。gcefdba图6.8 一棵树请画出该树。 由如图67所示的二叉树,回答如下问题:(1）画出该二叉树的中序线索二叉树；（2）画出该二叉树的后序线索二叉树；(3)画出该二叉树相应的森林。4. 已知一棵树如图6.8所示,转化为一棵二叉树,表达为_。5. 以数据集,5,6，7,0,12,18为结点权值，画出构造Hufmn树的每一步图示，计算其带权途径长度为。6一棵具有个结点的叉树,也许达到的最大深度和最小深度各为多少？. 证明:一棵满k叉树上的叶子结点数n和非叶子结点数n之间满足如下关系: n=(k-1)n+16.4 算法设计题1编写按层次顺序(同一层自左至右)遍历二叉树的算法。2试编写算法,对一棵二叉树,记录叶子的个数。3试编写算法,对一棵二叉树根结点不变,将左、右子树进行互换，树中每个结点的左、右子树进行互换。7. 假设用于通讯的电文仅有八个字母（,b,c,d,e,h)构成，字母在电文中浮现的频率分别为0.07, 0.19,.0,0.0，0.3， 0.03, 0.21, 010。试为这八个字母设计哈夫曼编码。使用7的二进制表达形式是另一种编码方案。对于上述实例，比较两种方案的优缺陷。8. 试编写算法，对一棵以孩子兄弟链表表达的树记录叶子的个数。假设一棵 二叉树的先序序列为EBADCFHGIK和中序序列为BCDFGHIJK。请画出该树。 习题答案6 1. 2. B 3. C 4. C . C 6.A 7 D 8.A 9. C 10. A1D 2. A 13. B 4. B . B . D17. C 18 C 19. B 20. B 21 B 22. B 2. B 24 A . C 6. . k1 k2,k5,k，k4 2 3 5,k6 eaEfjcdlghb图6.92 树的结点个数至少为1(不同教材规定不同),而二叉树的结点个数可觉得;树中结点的最大度数没有限制,而二叉树结点的最大度数为2；树的结点无左、右之分，而二叉树的结点有左、右之分；3.树可采用孩子-兄弟链表（二叉链表)做存储构造，目的并运用二叉树的已有算法解决树的有关问题。 如图.9所示 5. 2 k-1 、 k-1 、 2k-+1 6 2+1 . 2 i-1 2g2n+11 2og21 1 . 只有一种结点的树；空的二叉树9. 5;如图.1所示a图6.10 树形5种aaaacccccbbbbbb1 dbaech 、befhi 、gbeihfa 、. 1. 5种, 图6.11EBEFAECDKGHIJ图6.12图6.11 树形5种2二叉树如图6.2所示。3. 中序线索二叉树如图6.1（左)所示；后序线索二叉树如图6.13（右）所示；该二叉树转换后的的森林如图6.14所示。图6.13a 11dhjbkc 图 6.14 相应的森林iefabcedig图 6.15 一棵树的孩子兄弟表达4. 图68的树转化为一棵二叉树如下,图6.5:5.画出构造Hufmn树如图.1所示，计算其带权途径长度为 。6. 一棵具有N个结点的k叉树，也许达到的最大深度 h-k+1 ,最小深度各为: lk+1。623725191813121096745图6.16 Huffman树习题7 图71 单选题1.在一种图中,所有顶点的度数之和等于所有边数的_倍。. 1/2 B. 1 C. 2 .4 .任何一种无向连通图的最小生成树 。A.只有一棵B有一棵或多棵C一定有多棵D.也许不存在3在一种有向图中，所有顶点的入度之和等于所有顶点的出度之和的_倍。A 1/2 B.1 C 2 .44.一种有个顶点的无向图最多有_条边。. B. n(-） C. n(-1)/2 2n具有4个顶点的无向完全图有_条边。A B. 1 D. 06具有6个顶点的无向图至少应有_条边才干保证是一种连通图。A B.6 C. 7 D 87在一种具有n个顶点的无向图中，要连通所有顶点至少需要_条边。A. n B.n+1 C. -1 D n8.对于一种具有n个顶点的无向图,若采用邻接矩阵表达,则该矩阵的大小是_。A. n B (n-1)2 C. -1 D. n29对于一种具有n个顶点和条边的无向图，若采用邻接表表达,则表头向量的大小为_;所有邻接表中的接点总数是_。 A. B. n C. n-1 D. n+eA.e/2 B. e 2e D. n+ 10已知一种图如图.1所示,若从顶点a出发按深度搜索法进行遍历,则也许得到的一种顶点序列为_;按宽度搜索法进行遍历，则也许得到的一种顶点序列为_。 A. a,e，,d, e,c，,e,b,d C. a,e,b,c,d . a，e，d,f,c,baecdf . ,，c,e,， ,c,e，f, C. a,e,b,c,f,d D. a，c，f,d，图 7.1 一种无向图11.已知一有向图的邻接表存储构造如图.所示。12345324524图7.2 一种有向图的邻接表存储构造 根据有向图的深度优先遍历算法,从顶点出发，所得到的顶点序列是_。A. 1,v2,v3,v,v4 B. v1,v2，v3,v4,v5C. v1,v,v,v2 D. v,v4,v，v2 根据有向图的宽度优先遍历算法，从顶点v1出发,所得到的顶点序列是_。. 1，v2,v3,v4,v5 .v1,v3，v2,v4,v5C.v1,v2,v，v4 D1,v4,v3,v5,v2采用邻接表存储的图的深度优先遍历算法类似于二叉树的_。. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历1.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的_。A. 先序遍历 B. 中序遍历 C后序遍历 D. 按层遍历14鉴定一种有向图与否存在回路除了可以运用拓扑排序措施外，还可以运用_。A.求核心途径的措施 B. 求最短途径的Djstra措施C.宽度优先遍历算法 D.深度优先遍历算法15.核心途径是事件结点网络中 。A.从源点到汇点的最长途径 B从源点到汇点的最短途径C.最长的回路 D.最短的回路16.下面不对的的说法是 。 （1)在E网中,减小一种核心活动上的权值后,整个工期也就相应减小; (2）E网工程工期为核心活动上的权之和; (3）在核心途径上的活动都是核心活动，而核心活动也必在核心途径上。.(1）.(2）C.(3）D.（1）、(2）1.用DFS遍历一种无环有向图，并在F算法退栈返回时打印出相应的顶点，则输出的顶点序列是 。A逆拓朴有序的B.拓朴有序的C.无序的18.在图7.所示的拓朴排列的成果序列为 。A.264B.56234.12345D52134图7.3有向图9一种有n个顶点的无向连通图，它所涉及的连通分量个数为 。A.0.1.nD.n+120对于一种有向图,若一种顶点的入度为1,、出度为2，则相应邻接表中该顶点单链表中的结点数为 。A.kBk2C.k.k1+k221.对于一种有向图，若一种顶点的入度为k1,、出度为k2,则相应逆邻接表中该顶点单链表中的结点数为 。Ak1B.kC.k12D.k+k2. 填空题(将对的的答案填在相应饿空中)1n个顶点的连通图至少_条边。2.在无权图G的邻接矩阵中，若（i,)或属于图的边集合，则相应元素ij等于_,否则等于_。3在无向图的邻接矩阵A中,若ij等于1,则Aji 等于_。4已知图的邻接表如图7.4所示，其从顶点v1出发的深度有限搜索序列为_，其从顶点v1出发的宽度优先搜索序列为_。v1v3v2v4v5v6v2v5v4v3v5v6v4v6v3 图. 图的邻接表5.已知一种有向图的邻接矩阵表达，计算第i个结点的入度的措施是_。.已知一种图的邻接矩阵表达,删除所有从第i个结点出发的边的措施是_。如果含n个顶点的图形成一种环,则它有 棵生成树。8.一种非连通无向图,共有8条边,则该图至少有 个顶点。遍历图的过程实质上是 。BFS遍历图的时间复杂度为 ,F遍历图的时间复杂度为 ，两者不同之处在于 ,反映在数据构造上的差别是 。1.一种图的 表达法是唯一的，而 表达法是不唯一的。11.有向图中的结点前驱后继关系的特性是 。1若无向图G的顶点度数最小值不小于等于 时，G至少有一条回路。13.根据图的存储构造进行某种顺序的遍历，得到的顶点序列是 的。7.3 综合题1562431.已知如图7.5所示的有向图,请给出该图的:()每个顶点的入/出度;(2）邻接距阵；（）邻接表;（4)逆邻接表;（)强连通分量。图7。5一种有向图badcef161115151516131412212.请用克鲁斯卡尔和普里姆两种算法分别为图76、图7.7构造最小生成树：（1） 图7661213212495201516106154372(2) 图7.3.试列出图78中所有的拓扑排序序列。123456图7.请用图示阐明图7.9从顶点a到其他各顶点之间的最短途径。543223356abdfce图7.95.已知AO网有个结点：V,V2，V4,V，V6,7，V，V,其邻接矩阵如下：(1)请画出该AE图。(2)计算完毕整个筹划需要的时间。(3）求出该A网的核心途径。411974习题答案7.1 1 C2.B3B4. C. . A7.C8D9.AD . CB12.A13. D 4.D1A67.18.B.B20.B21.A 7.2 1.n 2. 1;0 3. 1 41,v2,v，v5,4;,v2,v5,v4，v3， 65求矩阵第i列非零元素之和 6. 将矩阵第i行所有置为零78.9.对每个顶点查找其邻接点的过程；O（e)（e为图中的边数)；(e);遍历图的顺序不同;DF采用栈存储访问过的结点,BFS采用队列存储访问过的结点。10.邻接矩阵 邻接表1.一种结点也许有若干个前驱，也也许有若干个后继1221唯一1562437.3 12badce1115131412f (1)612495106154372（2) 3.15236153152345123451624564134W=3W=7W=9W=6W=543233abdfce4.(1)该AE图为:(2)完毕整个筹划需要18天。（3)核心途径为：(V，V2，5，V7,V)和（V1, V，V8，V9,）习题8 查找8.1 单选题1.顺序查找法适合于存储构造为_的线性表。A 散列存储 B. 顺序存储或链接存储C. 压缩存储 D. 索引存储2.对线性表进行二分查找时,规定线性表必须_。A. 以顺序方式存储 .以链接方式存储C 以顺序方式存储，且结点按核心字有序排序D. 以链接方式存储,且结点按核心字有序排序3采用顺序查找措施查找长度为n的线性表时，每个元素的平均查找长度为_. n n/ C. (n+1)/2 D. （n-1)24采用二分查找措施查找长度为n的线性表时,每个元素的平均查找长度为_。.（n2） B. O(nlogn） . (n) . O（lon）5.二分查找和二叉排序树的时间性能_。A. 相似 .不相似有一种有序表为1,3，9,12,32，1，45，6，5,7,82，9,100，当二分查找值82为的结点时,_次比较后查找成功。A 1 B.2 D. 87.设哈希表长=4，哈希函数H(ke)=key%11。表中已有4个结点：add (15)=4; addr(38)=5; ad(61）6; adr(4）=如用二次探测再散列解决冲突,核心字为4的结点的地址是_。A. B.3 C. . 98.有一种长度为1的有序表,按二分查找法对该表进行查找，在表内各元素等概率状况下查找成功所需的平均比较次数为_。A. 35/12 B.712 C. 3/12 D. 4/2对于静态表的顺序查找法，若在表头设立岗哨,则对的的查找方式为 。从第0个元素往后查找该数据元素B.从第1个元素往后查找该数据元素.从第n个元素往开始前查找该数据元素.与查找顺序无关10解决散列法中浮现的冲突问题常采用的措施是 。A.数字分析法、除余法、平方取中法.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、多重散列法D.线性探测法、多重散列法、链地址法11.采用线性探测法解决冲突问题,所产生的一系列后继散列地址 。A.必须不小于等于原散列地址