中南大学计算机数据结构试题参考答案讲解学习

中南大学现代远程教育课程考试（考试）复习题及参考答案数据结构(使用教材：余腊生编著，人民邮电出版社出版，《数据结构—基于C++模板类的实现》一、判断题1．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。

[ ] 2．链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。

[ ]3．在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。

[ ] 4．通常递归的算法简单、易懂、容易编写，而且执行的效率也高。

[ ] 5．一个广义表的表尾总是一个广义表。

[ ] 6．当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。

[ ] 7．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）。

[ ] 8．存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。

[ ] 9．直接选择排序是一种稳定的排序方法。

[ ] 10．30、闭散列法通常比开散列法时间效率更高。

[ ] 11．有n个结点的不同的二叉树有n!棵。

[ ] 12．直接选择排序是一种不稳定的排序方法。

[ ] 13．在2048个互不相同的关键码中选择最小的5个关键码，用堆排序比用锦标赛排序更快。

[ ] 14．当3阶B_树中有255个关键码时,其最大高度(包括失败结点层)不超过8。

[ ] 15．一棵3阶B_树是平衡的3路搜索树,反之,一棵平衡的3路搜索树是3阶非B_树。

[ ] 16．在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。

在设计再散列函数时，要求计算出的值与表的大小m互质。

[ ] 17．在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。

[ ] 18．折半搜索只适用于有序表，包括有序的顺序表和有序的链表。

第10章内部排序习题练习答案1.以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。

(1) 直接插入排序(2)希尔排序(3)冒泡排序(4)快速排序(5) 直接选择排序(6) 堆排序(7) 归并排序(8)基数排序上述方法中，哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例。

答：(1)直接插入排序:(方括号表示无序区)初始态: 265[301 751 129 937 863 742 694 076 438]第一趟：265 301[751 129 937 863 742 694 076 438]第二趟：265 301 751[129 937 863 742 694 076 438]第三趟：129 265 301 751[937 863 742 694 076 438]第四趟：129 265 301 751 937[863 742 694 076 438]第五趟：129 265 301 751 863 937[742 694 076 438]第六趟：129 265 301 742 751 863 937[694 076 438]第七趟：129 265 301 694 742 751 863 937[076 438]第八趟：076 129 265 301 694 742 751 863 937[438]第九趟：076 129 265 301 438 694 742 751 863 937(2)希尔排序(增量为5，3，1)初始态: 265 301 751 129 937 863 742 694 076 438第一趟：265 301 694 076 438 863 742 751 129 937第二趟：076 301 129 265 438 694 742 751 863 937第三趟：076 129 265 301 438 694 742 751 863 937(3)冒泡排序(方括号为无序区)初始态[265 301 751 129 937 863 742 694 076 438]第一趟：076 [265 301 751 129 937 863 742 694 438]第二趟：076 129 [265 301 751 438 937 863 742 694]第三趟：076 129 265 [301 438 694 751 937 863 742]第四趟：076 129 265 301 [438 694 742 751 937 863]第五趟：076 129 265 301 438 [694 742 751 863 937]第六趟：076 129 265 301 438 694 742 751 863 937(4)快速排序：（方括号表示无序区，层表示对应的递归树的层数）初始态：[265 301 751 129 937 863 742 694 076 438]第二层：[076 129] 265 [751 937 863 742 694 301 438] 第三层：076 [129] 265 [438 301 694 742] 751 [863 937] 第四层：076 129 265 [301] 438 [694 742] 751 863 [937] 第五层：076 129 265 301 438 694 [742] 751 863 937第六层：076 129 265 301 438 694 742 751 863 937 (5)直接选择排序：(方括号为无序区)初始态[265 301 751 129 937 863 742 694 076 438]第一趟：076 [301 751 129 937 863 742 694 265 438]第二趟：076 129 [751 301 937 863 742 694 265 438]第三趟：076 129 265[ 301 937 863 742 694 751 438]第四趟：076 129 265 301 [937 863 742 694 751 438]第五趟：076 129 265 301 438 [863 742 694 751 937]第六趟：076 129 265 301 438 694 [742 751 863 937]第七趟：076 129 265 301 438 694 742 [751 863 937]第八趟：076 129 265 301 438 694 742 751 [937 863]第九趟：076 129 265 301 438 694 742 751 863 937(6)堆排序：（通过画二叉树可以一步步得出排序结果）初始态[265 301 751 129 937 863 742 694 076 438]建立初始堆：[937 694 863 265 438 751 742 129 075 301]第一次排序重建堆：[863 694 751 765 438 301 742 129 075] 937第二次排序重建堆：[751 694 742 265 438 301 075 129] 863 937第三次排序重建堆：[742 694 301 265 438 129 075] 751 863 937第四次排序重建堆：[694 438 301 265 075 129] 742 751 863 937第五次排序重建堆：[438 265 301 129 075] 694 742 751 863 937第六次排序重建堆：[301 265 075 129] 438 694 742 751 863 937第七次排序重建堆：[265 129 075] 301 438 694 742 751 863 937第八次排序重建堆：[129 075]265 301 438 694 742 751 863 937第九次排序重建堆：075 129 265 301 438 694 742 751 863 937(7)归并排序（为了表示方便，采用自底向上的归并，方括号为有序区）初始态：[265] [301] [751] [129] [937] [863] [742] [694] [076] [438]第一趟：[265 301] [129 751] [863 937] [694 742] [076 438]第二趟：[129 265 301 751] [694 742 863 937] [076 438]第三趟：[129 265 301 694 742 751 863 937] [076 438]第四趟：[076 129 265 301 438 694 742 751 863 937](8)基数排序（方括号内表示一个箱子共有10个箱子，箱号从0到9）初始态：265 301 751 129 937 863 742 694 076 438第一趟：[] [301 751] [742] [863] [694] [265] [076] [937] [438] [129]第二趟：[301] [] [129] [937 438] [742] [751] [863 265] [076] [] [694]第三趟：[075] [129] [265] [301] [438] [] [694] [742 751] [863] [937]在上面的排序方法中，直接插入排序、冒泡排序、归并排序和基数排序是稳定的，其他排序算法均是不稳定的，现举实例如下：以带*号的表示区别。

第7章图(基础知识)习题练习答案7.1 在图7.23所示的各无向图中：(1)找出所有的简单环。

(2)哪些图是连通图?对非连通图给出其连通分量。

(3)哪些图是自由树(或森林)?答:(1)所有的简单环：(同一个环可以任一顶点作为起点)(a)1231(b)无(c)1231、2342、12341(d)无(2)连通图：(a)、(c)、(d)是连通图，(b)不是连通图，因为从1到2没有路径。

具体连通分量为：(3)自由树(森林)：自由树是指没有确定根的树，无回路的连通图称为自由树：(a)不是自由树，因为有回路。

(b)是自由森林，其两个连通分量为两棵自由树。

(c)不是自由树。

(d)是自由树。

7.2 在图7.24(下图)所示的有向图中：(1) 该图是强连通的吗? 若不是，则给出其强连通分量。

(2) 请给出所有的简单路径及有向环。

(3) 请给出每个顶点的度，入度和出度。

(4) 请给出其邻接表、邻接矩阵及逆邻接表。

答：(1)该图是强连通的，所谓强连通是指有向图中任意顶点都存在到其他各顶点的路径。

(2)简单路径是指在一条路径上只有起点和终点可以相同的路径：有v1v2、v2v3、v3v1、v1v4、v4v3、v1v2v3、v2v3v1、v3v1v2、v1v4v3、v4v3v1、v3v1v4、另包括所有有向环,有向环如下：v1v2v3v1、v1v4v3v1(这两个有向环可以任一顶点作为起点和终点)(3)每个顶点的度、入度和出度：D(v1)=3ID(v1)=1OD(v1)=2D(v2)=2 ID(v2)=1OD(v2)=1D(v3)=3 ID(v3)=2OD(v3)=1D(v4)=2 ID(v4)=1OD(v4)=1(4)邻接表：(注意边表中邻接点域的值是顶点的序号，这里顶点的序号是顶点的下标值-1)vertex firstedge next┌─┬─┐┌─┬─┐┌─┬─┐0│v1│─→│ 1│─→│ 3│∧│├─┼─┤├─┼─┤└─┴─┘1│v2│─→│ 2│∧│├─┼─┤├─┼─┤2│v3│─→│ 0│∧│├─┼─┤├─┼─┤3│v4│─→│ 2│∧│└─┴─┘└─┴─┘逆邻接表：┌─┬─┐┌─┬─┐0│v1│─→│ 2│∧│├─┼─┤├─┼─┤1│v2│─→│ 0│∧│├─┼─┤├─┼─┤┌─┬─┐2│v3│─→│ 1│─→│ 3│∧│├─┼─┤├─┼─┤└─┴─┘3│v4│─→│ 0│∧│└─┴─┘└─┴─┘邻接矩阵：0 1 0 10 0 1 01 0 0 00 0 1 07.3 假设图的顶点是A,B...，请根据下述的邻接矩阵画出相应的无向图或有向图。

班号学号姓名成绩中南大学? 数据库系统概论?期末考试卷考前须知：1、考试时间2小时；2、答案写在答题纸上一：单项选择题(本大题共12小题，每题3分，共36分)1. 对现实世界进行第一层抽象的是【 D 】A. 用户数据模型B. 物理数据模型C. 逻辑数据模型D. 概念数据模型2. 以下不属于集合运算的是________。

【 C 】A. 并B. 广义笛卡尔积C. 除D. 差3. 假设一个关系有函数依赖集〔AB→CD, A→D〕，则可确定它最高属于：【 A 】A. 1NFB. 2NFC. 3NFD. BCNF4. 以下哪个SQL语句没有语法错误【 A 】A. Grant select on TableA to User1 with grant optionB. select count(a) from b where count(a)>3C. insert into TableA set a=1, b=2D. drop TableA where a=15. 定义学生对象来表示张三、李四等学生个体，这种抽象方法被称为【A】A. 分类B. 聚集C. 类比D. 概括6. 哪一级封锁协议解决了读脏数据问题？【B】A. 一级封锁协议B. 二级封锁协议C. 三级封锁协议D. 以上都不是7. 工资表〔职工号，岗位级别，岗位工资〕中有如下约束：岗位级别低的职工的岗位工资应低于岗位级别高的职工的岗位工资。

这种约束属于什么约束类型？【E】A. 静态列级约束B. 动态列级约束C. 静态元组约束D. 动态元组约束E. 静态关系约束F. 动态关系约束8. 设有关系R〔A，B，C〕的值如下：A B C1 4 11 2 44 3 4以下表达正确的选项是：【 D 】A. 关系中存在函数依赖A→CB. 关系中存在函数依赖BC→AC. 关系中存在函数依赖C→AD. 无法获知函数依赖关系9．有关系模式A (a, b, c, d, e, f)，存在如下函数依赖集：F={(a)→b，(a, c)→d，(c, d)→e, (e)→f }可知其候选键是【 B 】A. (a, c, e)B. (a, c)C. (b, d, f)D. (a, c, d, e)10．如果有5个不同的实体，存在5个不同的二元联系，其中2个为1：1联系，3个为M：N 联系，那么根据转换规则，转换出来的关系表个数不可能是：【 A 】A. 7个B.8个C.9个D. 10个11. 以下不属于数据库保护数据安全的机制的是：【 A 】A. 索引B. 并发控制C. 存取控制D. 数据完整性约束12. 以下属于数据库逻辑结构设计阶段工作内容的是：【 C 】I.数据字典II. 范式分解III. ER图IV. 数据流图V. 用户模式A. I, IVB. II, III, VC. II, VD. I, III, IV二：简答题：(3题，每题6分)1.试述数据库三层模式结构的含义。

中南大学现代远程教育课程考试<专科）复习题及参考答案数据结构一、判断题：1．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。

< ）2．链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。

< ）3．在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。

( >4．折半搜索只适用于有序表，包括有序的顺序表和有序的链表。

( >5．如果两个串含有相同的字符，则这两个串相等。

<）6．数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。

<）7．在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。

< ）8．通常递归的算法简单、易懂、容易编写，而且执行的效率也高。

< ）9．一个广义表的表尾总是一个广义表。

< ）10．当从一个小根堆<最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。

< ）11．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O<h）。

< ）12．存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。

< ）13．直接选择排序是一种稳定的排序方法。

< ）14．闭散列法通常比开散列法时间效率更高。

< ）15．有n个结点的不同的二叉树有n!棵。

( >16．直接选择排序是一种不稳定的排序方法。

( >17．在2048个互不相同的关键码中选择最小的5个关键码，用堆排序比用锦标赛排序更快。

( >18．当3阶B_树中有255个关键码时,其最大高度(包括失败结点层>不超过8。

( >19．一棵3阶B_树是平衡的3路搜索树,反之,一棵平衡的3路搜索树是3阶非B_树。

中南大学计算机数据结构2013试题参考答案中南大学考试试卷2015--2016学年上学期期末考试试题时间100分钟数据结构课程56学时3.5学分考试形式：闭卷专业年级：计算机科学与技术10级总分100分，占总评成绩70%姓名班级学号（本试卷共四道大题，答案全部做在答题纸上！）一、选择题(每题2分，共24分)1.以下数据结构中，属于线性结构的是（）A．图B．栈C．二分查找树D．森林2.用二分法查找表(a0,a1,a2,a3,……a16)，需要比较2次才能找到的元素是（）A．a7和a16 B．a11和a13C．a1和a14 D．a3和a123.用概率查找改进查找效率，是经过多次查找以后使得（）A．查找次数越少的元素查找速度越快B．查找次数越少的元素越往前存放C．查找次数越多的元素越往后存放D．查找次数越多的元素查找速度越快4.二分查找要求元素( )A.有序、顺序存储B.有序、链式存储C.无序、顺序存储D.无序、链式存储5.已知pPre为指向链表中某结点的指针，pNew是指向新结点的指针，以下哪段伪码算法是将一个新结点插入到链表中pPre所指向结点的后面？（）A．pPre->link = pNew; pNew = null;B．pPre->link = pNew->link; pNew->link = null;C．pNew->link = pPre->link; pPre->link = pNew;D．pNew->link = pPre->link; pPre->link = null;6.在递归算法执行过程中，计算机系统必定会用到的数据结构是（）A．队列B．链表C．栈D．二叉树7.一个队列的入列序为ABCD，则队列的可能输出序列为（）A．DCBA B．ABCDC．ADCB D．CBDA8.具有10个叶子结点的二叉树中有（）个度为2的结点A．8 B．9C．10 D．119.若A=10，B=4，C=6，D=4，E=15则后缀表达式“AB*CD+-E+”的值为( )。

中南大学网络教育课程考试复习题及参考答案数据结构一、填空 :1.设需要对 5 个不同的记录关键字进行排序，则至少需要比较________次，至多需要比较 __________ 次。

2.设二叉排序树的高度为h，则在该树中查找关键字key 最多需要比较 _________次。

3.设在长度为 20 的有序表中进行二分查找，则比较一次查找成功的结点数有_________个，比较两次查找成功有结点数有 _________个。

4.数据结构从逻辑上划分为三种基本类型：___________、__________ 和 ___________。

5.在一个具有 n 个顶点的无向完全图中，包含有________条边，在一个具有 n 个顶点的有向完全图中，包含有 ________条边。

6.向一棵 B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。

7.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为 ________。

8.在快速排序、堆排序、归并排序中，_________排序是稳定的。

9.在有 n 个叶子结点的哈夫曼树中，总结点数是_______ 。

10.一棵树 T 采用二叉链表存储，如果树T 中某结点为叶子结点，则在二叉链表BT 中所对应的结点一定_______。

11.3. 已知数组 A［10］［ 10］为对称矩阵，其中每个元素占5个单元。

现将其下三角部分按行优先次序存储在起始地址为 1000 的连续的内存单元中，则元素A［ 5， 6］对应的地址是 _______。

12.在有 n 个结点的无向图中，其边数最多为_______。

13.取出广义表 A=(x,(a,b,c,d))中原子 x的函数是 _______。

14.对矩阵采用压缩存储是为了_______。

15.带头结点的双循环链表 L 为空表的条件是 _______。

16.设线性表中元素的类型是实型，其首地址为1024 ，则线性表中第 6 个元素的存储位置是。

数据结构习题集答案（C 语言版 严蔚敏主编）第1章 绪论1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

是对一般数据类型的扩展。

1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。

一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。

抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。

在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。

1.3 设有数据结构(D,R)，其中{}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r =试按图论中图的画法惯例画出其逻辑结构图。

解：1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。

解：ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={<r,i>} 基本操作： InitComplex(&C,re,im)操作结果：构造一个复数C ，其实部和虚部分别为re 和imDestroyCmoplex(&C)操作结果：销毁复数CGet(C,k,&e)操作结果：用e返回复数C的第k元的值Put(&C,k,e)操作结果：改变复数C的第k元的值为eIsAscending(C)操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0 IsDescending(C)操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0 Max(C,&e)操作结果：用e返回复数C的两个元素中值较大的一个Min(C,&e)操作结果：用e返回复数C的两个元素中值较小的一个}ADT ComplexADT RationalNumber{数据对象：D={s,m|s,m为自然数，且m不为0}数据关系：R={<s,m>}基本操作：InitRationalNumber(&R,s,m)操作结果：构造一个有理数R，其分子和分母分别为s和mDestroyRationalNumber(&R)操作结果：销毁有理数RGet(R,k,&e)操作结果：用e返回有理数R的第k元的值Put(&R,k,e)操作结果：改变有理数R的第k元的值为eIsAscending(R)操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0 IsDescending(R)操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0 Max(R,&e)操作结果：用e返回有理数R的两个元素中值较大的一个Min(R,&e)操作结果：用e返回有理数R的两个元素中值较小的一个}ADT RationalNumber1.5 试画出与下列程序段等价的框图。

中南大学十套数据结构试题及答案数据结构试卷(1)................1数据结构试卷(2)................4数据结构试卷(3)................6数据结构试卷(4)................8数据结构试卷(5)................11数据结构试卷(6)................14数据结构试卷(7)................16数据结构试卷(8)................18数据结构试卷(9)................20数据结构试卷(10)................2 3数据结构试卷(1)参考答案.........26数据结构试卷(2)参考答案 (27)数据结构试卷(3)参考答案.........28数据结构试卷(4)参考答案 (30)数据结构试卷(5)参考答案.........32数据结构试卷(6)参考答案 (33)数据结构试卷(7)参考答案.........36数据结构试卷(8)参考答案...37数据结构试卷(9)参考答案.........38数据结构试卷(10)参考答案 (39)数据结构试卷(1)1，单项题(每题2分，共20分)1。

堆栈和队列的共同特征是()A.仅允许在端点b插入和删除元素。

所有元素都是先进先出。

所有元素都是先进先出。

没有公共基础2。

以链接方式存储的队列。

在插入操作过程中()。

A .只应修改头部指针b。

头指针和尾指针都应该修改c .只有尾指针d .头指针和尾指针都应该修改3。

下列哪种数据结构是非线性结构？()队列b堆栈c线性表d二叉树4。

有一个二维数组[m][n]。

假设[0][0]存储在644(10)中，[2][2]存储在676(10)中。

每个元素占据一个空间。

问一问[3][3)(10)它储存在哪里？脚注(10)用十进制表示a . 688b . 678c . 692d . 6965。

这棵树最适合用来代表()a .有序数据元素b .无序数据元素c .元素之间具有分支层次关系的数据d .元素之间没有连接的数据6。

中南⼤学数据结构与算法第5章数组和⼴义表课后作业答案第5章数组与⼴义表习题练习答案5.1请按⾏及按列优先顺序列出四维数组A2*3*2*3的所有元素在内存中的存储次序，开始结点为a0000。

解：按⾏优先的顺序排列时，先变化右边的下标，也就是右到左依次变化，这个四维数组的排列是这样的：(将这个排列分⾏写出以便与阅读，只要按从左到右的顺序存放就是在内存中的排列位置) a0000a0001a0002a0010a0011a0012a0100a0101a0102a0110a0111a0112a0200a0201a0202a0210a0211a0212a1000a1001a1002a1010a1011a1012a1100a1101a1102a1110a1111a1112a1200a1201a1202a1210a1211a1212按列优先的顺序排列恰恰相反，变化最快的是左边的下标，然后向右变化，所以这个四维数组的排列将是这样的，(这⾥为了便于阅读，也将其书写为分⾏形式)：a0000a1000a0100a1100a0200a1200a0010a1010a0110a1110a0210a1210a0001a1001a0101a1101a0201a1201a0011a1011a0111a1111a0211a1211a0002a1002a0102a1102a0202a1202a0012a1012a0112a1112a0212a02125.2 给出C语⾔的三维数组地址计算公式。

解：因为C语⾔的数组下标下界是0，所以Loc(A mnp)=Loc(A000)+((i*n*p)+k)*d其中Amnp表⽰三维数组。

Loc(A000)表⽰数组起始位置。

i、j、k表⽰当前元素的下标,d表⽰每个元素所占单元数。

5.3设有三对⾓矩阵A n*n，将其三条对⾓线上的元素逐⾏地存储到向量B[0...3n-3]中，使得B[k]=a ij,求：(1)⽤i , j 表⽰k的下标变换公式。

数据结构试卷（一） (1)数据结构试卷（二） (5)数据结构试卷（三） (9)数据结构试卷（四） (14)数据结构试卷（五） (19)数据结构试卷（六） (24)数据结构试卷（七） (28)数据结构试卷（八） (32)数据结构试卷（九） (36)数据结构试卷（十）.......................... 41 数据结构试卷（一）参考答案. (47)数据结构试卷（二）参考答案 (48)数据结构试卷（三）参考答案 (51)数据结构试卷（四）参考答案 (54)数据结构试卷（五）参考答案 (58)数据结构试卷（六）参考答案 (60)数据结构试卷（七）参考答案 (64)数据结构试卷（八）参考答案 (66)数据结构试卷（九）参考答案 (69)数据结构试卷（十）参考答案 (71)数据结构试卷（一）一、单选题（每题2 分，共20分）1.栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

A．688 B．678 C．692 D．6965.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

2022年中南大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（）。

A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next2、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。

A.5B.6C.8D.93、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。

A.单链表B.双向链表C.单循环链表D.顺序表4、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。

A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)5、下面关于串的叙述中，不正确的是（）。

A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储6、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。

下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ7、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。

A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，198、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。

A.107B.108C.214D.2159、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。

A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（）。

第9章查找习题练习答案1.对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较?答：设变量max和min用于存放最大元和最小元(的位置)，第一次取两个元素进行比较，大的放入max，小的放入min。

从第2次开始，每次取一个元素先和max比较，如果大于max则以它替换max，并结束本次比较；若小于max则再与min相比较，在最好的情况下，一路比较下去都不用和min相比较，所以这种情况下，至少要进行n-1次比较就能找到最大元和最小元。

2.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：(1)查找不成功，即表中无关键字等于给定值K的记录；(2)查找成功，即表中有关键字等于给定值K的记录。

答：查找不成功时，需进行n+1次比较才能确定查找失败。

因此平均查找长度为n+1，这时有序表和无序表是一样的。

查找成功时，平均查找长度为(n+1)/2,有序表和无序表也是一样的。

因为顺序查找与表的初始序列状态无关。

3.画出对长度为18的有序的顺序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。

答：等概率情况下，查找成功的平均查找长度为：ASL=(1+2*2+3*4+4*8+5*3)/18=3.556查找失败时，最多的关键字比较次树不超过判定树的深度，此处为5.4.为什么有序的单链表不能进行折半查找?答：因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。

5.设有序表为(a,b,c,e,f,g,i,j,k,p,q),请分别画出对给定值b,g和n进行折半查找的过程。

解：(1)查找b的过程如下(其中方括号表示当前查找区间，圆括号表示当前比较的关键字)下标： 1 2 3 4 5 6 7 8 9 10 11 12 13第一次比较： [a b c d e f (g) h i j k p q]第二次比较： [a b (c) d e f] g h i j k p q第三次比较： [a (b)]c d e f g h i j k p q经过三次比较，查找成功。

(一) 单选题1. 用邻接表表示图进行深度优先遍历时，通常是采用（）来实现算法的。

(A) 栈(B) 队列(C) 树(D) 图参考答案： (A)2. 设图的邻接链表如图所示，则该图的边的数目是（）。

(A) 4(B)5 (C) 10(D) 20参考答案： (B)3. 若采用邻接矩阵翻存储一个n 个顶点的无向图，则该邻接矩阵是一个（）。

(A)上三角矩阵(B)稀疏矩阵(C)对角矩阵(D)对称矩阵参考答案： (D)4.无向图,其中：，对该图进行深度优先遍历，得到的顶点序列正确的是（）。

(A)a,b,e,c,d,f (B)a,c,f,e,b,d (C)a,e,b,c,f,d(D)a,e,d,f,c,b参考答案： (D)5. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p ，p 的右子树结点个数为n,森林F 中第一棵子树的结点个数是（）。

(A)(B)(C)(D) 条件不足，无法确定参考答案： (A)6. 关键路径是事件结点网络中（）。

(A) 从源点到汇点的最长路径(B) 从源点到汇点的最短路径(C) 最长回路(D) 最短回路参考答案： (A)7. 树最适合用来表示（）。

(A)有序数据元素(B) 无序数据元素(C) 元素之间具有分支层次关系的数据(D) 元素之间无联系的数据参考答案：(C)8. 在一棵具有n个结点的二叉链表中，所有结点的空域个数等于（）。

(A)n(B)(C)(D)参考答案：(C)9. 在一个非空二叉树的中序遍历序列中，根结点的右边（）。

(A)只有右子树上的所有结点(B) 只有右子树上的部分结点(C) 只有左子树的上的部分结点(D) 只有左子树上的所有结点参考答案：(A)10. 有8个结点的无向连通图最少有（）条边。

(A)5 (B) 6 (C) 7 (D) 8参考答案：(C)11. 含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（）。

(A)3 (B) 4 (C) 5 (D) 6参考答案：(A)12. 在有n个叶子结点的哈夫曼树中，其结点总数为（）。

第一章绪论习题练习答案1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

● 数据：指能够被计算机识别、存储和加工处理的信息载体。

● 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。

数据元素有时可以由若干数据项组成。

● 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。

通常数据类型可以看作是程序设计语言中已实现的数据结构。

● 数据结构：指的是数据之间的相互关系，即数据的组织形式。

一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。

● 逻辑结构：指数据元素之间的逻辑关系。

● 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构.● 线性结构：数据逻辑结构中的一类。

它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。

线性表就是一个典型的线性结构。

栈、队列、串等都是线性结构。

● 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。

数组、广义表、树和图等数据结构都是非线性结构。

1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。

答：例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。

这张登记表中，每个学生的各项体检信息排在一行上。

这个表就是一个数据结构。

每个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。

这几个关系就确定了这个表的逻辑结构是线性结构。

这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢? 即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题。

2022年中南大学数据科学与大数据技术专业《计算机组成原理》科目期末试卷B（有答案）一、选择题1、容量为64块的Cache采用组相联映射方式，字块大小为128个字，每4块为一组。

如果主存为4K块，且按字编址，那么主存地址和主存标记的位数分别为（）。

A.16，6B.17，6C.18，8 D .19，82、某计算机主存按字节编址，由4个64M×8位的DRAM芯片采用交叉编址方式构成，并与宽度为32位的存储器总线相连，主存每次最多读写32位数据。

若double型变量x 的主存地址为80400lAH，则读取x需要的存储周期数是（）。

A.1B.2C.3D.43、假定变量i、f、d的数据类型分别为int、float、double（int用补码表示，float 和double用IEEE754标准中的单精度和双精度浮点数据格式表示），已知i=785，f-l.5678e3，d=1.5el00，若在32位机器中执行下列关系表达式，则结果为真的是（）。

I.i==（int）（float）i Ⅱ.f==（float）（int）fIⅡ.f==（float）（double）f Ⅳ.（d+f）-d=fA.仅I、ⅡB.仅I、ⅢC.仅Ⅱ、ⅢD.仅Ⅲ、Ⅳ4、常用的（n，k）海明码中，冗余位的位数为（）。

A.n+kB.n-kC.nD.k5、float类型（即IEEE754标准中的单精度浮点数格式）能表示的最大整数是（）。

A.2126-2103B.2127-2104C.2127-2105D.2128-21046、某机器I/O设备采用异步串行传送方式传送字符信息，字符信息格式为1位起始位、8位数据位、1位校验位和1位停止位。

若要求每秒传送640个字符，那么该设备的有效数据传输率应为（）。

A.640b/sB.640B/sC.6400B/sD.6400b/s7、在（）结构中，外部设备可以和主存储器单元统一编址。

A.单总线B.双总线C.三总线D.以上都可以8、假定编译器对高级语言的某条语句可以编译生成两种不同的指令序列，A、B和C三类指令的CPl和执行两种不同序列所含的三类指令条数见下表。

(一) 单选题1. 栈和队列的共同点是（）。

(A)都是先进先出(B) 都是先进后出(C) 只允许在端点处插入和删除元素(D) 没有共同点参考答案：(C)2.对广义表执行操作的结果是（）。

(A)(B)(C)(D) (e)参考答案：(B)3. 一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（）。

(A)较快(B) 较慢(C) 相同(D) 不定参考答案：(B)4.从一个长度为n的顺序表中删除第i个元素时，需向前移动的元素的个数是（）。

(A)(B)(C)(D)参考答案：(A)5. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（）。

(A)单链表(B) 仅有头指针的单循环链表(C) 双链表(D) 仅有尾指针的单循环链表参考答案：(D)6. 在下面的程序段中，对x的赋值语句的频度为（）。

(A)(B)(C)(D)参考答案： (C)7. 对于栈操作数据的原则是（）。

(A)先进先出(B)后进先出(C)后进后出(D)不分顺序参考答案： (B)8. 求循环链表中当前结点的后继和前驱的时间复杂度分别是（）。

(A)和(B) 和(C) 和(D)和参考答案： (C)9. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。

(A)存储结构(B)逻辑结构(C)算法(D)操作参考答案：(B)10.程序段如下：其中n为正整数，则最后一行的语句频度在最坏情况下是（）。

(A)(B)(C)(D)参考答案：(D)11.下述程序段中语句的频度是（）。

(A)(B)(C)(D)参考答案：(C)12.二维数组采用列优先的存储方法，若每个元素各占3个存储单元，且地址为150，则元素的地址为（）。

(A)429 (B) 432 (C) 435 (D) 438参考答案：(A)13.下列程序段的渐进时间复杂度为（）。

;(A)(B)(C)(D)参考答案：(C)14.下列程序的时间复杂度为（）。