02142数据结构导论 全国13年10月自考 试题

《02142数据结构导论 全国13年10月自考 试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、全国2013年10月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。1．下列几种算法时间复杂度中，最大的是A．O（1）B.O（n）C.O（nlog2n）D.O（n2）2．数据结构中结点按逻辑关系依次排列形成一条“链”的结构是A．集合B.图结构C.树形结构D.线性结构3．在表长为100的顺序表中做插入运算，平均移动元素的次数为A．25B.33C.5

2、0D.1004．已知尾指针的单向循环链表中，在第一个结点后面插入一个新结点，该算法的时间复杂度为A．O（1）B.O（log2n）C.O（n）D.O(n2)5．下列表述正确的是A．栈空时出栈产生“上溢”，栈满时进栈产生“下溢”B.栈空时出栈产生“下溢”，栈满时进栈产生“上溢”C.栈空时出栈和栈满时进栈均产生“上溢”D.栈空时出栈和栈满时进栈均产生“下溢”6.队列操作的原则是A.先进先出B.后进先出C.先进后出D.只进不出7．一棵深度为6的满二叉树有A．63个结点B.64个结点C.127个结点D.128个结点8.在一棵度为

3、3的树中，度为3的结点有4个，度为2的结点有2个，度为1的结点有3个，则度为0的结点有A.8个B.10个C.11个D.12个9．一棵二叉树T，度为2的结点数为20个，则叶子结点数为A．19个B.20个C.21个D.22个10．有10个叶结点的哈夫曼树中共有A．10个结点B.11个结点C.19个结点D.21个结点11．求图中两个结点之间的最短路径采用的算法是A．广度优先搜索（BFS）算法B.克鲁斯卡尔（Kruskal）算法C.普里姆（Prim）算法D.迪杰斯特拉（Dijkstra）算法12．顺序查找算法的平均查找长度为A

4、．log2nB.（n-1）/2C.n/2D.（n+1）/213．二叉排序树中，根的A．左子树是二叉排序树、右子树不一定是二叉排序树B.左子树是二叉排序树、右子树也是二叉排序树C.左子树不一定是二叉排序树、右子树是二叉排序树D.左子树不一定是二叉排序树、右子树也不一定是二叉排序树14．冒泡排序的时间复杂度为A．O(n)B.O(nlog2n)C.O(n2)D.O(log2n)15．关于稳定性的表述，正确的是A．稳定性是排序方法本身的特性，与数据无关B.稳定性不是排序方法本身的特性，与数据有关C.稳定性是排序方法本身的特性，

5、与数据有关D.稳定性不是排序方法本身的特性，与数据无关二、填空题(本大题共13小题，每小题2分，共26分)16．数据中不可分割的最小标识单位是__________。17．双向循环链表中，在p所指结点的后面插入一个新结点*t，需要修改四个指针，分别为：t->prior=p；__________；p->next->prior=t；p->next=t；。18.在带有头结点的循环链表中，头指针为head，判断指针p所指结点为首结点的条件是__________。19．元素的进栈次序为1，2，3，…，n，出栈的第一个元素是n，则第

6、k个出栈的元素是__________。20．在栈结构中，允许插入和删除的一端称为__________。21．100个结点的二叉树采用三叉链表存储时，空指针域NULL有__________个。22.某二叉树的先序遍历序列为ABKLMNO，中序遍历序列为BLKANMO，则该二叉树中结点A的右孩子为结点__________。23．一个二叉树的最少结点个数为__________。24．图中第一个顶点和最后一个顶点相同的路径称为回路。除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为__________。25．设查找表

7、有n个数据元素，则二分查找算法的平均查找长度为__________。26．用键值通过散列函数获取存储位置的这种存储方式构造的存储结构称为__________。27．若在线性表中采用二分查找法查找元素，则该线性表必须按值有序，并且采用__________存储结构。28．堆分为最小堆和最大堆，若键值序列{k1,k2,…，kn}，满足，则这n个键值序列{k1,k2,…，kn}是__________。三、应用题(本大题共5小题，每小题6分，共30分)29．设一个链栈的输入序列为X，Y，Z，试写出出栈的所有可能的输出序列及其操作

8、步骤。30．设二叉树的先序遍历序列为DCBAHEIFG，中序遍历序列为ABCHDIEFG，试画出该二叉树并写出后序遍历序列。31．已知连通带权图如题31图所示，试利用普里姆（Prim）算法，从顶点A出发，构造它的最小生成树，画出构造过程。题31图32．给定表（28，15，55，3，71，75，10，22，56），试按元素在表中的顺