数据结构高春晓复习

1、1. 数据的逻辑结构：数据的逻辑结构：描述数据间的逻辑关系描述数据间的逻辑关系。典型的典型的逻辑结构：逻辑结构：集合、线性、树、图集合、线性、树、图2. 数据的存储结构：数据的存储结构：逻辑结构在存储器中的映象逻辑结构在存储器中的映象。典典型的存储结构：型的存储结构：顺序和链式顺序和链式3. ADT：是对数据结构的一种更准确的抽象描述，它：是对数据结构的一种更准确的抽象描述，它忽略了数据结构的具体实现步骤，将更多的注意力忽略了数据结构的具体实现步骤，将更多的注意力放在数据的基本操作上，通过基本操作描述数据的放在数据的基本操作上，通过基本操作描述数据的逻辑关系。它包括三个部分：逻辑关系。它包括三

2、个部分：数据对象、数据关系数据对象、数据关系和基本操作和基本操作。4. 什么是算法的时间复杂度？如何计算？什么是算法的时间复杂度？如何计算？5. 什么是算法的空间复杂度？如何计算？什么是算法的空间复杂度？如何计算？ 1、在数据结构中，与所使用的计算机无关的是数据、在数据结构中，与所使用的计算机无关的是数据的（）的（） A. 存储结构存储结构 B. 逻辑结构逻辑结构 C. 逻辑和物理结构逻辑和物理结构 D. 物理结构物理结构 2、数据结构在计算机内存中的表示是指（）、数据结构在计算机内存中的表示是指（） A. 数据元素的结构数据元素的结构 B. 数据的逻辑结构数据的逻辑结构 C. 数据的存储结构

3、数据的存储结构 D. 数据元素之间的关系数据元素之间的关系 3、算法时间复杂度的含义是指算法的（）、算法时间复杂度的含义是指算法的（） A. 执行时间的长短执行时间的长短 B. 执行时间的增长率执行时间的增长率 C. 执行语句的多少执行语句的多少 D. 需要的存储空间需要的存储空间 4、如果某算法对于规模为、如果某算法对于规模为 n 的问题的时间耗费为的问题的时间耗费为 T（n）= n3 ，在一台计算机上运行时间为，在一台计算机上运行时间为 t 秒，则在另一台运行速度秒，则在另一台运行速度是其是其 64 倍的机器上，用同样的时间能解决的问题规模是原问倍的机器上，用同样的时间能解决的问题规模是原

4、问题规模的（）题规模的（） A. 4倍倍 B. 8倍倍 C. 64倍倍 D. 16倍倍 5、下面程序段的时间复杂度为（）、下面程序段的时间复杂度为（） for ( i=0; im; i+ ) for ( j=0; jn; j+ ) Aij = i*j; A. O (m * m) B. O (m * n) C. O (m + n) D. O (n * n) 线性表是线性表是n n个具有个具有相同类型相同类型的数据元素构成的的数据元素构成的有限有限序列序列线性表的存储线性表的存储链序存储链序存储(链表链表)顺序存储顺序存储(顺序表顺序表)双向循环链表双向循环链表单向循环链表单向循环链表单链表单链表

