《数据结构》复习题及参考答案.doc 64页

'《数据结构》复习题及参考答案`000101B1数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。~0001操作对象关系`000201B1数据结构被形式地定义为（D,R），其中D是的有限集合，R是D上的有限集合。~0002数据元素关系`000301B2数据结构包括数据的数据的和数据的这三个方面的内容。~0003逻辑结构存储结构运算`000401B1数据结构按逻辑结构可分为两大类，它们分别是和。~0004线性结构非线性结构`000501B1线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。~0005一对一一对多多对多`000601B1在线性结构中，第一个结点前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点后续结点，其余每个结点有且只有1个后续结点。~0006没有没有`000701B2在树形结构中，树根结点没有结点，其余每个结点有且只有个前驱结点；叶子结点没有结点，其余每个结点的后续结点数可以。~0007前驱1后续任意多个`000801B1在图形结构中，每个结点的前驱结点数和后续结点数可以。~0008任意多个`000901B2数据的存储结构可用四种基本的存储方法表示，它们分别是。~0009顺序链式索引散列`001001B2数据的运算最常用的有5种，它们分别是。~0010插入、删除、修改、查找、排序`001101B2一个算法的效率可分为效率和效率。~0011时间空间`001201C1非线性结构是数据元素之间存在一种：（）A、一对多关系B、多对多关系C、多对一关系D、一对一关系~0012B`001301C1 数据结构中，与所使用的计算机无关的是数据的（）结构；A、存储B、物理C、逻辑D、物理和存储~0013C`001401C1算法分析的目的是（）A、找出数据结构的合理性B、研究算法中的输入和输出的关系C、分析算法的效率以求改进D、分析算法的易懂性和文档性~0014C`001501C1算法分析的两个主要方面是（）A、空间复杂性和时间复杂性B、正确性和简明性C、可读性和文档性D、数据复杂性和程序复杂性~0015A`001601C2计算机算法指的是（）A、计算方法B、排序方法C、解决问题的有限运算序列D、调度方法~0016C`001701C2计算机算法必须具备输入、输出和（）等5个特性。A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性C、确定性、有穷性和稳定性D、易读性、稳定性和安全性~0017B`001801A2数据结构和数据类型两个概念之间有区别吗？~0018简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。`001901A1简述线性结构与非线性结构的不同点。~0019线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。`002001A2分析下面各程序段的时间复杂度：for(i=0;itop<>0Ｂ、ST->top=0Ｃ、ST->top<>m0Ｄ、ST->top=m0~0026B`002702B2向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动个元素。~0027n-i+1`002802B2向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动个元素。~0028n-i`002902B1在顺序表中访问任意一结点的时间复杂度均为，因此，顺序表也称为的数据结构。~0029O(1)随机存取`003002B1顺序表中逻辑上相邻的元素的物理位置相邻。单链表中逻辑上相邻的元素的物理位置相邻。~0030必定不一定`003102B1 在单链表中，除了首元结点外，任一结点的存储位置由指示。~0031其直接前驱结点的链域的值`003202B2在n个结点的单链表中要删除已知结点*p，需找到它的，其时间复杂度为。~0032前驱结点的地址O（n）`003302D1链表的每个结点中都恰好包含一个指针。（）~0033X`003402D1链表的物理存储结构具有同链表一样的顺序。（）~0034X`003502D1链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（）~0035X`003602D1线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）~0036X`003702D1顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（）~0037X`003802D1顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）~0038X`003902D1线性表在物理存储空间中也一定是连续的。（）~0039X`004002D1线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。（）~0040X`004102D1顺序存储方式只能用于存储线性结构。（）~0041X`004202D1线性表的逻辑顺序与存储顺序总是一致的。（）~0042X`004302C1数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（）A、存储结构B、逻辑结构C、顺序存储结构D、链式存储结构~0043C`004402C1一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）A、110B、108C、100D、120 ~0044B`004502C1在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）A、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B、在第i个结点后插入一个新结点（1≤i≤n）C、删除第i个结点（1≤i≤n）D、将n个结点从小到大排序~0045A`004602C2个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素A、8B、63.5C、63D、7~0046B`004702C2链接存储的存储结构所占存储空间（）A、分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B、只有一部分，存放结点值C、只有一部分，存储表示结点间关系的指针D、分两部分，一部分存放结点值，另一部分存放结点所占单元数~0047A`004802C1链表是一种采用（）存储结构存储的线性表；A、顺序B、链式C、星式D、网状~0048B`004902C1线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以~0049D`005002C1线性表Ｌ在（）情况下适用于使用链式结构实现。A、需经常修改Ｌ中的结点值B、需不断对Ｌ进行删除插入C、Ｌ中含有大量的结点D、Ｌ中结点结构复杂~0050B`005110B1若索引文件采用稠密索引,则每个索引项与主文件中的______记录相对应,若索引文件采用稀疏索引,则每个索引项与主文件中的_______记录相对应.~0051一个一组(成若干条)`005208E2已知一堆数组A中的数据如下,试写出在快速排序的过程中每次划分后数据的排序情况.12345678┌─┬─┬─┬─┬─┬─┬─┬─┐│45│28│64│53│15│36│74│30│└─┴─┴─┴─┴─┴─┴─┴─┘(1)(2)(3)~0052[30283615]45[537464] [1528]30364553[7464]1528303645536474`005308C1下列排序算法中,第一趟排序完毕后,其最大或最小元素不一定在其最终位置上的算法是()A、归并排序B、直接选择排序C、树形选择排序D、冒泡排序~0053A`005408C1直接插入排序的时间复杂度为().A、O(n)B、0(log2n)C、0(nlog2n)D、0(n2)~0054d`005510B1文件的检索和修改有两种方式______和______~0055实时的批量的`005610C2对顺序文件的检索方法可以是()A、顺序存取B、随机存取C、按关键字存取D、前三种方法都可以~0056D`005710B1在查找索引文件时,首先要查找_______;然后再查找________~0057索引表主文件`005808E3利用堆排序的方法给已知数组A中的数据排序,写出在构成初始堆和利用堆排序的过程中,每次筛运算后数据的排列情况:12345678┌─┬─┬─┬─┬─┬─┬─┬─┐A│45│28│49│16│37│82│56│75│└─┴─┴─┴─┴─┴─┴─┴─┘1.构成初始堆的过程(1)(2)(3)(4)2.利用堆排序的过程(1)(2)(3)(4)(5)(6)(7)~00581.(1)4528497537825616(2)4528827537495616(3)4575822837495616(4)82755628374945162.(1)7537562816494582(2)5637492816457582(3)4937452816567582(4)4537162849567582(5)3728164549567582(6)2816374549567582 (7)1628374549567582`005908E2判断以下序列是否为堆,若不是,调整为堆a.{12,15,23,35,28,87,49,86}b.{35,12,28,87,49,86,15,23}~0059a为堆b不是堆b相应的完全二叉树:(35)(35)(35)(12)(12)(12)(28)→(12)(28)→(12)(15)→(35)(15)→(23)(15)(87)(49)(86)(15)(23)(49)(86)(15)(23)(49)(86)(28)(23)(49)(86)(28)(35)(49)(86)(28)(23)(87)(87)(87)(87)b调整为堆排序列之后为{12,23,15,35,49,86,28,87}`006010C1堆排序的最坏时间复杂度为()A、0(n)B、0(log2n)C、0(nlog2n)D、0(n2)~0060c`006110B2设数组longintb[4][6]的首地址为s,按行主序方式存贮时元素b[2][4],b[3][4]的存贮地址分别为________~0061s+64s+88`006210E3设文件有12个记录,其关键字值分别为37,23,7,79,9,43,3,19,31,61,23",47,按非递减的次序进行排序试分别给出用下列方法排序时第一,二趟处理后的结果序列1.冒泡排序2.选择排序3.快速排序~00621.第一趟23,7,37,9,43,3,19,31,61,23",47,79第二趟7,23,9,37,3,19,31,43,23,47,61,792.第一趟37,23,7,47,9,43,3,19,31,61,23",79第二趟37,23,7,47,9,43,3,19,31,23",61,793.第一趟[23",23,7,31,9,3]37[43,61,79,47]第二趟[3,23,7,19,9]23"[31]37,43,[61,79,47]`006310B1文件按记录的结构可分为两类______和______,按记录中关键字的多少可分为______和________~0063定长记录文件不定长记录文件单关键字文件多关键字文件`006410B2外部分类包括______和________~0064磁带文件的归并分类磁盘文件的归并分类`006508B2设一组关键字为{23,3,39,9,7,5,16,8},进行线性插入分类,试写出第一遍分类后关键字的排列次序________~0065[23]339975168第一遍[323]39975168第二遍[32339]975168第三遍[3923397]5168第四遍[3792339]5168第五遍[35792339]168第六遍[3579162339]8第七遍[35789162339] `006608B2内部分类包括(任写六种)___________________________________~0066冒泡分类简单选择分类线性插入分类折半插入分类希尔分类快速分类堆分类归并分类基数分类`006710B1磁带主要由______,______,______组成.~0067磁带介质读写磁头磁带驱动器`006808B1分类的目的是____________________________~0068便于查询和处理数据`006908B2你所学过的排序的方法中,哪些是稳定的____________~0069直接插入二分(折半)插入冒泡归并排序枚举`007008C2下列排序算法中,排序花费的时间不受数据开始排列特性影响的算法是()A、直接插入排序B、冒泡排序C、直接选择排序D、快速排序~0070c`007108C2下列排序算法中,最好情况下时间复杂度为0(n)的算法是()A、选择排序B、归并排序C、快速排序D、冒泡排序~0071d`007208E3利用堆排序的方法给已知数据A中的数据排序,写出在构成初始堆和利用堆排序的过程中每次筛运算后数据的排列情况(要求构造大根堆)12345678┌─┬─┬─┬─┬─┬─┬─┬─┐A│45│28│49│16│37│82│56│75│└─┴─┴─┴─┴─┴─┴─┴─┘~00721:45284975378256162:45288275374956163:45758228374956164:82754528374956165:75374528164956826:56374528164975827:49374528165675828:45371628495675829:372816454956758210:281637454956758211:1628374549567582`007310B1根据排序文件所处的位置不同,可将排序分为______和______两大类.~0073内部外部`007408D1堆排序是不稳定排序()~0074正确`007510D1 文件中存取数据的基本单位是数据项()~0075错误`007608E2设文件有10个记录其关键字值分别为:37,23,7,79,29,43,73,19,31,61,试给出用冒泡排序法,按非递减的次序进行排序过程中的每一趟结果序列.~00763723779294373193161第一趟23737294373193161|79第二趟723293743193161|73三7232937193143|61四72329193137|43五723192931|37六7192329|31`007708D2堆排序与快速排序相比,堆比快速省时间()~0077错误`007810D2影响外排序的时间因素主要是内存与外设交换信息的总次数()~0078正确`007910B1ISAM文件由____,______,____和______组成.~0079主索引柱面索引磁道索引和主文件`008010B1顺序文件是指按记录进入文件的先后顺序存放,其________顺序和________顺序一致的文件.~0080逻辑物理`008110B1文件的存储结构是指文件在______上的组织形式~0081外存`008210B1常用的文件组织方式有______,________,______和______.~0082顺序文件.索引文件.散列文件.多关键字文件`008310B1文件是性质相同的______的集合.~0083记录`008410B1文件中存取的基本单位是________文件中可使用的最小单位是________~0084记录数据项`008510B1文件结构包括______,______以及在_______的各种操作~0085逻辑.物理.文件`008610B1文件上的基本操作主要有两类______和______~0086索引.维护`008710B1索引表中的每一项称为索引项,一段索引项都是由____和_____所在记录的物理地址组成的 ~0087主关键字.该关键字`008810B1在排序过程中,若整个文件被在内存中处理,排序时不涉及数据的内外存交换,则称之为______.~0088内排序`008910B1在排序过程中,若整个文件不完全在内存中处理,排序时涉及数据的内,外存交换,则称之为_______~0089外排序`009010B1直接插入排序的时间复杂度是_______.~00900(n2)`009108B1快速排序的平均时间复杂度是________.~00910(nlog2n)`009208E2对于给定的一组关键字:38,64,52,13,47,85写出快速排序的各趟运行结果~0092初始关键字:[38,64,52,13,47,85]第一趟[13]38[64,52,47,85]二1338[5247]64[85]三1338[47]526485最后结果133847526485`009308B2所谓归并是指将若干个__________的子文件合并成一个有序的文件.~0093已排序`009408B2给定一组关键字91,28,72,63,15,101,79,46,81将其用二路归并排序的各趟结果.~0094初始关键字[91][28][72][63][15][101][79][46][81]第一趟[28,91][63,72][15,101][46,79][81]第二趟[28,63,72,91][15,46,79,101][81]第三趟[15,28,46,72,79,91,101][81]第四趟[15,28,46,63,72,81,91,101]`009508B2n个关键字序列k1,k2,......,kn称为堆,当且仅当该序列满足特性______和______(1<=i<=[n/2])~0095k<=k2ik<=k2i+1`009608B2________的基本方法是:每一趟从待排序的记录中选出关键字最小的记录,顺序放在以排好序的文件的最后直到全部记录排序完毕.~0096选择排序`009708B2堆排序是一树形选择排序,特点是在排序过程中,将r[1]到r[n]看成一棵________顺序存储结构.~0097完全二叉树`009808B2起泡排序最好情况下,时间复杂度为______,其坏时间复杂度为_______,平均时间复杂度为_______.~00980(n),0(n2),0(n2)`009908B2 评价排序算法好坏的标准主要两条:第一条是算法执行时所需的_____,第二条是执行算法所需要的附加________~0099时间,附加空间`010008B2交换排序的基本思想是:两两比较待排序记录的_______,发现两个记录的次序相反时即进行交换,直到没有_______的记录为止,其中________和_________都属于交换排序.~0100关键字,反序,起泡排序,快速排序.`010103B2顺序栈S,栈顶指针为top,则栈置空操作是____________.~0101s->top=-1`010203B2设有一栈,结点结构为datanext栈顶指针为h.则执行*s结点入栈操作是________和__________.~0102s->next=h->nexth=s`010309B1在对有二十个数据有序表作二分查找时有___________个结点的查找长度是4.~01034`010409C1用折半查找法的查找速度比用顺序查找法的查找速度_________.A必然慢B必然快C速度相等D快慢不定~0104D`010503D2假定有三个元素abc进栈,进栈次序为abc,则可能出栈序列为abc,acb,bac,bca,cba()~0105正确`010609F2从循环单链表中查找出最大值.~0106intsearchmax(linklistl){intmax;int*p;p=l;max=p->data;p=p->next;while(p->next<>nil){if(maxdata)max=p->data;p=p->next;}returnmax;}`010709F2从循环单链表中查找出最小值.~0107intsearchmin(linklistl){intmin;int*p;p=l;min=p->data;p=p->next; while(p->next<>nil){if(min>p->data)min=p->data;p=p->next;}returnmin;}`010803B2栈是一种特殊的_________,又称为_________.~0108线性表后进先出表`010903C1设输入序列为1,2,3,4,5借助一个栈不可能得到的输出序列是()A、1,2,3,4,5B、5,4,3,2,1C、4,3,1,2,5D、1,3,2,5,4~0109C`011009C1适合折半查找的表的存贮方式及元素排列要求为()A、链式存贮元素无序B、链式存贮元素有序C、顺序存贮元素无序D、顺序存贮元素有序~0110D`011103D1顺序队列和循环队列的队满及队空判断条件是一样的()~0111错误`011203D1栈和队列都是线性表.()~0112正确`011303D1排序和查找是两种基本的数据结构.()~0113错误`011409D1队列只能采用链式存储结构.()~0114错误`011503B1队列是一种特殊的________,允许插入的一端称为_______,允许删除的一端称为______,所以队列又称为____________.~0115线性表队尾队头先进先出表`011603B1栈的两个重要应用是___________和_________.~0116在编译系统运行计算机语言程序的过程中,利用栈进行语法检查,实现递归调用.`011703A2栈和队列都是运算受到限制的特殊的线性表,栈和队列有何不同?~0117栈是仅允许在一端进行插入和删除的线性表,又称为后进先出表,队列是允许在一端插入,在另一端删除的线性表,允许插入的一端的称为队尾,允许删除的一端称为队头,又称为先进先出表.`011809F2写出在有序表A上进行递归形式的折半查找的算法,其中给定值K为待查的关键字,若查找成功则返回该元素的下标,否则返回零值.~0118 intbinasearch(Sqlists;keytypek;intlow;inthigh;){intmid;while(low<=high){mid=(low+high)/2;if(k==s.elem[mid].key)returnmid;if(khigh)return-1;}`011903C1用数组A存放循环队列的元素值,若其头指针为front,尾指针为rear,则循环队列中当前元素个数为().A、(rear-front+m)modmB、(rear-front+1)modmC、(rear-front-1+m)modmD、(rear-front)modm~0119A`012003A2设循环队列Q头指针为front,尾指针为rear,队列的最大容量为M,写出循环队列队满和队空的判定条件.~0120队满条件:(q.front+1)modm=q.rear队空条件:q.front=q.rear`012109F2对一个链式存贮结构的线性表进行顺序查找算法.~0121structnode{intdata;structnode*next;};typedefsealink(node*head,x){node*p;p=head->next;while(p!=NULL&&p->data!=x)p=p->next;rerurn(p);}`012203F2给出循环队列的入队和出队算法.~0122intENQUEUE(sequeue*sq;datatypex){if(sq->front==(sq->rear+1)%maxsize){printf("queueisfull");returnNULL;}else{sq->rear=(sq->rear+1)%maxsize;sq->data[sq->rear]=x;return(TRUE);}} datatypeDEQUEUE(sequeue*sq){if(EMPTY(sq)){printf("queueisempty");}else{sq->front=(sq->front+1)%maxsize;return(sq->data[sq->front];}}`012309C1顺序查找法适用于存储结构为()的线性表.A、散列存储B、压缩存储C、顺序或链式存储D、索引存储~0123C`012403B2由于查找运算的主要操作是关键字的比较,所以,通常把查找过程中对关键字需要执行的_________作为衡量一个查找算法效率优劣的标准.~0124平均比较次数(或平均查找长度)`012503F2设计算法判断一个算术表达式的圆括号是否正确配对,(提示:对表达式进行扫描,凡遇"("就进栈,遇")"就退掉栈顶的")",表达式被扫描完毕,栈就为空.)~0125booleanpair(b){stacks;s.top=0;i=1;ch=b[i];while(ch!="@"){if((ch="(")||(ch=")"))switch{"(":push(s,ch);break;")":ifempty(s){pair=false;return;}elsepop(s)}i=i+1;ch=b[i];}ifempty(s)pair=true;elsepair=false;}`012609F2编写顺序查找算法,并求在等概率情况下的平均查找长度ASL.~0126typedefstruct{deytypekey;datatypeother;}table; tabler[n+1];intSEQSEARCH(R,K)tableR[];keytypeK;{inti;R[n].key=K;i=0;while(R[i].key!=K)i++;if(i==n)return(-1);elsereturni;}在等概率情况下的平均查找长度是ASL=(n+1)/2`012703B2程序段的输出结果是_________（队列中的元素类型QElemType为char）。voidmain(){QueueQ;InitQueue(Q);Charx=’e’;y=’c’;EnQueue(Q,’h’);EnQueue(Q,’r’);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,’a’);while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);};Printf(x);}~0127stack`012809E2在地址空间为0-16的散列区中,对以下关键字序列构造两个哈希表:(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)(1)用线性探测开放定址法处理冲突(2)用链地址法处理并分别求这两个哈希表要在等概率情况下查找成功和不成功时的平均查找长度.设哈希函数为H(x)=i/2,其中i为关键字中第一个字母在字母表中的序号.~0128用线性探测开放定址法处理冲突:h(Jan)=8/2=4h(Feb)=6/2=3h(Mar)=13/2=6h(Apr)=1/2=0h(May)=13/2=6h(June)=8/2=4h(July)=8/2=4h(Aug)=1/2=0h(Sep)=19/2=9h(Nov)=20/2=10h(Dec)=4/2=2May:(6+1)/2=3(6+2)/2=4(6+3)/2=4(6+4)/2=5June:(4+1)/2=2July:(4+1)/2=2(4+2)/2=3(4+3)/2=3 (4+4)/2=4(4+5)/2=4(4+6)/2=5(4+7)/2=5(4+8)/2=6(4+9)/2=6(4+10)/2=7Aug:(0+1)/2=0(0+2)/2=1Dec:(2+1)/2=1(2+2)/2=2(2+3)/2=2(2+4)/2=3(2+5)/2=3(2+6)/2=4(2+7)/2=4(2+8)/2=5(2+9)/2=5(2+10)/2=6(2+14)/2=8链地址法0Apr->Aug12Dec345Jan->June->July6Feb->Mar->May7Oct->Nov89Sep10111213`012909E2什么是二叉排序树,按如下关键字的插入次序生成一棵二叉排序树,试画出此二叉排序树25,48,36,16,45,20,18,72~0129二叉排序树或者是一棵空树,或者是具有如下性质的二叉树:(1)若它的左子树不空,则左子树上所有结点的值均小于根结点的值;(2)若它的右子树不空,则右子树上所有结点的值均大于根结点的值;(3)左右子树又各是一棵二义排序树.2516482036721845`013009F2编写从二叉排序树上插入一个关键字的算法.~0130bstnode*INSERT(t,s)bstnode*s,*t;{bstnode*f,*p;p=t;while(p!=NULL) {f=p;if(s->key==p->key)returnt;if(s->keykey)p=p->lchild;elsep=p->rchild;}if(t==NULL)returns;if(s->keykey)f->lchild=s;elsef->rchild=s;returnt;}`013109F2二叉排序树的生成,是从空的二叉排树开始,每输入一个结点数据,就建立一个新结点插入到当前已生成的二叉排树中,编写生成二叉排序树算法.~0131bstnode*CREATBST(){bstnode*t,*s;keytypekey,endflag=0;datatypedata;t=NULL;scanf("%d",&key);while(key!=endflag){s=malloc(sizeof(bstnode));s->lchild=s->rchild=NULL;s->key=key;scanf("%d",&data);s->other=data;t=INSERTBST(t,s);scanf("%d",&key);}returnt;}`013209F2编写在树根指针为BT的二叉排序树上进行查找的算法.要求,若查找成功,则将变参T置0,否则返回零值.~0132bstnode*SEARCHBST(t,k)bstnode*t;keytypek;{while(t!=NULL){if(t->key==k)returnt;if(t->key>k)t=t->lchild;elset=t->rchild;}returnNULL;}`013309E2散列的基本思想是什么?举出五种常用的散列函数的构造方法.~0133散列的基本思想是:以结点的关键字K为自变量,通过一个确定的函数关系f,计算出对应的函数值f(K),把这个值解释为结点的存储地址,然后到相应的单元里去取要找的结点.散无函数的构造方法:1.数字选择法2.平方到中法3.折叠法4.除余法5基数转换法6随机数法`013409E2 什么是冲突?处理冲突的方法是什么?~0134若某个散列函数H对于不相等的关键字key1和key2得到相同的散列地址(即H(key1)=H(key2))则将该现象称为冲突.解决冲突的方法有:开放定址法和链地址法`013503E1设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有①front=11，rear=19;②front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？~0135用队列长度计算公式：(N＋r－f)%N①L=（40＋19－11）%40=8②L=（40＋11－19）%40=32`013609F3试编写利用折半查找确定所在块的分块查找算法,并讨论在块中进行顺序查找时使用"监视哨"有优缺点,以及必要时如何在分块查找的算法中实现设置"监视哨"的技巧.~0136typedefstruct{keytypekey;intaddr;}IDtable;IDtableID[b];intBLKSEARCH(R,ID,K)tableR[];IDtableID[];keytypeK;{inti,low1,low2,mid,high1,high2;low1=0;high1=b-1;while(low1<=high1){mid=(low1+high1)/2;if(K<=ID[mid].key)high1=mid-1;elselow1=mid+1;}if(low10,n=0时akm(m-1,akm(m,n-1))当m<>0,n<>0时(1)写出递归算法(2)写出非递归算法~0139递归算法:intakm(intm,intn){if(m==0)akm=n+1;elseif(n==0)akm=akm(m-1,1);else{g=akm(m,n_1);akm=akm(m-1,g);}}非递归算法:intakm(intm,intn){top=0;s[top].mval=m;s[top].nval=n;do{while(s[top].mvalwhile(s[top].nval){top++; s[top].mval=s[top-1].mval;s[top].nval=s[top-1].nval-1;}s[top].mval--;s[top].nval=1;}if(top>0){top--;s[top].mval--;s[top].nval=s[top+1].nval+1;}while(top!=0||s[top].mval!=0);akm1=s[top].nval+1;top--;}`014003F1设HS为一个链栈的栈顶指针,试写出退栈的算法,(回收被删除的结点)~0140linkstack*POPSTACK(top,datap)linkstack*top;datatype*datap;{linkstack*pif(top==NULL){printf("underflow");returnNULL)}else{*data=top->data;p=top;top=top->next;free(p);returntop;}}`014103B1中缀算术表达式3*(5+x)/y所对应的后缀算术表达式为________________.~014135x+*/`014209B1在如下一维数组A中折半查找36和85时,所需比较的次数分别为__________和__________.25,36,40,45,48,56,60,68,72,85~014224`014303E3设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序.~0143至少有14种。①全进之后再出情况，只有1种：4，3，2，1②进3个之后再出的情况，有3种，3,4,2,13,2,4,13,2,1,4③进2个之后再出的情况，有5种，2,4,3,12,3,4,12,1,3,42,1,4,32,1,3,4④进1个之后再出的情况，有5种，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,3`014409B1折半查找的时间复杂性是__________.~0144Olog2(n)`014510B1要查的索引文件时,首先要查找_________,然后要查找__________. ~0145索引表主文件`014609F2写出在有序表A上进行非递归形式的折半查找的算法,其中给定值K为待查元素的关键字,若查找成功则返回该元素的下标,否则返回零值.~0146intbinsearch(Sqlists;intlow;inthigh;keytypeK){flag=0;while(lowK:high=mid-1;break;cases.elem[mid].key=K:flag=1;break;default:;}}}`014703E2写出栈的顺序存储结构(即顺序栈)的类型定义.~0147顺序栈的结构:typedefintdatatype;#definemaxsize64typedefstruct{datatypedata[maxsize];inttop}seqstack;seqstack*s;`014803A1写出队列的顺序存储结构(顺序队列)的类型定义.~0148顺序队列的结构:typedefstruct{datatypedata[maxsize]intfrontrear;}sequeue;sequeue*sq;`014903F3假设表达式由单字母变量和双目运算符构成.试写一个算法,将一个通常书写正确的表达式转换为逆波兰式.~0149change(E,A){setnull(S2);push(S2,"@");i=1;j=1;ch=E[i];whilech<>"@"{if(chinop1) {while(chinop1){S[j]=ch;j=j+1;i=i+1;chE[i]}A[j]="";j=j+1;}if(chinop2){w=readop(S2);while(precede(w,ch)=">"A[j]=w;j=j+1;pop(S2);w=readtop(S2);}ifprecede(w,ch)="<"push(S2,ch)elsepop(S2);}w=pop(S2);whilew<>"@"{A[j]=w;j=j+1;w=pop(S2)}A[j]="@";}`015003B2带有头结点的链队列q,队头指针front,队尾指针rear,则置空队的算法描述为:q->front=malloc(sizeof(linklist));________________;________________;~0150q->front->next=NULLq->rear=q->front;`015106B2深度为６的完全二叉树至多有___个结点,至有___个结点。~015163;32`015206B1二叉树的子树有___之分，次序___任意颠倒。~0152左右，不能`015306C2已知完全二叉树有２８个结点，则整个二叉树有()个度为１的结点。A、0;B、1;C、2;D、不确定~0153B`015406D2树的度是指树内结点的度。()~0154错`015506D1满二叉树是完全二叉树的特例.()~0155对`015604A2已知S="(syz)"*"T="(s+z)*y"试利用联接(strcat(s1,s2),求子串(substr(s,i,j)和置换replace(s1,i,j.s2)等基本运算将S转换为T.~0156S1=SUBSTR(S,3,1)S=REPLACE(S,3,1,"+")T=STRCAT(S,S1)`015706D1 二叉树是树。()~0157对`015806E1已知一棵二叉树如图,试分别写出按中序、先序、后序遍历得到的结点序列。~0158中序：16,24,35,42,53,57,60,84,88,92先序：60,35,24,16,53,42,57,92,84,88后序：16,24,42,57,53,35,88,84,92,60`015903B2带表头结点的空循环双向链表的长度等于。~01590`016006F2以二叉链表作存储结构,试编写二叉树的高度算法.~0160求二叉树高度算法intHIGH(bintree)bintree*tree;{intm=0;k=0;l=0if(tree==NULL)m=0elsem=1if(tree->lchild!=NULL)k=HIGH(tree->lchild);if(tree->rchild!=NULL)l=HIGH(tree->rchild);if(k>l)m=k+1;elsem=l+1return(m);}`016106B2二叉树是空的,或者由一个根结点和两棵______分别称为左子树和右子树的_____组成。~0161互不相交的；二叉树`016206D1不存在有偶数个结点的满二叉树。()~0162对`016304D2空白串即为空串。()~0163错`016406D1深度为K的二树至多有2k-1-1结点。()~0164错`016506E3已知一棵二叉树中序和后序序列为分别为:BDCEAFHG和DECBHGFA画出这棵二叉树~0165 `016606F2已知一棵以链表结构存贮的二叉树,如欲从根结点起,由上而下,逐层打印各结点的数据,同一层的结点自左而右打印,试写其算法(队列的出队和入队算法已知)~0166bintree*t,*rootsequeue*sqt=rootprintf(t->data);while(t->lchild!=NULL||t->rchild!=NULL)if(t->lchild!=NULL)printf(t->lchild);ENQUENE(sq,t->lchild);if(t->rchild!=NULL){printf(t->rchild);ENQUENE(t->rchild);}t=DEQUEUE(sq);}`016706E1已知一棵树如图,请回答下列问题:(1)树的度为多少?结点G的度为多少?(2)树的深度为多少?哪些是叶子结点?(3)结点G的祖先有哪些?(4)结点B的兄弟有哪些?孩子有哪些?~0167１、3;2２、4;３、E,F,I,J,N４、A,C５、C,D;E,F`016806D1哈夫曼树的带权路径长度WPL等于叶子结点的权值之和。()~0168对`016906E3已知二叉树的先序、中序、后序序列分别如下,但其中有一些已模糊不清,构造出该二叉树.先序:_23_5_78中序:3_41_789后序:_42__651 ~0169`017003D1栈和链表是两种不同的数据结构。（）~0170X`017106D3由二叉树的先序序列和中序序列能唯一确定一棵二叉树。()~0171对`017206B3在有N(N>0)个结点的二叉链表中，空链域的个数是：_____。~0172N+1`017306D2树是一种特殊形式的图。()~0173对`017406E2满足下列性质之一的二叉树是否存在？若有举例，若无说明原因：１先序遍历和中序遍历结果相同。２先序遍历和后序遍历结果相同。３中序遍历和后序遍历结果相同。~01741.有2.无3.有`017506D2不存在有偶数个结点的完全二叉树。()~0175错`017606E1 根据二叉树的定义，二叉树有几种基本形式。图示之。~0176有五种。`017706E2画出图Ａ中森林转化为二叉树及图Ｂ中由二叉树转为对应的森林。~0177`017806F1以二叉链表作存贮结构，试写出中序遍历二叉树的算法。 ~0178INORDER()bitree*t;{if(t){INORDER(t->lchild);printf("|t%c|n",t->data);INORDER(t->rchild);}}`017906F3设二叉树以二叉链表存贮,root指向根结点写出中序遍二叉树的非递归算法。~0179MIDBINTREE(p)bintree*root,*pseqstack*swhile(p->lchild!=NULL){printf(p->data)if(p-rchild!=NULL)PUSH(s,p);p=p->lchild;}printf(p->data);while(EMPTY(s)!=NULL)p=pop(s);{while(p->lchild!=NULL){print(p->data);if(p-rchild!=NULL)PUSH(s,p);p=p->lchild;}printf(p->data);}}`018006F2递归算法，将二叉树所有结点的左、右子树交换。~0180*tEXBINTREE(bintree)bintree*t,*root,*s{t=root;s=t->rchild;t->rchild=t->lchild;t->lchild=s;EXBINTREE(t->lchild);EXBINTREE(t->rchild);}`018106B2具有N个结点的完全二叉树的深度为_________。~0181└log2n+1┘+1或┌log2(n+1)┐`018206D1二叉树的结点必须有两棵子树。()~0182错`018304D1由空格组成的串称空串。()~0183错`018406A2何谓哈夫曼树?何谓完全二叉树,它具有哪些特点?~0184哈夫曼树：带权路径WPL最小的二叉树称最优二叉树或哈夫曼树。 完全二叉树：若一棵二叉树至多只有最下面的两层上结点的度数可以小于２，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树为完全二叉树。特点：１只有最下面两层有叶子。２如果一个结点无左子树，那它一定是叶子。３完全二叉树中任一个结点的左子树深度为Ｔ，其右子树深度为Ｔ或Ｔ－１。`018506C1深度为K的二叉树,所含叶子的个数最多为_____.A、2kB、K;C、2k-1D、2k-1~0185D`018606D2存在着这样的二叉树,对它采用任何次序遍历,其结点访问序列均相同。()~0186对`018706D3树和二叉树都是森林。()~0187对`018806B1在一棵非空的树中,有且仅有一个结点没有______,这个结点称为______.~0188前趋（双亲）；根`018903D1一个栈的输入序列是12345，则栈的输出序列不可能是12345。（）~0189X`019006E3已知二叉树的中序和先序序列分别为:中序序列:DEBAFCHG先序序列:ABDECFGH试构造该二叉树~0190`019106A3度为２的树与二叉树的区别。~0191度为２的树每个结点如度为１子树无左右之分；而二叉树则有。`019206F2试编写算法判断两棵二叉树是否等价,称二叉树T1和T2的根结点的值相同,并且T1的左子树与T2的左子树是等价的，T1的右子树和T2的右子树是等价的.~0192EQUBINTREE(t1,t2)bintree*t1,*t2;{if(t1=NULL&&t1=NULL)returnTRUEelse{if(t1->data=t2->data&&ERUBINTREE(t1->lchild,t2->lchild)&&ERUBINTREE(t1->rchild,t2->rchild))returnTRUE;} elsereturnFALSE;}`019304C1两个串相等的条件为()A、长度相等B、对应位置上的字符相同.C、A和BD、A或B~0193C`019406B1结点拥有______称为结点的度。~0194子树个数`019504C1当串的长度超过上界MAX时,将采用()进行处理.A、截尾法B、四舍五入C、进位法D、溢出错误~0195A`019606D2将二叉树变为线索二叉树的过程称为线索化。()~0196对`019706B1具有30个结点的完全二叉树深度为______.~01974`019806E2已知一棵度为m的树中有N1个度为1的结点,N2个度为2的结点,问该树中有多少片叶子.~0198N0=1+(i-1)Ni(i=1tom)`019906A2分别画出具有3个结点的树和3个结点二叉树的所有不同形态.~0199三个结点的树有：三个结点的二叉树有：`020006E3一个深度为L的满K叉树有如下性质:第L层上的结点是叶子结点,其余各层上每个结点都有K棵非空子树,如果按层次顺序从1开始对全部结点编号,问:(1)各层的结点的数目是多少?(2)编号为n的结点的双亲结点(若存在)编号是多少?(3)编号为n的结点的第i个孩子(若存在)编号是多少?(4)编号为n的结点有右兄弟的条件是什么?其右兄弟的编号是多少?~02001.K^(I-1)(1<=I<=k)2.(n+k-2)/k 3.kÚn+I-k+14.nÚki+1(I=0,1,……);n+1`020105B1设有二维数组A(m*n),其中每个元素占w个存储单元,第一个元素a[1][1]的起始地址为L,则以列主序方式存储a[i][j]的存储单元地址是__________.~0201L+[(j-1)*m+i-1]*w`020205A2C语言是按行主序方式顺序存储数组,设有定义inta[3][2][2][3];要求列出其所有数组元素在内存中的存储次序.~0202a[0][0][0][0],a[0][0][0][1],a[0][0][0][2]a[0][0][1][0],a[0][0][1][1],a[0][0][1][2]a[0][1][0][0],a[0][1][0][1],a[0][1][0][2]a[0][1][1][0],a[0][1][1][1],a[0][1][1][2]a[1][0][0][0],a[1][0][0][1],a[1][0][0][2]a[1][0][1][0],a[1][0][1][1],a[1][0][1][2]a[1][1][0][0],a[1][1][0][1],a[1][1][0][2]a[1][1][1][0],a[1][1][1][1].a[1][1][1][2]a[2][0][0][0],a[2][0][0][1].a[2][0][0][2]a[2][0][1][0],a[2][0][1][1],a[2][0][1][2]a[2][1][0][0],a[2][1][0][1],a[2][1][0][2]a[2][1][1][0],a[2][1][1][1],a[2][1][1][2].`020305F3试编写算法,将数组intA[n]中的所有奇数移到所有偶数之前.要求时间复杂度为O(n).~0203move(a,n)inta[];intn;{intlow,high,temp;low=0;high=n-1;temp=a[high];while(low│3│─┼──>│4│nil││││└─┴─┘└─┴──┘├─┼──┤┌─┬──┐┌─┬──┐│2│─┼─>│1│──┼>│3│nil││││└─┴──┘└─┴──┘├─┼──┤┌─┬──┐│3│─┼─>│2│nil││││└─┴──┘├─┼──┤┌─┬───┐┌─┬───┐│4│─┼>│1│──┼──>│2│nil││││└─┴───┘└─┴───┘└─┴──┘~0222顶点1的入度为2,出度为2顶点2的入度为2,出度为2顶点3的入度为2,出度为1顶点4的入度为1,出度为2`022303D1栈和队列的存储方式既可是顺序方式，也可是链接方式.()~0223对`022405B1数组通常只有两种运算_________和_______~0224值检索、值存储`022505A3什么是稀疏矩阵?~0225非零元比较少,且非零元分布没有一定规律的矩阵.`022607B1图的常用存储结构有________和________.~0226邻接矩阵、邻接表`022705B1三维数组a[5][7][9]共含有_______个元素.~0227315`022807B1图的遍历方法一般有________和_________两种.~0228深度(纵向)优先搜索、广度(横向)优先搜索`022905D1数组通常采用链式存储结构()~0229错误`023003D1对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（）~0230对`023105B2设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为。~02318950`023207A1何为子图? ~0232设G(V,E)是一个图,若V"是V的子集,E"是E的子集,则G"=(V",E")为G的子图.`023307A2何为连通图?~0233在无向图G中,若任意两个不同的顶点都是连通的,则称G为连通图`023404B2若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为。~0234(n-m+1)*m`023507D1树是一种特殊形式的图()~0235正确`023607C1从邻接矩阵│010│可以看出,该图共有__(1)__个顶点,│101││010│如果是有向图,该图共有__(2)__条弧;如果是无向图则共有__(3)__条边.(1)A9B3C6D1(2)A5B4C3D2(3)A5B4C3D2~0236(1)B(2)B(3)D`023707B2有向图中,所有的顶点的入度之和与出度之和的关系_________~0237相等`023807B1无向图G是连通的无回路图,有且仅有_______条边.~0238n-1`023907A2何为网络?~0239若将图的每条边都赋上一个权,则称这种带权图为网络`024005B2求三维数组A（m*n*p）按行优先顺序存储的地址计算公式___________.~0240Loc(a[i][j][k])=Loc(a[1][1][1])+[(i-1)*n*p+(j-1)*p+(k-1)]*d其中:d为每个元素占的存储单元数.`024105B2求下列广义表运算的结果(1)head((x,y,z))=______________(2)tail((a,b),(x,y))=_______________.~0241(1)x,(2)(x,y)`024205B3求下列广义表运算的结果(1)head(tail((x,y),(a,b)))=________________(2)tail(head((a,b,c),(x,y),(e,f)))=______________~0242(1)a(2)(b,c)`024304B2 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第次匹配成功。~02436`024407E1已知如下图所示的有向图,请给出该图的(1)每个顶点的入度/出度(2)邻接表~0244(1)顶点│123456────┼─────────────────入度│321122────┼──────────────────出度│022313────┴──────────────────(2)邻接表┌─┬─┐│1│∧│├─┼─┤┬─┬─┐┌─┬──┐│2│─┼──>│4│─┼─>│1│∧││││└─┴─┘└─┴──┘├─┼─┤┌─┬─┐┬─┬─┐│3│─┼──>│6│─┼─>│2│∧││││└─┴─┘└─┴─┘├─┼─┤┌─┬──┐┌─┬──┐┌─┬─┐│4│─┼──>│6│─┼─>│5│─┼─>│3│∧││││└─┴──┘└─┴──┘└─┴─┘├─┼─┤┬─┬──┐│5│─┼──>│1│∧││││└─┴──┘├─┼─┤┌─┬──┐┌─┬──┐┌─┬──┐│6│─┼──>│5│─┼>│2│─┼──>│1│∧││││└─┴──┘└─┴──┘└─┴──┘└─┴─┘`024504B1子串的定位运算称为串的模式匹配；称为目标串，称为模式。~0245被匹配的主串、子串`024607E3试利用dijkstra算法求右图中从顶点a到其它各顶点间的最短路径长度,写出执行算法过程中各步的状态.~0246邻接矩阵│015212∞∞∞│a│∞0∞∞6∞∞│b│∞∞0∞84∞│c│∞∞∞0∞∞3│dcost=│∞∞∞∞0∞9│e│∞∞∞5∞010│f│∞4∞∞∞∞0│gdist[]a│b│c│d│e│f│g│选项点│S集─┼┴──┼──┼──┼──┼──┼──┼───┼────初始化0│15│2│12│∞│∞│∞│c│{a,c}││││10│6│∞│f│{a,c,f}│││11│││16│e│{a,c,f,e} ││││││14│d│{a,c,f,e,d}│││││││g│{a,c,f,e,d,g}│││││││b│Ｖ││││││││`024703A2顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？~0247答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。采用循环队列是解决假溢出的途径。另外，解决队满队空的办法有三：①设置一个布尔变量以区别队满还是队空；②浪费一个元素的空间，用于区别队满还是队空。③使用一个计数器记录队列中元素个数（即队列长度）。我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。判断循环队列队空标志是：f=rear队满标志是：f=(r+1)%N`024807F2试给出以邻接矩阵表示无向图的深度优先搜索算法~0248intvisited[n]graphg;DFS(i)inti;{intj;printf("node:%cn",g.vexs[i]);visited[i]=TRUE;for(j=0;jadjvex]){printf("%cn",gl[p->adjvex].vertex)visited[p->adjvex]=TRUE;ENQUEUE(Q,p->adjvex);}}}`025007C1 设有无向图G,从顶点V1出发,对它进行深度优先遍历得到的顶点序列是____(1)___;而进行广度优先遍历得到的顶点序列是___(2)___.(1)AV1V3V5V4V2V6V7BV1V5V3V4V2V7V6CV1V2V4V7V6V5V3DV1V4V7V2V6V5V3(2)AV1V5V3V4V2V6V7BV1V7V2V6V4V5V3CV1V3V5V4V2V7V6DV1V2V4V7V6V5V3~0250(1)B(2)C`025106D1若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。()~0251√`025206D1二叉树中每个结点的两棵子树的高度差等于1。()~0252×`025306D2二叉树中每个结点的两棵子树是有序的。()~0253√`025406D1二叉树中每个结点有两棵非空子树或有两棵空子树。()~0254×`025506D2二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。()~0255×`025606D2二叉树中所有结点个数是2k-1-1，其中k是树的深度。()~0256×`025706D2二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。()~0257×`025806D1对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。()~0258×`025906D2用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。()~0259√`026006D1具有12个结点的完全二叉树有5个度为2的结点。()~0260√`026106B1由３个结点所构成的二叉树有种形态。 ~02615`026206B1一棵深度为6的满二叉树有个分支结点和个叶子。注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。~0262n1+n2=0+n2=n0-1=3126-1=32`026306B1棵具有２５７个结点的完全二叉树，它的深度为~02639（注：用ëlog2(n)û+1=ë8.xxû+1=9`026406B1设一棵完全二叉树有700个结点，则共有个叶子结点。~0264350`026506B1设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。~0265500、499、1、0`026606B2一棵含有n个结点的k叉树，可能达到的最大深度为，最小深度为。~0266n、2`026706B1二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按NLR次序），后序法（即按次序）和中序法（也称对称序法，即按LNR次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是。~0267LRN、FEGHDCB`026806B2中序遍历的递归算法平均空间复杂度为。~0268O(n)`026906B3用5个权值{3,2,4,5,1}构造的哈夫曼（Huffman）树的带权路径长度是。~026933`027006C1不含任何结点的空树()Ａ、是一棵树;Ｂ、是一棵二叉树;Ｃ、是一棵树也是一棵二叉树;Ｄ、既不是树也不是二叉树~0270C`027106C1二叉树是非线性数据结构，所以（）。Ａ、它不能用顺序存储结构存储;Ｂ、它不能用链式存储结构存储;Ｃ、顺序存储结构和链式存储结构都能存储;Ｄ、顺序存储结构和链式存储结构都不能使用~0271C`027206C1具有n(n>0)个结点的完全二叉树的深度为（）。Ａ、élog2(n)ùＢ、ëlog2(n)ûＣ、ëlog2(n)û+1Ｄ、élog2(n)+1ù~0272C `027306C1把一棵树转换为二叉树后，这棵二叉树的形态是（）。Ａ、唯一的Ｂ、有多种Ｃ、有多种，但根结点都没有左孩子Ｄ、有多种，但根结点都没有右孩子~0273A`027406C2树是结点的有限集合，它（）根结点，记为T。其余的结点分成为m（m≥0）个（）的集合T1，T2，…，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子结点个数为该结点的（）。供选择的答案A：①有0个或1个②有0个或多个③有且只有1个④有1个或1个以上B:①互不相交②允许相交③允许叶结点相交④允许树枝结点相交C：①权②维数③次数（或度）④序~0274ABC＝1，1，3`027506C2二叉树（）。在完全的二叉树中，若一个结点没有（），则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的（），而N的右子女是它在原树里对应结点的（）。供选择的答案A：①是特殊的树②不是树的特殊形式③是两棵树的总称④有是只有二个根结点的树形结构B:①左子结点②右子结点③左子结点或者没有右子结点④兄弟C～D：①最左子结点②最右子结点③最邻近的右兄弟④最邻近的左兄弟⑤最左的兄弟⑥最右的兄弟~0275ABCDE＝2，1，1，3`027606E1一棵度为2的树与一棵二叉树有何区别？~0276度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。`027706E3设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为：（lchild,data,rchild）。其中lchild，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题：1.对下列二叉树B，执行下列算法traversal(root)，试指出其输出结果；2.假定二叉树B共有n个结点，试分析算法traversal(root)的时间复杂度。ABDCFGE二叉树BC的结点类型定义如下：structnode{chardata;structnode*lchild,rchild;};C算法如下：voidtraversal(structnode*root){if(root){printf(“%c”,root->data);traversal(root->lchild); printf(“%c”,root->data);traversal(root->rchild);}}~0277这是“先根再左再根再右”，比前序遍历多打印各结点一次，输出结果为：ABCCEEBADFFDGG特点：①每个结点肯定都会被打印两次；②但出现的顺序不同，其规律是：凡是有左子树的结点，必间隔左子树的全部结点后再重复出现；如A，B，D等结点。反之马上就会重复出现。如C，E，F，G等结点。时间复杂度以访问结点的次数为主，精确值为2*n，时间渐近度为O(n).`027806E1给定二叉树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I；中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。~0278解：方法是：由前序先确定root，由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。DACFEGBHI`027906E3给定如图所示二叉树T，请画出与其对应的中序线索二叉树。2825334060085455~0279解：要遵循中序遍历的轨迹来画出每个前驱和后继。282540555560330854中序遍历序列：5540256028083354NILNIL2825334060085455`028006E1试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。~0280 答：DLR：ABDFJGKCEHILMLDR:BFJDGKACHELIMLRD：JFKGDBHLMIECA`028106E2把如图所示的树转化成二叉树。~0281注意全部兄弟之间都要连线（包括度为2的兄弟）,并注意原有连线结点一律归入左子树，新添连线结点一律归入右子树。ABECKFHDLGIMJ`028206E2画出和下列二叉树相应的森林。~0282注意根右边的子树肯定是森林，而孩子结点的右子树均为兄弟。`028306F2编写递归算法，计算二叉树中叶子结点的数目。~0283 思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。法一：核心部分为：DLR(liuyu*root)/*中序遍历递归函数*/{if(root!=NULL){if((root->lchild==NULL)&&(root->rchild==NULL)){sum++;printf("%dn",root->data);}DLR(root->lchild);DLR(root->rchild);}return(0);}法二：intLeafCount_BiTree(BitreeT)//求二叉树中叶子结点的数目{if(!T)return0;//空树没有叶子elseif(!T->lchild&&!T->rchild)return1;//叶子结点elsereturnLeaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数}//LeafCount_BiTree`028406F3写出求二叉树深度的算法，先定义二叉树的抽象数据类型。~0284设计思路：只查后继链表指针，若左或右孩子的左或右指针非空，则层次数加1；否则函数返回。但注意，递归时应当从叶子开始向上计数，否则不易确定层数。intdepth(liuyu*root)/*统计层数*/{intd,p;/*注意每一层的局部变量d,p都是各自独立的*/p=0;if(root==NULL)return(p);/*找到叶子之后才开始统计*/else{d=depth(root->lchild);if(d>p)p=d;/*向上回朔时，要挑出左右子树中的相对大的那个深度值*/d=depth(root->rchild);if(d>p)p=d;}p=p+1;return(p);}法二：intGet_Sub_Depth(BitreeT,intx)//求二叉树中以值为x的结点为根的子树深度{if(T->data==x){printf("%dn",Get_Depth(T));//找到了值为x的结点,求其深度exit1;}}else{if(T->lchild)Get_Sub_Depth(T->lchild,x);if(T->rchild)Get_Sub_Depth(T->rchild,x);//在左右子树中继续寻找}}//Get_Sub_DepthintGet_Depth(BitreeT)//求子树深度的递归算法{if(!T)return0;else{ m=Get_Depth(T->lchild);n=Get_Depth(T->rchild);return(m>n?m:n)+1;}}//Get_Depth`028506F2编写按层次顺序（同一层自左至右）遍历二叉树的算法。(或：按层次输出二叉树中所有结点；)~0285思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。这是一个循环算法，用while语句不断循环，直到队空之后自然退出该函数。技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，……以此产生了按层次输出的效果。level(liuyu*T)/*liuyu*T,*p,*q[100];假设max已知*/{intf,r;f=0;r=0;/*置空队*/r=(r+1)%max;q[r]=T;/*根结点进队*/while(f!=r)/*队列不空*/{f=(f+1%max);p=q[f];/*出队*/printf("%d",p->data);/*打印根结点*/if(p->lchild){r=(r+1)%max;q[r]=p->lchild;}/*若左子树不空，则左子树进队*/if(p->rchild){r=(r+1)%max;q[r]=p->rchild;}/*若右子树不空，则右子树进队*/}return(0);}法二：voidLayerOrder(BitreeT)//层序遍历二叉树{InitQueue(Q);//建立工作队列EnQueue(Q,T);while(!QueueEmpty(Q)){DeQueue(Q,p);visit(p);if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);}}//LayerOrder`028603C1若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为()Ａ、iＢ、n=iＣ、n-i+1Ｄ、不确定~0286C`028706F1编写算法判别给定二叉树是否为完全二叉树。~0287intIsFull_Bitree(BitreeT)//判断二叉树是否完全二叉树,是则返回1,否则返回0{InitQueue(Q);flag=0;EnQueue(Q,T);//建立工作队列while(!QueueEmpty(Q)){ {DeQueue(Q,p);if(!p)flag=1;elseif(flag)return0;else{EnQueue(Q,p->lchild);EnQueue(Q,p->rchild);//不管孩子是否为空,都入队列}}//whilereturn1;}//IsFull_Bitree分析:该问题可以通过层序遍历的方法来解决.与6.47相比,作了一个修改,不管当前结点是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,则序列中会含有空指针.`028806F3假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用0～7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。~0288解：方案1；哈夫曼编码先将概率放大100倍，以方便构造哈夫曼树。w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6],(7,10)】,……19,21,3201010119213201010171060123（100）（40）（60）192132（28）（17）（11）7106（5）23方案比较：字母编号对应编码出现频率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10字母编号对应编码出现频率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10方案1的WPL＝2(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方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3结论：哈夫曼编码优于等长二进制编码`028903D1队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（）~0289X`029002B1线性表中结点的集合是的，结点间的关系是的。~0290有限、一对一 `029103C1判定一个队列QU（最多元素为m0）为满队列的条件是（）Ａ、QU->rear－QU->front==m0Ｂ、QU->rear－QU->front－1==m0Ｃ、QU->front==QU->rearＤ、QU->front==QU->rear+1~0291A`029203C2数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为A、r－f;B、（n＋f－r）%n;C、n＋r－f;D、（n＋r－f）%n~0292D`029303A1说明线性表、栈与队的异同点。~0293相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。②用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。`029403A2设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。~0294至少有14种。①全进之后再出情况，只有1种：4，3，2，1②进3个之后再出的情况，有3种，3,4,2,13,2,4,13,2,1,4③进2个之后再出的情况，有5种，2,4,3,12,3,4,12,1,3,42,1,4,32,1,3,4④进1个之后再出的情况，有5种，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,3`029504C1串是一种特殊的线性表，其特殊性体现在（）Ａ、可以顺序存储Ｂ、数据元素是一个字符Ｃ、可以链式存储Ｄ、数据元素可以是多个字符~0295B`029605C2假设有60行70列的二维数组a[1…60,1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为（）。（无第0行第0列元素）Ａ、16902Ｂ、16904Ｃ、14454Ｄ、答案A,B,C均不对~0296A`029704A1给出空串和空白串的概念。~0297不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。`029805B1三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标、和。~0298列下标元素值`029905B1求下列广义表操作的结果：GetHead【((a,b),(c,d))】===;GetHead【GetTail【((a,b),(c,d))】】===;~0299(a,b)(c,d)`030005B1 求下列广义表操作的结果：GetHead【GetTail【GetHead【((a,b),(c,d))】】】===;GetTail【GetHead【GetTail【((a,b),(c,d))】】】===;~0300b（d）`030108B1在数据的存放无规律而言的线性表中进行检索的最佳方法是。~0301顺序查找（线性查找）`030208B2线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索次。设有100个结点，用二分法查找时，最大比较次数是。~03028、7`030308B2假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。~03032、8、3.7`030408B2折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素比较大小。~030428，6，12，20`030508B2在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。~0305散列查找`030608B2散列法存储的基本思想是由决定数据的存储地址。~0306关键字的值`030708B3有一个表长为m的散列表，初始状态为空，现将n（nhigh)return0;//查找不到时返回0mid=(low+high)/2;if(ST.elem[mid].key==key)returnmid;elseif(ST.elem[mid].key>key)returnSearch_Bin_Recursive(ST,key,low,mid-1);elsereturnSearch_Bin_Recursive(ST,key,mid+1,high);}}//Search_Bin_Recursive`032808F3试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。~0328intlast=0,flag=1;//last是全局变量，用来记录前驱结点值，只要每个结点都比前驱大就行。intIs_BSTree(BitreeT)//判断二叉树T是否二叉排序树，是则返回1，否则返回0{if(T->lchild&&flag)Is_BSTree(T->lchild);if(T->datadata;if(T->rchild&&flag)Is_BSTree(T->rchild);returnflag;}//Is_BSTree`032908E2已知一个含有1000个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过3。~0329设计哈希表的步骤为：a)根据所选择的处理冲突的方法求出装载因子a的上界；b)由a值设计哈希表的长度m；c)根据关键字的特性和表长m选定合适的哈希函数。注：要求ASL≤3，则m必然要尽量长，以减少冲突；`033008F2已知某哈希表的装载因子小于1，哈希函数H(key) 为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。~0330voidPrintWord(HashTableht){//按第一个字母的顺序输出哈希表ht中的标识符。哈希函数为表示符的第一个字母在字母表中的序号，处理冲突的方法是线性探测开放定址法。for(i=1;i<=26;i++){j=i;While(ht.elem[j].key){if(Hash(ht.elem[j].key==i)printf(ht.elem[j].key);j=(j+1)%m;}}}//PrintWord`033109B1大多数排序算法都有两个基本的操作：和。~0331比较、移动`033209B1在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较次。~03326`033309B1在插入和选择排序中，若初始数据基本正序，则选用；若初始数据基本反序，则选用。~0333插入、选择`033409B2在堆排序和快速排序中，若初始记录接近正序或反序，则选用；若初始记录基本无序，则最好选用。~0334堆排序、快速排序`033509B2对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是。若对其进行快速排序，在最坏的情况下所需要的时间是。~0335O(n2)O(n2)`033609B2对于n个记录的集合进行归并排序，所需要的平均时间是，所需要的附加空间是。~0336O(nlog2n)、O(n)`033709B2对于n个记录的表进行2路归并排序，整个归并排序需进行趟（遍）。~0337┌log2n┐`033809B3设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是；初始步长为4的希尔（shell）排序一趟的结果是；二路归并排序一趟扫描的结果是；快速排序一趟扫描的结果是；堆排序初始建堆的结果是。~0338HCQPAMSRDFXYPACSQHFXRDMYHQCYAPMSDRFX FHCDPAMQRSYXADCRFQMSYPHX`033909B3在堆排序、快速排序和归并排序中，若只从排序结果的稳定性考虑，则应选取方法；若只从平均情况下最快考虑，则应选取方法；若只从最坏情况下最快并且要节省内存考虑，则应选取方法。~0339归并排序堆排序、快速排序和归并排序堆排序`034009C1将5个不同的数据进行排序，至多需要比较()次。Ａ、8Ｂ、9Ｃ、10Ｄ、25~0340C`034109C2排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）Ａ、希尔排序Ｂ、冒泡排序Ｃ、插入排序Ｄ、选择排序~0341C`034209C1从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为（）Ａ、希尔排序Ｂ、归并排序Ｃ、插入排序Ｄ、选择排序~0342D`034309C2对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多（）Ａ、从小到大排列好的Ｂ、从大到小排列好的Ｃ、元素无序Ｄ、元素基本有序~0343B`034409C1对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为（）Ａ、n+1Ｂ、nＣ、n-1Ｄ、n(n-1)/2~0344D`034509C2快速排序在下列哪种情况下最易发挥其长处（）Ａ、被排序的数据中含有多个相同排序码Ｂ、被排序的数据已基本有序Ｃ、被排序的数据完全无序Ｄ、被排序的数据中的最大值和最小值相差悬殊~0345C`034609C2对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是（）A、O(n)B、O(n2)C、O(nlog2n)D、O(n3)~0346B`034709C1若一组记录的排序码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）Ａ、38,40,46,56,79,84Ｂ、40,38,46,79,56,84Ｃ、40,38，46,56,79,84Ｄ、40,38,46,84,56,79~0347C`034809C2下列关键字序列中，（）是堆。 Ａ、16,72,31,23,94,53Ｂ、94,23,31,72,16,53Ｃ、16,53,23,94，31,72Ｄ、16,23,53,31,94,72~0348D`034909C1堆是一种（）排序。Ａ、插入Ｂ、选择Ｃ、交换Ｄ、归并~0349B`035009C1堆的形状是一棵（）Ａ、二叉排序树Ｂ、满二叉树Ｃ、完全二叉树Ｄ、平衡二叉树~0350C`035107C1在一个图中，所有顶点的度数之和等于图的边数的()倍。A、1/2B、1C、2D、4~0351C`035207C1在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的()倍。A、1/2B、1C、2D、4~0352B`035307C1有8个结点的无向图最多有()条边。A、14B、28C、56D、112~0353B`035407C1有8个结点的无向连通图最少有()条边。A、5B、6C、7D、8~0354C`035507C1有8个结点的有向完全图有()条边。A、14B、28C、56D、112~0355C`035607C1用邻接表表示图进行广度优先遍历时，通常是采用()来实现算法的。A、栈B、队列C、树D、图~0356B`035707C1用邻接表表示图进行深度优先遍历时，通常是采用()来实现算法的。A、栈B、队列C、树D、图~0357A`035807C2 A．0243156B.0136542C.0423165D.0361542建议：0134256已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是()~0358C`035907C2已知图的邻接矩阵,根据算法，则从顶点0出发，按深度优先遍历的结点序列是()A、0243156B、0135642C、0423165D、0134256~0359C`036007C2已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是()A、0243651B、0136425C、0423156D、0134256（建议：0123456）~0360B`036107C2已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是()A、0243165B、0135642C、0123465D、0123456~0361C `036207C2已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是()A．0132B.0231C.0321D.0123~0362D`036307C2已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是()A、0321B、0123C、0132D、0312~0363A`036407C1深度优先遍历类似于二叉树的()A、先序遍历B、中序遍历C、后序遍历D、层次遍历~0364A`036507C1广度优先遍历类似于二叉树的()A、先序遍历B、中序遍历C、后序遍历D、层次遍历~0365D`036607C1任何一个无向连通图的最小生成树()A、只有一棵B、一棵或多棵C、一定有多棵D、可能不存在（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）~0366A`036707B1图有、等存储结构，遍历图有、等方法。~0367邻接矩阵、邻接表深、度优先遍历、广度优先遍历`036807B1有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的。~0368出度`036907B1如果n个顶点的图是一个环，则它有棵生成树。（以任意一顶点为起点，得到n-1条边）~0369n`037007B1n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为。~0370O(n2)`037107B1n个顶点e条边的图，若采用邻接表存储，则空间复杂度为。~0371 O(n+e)`037207B1设有一稀疏图G，则G采用存储较省空间。~0372邻接表`037307B1设有一稠密图G，则G采用存储较省空间。~0373邻接矩阵`037407B1图的逆邻接表存储结构只适用于图。~0374有向`037507B1已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是。~0375将邻接矩阵的第i行全部置0`037607B1图的深度优先遍历序列惟一的。~0376不是`037707B1n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为；若采用邻接表存储时，该算法的时间复杂度为。~0377O(n2)、O(n+e)`037807B1n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为；若采用邻接表存储，该算法的时间复杂度为。~0378O(n2)、O(n+e)`037907B1图的BFS生成树的树高比DFS生成树的树高。~0379小或相等`038007B1用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为；用克鲁斯卡尔(Kruskal)算法的时间复杂度是。~0380O(n2)、O(elog2e)`038107B1若要求一个稀疏图G的最小生成树，最好用算法来求解。~0381克鲁斯卡尔(Kruskal)`038207B1若要求一个稠密图G的最小生成树，最好用算法来求解。~0382普里姆(Prim)`038307B1用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度的次序来得到最短路径的。~0383递增`038407B1拓扑排序算法是通过重复选择具有个前驱顶点的过程来完成的。~03840 `038507E3已知如图所示的有向图，请给出该图的:（1）每个顶点的入/出度；（2）邻接矩阵；（3）邻接表；（4）逆邻接表。顶点123456入度出度~0385 `038607E3请对下图的无向带权图：（1）写出它的邻接矩阵;（2）写出它的邻接表。~0386(1)(2)邻接表为：a→b4→c3b→a4→c5→d5→e9^c→a3→b5→d5→h5^d→b5→c5→e7→f6→g5→h4^e→b9→d7→f3^f→d6→e3→g2^g→d5→f2→h6^h→c5→d4→g6^`038707E3已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。~0387 `038807E3试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。~0388解：最短路径为：（a,c,f,e,d,g,b）`038907E3给定下列网G:(1)试着找出网G的最小生成树，画出其逻辑结构图；(2)用两种不同的表示法画出网G的存储结构图；(3)用C语言（或其他算法语言）定义其中一种表示法（存储结构）的数据类型。~0389AB———————CE————FG————D解：(1)最小生成树可直接画出，如右图所示。(2)可用邻接矩阵和邻接表来描述：邻接表为： a→b12→e4^b→a12→c20→e8→f9^c→b20→d15→g12^d→c15→g10^e→a4→b8→f6^f→b9→e6^g→c12→d10(3)注：用两个数组分别存储顶点表和邻接矩阵#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//假设的最大顶点数（可取为7）Typedefenum{DG,DN,AG,AN}GraphKind;//有向/无向图，有向/无向网TypedefstructArcCell{//弧（边）结点的定义VRTypeadj;//顶点间关系，无权图取1或0；有权图取权值类型InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];Typedefstruct{//图的定义VertexTypevexs[MAX_VERTEX_NUM];//顶点表，用一维向量即可AdjMatrixarcs;//邻接矩阵IntVernum,arcnum;//顶点总数（7），弧（边）总数（9）GraphKindkind;//图的种类标志}Mgraph;`039007F3编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。~0390解：StatusBuild_AdjList(ALGraph&G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表{InitALGraph(G);scanf("%d",&v);if(v<0)returnERROR;//顶点数不能为负G.vexnum=v;scanf("%d",&a);if(a<0)returnERROR;//边数不能为负G.arcnum=a;for(m=0;mnextarc;q=q->nextarc);q->nextarc=p;}p->adjvex=j;p->nextarc=NULL;}//whilereturnOK;}//Build_AdjList`039107F3试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w)，即删除一条边的操作。（如果要删除所有从第i个顶点出发的边呢？提示：将邻接矩阵的第i行全部置0）~0391 解：//本题中的图G均为有向无权图。StatusDelete_Arc(MGraph&G,charv,charw)//在邻接矩阵表示的图G上删除边(v,w){if((i=LocateVex(G,v))<0)returnERROR;if((j=LocateVex(G,w))<0)returnERROR;if(G.arcs[i][j].adj){G.arcs[i][j].adj=0;G.arcnum--;}returnOK;}//Delete_Arc`039207F3试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。~0392intvisited[MAXSIZE];//指示顶点是否在当前路径上intlevel＝1;//递归进行的层数intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0{if(i==j)return1;//i就是jelse{visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p->nextarc，level--){level++;k=p->adjvex;if(!visited[k]&&exist_path(k,j))return1;//i下游的顶点到j有路径}//for}//elseif(level==1)return0;}//exist_path_DFS`039307F3采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。（注：一条路径为简单路径指的是其顶点序列中不含有重现的顶点。）~0393intvisited[MAXSIZE];intexist_path_len(ALGraphG,inti,intj,intk)//判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径{{if(i==j&&k==0)return1;//找到了一条路径,且长度符合要求elseif(k>0){visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p->nextarc){l=p->adjvex;if(!visited[l])if(exist_path_len(G,l,j,k-1))return1;//剩余路径长度减一}//forvisited[i]=0;//本题允许曾经被访问过的结点出现在另一条路径中}//else return0;//没找到}//exist_path_len`039402C1单链表的存储密度（）A、大于1；B、等于1；C、小于1；D、不能确定~0394C`039502C2设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）P034P0àa13àa24àA30A、循环链表B、单链表C、双向循环链表D、双向链表~0395B`039602A2试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？~0396①顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（＝1？），存储空间利用率高。缺点：插入或删除元素时不方便。②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。`039702A2描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？~0397头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针！！！）首元素结点是指链表中存储线性表中第一个数据元素a1的结点。`039803B1向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈只能在插入和删除元素；对于队列只能在插入和删除元素。~0398线性任何栈顶队尾队首`039903B1栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为。~0399栈顶栈底`040003B1是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。~0400队列`########（结束标记）'