实习四等多个文件2015总复习

1数据结构2015年秋季授课教师：张剑波授课班级：111141-2班2课程总复习

考试安排各部分比重分布各章重要知识点题型3考试安排考试时间：2015年12月20日，19:00-21:00考试地点：教一楼204、206、2074考前答疑安排

安排在数据结构专业实习的时间段2015年12月17周四下午时间：2:00—5:45地点：信息楼805可以增加其他答疑时间（学委联系）5课程各部分内容比重分布内容比例涵盖章节时间复杂度、线性表±15%第1、2章栈和队列±15%第3章数组和矩阵±10%第4章二叉树、堆、Huffman±20%第5章散列、字典±5%第6章图±20%第8章搜索结构及排序算法±15%第7、9章6考试题型及大致分值分布大致题型大致分值一、单选题30分15*2二、解答题40——50分,6题三、算法分析与设计20——30分，3题7成绩评定考勤+上机实习期末考试30-40%60-70%8重要知识点回顾9Chapter1程序性能-重要知识点本章重要知识点：算法的性能分析与度量程序（算法）的时间复杂性操作计数：识别关键操作10Chapter1程序性能-重要复习题本章重要复习题P381.10P391.12、1.1311示例计算机执行下面的语句时，语句s的执行次数为

。

for(i=1;i<n-1;i++)for(j=1;j<=i;j++)s;12Chapter2线性表-重要知识点本章重要知识点什么是线性结构公式化描述与链表描述的含义线性表的公式化描述——顺序表特性：操作：插入、删除、搜索线性表的链表描述——链表（重点）单链表双向链表、循环链表操作：插入、删除、搜索、合并、拆分、逆置等13

Chapter2线性表本章重要算法（程序）顺序表类：P46-47顺序表的基本操作：P47-49，reSize单链表类：P60-61单链表的基本操作：P57-58，P61-66循环链表类：P67-68，约瑟夫环问题双向链表类：P70双向链表的基本操作：P71-7314Chapter2线性表1、顺序存储与链式存储的比较与区别2、区别带表头节点和不带表头节点的链表结构；为了避免把空链表作为特殊情况处理使用头节点后，每个链表至少包含一个节点（头节点）3、各种链表结构的区别4、链表合并、拆分、逆置等算法15Chapter2线性表-重要复习题本章重要复习题P832.2P842.4线性表的逆置：2.62.17P862.15、2.2216示例在双向链表存储结构中，删除p所指的结点时须修改指针的操作为（）。A．p->llink->rlink=p->rlink;p->rlink->llink=p->llink;B．p->llink=p->llink->llink;p->llink->rlink=p;C．p->rlink->llink=p;p->rlink=p->rlink->rlinkD．p->rlink=p->llink->llink;p->llink=p->rlink->rlink;A17Chapter3栈和队列-重要知识点

栈重要知识点栈结构的特性：LIFO栈的公式化描述——顺序栈（重点）栈的链式描述——链栈描述操作：入栈、出栈、取栈顶元素、栈空、栈满等栈的应用括号匹配表达式求值栈与递归：递归工作栈18Chapter3栈和队列-重要算法

栈重要算法顺序栈定义及操作：P89-91链栈定义及操作：P93-94括号匹配算法：P95表达式求值：P95-100中缀表达式转为后缀表达式利用后缀表达式计算值栈与递归：P105-109用栈实现递归转为非递归用迭代法实现递归19Chapter3栈和队列-重要知识点

队列重要知识点队列结构的特性：FIFO队列的公式化描述——循环队列（重点）队列的链式描述——链队列描述操作：入队列、出队列、取队头元素、队空、队满等队列的应用：杨辉三角优先队列的概念20Chapter3栈和队列-重要算法队列重要算法循环队列及操作：P116-117链队列及操作：118-119杨辉三角：P121优先队列的存储与表示：P124-12621Chapter3栈和队列-重要复习题本章重要复习题P1323.7、3.16P1333.22，rear和length22示例1、用I表示入栈操作，O表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的I和O操作串为（）。

