数据结构复习答案2011要点

1、1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.数据结构复习答案 选择填空 下面关于线性表的叙述中，错误的是哪一个？( )A) 线性表采用顺序存储，必须占用一片连续的存储单元。 V B)线性表采用顺序存储，便于进行插入和删除操作。C) 线性表采用链接存储，不必占用一片连续的存储单元。D) 线性表采用链接存储，便于插入和删除操作。若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用 ( )存储方式最节省时间。VA )顺序表B)双链表 C)带头结点的双循环链表D)单循环链表链表不具有的特点是( )。 A )插入、删除不需要移动元素C)不必事先估计

2、存储空间VB)可随机访问任一元素D)所需空间与线性长度成正比5若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为( ) (1=inext=s;s-next=p-next;VB) s-next=p-next;p-next=s;C) p-next=s;p-next=s-next;D) p-next=s-next;p-next=s;设指针变量 p 指向单链表结点VA ) p-next=p-next-nextC) p=p-next-nextA，则删除结点A的后继结点B需要的操作为(B ) p=p-nextD) p-next=p)。() 又称为 FIFO 表； () 又

3、称为 FILO 表。VA )队列B)散列表VC)栈对于栈操作数据的原则是( )。A) 先进先出 VB) 后进先出C) 后进后出D )哈希表D ) 不分顺序用不带头结点的单链表存储队列时， 在进行删除操作时 ()。VA )仅修改队头指针其队头指针指向队头结点，其队尾指针指向队尾结点，B ) 仅修改队尾指针C) 队头、队尾指针都要修改D) 队头、队尾指针都可能要修改假设以数组Am存放循环队列的元素，其头尾指针分别为front和rear,则当前队列中的元素个数为( )。VA )(rear-front+m)%mB )rear-front+1C) (front-rear+m)%mD)(rear-fron

4、t)%m 栈和队列的共同点是( )。A ) 都是先进先出B ) 都是先进后出VC) 只允许在端点处插入和删除元素D) 没有共同点 设栈S和队列Q的初始状态为空，元素 e1, e2, e3, e4,e5和e6依次通过栈S, 个元素出栈 后即进队列Q,若6个兀素出队的序列是 e2, e4, e3,e6,e5,e1则栈S的容量至少应该是()。A) 6B) 4VC) 3 D) 2设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a11为第一元素，其存储16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.地址为 1，每个元素占一个地址空间，则a85

5、 的地址为( )。A) 12V B)33C) 18D) 40由 3 个结点可以构造出多少种不同的二叉树？ ()A) 2B) 3C) 4VD) 5二叉树中第i(i 1)层上的结点数最多有()个。A) 2iB)2iVC) 2i-1D) 2i-1在有 n 个叶子结点的哈夫曼树中，其结点总数为 ()。A)不确定B) 2n C) 2n+1V D) 2n-1一棵二叉树高度为A) 2h若一棵二叉树具有A) 9h,所有结点的度或为 0、或为2,则这棵二叉树最少有()结点。)。VB) 2h-1C) 2h+1D) h+110个度为 2的结点, 5个度为 1 的结点,则度为 0的结点个数是 (V B) 11C) 1

6、5D)不确定树的后根遍历序列等同于该树对应的二叉树的 ()。A ) 先序序列VB)中序序列C) 后序序列D )层序序列在二叉树结点的先序序列,中序序列和后序序列中,所有叶子结点的先后顺序()。A)都不相同V B )完全相同中序和后序相同,而与先序不同网D ) AOE 网( 2 )倍,在一个有向图中,所有顶点的D) 4C)先序和中序相同，而与后序不同D)下列哪一种图的邻接矩阵是对称矩阵？ ()A)有向图VB)无向图C) AOV在一个无向图中,所有顶点的度数之和等于所有边数 入度之和等于所有顶点出度之和的 ( 1 )倍。A) 1/2VB) 2VC) 1一个有 n 个顶点的无向图最多有 ()条边。由

7、 n 个顶点组成的有向图,最多可以有 ( )条边。A) n*n B) 2nVC) n(n-1)VD) n(n-1)/2下列说法不正确的是 ()。A )图的遍历是从给定的源点出发每一个顶点仅被访问一次B )遍历的基本算法有两种：深度遍历和广度遍历V C)图的深度遍历不适用于有向图D )图的深度遍历是一个递归过程 下面哪一方法可以判断出一个有向图是否有环(回路 ) ()。A )深度优先遍历 V B ) 拓扑排序C) 求最短路径 D ) 求关键路径下列算法中, ()算法用来求图中每对顶点之间的最短路径。A ) DijkstraVB ) Floyed C) Prim D ) Kruskal关键路径是事

