《算法数据结构》期末试题及答案

《《算法数据结构》期末试题及答案》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《算法数据结构》期末试题及答案　　　　《数据结构与算法分析C++描述》(第3版)适合作为计算机相关专业本科生的数据结构课程和研究生算法分析课程的教材以下是由阳光网小编整理关于《算法数据结构》期末试题的内容希望大家喜欢　　　　运算题(每小题6分共30分)　　　　1.设有一个lOXl0的对称矩阵A将其上三角部分按行存放在一个一维数组B中A[o][0]存放于B[o]中那么A[5][8]存放于B中什么位置.　　　　A[5][8]在B中的存放位置：　　　　2.有7个带权结点其权值分别为37.8261014试以它们为叶子结点生成一棵霍夫曼树求出该树的

2、带权路径长度和高度假定树根的高度为o.　　　　带权路径长度：　　　　高度：　　　　3.已知图G一(VE)其中V={abcdc}　　　　E={}　　　　请问该图的邻接表中每个顶点单链表各有多少边结点.顶点：abcde　　　　边结点数：　　　　4.已知一个AOV网络的顶点集V和边集E分别为：　　　　V={O4321567);　　　　E{<02><13><1.4><24><25><36>.<37>.<47><57><67>)　　　　若存储它采用邻接表并且每个顶点邻接表中的边结点都是按照终点序号(即dest域的值)从小到大的次序链接的则按主教材中

3、介绍的进行拓扑排序的算法写出得到的拓扑序列(提示：先画出对应的图形然后再运算).　　　　拓扑序列：　　　　5.已知有一个数据表为{3018xx38124453.4618·2686)给出进行归并排序的过程中每一趟排序后的数据表变化.　　　　(0)[30182015381244534618*2686]　　　　(1)　　　　(2)　　　　(3)　　　　(4)　　　　答案　　　　1.43　　　　答案说明：根据题意矩阵A中当元素下标I与J满足I≤J时任意元素A[i][j]在一维　　　　数组B中的存放位置为(2n一1—1)*1/2+J因此A[5][8

4、]在数组B中的位置为：　　　　(2*10—5—1)*5/2+8=43　　　　2.　　　　带权路径长度：131　　　　高度：4　　　　3评分标准：每个数据对给1分全对给6分.　　　　便点：abcde　　　　边结点数：11212　　　　4.评分标准;若与答案完全相同得6分若仍为一种拓扑序列用得3分其他用酌情处　　　　理.　　　　拓扑序列：13602547　　　　5.分步给分　　　　(0)[30182015381244534618*2686]　　　　(1)[1830][1520][1238][4453][18*46][2686]　　　　(2)[

5、15182030][123e44S3][18*264686]　　　　(3)[1215182030384453][18*264686]　　　　(4)[12151818*2026303a44465386]　　　　一、单选题(每题2分共20分)　　　　1.栈和队列的共同特点是()　　　　A.只允许在端点处插入和删除元素　　　　B.都是先进后出　　　　C.都是先进先出　　　　D.没有共同点　　　　2.用链接方式存储的队列在进行插入运算时().　　　　A.仅修改头指针B.头、尾指针都要修改　　　　C.仅修改尾指针D.头、尾指针可能都要修改　　　　3

6、.以下数据结构中一个是非线性结构?()　　　　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.688B.678C.692D.696　　　　5.树最适合用来表示()　　　　A.有序数据元素B.无序数据元素　　　　C.元素之间具有分支层次关系的数据D.元素之间无联系的数据　　　　6.二叉树的第k层的结点数最多为().　　　　kk1

7、A.21B.2K+1C.2K1D.2　　　　7.若有18个元素的有序表存放在一维数组A[19]中第一个元素放A[1]中现进行二　　　　分查找则查找A〔3〕的比较序列的下标依次为()　　　　A.123B.9523　　　　C.953D.9423　　　　8.对n个记录的文件进行快速排序所需要的辅助存储空间大致为　　　　A.O(1)B.O(n)C.O(1og2n)D.O(n2)　　　　9.对于线性表(734552564462010)进行散列存储时若选用H(K)　　　　=K%9作为散列函数则散列地址为1的元素有()个　　　　A.1B.2C.3D.4

8、　　　　10.设有6个结点的无向图该图至少应有()条边才能确保是一个连通图　　　　A.5B.6C.7D.8　　　　二、填空题(每空1分共26分)　　　　1.通常从四个方面评价算法的质量：、、和