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

长沙理工大学计算机与通信工程学院 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