中南大学十套数据结构试题及答案数据结构试卷(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。
二叉树k级的最大节点数是()。
a . 2k-1b . 2k+1c . 2k-1d . 2k-17。
如果18个元素的有序表存储在一维数组A[19]中，则第一个元素被放置在[1]中，现在执行分数搜索。
那么搜索a [3]的比较序列的下标是()A1，2，3 B，5，2，3 C，5，3 D，4，2，38。
n个记录的文件快速排序，所需的辅助存储空间约为a . o(1)b . o(n)c . o(1 og2n)d . o(N2)9。
当对线性表(7，34，55，25，64，46，20，10)进行散列时，如果选择H(K)=K %9作为散列函数，则有()个元素的散列地址为1，a.1b.2c.3d.410。
有6个节点的无向图应该至少有()条边，以确保它是连通图A.5b.6c.7d.8ii .填写问题(每栏1分，共26分)1。
通常，算法的质量是从四个方面来评估的:_ _ _ _ _ _ _ _ _ _ _、_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _、和_ _ _ _ _ _ _ _ _ _ _ _ _3222。
算法的时间复杂度为(n+nlog2n+14n)/n，其数量级表示为_ _ _ _ _ _ _ _ _3.假设树的广义表表示为A(C，D(E，F，G)，H(I，J))，树中的节点数为_ _ _ _ _ _ _ _，树的深度为_ _ _ _ _ _ _ _，树的度数为_ _ _ _ _ _ _ _ _4。
后缀公式9 2 3+-10 2/-的值为_ _ _ _ _ _ _ _ _ _对应于中缀公式(3+4X)-2Y/3的后缀公式1是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _5.如果一个二叉树存储在一个链表中，除了数据字段外，每个节点还有个引脚指向左子节点和右子节点在这种存储结构中，由n个节点组成的二叉树总共有_ _ _ _ _ _ _ _个指针字段，其中_ _ _ _ _ _ _ _个指针字段存储地址，_ _ _ _ _ _ _ _个指针为空指针6.对于具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，分别有_ _ _ _ _ _ _ _个和_ _ _ _ _ _ _ _个边节点7。
AOV网络是一种_ _ _ _ _ _ _ _ _ _ _ _ _ _ _图8.一个有n个顶点的无向完全图包含_ _ _ _ _ _ _ _条边，而一个有n个顶点的方向的完全图包含_ _ _ _ _ _ _ _条边9。
假设一个线性表是(12，23，74，55，63，40)，如果根据键% 4的条件进行划分，那么具有相同余数的元素成为一个子表，那么所获得的四个子表是_ _ _ _ _ _ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _，_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _和_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _分别为10.在将元素插入到B_树的过程中，如果根节点最终被拆分，则新树的高度为__________11。
在堆排序过程中，筛选任何分支节点的时间复杂度为_ _ _ _ _ _，堆排序整个过程的时间复杂度为_ _ _ _ _ _ _12。
在快速排序、堆排序和合并排序中，_ _ _ _ _ _ _ _ _ _ _排序是稳定的3.计算题(每题6分，共24分)1。
线性表链接并存储在下面的数组中。
标题中的指针是[0]。
接下来，试着写线性表格A 0 1 2 3 4 5 6 7数据60 50 78 90 34 40下一个3 5 7 2 0 4 12。
请在下图中绘制邻接矩阵和邻接表3。
已知图的顶点集V和边集E是:V={1，2，3，4，5，6，7 }；E={(1，2)3，(1，3)5，(1，4)8，(2，5)10，(2，3)6，(3，4)15，(3，5)12，(3，6)9，(4，6)4，(4，7)20，(5，6)18，(6，7)25 }；使用Kruskar算法获得最小生成树，并尝试写出在最小生成树中按顺序获得的每条边4.将数据4、2、5、8、3添加到小根堆后，绘制堆的变化。
4.阅读算法(每题7分，共14分)1。
link listmynote(link listl){//l是没有头节点的单个链表的头指针if (lbc (Bt-> right );coutdatap-> next = q-> next；自由(q)；(二)q=p->下一个；q->数据=p->数据；p-> next = q-> next；自由(q)；(三)q=p->下一个；p-> next = q-> next；自由(q)；(D) q=p->下一个；p->数据=q->数据；自由(q)；4。
对于要排序的n个记录关键字，()在堆排序中需要辅助记录单元(a)1(b)n(c)nlog 2n(d)n5。
如果一组初始密钥记录密钥为(20，15，14，18，21，36，40，10)，则基于20的快速排序后的结果为()(A) 10、15、14、18、20、36、40、21 (B) 10、15、14、18、20、40、36、21 (C) 10、15、14、20、18、40、36、2l (D) 15、10、14、18、20、36、40、216。
如果二进制排序树中有n个节点，则二进制排序树中的平均搜索长度为()(a)o(1)(b)o(log2n)(c)(d)o(N2)7。
如果无向图g中有n个顶点和e条边，则其对应的邻接表中头节点和表节点的数量为()(A) n，e (B) e，n (C) 2n，e (D) n，2e 8。
如果强连通图中有n个顶点，那么强连通图中至少有()条边(a)n(n-1)(b)n+1(c)n(d)n(n+1)9。
有5000个记录关键字需要排序。
如果需要用最快的方法选择最短的10个记录关键字，可以使用下面的()方法来实现这个目标(a)快速排序(b)堆排序(c)合并排序(d)插入排序10。
在以下四种类型中()，空间复杂度最大(a)插入排序(B)冒泡排序(C)堆排序(D)合并排序22，填入空格(每空一个20分)1。
数据的物理结构主要包括_ _ _ _ _ _ _ _ _和_ _ _ _ _ _ _ _ _两种情况2。
如果在一个完整的二叉树中有500个节点，那么二叉树的深度是_ _ _ _ _ _；如果使用二进制链表作为完整二叉树的存储结构，则总共有_ _ _ _ _ _ _ _ _ _ _个空指针字段3。
如果输入序列是1、2、3，_ _ _ _ _ _ _ _ _ _在堆栈操作后可以获得不同的输出序列。
4.如果邻接矩阵A[n][n]被用作图g的存储结构，则邻接矩阵的第一行中所有元素的和等于顶点1的_ _ _ _ _ _ _并且第一列中所有元素的和等于顶点1的_ _ _ _ _ _ _65。
如果哈夫曼树中有n个节点，那么哈夫曼树中有_ _ _ _ _ _ _个1度节点6.有向图g中有n个顶点，有e条有向边。
如果所有顶点度数的和是d，那么e和d之间的关系是_ _ _ _ _ _ _ _ _7.________遍历二进制排序树中的节点以获得递增的键序列(填入第一个顺序、中间顺序或顺序后的)8.假设查找表中有100个元素。
如果使用二进制搜索方法来查找数据元素x，您最多可以通过比较_ _ _ _ _ _次来确定数据元素x是否在查找表中。
9.无论是顺序存储结构的堆栈还是链式存储结构的堆栈，堆栈进入和堆栈退出操作的时间复杂度都是_ _ _ _ _ _ _ _ _ _ _10。
有n个节点的完全二叉树。
如果从1开始从上到下、从左到右编号，则第256个+i节点的父节点号为_ _ _ _ _ _ _ _ _ _ _ _ _ _，而右子节点号为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _11.如果一组初始记录关键字是(72，73，71，23，94，16，5)，则基于记录关键字72的快速排序的结果是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _12。