2015数据结构试卷A.doc

《2015数据结构试卷A.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、上饶师范学院试卷（A卷）课程名称：数据结构适用学期：第四学期适用专业：信息管理与信息系统适用层次：本科班级：学号：姓名命题人：徐晓晖教研室审核人：周玉林二级学院审定人:李波题号一二三四五六总分得分阅卷教师签名得分一、选择题（每小题2分，共20分）1．评价算法优劣的两个主要方面是()。A.时间复杂性和空间复杂性　　　B.正确性和简明性C.可读性和文档性　　　　　　　D.数据复杂性和程序复杂性2．用链表表示线性表的优点是()。A．便于随机存储　　　　B．花费的存储空间较顺序存储少C．便于插入和删除操作D．数据元素的物理顺序与逻辑顺序相同3．若元素a、b、

2、c、d、e、f依次进栈，允许进栈、出栈操作交替进行，但不允许连续三次进行出栈工作，则不可能得到的出栈序列是()A．dcebfaB.cbdaefC.bcaefdD.afedcb4．以下那一个术语与数据的存储结构无关？()A．栈B.单链表C.线索树D.双向链表5．下面关于串的的叙述中，哪一个是不正确的？()A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储6．在下述结论中，正确的是()①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树

3、的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④7．一个递归算法必须包括()。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分8．在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是()。A．G中有弧B．G中有一条从Vi到Vj的路径C．G中没有弧D．G中有一条从Vj到Vi的路径9．依次将每两个相邻的有序表合并成一个有序表的排序方法称为()。A.插入排序B.交换排序C.选择排序D.归并排序10．使用二分查找法时，要求查找表中各元素的键值必须是()排序。A.

4、递增或递减B.递增C.递减D.无序得分二、填空题（每小题2分，共16分）11．已知一棵完全二叉树中共有768个结点，则该树中共有个叶子结点。12．经过以下栈运算后，x的值是什么?InitStack(S);Push(S,‘a’);Push(S,‘b’);Pop(S,x);x=GetTop(S);13．对n个元素的序列进行起泡排序时，最少的比较次数是。14．一棵深度为k且具有2k-1个结点的二叉树称为。这类二叉树的特点是：二叉树中第i层的个数是。15．在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。16．在图G的邻接表表

5、示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的______；对于有向图来说等于该顶点的______。17．从逻辑上可以把数据结构分为以下几类：、、、。18．在散列表示的字典中，解决碰撞有两种处理方法：和。得分三、简答题（每小题4分，共12分）19．证明对于一棵非空二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有n0=n2+1。20．简述栈与队列的概念；并解释两者的异同点。21．什么是强连通图？什么是强连通分量？得分四、解答题（每小题5分，共20分）22．已知一棵树如图（1）试画出该二叉树的中序穿线（或线索）树；（2）试画出该

6、二叉树对应的森林；23．对于图1所示的有向图，试给出：(1)每个顶点的入度和出度(2)邻接矩阵；(3)邻接表。24．以数据集{4，5，6，7，10，12，18}为结点权值来构造的哈夫曼树，并计算其带权的外部路径长度。25．对已知序列{503，87，512，61，908，170，897，275，653，462}采用基数排序法作升序排序，请写出每一趟的排序结果。得分五、算法阅读理解题（每小题6分，共12分）26．将下面的二分插入排序算法中空缺处填写完整。voidBinSort(SeqList*pvector){intI,j,left,mid,right;

7、for(i=2;in;i++){pvector->r[0]=pvector->r[i];left=1;right=i-1;while(left<=right){mid=if(pvector->r[0].keyr[mid].key)right=mid-1;else;}for(j=i-1;j>=left;j--);pvector->r[j+1]=pvector->r[0];}}27．[程序说明]以下函数中，h是带头结点的双向循环链表的头指针。(1)说明此程序的功能；(2)当链表中结点数分别为1和6(不包括头结点)时

8、，请写出程序中while循环体的执行次数。intf(DListNode*h){　DListNode*p,*q