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

...wd......wd......wd...数据构造课程复习资料一、填空题：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为空的条件是〔假设指针域的名称为next〕head->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〔1〕B.O〔log2n〕C.O〔n〕D.O〔n2〕12.哈夫曼树中一定不存在[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〔n2〕B.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〔n2〕B.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〔n2〕B.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，15〕37.堆排序、快速排序、归并排序、归并排序、快速排序、堆排序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.B