5、链表的静态存储链表的静态存储结构性结构性操作操作ListEmpty( L ) /判断线性表是否为空判断线性表是否为空ListLength( L ) /求线性表的长度求线性表的长度GetElem( L, i, &e ) /读取第读取第i个元素的值个元素的值LocateElem( L, e, compare( ) ) /定位定位eListTraverse(L, visit( ) /遍历线性表遍历线性表属性类属性类操作操作ListInsert( &L, i, e ) /插入数据元素插入数据元素ListDelete(&L, i, &e) /删除数据元素删除数据元素引用性引用性操作操作加工性加工性操作操

6、作InitList( &L ) /初始化一个线性表初始化一个线性表DestroyList( &L ) /删除线性表删除线性表 0 1 . i-2 i-1 . n-1a1a2ai-1aiantypedef struct ElemType *elem; / 存储空间基址存储空间基址 int length; / 当前长度当前长度 int listsize; / 当前分配的存储容量当前分配的存储容量 / (以以sizeof(ElemType)为单位为单位) SqList; / 俗称顺序表俗称顺序表elemlength listsizeLSqList L;L.elem+L. length1L.elem+

7、L. listsize134161182531341612531341613018253134161182531ListInsert(&L, 5, 30)123456789ListDelete (&L, 5, &e)123456789操作步骤操作步骤1) 判断位置合法判断位置合法性性2) 依次后依次后length-i+1个元素个元素后移后移一一位位3) 将新元素将新元素e写入写入到第到第i个位置个位置4) 将表的长度将表的长度加加1操作步骤操作步骤1) 判断位置合法判断位置合法性性2)将第将第i个位置的个位置的值赋给变量值赋给变量e3)依次后依次后length-i+1个元素个元素前移前移一一位

