第五章数据结构及常用算法
本章内容: 常用集合元素有: 向量(Vector), 枚举(Enumeration), 散列表(哈希表)(Hashtable)和属性(Properties)﹑数据结构中的接口﹑堆栈﹑链表﹑数据排序算法﹑数据查找算法.
教学目标: 学生通过本章学习应掌握Java常用集合元素﹑堆栈﹑链表﹑数据排序算法﹑数据查找算法的应用
一、重点与难点: Java语法基础及Java面向对象特性,掌握常用的集合元素及常用的结合接口,熟练使用
常用集合元素, 数据排序算法﹑数据查找算法。
二、教具: 可进行广播的教学或多媒体计算机局域网,投影仪及相关的软硬件.
三、教学方法: 理论与实训相结合。
四、教学时数: 第8-9周6小时
五、作业及上机练习: P.139-- 1.3.4.6.7.8.
5.1 向量(Vector)
向量(Vector)是常见的数据结构, 向量对象由java.util包中的Vector类来创建.它类似数组结构,但不要求每个元素的类型相同, 向量中可以混合多种数据类型. 向量元素可动态增加. Vector类中的对象不但可以顺序存储数据,还封装了一些方法来处理和操作向量中的数据,使用非常方便.
5.1.1 创建向量对象:
(1) Vector stu = new Vector(); //使用无参数构造函数创建向量对象，不给出向量大小
(2) 带参数的构造函数
Public Vector(int Capacity, int Increament ); // 形参int Capacity –容量(初始化向量元素多少); int Increament –追加元素个数,如:
Vector stu = new Vector(40,5); //容量为40个元素,一次可添加5个元素.
5.1.2 向量对象的常用方法:
1. 添加元素方法
(1) public void add (Object o) : 将新对象o添加到向量末尾.
(2) public void add (int index, Object o) : 将新对象o添加到向量的指定索引位置.
(3) public void insertElement (Object o ,int index) : 将新对象o插入到向量的指定索引位置.
(4) public void addElement (Object o ,int index) : 将新对象o添加到向量指定索引位置.
2. 修改和删除向量元素
(1) public void set(Object o ,int index) : 将指定索引位置的对象设置为o,覆盖原来的对象.
(2) public void setElement (Object o ,int index) : 将指定索引位置的对象设置为o,覆盖原来的对象元素.
(3) public boolean removeElement (Object o) : 将向量序列中第一次出现的对象o删除, 同时将后面元素移补上前删除空位.
(4) public void removeALLElement ( ) : 将向量序列中所有对象删除.
(5) public Object remove (int index ) : 将向量序列中指定索引位置的对象元素删除,并返回该对象.
(6) public Object ElementAt (int index ) : 获取向量序列中指定索引位置的对象.
(7) public Object get (int index ) : 获取向量序列中指定索引位置的对象.
(8) public Object firstElement ( ) : 获取向量序列中的第一个对象.
(9) public Object lastElement ( ) : 获取向量序列中在的最后一个对象.
(10) public Enumeration Element( ) : 获取向量序列中的一个枚举对象.
(11) public index indexOf (Object o) : 获取对象o在向量序列中首次出现的位置.
(12) public index lastIndexOf (Object o) : 获取对象o在向量序列中最后出现的位置.
(13) public index lastIndexOf (Object o, int index) : 获取向量序列中在向量位置之前出现的最后位置.
(3) public boolean contains (Object o) :判断对象o是否是向量成员.
例5-1 TestVector1.java - 使用向量
例5-2 TestVector2.java - 使用向量依次存储不同数据类型
【例13.12】向量随机排列
5.1.3枚举(Enumeration)–Vector类也可以用枚举器来列举和存放许多元素。Vector类的Enumeration（）方法可返回一个Enumeration接口，该接口有两个常用方法:
（1）hasMoreElements() //判断是否还有元素
（2）nextElement() //下一个元素
使用方法如下:
例5-3 TestEnumeration
5.2 散列表(Hashtable-哈希表)
数组,向量提供了集合内容的顺序访问, 哈希表可以对集合内容进行随机访问。哈希表是使用关键字查找被存储的数据项的一种数据结构,可以通过键（名）-值对应集合内容进行随机访问,是Map接口的主要实现类.
5.2.1 创建哈希表对象–用java.util包中Hashtable类的构造函数来创建,其Hashtable类的构造函数如下:
(1) public Hashtable ( ); 创建具有默认容量和装载因子为0.75的散列表
(2) public Hashtable ( int intialCapacity); 创建具有指定容量和装载因子为0.75的散列表.
(3) public Hashtable ( int intialCapacity , float loadFactor); 创建具有指定容量和指定装载因子的散列表.如:
Hashtable table1 = new Hashtable ( );
5.2.2 哈希表主要方法如下:
(1)public void put (Object key, Object value)-- 加进对象(键/值)关键字/数值对.
(2)public Object get (Object key)—取得一个关键字的值.
(3)public Object remove (Object key)---删除一个元素
(4)public int size()---取得哈希表中关键字的数目
(5)public Boolean empty()---判断哈希表是否为空
(6)public Enumeration keys()---取得所有关键字设置
(7)public Enumeration elements()---取得所有数值的设置,两者都返回Enumeration.
例5-4 TestHarsh.java
5.3 数据结构中的接口
Java2数据结构提供了4种重要接口: Collection﹑List﹑Set﹑Iterator接口,用于描述不同类型的数据结构.
5.3.1 Collection接口
Collection接口是任何对象组的集合,对象的存放没有一定的顺序,并且允许重复,可以存放几个相同的对象. Collection接口的常用方法如下:
(1) public boolean add (object o) –向集合添加对象.
(2) public boolean remove (object o) –从集合删除对象.
(3) public boolean contains (object o) –判断是否包含对象.
(4) public boolean equals (object o) –比教两个对象是否相同
例5-5 TestCollection.java –使用Collection接口
5.3.2 Set接口
集合是由不重复元素组成的. Set集合接口中的元素不重复,且至多包含一个null元素.
例5-6 TestSet.java使用Set接口（对象无序存放）
5.3.3 List接口
List接口是一种可含有重复元素的,有序的数据集合,也称序列.用户可以控制向序列中插入元素的位置,并可按元素的位序(加入顺序)来进行访问, 位序从0开设.
5-7 TestList.java使用List接口（可存储重复元素）
5.3.4 Iterator接口
可以通过任何Collection接口中定义的iterator()方法获得一个Iterator对象. List接口中声明了三种方法hasNext(),next(),remove(). Set对象对应的Iterator仍然是无序的.
例5-8 TestIterator.java使用Iterator接口
5.4 堆栈
堆栈(Stack)是一种遵循:‖后进先出‖原则的重要线性数据结构,只允许在一端输入和输出线性的顺序表.堆栈把一个输入的数据放在最底下,把后面放入的数据放在已有数据的顶上,最后输入的数据在堆栈的最上面.这样堆栈就有一个固定的栈底和一个浮动的栈顶.允许输入和输出的一端称为栈顶(top),另一端称为栈底(bottom).
向堆栈中压入数据的操作称为‖压栈‖;从堆栈中输出数据的操作称为‖弹栈‖.由于堆栈总是在栈顶进行数据的输入输出操作,所以弹栈总是先输出最后压入堆栈中的数据,这就是后进先出的原理.
在Java中,使用jsva.util包中的Stack类来创建堆栈对象.如:
Stack person = new stack(); // Stack()是Stack类唯一的构造函数
Stack类是向量Vector类的子类,所以Stack类不但具有Vector类的所以方法,同时还有自己操作堆栈对象的方法,主要方法如下.
Public Object push(Object o)-- 将对象压入(输入)堆栈的操作.
Pubilc object pop (Object o)--将栈顶对象弹出(输出)堆栈的操作.
Public Boolean empty ()-- 判断堆栈是否还有数据,若有数据,返回false; 否则返回true.
Public Object peek (): -- 查看并返回堆栈顶端数据,但不删除.
Public int search (Object o); 查看数据在堆栈中的位置,最顶端的位置1,向下依次增加,如果堆栈不含该数,则返回-1.
例5-9 TestStack.java -堆栈类的使用
5.5 链表
链表(LinkedList)是一种线性数据结构,是由若干个节点的对象组成的数据结构,每个节点包含一个数据和下一个节点对象的引用(单链表) ,如果每个节点包含两个对象的引用,即上一个节点和下一个节点的引用,这样的链表称双链表. 用java.util包中的LinkedList类创建一个链表,并且该类提供足够的方法对链表中对象操作.
创建一个链表对象:
LinkedList List1 = new LinkedList( ); //创建一个空双链表对象
用add( )方法向这个链表对象中添加节点,如:
List1.add("white "); List1.add("black "); List1.add("red "); List1.add("yellow");
这样链表List1就自动生成四个节点.
例5-10 ListTest1.java - 链表类的应用
LinkedList类常用方法：
（1）public void add ( int index, Object o ) –向链表的指定位置末尾添加一个新的对象元素。
（2）public boolean add (Object o ) –向链表的末尾添加一个新的对象元素。
（3）public boolean addFirst (Object o ) –向链表的表头添加一个新的对象元素。
（4）public boolean addLast (Object o ) –向链表的末尾添加一个新的对象元素。
（5）public Object remove ( int index ) –从链表的指定位置删除一个对象元素。
（6）public Object remove (Object o ) –从链表中删除首次出现的对象元素。
（7）public Object removeFirst (Object o ) –从链表中删除第一个节点对象元素。
（8）public Object removeLast (Object o ) –从链表中删除最后一个节点对象元素。
（9）public Object clear -- 从链表中删除所有节点对象元素。
（10）public Object set ( int index , Object o) -- 在链表的指定位置用指定对象o代替原来对象，并返回原来对象。
（11）public Object get ( int index) -- 从链表的指定位置获取一个对象元素。
（12）public Object getFirst ( ) -- 从链表的第一个节点获取对象元素。
（13）public Object getLast ( ) -- 从链表的最后为值获取对象元素。
（14）public int indexOf (Object o ) -- 返回链表中的指定对象首次出现的位置, 如果链表中无此节点，则返回-1。
（15）public int lastIndexOf (Object o ) -- 返回链表中的指定对象最后出现的位置, 如果链表中无此节点，则返回-1。
（16）public int size( ) -- 返回链表的长度.
（17）public boolean contains (Object o ) –判断链表中是否包含指定对象o。
例5-11 ListTest2.java - 链表类的应用
5．6 数据排序算法—从大到小（降序），从小到大（升序）
5．6．1 冒泡法排序
把当前数据序列中的各相邻数据两两比较，如两数之间不符合降序或升序关系，就交换两数据的顺序，经多次比较和交换，直到排序的数据数目为零，冒泡法排序就结束。
例5-12 BubbleSort.java –冒泡法升序排序
5．6．2 选择法排序
把当前数据序列中的第一个数和其它各数进行比较和交换，选出最小的数，放到0位，然后在其它数中再选择一个最小值，放在1为，依次类推，直到选择排序结束，方法和上例类似。
例5-13 SelectSort.java --选择法排序
5．7 数据查找算法
查找是利用关键值在特定的数据集合中找出符合匹配关键值的过程，有顺序查找法和二分查找法。5．7．1 顺序查找法
从数据序列的第一个数开始，将数据集合或序列中的每个数据与关键值一一匹配，若找到匹配数据，则查找成功，否则失败。该算法为穷举算法，用于较少的数据个数。
例5-14 OrderSearch.java -- 顺序查找法
小结：本章介绍了java.util包内的常用数据集合（数据结构向量类﹑散列表类和接口），主要用来保存各种类型对象数据的应用及数据排序算法-冒泡法升序排序﹑选择法排序和顺序查找法的应用。主要要求掌握数据集合的应用和了解数据排序算法的原理。
《数据结构》必须掌握的知识点与算法 第一章绪论 1、算法的五个重要特性（有穷性、确定性、可行性、输入、输出） 2、算法设计的要求（正确性、可读性、健壮性、效率与低存储量需求） 3、算法与程序的关系： （1）一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。 （2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。 （3）一个算法若用程序设计语言来描述，则它就是一个程序。 4、算法的时间复杂度的表示与计算（这个比较复杂，具体看算法本身，一般关心其循环的次数与N的关系、函数递归的计算） 第二章线性表 1、线性表的特点： （1）存在唯一的第一个元素；（这一点决定了图不是线性表） （2）存在唯一的最后一个元素； （3）除第一个元素外，其它均只有一个前驱（这一点决定了树不是线性表） （4）除最后一个元素外，其它均只有一个后继。 2、线性表有两种表示：顺序表示（数组）、链式表示（链表），栈、队列都是线性表，他们都可以用数组、链表来实现。 3、顺序表示的线性表（数组）地址计算方法： （1）一维数组，设DataType a[N]的首地址为A0，每一个数据（DataType类型）占m个字节，则a[k]的地址为：A a[k]＝A0+m*k（其直接意义就是求在数据a[k]的前面有多少个元素，每个元素占m个字节） （2）多维数组，以三维数组为例，设DataType a[M][N][P]的首地址为A000，每一个数据（DataType 类型）占m个字节，则在元素a[i][j][k]的前面共有元素个数为：M*N*i+N*j+k，其其地址为： A a[i][j][k]＝A000+m*(M*N*i+N*j+k)； 4、线性表的归并排序： 设两个线性表均已经按非递减顺序排好序，现要将两者合并为一个线性表，并仍然接非递减顺序。可见算法2.2 5、掌握线性表的顺序表示法定义代码，各元素的含义； 6、顺序线性表的初始化过程，可见算法2.3 7、顺序线性表的元素的查找。 8、顺序线性表的元素的插入算法，注意其对于当原来的存储空间满了后，追加存储空间（就是每次增加若干个空间，一般为10个）的处理过程，可见算法2.4 9、顺序线性表的删除元素过程，可见算法2.5 10、顺序线性表的归并算法，可见算法2.7 11、链表的定义代码，各元素的含义，并能用图形象地表示出来，以利分析； 12、链表中元素的查找 13、链表的元素插入，算法与图解，可见算法2.9 14、链表的元素的删除，算法与图解，可见算法2.10 15、链表的创建过程，算法与图解，注意，链表有两种（向表头生长、向表尾生长，分别用在栈、队列中），但他们的区别就是在创建时就产生了，可见算法2.11 16、链表的归并算法，可见算法2.12 17、建议了解所谓的静态单链表（即用数组的形式来实现链表的操作），可见算法2.13 18、循环链表的定义，意义 19、循环链表的构造算法（其与单链表的区别是在创建时确定的）、图解
数据结构作业系统_第五章答案 5.21④假设稀疏矩阵A和B均以三元组表作为存储结构。 试写出矩阵相加的算法，另设三元组表C存放结果矩阵。 要求实现以下函数： Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C); /* 三元组表示的稀疏矩阵加法: C=A+B */ 稀疏矩阵的三元组顺序表类型TSMatrix的定义： #define MAXSIZE 20 // 非零元个数的最大值 typedef struct { int i,j; // 行下标,列下标 ElemType e; // 非零元素值 }Triple; typedef struct { Triple data[MAXSIZE+1]; // 非零元三元组表,data[0]未用 int mu,nu,tu; // 矩阵的行数、列数和非零元个数 }TSMatrix; Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C) /* 三元组表示的稀疏矩阵加法: C=A+B */ { int k=1,n=1,p=1; ElemType ce; if(A.mu!=B.mu||A.nu!=B.nu)return ERROR; while(k<=A.tu&&n<=B.tu) {
if(A.data[k].i==B.data[n].i&&A.data[k].j==B.data[n].j) { ce=A.data[k].e+B.data[n].e; if(ce) { C.data[p].i=A.data[k].i; C.data[p].j=A.data[k].j; C.data[p].e=ce; p++; //printf("%d,,%d ",ce,C.data[p-1].e); } k++;n++; } else if(A.data[k].i
数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件：
（1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：adr(ai)=adr(a1)+(i-1)k,，adr(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。 队列是“先进行出”（fifo）或“后进后出”（lilo）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满
数据结构常考算法大全 HL是单链表的头指针，试写出删除头结点的算法。ElemTypeDeleFront(LNode * & HL) { if (HL==NULL){ cerr<<"空表"<
P=p→next; q→next=HL; HL=q; } } 34．阅读下列函数arrange() int arrange(int a[],int 1,int h,int x) {//1和h分别为数据区的下界和上界 inti,j,t； i=1；j=h； while(i while(i=x)j--； while(i=x)i++； if(i { t=a[j]；a[j]=a[i]；a[i]=t；} } if(a[i]； else return i－1； } （1）写出该函数的功能； （2）写一个调用上述函数实现下列功能的算法：对一整型数组b[n]中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。 五、算法设计题（本题共10分） 34．（1）该函数的功能是：调整整数数组a[]中的元素并返回分界值i，使所有＜x的元素均落在a[1..i]上，使所有≥ x的元素均落在a[i＋1..h]上。 （2）int f(int b[],int n) 或int f(int b[],int n) { { intp,q；intp,q； p=arrange(b,0,n－1,0)；p=arrange(b,0,n－1,1)； q= arrange(b,p+1,n－1,1)；q= arrange(b,0,p,0)； return q－p；return p－q； } } 设计判断单链表中结点是否关于中心对称算法。 typedefstruct {int s[100]; int top;} sqstack; intlklistsymmetry(lklist *head)
《数据结构与算法》期末复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i 大学 《数据结构与算法分析》课程 习题及参考答案 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( ) 个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________; 删除一个结点时，需要执行的操作是______________________________（假设栈不空而 且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左 孩子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有 双亲，则双亲结点的编号为________。 5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整 到____________位置为止。 6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 7.表示图的三种常用的存储结构为_____________、____________和_______________。 8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。 三、运算题（每题 6 分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。 3.判断以下序列是否是小根堆? 如果不是, 将它调 图2 整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7}; 习题参考答案 一．选择题 1.从逻辑上可以把数据结构分为（C)两大类。 A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 2.在下面的程序段中，对x的斌值语句的频度为（C)。 for( t＝1；k＜＝n;k＋＋） for（j=1;j＜＝n; j＋＋） x=x十1； A. O(2n) B. O (n) C. O (n2)． D. O（1og2n) 3.采用链式存储结构表示数据时，相邻的数据元素的存储地址（C)。 A.一定连续B．一定不连续 C.不一定连续 D.部分连续，部分不连续 4.下面关于算法说法正确的是（D）。 A.算法的时间复杂度一般与算法的空间复杂度成正比 B.解决某问题的算法可能有多种，但肯定采用相同的数据结构 C.算法的可行性是指算法的指令不能有二义性 D.同一个算法，实现语言的级别越高，执行效率就越低 5.在发生非法操作时，算法能够作出适当处理的特性称为（B）。 A.正确性 B.健壮性 C.可读性 D.可移植性 二、判断题 1.数据的逻辑结构是指数据的各数据项之间的逻辑关系。（√） 2.顺序存储方式的优点是存储密度大，且插人、删除运算效率高。（×） 3.数据的逻辑结构说明数据元素之间的次序关系，它依赖于数据的存储结构。（×） 4.算法的优劣与描述算法的语言无关，但与所用计算机的性能有关。（×） 5.算法必须有输出，但可以没有输人。（√） 三、筒答题 1．常见的逻辑结构有哪几种，各自的特点是什么？常用的存储结构有哪几种，各自的特点是什么？ 【答】常见的四种逻辑结构： ①集合结构：数据元素之间是“属于同一个集合” ②线性结构：数据元素之间存在着一对一的关系 ③树结构：数据元素之间存在着一对多的关系 ④结构：数据元素之间存在着多对多的关系。 常见的四种存储结构有： ①顺序存储：把逻辑上相邻的元素存储在物理位置相邻的存储单元中。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。 ②链接存储：对逻辑上相邻的元素不要求物理位置相邻的存储单元，元素间的逻辑关系通过附设的指针域来表示。 ③索引存储：通过建立索引表存储结点信息的方法，其中索引表一般存储结点关键字和一个地点信息，可通过该地址找到结点的其他信息。 ④散列存储：根据结点的关键字直接计算出该结点的存储地址的方法。 2．简述算法和程序的区别。 【解答】一个算法若用程序设计语言来描述，则它就是一个程序。算法的含义与程序十分相 一、概念题（每空1分，共53分） 1．树（及一切树形结构）是一种“________”结构。在树上，________结点没有直接前趋。对树上任一结点X来说，X是它的任一子树的根结点惟一的________。 2．由３个结点所构成的二叉树有种形态。 3．一棵深度为6的满二叉树有个分支结点和个叶子。 4．一棵具有２５７个结点的完全二叉树，它的深度为。 5．二叉树第i(i>=1)层上至多有______个结点；深度为k(k>=1)的二叉树至多有______个结点。6．对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。 7．满二叉树上各层的节点数已达到了二叉树可以容纳的______。满二叉树也是______二叉树，但反之不然。 8．设一棵完全二叉树有700个结点，则共有个叶子结点。 9.设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。 10.一棵含有n个结点的k叉树，可能达到的最大深度为，最小深度为。 11.二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是。 12.中序遍历的递归算法平均空间复杂度为。 13.二叉树通常有______存储结构和______存储结构两类存储结构。 14.如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X有： （1）若i=1,则结点X是______；若i〉1,则X的双亲PARENT(X)的编号为______。 （2）若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号为______。 （3）若2i+1>n，则结点X无______；否则，X的右孩子RCHILD(X)的编号为______。 15.每个二叉链表的访问只能从______结点的指针，该指针具有标识二叉链表的作用。 16.二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是____________的指针，或者是______。 17.具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左 右孩子，其余的________个指针域为NULL。 18.二叉树有不同的链式存储结构，其中最常用的是________与________。 19.若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的________个结点。 20.树与二叉树之间最主要的差别是：二叉树中各结点的子树要区分为________和________，即使在结点只有一棵子树的情况下，也要明确指出该子树是________还是________。 21.树的结点数目至少为________，二叉树的结点数目至少为________。 22.树的主要遍历方法有________、________、________等三种。 23.由________转换成二叉树时，其根结点的右子树总是空的。 24.哈夫曼（Huffman）树是带权路径度________的树，通常权值较大的结点离根________。 25.用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是。 二、选择题（每空1分，共12分） （）1．不含任何结点的空树。 （Ａ）是一棵树; （Ｂ）是一棵二叉树; （Ｃ）是一棵树也是一棵二叉树; （Ｄ）既不是树也不是二叉树 （）2．二叉树是非线性数据结构，所以。 《数据结构与算法》复习题 选择题 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑 B．存储 C．逻辑和存储 D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何 B．结点个数的多少 C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是 O(n2) 。 s =0; for( I =0; i //四章算法 //说明 //sqstring——顺序串 listring——链串 //目录 //算法1:按字典顺序比较两个串s和t的大小(sqstring.cpp) //算法2:求串s中第一个最长的连续相同字符构成的平台(sqstring.cpp) //算法3:把串s中最先出现的子串"ab"改为"xyz"(listring.cpp) //算法4:BF算法(listring.cpp) //算法5:KMP算法(sqstring.cpp) //算法6:改进的KMP算法(sqstring.cpp) //算法 //算法1：按字典顺序比较两个串s和t的大小 #include"sqstring.cpp" int Strcmp(SqString s,SqString t) { int i,comlen; if (s.length 常用的大数据结构与算法 在学习了解这些数据结构和算法之前，引用一位前辈的话： “我们不需要你能不参考任何资料，实现红黑树；我们需要的是你能在实践当中，选择恰当的数据结构完成程序开发；在必要的时候，能在已有的数据结构基础上进行适当改进，满足工程需要。但要做到这一点，你需要掌握基础的算法和数据结构，你需要理解并应用一些高级数据结构和算法的思想。因此，在程序员这条道路上，你要想走得更远，你需要活用各种数据结构，你需要吸收知名算法的一些思想，而不是死记硬背算法本身。” 那么，工程实践当中，最常用的算法和数据结构有哪些？ 以下是Google工程师Arjun Nayini在Quora给出的答案，得到了绝大多数人的赞同。 最常用的算法 1.图搜索算法(BFS,DFS) 2.排序算法 3.通用的动态规划算法 4.匹配算法和网络流算法 5.正则表达式和字符串匹配算法 最常用的数据结构 1.图，尤其是树结构特别重要 2.Maps结构 3.Heap结构 4.Stacks/Queues结构 5.Tries树 其他一些相对比较常用的数据算法还有：贪心算法、Prim’s / Kruskal’s算法、Dijkstra’s 最短路径算法等等。 怎么样才能活用各种数据结构？ 你能很清楚的知道什么时候用hash表，什么时候用堆或者红黑色？在什么应用场景下，能用红黑色来代替hash表么？要做到这些，你需要理解红黑树、堆、hash表各有什么特性，彼此优缺点等，否则你不可能知道什么时候该用什么数据结构。 常言道： 程序=算法＋数据结构 程序≈数据结构 小编希望这些算法的掌握能够帮助大家拓宽握数据结构和算法的视野，提高算法设计和动手编程的能力。 //插入排序法 void InsertSort() { int s[100]; int n,m,j,i=0,temp1,temp2; printf("请输入待排序的元素个数："); scanf("%d",&n); printf("请输入原序列："); for (i=0; i //堆排序 static a[8] = {0,25,4,36,1,60,10,58,}; int count=1; void adjust(int i,int n) { int j,k,r,done=0; k = r = a[i]; j = 2*i; while((j<=n)&&(done==0)) { if(j 第5章常用数据结构与算法 5.1 字符串 字符串(string)类型直接从object类派生,它是被密封的,不能再有派生类。 5.1.1字符串类型定义 1.定义 2.两种字符串: (1)规则字符串:由包含在双引号中的零个或多个字符组成,并且可以 包含简单转义序列、十六进制转义序列、Unicode转义序列。 如：”hello” (2)逐字字符串:由@后跟双引号字符、零个或多个字符组成。如： @”hello” 区别：规则字符串要对字符串中的转义序列进行解释 逐字字符串除了对双引号进行解释之外，对其他字符，原样显示。例如：string str1;//定义字符串类型 string str2=”hello,word”//规则字符串hello,word string str3=@”hello,word”//逐字字符串hello,word string str4=”hello\tword”//规则字符串hello word string str5=@”hello\tword”//逐字字符串hello\tword 5.1.2 字符串类型的应用 1．判断一个字符串的长度 在C#中，字符串类型有一个Length属性，利用它可得到一个字符串变量或 一个字符串常量的长度。 例如： string str=”abcdefghijk”;// str变量中的串由11个字符组成Console.WriteLine(str.Length); //str变量的长度为11 Console.WriteLine(”abcdefghijk”.Length);//直接取串的长度为11 2.比较两个字符串是否相等 C#直接重载了”==”和”!=”两个运算符处理两个字符串是否相等。 在C#中，字符串相等的条件： 两个字符串都为空串（null）或两个字符串实例长度相同，并且每个字符位置中的字符都相同。 例如： string str1=”abcdefghijk”; string str2=”abcdefghijk”; Console.WriteLine(str1==str2); //str1和str2相等，得到真值true 3.字符串的连接 直接使用”+”运算符. string str1=”abcde”; str1+=”fghijk”; Console.WriteLine(str1); //str1的值为”abcdefghijk” 4.在字符串中插入另一字符串 使用字符串类的Insert方法。该方法的参数有两个,前一个参数是新字符串要插入的位置,后一个参数是要插入的字符串。 [试题分类]：数据结构与算法 1.数据结构可形式地定义为(D, S)，其中S是D上( )的有限集。 A.操作 B.存储映像 C.关系 D.数据元素 答案:C 题型:单选题 知识点:1.2 基本概念和术语 难度:1 2.一般而言，最适合描述算法的语言是( )。 A.自然语言 B.计算机程序语言 C.介于自然语言和程序设计语言之间的伪语言 D.数学公式 答案:C 题型:单选题 知识点:1.4 算法和算法分析 难度:1 3．在下列序列中，不是线性表的是( )。 A. (‘a’,‘b’) B. (a, b) C. (‘AB’,‘CD’) D. (‘a’, b) 答案:D 题型:单选题 知识点:2.1 线性表的类型定义 难度:2 4.对于顺序表的优缺点，以下说法错误的是( )。 A.插入和删除操作较方便 B.可以方便地随机存取表中的任一结点 C.无需为表示结点间的逻辑关系而增加额外的存储空间 D.由于顺序表要求占用连续的空间，存储分配只能预先进行 题型:单选题 知识点:2.2线性表的顺序表示和实现 难度:2 5.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行( )。 A. s->next=p->next;p->next=s; B. p->next=s->next;s->next=p; C. q->next=s;s->next=p; D. p->next=s;s->next=q; 题型:单选题 知识点:2.3线性表的链式表示和实现 难度:2 6.若某链表中最常用的操作是在最后一个结点后插入一个结点和删除最后一个结点，则采用( )存储方式最节省时间。 A.单链表 B.带头结点的单链表 C.单循环链表 1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998 三、1 （5分）】 LinkedList Union(LinkedList la,lb) { pa=la->next; pb=lb->next; la->next=null; while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data) { r=pa->next; pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。 la->next=pa; pa=r; } else {r=pb->next; pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb; pb=r; } while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb!=null) {r=pb->next; pb->next=la->next; la->next=pb; pb=r; } } 1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997 四、3（15分）】 LinkedList Union(LinkedList ha, hb)∥ha和hb是两个无头结点的数据域值递增有序的单链 ｛LinkedList 表，本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏hb链表。 la; la=(LinkedList)malloc(sizeof(LNode)); la->next=ha; pa=ha; pb=hb; pre=la; while(pa&&pb) if(pa->data 《数据结构与算法》(张晓莉)习题：选择题、判断题(同名10048) 第一章绪论 1. 从逻辑上可以把数据结构分为（ C ）两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 2. 在下面的程序段中，对x的赋值语句的频度为（ C ）。 For（k=1；k<=n；k++） For（j=1；j<=n；j++） x=x＋1； A．O(2n) B．O(n) C．O(n2) D．O(log2n) 3. 采用顺序存储结构表示数据时，相邻的数据元素的存储地址（ A ）。 A．一定连续B．一定不连续 C．不一定连续D．部分连续、部分不连续 4. 下面关于算法的说法，正确的是（ D ）。 A．算法的时间复杂度一般与算法的空间复杂度成正比 B．解决某问题的算法可能有多种，但肯定采用相同的数据结构 C．算法的可行性是指算法的指令不能有二义性 D．同一个算法，实现语言的级别越高，执行效率就越低 5. 在发生非法操作时，算法能够作出适当处理的特性称为（ B ）。 A．正确性B．健壮性C．可读性D．可移植性 第二章线性表 1. 线性表是（ A ）。 A．一个有限序列，可以为空B．一个有限序列，不能为空 C．一个无限序列，可以为空D．一个无限序列，不能为空 2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（ A ）个元素。 A．n/2 B．（n＋1）/2 C．（n－1）/2 D．n 3．线性表采用链式存储时，其地址（ D ）。 A．必须是连续的B．部分地址必须是连续的 C．一定是不连续的D．连续与否均可以 4．用链表表示线性表的优点是（C）。 A．便于随机存取B．花费的存储空间较顺序存储少 C．便于插入和删除D．数据元素的物理顺序与逻辑顺序相同 数据结构与算法基础 一．判断题： 1．数据元素是数据的最小单位。 2．数据结构是带有结构的数据元素的集合。 3．数据结构、数据元素、数据项在计算机中的映像（或表示）分别称为存储结构、结点、数据域。 4．数据项是数据的基本单位。 5．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的。 6．数据的物理结构是指数据在计算机内实际的存储形式。 7．算法和程序没有区别，所以在数据结构中二者是通用的。 二． 数据结构是研究数据的 A 和 B 以及它们之间的相互关系，并对这种结构定义相应的 C ，设计出相应的 D ，而确保经过这些运算后所得到的新结构是 E 结构类型。 供选择答案： A、Ｂ：ａ理想结构ｂ抽象结构ｃ物理结构ｄ逻辑结构 Ｃ、Ｄ、Ｅ：ａ运算ｂ算法ｃ结构ｄ规则ｅ现在的ｆ原来的 三．从供选择的答案中选取正确的答案天趣下面叙述中的横线上： 1． A 是描述客观事物的数、字符以及所能输入到计算机中并呗计算机程序加工处理的符号的集合。 2. B 是数据的基本单位,即数据集合中的个体。有时一个 B 由若干个_______组成，在这种情况下，称 B 为记录。 C 是数据的最小单位。而由记录所组成的线性表为 D 。 3. E 是具有相同特性的数据元素的集合，是数据的子集。 4. Ｆ是带有结构特性数据元素的集合。 5. 被计算机加工的数据元素不是孤立无关的，它们彼此之间一般存在着某种联系。通常将数据元素的这种关系称为Ｇ。 6. 算法的计算量的大小称为计算的Ｈ。 供选择的答案： Ａ－Ｆ：ａ数据元素ｂ符号ｃ记录ｄ文件ｅ数据ｆ数据项ｇ数据对象ｈ关键字ｉ数据结构 Ｇ：ａ规则ｂ集合ｃ结构ｄ运算 Ｈ：ａ现实性ｂ难度ｃ复杂性ｄ效率 四.分析一下各程序段，并用大“O”表示执行时间为n（正整数）的函数。 1. i:=1 k:=0; WHILE(i＜＝ｎ－１) DO BEGIN k:=ｋ＋１０*ｉ；ｉ：＝ｉ＋１ ＥＮＤ数据结构与算法分析习题与参考答案
数据结构与算法第1章参考答案
数据结构第五章自测题及解答
数据结构(C语言)【经典题库】含标准答案
数据结构第五章算法
常用的大数据结构与算法
数据结构经典算法 C语言版
第5章 常用数据结构与算法
数据结构与算法
数据结构经典算法试题
《数据结构与算法》(张晓莉)习题：选择题、判断题(同名10048)
数据结构与算法基础习题
相关主题
文本预览