数据结构复习答案.doc

数据结构复习答案一、选择填空1. 下面关于线性表的叙述中，错误的是哪一个？（ ）A）线性表采用顺序存储，必须占用一片连续的存储单元。B）线性表采用顺序存储，便于进行插入和删除操作。C）线性表采用链接存储，不必占用一片连续的存储单元。D）线性表采用链接存储，便于插入和删除操作。2. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。A）顺序表 B）双链表 C）带头结点的双循环链表 D）单循环链表3. 链表不具有的特点是（ ）。 A）插入、删除不需要移动元素 B）可随机访问任一元素C）不必事先估计存储空间 D）所需空间与线性长度成正比4. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1=inext=s;s-next=p-next; B） s-next=p-next;p-next=s;C）p-next=s;p-next=s-next; D） p-next=s-next;p-next=s;8. 设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为( )。A）p-next=p-next-nextB） p=p-nextC）p=p-next-nextD） p-next=p9. ( )又称为FIFO表；( )又称为FILO表。A）队列 B）散列表 C）栈 D）哈希表10. 对于栈操作数据的原则是（ ）。A） 先进先出B） 后进先出 C） 后进后出 D） 不分顺序11. 用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时( )。A）仅修改队头指针 B） 仅修改队尾指针C） 队头、队尾指针都要修改 D） 队头、队尾指针都可能要修改12. 假设以数组Am存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。A）(rear-front+m)%m B）rear-front+1 C）(front-rear+m)%m D）(rear-front)%m13. 栈和队列的共同点是（ ）。A） 都是先进先出 B） 都是先进后出C） 只允许在端点处插入和删除元素 D） 没有共同点14. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。A） 6 B） 4 C） 3 D） 215. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。A） 12 B） 33 C） 18 D） 4016. 由3 个结点可以构造出多少种不同的二叉树？( )A）2 B）3 C）4 D）517. 二叉树中第i(i1)层上的结点数最多有( )个。A） 2iB） 2iC） 2i-1D） 2i-118. 在有n个叶子结点的哈夫曼树中，其结点总数为( )。A）不确定 B）2n C）2n+1 D）2n-1 19. 一棵二叉树高度为h，所有结点的度或为0、或为2，则这棵二叉树最少有( )结点。A）2h B）2h-1 C）2h+1 D）h+120. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( )。A）9 B）11 C）15 D）不确定21. 树的后根遍历序列等同于该树对应的二叉树的( )。A） 先序序列B） 中序序列 C） 后序序列D）层序序列22. 在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序( )。A）都不相同B）完全相同 C）先序和中序相同，而与后序不同 D）中序和后序相同，而与先序不同23. 下列哪一种图的邻接矩阵是对称矩阵？( ) A）有向图B）无向图 C）AOV网 D）AOE网24. 在一个无向图中，所有顶点的度数之和等于所有边数(2 )倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的(1 )倍。A）1/2 B）2 C）1 D）425. 一个有n个顶点的无向图最多有( )条边。由n个顶点组成的有向图，最多可以有( )条边。A）n*n B）2n C）n(n-1)D）n(n-1)/226. 下列说法不正确的是( )。A）图的遍历是从给定的源点出发每一个顶点仅被访问一次 B）遍历的基本算法有两种：深度遍历和广度遍历 C）图的深度遍历不适用于有向图 D）图的深度遍历是一个递归过程27. 下面哪一方法可以判断出一个有向图是否有环(回路) ( )。 A）深度优先遍历 B） 拓扑排序 C） 求最短路径 D） 求关键路径 28. 下列算法中，( )算法用来求图中每对顶点之间的最短路径。A）DijkstraB）FloyedC）PrimD）Kruskal29. 关键路径是事件结点网络中( )。A）从源点到汇点的最长路径 B）从源点到汇点的最短路径C）最长回路 D）最短回路30. 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。A） (n-1)/2 B） n/2 C） (n+1)/2 D） n31. 下面关于二分查找的叙述正确的是 ( ) 。A） 表必须有序，表可以顺序方式存储，也可以链表方式存储 B） 表必须有序，而且只能从小到大排列C 表必须有序且表中数据必须是整型，实型或字符型 D） 表必须有序，且表只能以顺序方式存储32. 折半查找的时间复杂性为( ) 。A） O(n2) B） O(n) C） O(nlogn) D）O(logn)33. 当采用分快查找时，数据的组织方式为 ( ) 。A）数据分成若干块，每块内数据有序B）数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C） 数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D） 数据分成若干块，每块(除最后一块外)中数据个数需相同 34. 下面关于哈希(Hash，杂凑)查找的说法正确的是( )。A）哈希函数构造的越复杂越好，因为这样随机性好，冲突小B）除留余数法是所有哈希函数中最好的C）不存在特别好与坏的哈希函数，要视情况而定D）若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可 35. 下面给出的四种排序法中( )排序法是不稳定性排序法。A） 插入 B） 冒泡 C） 二路归并D） 堆36. 稳定的排序方法是( ) 。A）直接插入排序和快速排序 B）折半插入排序和起泡排序C）简单选择排序和四路归并排序 D）树形选择排序和shell排序 37. 有一组数据(15，9，7，8，20，-1，7，4) 用快速排序的划分方法进行一趟划分后数据的排序为 ( )(按递增序)。A）下面的B，C，D都不对。 B）9，7，8，4，-1，7，15，20C）20，15，8，9，7，-1，4，7 D）9，4，7，8，7，-1，15，2038. 设有一个文件有200个记录，按分块查找法查找记录，如分成10块，每块20个记录，用二分查找法查索引表，用顺序查找法查块内记录，则平均查找长度为( )。A）8）4B）10）5 C）13）4D）1639. 快速排序在最坏情况下的时间复杂性为( )。A）O(nlog2n)B）O(n2) C）O(n)D）O(nlogn)二、填空1. 一个算法的效率可分为 时间 效率和 空间 效率。2. 线性表L=（a1,a2,an）用数组表示，假定插入、删除表中任一元素的概率相同，则插入、删除一个元素平均需要移动元素的个数是 n/2 和 (n-1)/2 。3. 对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为 O(1) ，在给定值为x的结点后插入一个新结点的时间复杂度为 O(n) 。4. 顺序存储结构是通过 元素在计算机内“物理位置相邻” 表示元素之间的逻辑关系的，链式存储结构是通过 指针 表示元素之间的逻辑关系的。5. 带头结点的双循环链表L为空表的条件是： p-next=head 。6. 当两个栈共享一存储区时，栈利用一维数组stack(1,n)表示，两栈顶指针为top1与top2，则当栈1空时，top1为 1 ，栈2空时 ，top2为 n ，栈满时为 top1+top2=n 。7. 顺序栈S用data1）n存储数据，栈顶指针是top，则值为x的元素入栈的操作是 *S）top+=x 。8. 已知链队列Q的头尾指针分别是f和r，则将值x入队的操作序列是 p-data=e;p-next=NULL;Q）r-next=p;Q）r=p; 。9. 稀疏矩阵的存储策略是只存储 非零 元素。10. 稀疏矩阵的存储方法主要有两个：一个是 三元组 ，另一个是十字链表示法。11. 二叉树由 根 ， 左子树 、 右子树 三个基本单元组成。12. 一棵有n个结点的满二叉树有 n1=0 个度为1的结点、有 (n-1)/2, (n1+2n2)个分支 (非终端)结点和 (n=n0+n1+n2, n0= n2+1), (n+1)/2 个叶子，该满二叉树的深度为log2(n+1) 。13. 设F是由T1,T2,T3三棵树组成的森林，与F对应的二叉树为B，已知T1,T2,T3的结点数分别为n1，n2和n3则二叉树B的左子树中有 n1-1 个结点，右子树中有 n2+n3 个结点。14. 线索二叉树的左线索指向其 前驱 右线索指向其 后继 。15. 设一棵Huffman树有6个叶结点，权值分别为3、4、7、14、15、20，则根节点的权值是 63 。当 初始记录序列按关键字有序或基本有序 时，快速排序算法的时间复杂性为O(n2)。16. 在有n个结点的二叉链表中，空链域的个数为 n+1 。17. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个 度为2的结点，有 1 个度为1的结点。18. 若用n表示图中顶点数目，则有 n*(n-1)/2 条边的无向图成为完全图。19. 设无向图 G 有n 个顶点和e 条边，每个顶点Vi 的度为di(1=i=n，则e=。20. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要 n*(n-1) 条弧。 21. 在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的 度 ；对于有向图来说等于该顶点的 出度 。22. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为 n 次；当使用监视哨时，若查找失败，则比较关键字的次数为 n+1 。23. 在顺序表(8,11,15,19,25,26,30,33,42,48,50)中，用二分(折半)法查找关键码值20，需做的关键码比较次数为 4 。24. 对于长度为255的表，采用分块查找，每块的最佳长度为 16 。25. 已知二叉排序树的左右子树均不为空，则 左子树 上所有结点的值均小于它的根结点值， 右子树 上所有结点的值均大于它的根结点的值。26. 动态查找表和静态查找表的重要区别在于前者包含有 插入 和 删除 运算，而后者不包含这两种运算。27. 为了能有效地应用HASH查找技术，必须解决的两个问题是 设计一个好的哈希函数 和 选择一个处理冲突的方法 。28. 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 比较 和记录的 移动 。29. 属于不稳定排序的有 希尔、快速、选择、堆排序 。30. 快速排序算法的时间复杂度为 O(n2) 。ijv131821334245366三、应用题1. 试画出下列稀疏矩阵的三元组表示。 稀疏矩阵2. 二叉树有哪几种基本形态? 画图说明之。AAABCBCA解答：5种。NULL-+/a*debc3. 写出下列二叉树的前序，中序，后序遍历序列及对应的森林。+cab*/de解答：前序：- + a * b c / d e中序：a + b * c - d / e后序：a b c * + d e / -4. 试将森林 F= T1,T2,T3,T4 转换为一棵二叉树。FDGEHKJCBIALMNOPQ T1 T2 T3 T4解答：5. 已知叶子结点值2，3，5，6，9，11，构造哈夫曼树，计算其带权路径长度。1055236911211536解答：L=4*2+3+3*2=176. 设一棵树T中边的集合为(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。ABDEGFCABCEGFD解答：7. 已知有向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=,G的拓扑序列是( )。2532813553958. 有7个顶点（v1,v2,v3,v4,v5,v6,v7）的有向图的邻接矩阵如右图。请回答相关问题：v1v2v4v6v3v7v5253821335395（1） 画出该有向图。解答：（2） 写出从v1出发的深度优先遍历和广度优先遍历序列。深度优先遍历：V1 V2 V6 V7 V3 V4 V5广度优先遍历：V1 V2 V3 V4V6 V5 V79. 已知如图所示的有向图，请给出该图的:顶点123456入度321122出度022313（1） 每个顶点的入/出度；（2） 邻接矩阵；（3） 邻接表；11111111111邻接矩阵（4） 逆邻接表。0112-0-323-1-534-2-5-645-056-0-1-4邻接表01-1-4-512-2-523-334-1453-556-2-3逆邻接表 10. ABEDCFG315554设无向图G（所下图所示），要求给出该图的深度优先和广度优先遍历的序列，找出下面网络的最小生成树。解答：深度优先:：A B D F C E G 广度优先： A B D C E F G11. 分别说明Huffman算法、Dijkstra算法、Prim算法、Kruskal算法的功能。解答：Huffman算法：最优二叉树，树的带权路径最短。Dijkstra算法：求单源最短路径Prim算法：求最小生成树Kruskal算法：求最小生成树12. 已知图G如图所示。（1） 画出图G的邻接表；（2） 画出从顶点1出发的深度优先生成树和广度优先生成树；（3） 写出图G的拓扑排序列；解答：（1）0112312423453451245763455656667（2）（3）1，2，3，4，5，6，713. 已知AOE网如下，试求其关键路径。要求写出计算过程。解答：123456ve0438710vl044891014. 设一组记录的关键字为4，5，7，2，1，3，6，请回答相关问题：（1）按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求出在等概率情况下查找成功的平均查找长度。（2）按表中元素的顺序进行插入生成一棵AVL树，画出该树。并求出在等概率情况下查找成功的平均查找长度。解答：4251367（1） ASL=(1+2*2+3*3+4)/12=18/74261357（2） ASL=(1+2*2+3*4)/12=17/7 15. 假定一个线性表为L=（18，75，60，43，54，90，46，31，58，73，15，34）进行散列存储，采用的Hash函数为H（K）=K mod 13 ，当发生冲突时用线性探测法处理冲突，设Hash表的表长为13，试构造Hash表，并求出平均查找长度。解答：0123456789101112345415431831466058757390612112114141ASL=(7+2*2+4*2+6)/12=25/1216. 用快速排序方法对下列整数序列进行排序，写出中间及最后结果。89,27,52,90,15,28,100,72解答：一趟：89 72,27,52, 28,15, 89,100, 90二趟：72 15,27,52, 28, 72 89 100, 90三趟：15 ,27,52, 28 72 89 100, 90四趟：15 27 ,52, 28 72 89 100, 90五趟：15 27 28, 52 72 89 100, 90六趟：15 27 28 52 72 89 90, 10017. 序列40，38，60，95，76，10，25，50，99是堆吗？若不是，创建一个堆。403860957610255099解答：四、算法设计题1. 已知L为带头结点的单链表，设计一个算法计算数据域为x的结点个数。int count(LinkList La,ElemType x) /计数x出现的次数LinkList p=La-next; /p为工作指针int n=0;while(p)if(p-data =x) n+;p=p-next ;return n;2. 设L为有序顺序表，试编写一个算法删除L中的重复元素。要求不要另开辟数据存储空间。例如：L=（1，1，2，4，4，9，9，9），执行算法后L=（1，2，4，9）int delduplicate(int a,int n)int i,j,k,count;i=0;while (in)j=i+1;count=0;while (jn & aj=ai) j+;count+;if (count!=0)for(k=j;kn;k+)ak-count=ak;n=n-count;i+;return n;3. 假设一个人算术表达式包含圆括弧，编写一个判别表达式中括弧是否正确匹配的算法。Status matching(SqStack S,string exp)int state = 1;int i=0;SElemType e;while(ilchild );depthRight= Depth( T-rchild );depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;5. 编写算法,求二叉树中度为2结点个数。void Countdu2 (BiTree &T, int &count) /统计二叉树中度为2结点的个数 if ( T ) if (T-lchild)& (T-rchild) count+; / 对度为2的结点计数 Countdu2( T-lchild, count); Countdu2( T-rchild, count); / if / Countdu26. 编写算法,求二叉树中叶结点个数。/统计二叉树中叶子结点的个数void CountLeaf (BiTree &T, int &count)if ( T ) if (!T-lchild)& (!T-rchild) count+; / 对叶子结点计数 CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeaf12