广东工业大学2015数据结构复习题剖析

1、考试题型：选择题、填空题、简答题、算法填空、算法设计、附加题第一章绪论1. 在数据结构中，数据的基本单位是 _ 答案： CB. 数据类型D.数据变量A. 数据项C.数据元素2. 数据结构中数据元素之间的逻辑关系被称为 _B. 数据的基本操作D. 数据的逻辑结构C.程序的算法A. 数据的存储结构3. 在定义 ADT 时，除数据对象和数据关系外，还需说明 _A. 数据元素D.数据项C.基本操作B. 算法4. 抽象数据类型的三个组成部分分别是：数据对象， _数据关系 _，基本操作。第二章线性数据结构基础1.1.对定义“ int a2 ；”的正确描述是（）。A 、定义一维数组a，包含 a1 和 a2

2、两个元素B、定义一维数组a，包含 a0 和 a1 两个元素C、定义一维数组a，包含 a0 、 a1 和 a2 三个元素D、定义一维数组a，包含 a(0)、 a(1)和 a(2)三个元素2. 具有后进先出特点的结构是 _。A ） 栈B ） 队列C） 线性表D） 数组3. 具有先进先出特点的结构是 _。A ） 栈B ） 队列C） 线性表D） 数组第三章线性结构的顺序存储和实现1. 已知栈 S = (l , b , c , y) ，Pop( S,e )操作之后栈 S 的结果是 _。答案示例 ： (a,b,c)或 ()2.已知栈 S = (u,b,m,k,v)，Push( S, c )操作之后栈 S

3、的结果是 _。答案示例： (a,b,c)或 ()3. 用 S 表示入栈操作， X 表示出栈操作，若元素入栈的顺序是 (d,l,g,k,a)，为了得到 (d,g,l,k,a)出栈序列，用相应的S 和 X 表示的操作串为 _。答案示例： SSXXS4. 3.1.5、用 S 表示入栈操作， X 表示出栈操作， 若元素入栈的顺序是 (e,n,d,c,z)，为了得到 (d,z,c,n,e)出栈序列，用相应的S 和 X 表示的操作串为 _。答案示例： SSXXS5. 3.2.1、已知队列 Q = (q,v,d,m,e,c)，EnQueue( Q, y )操作之后队列 Q 的结果是_。答案形式：（ a,b）

4、6. 若用一个长度为 7 的数组来表示循环队列， 且当前 front 和 rear 的值分别是 0和 1 则该队列的长度是 _。7. 若用一个长度为 6 的数组来表示循环队列， 且当前 front 和 rear 的值分别是 1和 3 当从队列中删除 2 个元素，再加上 4 个元素后， rear 和 front 的值分别为_和 _。8. 以下操作不属于队列的操作是： _B. 构造空队列A. 队尾添加一个元素D. 删除队列中部的元素9. 在队列中，允许进行插入操作的一端称为 _A. 队首B. 队尾D. 栈底10. 一个栈的入栈序列是 a,b,c,d,e，则栈的不可能的输出序列是 _A.edcbaB

5、.decbaD.abcdeC.dceab11. 下述哪一条是顺序存储结构的优点？ _B. 插入运算方便A. 存储密度大C.删除运算方便D. 可方便地用于各种逻辑结构的存储表示12. 线性表是一种逻辑结构，下面的的叙述中哪一个是错误的？_A. 线性表采用顺序存储，必须占用一片连续的存储单元。D. 线性表采用链接存储，便于插入和删除操作。B. 线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储，不必占用一片连续的存储单元。13. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。_D. 单循环链表B. 双链表A. 顺序表C.带头

