2013-2014学年二学期数据结构期末考试试卷(3卷).doc

长沙理工大学计算机与通信工程学院 班级:___________学号:___________姓名:___________得分:___________ 题号 一 二 三 四 五 六 七 八 九 十 成绩 复核 得分 ? ? ? ? ? ? ? ? ? ? ? ? 阅卷 ? ? ? ? ? ? ? ? ? ? ? 题目部分，(卷面共有35题,100分,各大题标有题量和总分) 一、应用题(2小题,共16分) 1．对给定的一组权值W＝（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长度。 2．分析下面各程序段的时间复杂度 （1） s1(int n) { int p=1,s=0; ? for (i=1;i<=n;i++) ???? { p*=i;s+=p; } return(s); } （2） s2(int n) x=0; y=0; For (k=1;k<=n;k++) x++; For (i=1;i<=n;i++) For (j=1;j<=n;j++) y++; ? ? 二、判断正误(6小题,共12分) 1．由树转化成二叉树，该二叉树的右子树不一定为空。（? ） ? 2．稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（? ） 3．用邻接矩阵存储图，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。（? ） 4．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（? ） 5．设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（? ） 6．每种数据结构都具备三个基本操作：插入、删除和查找。（? ） 三、单项选择题(15小题,共30分) 1．已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（??? ）。 A． B+(i-1)*m????? ? B．B+i*m?? ?? ?????C． B-i*m? ?? ??????D． B+(i+1)*m ? 2．使用双链表存储线性表，其优点是可以（ ）。A 提高查找速度??? ?B 更方便数据的插入和删除C 节约存储空间 ????D 很快回收存储空间 3．若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（ ）存储方法最节省时间。 A 单链表 B 带头指针的单循环链表 C 双链表 D 带尾指针的单循环链表 4．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（?? ）结构。 A 栈??????????? B队列??????? C 数组???????? D线性表 ? 5．用链接方式存储的队列，在进行插入运算时(?? ). ?? A. 仅修改头指针? 　????????? B. 头、尾指针都要修改 ?? C. 仅修改尾指针????????????? D.头、尾指针可能都要修改 ? 6．以下论述正确的是（??? ）。 ?? A．空串与空格串是相同的???? ? B．"tel"是"Teleptone"的子串 ?? C．空串是零个字符的串?????? ? D. 空串的长度等于1 ? 7．对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次为（ ）。 A h???????? ?B h+1??????? ?C h或h+1????????? ?D 任意 8．设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（?? ）。 ??? ?A ?N1-1??????????????? B ?N2-1?????????????? C ?N2+N3???????????? D ?N1+N3 ? 9．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（? ）个空指针域。 ???? A ?2m-1????????????????? B? 2m???????????????? C ?2m+1????????????? D? 4m ? 10．设某有向图中有n个顶点，则该有向图对应的邻接表中有（? ）个表头结点。 ???? A? n-1???????????????????? B ?n??????????????????? C ?n+1??????????????? D ?2n-1 ? 11．二叉排序树中左子树上所有结点的值均（? ）根结点的值。 ???? A ?<??????????????????????