8、件结点网络中 ()。VA )从源点到汇点的最长路径B)从源点到汇点的最短路径C)最长回路D )最短回路若查找每个记录的概率均等, 则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一个记 录,其平均查找长度 ASL 为()。A) (n-1)/2B)n/2VC)(n+1)/2D) n下面关于二分查找的叙述正确的是() 。A ) 表必须有序,表可以顺序方式存储,也可以链表方式存储B) 表必须有序,而且只能从小到大排列C 表必须有序且表中数据必须是整型,实型或字符型VD ) 表必须有序,且表只能以顺序方式存储32. 折半查找的时间复杂性为（）。A） O（n ）B） 0（n）C） 0（nlogn）

9、V D） O（log n）33. 当采用分快查找时，数据的组织方式为（）。A）数据分成若干块，每块内数据有序（或最小）的数据V B ）数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大 组成索引块C） 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D）数据分成若干块，每块（除最后一块外）中数据个数需相同34. 下面关于哈希（Hash,杂凑）查找的说法正确的是（）。A）哈希函数构造的越复杂越好，因为这样随机性好，冲突小B ）除留余数法是所有哈希函数中最好的V C）不存在特别好与坏的哈希函数，要视情况而定35.36.37.38.39.D）若需在哈希表中删去一个元素

10、，不管用何种方法解决冲突都只要简单的将该元素删去即可 .下面给出的四种排序法中（A）插入B）冒泡.稳定的排序方法是（）A ）直接插入排序和快速排序C）简单选择排序和四路归并排序 .有一组数据（15, 9, 7, 8, 20,为（）（按递增序）VA）下面的B, C, D都不对。C） 20, 15, 8, .设有一个文件有查找法查索引表，A） 8） 4快速排序在最坏情况下的时间复杂性为2A） O（nlog 2n）VB） O（n ）、填空）排序法是不稳定性排序法。C）二路归并V D）堆-1 ,V B）折半插入排序和起泡排序D ）树形选择排序和shell排序乙4）用快速排序的划分方法进行一趟划分后数据

11、的排序B) 9, 7,D) 9, 4,9, 7,-1, 4, 7200个记录，按分块查找法查找记录, 用顺序查找法查块内记录，B） 10） 58, 4, -1 , 7, 15, 207, 8, 7,如分成则平均查找长度为( C)C) 13)O(n)-1 , 15, 2010块，每块20个记录，用二分（）V D） 16D) O(nlogn)1. 一个算法的效率可分为时间 效率和 空间 效率。2. 线性表L= （a1,a2,n用数组表示，假定插入、删除表中任一元素的概率相同，则插入、删除一个元素平均需要移动元素的个数是n/2和 （n-1）/23. 对于一个具有n个结点的单链表，在已知的结点 *p后

12、插入一个新结点的时间复杂度为0（1），在给定值为x的结点后插入一个新结点的时间复杂度为0（n）4. 顺序存储结构是通过元素在计算机内“物理位置相邻”表示元素之间的逻辑关系的，链式存储结构是通过指针 表示元素之间的逻辑关系的。5. 带头结点的双循环链表L为空表的条件是： p-next=head6. 当两个栈共享一存储区时，栈利用一维数组stack（1,n）表示，两栈顶指针为 top1与top2，则当栈1空时，top1为 1 ，栈2空时，top2为 n ，栈满时为 top1+top2=n 7. 顺序栈S用data1） n存储数据，栈顶指针是top,则值为x的元素入栈的操作是*S）top+=x 8.

13、 已知链队列Q的头尾指针分别是f和r ,则将值x入队的操作序列是 p-data=e：p-next=NULL:Q ） r-next=p：Q ） r=p： 9. 稀疏矩阵的存储策略是只存储非零兀素。10.稀疏矩阵的存储方法主要有两个：一个是三元组，另一个是十字链表示法11. 二叉树由 _， 左子树、 右子树三个基本单元组成。12. 一棵有n个结点的满二叉树有 ni=0个度为1的结点、有(n-1)/2, (ni+2n2)个分支(非终端)结点和(n=ng+ni+n2, ng= n?+1), (n+1)/2 个叶子，该满二叉树的深度为Iog2(n+1)。13. 设F是由T1,T2,T3三棵树组成的森林，

14、与F对应的二叉树为 B，已知T1,T2,T3的结点数分别为n1，n2和n3则二叉树B的左子树中有n1-1个结点，右子树中有n2+n3 个结点。14. 线索二叉树的左线索指向其前驱 右线索指向其 后继。15. 设一棵Huffman树有6个叶结点，权值分别为3、4、7、14、15、20,则根节点的权值是63。当 初始记录序列按关键字有序或基本有序时，快速排序算法的时间复杂性为0(n2)。16. 在有n个结点的二叉链表中，空链域的个数为n+1。17. 设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点，有499个度为2的结点，有 1个度为1的结点。18. 若用n表示图中顶点数目，则

