2013~2014学年第1学期南阳理工学院软件学院数据结构课程试卷a卷

《2013~2014学年第1学期南阳理工学院软件学院数据结构课程试卷a卷》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、南阳理工学院2013–2014学年第一学期试卷（A卷）课程：《数据结构》课程号：1504108130考核方式：（闭卷）课程性质：专业必修课适用对象：12软工媒体、11软工NET、12网工、12网安本科题号一二三四五总分复核人满分1030103020100得分一、填空题：（每空1分，共10分）评卷人得分1．_______________是相互之间存在一种或多种特定关系的数据元素的集合。2．一个算法必须满足_______________、确定性、可行性、输入和输出五个重要的特性。3．链接存储的存储结构所占存储空间分两部分，一部分存放结点值，另一部分存放表

2、示_______________。4．在二叉树的第i层上至多有_______________个结点。5．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_______________倍。6．具有n个顶点的有向图最多有_______________条边。7．对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为_______________。8．_______________又称最优树，是一类带权路径长度最短的树。9．从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为

3、_______________。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．(*

4、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．串中所含不同字符

5、的个数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．逻

6、辑和存储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三、判断题：（每题

7、1分，共10分）评卷人得分（说明：认为陈述正确的在括号内打“√”；否则在括号内打“×”）1．线性表的链式存储结构优于顺序存储结构。（）2．线性表中每个元素都有一个且仅有一个直接前驱和直接后继。（）3．线性表若采用链式存储结构时，要求内存中可用存储单元的地址必须连续。（）4．栈又称先进先出的线性表。（）5．深度为k的满二叉树含有2k-1个结点。（）共5页第2页6．遍历二叉树可采用深度优先搜索算法进行。（）7．空串是由空格构成的串。（）9．若一组记录的排序码为（46,79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结

8、果为（40，38，46，56，79，84）。（）9．从未排序序列中挑选元素，并将其依次放入已排序序列初始时为