数据结构附部分答案

第1页共11页一、选择题1、下面关于线性表的叙述错误的是（C）。A.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现2、栈是一种特殊的线性表，具有（B）性质A．先进先出B.先进后出C.后进后出D.顺序进出3、顺序循环队列中（数组大小为n），队头指示front指向队列的第一个元素，队尾指示rear指向队列最后一个元素的后一个位置，则循环队列中存放了n-1个元素，即循环队列满的条件是（B）。A．(rear+1)%n=front-1B.(rear+1)%n=frontC.(rear)%n=frontD.rear+1=front4、在一个单链表中，若删除p所指结点的后续结点，则执行（A）。A．p-next=p-next-nextB.p=p-next;p-next-nextC.p-next=p-nextD.p=p-next-next5、设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（A）。A.N0=N2+1B.N0=Nl+N2C.N0=N1+1D.N0=2N1+l6、设有6个结点的无向图，该图至少应有（D）条边才能确保是一个连通图。A.8B.6C.7D.57、设有向无环图G中的有向边集合E={1，2，2，3，3，4，1，4}，则下列属于该有向图G的一种拓扑排序序列的是（A）。A.1，2，3，4B.2，3，4，1C.1，4，2，3D.1，2，4，38、已知一个有向图如下所示，则从顶点a出发进行深度优先遍历，不可能得到的DFS序列为（A）。A.adbefcB.adcefbC.adcebfD.adefbcbecfad第2页共11页9、适用于折半查找的表的存储方式及元素排列要求是（D）A.链式方式存储，元素无序B.链式存储方式，元素有序C.顺序存储方式，元素无序D.顺序存储方式，元素有序10、设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（C）趟的分配和回收才能使得初始关键字序列变成有序序列。A.5B.4C.3D.811、栈和队列的共同特点是(A)。A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点12、用链接方式存储的队列，在进行插入运算时(D).A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改13、以下数据结构中哪一个是非线性结构？(D)A.队列B.栈C.线性表D.二叉树14、树最适合用来表示(C)。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据15、二叉树的第k层的结点数最多为(D).A．2k-1B.2K+1C.2K-1D.2k-116、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A）。(A)BADC(B)BCDA(C)CDAB(D)CBDA前序遍历先访问根，所以C为根，在中序遍历中先访问左子树，再访问根，最后访问右子树，所以在中序序列中，C前面的为左子树，第二个访问的是左子树的根A以此类推可得这样的一棵二叉树：第3页共11页17、下列四种排序中（D）的空间复杂度最大。(A)插入排序(B)冒泡排序(C)堆排序(D)归并排序18、对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（D）个，A．
1B．2C．3D．4分别是：55，64，46，10.H（K）=K%9，表示除以9的余数。由于地址重叠造成冲突，所以散列存储时，通常还要有解决冲突的办法，如线性探查法等等。19、设有6个结点的无向图，该图至少应有(A)条边才能确保是一个连通图。A.5B.6C.7D.820、设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（B）个空指针域。(A)2m-1(B)2m(C)2m+1(D)4m21.对一个算法的评价，不包括如下（B）方面的内容。A．健壮性和可读性B．并行性C．正确性D．时空复杂度22.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行(A)。A.p-next=HL-next;HL-next=p;B.p-next=HL;HL=p;C.p-next=HL;p=HL;D.HL=p;p-next=HL;23.对线性表，在下列哪种情况下应当采用链表表示？(B)A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变24.一个栈的输入序列为123，则下列序列中不可能是栈的输出序列的是(C)A.231B.321C.312D.12325.AOV网是一种（D）。A．有向图B．无向图C．无向无环图D．有向无环图26.下面程序的时间复杂为（B）for（i=1，s=0；i=n；i++）{t=1；for(j=1；j=i；j++)t=t*j；s=s+t；}(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4)27．设某有向图的邻接表中有n个头结点和m个表结点，则该图中有（C）条有向边。C(A)n(B)n-1(C)m(D)m-1有向图m个表结点对应m条边，每条边都是有向的第4页共11页28．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（B）。(A)abedfc(B)acfebd(C)aebdfc(D)aedfcb29.快速排序在最坏情况下的时间复杂度为（D）。A．O(log2n)B．O(nlog2n)C．0(n)D．0(n2)30.从二叉搜索树中查找一个元素时，其时间复杂度大致为(C)。A.O(n)B.O(1)C.O(log2n)D.O(n2)解析：如果二叉搜索树为平衡二叉树，查找一个元素的最坏时间复杂度为O(log2n)。二、填空题1、数据的物理结构主要包括顺序存储和链式存储两种情况。2、设顺序线性表中有n个数据元素，删除第i个位置上的数据元素需要移动表中n-1个元素。则第i个位置上插入一个数据元素需要移动表中n+1-i个元素3、用一维数组存放完全二叉树：ABCDEFGHI，则中序遍历该二叉树的结点序列为（）。4、设待排序的7记录的排序码为{312，126，272，226，28，165，123}，从小到大直接插入排序，一趟排序的结果是：（）。第5页共11页5.数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。6一个算法的效率可分为______时间____效率和____空间____效率。7.在树型结构中，树根结点没有____前趋___结点，其余每个结点的有且只有___一___个前趋驱结点；叶子结点没有___后继__结点；其余每个结点的后续结点可以__多个_。8.对于一个有n个结点的二叉树，当它为一棵__满/完全__二叉树时具有最小高度，即为___log2(N+1)____，当它为一棵单支树具有_最大__高度，即为__n__。9.在一棵二叉排序树上按___中序____遍历得到的结点序列是一个有序序列。10.对于一棵具有n个结点的完全二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为____2i____，右孩子结点的编号为___2i+1_____，双亲结点的编号为___i/2_____。11.在线性表的散列存储中，处理冲突的常用方法有___线性探测再散列____和__二次探测再散列___两种。12、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有___2n_____个指针域，其中有____n-1____个指针域是存放了地址，有____n+1____个指针是空指针。13.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为___O(log2n)_____，整个堆排序过程的时间复杂度为__O(nlog2n)______。14.在快速排序、堆排序、归并排序中，___归并______排序是稳定的。第6页共11页15.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有_e=2m_____关系。一个点的度数就等于该点连接的边数,一条边连接2个点,这两个点的度数都要加1,也就是说,有一条边总的度数就要加2,所以总度数是边数的2倍16．已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是(1，3，4，5，2)，BFS遍历的输出序列是(1，3，2，4，5)三、应用题1、假定有四个元素A,B,C,D依次进栈，进栈过程中允许出栈，请写出所有可能的出栈序列。进一个出一个，ABCD先进两个，AB进，进C出C,进D出D，出B出A，CDBA进A进B，进C进D，出D出C出B出A，DCBA下面的不解释了，不明白你再问BCDA,BDCA,BCAD,BADC,BACD,前三个一起进CBAD,CBDA,CDBA第一个进去就出来ADCB,ACDB,ACBD一共14种例题第7页共11页第8页共11页图3.2有向图用5个带权值{3,2,4,5,1}构造的哈夫曼树的带权路径长度是（）第9页共11页8、设有一个输入数据的序列是{46,25,78,62,12,80},试画出从空树起，逐个输入各个数据而生成的二叉排序树。第10页共11页四、程序填空1、如下为二分查找的非递归算法，试将其填写完整。IntBinsch(ElemTypeA[],intn,KeyTypeK){intlow=0;inthigh=n-1;while(low=high){intmid=_______________________________；if(K==A[mid].key)returnmid;//查找成功，返回元素的下标elseif(K[mid].key)______________________________________;//在左子表上继续查找else__________________________________;//在右子表上继续查找}return-1;//查找失败，返回-1}答案：(low+high)/2high=mid-1low=mid+12．循环队列的插入。循环队列数据结构定义如下：四、算法设计题1、设计算法，在顺序表test中插入元素a到第i个位置。要求考虑表满情况。第11页共11页2、设计算法，实现二叉树的递归先序遍历。3、设计算法，实现n个整数的快速排序。4、统计出单链表HL中结点的值等于给定值X的结点数。intCountX(LNode*HL,ElemTypex){inti=0;LNode*p=HL;//i为计数器while(p!=NULL){if(P-data==x)i++;p=p-next;}//while,出循环时i中的值即为x结点个数returni;}//CountX5、设计判断两个二叉树是否相同的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){if(bt1==0&&bt2==0)return(1);elseif(bt1==0||bt2==0||bt1-data!=bt2-data)return(0);elsereturn(judgebitree(bt1-lchild,bt2-lchild)*judgebitree(bt1-rchild,bt2-rchild));}6、设计两个自小到大有序单链表ha，hb的合并排序算法，合并