2018年-2018数据结构专科复习资料

.PAGE.《数据结构》课程复习资料一、填空题：1.设需要对5个不同的记录关键字进行排序,则至少需要比较4次,至多需要比较10次。2.设二叉排序树的高度为h,则在该树中查找关键字key最多需要比较n次。3.设在长度为20的有序表中进行二分查找,则比较一次查找成功的结点数有1个,比较两次查找成功有结点数有2个。4.数据结构从逻辑上划分为三种基本类型：线性结构、树型结构和图型结构。5.在一个具有n个顶点的无向完全图中,包含有n<n-1>/2条边,在一个具有n个顶点的有向完全图中,包含有n<n-1>条边。6.向一棵B_树插入元素的过程中,若最终引起树根结点的分裂,则新树比原树的高度增加1。7.在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为O<log2n>,整个堆排序过程的时间复杂度为O<nlog2n>。8.在快速排序、堆排序、归并排序中,归并排序是稳定的。9.在有n个叶子结点的哈夫曼树中,总结点数是n-1。评卷人得分10.一棵树T采用二叉链表存储,如果树T中某结点为叶子结点,则在二叉链表BT中所对应的结点一定左右子树空。11.已知数组A［１０］［１０］为对称矩阵,其中每个元素占5个单元。现将其下三角部分按行优先次序存储在起始地址为1000的连续的内存单元中,则元素A［5,6］对应的地址是1225。12.在有n个结点的无向图中,其边数最多为n<n-1>/2。13.取出广义表A=<x,<a,b,c,d>>中原子x的函数是head<A>。14.对矩阵采用压缩存储是为了节省空间。15.带头结点的双循环链表L为空表的条件是L->next=L->prior或L->next=L。16.设线性表中元素的类型是实型,其首地址为1024,则线性表中第6个元素的存储位置是1044。17.对于顺序存储的栈,因为栈的空间是有限的,在进行入栈〔插入运算时,可能发生栈的上溢,在进行出栈〔删除运算时,可能发生栈的下溢。18.在双向链表中,每个结点有两个指针域,一个指向前驱结点,另一个指向后继结点。19.由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。20.折半查找的存储结构仅限于顺序存储结构,且是有序的。21.对于一个顺序存储的线性表,在表头插入元素的时间复杂度为O<n>,在表尾插入元素的时间复杂度为O<1>。22.在稀疏距阵所对应的三元组线形表中,每个三元组元素按行号为主序,列号为辅序的次序排列。23.中缀表达示3+X*〔2.4/5-6所对应的后缀表达示为3x2.45／6－*＋。24.在一棵高度为h的3叉树中,最多含有<3h-1>/2结点。25.分析下面算法〔程序段,给出最大语句频度n3,该算法的时间复杂度是O<n3>。for<i=0;i<n;i++>for<j=0;j<n;j++>A[i][j]=0;26.空串是零个字符的串,其长度等于零。27.一个图的邻接矩阵表示法是唯一的,而邻接表表示法是不唯一的。28.在一个单链表中p所指结点之前插入一个s<值为e>所指结点时,可执行如下操作：q=head;while<q->next!=p>q=q->next;s=newNode;s->data=e;q->next=s;//填空s->next=p;//填空29.在一个单链表中删除p所指结点的后继结点时,应执行以下操作：q=p->next;p->next=q->next;//填空deleteq;//填空30.两个串相等的充分必要条件是两个串的长度相等且对应位置的字符相同。31.二维数组A[10][20]采用列序为主方式存储,每个元素占一个存储单元并且A[0][0]的存储地址是200,则A[6][12]的地址是200+〔6*20+12=326。32.二维数组A[10..20][5..10]采用行序为主方式存储,每个元素占4个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的地址是1000+<<18-10>*6+<9-5>>*4=1208。33.求下列广义表操作的结果：<1>GetTail[GetHead[<<a,b>,<c,d>>]];<b><2>GetTail[GetHead[GetTail[<<a,b>,<c,d>>]]]<d>34.已知一个有向图的邻接矩阵表示,计算第i个结点的入度的方法是求矩阵第i列非零元素之和。35.已知一个图的邻接矩阵表示,删除所有从第i个结点出发的边的方法是将矩阵第i行全部置为零。36.在利用快速排序方法对一组记录〔54,38,96,23,15,72,60,45,83进行快速排序时,递归调用而使用的栈所能达到的最大深度为2,共需递归调用的次数为4,其中第二次递归调用是对〔23,38,15组记录进行快速排序。37.在堆排序,快速排序和归并排序中,若只从存储空间考虑,则应首先选取堆排序方法,其次选取快速排序方法,最后选取归并排序方法；若只从排序结果的稳定性考虑,则应选取归并排序方法；若只从平均情况下排序最快考虑,则应选取快速排序方法；若只从最坏情况下排序最快并且要节省内存考虑,则应选取堆排序方法。38.称算法的时间复杂度为O<f<n>>,其含义是指算法的执行时间和f<n>的数量级相同。39.在一个长度为n的单链表L中,删除链表中*p的前驱结点的时间复杂度为O<n>。40.假设为循环队列分配的向量空间为Q[20],若队列的长度和队头指针值分别为13和17,则当前尾指针的值为10。41.对于栈只能在栈顶插入和删除元素。42.设有一个顺序栈S,元素sl,s2,s3,s4,s5,s6依次进栈,如果6个元素的出栈顺序为s2,s3,s4,s6,s5,sl,则顺序栈的容量至少应为3。43.数据结构一般包括三个方面内容：数据的逻辑结构,数据的存储结构及数据的运算。44.在包含n个结点的顺序表上做等概率插入运算,平均要移动n/2个结点。45.队列的特性是先进先出。46.已知二叉树中叶子数为30,仅有一个孩子的结点数为20,则总结点数为79。47.中序遍历二叉排序树中的结点可以得到一个递增的关键字序列〔选填"先序"、"中序"或"后序"。48.n个节点的连通图至少有n-1条边。49.在堆排序和快速排序中,如果从平均情况下排序的速度最快的角度来考虑,应最好选择快速排序排序。50.带有一个头结点的单链表head为空的条件是〔假设指针域的名称为nexthead->next==NULL。51.设一组初始关键字序列为<38,65,97,76,13,27,10>,则第3趟简单选择排序后的结果为10,13,27,76,65,97,38。52.在拓扑排序中,拓扑序列的第一个顶点必定是入度为零的顶点。53.数据的逻辑结构分为两大类,它们是线性结构和非线性结构。54.在单链表中〔假设结点指针域名称为next,删除指针P所指结点的后继结点的语句是p->next=p->next->next。55.已知循环队列用数组data[n]存储元素值,用front,rear分别作为头尾指针,则当前元素个数为<rear-front+n>%n。56.若n为主串长,m为子串长,则串的朴素匹配算法最坏的情况下需要比较字符的总次数〔n-m+1×m。57.广义表<<a>,<<b>,j,<<<d>>>>>的表尾是<<<b>,j,<<<d>>>>>。58.已知二叉树有61个叶子节点,且仅有一个孩子的节点数为45,则总节点数为166。59.解决计算机与打印机之间速度不匹配问题,须要设置一个数据缓冲区,应是一个队列结构。二、单项选择题：1.队列的特点是[B]A.先进后出B.先进先出C.任意位置进出D.前面都不正确2.[B]A.nB.dC.rD.n-d3.在二叉树结点的先序序列、中序序列和后序序列中,所有叶子结点的先后顺序[B]A.都不相同B.完全相同C.先序和中序相同,而与后序不同D.中序和后序相同,而与先序不同4.设有198个初始归并段,如采用K-路平衡归并三遍完成排序,则K值最大为[C]A.12B.13C.14D.155.下面关于广义表的叙述中,不正确的是[B]A.广义表可以是一个多层次的结构B.广义表至少有一个元素C.广义表可以被其他广义表所共享D.广义表可以是一个递归表6.设二叉树根结点的层次为0,一棵深度〔高度为k的满二叉树和同样深度完全二叉树各有f个结点和c个结点,下列关系式不正确的是[B]A.f>=c B.c>fC.f=2k+1-aD.c>sk-17.从L=<<apple,pear>,<orange,banana>>中,取出banana元素的表达式为[D]A.head<tail<L>>B.head<head<tail<L>>>C.tail<head<tail<L>>> D.head<tail<head<tail<L>>>>8.下列文件的物理结构中,不利于文件长度动态增长的文件物理结构是[A]A.顺序结构B.链接结构C.索引结构D.Hash结构9.在数据结构中,数据元素可由[C]A.实体B.域C.数据项D.字段10.,〔FloyD[D]A.O<1>B.O<n>C.O<n>D.O<n3>11.对n个记录的文件进行快速排序,所需要的辅助存储空间为[B]A.O〔1B.O〔log2nC.O〔nD.O〔n212.哈夫曼树中一定不存在[B]A.度为0的结点B.度为1的结点C.度为2的结点D.带权的结点13.下述哪一条是顺序存储方式的优点？[A]A.存储密度大B.插入和删除运算方便C.获取符合某种条件的元素方便D.查找运算速度快14.有一个二维数组A[m][n],假设A[0][0]存放位置在600<10>,A[3][3]存放位置在678<10>,每个元素占一个空间,问A[2][3]<10>存放在什么位置？〔脚注<10>表示用10进制表示,m>3[D]A.658B.648C.633D.65315.下列关于二叉树遍历的叙述中,正确的是[A]A.若一个叶子是某二叉树的中序遍历的最后一个结点,则它必是该二叉树的前序遍历最后一个结点B.若一个结点是某二叉树的前序遍历最后一个结点,则它必是该二叉树的中序遍历的最后一个结点C.若一个结点是某二叉树的中序遍历的最后一个结点,则它必是该二叉树的前序最后一个结点D.若一个树叶是某二叉树的前序最后一个结点,则它必是该二叉树的中序遍历最后一个结点16.第K层二叉树的结点总数最多为[A]A.2k-1B.2k+1C.2K-1D.2k-117.线性表进行二分法查找,其前提条件是[C]A.线性表以链接方式存储,并且按关键码值排好序B.线性表以顺序方式存储,并且按关键码值的检索频率排好序C.线性表以顺序方式存储,并且按关键码值排好序D.线性表以链接方式存储,并且按关键码值的检索频率排好序18.n个记录进行堆排序,所需要的辅助存储空间为[C]A.O<1og2n>B.O<n>C.O<1>D.O<n2>19.线性表〔7,34,77,25,64,49,20,14进行散列存储时,若选用H〔K=K%7作为散列函数,则散列地址为0的元素有〔个。[D]A.1B.2C.3D.420.下列关于数据结构的叙述中,正确的是[D]A.数组是不同类型值的集合B.递归算法的程序结构比迭代算法的程序结构更为精炼C.树是一种线性结构D.用一维数组存储一棵完全二叉树是有效的存储方法21.以下数据结构中哪一个是线性结构？[B]A.有向图B.队列C.线索二叉树D.B树22.在一个单链表HL中,若要在当前由指针p指向的结点后面插入一个由q指向的结点,则执行如下〔语句序列。[D]A.p=q;p->next=q;B.p->next=q;q->next=p;C.p->next=q->next;p=q;D.q->next=p->next;p->next=q;23.〔不是队列的基本运算。[A]A.在队列第i个元素之后插入一个元素B.从队头删除一个元素C.判断一个队列是否为空D.读取队头元素的值24.若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi为[C]A.iB.n=iC.n-i+1D.不确定25.栈的特点是〔B,队列的特点是〔A。A.先进先出B.先进后出26.设有两个串p和q,求q在p中首次出现的位置的运算称作[B]A.连接B.模式匹配C.求子串D.求串长27.二维数组A中,每个元素A[i][j]的长度为3个字节,行下标i从0到7,列下标j从0到9,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A[4][7]的起始地址为[B]A.SA+141B.SA+180C.SA+222D.SA+22528.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是[D]A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca29.在一非空二叉树的中序遍历序列中,根结点的右边[A]A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点30.具有6个顶点的无向图至少应有〔条边才能确保是一个连通图。[A]A.5B.6C.7D.831.二分查找和二叉排序树的时间性能[B]A.相同B.不相同32.采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为[B]A.O〔n2B.O<nlog2n>C.O<n>D.O<log2n>33.在待排序的元素序列基本有序的前提下,效率最高的排序方法是[A]A.插入排序B.选择排序C.快速排序D.归并排序34.下述几种排序方法中,要求内存量最大的是[D]A.插入排序B.选择排序C.快速排序D.归并排序35.设有两个串p和q,求q在p中首次出现的位置的运算称作[B]A.连接B.模式匹配C.求子串D.求串长36.二维数组A中,每个元素A[i][j]的长度为3个字节,行下标i从0到7,列下标j从0到9,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A[4][7]的起始地址为[B]A.SA+141B.SA+180C.SA+222D.SA+22537.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是[D]A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca38.在一非空二叉树的中序遍历序列中,根结点的右边[A]A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点39.具有6个顶点的无向图至少应有〔条边才能确保是一个连通图。[A]A.5B.6C.7D.840.二分查找和二叉排序树的时间性能[B]A.相同B.不相同C.可能相同D.不确定41.采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为[B]A.O〔n2B.O<nlog2n>C.O<n>D.O<log2n>42.在待排序的元素序列基本有序的前提下,效率最高的排序方法是[A]A.插入排序B.选择排序C.快速排序D.归并排序43.下面的序列中〔是大顶堆。[D]A.1,2,8,5,3,9,10,4B.1,5,10,6,7,8,9,2C.9,8,7,6,4,8,2,1D.9,8,7,6,5,4,3,144.对一个算法的评价,不包括如下〔方面的内容。[B]A.健壮性和可读性B.并行性C.正确性D.时空复杂度45.在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点,则执行[A]A.p->next=HL->next;HL->next=pB.p->next=HL;HL=pC.p->next=HL;p=HLD.HL=p;p->next=HL46.对线性表,在下列哪种情况下应当采用链表表示？[B]A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变47.一个栈的输入序列为123,则下列序列中不可能是栈的输出序列的是[C]A.231B.321C.312D.12348.每一趟都能选出一个元素放在其最终位置上,并且不稳定的排序算法是[B]A.冒泡排序B.简单选择排序C.希尔排序D.直接插入排序49.采用开放定址法处理散列表的冲突时,其平均查找长度[B]A.低于链接法处理冲突B.高于链接法处理冲突C.与链接法处理冲突相同D.高于二分查找50.若需要利用形参直接访问实参时,应将形参变量说明为〔参数。[D]A.值B.函数C.指针D.引用51.在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具有相同的[A]A.行号B.列号C.元素值D.非零元素个数52.快速排序在最坏情况下的时间复杂度为[D]A.O<log2n>B.O<nlog2n>C.O<n>D.O<n2>53.从二叉搜索树中查找一个元素时,其时间复杂度大致为[C]A.O<n>B.O<1>C.O<log2n>D.O<n2>54.设一个有序的单链表中有n个结点,现要求插入一个新结点后使得单链表仍然保持有序,则该操作的时间复杂度为[D]A.O<log2n>B.O<1>C.O<n2>D.O<n>55.设一棵m叉树中度数为0的结点数为N0,度数为1的结点数为Nl,……,度数为m的结点数为Nm,则N0=[B]A.Nl+N2+……+NmB.l+N2+2N3+3N4+……+<m-1>NmC.N2+2N3+3N4+……+<m-1>NmD.2Nl+3N2+……+<m+1>Nm56.二维数组A中,每个元素A的长度为3个字节,行下标i从0到7,列下标j从0到9,从首地址SA开始连续存放在存储器内,该数组按行存放时,数组元素A[7][4]的起始地址为[C]A.SA+141B.SA+144C.SA+222D.SA+22557.如果某二叉树的前根次序遍历结果为stuwv,中序遍历为uwtvs,那么该二叉树的后序为[B]A.uwvtsB.vwutsC.wuvtsD.wutsv58.深度为5的二叉树至多有〔个结点。[C]A.16B.32C.31D.1059.在一个无向图中,所有顶点的度数之和等于所有边数的〔倍。[C]A.1/2B.1C.2D.460.采用顺序查找方法查找长度为n的线性表时,每个元素的平均查找长度为[C]A.nB.n/2C.<n+1>/2D.<n-1>/261.采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为[C]A.O〔n2B.O<nlog2n>C.O<n>D.O<log2n>62.下述几种排序方法中,要求内存量最大的是[D]A.插入排序B.选择排序C.快速排序D.归并排序63.排序方法中,从未排序序列中依次取出元素与已排序序列〔初始时为空中的元素进行比较,将其放入已排序序列的正确位置上的方法,称为[C]A.希尔排序B.起泡排序C.插入排序D.选择排序64.对于长度为9的有序顺序表,若采用折半搜索,在等概率情况下搜索成功的平均搜索长度为〔的值除以9。[C]A.20B.18C.25D.2265.在有向图中每个顶点的度等于该顶点的[C]A.入度B.出度C.入度与出度之和D.入度与出度之差66.在基于排序码比较的排序算法中,〔算法的最坏情况下的时间复杂度不高于O<n10g2n>。[C]A.起泡排序B.希尔排序C.归并排序D.快速排序67.当α的值较小时,散列存储通常比其他存储方式具有〔的查找速度。[B]A.较慢B.较快C.相同D.不清楚68.设有一个含200个表项的散列表,用线性探查法解决冲突,按关键码查询时找到一个表项的平均探查次数不超过1.5,则散列表项应能够至少容纳〔个表项。[A]<设搜索成功的平均搜索长度为Snl＝{1+l／<1一α>}／2,其中α为装填因子>A.400B.526C.624D.67669.堆是一个键值序列{k1,k2,…..kn},对I=1,2,….|_n/2_|,满足[C]A.ki≤k2i≤k2i+1B.ki<k2i+1<k2iC.ki≤k2i且ki≤k2i+1<2i+1≤n>D.ki≤k2i或ki≤k2i+1<2i+1≤n>70.若将数据结构形式定义为二元组<K,R>,其中K是数据元素的有限集合,则R是K上[B]A.操作的有限集合B.映象的有限集合C.类型的有限集合D.关系的有限集合71.下列图示的顺序存储结构表示的二叉树是[A]72.由同一关键字集合构造的各棵二叉排序树[B]A.其形态不一定相同,但平均查找长度相同B.其形态不一定相同,平均查找长度也不一定相同C.其形态均相同,但平均查找长度不一定相同D.其形态均相同,平均查找长度也都相同73.ISAM文件和VSAM文件的区别之一是[C]A.前者是索引顺序文件,后者是索引非顺序文件B.前者只能进行顺序存取,后者只能进行随机存取C.前者建立静态索引结构,后者建立动态索引结构D.前者的存储介质是磁盘,后者的存储介质不是磁盘74.下列描述中正确的是[D]A.线性表的逻辑顺序与存储顺序总是一致的B.每种数据结构都具备三个基本运算：插入、删除和查找C.数据结构实质上包括逻辑结构和存储结构两方面的内容D.选择合适的数据结构是解决应用问题的关键步骤75.下面程序段的时间复杂度是[B]I=s=0While<s<n>{I++;s+=I;}A.O<1>B.O<n>C.O<log2n>D.O<n^2>76.如果只想得到1024个元素组成的序列中的前5个最小元素,那么用〔方法最快。[A]A.起泡排序B.快速排序C.堆排序D.直接选择排序77.算法分析的目的是[B]A.辨别数据结构的合理性B.评价算法的效率C.研究算法中输入与输出的关系D.鉴别算法的可读性78.在线性表的下列运算中,不改变数据元素之间结构关系的运算是[C]A.插入B.删除C.定位D.排序79.若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则可能出现的出栈序列为[D]A.3,2,6,1,4,5B.5,6,4,2,3,1C.1,2,5,3,4,6D.3,4,2,1,6,580.设串sl=″DataStructureswithJava″,s2=″it″,则子串定位函数index<s1,s2>的值为[A]A.15B.16C.17D.1881.一个顺序存储的线性表的第一个元素的存储地址是100,每个元素的长度为4,则第4个元素的存储地址是[B]A.108B.112C.116D.12082.从一个具有n个结点的单链表中查找其值等于x的结点,在查找成功的情况下,平均需要比较〔个结点。[C]A.nB.n/2C.<n+1>/2D.<n-1>/283.在任意一棵二叉树的前序序列和后序序列中,各叶子之间的相对次序关系[D]A.不一定相同B.互为逆序C.都不相同D.都相同84.高度为5的二叉树至多有结点数为[A]A.63B.32C.24D.6485.若用邻接矩阵表示一个有向图,则其中每一列包含的″1″的个数为[B]A.图中每个顶点的出度B.图中每个顶点的入度C.图中弧的条数D.图中连通分量的数目86.图的邻接矩阵表示法一般不太适用于表示[A]A.无向图B.有向图C.稠密图D.稀疏图87.循环队列是空队列的条件是[B]A.Q->rear==Q->frontB.<Q->rear+1>%maxsize==Q->frontC.Q->rear==0D.Q->front==088.设有一广义表E=〔a,b,<c,d>,其长度为[A]A.2B.3C.4D.589.某二叉树的前序遍历序列为ABDEFC,中序遍历序列为DBEFAC,则后序遍历序列为[D]A.DFEBCAB.DBECFAC.BDAECFD.DBEFCA90.下列〔不是利用查找表中数据元素的关系进行查找的方法。[C]A.有序表的查找B.二叉排序树的查找C.平衡二叉树D.散列查找91.下述几种排序方法中,要求内存量最大的是[B]A.插入排序B.快速排序C.归并排序D.选择排序92.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的〔倍。[B]A.1/2B.1C.2D.493.在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点,则执行[A]A.p->next=HL->next;HL->next=pB.p->next=HL;HL=pC.p->next=HL;p=HLD.HL=p;p->next=HL94.对线性表,在下列哪种情况下应当采用链表表示？[B]A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变95.一个栈的输入序列为123,则下列序列中不可能是栈的输出序列的是[C]A.231B.321C.312D.12396.每一趟都能选出一个元素放在其最终位置上,并且不稳定的排序算法是[B]A.冒泡排序B.简单选择排序C.希尔排序D.直接插入排序97.采用开放定址法处理散列表的冲突时,其平均查找长度[B]A.低于链接法处理冲突B.高于链接法处理冲突C.与链接法处理冲突相同D.高于二分查找98.若需要利用形参直接访问实参时,应将形参变量说明为〔参数。[D]A.值B.函数C.指针D.引用99.在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具有相同的[A]A.行号B.列号C.元素值D.非零元素个数100.快速排序在最坏情况下的时间复杂度为[D]A.O<log2n>B.O<nlog2n>C.O<n>D.O<n2>101.从二叉搜索树中查找一个元素时,其时间复杂度大致为[C]A.O<n>B.O<1>C.O<log2n>D.O<n2>102.设一个有序的单链表中有n个结点,现要求插入一个新结点后使得单链表仍然保持有序,则该操作的时间复杂度为[D]A.O<log2n>B.O<1>C.O<n2>D.O<n>103.设一棵m叉树中度数为0的结点数为N0,度数为1的结点数为Nl,……,度数为m的结点数为Nm,则N0=[B]A.Nl+N2+……+NmB.l+N2+2N3+3N4+……+<m-1>NmC.N2+2N3+3N4+……+<m-1>NmD.2Nl+3N2+……+<m+1>Nm104.设有序表中有1000个元素,则用二分查找查找元素X最多需要比较〔次。[B]A.25B.10C.7D.1105.设连通图G中的边集E={<a,b>,<a,e>,<a,c>,<b,e>,<e,d>,<d,f>,<f,c>},则从顶点a出发可以得到一种深度优先遍历的顶点序列为[B]A.abedfcB.acfebdC.aebdfcD.aedfcb106.拓扑排序运算只能用于[C]A.带权有向图B.连通无向图C.有向无环图D.无向图107.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是[B]A.O<1>B.O<n>C.O<n2>D.O<nlogn>计算与算法应用题：1.已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};E={<1,2>3,<1,3>5,<1,4>8,<2,5>10,<2,3>6,<3,4>15,<3,5>12,<3,6>9,<4,6>4,<4,7>20,<5,6>18,<6,7>25};按照普里姆算法从顶点1出发得到最小生成树,试写出在最小生成树中依次得到的各条边。2.一棵二叉树的先序、中序和后序序列分别如下,其中有一部分未显示出来。试求出空格处的内容,并画出该二叉树。先序序列：BFICEHG中序序列：DKFIAEJC后序序列：KFBHJGA3.画出下列树对应的二叉树,并写出其先根遍历序列：BBDFCAEG4.将关键字序列为{54,29,37,86,71,91,8,31,44,26}进行归并排序,写出各趟详细过程。5.试列出如下图中全部可能的拓扑排序序列。6.设某通信系统使用A,B,C,D,E,F,G,H八个字符,他们出现的概率w={5,29,7,8,14,23,3,11},试构造对应的哈夫曼树〔请按左子树根结点的权小于右子树树根结点的权的次序构造。7.给定表〔119,14,22,1,66,21,83,27,56,13,10,请按表中元素的顺序构造一棵平衡二叉树,并求其在等概率情况下查找成功的平均长度。8.已知一个有向图的顶点集V和边集G分别为：V={a,b,c,d,e,f,g,h}E={<a,b>,<a,c>,<b,f>,<c,d>,<c,e>,<d,a>,<d,f>,<d,g>,<e,g>,<f,h>};假定该图采用邻接矩阵表示,则分别写出从顶点a出发进行深度优先搜索遍历和广度优先搜索遍历得到的顶点序列。9.设散列表的长度为13,散列函数为H〔h=k%13,给定的关键码序列为19,14,23,01,68,20,84,27。试画出用线性探查法解决冲突时所构成的散列表。012345678910111210.对7个关键字进行快速排序,在最好的情况下仅需进行10次关键字的比较。<1>假设关键字集合为{1,2,3,4,5,6,7},试举出能达到上述结果的初始关键字序列；<2>对所举序列进行快速排序,写出排序过程。11.如图所示二叉树,回答下列问题。12.画出在一个初始为空的AVL树中依次插入3,1,4,6,9,8,5,7时每一插入后AVL树的形态。若做了某种旋转,说明旋转的类型。然后,给出在这棵插入后得到的AVL树中删去根结点后的结果。13.已知一组记录的排序码为〔46,79,56,38,40,80,95,24,写出对其进行快速排序的每一次划分结果。14.一个线性表为B=〔12,23,45,57,20,03,78,31,15,36,设散列表为HT[0..12],散列函数为H〔key=key%13并用线性探查法解决冲突,请画出散列表,并计算等概率情况下查找成功的平均查找长度。15.已知一棵二叉树的前序遍历的结果序列是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试写出这棵二叉树的后序遍历结果。16.假定对线性表<38,25,74,52,48,65,36>进行散列存储,采用H<K>=K％9作为散列函数,若分别采用线性探查法和链接法处理冲突,则计算对应的平均查找长度。17.已知哈希表地址空间为0..8,哈希函数为H<key>=key%7,采用线性探测再散列处理冲突,将数据序列{100,20,21,35,3,78,99,45}依次存入此哈希表中,列出插入时的比较次数,并求出在等概率下的平均查找长度。18.试画出下面带权无向图的一棵最小生成树。55768432997abdcef19.已知关键字序列为：{03,87,12,61,98,70,61*,97,27,53,42,56,77,}请采用希尔<Shell>排序法对该序列作非递减排序.按5,3,1分组,写出下列标明的趟的结果。初始03,87,12,61,98,70,97,27,53,42,56,77第一趟第二趟每三趟四、阅读下列算法,分析它的作用：1.intAA<LNode*HL,ElemTypex>{intn=0;LNode*p=HL;while<p!=NULL>{if<p->data==x>n++;p=p->next;}returnn;}对于结点类型为LNode的单链表,以上算法的功能为：2.intAA<LNode*HL,ElemTypex>{intn=0;LNode*p=HL;while<p!=NULL>{if<p->data==x>n++;p=p->next;}returnn;}对于结点类型为LNode的单链表,以上算法的功能为：3.假定从键盘上输入一批整数,依次为：786345309134–1,请写出输出结果。#include<iostream.h>#include<stdlib.h>constintstackmaxsize=30;typedefintelemtype;structstack{elemtypestack[stackmaxsize];inttop;};#include"stack.h"voidmain[]{stacka;initstack<a>;intx;cin>>x;while<x!=-1>{push<a,x>;cin>>x;}while<!stackempty<a>>cout<<pop<a><<"";cout<<end1;}该算法的输出结果为：_____________。4.读下述算法,说明本算法完成什么功能。template<calsstype>voidBinTree<Type>：：unknown<BinTreeNode<Type>*t>{BinTreeNode<Type>*p=t,*temp;if<p!=NULL>{temp=p→leftchild;p→leftchild=p→rightchild;p→rightchild=temp;unknown<p→leftchild>;undnown<p→rightchild>;}}该算法的功能是：______________。5.阅读下列算法,说明该算法的作用。//类定义//类定义constintMAX=20;typedefcharElemType;classSqstack{private:ElemTypeelem[MAX];inttop;public:Sqstack<>{top=0};ElemTypepop<>;voidpush<ElemTypex>;//…….;};{if<top==MAX-1>cout<<"\n满！"；else{top++;elem[top]=x;}}//pushstructSnode//结点结构structSnode//结点结构{chardata;Snode*next;};classLink//链表类{private:Snode*Head;public:Link<>{Head=NULL};voidcreat<>;voidoutput<>;//…….;voidLink:output<>{p=Head->next;while<p!=NULL>{cout<<"\ndata="<<p->data;p=p->next;}}//output7.读下述算法,说明本算法完成什么功能。voidBtree::inordern<bnode*p,int&n>{if<p!=NULL>{inordern<p->lch,n>;if<p->lch==NULL&&p->rch==NULL>n++;inordern<p->rch,n>;}}//inordern8.voidAD<Lnode*&HL>{Insert<HL,30>;Insert<HL,50>;Delete<HL,26>;Delete<HL,55>;}假定调用该算法时以HL为表头指针的单链表中的内容为〔15,26,48,55,则调用返回后该单链表中的内容为：____________。9.voidAI<adjmatrrixGA,inti,intn>{cout<<i<<’’;visted[i]=true;for<intj=0;j<n;j++>if<Ga[I][j]!=0&&GA[i][j]!=MaxValue&&!visited[j]>AI<GA,j,n>;}该算法的功能为：_______________。//类定义//类定义constintMAX=20;typedefcharElemType;classSqstack{private:ElemTypeelem[MAX];inttop;public:Sqstack<>{top=0};ElemTypepop<>;voidpush<ElemTypex>;//…….;};ElemTtypeSqstack::pop[]{ElemTypex;if<top==0>x=-999;else{x=elem[top];top--;}returnx;}//popstructSnode//结点结构structSnode//结点结构{chardata;Snode*next;};classLink//链表类{private:Snode*Head;public:Link<>{Head=NULL};voidcreat<>;voidreverse<>;voidoutput<>;//…….;voidLink::reverse<>{Snode*p,*q;p=Head->next;Head->next=NULL;while<p!=NULL>{q=p->next;p->next=Head->next;Head>next=p;p=q;}aHeadaHeadbc^ed12.下列函数是二叉排序树的什么算法？如果K值为5,针对下图所示二叉树,运行下列算法,输出是什么？比较几次得到结果？VoidBstree::Search<KeyTypeK>{intflag=0;BstNode*q=root,*p=NULL;while<<q!=NULL>&&<flag==0>>7878524929elseif<K<q->key>{p=q;q=q->lch;}else{p=q;q=q->rch;}}if<flag==0>cout<<"\n查找失败,无此结点！\n";elsecout<<"\n查找成功,找到："<<q->key<<endl;}13.voidAA<LNode*HL,constElemType&item>{LNode*newptr=newLnode;newptr->data=item;LNode*p=HL;while<p->next!=HL>p=p->next;newptr->next=HL;p->next=newptr;}对于结点类型为LNode的单链表,以上算法的功能为：14.voidBB<List&L>{inti=0;while<i<L.size>{intj=i+1;while<j<L.size>{if<L.list[j]==L.list>{for<intk=j+1;k<L.size;k++>L.list[k-1]=L.list[k];L.size--;}elsej++;}i++;}}以上算法的功能为：15.voidCC<BTreeNode*&BST>{ElemTypea[6]={45,23,78,35,77,25}；BST=NULL；for<inti=0,i<6;i++>Insert<BST,a[i]>;}调用该算法后,生成的二叉搜索数的中序序列为：16.voidDD<>{ElemTypeA[]={1,3,5,7,9,2,4,6,8,10},B[10];TwoMerge<A,B,0,4,9>;for<inti=0;i<10;i++>cout<<B[i]<<"";cout<<endl;}调用该算法后,输出结果为：17.template<classType>intSeqList<Type>::Insert<Type&x,inti>{if<i<0||i>last+1||last==MaxSize-1>return0;else{Last++;for<intj=last;j<i;j-->data[j]=data[j-1];data[i]=x;return1;}}对于结点类型为SeqList的顺序表,以上算法的功能为：算法设计题：1.编写复制一棵二叉树的非递归算法。aaHeadbbc^ed77Head97b15^5026boolFind〔BtreeNode*BST,ElemType&item《数据结构》课程复习参考答案一、填空题：1.4,102.n3.1,24.线性结构树型结构图型结构5.n<n-1>/2n<n-1>6.增加17.O<log2n>O<nlog2n>8.归并9.n-110.左右子树空11.122512.n<n-1>/213.head<A>14.节省空间15.L->next=L->prior或L->next=L16.104417.入栈〔插入出栈〔删除18.前驱结点后继结点19.中序序列20.顺序存储结构有序的21.O<n>O<1>22.行号列号23.3x2.45／6－*＋24.<3h-1>/225.n3O<n3>26.零个字符的串零27.邻接矩阵邻接表28.sp29.q->nextq30.两个串的长度相等且对应位置的字符相同31.200+〔6*20+12=32632.1000+<<18-10>*6+<9-5>>*4=120833.<1>.<b><2>.<d>34.求矩阵第i列非零元素之和35.将矩阵第i行全部置为零36.2.2;4;〔23,38,1537.堆排序、快速排序、归并排序、归并排序、快速排序、堆排序38.f<n>39.O<n>40.1041.栈顶42.343.逻辑结构44.n/245.先进先出46.7947.中序48.n-149.快速排序50.head->next==NULL51.10,13,27,76,65,97,3852.入度为零53.非线性结构54.p->next=p->next->next55.<rear-front+n>%n56.〔n-m+1×m57.<<<b>,j,<<<d>>>>>58.16659.队列二、单项选择题：1.B2.B3.B4.C5.B6.B7.D8.A9.C10.D11.B12.B13.A14.D15.A16.A17.C18.C19.D20.D21.B22.D23.A24.C25①.B25②.A26.B27.B28.D29.A30.A31.B32.B33.A34.D35.B36.B37.D38.A39.A40.B41.B42.A43.D44.B45.A46.B47.C48.B49.B5