重修数据结构试卷(2)最终版

《重修数据结构试卷(2)最终版》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、常州大学考试命题用纸考试科目数据结构共2页，第页信息科学与工程学院2010~2011学年第1学期数据结构重修考试卷题号一二三四总分题分30105010100得分阅卷签名一、单项选择题（共15题，每题2分，共计30分）1、某二叉树的先序序列和后序序列正好相同，则该二叉树一定是(A)的二叉树。（A）空或只有一个结点（B）高度等于其结点数（C）任一结点无左孩子（D）任一结点无右孩子2、下列说法错误的是(D)。（A）一个图的邻接矩阵表示是唯一的（B）一个图的邻接表表示是不唯一的（C）一个图的生成树必为该图的极小连通子图（D）一个无环有向图的拓扑

2、排序序列必唯一3、下列排序算法中，(C)算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。（A）堆排序（B）冒泡排序（C）快速排序（D）SHELL排序4、一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是(B)（A）23415（B）54132（C）23145（D）154325、设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（B）（A）front=front+1（B）front=(front+1)%m（C）rear=(rear+1)%m（D）

3、front=(front+1)%(m+1)6、若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用(C)存储方式最节省时间。（A）单链表（B）双链表（C）带头结点的双循环链表（D）单循环链表7、在有n个结点的二叉链表中，值为非空的链域的个数为(A)（A）n-1（B）2n-1（C）n+1（D）2n+18、一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为(B)（A）0（B）1（C）2（D）不确定9、设矩阵A（aij，l≤i,j≤10）的元素满足：aij≠0(i≥j,l≤i,j≤10)aij=0(i

4、i,j≤10)现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A[9][5]的首址为（B）（A）2340（B）2336（C）2164（D）216010、求最短路径的DIJKSTRA算法的时间复杂度为(C)（A）O(n)（B）O(n+e)（C）O(n2)（D）O(n×e)11、二分查找要求被查找的表是（C）系（部）教研室拟题人校核：系（部）主任教学院长年月日常州大学考试命题用纸考试科目数据结构共2页，第页（A）键值有序的链接表（B）链接表但键值不一定有序（C）键值有序的顺序表（D）顺序表但键

5、值不一定有序12、DFS算法的时间复杂度为(C)（A）O(n)（B）O(n3)（C）O(n2)（D）O(n+e)13、通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质量。以下解释错误的是(D)（A）正确性算法应能正确地实现预定的功能(即处理要求)（B）易读性算法应易于阅读和理解，以便于调试、修改和扩充（C）健壮性当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果（D）高效性即达到所需要的时间性能14、栈和队列的共同特点是(C)（A）都是先进后出（B）都是先进先出（C）只允许在端点处插入和删除

6、元素（D）没有共同点15、串是（　D）（A）一些符号构成的序列　（B）有限个字母构成的序列（C）一个以上的字符构成的序列　（D）有限个字符构成的序列二、填空题（共5题，每题2分，共计10分）16、一棵树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定___左右子树空____。17、在有n个结点的无向图中，其边数最多为_1/2*n*(n-1)______。18、对广义表A=(x,((a,b),c,d))的运算head(head(tail(A)))的结果是__(a)___。19、判断线索二叉树中某结点指针P

7、所指结点有左孩子的条件是___P->ltag=1____。20、己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找90时，需_____2_____次查找成功，47时____4_____成功，查100时，需___3______次才能确定不成功。三、解答题（共5题，每题10分，共计50分）21、对图1（下图）所示的连通图，请分别用Prim和Kruskal算法构造其最小生成树。 　　　图1系（部）教研室拟题人校核：系（部）主任教学院长年月日常州大学考试命题用纸考试科目数据结构共2页，第页22、已

8、知一棵二叉树的先序序列是ABCDEFGHIJK，中序序列是CDBGFEAHJIK，请构造出该二叉树。23、设哈希表a、b分别用向量a[0..9],b[0..9]表示，哈希函数均为H（key）=keyMOD7