8、位4) 将表的长度将表的长度减减12) 1(1111ninnEniisn若假定在线性表中任何若假定在线性表中任何一个位置上进行一个位置上进行插入的插入的概率概率都是都是相等相等的，则的，则移移动元素的期望值动元素的期望值为为：n若假定在线性表中任若假定在线性表中任何一个位置上进行何一个位置上进行删除删除的概率的概率都是都是相等相等的，则的，则移动元素的期望值移动元素的期望值为为：21)(11ninnEnidl 用一组用一组地址任意地址任意的存储单元的存储单元存放存放线性表中的线性表中的数据元素数据元素a1 .ana2L:头指针头指针表尾表尾:空指针空指针头结点头结点 typedef struc

9、t LNode ElemType data; / / 数据域数据域 struct LNode *next; / / 指针域指针域 LNode, *LinkList; LinkList L； / L 为单链表的头指针为单链表的头指针a1 .ana2L:头指针头指针表尾表尾:空指针空指针头结点头结点 GetElem(L, i, &e) /取第取第i i个数据元素个数据元素a1 .ana2基本操作：基本操作：移动指针移动指针 i i 次次。 结束条件：结束条件：1 1、找到第找到第i i个结点个结点 2 2、i i大于链表的长度大于链表的长度, ,即即p pnullnull基本方法基本方法: : 1

10、 1、设置一个计数器、设置一个计数器j j； 2 2、设置一个依次向后移动的指针、设置一个依次向后移动的指针p p 。 主循环：主循环：while (p & ji) p = pnext; +j; ai-1 eaipss next = pnext; pnext = s;ListInsert(&L, i, e)找到线性表中第找到线性表中第i-1i-1个结点个结点修改其后继指针修改其后继指针ListDelete(&L, i, e)找到线性表中第找到线性表中第i-1i-1个结点个结点修改其后继指针修改其后继指针ai-1aiai+1ai-1pq = pnext; pnext = qnext ;free(

11、q);q正确连接正确连接指针指针找到正确找到正确位置位置不要丢失不要丢失结点结点 单向循环链表单向循环链表 双向链表双向链表 双向循环链表双向循环链表a1a2an a1 a2 . an a1 a2 . an 静态链表：用静态链表：用数组数组实现的链式结构实现的链式结构08122ZHAO33QIAN44SUN55LI96ZHOU0708109WAN6107数据链表尾结点数据链表尾结点数据链表头结点数据链表头结点space(1)备用空间链表头结点备用空间链表头结点space(0)备用空间链表尾结点备用空间链表尾结点space同时维护两个链表：备用空间链表同时维护两个链表：备用空间链表完成对一个链表

12、的插入操作完成对一个链表的插入操作同时完成对另一个链表的删除操作同时完成对另一个链表的删除操作 1、在下列各项叙述中，正确的说法是（）、在下列各项叙述中，正确的说法是（） A. 在线性表中，每个元素有且仅有一个直接前趋，在线性表中，每个元素有且仅有一个直接前趋，有且仅有一个直接后继有且仅有一个直接后继 B. 线性表中至少有一个元素线性表中至少有一个元素 C. 在线性表中，除第一个元素和最后一个元素之在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继有一个直接后继 D. 线性表中元素必须从大到小或从小到大排列

13、线性表中元素必须从大到小或从小到大排列 3、对于经常要存取线性表任意指定位置元素的应用，、对于经常要存取线性表任意指定位置元素的应用，线性表应采用的存储结构是线性表应采用的存储结构是（）（） a. 链式链式 b. 线性链表线性链表 c. 栈栈 d. 顺序顺序 2、用线性链表存储线性表时，要求存储空间（）、用线性链表存储线性表时，要求存储空间（） A. 连续不连续都可以连续不连续都可以 B. 部分元素的存储空间必须是连续的部分元素的存储空间必须是连续的 C. 必须是连续的必须是连续的 D. 必须是不连续的必须是不连续的 5、线性表的顺序存储结构是通过何种方式表示元素之间的关系、线性表的顺序存储结

14、构是通过何种方式表示元素之间的关系（）（） A. 保存左、右孩子地址保存左、右孩子地址 B. 后继元素的数组下标后继元素的数组下标 C. 元素的存储顺序元素的存储顺序 D. 保存后继元素地址保存后继元素地址 4、在下列对顺序表进行的操作中，算法时间复杂度为、在下列对顺序表进行的操作中，算法时间复杂度为 O(1) 的是的是（）（） a. 访问第访问第i个元素的前驱（个元素的前驱（1 next; p-next = s; s-next = r; b. p-next = s; s-next = p; c. s-next = p-next; p-next = s; d. 以上都不对以上都不对 8、在链式

15、存储结构中，体现数据之间关系的是（）、在链式存储结构中，体现数据之间关系的是（） a. 数据在内存的相对位置数据在内存的相对位置 b. 指示数据元素的指针指示数据元素的指针 c. 指针指针 d. 数据的存储地址数据的存储地址9、静态链表与动态链表相比，其缺点是（）、静态链表与动态链表相比，其缺点是（） a. 插入、删除时需移动较多数据插入、删除时需移动较多数据 b. 不能随机存取不能随机存取 c. 有可能浪费较多存储空间有可能浪费较多存储空间 d. 以上都不是以上都不是 10、若某线性表最常用的操作是在最后一个结点之、若某线性表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则

16、采用存储后插入一个结点或删除最后一个结点，则采用存储结构算法的时间效率最高的是（）结构算法的时间效率最高的是（） a. 单链表单链表 b. 给出表尾指针的单循环链表给出表尾指针的单循环链表 c. 双向链表双向链表 d. 给出表尾指针双向循环链表给出表尾指针双向循环链表 11、算法指的是算法指的是_。(A) (A) 计算方法计算方法 (B) (B) 排序方法排序方法 (C) (C) 查找方法查找方法 (D) (D) 解决问题的有限运算序列解决问题的有限运算序列 1212、算法设计需要达到的目标是算法设计需要达到的目标是 。（A A）正确性）正确性 （B B）高效率）高效率（C C）低存储）低存储

17、 （D D）全是）全是 1313、以下、以下 操作不是栈的基本运算。操作不是栈的基本运算。（A A） 删除栈顶元素删除栈顶元素 （B B） 删除栈底元素删除栈底元素（C C） 判断栈是否为空判断栈是否为空 （D D） 将栈置为空栈将栈置为空栈 1414、在顺序存储结构中，只要知道、在顺序存储结构中，只要知道 ，就可，就可在相同时间内求出任一结点的存储地址。在相同时间内求出任一结点的存储地址。（A A）基地址）基地址（B B）结点大小）结点大小（C C）向量大小）向量大小（D D）基地址和结点大小）基地址和结点大小 15、对于给定的对于给定的n n个元素，可以构造出的逻辑结构个元素，可以构造出的

18、逻辑结构有有 、 、 、 四种。四种。 16、单链表中指针单链表中指针P P所指结点不为尾结点的条件所指结点不为尾结点的条件是是 。 1717、在有头结点的单链表中，第、在有头结点的单链表中，第1 1个结点的地址存放个结点的地址存放 在（在（ ）中，其他结点的存储地址存放在前驱结中，其他结点的存储地址存放在前驱结点的点的 域中。域中。 栈和队列都是操作受限的栈和队列都是操作受限的线性表线性表 栈：栈： 限定仅能在表尾一端进限定仅能在表尾一端进行插入、删除操作的线行插入、删除操作的线性表；性表； 栈的特点栈的特点： 后进先出后进先出的线性表的线性表 LIFO-Last In First Outa

19、 an na a2 2a a1 1栈顶栈顶栈底栈底出栈出栈进栈进栈 队列：队列： 一端插入，另一端删一端插入，另一端删除除 从尾进，从头出从尾进，从头出 队列的特点：队列的特点： 先进先出的线性表先进先出的线性表 FIFO-First in First outa a1 1a an-1n-1a an n出队列出队列进队列进队列队首队首队尾队尾 Pop(&S, &e) ,Push(&S, e) 顺序栈：顺序栈： Push(&S, e)： *S.top+ = e Pop(&S, &e)： e = *-S.top;a a2 2a a1 1an-1basetop #define STACK_INIT_S

20、IZE 100 #define STACKINCREMENT 10 typedef struct SElemType *base; /栈底栈底 SElemType *top; /栈顶栈顶 int stacksize; /栈的大小栈的大小 SqStack; Pop(&S, &e) , Push(&S, e) 链式栈链式栈 Push(&S, e)：在链表开始插入一个新节点：在链表开始插入一个新节点 Pop(&S, &e)：删除链表第一个节点：删除链表第一个节点topa1 .ana2 EnQueue(&Q, e)，DeQueue(&Q, &e) 链式队列链式队列 EnQueue(&Q, e)：在链表

21、最后插入一个新节点：在链表最后插入一个新节点 DeQueue(&Q, &e)：删除链表第一个节点：删除链表第一个节点a1a2anfrontrear 顺序队列顺序队列 EnQueue(&Q, e)：队列尾指针加：队列尾指针加1 DeQueue(&Q, &e)：队列头指针加：队列头指针加1Q.baseQ.rearQ.front1 14 40 01 14 43 32 25 5J7J7J6J6J5J5Q.rearQ.front J1J1 J2J2 J3J3 Q.base循环顺序队列：注意判断队列循环顺序队列：注意判断队列空和满的条件空和满的条件 1、队列和栈的共同点是、队列和栈的共同点是 【 】 A.

22、 LIFO B. 都是线性表都是线性表 C. 无共同点无共同点 D. FIFO 2、若用一个大小为若用一个大小为 6 的数组来实现循环队列，且当前的数组来实现循环队列，且当前 rear 和和 front 的值分别为的值分别为0和和3 。当从队列中删除一个元素，再加入两。当从队列中删除一个元素，再加入两个元素后，个元素后， rear 和和 front 的值分别为的值分别为 【 】 A. 5和和1 B. 1和和5 C. 4和和2 D. 2和和4 3、向一个栈顶指针为向一个栈顶指针为 h 的带头结点链栈中插入指针的带头结点链栈中插入指针 s 所指的结点时，应执行的语句序列是所指的结点时，应执行的语句

23、序列是【 】 A. snext = h；h = hnext； B. snext = hnext；hnext = s； C. hnext = s； D. snext = h；4、对于循环队列，正确的是对于循环队列，正确的是 【 】 A. 无法判断队列是否为满无法判断队列是否为满 B. 循环队列不会满循环队列不会满 C. 无法判断队列是否为空无法判断队列是否为空 D. 以上说法都是错误的以上说法都是错误的 5、设、设 栈栈 S 和队列和队列 Q 的初始状态均为空，元素的初始状态均为空，元素 a, b, c, d, e, f, g 依次进入栈依次进入栈 S 。若每个元素出栈后立即进入队列。若每个元素

24、出栈后立即进入队列 Q ，且，且 7 个元素出队的顺序是个元素出队的顺序是 b, d, c, f, e, a, g ，则栈，则栈 S 的容量至少是的容量至少是 【 】 A. 2 B. 1 C. 3 D. 4 6、为解决计算机主机与打印机之间速度不匹配问题，通常设、为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是，结构应该是，【 】 A. 栈栈 B. 图图 C. 树树 D

25、. 队列队列 7、若一个栈的输入序列为、若一个栈的输入序列为 1 ， 2 ， 3 ， n ，输出序列，输出序列的第的第 1 个元素为个元素为 n ，则第，则第 i 个输出的元素是个输出的元素是( ) A. i B. ni C. ni+1 D. 可是其他任意元素可是其他任意元素 8、用不带头结点的单链表存储队列，其队头指针指向队头、用不带头结点的单链表存储队列，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时，结点，其队尾指针指向队尾结点，则在进行删除操作时，( ) A. 队头，队尾指针都要修改队头，队尾指针都要修改 B. 队头，队尾指针都可能要修改队头，队尾指针都可能要修改

26、C. 仅修改队头指针仅修改队头指针 D. 仅修改队尾指针仅修改队尾指针 9、一个栈的输入序列为：一个栈的输入序列为：1 2 3 4 5 ，则下列序列中，则下列序列中不可能的输出序列是，不可能的输出序列是， 【 】 A. 1 5 4 3 2 B. 5 4 2 3 1 C. 2 3 4 1 5 D. 2 3 1 4 5 10、在算符优先算法中，算符在算符优先算法中，算符和和（的优的优先关系应是，先关系应是， 【 】 A. （ 判断正误判断正误1. 在单链表中在单链表中,指向第一个结点的指针定义了该链表指向第一个结点的指针定义了该链表2. 能够通过在链表的表头不断插入新结点来创建一个能够通过在链表的

27、表头不断插入新结点来创建一个单向链表单向链表3. 堆栈和队列不属于线性表堆栈和队列不属于线性表4. 循环队列是一种物理结构循环队列是一种物理结构5. 删除单链表的最后一个结点需要遍历整个链表删除单链表的最后一个结点需要遍历整个链表YYNNY 1、向具有、向具有n个不同元素的链表中插入一个数据元素个不同元素的链表中插入一个数据元素,最坏情况下需要访问最坏情况下需要访问 个元素个元素? A n B n/2 C1 Dn/3 2、若链表中的元素有序、若链表中的元素有序,下列叙述哪一个正确下列叙述哪一个正确? A 找第找第k个元素的时间复杂度是个元素的时间复杂度是O(1) B 插入一个给定元素的时间复杂

28、度是插入一个给定元素的时间复杂度是O(n2) C 删除一个给定元素的时间复杂度是删除一个给定元素的时间复杂度是O(1) D 查找一个元素查找一个元素a是否属于链表的时间复杂度是是否属于链表的时间复杂度是O(n)AD 3、设栈的输入序列是、设栈的输入序列是1、2、3、4，则，则 不可能是不可能是其出栈序列：其出栈序列： A 1234 B 2134 C1432 D4312 4、若频繁地对线性表进行插入和删除操作，该线性、若频繁地对线性表进行插入和删除操作，该线性表应该采用表应该采用 存储结构。存储结构。 A散列散列 B顺序顺序 C链表链表 D任意任意DC 5、线性表中各个结点之间的地址、线性表中各

29、个结点之间的地址 。 A必须连续必须连续 B不一定连续不一定连续 C任意任意 6、在非空链表中，在由、在非空链表中，在由p指向的结点后面插入一个指向的结点后面插入一个由由q指向的结点过程是：指向的结点过程是： A p = q-next; p-next = q; B q-next = p-next; p-next = q; C q-next = p-next; p = q; D p-next = q; q-next = p;BB 7、若删除非空链表中由、若删除非空链表中由p所指向的结点的直接后继所指向的结点的直接后继结点的过程是：结点的过程是： A r = p-next; p-next = r;

30、 free(r); B r = p-next; p-next = r-next; free(r); C r = p-next; p = r-next; free(r); D p-next = p-next -next -next; 8、在非空双向循环链表中，在由、在非空双向循环链表中，在由q指向结点前插入指向结点前插入一个由一个由p指向的结点的过程是：指向的结点的过程是： p-right = q; p-left = q-left; q-left = p, ( ) . A q-left = p; B q-left-right = p; C p-right-right D p-left-right

31、 = p;BD 用静态链表实现的队列如用静态链表实现的队列如右图所示右图所示:front = 9, rear = 7. 队列有头结点队列有头结点 当执行下列操作时当执行下列操作时,队列队列有什么变化有什么变化? 1) 元素元素S入队入队 2) 队首元素出队队首元素出队0A11B32C43D64E105F76G87H08I09J210K5spacefrontrear0A31S02C43D64E105F76G87H18I09J210K5spacefrontrear0A21S02C33D64E105F76G87H18I09J410K5spacefrontrear1) 元素元素S入队入队2) 队首元素

