搜索
南阳理工学院2013–2014学年第一学期试卷（A卷）课程：《数据结构》课程号：1504108130考核方式：（闭卷）课程性质：专业必修课适用对象：12软工媒体、11软工NET、12网工、12网安本科题号一二三四五总分复核人满分1030103020100得分一、填空题：（每空1分，共10分）1．_______________是相互之间存在一种或多种特定关系的数据元素的集合。2．一个算法必须满足_______________、确定性、可行性、输入和输出五个重要的特性。3．链接存储的存储结构所占存储空间分两部分，一部分存放结点值，另一部分存放表示_______________。4．在二叉树的第i层上至多有_______________个结点。5．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_______________倍。6．具有n个顶点的有向图最多有_______________条边。7．对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为_______________。8．_______________又称最优树，是一类带权路径长度最短的树。9．从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为_______________。10．若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为______________________________。二、选择题：（每题2分，共30分）1．以下数据结构中，（）是非线性数据结构A．字符串B．队C．栈D．树2．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。A．110B．108C．100D．1203．在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（）。A．s-next=p+1;p-next=s;B．(*p).next=s;(*s).next=(*p).next;C．s-next=p-next;p-next=s-next;D．s-next=p-next;p-next=s;评卷人得分评卷人得分共5页第1页4．线性表Ｌ在（）情况下适用于使用链式结构实现。A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂5．串是一种特殊的线性表，其特殊性体现在（）。A．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符若6．串的长度是指（）。A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数7．数组A[0..4,-1..-3,5..7]中含有元素的个数（）。A．55B．45C．36D．168．广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（）。A．(g)B．(d)C．cD．D9．把一棵树转换为二叉树后，这棵二叉树的形态是（）。A．唯一的Ｂ．有多种C．有多种，但根结点都没有左孩子Ｄ．有多种，但根结点都没有右孩子10．由3个结点可以构造出多少种不同的二叉树？（）A．2B．3C．4D．511．线索二叉树是一种（）结构。A．逻辑B．逻辑和存储C．物理D．线性12．利用二叉链表存储树，则根结点的右指针是（）。A．指向最左孩子B．指向最右孩子C．空D．非空13．在一个图中，所有顶点的度数之和等于图的边数的（）倍。A．1/2B．1C．2D．414．对n个不同的关键字由小到大进行冒泡排序，在下列（）情况下比较的次数最多。A．从小到大排列好的B．从大到小排列好的C．元素无序D．元素基本有序15．下列关键字序列中，（）是堆。A．16，72，31，23，94，53B．94，23，31，72，16，53C．16，53，23，94，31，72D．16，23，53，31，94，72三、判断题：（每题1分，共10分）（说明：认为陈述正确的在括号内打“√”；否则在括号内打“×”）1．线性表的链式存储结构优于顺序存储结构。（）2．线性表中每个元素都有一个且仅有一个直接前驱和直接后继。（）3．线性表若采用链式存储结构时，要求内存中可用存储单元的地址必须连续。（）4．栈又称先进先出的线性表。（）5．深度为k的满二叉树含有2k-1个结点。（）评卷人得分共5页第2页6．遍历二叉树可采用深度优先搜索算法进行。（）7．空串是由空格构成的串。（）9．若一组记录的排序码为（46,79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（40，38，46，56，79，84）。（）9．从未排序序列中挑选元素，并将其依次放入已排序序列初始时为空的一端的方法，称为选择排序。（）10．堆的形状是一棵满二叉树。（）四、应用题：（每题6分，共30分）1．若让元素1，2，3，4，5依次进栈S，至少写出五种出栈的情况。2．设一棵二叉树的后序序列：FDBGHECA，中序序列：BFDAGEHC，要求：(1)画出这棵二叉树；(2)写出这棵二叉树的前序序列。评卷人得分共5页第3页3．已知如下图所示的有向图，请给出：(1)每个顶点的入度和出度；(2)邻接表。4．采用普里姆算法的构造最小成生树。5．已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)，哈希函数为：H(key)=keyMOD13,哈希表长为m=16，设每个记录的查找概率相等，采用线性探测法处理冲突。构造关键字的散列表，并计算查找成功和查的失败时的平均查的长度。共5页第4页五、算法分析与设计：（第1题8分，第2题12分，共20分）1．采用顺序存储表示方法，实现循环队列中的出队和入队算法。2．Pleasewritedownthecodeofbinary（折半）searchalgorithmandBinaryinsertionsort（折半插入排序）algorithm评卷人得分共5页第5页南阳理工学院课程考试参考答案与评分标准考试课程：数据结构学年学期：2013-2014-1试卷类型：A考试时间：120分钟一、填空题1.数据结构（或其他结构一种结构也正确）2.有穷性3.结点间关系的指针4．2i-15.16．n(n-1)7．(n+1)/28．赫夫曼树9．插入排序10．84，79，56，38，40，46或38，40，56，79，46，84二、选择题1-5DBDBB6-10BBDAD11-15CCCBD三、判断题1—5：××××√6—10：××√√×四、应用题1.12345（1分）54321（1分）12354（1分）32145（1分）32154（1分）答案仅供参考并不唯一，改题时具体分析2.（左右子树各2分）先序序列：ABDFCEGH（2分）3.4.一条正确边给1分，全对给满分。5.五、算法分析与设计1.1.结构体定义：#defineMAXQSIZE100typedefstruct{QElemType*base;intfront;intrear;}SqQueue;（2分）若没写出代码，仅写出算法思想给5分。循环队列入队算法：StatusEnQueue(SqQueue&Q,QElemTypee){if((Q.rear+1)%MAXQSIZE==Q.front)ReturnERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}（3分）循环队列出队算法：StatusDeQueue(SqQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;E=Q.base[Q.front]Q.front=(Q.front+1)%MAXQSIZE;returnOK;}（3分）2.A.拆半查找算法intSearch_Bin(SSTableST,KeyTypekey){intlow,high,mid;low=1;high=ST.length;（1分）while(low=high)（1分）{mid=(low+high)/2;（1分）if(key==ST.elem[mid].key))returnmid;（1分）elseif(keyST.elem[mid].key))high=mid-1;（1分）elselow=mid+1;（1分）}return0;}若没写出代码，仅写出算法思想给3分。A.拆半插入排序算法voidBInsertSort(Sqlist&L){for(i=2;i=L.length;++i){L.r[0]=L.r[i];（1分）low=1;high=i-1;（1分）while(low=high){m=(low+high)/2;（1分）if(l.r[0].keyL.r[m].key)high=m-1;（1分）elselow=m+1;}for(j=i-1;j=high+1;--j)L.r[j+1]=L.r[j];（1分）L.r[high+1]=L.r[0];（1分）}}若没写出代码，仅写出算法思想给3分。