数据结构复习题

2017 2018学年度第2学期数据结构 复习提纲 一、单项选择题题号12345678910答案CADCABABCD题号11121314151617181920答案AADAADCBAB1在数据结构中，从逻辑上可以把数据结构分为_两类。A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D内部结构和外部结构2链表不具有的特点是_。A可随机访问任一元素B插入、删除不需要移动的元素C不必事先估计存储空间D所需空间与线性表长度成正比3若线性表最常用的运算是存取第i个元素及其前驱元素，则采用_存储方式节省时间。A单链表B双链表C循环单链表D顺序表4算法分析的目的是_。A找出数据结构的合理性B研究算法中的输入和输出关系C分析算法的效率以求改进D分析算法的易读性和文档性5若一个栈用数组data1.n存储，初始栈顶指针top为0，则以下元素x进栈的操作正确的是_。Atop+; datatop=x;Bdatatop=x; top+;Ctop-; datatop=x;Ddatatop=x; top-;6表达式a*(b+c)-d的后缀表达式是_。Aabcd*+-Babc+*d-Cabc*+d-D-+*abcd7递归函数f(1)=1，f(n)=f(n-1)+n(n1)的递归出口是_。Af(1)=1Bf(1)=0Cf(0)=0Df(n)=n8将递归算法转换成对应的非递归算法时，通常需要使用_保存中间结果。A队列B栈C链表D树9对稀疏矩阵采用压缩存储，其缺点之一是_。A无法判断矩阵有多少行、多少列B无法根据行、列号查找某个矩阵元素C无法根据行、列号直接计算矩阵元素的存储地址D使矩阵元素之间的逻辑关系更加复杂10一个n阶上三角矩阵a按行优先顺序压缩存放在一维数组b中，则b中的元素个数是_。AnBn2Cn(n+1)/2Dn(n+1)/2+111度为4，高度为h的树_。A至少有h+3个结点B最多有4h-1个结点C最多有4h个结点D至少有h+4个结点12用双亲存储结构表示树，其优点之一是比较方便_。A找指定结点的双亲结点B找指定结点的孩子结点C找指定结点的兄弟结点D判断某结点是不是叶子结点13设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有_个结点。A13B12C26D2514无向图的邻接矩阵是一个_。A对称矩阵B零矩阵C上三角矩阵D对角矩阵15在图的广度优先遍历算法中用到一个队列，每个顶点最多进队_次。A1B2C3D不确定16在用Prim和Kruskal算法构造最小生成树时，前者更适合于_。A有向图B无向图C稀疏图D稠密图17有一个有序表R1.13=1, 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100，当用二分查找法查找值为82的节点时，经过_次比较后查找成功。A1B2C4D818在采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块，则每块分为_个结点最佳。A9B25C6D62519若R中有10000个元素，如果仅要求求出其中最大的10个元素，则采用_方法最节省时间。A堆排序B希尔排序C快速排序D基数排序20有一组序列（48, 36, 68, 99, 75, 24, 28, 52）进行快速排序，要求结果从小到大排序，则进行一次划分之后的结果为_。A24 28 36 48 52 68 75 99B28 36 24 48 75 99 68 52C36 68 99 48 75 24 28 52D28 36 24 48 99 75 68 52二、填空题题号答案题号答案题号答案1问题规模2O(n)3假溢出42855462h-17关键活动8无环图9RL10基数排序1在分析算法的时间复杂度时，通常认为算法的执行时间是_的函数。2求一个双链表长度的算法的时间复杂度为_。3在实现顺序队的时候，通常将数组看成是一个首尾相连的环，这样做的目的是为了避免产生_现象。4有如下递归过程：void reverse( int m ) printf(%d, n%10); if( n/10!=0 ) reverse(n/10);调用语句reverse(582)的结果是_。5广义表(a, b,( ), c), d), e, (f), g)的深度是_。6在高度为h（h0）的二叉树中最多有_个结点。7AOE网中从源点到汇点长度最长的路径称为关键路径，该路径上的活动称为_。8可以进行拓扑排序的有向图一定是_。9输入序列为（20， 35， 30，），构造一棵平衡二叉树，其中的第一次调整为_型调整。10在排序过程中，任何情况下都不比较关键字大小的排序方法是_。三、判断题题号12345678910答案FTFFFTFTFF1如果数据元素值发生改变，则数据的逻辑结构也随之改变。（ ）2在循环单链表中没有为空的指针域。（ ）3顺序栈中元素值的大小是有序的。（ ）4任何递归算法都是尾递归。（ ）5稀疏矩阵的特点是矩阵中元素较少。（ ）6哈夫曼树中不存在度为1的结点。（ ）7完全二叉树中的每个结点或者没有孩子或者有两个孩子。（ ）8强连通分量是有向图中的极大强连通子图。（ ）9哈希冲突是指同一个关键字的记录对应多个不同的哈希地址。（ ）10任何情况下折半插入排序都优于直接插入排序。（ ）四、问答题1设计一个算法，删除一个单链表L中元素值最大的结点（假设这样的结点唯一）。void delmaxnode(LinkList *&L) LinkList *p,*pre, *maxp, *maxpre; p=L-next; pre=L; maxp=p; maxpre=pre; while (p!=NULL) if (maxp-datadata) maxp=p; maxpre=pre; pre=p; p=p-next; maxpre-next=maxp-next; free(maxp);2已知一棵完全二叉树的第6层（设根为第1层）有8个叶子结点，则该完全二叉树的结点个数最多是多少。完全二叉树的叶子结点只能在最下两层，对于本题，结点最多的情况是第6层为倒数第二层，即16层构成一个满二叉树，其结点总数为26-1=63。第6层有25=32个结点，其中含8个叶子结点，另外有32-8=24个非叶子结点，它们中的每个结点都有两个孩子结点（均为第7层的叶子结点），计48个叶子结点，这样最多的结点个数=63+48=111。3一个有向图G的邻接表存储如下图所示，要求：（1）给出该图的邻接矩阵存储结构；（2）给出该图的所有强连通分量。4什么是平衡二叉树？输入关键字序列（16，3，7，11），给出构造一棵平衡二叉树的过程。若一棵二叉排序树中每个结点的左右子树的高度最多相差1，则称此二叉树为平衡二叉树。160161307030160161110307-15线性表有顺序表和链表两种存储方式，不同的排序方法适合不同的存储结构。对于常见的内部排序方法，说明哪些更适合于顺序表，哪些更适合于链表？哪些两者都适合？ 更适合于顺序表的排序方法有希尔排序、折半插入排序、快速排序、堆排序和归并排序。更适合于链表的排序方法是基数排序两者都适合的排序方法有直接插入排序、冒泡排序和简单排序。五、算法设计题用Floyd算法计算图中任意两个顶点之间的最短路径。void Floyd(MGraph g) int AMAXVMAXV,pathMAXVMAXV; int i,j,k; for (i=0; ig.n; i+) for (j=0; jg.n; j+) Aij=g.edgesij; pathij=-1; for (k=0; kg.n; k+) for (i=0; ig.n; i+) for (j=0; jAik+Akj) Aij=Aik+Akj; pathij=k;/修改最短路径 Dispath(A,path,g.n); /输出最短路径一、选择题1 研究数据结构就是研究（ ）。A 数据的逻辑结构B 数据的存储结构C 数据的逻辑和存储结构D 数据逻辑结构、存储结构及其数据在运算上的实现2 链表不具有的特点是（ ）。A 可随机访问任一元素B 插入删除不需要移动元素C 不必事先估计存储空间D 所需空间与线性表长度成正比3 设一个栈的输入序列为1，2，3，4，则借助一个栈所得到的输出序列不可能是（ ）。A 1，2，3，4B 2，4，3，1C 3，1，4，2D 3，2，4，14 设计一个判别表达式中左、右括号是否配对出现的算法，采用（ ）数据结构最佳。A 线性表的顺序存储结构B 栈C 线性表的链式存储结构D 队列5 表达式a*(b+c)-d的后缀表达式是（ ）。A abcd*+-B abc+*d-C abc*+d-D -+*abcd6 队列的操作原则是（ ）。A 先进先出B 只能进行插入C 后进先出D 只能进行删除7 判断带头结点的单链表llist为空的条件是（ ）。A llist-link=llistB llist=NULLC llist-link=NULLD llist!=NULL8 一个具有20个结点的完全二叉树，其叶结点个数为（ ）。A 9B 10C 11D 129 下列不属于内部排序的算法是（ ）。A 归并排序B 拓扑排序C 选择排序D 插入排序10 在一棵度为3的树中，度为3的结点数为2，度为2的结点数为1，则叶结点数为（ ）。A 4B 5C 6D 712345678910DACBBACBBC二、填空题第 13 页 共 13 页1 已知二叉树有50个叶子结点，则该二叉树的总结点数至少是 99 。2 在一个长度为n的线性表的第i个元素（1in）之前插入一个元素时，插入函数需向后移动 n-i+1 个元素。3 若频繁地对线性表进行插入与删除操作，该线性表应采用 链式 存储结构。4 若某线性表采用顺序存储结构，每个元素占2个存储单元，首地址为是100，则第5个元素的地址是 108 。5 若结点y是结点x的一棵子树的根，则x称作y的 父结点 。6 一个串中包括的字符个数称作这个串的 长度 。7 一棵树高为h的完全二叉树至少有2h-1个结点，至多有 2h-1 个结点。8 算法的复杂性分析主要从算法的时间复杂性和 空间 复杂性进行考虑。9 数据结构主要根据 逻辑 结构和存储结构进行分类。10 图的遍历分为两种类型：深度优先遍历和 广度 优先遍历。三、算法分析与设计题1 在链表中，若已知指针p，要在指针p所指的结点之后插入数据域值相继为a和b的两个结点，已知指针s指向结点a。写出实现上述插入操作的关键语句。ABDCEFs-next-next=p-next; p-next=s; 2 如图所示的一棵二叉树，写出对此树的先根序列、中根序列和后根序列。先根序列：ABDEFC 中根序列：DEFBAC 后根序列：FEDBCA 3 以5，6，7，8，9，10，15，18，22作为叶结点的权值来构造一棵Huffman树。1004159192633111522910658718154 请设计一个算法，求出循环表中结点的个数。int Countnode(ClinkList clist) int n； PNode p； p=clist-link； n=0； while(p!=clist) n+； p=p-link； return(+n)；一、填空题1设有一个8阶的对称矩阵A, 采用压缩存储方式, 按行优先顺序存储方式。设a11为第一个元素,其存储地址为1,假设每个元素占用1个存储单元,则a64的存储地址为 19 。2若频繁地对线性表进行插入与删除操作，该线性表应采用 链式 存储结构。3算法的5个重要特征是 有穷性 、确定性、可行性、输入和输出。4. 每次从无序子表中取出一个元素，然后把它插入到有序子表的适当位置，则此种排序方法叫做 直接插入 排序。5设二维数组A1.M，1.N（即M行N列）按行优先顺序存储在一维数组B1.M*N中，则二维数组元素Ai,j在一维数组B中的下标为 (i-1)*N+j 。6在序列(2,5,8,11,15,16,22,24,27,35,50)中采用折半查找(二分查找)方法查找元素24，需要进行 4 次元素之间的比较。7一棵树高为h的完全二叉树至少有 2h-1 个结点，至多有 2h-1 个结点。8由权值分别为11,8,6,2,5的叶结点生成一棵Huffman树，它的带权路径长度为 71 。9对关键字序列(52,80,63,44,48,91)一趟快速排序后的结果 (48，44，52，63，80，91) 。二、单项选择题题号12345678910答案DAAACBDBAC题号11121314151617181920答案CAADDCDAAC1. 数据结构是指 。A. 一种数据类型B. 数据的存储结构C. 一组性质相同的数据元素的集合D. 相互之间存在一种或多种特定关系的数据元素的集合2. 以下算法的时间复杂度为 。void fun(int n)int i=1;while (i=n)i+;A. O(n)B. O()C. O(nlog2n)D. O(log2n)3. 在一个长度为n的有序顺序表中删除元素值为x的元素时，在查找元素x时采用二分查找，此时的时间复杂度为 。A. O(n)B. O(nlog2n)C. O(n2)D. O()4. 在一个带头结点的循环单链表L中，删除元素值为x的结点，算法的时间复杂度为 。A. O(n)B. O()C. O(nlog2n)D. O(n2)5. 若一个栈采用数组s0.n-1存放其元素，初始时栈顶指针为n，则以下元素x进栈的正确操作是 。A.top+;stop=x;B.stop=x;top+;C.top-;stop=x;B.stop=x;top-;6. 中缀表达式“2*(3+4)-1”的后缀表达式是 ，其中#表示一个数值的结束。A. 2#3#4#1#*+-B. 2#3#4#+*1#-C. 2#3#4#*+1#-D. -+*2#3#4#1#7. 设环形队列中数组的下标为0N-1，其队头、队尾指针分别为front和rear（front指向队列中队头元素的前一个位置，rear指向队尾元素的位置），则其元素个数为 。A. rear-frontB. rear-front-1C. (rear-front)N+1D. (rear-front+N)N8. 若用一个大小为6的数组来实现环形队列，队头指针front指向队列中队头元素的前一个位置，队尾指针rear指向队尾元素的位置。若当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为 。A. 1和5B. 2和4C. 4和2D. 5和19. 一棵深度为h（h1）的完全二叉树至少有 个结点。A. 2h-1B. 2hC. 2h+1D. 2h-1+110. 一棵含有n个结点的线索二叉树中，其线索个数为 。A. 2nB. n-1C. n+1D. n11. 设一棵哈夫曼树中有1999个结点，该哈夫曼树用于对 个字符进行编码。A. 999B. 998C. 1000D. 100112. 一个含有n个顶点的无向连通图采用邻接矩阵存储，则该矩阵一定是 。A. 对称矩阵B. 非对称矩阵C. 稀疏矩阵D. 稠密矩阵13. 设无向连通图有n个顶点e条边，若满足 ，则图中一定有回路。A. enB. e1）个元素的线性表的运算只有4种：删除第一个元素；删除最后一个元素；在第一个元素前面插入新元素；在最后一个元素的后面插入新元素，则最好使用以下哪种存储结构，并简要说明理由。（1）只有尾结点指针没有头结点指针的循环单链表（2）只有尾结点指针没有头结点指针的非循环双链表（3）只有头结点指针没有尾结点指针的循环双链表（4）既有头结点指针也有尾结点指针的循环单链表答：本题答案为（3），因为实现上述4种运算的时间复杂度均为O(1)。4. 已知一棵度为4的树中，其度为0、1、2、3的结点数分别为14、4、3、2，求该树的结点总数n和度为4的结点个数，并给出推导过程。答：结点总数n=n0+n1+n2+n3+n4，即n=23+n4，又有：度之和=n-1=0n0+1n1+2n2 +3n3+4n4，即n=17+4n4，综合两式得：n4=2，n=25。所以，该树的结点总数为25，度为4的结点个数为2。四、算法设计题1. 假设二叉树b采用二叉链存储结构，设计一个算法void findparent(BTNode *b, ElemType x, BTNode *&p)求指定值为x的结点的双亲结点p。提示：根结点的双亲为NULL；若在b中未找到值为x的结点，p亦为NULL。void findparent(BTNode *b,ElemType x,BTNode *&p) if (b!=NULL) if (b-data=x) p=NULL; else if (b-lchild!=NULL & b-lchild-data=x) p=b; else if (b-rchild!=NULL & b-rchild-data=x) p=b;elsefindparent(b-lchild,x,p); if (p=NULL) findparent(b-rchild,x,p); else p=NULL; 2. 设A和B是两个结点个数分别为m和n的单链表（带头结点），其中元素递增有序。设计一个尽可能高效的算法求A和B的交集，要求不破坏A、B的结点，将交集存放在单链表C中。给出所设计的算法的时间复杂度和空间复杂度。void insertion(LinkList *A,LinkList *B,LinkList *&C) LinkList *p=A-next,*q=B-next,*s,*t; C=(LinkList *)malloc(sizeof(LinkList);t=C;while (p!=NULL & q!=NULL) if (p-data=q-data) s=(LinkList *)malloc(sizeof(LinkList); s-data=p-data; t-next=s;t=s;p=p-next;q=q-next;else if (p-datadata) p=p-next;elseq=q-next;t-next=NULL; 算法的时间复杂度为O(m+n)，空间复杂度为O(MIN(m, n)。