数据结构模拟试题.doc

《数据结构模拟试题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一．选择题（每小题1分，共8分）1.设有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主存储，a[0][0]的存储地址为100，每个元素占1个地址空间，则a[3][2]的地址为（）。（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）n^2－e（D）n^2－2e4.在内部排序中，排序时不稳定的有（）。（A

2、）插入排序　（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.已知某算法的执行时间为（n^3+n^2+n）log2（n+2），n为问题规模，则该算法的时间复杂度是（）。（A）O（n）（

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

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

5、，6，15，11，20，2，18）调整为大顶堆（用二叉树表示）。（5分）（2）在上述堆的堆顶元素去掉，把堆的最后一个元素放到堆顶位置，再调整为大顶堆（用二叉数表示）。（15分）2.给出右图所示数的先序遍历结果。（5分）ABCDEFGH3.假设字符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算法（一条边一条

6、边地加入生成树）求右下图的最小生成树。（1）写出各条边加入生成树的次序（用权值表示）。（5分）（2）画出最终的最小生成树。（4分）12DDE38C20CF1510EBGB11G51FAA五．程序填空题（共15分）1.已知单链表的表首指针为head，下面的函数delete是从单链表中删除指针为p的结点，并返回新的表首指针。请完成如下程序。（4分）typedefstructLinkNode{intdata；structLinkNode*next；}Node；Node*delete(Node*head，Node*p){Node*pf；if(head＝＝p){　　　he

7、ad＝　　　　　　　　　　　；　　　free（p）；}else{for（pf＝head；pf－>next！＝p；pf＝pf－>next）；＝p－>next；free（p）；}}returnhead；}2.已知数组r有n个元素，并已经由小到大排序。下面的函数search的功能是采用折半查找法查找值为e的元素，并返回其下标，如果找不到，返回－１。完成下面的程序。（4分）intsearch（elemr[]，intn，inte）{inti1，i2，l；i1＝0；i2＝n－１；while（i1<＝i2）{k＝（i1+i2）/2；if（r[k]＝＝e）；if（e

8、i2＝k－1；else；