数据结构复习资料

数据结构复习资料这是我们12级的数据结构考试试卷回忆版。大家看看，上面的答案我现在也没核实是否完全正确，如有疑问的话请问老师哦一，选择1.栈和队列的共同点是(C)。A．都是先进后出B．都是先进先出C．只允许在端点处插入和删除元素D．没有共同点2.一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是(C)。A．edcbaB．decbaC．dceabD．Abcde3.在循环队列中，若front与rear分别表示对头元素和队尾元素的位置，则判断循环队列空的条件是(C)。A．front＝＝rear＋1B．rear＝＝front＋1C．front＝＝rearD．front＝＝04.设二维数组A[1…m，1…n]按行存储在数组B中，则二维数组元素A[i，j]在一维数组B中的下标为(A)。A．n*（i－1）＋jB.n*（i－1）＋j－1C．i*（j－1）D．j*m＋i－15.深度为5的二叉树至多有(C)个结点。A．16B．32C．31C．106.深度为5的二叉树至多有(D)个结点。A．32B．16C．10D．317.在数据结构中，从逻辑上可以把数据结构分为(C)。A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构8.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着(B)。A．数据元素具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等9.在循环双链表的p所指的结点之前插入s所指结点的操作是(D)。A．p－＞prior－＞priorB．p－＞prior－＞priorC．s－＞prior－＞next＝sD．s－＞prior－＞prior＝s10.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为(C)。A．O（n）O（n）B．O（n）O（1）C．O（1）O（n）D．O（1）O（1）11.已知一算术表达式的中缀形式为A＋B*C–D/E，后缀形式为ABC*＋DE/–，其前缀形式为（D）。A.–A＋B*C/DEB.–A＋B*CD/EC.–＋*ABC/DED．–＋A*BC/DE12.二叉树的第k层的结点数最多为(D).A．2^k-1B.2K+1C.2K-1D.2^(k-1)13.设有6个结点的无向图，该图至少应有(A)条边才能确保是一个连通图。A.5B.6C.7D.814.设一棵完全二叉树中有65个结点，则该完全二叉树的深度（B）。(A)8(B)7(C)6(D)515.（必考）设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（D）。(A)p-right=s；s-left=p；p-right-left=s；s-right=p-right；(B)s-left=p；s-right=p-right；p-right=s；p-right-left=s；(C)p-right=s；p-right-left=s；s-left=p；s-right=p-right；(D)s-left=p；s-right=p-right；p-right-left=s；p-right=s；16.设顺序表的长度为n,则顺序查找的平均比较次数为（C）。(A)n(B)n/2(C)(n+1)/2(D)(n-1)/217.组成数据的基本单位是（A）。(A)数据项(B)数据类型(C)数据元素(D)数据变量18.函数substr(“DATASTRUCTURE”，5，9)的返回值为（A）。(A)“STRUCTURE”(B)“DATA”(C)“ASTRUCTUR”(D)“DATASTRUCTURE”19.设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（C）。(A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l20.下列四种排序中（D）的空间复杂度最大。(A)插入排序(B)冒泡排序(C)堆排序(D)归并排序二，填空题1.通常从四个方面评价算法的质量：正确性易读性强壮性高效率2.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为_____9_____个，树的深度为______3_____，树的度为____3_____。3.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有2n个指针域，其中有n-1个指针域是存放了地址，有n+1个指针是空指针.4.快速排序的最坏时间复杂度为______O(n^2)___，平均时间复杂度为_____O(nlog2n)_____。5.数据的物理结构主要包括____顺序存储结构___和____链式存储结构___两种情况6.设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s-next=p-next;p-next=s;。7.设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为____6______。8.数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储（或存储结构）无关，是独立于计算机的三，计算题1.请画出下图的邻接矩阵和邻接表。解：邻接矩阵：邻接表如下图所示：2.设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果解：简单选择排序：(22，40，45，48，80，78)直接插入排序：(40，45，48，80，22，78)3.设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列解：后序遍历序列：DEBCA二叉树如图：4.已知一个无向图的顶点集为{a,b,c,d,e},其邻接矩阵如下所示：「01001｜｜10010｜｜00011｜｜01101｜｜10110(1)画出该图的图形；（2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列解：（1）：（2）：深度优先遍历序列为：abdce广度优先遍历序列为：abedc5.设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合解：E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}四．算法编程1.写出直接选择排序解：voidSelectSort(DataTypea[],intn){inti,j,small;DataTypetemp;for(i=0;in-1;i++){small=i;/*设第i个数据元素关键字最小*/for(j=i+1;jn;j++)/*寻找关键字最小的数据元素*/if(a[j].keya[small].key)small=j;/*记住最小元素的下标*/if(small!=i)/*当最小元素的下标不为i时交换位置*/{temp=a[i];a[i]=a[small];a[small]=temp;}}}2.二分法查找算法intBinarySearch(SeqListS,DataTypex){intlow=0,high=S.size-1;/*确定初始查找区间上下界*/intmind;while(low=high){mid=(low+high)/2;/*确定查找区间中心位置*/if(S.list[mid].key==x.key)returnmid;/*查找成功*/elseif(S.list[mid].keyx.key)low=mid+1;elseif(S.list[mid].keyx.key)high=mid-1;}return-1;/*查找失败*/}