02142数据结构导论.doc

自考单科包过联系Q 187149962 实力验证 2017年4月高等教育自学考试全国统一命题考试 数据结构导论试卷 (课程代码02142) 本试卷共4页，满分l00分，考试时间l50分钟。 考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。 2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。 3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。 4．合理安排答题空间。超出答题区域无效。 第一部分选择题(共30分) 一、单项选择题(本大题共l5小题。每小题2分，共30分) 在每小题歹硅出的四个备选项中只有一个是符合题目要求的．请将其选躜并将“答题卡”的相应代码涂黑。错涂、多涂或未涂均无分。 1．任意两个结点之间都没有邻接关系，组织形式松散，这种组织形式称为 A．集合 B．线性结构 C．树形结构 D．图结构 2．表示数据元素之间的关联方式通常采用的存储方式是 A．顺序存储方式和索引存储方式 B．链式存储方式和散列存储方式 C．顺序存储方式和链式存储方式 D．链式存储方式和索引存储方式 3．下面几种算法时间复杂度阶数中，最小的是 A．O(1092n) B．0(n) C．O(n2) D．0(2“) 4．双向循环链表中，在指针P所指结点的后面插入一个新结点*t，正确的语句为 A．t->prior—P； B．t->prior=p； t->next=p-->next； t->next=p->next； p->next一>prior=t； p->next=t卜 p->next=t； C．t一>prior—P； D．p->next-->prior=t； p一>next一>prior=t； p->next=t； t一>next=p-->next； P一>next=t； 5．栈的修改原则是 A．先进先出 B。后进先出 C．栈空则进 D．栈满则出 6．设有一顺序队列S0，已知尾指针rear<队列的最大长度一l，则数据x进行人队列操作的语句为 A．SQ．front SQ．front+1； B．SQ．front=S0．rear+1； C．SQ．front=S0．front+1；S0．dataFSq．front-]=x； D．SQ．rear—S0．rear+1；SQ．datarSQ。rear]一x； 7．一个数组的第一个元素的存储地址是100，每个元素占2存储单元，则第5个元素的存储地址是______m A．105 B.108 C．115 D．118 8．树中叶子的度是 A．0 B．1 C．2 D．3 9．将一棵有n个结点的完全二叉树按层编号，若编号i所对应的结点为A，且i>1，则A的双 亲的编号为 A．i B.i/2 C．[i/2] D．[i/2] 10．含有100个结点的二叉树采用二叉链表存储时，空指针域NULL的个数是 A．99个 B．100个 C．101个 D．200个 11．一个具有n个顶点的有向完全图的弧数为 A．n(n一1)/2 B．n(n一1) C.n2/2 D．n2 12．图的深度优先搜索遍历类似于树的 A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 13．静态查找表指对查找表只进行两项操作，即 A．插入和删除一个数据元素 B．查找表中某一元素和插入一个数据元素 C．读取表中“特定”数据元素和删除一个数据元素 D．查找表中某一元素和读取表中“特定”数据元素 14．若在线性表中采用二分查找法查找元素，该线性表应该 A．元素按值有序，且采用链式存储结构 B．元素按值无序，且采用链式存储结构 C．元素按值有序，且采用顺序存储结构 D．元素按值无序，且采用顺序存储结构 15．下列排序方法中不稳定的是 A．冒泡排序 B．二路归并 C．堆排序 D．直接撬入排序 第二部分 非选择题(共70分) 二、填空题(本大题共l3小题，每小题2分。共26分) 16．从宏观上看，数据、数据元素和_____反映了数据组织的三个层次。 17．线性表、栈和队列中的元素具有相同的逻辑结构，即 _____。 18．一个算法的时空性是指该算法的时间性能和 _____。 19．为了便于运算的实现，在单链表的第一个结点之前增设一个类型相同的结点，称之为_____。 20．假设一个8阶的上三角矩阵A按照列优先顺序压缩存储在一维数组8中，则B数组的大小应为_____。 21．在栈中，允许进行插入和删除操作的一端称为_____。 22．即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果， 这种评价算法好坏的因素称为_____。 23．设栈S的初始状态为空，若元素a，b，C，d依次进栈，得到的出栈序列是c，d，b，a，则栈的容量至少是_____。 24．若一棵完全二叉树有l4个结点，则它的深度为_____。 25．树的双亲表示法由一个一维数组构成，数组的每个分量包含_____和双亲域两个域。 26．如果包含n个顶点的连通图G的一个子图G 7的边数大于n一1，则G’中一定有 _____。 27．在含有9个元素的有序表(2，4，12，18，23，37，49，51，68)中二分查找关键字(关键字即为数据元素的值)为37的元素时，所需进行的比较次数为_____次。 28．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为_____排序法。 三、应用题(本大题共S小题。每小题6分，共30分) 29．设A、B、C、D、E五个元素依次进栈(进栈后可立即出栈)，问能否得到下列序列： (1)A，B，C，D，E； (2)A，C，E，B，D 若能得到，刚给出该序列的操作过程(用push(A)表示A进栈，pop(A)表示A出栈)；若不能，则说明理由。 30．已知一棵二叉树的先序遍历结果为ABDCEF，中序遍历结果为DBAECF，试画出这棵二叉树，并写出这棵二叉树的后序遍历序列。 33．将一组键值{83，69，41，22，15，33，8，76)应用二路归并排序算法从小刭大排序，试写出各趟 排序的结果。 四、算法设计题(本大题共2小题，每小题7分。共l4分) 34．设计一个算法实现以下功能：在整型数组A[n]中查找值为k的元素，若找到，贝!1输出其位置i(0≤i≤n一1)，否则输出一l作为标志。 35．已知二叉链表的类型定义如下： typedef struct btnode {DataType data； struct btnode*lchild。*rchild； }*BinTree； 利用二叉树遍历的递归算法，设计求二叉树的高度的算法Height(BinTree bt)。 自考单科包过联系Q 187149962 实力验证