数据结构模拟试题分享

1、文档供参考，可复制、编制，期待您的好评与关注！ 1 选择题（每小题1分，共8分） 1.设有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主存储，a00的存储地址为100，每个元素占1个地址空间，则a32的地址为（）。（A）102 （B）105 （C）106 （D）1082. 森林转换为二叉树后，从根结点开始一直沿着右子数下去，一共有4个结点，表明（）。（A）森林有4棵树 （B）森林的最大深度为4（C）森林的第一棵树有4层 （D）森林有4个结点3. 在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）。（A）e （B）2e （C）n2e （D）n22e4. 在内部排序中，排序时不稳定

2、的有（）。（A）插入排序 （B）冒泡排序 （C）快速排序 （D）归并排序5. 设一数列的顺序为1，2，3，4，5，通过栈结构不可能派成的顺序数列为（）。（A）3，2，5，4，1 （B）1，5，4，2，3（C）2，4，3，5，1 （D）4，5，3，2，16. 一个n条边的连通无向图，其顶点的个数至多为（）。（A）n（B）n（C）n（）nlog2n7. 总共3层的完全二叉树，其结点数至少有（）个。（A）3 （B）4 （C）7 （D）88. 已知某算法的执行时间为（n3+n2+n）log2（n+2），n为问题规模，则该算法的时间复杂度是（）。（A）O（n） （B）O（n2） （C）O（log2n）

3、（D）O（n3log2n）2 判断题（每题1分，共8分。正确的打，错误的打×）1.只要是算法，肯定可以在有限的时间内完成。（）2.无论是线性表还是树，每一个结点的直接前驱结点最多只有一个。（）3.不论是行优先还是列优先，二维数组的最后一个元素的存储位置是一样的。（）4.直接插入排序时，关键码的比较次数与记录的初始排列无关。（）5.二叉树的先序遍历不可能与中序遍历相同。（）6.任何一棵二叉树，不可能没有叶子结点。 （）7.一个稀疏矩阵采用三元组法存储不可能是（5，3，7），（5，4，4），（5，3，5）。（）8.一个无序的顺序表不能采用折半查找法进行查找。（）。三填空题（每题2分，共1

4、6分）1.在一个长度为n的顺序表中插入一个元素，平均需移动 个元素，时间复杂度是 。2. 一个5×5的对称矩阵采用压缩存储，需要存储 个元素。3.具有26个结点的完全二叉树的深度为 。4. 有向图用邻接矩阵存储，其第i列的所有元素之和等于顶点i 的 。5.一棵深度为5的二叉树，至少有 个叶子结点。6. 快速排序法在最差的情况下的时间复杂度是 。7.衡量一个算法的优劣主要看它的 效率和 效率。8. 如果某线性表的每一个元素都没有后继元素，则其长度最多是 。4 简答题（共38分）1.堆排序（1）写出线性表（16，4，12，25，30，6，15，11，20，2，18）调整为大顶堆（用二叉树

5、表示）。（5分）（2）在上述堆的堆顶元素去掉，把堆的最后一个元素放到堆顶位置，再调整为大顶堆（用二叉数表示）。（15分）2. 给出右图所示数的先序遍历结果。（5分） A B C D E F G H3.假设字符a，b，c，d，e，f的使用频率分别是0.07，0.09，0.12，0.22，0.23，0.27，写出a，b，c，d，e，f的Huffman编码。（5分）4. 已知左下图是一个无向图。（1）画出该无向图的邻接矩阵。（5分）（2）基于你给出的邻接矩阵，求从顶点A出发的深度优先遍历。（4分）5.用Kruskal算法（一条边一条边地加入生成树）求右下图的最小生成树。（1）写出各条边加入生成树的次

6、序（用权值表示）。（5分）（2）画出最终的最小生成树。（4分） 12 D D E 3 8 C 20 C F 15 10 E B G B 11 G 5 1 F A A 5 程序填空题（共15分）1.已知单链表的表首指针为head，下面的函数delete是从单链表中删除指针为p的结点，并返回新的表首指针。请完成如下程序。（4分） typedef struct LinkNode int data； struct LinkNode *next； Node； Node *delete(Node *head，Node *p) Node *pf； if(headp)head；free（p）； else fo

7、r（pfhead；pf>next！p；pfpf>next）； p>next； free（p）； return head； 2. 已知数组r有n个元素，并已经由小到大排序。下面的函数search的功能是采用折半查找法查找值为e的元素，并返回其下标，如果找不到，返回。完成下面的程序。（4分）int search（elem r，int n，int e）int i1，i2，l；i10；i2n；while（i1<i2）k（i1+i2）/2；if（rke） ；if（e<rk）i2k1；else ；rerurn 1；3. 以下算法是将线性表L中所有负数元素删除，返回被删除的元素个数。完成以下算法。（7分）Typedef structint elem100；Int length；SQ；Int deln（SQ *L）/*算法思路是，对每个元素做以下循环，如果第i个元素大于等于0，且前面有c 个小于0的元素，则将它前移c个位置*/int i，c；/*c将记录小于0的元素个数*/for（i0；c0；iLlength；i+） if（ ）c+； else if（c>0）x>ei x>ei； xlength ；return c；6 编程题（共15分）1. 编写算法，求一个整型数组中不同值的个数。例如数组5，3，5，7，3，6，不同的值