15、有n*(n-1)/2条边的无向图成为完全图。n19. 设无向图 G有n个顶点和e条边，每个顶点 Vi的度为di(1=i，则e=1/2送di。i=120. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要n*(n-1) 条弧。21. 在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的度；对于有向图来说等于该顶点的出度。22. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为n 次；当使用监视哨时，若查找失败，则比较关键字的次数为n+1。23. 在顺序表(8,11,15,19,25,26,30,33,42,48,50)中，用二分(折半)法查

16、找关键码值20,需做的关键码比较次数为4。24. 对于长度为255的表，采用分块查找，每块的最佳长度为16。25. 已知二叉排序树的左右子树均不为空，则左子树上所有结点的值均小于它的根结点值，右子树上所有结点的值均大于它的根结点的值。26. 动态查找表和静态查找表的重要区别在于前者包含有插入 和 删除 运算，而后者不包含这两种运算。27. 为了能有效地应用 HASH查找技术，必须解决的两个问题是设计一个好的哈希函数和选择一个处理冲突的方法。比较 和记录28. 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 的 移动 。29. 属于不稳定排序的有希尔、快速、选择、堆排序。30

17、. 快速排序算法的时间复杂度为O(n2)。三、应用题、1.试画出下列稀疏矩阵的三元组表示。jv00180、1318300021300024000034240066o J5366稀疏矩阵+ a *b c / d eNULL3. 写出下列二叉树的前序，中序，后序遍历序列及对应的森林。解答：前序:中序：a + b * c后序：a b c * + d e / -4.试将森林 F= T1,T2,T3,T4 转换为一棵二叉树。126.设一棵树 T 中边的集合为(A , B), (A, C), (A , D), (B , E), (C, F), (C, G)，要求用孩7. 已 知 有 向 图G=(V,E)其

18、 中V=V1,V2,V3,V4,V5,V6,V7E=vV1,V2,vV1,V3,vV2,V5,vV3,V5,vV3,V6,vV4,V6,vV5,V7,vV6,V7,G 的拓扑序列是()。8. 有 7 个顶点(v1,v2,v3,v4,v5,v6,v7)的有向图的邻接矩阵如右图。请回答相关问题:(1)画出该有向图。解答:3v1v4215v22v3v5383v69v75OO253OOOOOOOOOO2OOOO8OOOOOOOO135OOOOOOOOOO5OOOOOOOOOOOOOO39OOOOOOOOOOOO5OOOOOOOOOOOOOO(2) 写出从v1出发的深度优先遍历和广度优先遍历序列。深度优

19、先遍历： V1 V2 V6 V7 V3 V4 V5 广度优先遍历： V1 V2 V3 V4V6 V5 V79.已知如图所示的有向图，请给出该图的(1) 每个顶点的入/出度;(2) 邻接矩阵；(3) 邻接表；顶点123456入度321122出度022313OOOOOOOOOOOOOO11OOOO1OOOO11OOOO1111邻接矩阵01A12-0-3A23-1-5A34-2-5-6A45-0A56-0-1-4A邻接表01-12-2 3-3 4-4 51 -42 -53 A1A3-556-2-3逆邻接表10.设无向图G (所下图所示)，要求给出该图的深度优先和广度优先遍历的序列，找出下面网络的最小

20、生成树。解答：深度优先：A B D F C E G广度优先： A B D C E F G(4) 逆邻接表。11.分别说明Huffman算法、Dijkstra算法、Prim算法、Kruskal算法的功能。 解答：Huffman算法：最优二叉树，树的带权路径最短。Dijkstra算法：求单源最短路径Prim算法：求最小生成树Kruskal算法：求最小生成树12.已知图G如图所示。（1）画出图G的邻接表；（2）画出从顶点1出发的深度优先生成树和广度优先生成树；（3）写出图G的拓扑排序列；解答：（1）1123A24A345A45A556A66A7A13. 已知AOE网如下，试求其关键路径。要求写出计算

21、过程。a2=3解答:123456ve0438710vl044891014. 设一组记录的关键字为4，5，7，2，1，3, 6，请回答相关问题：（1）按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树， 并求出在等概率情况下查找成功的平均查找长度。（2） 按表中元素的顺序进行插入生成一棵AVL树，画出该树。并求出在等概率情况下查找成功 的平均查找长度。进行散列存设 Hash15. 假定一个线性表为 L= (18, 75, 60, 43, 54, 90, 46, 31, 58, 73, 15, 34) 储，采用的Hash函数为H( K) =K mod 13 ,当发生冲突时

22、用线性探测法处理冲突, 表的表长为13,试构造Hash表，并求出平均查找长度。解答：0123456789101112345415431831466058757390*2+4212=22/1211211414116. 用快速排序方法对下列整数序列进行排序，写出中间及最后结果。89,27,52,90,15,28,100,72解答：一趟二趟17解答:三趟：15 ,27,52, 287289100, 90四趟：1527 ,52,287289100, 90五趟：152728, 527289100, 90六趟：15272852728990, 100.序列40 ,38, 60,95, 76,10,25, 5

23、0, 99是堆吗？若不是，创建一个堆。100, 9089 72,27,52, 28,15, 89,100, 9072 15,27,52, 28, 7289四、算法设计题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