《2013年-数据结构-复习题》由会员分享，可在线阅读，更多相关《2013年-数据结构-复习题（9页珍藏版）》请在金锄头文库上搜索。
1、第一部分：数据结构线性结构(顺序表、链表、栈、队列、数组、串)考点：1、时间复杂度2、数据的逻辑结构与存储结构相关知识分类、与存储结构之间的关系3、顺序表的知识特点4、链表的知识编程求单链表中结点的个数、插入、删除。5、栈与队列知识特点、循环队列、基本术语、链队列6、数组与矩阵求元素的地址、稀疏矩阵行优先存储:下标从1开始:Loc(Ai,j)=Loc(A1,1)+(i-1)*n+j-1*bi,j1,1下标从0开始:Loc(Ai,j)=Loc(A0,0)+(i*n+j)*b列优先存储:i,j0,0下标从1开始:Loc(Ai,j)=Loc(A1,1)+(j-1)*m+i-1*bi,j1,1下标从0
2、开始:Loc(Ai,j)=Loc(A0,0)+(j*m+i)*b1. 设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中个数据元素；删除第i个位置上的数据元素需要移动表中个元素。2. 数据的逻辑结构通常有集合、线性结构、和四类结构。3. 若进栈序列为a、b、c，且进栈和出栈可以穿插进行，则可能出现个不同的出栈序列。4. 在栈结构中，允许插入的一端称为；在队列结构中，允许删除的一端称为。5. 下列程序段的时间复杂度为s=0;for(i=1;in;i+)for(j=1;jnext=NULLC、head!=NULLD、head-next=head7. 栈是一种操作受限的线性结构
3、，其操作的主要特点是()A、先进先出B、后进先出C、进优于出D、出优于进8. 假设以数组An存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为:9. 二维数组A45按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A00的存储地址为1000，则数组元素A32的存储地址为.10设某数据结构的二元组形式表示为A=(D，R)，D=01，02，03，04，05，06，07，08，09，R=r，r=，则数据结构A是()。(A) 线性结构(B)树型结构(C)物理结构(D)图型结构11下面关于
4、线性表的叙述错误的是()。(A) 线性表采用顺序存储必须占用一片连续的存储空间(B) 线性表采用链式存储不必占用一片连续的存储空间（C）线性表采用链式存储便于插入和删除操作的实现（D）线性表采用顺序存储便于插入和删除操作的实现12. 通常从四个方面评价算法的质量：、和。11-15为判断题:11. 顺序存储方式的优点是存储效率高，且插入元素和删除元素效率高。12. 对于单循环链表，从表中任一结点出发都能扫描表中全部结点。13. 栈是一种对进栈、出栈操作总次数做了限制的线性表。14. 无论是顺序队列还是链队列，插入和删除元素运算的时间复杂度都是O（1）。15. 稀疏矩阵的特点是矩阵中元素较少。第二
5、部分：数据结构非线性结构（树与二叉树、图）考点：1、二叉树的基本术语和性质应用2、二叉树的遍历先序、中序、后序3、完全二叉树和满二叉树4、二叉树与树之间的转换、二叉树与森林之间的转换5、哈夫曼树构造哈夫曼树、WL、哈夫曼编码6、采用二叉链表存储结构，实现二叉树递归编程遍历、求二叉树总结点数、求二叉树叶子结点数、求二叉树的深度7、图的基本术语8、图的存储结构邻接矩阵表示法、邻接链表表示法9、图的遍历深度优先搜索遍历（DFS）、广度优先搜索遍历（BFS）10、图的应用最小生成树（普里姆算法）、拓扑排序1深度为k的二叉树至多有个结点，最少有个结点。2. 设哈夫曼树中共有99个结点，则该树中有个叶子结
6、点；若采用二叉链表作为存储结构，则该树中有个空指针域。3. 设无向图对应的邻接矩阵为A,则A中第i行上非0元素的个数第i列上非0元素的个数（填等于，大于或小于）。4. 二叉树就是度为2的树。5. 只要知道完全二叉树中结点的先序序列，就可以唯一确定它的逻辑结构。6. 将一棵树转化成二叉树后，该二叉树根结点没有左子树。7. 在有向图中，各顶点的入度之和等于各顶点的出度之和。8. 强连通图不能进行拓扑排序。9. 高度为5的完全二叉树中含有的结点数至少为.10. 一棵完全二叉树上有1001个结点，其叶子结点的个数是.11. 在高度为h的完全二叉树中，（）A、度为0的结点都在第h层上B、第i（1=i=h
7、）层上结点都是度为2的结点C、第i（1=i=h-1）层上有2i-个结点D、不存在度为1的结点12. 有n个结点的无向图的边数最多为（）A、n+1B、n(n-1)/2C、n(n+1)D、2n#13. 如图所示有向图的一个拓扑序列是（）A、ABCDEFB、FCBEADC、FEDCBAD、DAEBCFo1r00114. 设图的邻接矩阵为W，则该图为()A、有向图B、无向图C、强连通图D、完全图15. 已知一棵二叉树的前序序列是ABCDEFG，中序序列是CBDAEGF。请画出该二叉树，并给出该二叉树的后序序列。16. 设无向图G(如下图所示)，给出该图的最小生成树上边的集合，并计算最小生成树各边上的权
8、值之和。10，15，18，22作为叶子结点的权值构造一棵哈夫曼树，17. 以数据5，6，7，8，9并计算出其带权路径长度。18、以二叉链表为存储结构：(1) 写出求二叉树总结点数的算法。(2) 写出求二叉树的深度的算法。(3) 设计一个求结点x在二叉树中的双亲结点算法.要求：给出二叉链表的C语言描述；采用递归的思想实现该算法。19、给出某个图的邻接矩阵或邻接链表，请画出该图，并给出DFS和BFS.20若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是()。(A)树中没有度为2的结点(B)树中只有一个根结点(C) 树中非叶结点均只有左子树(D) 树中非叶结点均只有右子树21设某
9、强连通图中有n个顶点，则该强连通图中至少有()条边。(A)n(n-1)(B)n+1(C)n(D)n(n+1)22设某有向图中有n个顶点，则该有向图对应的邻接表中有()个表头结点。(A)n-1(B)n(C)n+1(D)2n-123. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有个指针域，其中有个指针域是存放了地址，有个指针是空指针。24. 深度为k的完全二叉树中最少有个结点。25对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有个和个。第三部分：数据结构查找与内部排序考点：1、二分查找(折半
10、查找)2、哈希查找哈希函数:除留余数法解决冲突方法:线性探测法、二次探测法3、二叉排序树1. 对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为.A、39/15B、49/15C、50/15D、55/152. 已知一个散列表如图所示，其散列函数为H(key)=key%ll,采用二次探测法处理冲突，则下一个插入的关键字49的地址为()II|必|3苦阳|厂U.30I234567B910D.9題却图5. 根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为。9.下面程序段的功能是实现二分查找算法，请在下划线处填上正
11、确的语句。structrecordintkey;intothers;intbisearch(structrecordr,intk)intlow=0,mid,high=n-1;while(low=high)if(rmid.key=k)return(mid+1);elseif()high=mid-1;elselow=mid+1;return(0);7. 设一组初始记录关键字序列为(15，17，18，22，35，51，60)，要求使用二分查找时，计算出成功查找时的平均查找长度。内部排序直接插入排序冒泡排序简单选择排序快速排序堆排序归并排序3. 数据表A中有10000个元素，如果仅要求选出其中最大的1
12、0个元素，则采用()方法最节省时间。A、堆排序B、冒泡排序C、快速排序D、简单选择排序4. 设有n个无序的记录关键字，则直接插入排序的时间复杂度为。12. 设初始记录关键字序列为(K,K,，K)，则用筛选法思想建堆必须从第个元素开始进行筛选。12n13. 设一组初始记录关键字序列为(20，18，22，16，30，19)，则以20为中轴的一趟快速排序结果为15.在快速排序、堆排序、归并排序中，排序是稳定的。9设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为()。(A)10，15，14，18，20，36，40，21(B)
13、 10，15，14，18，20，40，36，21(C) 10，15，14，20，18，40，36，2l(D) 15，10，14，18，20，36，40，2117设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为()。(A)2，3，5，8，6(B)3，2，5，8，6(C)3，2，5，6，8(D)2，3，6，5，820下列四种排序中()的空间复杂度最大。(D)归并排序(A)插入排序(B)冒泡排序(C)堆排序6. 设一组初始记录关键字序列为(49,38,65,97,76,13,27)，要求写出2-路归并排序各趟排序序列。8下面程序段的功能是实现冒泡排序
14、算法，请在下划线处填上正确的语句。voidbubble(intrn)for(i=1;i=n-1;i+);j+)；rj=temp;exchange=l;for(exchange=0,j=0;jrj+1)temp=rj+l;if(exchange=0)return；第9章查找考点：1、二分查找(折半查找)比较式查找2、哈希查找计算式查找又称为散列查找构造哈希函数:除留余数法最常见的方法H(key)=key%p,p取小于等于表长的素数冲突：给出多个查找的值，经过哈希函数计算后得到相同的地址，这种情况称为冲突。解决冲突方法:线性探测法、二次探测法(1) 线性探测法D=(H(key)+i)%m,m代表表长，i=l,2,3,4,.(2) 二次探测法D=(H(key)+i)%m,m代表表长，i=2,-2,2”2,-2”2,3、二叉排序树(1) 定义：若二叉树满足：左子树上结点的值小于根结点的值小于右子树上的结点的值，且左子树和右子树同样满足上述规则。(2) 特点：若对二叉排序树进行中序遍历，则结果一定