A．IIOOIIOOB．IOIOIIOOC．IOIIOIOOD．IOIIOOIOC2、算术表达式a+b*（c+d/e）转为后缀表达式后为（）。A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++B23示例若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？（）A．1和5B．2和4C．4和2D．5和1Brear=(rear+1)%MaxSize;front=(front+1)%MaxSize;24Chapter4数组和矩阵（串不考）本章重要知识点二维数组的一维存储（行优先、列优先）计算元素位置特殊矩阵的压缩存储：P138-141对角、三对角（带状）、上（下）三角、对阵矩阵注意下标的起止值行、列、对角线优先映射公式稀疏矩阵的压缩存储三元组顺序表转置操作（P145）25Chapter4数组和矩阵-重要复习题本章重要复习题P1834.1、4.226示例数组A[0..5,0..6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是（）。A．1175B．1180C．1205D．1210A设有二维数组a[m][n]行优先：LOC(i,j)=LOC(0,0)+(i*n+j)*l列优先：LOC(i,j)=LOC(0,0)+(j*m+i)*l

27Chapter5二叉树和树、Huffman、堆-重要知识点本章重要知识点非线性结构树结构的特性二叉树、满二叉树、完全二叉树的定义二叉树的特性及证明方法（注意特性P190）二叉树的顺序存储二叉树的链式存储——二叉链表二叉树的遍历及遍历的应用树的二叉链表表示形式28Chapter5二叉树和树、Huffman、堆-重要知识点堆堆的定义、判断堆的、初始化及插入、删除算法堆排序Huffman树及Huffman算法Huffman树的定义及性质带权路径长度（WPL）Huffman算法Huffman编码：P244-24529Chapter5二叉树和树、Huffman、堆-重要程序本章重要程序二叉链表类：P194-195二叉树的操作：P196二叉树遍历的应用(高度、交换）：P198-207前序和中序或中序和后序唯一确定一棵二叉树表达式二叉树：前缀、中缀、后缀树的二叉树描述左孩子-右兄弟表示法：P222转换方法30Chapter5二叉树和树、Huffman、堆-重要程序最小（大）堆类：P236最小（大）堆的插入、删除及复杂度分析：P238-239初始化非空最大堆：P237堆排序及性能分析Huffman树的建立：P242-24331Chapter5二叉树和树、Huffman、堆-重要复习题本章重要复习题性质：P2465.6、5.7、5.9堆：P2475.16树与二叉树：P2485.17、5.18Huffman：P2485.19、5.20应用：P2485.235.26321、一棵高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有

成立。A、n=h+mB、h+m=2nC、m=h-1D、n=2m-1

D示例332、已知一棵完全二叉树中共有768结点，则该树中共有_____个叶子结点。384

3、已知一棵完全二叉树中共有767结点，则该树中共有_____个叶子结点。（软考真题）384完全二叉树中度为1的节点数只有两种可能：要么为0个（奇数个结点），要么为1个（偶数个结点）。34

4、设节点x和y是二叉树中任意两个节点，在该二叉树的前序遍历序列中x在y之前，而在后序遍历序列中x在y之后，则x和y的关系是：A、x是y的左兄弟B、x是y的右兄弟C、x是y的祖先D、x是y的后裔C355、已知某二叉树的中序遍历序列是dgbaechf，后序遍历序列是gdbehfca，则其前序遍历序列是（）。

A．abdgcefhB．agdbecfh C．abdgechfD．adbgcefh6、用一维数组存放的一棵完全二叉树：ABCDEFGHI，写出中序遍历该二叉树时访问节点的顺序

。AHDIBEAFCG36堆及Huffman的示例1、初始关键码序列为{E，D，X，K，H，L，M，C，P}，用筛选法所建的最大堆得到的序列是

。2、给定14个字母，假设它们的权值都相等。采用Huffman编码，则每个字母的平均编码长度是

。XPMKHLECD54/14（或3.857）373、下列序列不是堆的是

。A、（100，85，98，77，80，60，82，40，20，10，66）B、（100，98，85，82，80，77，66，60，40，20，10）C、（10，20，40，60，66，77，80，82，85，98，100）D、（100，85，40，77，80，60，66，98，82，10，20）D38

4、有组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始最大堆为：A、79，46，56，38，40，80B、84，79，56，38，40，46C、84，79，56，46，40，38D、84，56，79，40，46，38B39

5、在数据压缩编码应用中，Huffman算法可以用来构造具有

（1）的二叉树，这是一种采用了（2）算法的算法。（1）A、前缀码B、最优前缀码C、后缀码D、最优后缀码（2）A、贪心B、分治C、递推D、回溯解答：（1）B（2）A406、假设用于通信的电文仅由a，b，c，d，e，f，g，h，8个字母组成，各字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。（1）试为这8个字母设计Huffman编码（需画出相应的Huffman树）。（2）使用0-7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。（提示：试从两种编码的带权路径长度上进行比较说明）WPLHF=2.61，WPLEQ=3提高通信信道的利用率，提高报文发送速度或/和节省存储空间。41Chapter6集合、字典散列-重要知识点

本章重要知识点字典结构的特点散列（重点）散列函数-除留余数法：f(k)=k%D什么是冲突？冲突解决方案：开散列散列表搜索：P284-287Hi（k）=（H（k）+di）modm（i=1,2,...k（k≤m-1））42Chapter6集合、字典散列-重要复习题本章重要复习题P2956.9（1）43示例设有一组关键码{19，01，23，14，55，20，84，27，68，11，10，77}，采用散列函数H（key）=key%13，处理冲突的方法是线性探测再散列的方法（即dj+1=（dj+1）%m）若在0~18（即m=19）的散列地址空间中对该关键码构造散列表，则关键码14对应的地址是（）。

A．1B．2C．3D．14B设有8个数据元素，其关键字分别为{17,26,35,49,63,72,19,25}，散列表长度为10，散列函数H（Key）=Key%7。写出采用“线性探测再散列法”解决冲突所得的散列表，并计算搜索成功、搜索不成功的平均搜索长度。4445Chapter7搜索结构本章重要知识点静态搜索结构：顺序搜索、折半搜索二叉搜索树（BST树）二叉搜索树定义、特点在二叉搜索树中搜索元素的算法平均搜索长度的计算:ASL二叉搜索树的插入、删除AVL树定义、特点平衡化旋转的方法46Chapter7搜索结构本章重要程序有序表的折半搜索：P304-305二叉搜索树类：P310二叉搜索树树的搜索、插入：P311-312二叉搜索树的删除：P313-314AVL树的构造及四种平衡化旋转的方法P321-32547Chapter7搜索结构-重要复习题本章重要复习题顺序搜索：P3427.2（对画判定树不做要求）折半搜索：P3427.3BST插入与删除：P3427.8AVL：P3437.14、7.1548示例已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半搜索90时，需进行

次搜索可确定搜索成功；搜索40时需进行

___次搜索才能确定不成功。2，449B

1、有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉搜索树，若希望高度最小，则应选择下面哪个序列输入

。

A、45，24，53，12，37，96，30B、37，24，12，30，53，45，96C、12，24，30，37，45，53，96D、30，24，12，37，45，96，53示例50

2、一棵二叉搜索树，其节点A、B、C、D、E、F依次存放在一个起始地址为n（假定地址以字节为单位顺序编号）的连续区域中，每个节点占4个字节：前2个字节存放节点值，后2个字节依次存放左指针、右指针。若该二叉搜索树的根节点为E，则它的一种可能的前序遍历为

(1)，相应的层序遍历为

(2)。在以上两种遍历的情况下，节点C的左指针Lc的存放地址为

(3)，Lc的内容为

(4)。节点A的右指针Ra的内容为

(5)。（1）A.EAFCBDB.EFACDBC.EABCFDD.EACBDF（2）A.EAFCBDB.EFACDBC.EABCFDD.EACBDF（3）A.n+9B.n+10C.n+12D.n+13（4）A.n+4B.n+8C.n+12D.n+16（5）A.n+4B.n+8C.n+12D.n+16解答：（1）D；（2）A；

（3）B；（4）A；（5）B513、已知一长度为12的表（Jan，Feb，Mar，Apr，May，June，July，Aug，Sept，Oct，Nov，Dec）。（1）依次取表中各元素构造一棵二叉搜索树（按照在英文字典中的先后顺序比较元素值的大小）；并求其在等概率情况下搜索成功时的平均搜索长度。（2）若对表中元素进行排序构成有序表，求在等概率情况下对此有序表进行折半搜索成功的平均搜索长度。（3）按表中元素顺序构造一棵AVL树，并求其在等概率情况下搜索成功的平均搜索长度。解答：（1）42/12；（2）37/12；（3）38/1252JanFebJulyNovSeptMarJuneMayOctAprAugDec二叉搜索树53JanFebJulyNovSeptMarJuneMayOctAprAugDec342341342434折半搜索54MarJanAprJulyNovOctJuneMaySeptAugFebDecAVL树55Chapter8图本章重要知识点图的基本概念路径、连通分量、生成树图的类型无向图、有向图、加权图（网）每种图的基本特性图的表示方法及特点邻接矩阵、邻接链表图的遍历及应用DFSBFS56最小生成树KruskalPrim最短路径非负权值的单源点最短路径Dijkstra活动网络AOV网络：拓扑排序57Chapter8图本章重要算法：图的邻接矩阵表示：P352-354图的邻接链表表示：P356-360DFS实现：P364-365BFS实现：P366最小生成树

Kruskal算法：P371-373

Prim算法：P374-375最短路径Dijkstra算法：P376-378拓扑排序(AOV网络)：P384-38758Chapter8图-重要复习题本章重要复习题图的概念：P3928.1、8.2、8.3、8.4、8.6、8.7图的遍历：P392

8.10最小生成树：P392

8.11最短路径：P3958.2459

1、在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为

。

A．e

B．2e

C．n2-e

D．n2-2eD示例2、设一个包含N个顶点、E条边的简单有向图采用邻接矩阵存储结构（矩阵元素A[i][j]等于0/1分别表示顶点i与顶点j之间有/无弧），则该矩阵的元素数目为（1），其中非零元素数目为为（2）。

A.E2B.N2C.N2-E2D.N2+E2A.NB.N+EC.ED.N-E解答：（1）B；（2）C60

3、若采用邻接矩阵来存储简单有向图，则某个顶点i的入度等于该矩阵

。A、第i行中值为1的元素个数

B、所有值为1的元素总数C、第i行及第i列中值为1的元素总个数D、第i列中值为1的元素个数D4、假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是

。

A．O(n)

B．O(e)

C．O(n+e)

D．O(n*e)C615、若G是一个具有36条边的非连通无向图（不含自回路和多重边），则图G至少有

个顶点。A、11B、10C、9D、8B有n个顶点的无向图至多有n(n-1)/2条边。6、无向图G=(V,E)，其中：V={a,b,c,d,e,f}，E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b

D627、已知带权的无向图G如左图所示（1）画出G的邻接表结构（要求：顶点的各邻接边的链接顺序按照顶点序号由小到大的顺序链接）；（2）基于上述邻接表结构，从顶点A出发，分别写出按深度优先和宽度优先遍历图G的顶点序列。12AB720152430108CED63hA[1]B[2]C[3]D[4]E[5]2123711241017210dataweightlink520∧515∧48524∧38530∧120215324430∧深度优先遍历序列：ABDCE宽度优先遍历序列：ABCED12AB720152430108CED641、已知带权的无向图G如左图所示（1）画出G的邻接表结构（要求：顶点的各邻接边的链接顺序按照顶点序号由小到大的顺序链接）；（2）基于上述邻接表结构，从顶点A出发，分别写出按深度优先和宽度优先遍历图G的顶点序列。（3）以VA为出发点，按Prim算法和Kruskal算法分别求G的最小生成树；12AB720152430108CED图的应用示例652、对如下有向图用Dijkstra算法，求V0到各顶点的最短距离和路线，要求填写过程：66V0V1<01>5V2<02>1010V3<03><023><043>------504040V4<04>202020V5<05><045>5050502567Chapter9排序本章重要知识点直接插入排序折半直接插入排序希尔排序冒泡排序快速排序堆排序归并排序68Chapter9排序-重要复习题本章重要复习题排序练习：P4409.2堆排序：P4419.11冒泡的改进：P4419.1769示例1、在文件“局部有序”或文件长度较小的情况下，最佳的内部排序方法是（）A、插入排序B、堆排序C、归并排序D、快速排序A最不合适的是？702、给出一组关键码K={12，2，16，30，8，28，4，10，20，6，18}，按关键字从小到大排序：（1）写出归并第一趟结束时的序列；（2）写出快速排序第一趟结束时的序列（选第一个数为支点）；71示例【荷兰国旗问题】设有红、白、蓝三种颜色的条块组成的条块数组（颜色随机排列），请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。【算法思想】利用选择排序的思想。首先从序列中选择所有的红色条块，依次放到序列的前面，然后再从剩余的序列中选择所有的白色条块，依次放到红色条块后面。这样经过两趟选择，时间复杂度为O(n)。设这些条块颜色依次存放在L[0,…,n-1]中，

72各章复习示例汇总731、给定一个有n个元素的线性表。若采用顺序存储结构，则在等概率前提下，向其插入一个元素需要移动的元素个数平均为（）。A．nB．n/2C．(n-1)/2D．(n+1)/22、已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半搜索90时，需进行

____次搜索可确定搜索成功；搜索40时需进行

____

次搜索才能确定不成功。一、单选题、填空D2，4743、以下程序中划线语句的执行次数是（）。intsum(intn){intsum=0,i,j;for(i=1;i<=n;i++){p=1;for(j=1;j<=i;j++)

p*=j;

sum+=p;}returnsum;}

A．n(n+1)/2 B．n(n+1) C．n(n-1)/2 D．n(n-1)A754、计算机执行下面的语句时，语句s的执行次数为

。

for(i=1;i<n-1;i++)for(j=1;j<=i;j++)s;765、下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。B776、在双向链表存储结构中，删除p所指的结点时须修改指针（）。A．p->llink->rlink=p->rlink;p->rlink->llink=p->llink;B．p->llink=p->llink->llink;p->llink->rlink=p;C．p->rlink->llink=p;p->rlink=p->rlink->rlinkD．p->rlink=p->llink->llink;p->llink=p->rlink->rlink;7、递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。A．队列B．多维数组C．栈D.线性表AC788、用I表示入栈操作，O表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的I和O操作串为（）。

A．IIOOIIOOB．IOIOIIOOC．IOIIOIOOD．IOIIOOIO9、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？（）A．1和5B．2和4C．4和2D．5和1CB7910、数组A[0..5,0..6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是（）。

A．1175B．1180C．1205D．121011、算术表达式a+b*（c+d/e）转为后缀表达式后为（）。A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++AB8013、设有一组关键码{19，01，23，14，55，20，84，27，68，11，10，77}，采用散列函数H（key）=key%13，处理冲突的方法是线性探测再散列的方法（即dj+1=（dj+1）%m）若在0~18（即m=19）的散列地址空间中对该关键码构造散列表，则关键码14对应的地址是（）。

A．1B．2C．3D．14B12、散列技术中的冲突指的是（）。A．两个元素具有相同的序号B．两个元素的关键码不同，而其他属性相同C．数据元素过多D．不同关键码的元素对应于相同的存储地址D8114.在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为

。A．e

B．2e

C．n2-e

D．n2-2eD

15.假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是

。

A．O(n)

B．O(e)

C．O(n+e)

D．O(n*e)C82

16.设一个包含N个顶点、E条边的简单有向图采用邻接矩阵存储结构（矩阵元素A[i][j]等于0/1分别表示顶点i与顶点j之间有/无弧），则该矩阵的元素数目为（1），其中非零元素数目为为（2）。

A.E2B.N2C.N2-E2D.N2+E2A.NB.N+EC.ED.N-E解答：（1）B；（2）C8317.若G是一个具有36条边的非连通无向图（不含自回路和多重边），则图G至少有

个顶点。A、11B、10C、9D、8有n个顶点的无向图至多有n(n-1)/2条边。84二、解答题1、设有三对角矩阵，如上图所示，将带状区域中的元素ai,j(|i-j|≤1)放在一维数组B中，则（1）B的大小为多少？（2）元素ai,j在B中的位置是什么？（B的下标从0开始计，以行优先方式存储）85参考解答（1）B的大小：3n-2（2）A[i,j]=B[2i+j-2]

862、设有以下次序出现的关键字：65，23，31，26，7，91，53，15，72，52，49，68，要求用散列（哈希）方法将它们填入有14个位置的表中。（1）对上述关键字构造一个散列（哈希）函数，使得发生的冲突尽可能少；（2）用线性开型寻址方法（线性探测再散列法）解决冲突，写出散列（哈希）函数并指出上述各关键字在表中的位置。87解：用除留余数法，H(k)=k%p，p=13，各元素的散列地址如下：H(65)=0，H(23)=10，H(31)=5，H(26)=0，H(7)=7，H(91)=0，H(53)=1，H(15)=2，H(72)=7，H(52)=0，H(49)=10，H(68)=3，65269153153152772682349012345678910111213参考解答88三、算法阅读1、已知一带表头节点的单链表L为（5，7，0，9，4，2，8），first指针指向表头节点，data为链表的值域，link为指针域。阅读以下程序，回答问题。template<classType>voidChain<Type>::fun(Typemin,Typemax){ChainNode<Type>*pr=first,*p=first->link;while(p){if(p->data>min&&p->data<max){pr->link=p->link;deletep;p=pr->link;}else{pr=p;p=pr->link;}}}（1）说明该程序的功能；（2）试画出执行L.fun(3,7);调用后的L链表的逻辑示意图。89参考解答（1）删除单链表中所有大于min且小于max的元素。（2）first->7->0->9->2->8。90

（1）Fibonacci序列0,1,1,2,3,5,8,13,21,34..，其中每个元素是前两个元素之和，可递归定义为：

试利用栈来模拟计算的递归调用，编写一个非递归实现的算法代码，并给出必要的注释。【注明】已知栈的三个运算定义如下（可直接使用）：Push（S，x）：元素x入S栈；Pop（S，x）：S栈顶元素出栈；S_IsEmpty（S）：判断栈空，true为空，false不为空。另外，top为栈顶指针。四、算法设计与实现91inti,x1,x2