长沙理工大学-2014-2015学年一学期数据结构期末考试试卷7.doc

长沙理工大学-2014-2015学年一学期数据结构期末考试试卷7.doc

  1. 1、本文档共5页,可阅读全部内容。
  2. 2、本文档内容版权归属内容提供方,所产生的收益全部归内容提供方所有。如果您对本文有版权争议,可选择认领,认领后既往收益都归您。
  3. 3、本文档由用户上传,本站不保证质量和数量令人满意,可能有诸多瑕疵,付费之前,请仔细先通过免费阅读内容等途径辨别内容交易风险。如存在严重挂羊头卖狗肉之情形,可联系本站下载客服投诉处理。
  4. 文档侵权举报电话:400-050-0739(电话支持时间:9:00-19:00)。
长沙理工大学计算机与通信工程学院 2014-2015学年一学期数据结构期末考试试卷(C卷) 班级:___________学号:___________姓名:___________得分:___________ 题号 一 二 三 四 五 六 七 八 九 十 成绩 复核 得分 ? ? ? ? ? ? ? ? ? ? ? ? 阅卷 ? ? ? ? ? ? ? ? ? ? ? 题目部分,(卷面共有32题,100分,各大题标有题量和总分) 一、应用题(2小题,共16分) 1.分析下列程序段的时间复杂度: (1)for (i=1; i<=n; i=2*i) ?????? ??? ++x; ?(2)for (i=1; i<=n; ++i) ?????? for (j=1; j<=i-1; ++j) ??????????????????? ++x; 2.对给定的一组权值W=(5,2,9,11,8,3,7),试构造相应的哈夫曼树,并计算它的带权路径长度。 二、判断正误(5小题,共10分) 1.顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。(? ) 2.非空的双向循环链表中任何结点的前驱指针均不为空。(? ) 3.在循环队列中无溢出现象。(? ) 4.稀疏矩阵压缩存储后,必会失去随机存取功能。(? ) 5.当向二叉排序树中插入一个结点,则该结点一定成为叶子结点。(? ) 三、单项选择题(10小题,共20分) 1.递归算法一般需要利用( )实现。 2.已知一个顺序存储的线性表,设每个结点占m个存储单元,若第一个结点的地址为B,则第i个结点的地址为(??? )。 A. B+(i-1)*m????? ? B.B+i*m?? ?? ?????C. B-i*m? ?? ??????D. B+(i+1)*m 3.在C或C++语言中,一个顺序栈一旦被声明,其占用空间的大小(??? )。 ?? A.已固定??? B.不固定?????? C.可以改变?? D.动态变化 4.设指针变量top指向当前链式栈的栈顶,则删除栈顶元素的操作序列为(? )。 ???? A ?top=top+1;??????????? B ?top=top-1;?????? C ?top->next=top;???? ??? D ?top=top->next; 5.若串S="SOFTWARE",其子串的数目最多是:(??? ) 。 ??? A.35???????? B.36?????????? C.37?????????? D.38 6.对于完全二叉树中的任一结点,若其右分支下的子孙的最大层次为h,则其左分支下的子孙的最大层次为( )。 A h???????? ?B h+1??????? ?C h或h+1????????? ?D 任意 7.下列命题正确的是( )。 A 一个图的邻接矩阵表示是唯一的,邻接表表示也唯一 B 一个图的邻接矩阵表示是唯一的,邻接表表示不唯一 C 一个图的邻接矩阵表示不唯一的,邻接表表示是唯一 D 一个图的邻接矩阵表示不唯一的,邻接表表示也不唯一 8.? 设某散列表的长度为100,散列函数H(k)=k % P,则P通常情况下最好选择(? )。 ???????? A ?99???????????????????? B ?97???????????????? C ?91????????????????? D ?93 ? 9.堆的形状是一棵( )。 A二叉排序树???? ?B满二叉树 ?????C完全二叉树??? ?D 判定树 10.设一组初始记录关键字序列为(Q,H,C,Y,P,A,M,S,R,D,F,X),则按字母升序的第一趟冒泡排序结束后的结果是(?? )。 A ??F,H,C,D,P,A,M,Q,R,S,Y,X B ??P,A,C,S,Q,D,F,X,R,H,M,Y C ??A,D,C,R,F,Q,M,S,Y,P,H,X D ??H,C,Q,P,A,M,S,R,D,F,X,Y ? 四、算法设计题(4小题,共32分) 1.设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符),要求利用原单链表中结点空间设计出三个单链表的算法,使每个单链表只包含同类字符。 ?2.设有两个集合A和集合B,要求设计生成集合C=A∩B的算法,其中集合A、B和C用链式存储结构表示。 3.?对给定的带头结点的单链表L,编写一个删除L中值为X的结点的直接前趋结点的算法。 4.设计一个在链式存储结构上统计二叉树中结点个数的算法。 五、填空题(11小题,共22分) 1.已知顺序栈S,在对S进行进栈操作之前首先要判断(??? ),在对S进行出栈操作之前首先要判断(??? )。 2.设循环队列存放在向量sq.data[0:M]中,若用牺牲一个单元的办法来区分队满和队空(设队尾指针s

文档评论(0)

173****6432
该用户很懒,什么也没介绍

相关文档

相关课程推荐