2016年10月自考《2331数据结构》真题和答案.doc

2016年10月高等教育自学考试全国统一命题考试 (课程代码02331) 7页，满分l00分，考试时间l50分钟。 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。 2．第一部分为选择题。必须对应试卷上的题号使用2铅笔将“答题卡”的相应代码涂黑。 3．第二部分为非选择题。毖须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。 4．合理安排答题空间，超出答题区域无效。 (共30分) (本大题共l5小题，每小题2分，共30分 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题 卡”的相应代码涂黑。错涂、多涂或未涂均无分。 1．下列选项中，不属于线性结构特征的是 A．数据元素之间存在线性关系 B．结构中只有一个开始结点 C．结构中只有一个终端结点 D．每个结点都仅有一个直接前趋 2．设l7个元素的顺序表中，若将第个元素e移动到第个位置， 不改变除e外其他元素之间的相 3．若用一个大小为7的数组作为循环队列的存储结构，且当前rew和盘0nt的值分别 为2和4，在此之前的操作是从队列中删除了一个元素及加入两个元素，请问这3 个操作之前rear和矗0nt的值分别是 A．0和l B．0和3 C．3和6 D．4和5 4．已知广义表LS=(((a))，((b，(c))，(d，(e，f)))，0)，LS的长度是 A．2 ．3 C．4 D. 5 5．一棵完全二叉树T的全部k个叶结点都在同一层中且每个分支结点都有两个孩子结点。于中包含的结点数是 A．k B. 2k-1 C．D．2k1 6．如果某二叉树的前序遍历序列为abced，中序遍历序列为cebda，则该二叉树的后序 遍历序列是 A．cedba B．decba C．ecdbaD．ecbad 7．一个森林有棵树，顶点总数为，则森林中含有的总边数是 A．m B. n-l C．n-m D．+m 8．设图的邻接A如下所示。各顶点的度依次是 A．1，2，1，2 ．2，2，1，l C．3，4，2，3 D．4，4，2，2 9．若对下厦无向图进行深度优先遍历，得到的正确遍历序列是 A．h，C，a，b，d，e，g，f B．e，a，，b，h，c，d Cd，b，c，a，h，e， D．a，b，C，d，h，e， 10．己知有向图G如下所示，G的拓扑序列是 A．a，b，e，c，d， B．c，b，d，e，g Ca，C，d，e，b，f，g D. a，c，d，b，e，g 11．下列排序算法中，在每一趟都能选出一个元素放到其最终位置上的是 A．插入排序 B．希尔排序 C．归并排序D．直接选择排序 12．对一组数据(2，l2，16，88，5，10)进行排序，若前3趟排序结果如下： 第一趟：2，12，l6，5，10，88 第二趟：2，12，5，l0，16，88 第三趟：2，5，10，l2，l6，88 则采用的排序方法是 A．冒泡排序 B．希尔排序 ．归并排序 D．基数排序 13．设有序表为{9，l2，21，32，41，45，52}，当二分查找值为52的结点时，元素之间的比较次数是 A．1 B．2 C．3 D．4 14．下列选项中，既熊捌回事存储结构也能在链式存储结构上进行查找的方法是 A．散列查找 B．顺序查找 C．二分查找 D．以上选项均不能 15．在一棵5阶B树中，每个非根结点中所含关键字的个数最少是 A．1 ．2 C．3 D．4 第二部分 非选择题(共70分) 二、填空题(本大题共l0小题，每小题2分，共20分) 16．两个栈和S2共用含100个元素的数组[0一99]，为充分利用存储空间，若S2的 栈底元素保存在S[99]中，则的栈底元素保存在中。 17．在一个单链表中，已知指针变量q所指结点不是表尾结点，若在q所指结点之后插 入指针变量S所指结点，则正确的执行语句是 18．设顺序表第个元素的存储地址是1000，每个数据元素占6个地址单元，则第 个元素的存储地址是。 19．二叉树采用顺序存储方式保存，结点Z保存在数组A[7]L 则Y保存在中。 20．一棵二叉树中，度数为l的结点个数为1，度数为2的结点个数为n2，则叶结点的 21．已知广义表LS=((≈b)，c，d)，head(LS)是。 22．在无向图G的邻接矩阵A中，=。 23已知大根堆中的所有关键字均不相同，最大元素在难项，第2大元素可能存在的位置有2个，第3大元素可能存在的位置有个。 24．在有个元素组成的顺序表上进行顺序查找。若查找每个元素的概率相等，则查找 成功时平均查找长度是