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

考试题型：

选择题、填空题、简答题、算法填空、算法设计、附加题

第一章 绪论

1. 在数据结构中，数据的基本单位是___ 答案：C

B.数据类型 D.数据变量 A.数据项 C.数据元素

2. 数据结构中数据元素之间的逻辑关系被称为___

B.数据的基本操作 D.数据的逻辑结构 C.程序的算法 A.数据的存储结构

3. 在定义ADT时，除数据对象和数据关系外，还需说明___

A.数据元素 D.数据项 C.基本操作 B.算法

4. 抽象数据类型的三个组成部分分别是：数据对象，__数据关系_，基本操作。

第二章 线性数据结构基础

1. 1.对定义“int a[2]；”的正确描述是（ ）。

A、定义一维数组a，包含a[1]和a[2]两个元素

B、定义一维数组a，包含a[0]和a[1]两个元素

C、定义一维数组a，包含a[0]、a[1]和a[2]三个元素 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的结果是____。

答案示例：(a,b,c)或()

3. 用S表示入栈操作，X表示出栈操作，若元素入栈的顺序是(d,l,g,k,a)，为了

得到(d,g,l,k,a)出栈序列，用相应的S和X表示的操作串为____。

答案示例：SSXXS

4. 3.1.5、用S表示入栈操作，X表示出栈操作，若元素入栈的顺序是(e,n,d,c,z)，

为了得到(d,z,c,n,e)出栈序列，用相应的S和X表示的操作串为____。

答案示例：SSXXS

5. 3.2.1、已知队列Q = (q,v,d,m,e,c)，EnQueue( Q, 'y' )操作之后队列Q的结果是

___。

答案形式：（a,b）

6. 若用一个长度为7的数组来表示循环队列，且当前front和rear的值分别是0

和1则该队列的长度是___。

7. 若用一个长度为6的数组来表示循环队列，且当前front和rear的值分别是1

和3当从队列中删除2个元素，再加上4个元素后，rear和front的值分别为___和___。

8. 以下操作不属于队列的操作是：___

B.构造空队列

A.队尾添加一个元素 C.取队列长度

D.删除队列中部的元素

9. 在队列中，允许进行插入操作的一端称为___

A.队首 C.栈顶 B.队尾 D.栈底

10. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是___

A.edcba B.decba D.abcde C.dceab

11. 下述哪一条是顺序存储结构的优点？___

B.插入运算方便 A.存储密度大 C.删除运算方便

D.可方便地用于各种逻辑结构的存储表示

12. 线性表是一种逻辑结构，下面的的叙述中哪一个是错误的？___

A.线性表采用顺序存储，必须占用一片连续的存储单元。 D.线性表采用链接存储，便于插入和删除操作。 B.线性表采用顺序存储，便于进行插入和删除操作。 C.线性表采用链接存储，不必占用一片连续的存储单元。

13. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和

删除运算，则利用（ ）存储方式最节省时间。___

D.单循环链表 B.双链表 A.顺序表

C.带头结点的双循环链表

第四章 线性结构的链式存储和实现

1. 如果用不带头结点的链表表示队列，则在做删除元素操作时，（ ）___

B.仅修改尾指针

C.头尾指针都要修改

D.仅将被删除元素结点的next域置为null A.仅修改头指针

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,63,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。表中已有4个结点： addr (15)=4;

addr (38)=5; addr (61)=6; addr (84)=7；如用二次探测再散列处理冲突，关键字为49的结点的地址是____。

A.8 D.9 C.5 B.3

2. 解决散列法中出现的冲突问题常采用的方法是______

B.数字分析法、除余法、线性探测法 C.数字分析法、线性探测法、多重散列法 D.线性探测法、多重散列法、链地址法 A.数字分析法、除余法、平方取中法

3. 设哈希函数为H(k)=key MOD 7，用线性探测法处理冲突。请画出依次插入

元素81，80，6，83，7，13，45后，该哈希表的状态，在各元素下面标出其冲突次数，并求出等概率情况下查找成功的平均查找长度是____。(若平均长度小数超过两位，请保留两位！)