32、出队队首元素出队cp = head;for( int i=1; idata); p = p-next; p = p-next;p = head;for( int i=1; idata); p = p-next; p = p-next; p = p-next;AECBDheadCEDABCBADE 已知长度为已知长度为n的线性表的线性表A=(a1, a2, , an)。请将线性。请将线性表转换为表转换为A=(an, an-1, , a1)。 1）请写出顺序表求逆的算法）请写出顺序表求逆的算法 2）请写出单链表求逆的算法）请写出单链表求逆的算法/顺序表求逆顺序表求逆void SqReverse(L

33、) / SqReversea1a2a3a4a5a6a7a8a9 m=n/2; ElemType tpElem; for( i=0; inext;r=NULL; while(p) q = p-next; p-next = r; r = p; p = q; L-next = r;a1 .ana2 1）已知线性表中的元素以值递增有序排列，并以单）已知线性表中的元素以值递增有序排列，并以单链表为存储结构。试写一高效算法，删除表中所有链表为存储结构。试写一高效算法，删除表中所有值大于值大于mink且小于且小于maxk的元素的元素.aiai+1ax 2）已知线性表中的元素以值递增有序排列，并以顺）已知线性

34、表中的元素以值递增有序排列，并以顺序表为存储结构。试写一高效算法，删除表中所有序表为存储结构。试写一高效算法，删除表中所有值大于值大于mink且小于且小于maxk的元素的元素 。aiaxax+1 3）若线性表中的元素排列是随机的，并以顺序表为）若线性表中的元素排列是随机的，并以顺序表为存储结构。试写一高效算法，删除表中所有值大于存储结构。试写一高效算法，删除表中所有值大于mink且小于且小于maxk的元素的元素 。 mink = 7 maxk =16371561211094148 球钟：一种通过小球来计时的设备。球钟：一种通过小球来计时的设备。 假设有一台机器，其中有一根管子，管子里顺序放假设有一台机器，其中有一根管子，管子里顺序放有有n个球，每分钟吐出一个球，现在通过它来计时个球，每分钟吐出一个球，现在通过它来计时 球钟有三个指示器：球钟有三个指示器：分钟指示器分钟指示器五分钟指示器五分钟指示器小时指示器小时指示器5:32 球钟的工作原理：球钟的工作原理： 1）每分钟机器从管子里吐出一个小球放到分钟指示）每分钟机器从管子里吐出一个小球放到分钟指示器。当放入第器。当放入第5个小球时