6、结点的双循环链表第四章线性结构的链式存储和实现1. 如果用不带头结点的链表表示队列，则在做删除元素操作时， （）_B. 仅修改尾指针C.头尾指针都要修改D. 仅将被删除元素结点的next 域置为 nullA. 仅修改头指针2. 链式实现中队列为空时， front 和 rear 指针是否可以相等： _C.不清楚D. 以上都不A. 可以相等B. 不可以相等3. 在链式存储结构中是否存在“空间已满”的情况？ _A. 存在C.不一定B. 不存在第五章排序基础1. 基数排序的时间复杂度是 _C.O(nlog n)D.O(d(n+rd)B.O(log n)A.O(n*n)2. 对序列 74,29,58,6

7、3,90,98,41执行升序的简单插入算法， 写出排序中各趟的结果是 _。3. 对序列 13,25,96,76,75,47,8执行降序的希尔排序算法， 增量序列为（ 5，3，1），写出排序中各趟的结果是 _。4.5.插入排序算法是（稳定或不稳定）_的排序算法。给定关键字序列 483， 35，126，86， 678，257， 513，750， 680， 226，执行三趟希尔排序，设增量序列为5,3,1 ，请依次写出每一趟的排序结果。第六章哈希表1. 设哈希表长 m=14，哈希函数 H(key)=key%11。表中已有 4 个结点： addr (15)=4; addr (38)=5; addr (

8、61)=6; addr (84)=7；如用二次探测再散列处理冲突， 关键字为 49 的结点的地址是 _。A.8D.9C.5B.32. 解决散列法中出现的冲突问题常采用的方法是 _B. 数字分析法、除余法、线性探测法C.数字分析法、线性探测法、多重散列法D. 线性探测法、多重散列法、链地址法A. 数字分析法、除余法、平方取中法3. 设哈希函数为 H(k)=key MOD 7，用线性探测法处理冲突。请画出依次插入元素 81， 80，6，83，7， 13，45 后，该哈希表的状态，在各元素下面标出其冲突次数，并求出等概率情况下查找成功的 平均查找长度 是 _。 (若平均长度小数超过两位，请保留两位！

9、 )4. 设哈希函数为 H(k)=key MOD 7，用二次探测法处理冲突。请画出依次插入元素 1，71， 99，20，9， 27，75 后，该哈希表的状态，在各元素下面标出其冲突次数，并求出等概率情况下查找成功的平均查找长度是 _。5. 将关键字序列： (19,14,1,29,20,23,57,11,10)，存入用数组 A0.12 实现的哈希表(见下表 )，设哈希函数为： H0= key MOD 11 ，按线性探测再散列法处理冲突： Hi=(H0+di ) MOD 13 。要求：(1) 填写关键字序列的存储情况；0123456789101112(2) 请写出在哈希表 A 中查找给定值 K=5

10、7 的过程中，所求得的哈希地址序列。第七章递归1. 在有 5 个互不相同元素的有序表 A1. 5中折半查找值等于 A1 的元素，被比较的元素的下标依次为 _。2. 在序列 2, 5, 8, 11, 18 , 23, 31, 39, 46, 55, 79, 92, 99中，用折半查找（二分查找）算法查找是否存在关键字 13，写出相应的各趟结果。并写出以 C 语言描述的完整算法，测试通过3. 在对长度为 7 的有序表进行折半查找， 其等概率时查找成功的平均查找长度是_。结果保留三位有效数字4. 对序列 31,35,19,34,77,30,0 执行升序的归并排序，写出三次调用过程 Merge的排序结

11、果是 _。5. 归并排序算法的平均时间复杂度是 _，最坏情况时间复杂度是 _，辅助存储空间是 _。6. 对序列 46,19,47,12,35,23,7, 1, 99, 62, 57, 86执行升序的一趟快速排序，设其中第一个元素 46 为枢轴，写出一趟快速排序结果是_。并写出以 C 语言描述的完整算法，测试通过7. 对序列 35,20,88,6,54,60,80执行升序的快速排序， 写出三次调用过程 Partition的排序结果是 _。8. 快速排序算法的平均时间复杂度是 _，最坏情况时间复杂度是 _，辅助存储空间是 _。9. 某内排序方法的稳定性是指 _B.该排序算法允许有相同的关键字记录A

12、. 该排序算法不允许有相同的关键字记录C.平均时间为0（ n log n ）的排序方法D.执行排序算法之后，相等的关键字的原有位置顺序不变。10. 针对下述快速排序算法，请进行代码填空。int Partition (SqList &L,int low,int high)int pivotkey;L.r0 = L.rlow;pivotkey = L.rlow.key;while(_(1)_)while(low=pivotkey)_(2)_;L.rlow = L.rhigh;while(lowhigh&L.rlow.key=pivotkey)_(3)_;L.rhigh = L.rlow;L.rlo

13、w = L.r0;return low;void QSort (RedType & R,int s,intt )if(s 3）B 树，若不为空树， 则树中的每个结点至多有 _棵子树。A.m-1B.mC.m+1D.以上都不是4. 并查集的合并操作所需的时间主要取决于树的 _；有两种方法可优化算法效率，分别是 _和_；5.在一棵 m 阶 B 树中，若某结点的原有关键字个数等于_，则插入一个新关键字将导致该结点分裂；若某结点及相邻兄弟结点的原有的关键字的个数等于 _，则删除一个关键字而导致结点合并。第十章图1. 任何一个带权的无向连通图的最小生成树 _A. 只有一棵B.有一棵或多棵C.一定有多棵D.

14、 可能不存在2. 具有 N 个顶点的无向图至多有（）条边。 _A. NB. N*(N 1)C. N*(N 1)/2D. 2N3. 有 n 个顶点的无权无向图 , 采用邻接数组表示 , 图中的边数与邻接矩阵中非零元素之和的关系是 _A.1 / 2B. 相等C.2 倍D. 不确定4. 不带权的有向图中顶点 V i 的度等于其邻接矩阵中 _；A .第 i 行中的非0 元的个数；B. 第 i 列中的非 0 元的个数；C. 第 i 行中的非 0 元的个数 + 第 i 列中的非 0 元的个数；D. 不能确定5. 已知无向图 G 如图所示，从顶点 A 开始，分别写出深度优先搜索序列和广度优先搜索序列。6.

15、包含 8 个顶点的连通图的生成树有 _个顶点， _条边。7. 已知某无向图对应的邻接矩阵如下所示， 可得该图有 _个顶点 , _条边，其中顶点 E 的度是 _。8.已知某有向图对应的邻接矩阵如下所示，可得该图有_个顶点 _条边，其中顶点 F 的出度是 _，入度是 _，度是 _。9. 已知图 G 如图所示，其对应的邻接表共有 _个头结点， _个表结点。10. 已知某图的邻接矩阵如图所示，从顶点A 出发对图进行深度优先搜索，得到的顶点序列为 _。从顶点 A 出发对图进行广度优先搜索，得到的顶点序列为 _。分别写出 DFS 和 BFS 用 C 语言描述的算法。11. 已知某图的邻接表如图所示， 从顶点 A 出发对图进行广度优先搜索， 得到的顶点序列为