数据结构导论2013年10月真题（02142） 数据结构导论2013年10月真题及答案解析（02142） 数据结构导论2013年10月真题及答案解析（02142），该试卷为数据结构导论自考历年真题试卷，包含答案及详细解析。 一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1.下列几种算法时间复杂度中，最大的是( ) A.O(1)B.O(n)C.O(log2n)D.O(n2) 2.数据结构中结点按逻辑关系依次排列形成一条“链”的结构是( ) A.集合B.图结构C.树形结构D.线性结构 3.在表长为100的顺序表中做插入运算，平均移动素的次数为( ) A.25B.33C.50D.100 4.已知尾指针的单向循环链表中，在第一个结点后面插入一个新结点，该算法的时间复杂度为( ) 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的结点有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.log2nB.(n-1)/2C.n/2D.(n+1)/2 13.二叉排序树中，根的( ) A.左子树是二叉排序树、右子树不一定是二叉排序树B.左子树是二叉排序树、右子树也是二叉排序树C.左子树不一定是二叉排序树、右子树是二叉排序树D.左子树不一定是二叉排序树、右子树也不一定是二叉排序树 14.冒泡排序的时间复杂度为( ) A.O(n)B.O(nlog2n)C.O(n2)D.O(log2n) 15.关于稳定性的表述，正确的是( ) A.稳定性是排序方法本身的特性，与数据无关B.稳定性不是排序方法本身的特性，与数据有关C.稳定性是排序方法本身的特性，与数据有关D.稳定性不是排序方法本身的特性，与数据无关 二、填空题(本大题共13小题，每小题2分，共26分) 11.数据中不可分割的最小标识单位是__________。 12.双向循环链表中，在p所指结点的后面插入一个新结点*t，需要修改四个指针，分别为：t->prior=p; __________; p->next->prior=t; p->next=t;。 13.在带有头结点的循环链表中，头指针为head，判断指针p所指结点为首结点的条件是__________。 14.素的进栈次序为1，2，3，…，n，出栈的第一个素是n，则第k个出栈的素是__________。 15.在栈结构中，允许插入和删除的一端称为__________。 16.100个结点的二叉树采用三叉链表存储时，空指针域NULL有__________个。 17.某二叉树的先序遍历序列为ABKLMNO，中序遍历序列为BLKANMO，则该二叉树中结点A的右孩子为结点__________。 18.一个二叉树的最少结点个数为__________。 19.图中第一个顶点和最后一个顶点相同的路径称为回路。除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为__________。 110.设查找表有n个数据素，则二分查找算法的平均查找长度为__________。 111.用键值通过散列函数存储位置的这种存储方式构造的存储结构称为__________。 112.若在线性表中采用二分查找法查找素，则该线性表必须按值有序，并且采用__________存储结构。 113.堆分为最小堆和最大堆，若键值序列{k1, k2, …, kn}，满足
，则这n个键值序列{k1, k2,…, kn}是__________。 三、应用题(本大题共5小题，每小题6分，共30分) 21.设一个链栈的输入序列为X，Y，Z，试写出出栈的所有可能的输出序列及其操作步骤。 22.设二叉树的先序遍历序列为DCBAHEIFG，中序遍历序列为ABCHDIEFG，试画出该二叉树并写出后序遍历序列。 23.已知连通带权图如题31图所示，试利用普里姆(Prim)算法，从顶点A出发，构造它的最小生成树，画出构造过程。
题31图 24.给定表(28，15，55，3，71，75，10，22，56)，试按素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。 25.应用直接选择排序算法，对初始关键字序列为48，35，61，98，82，18，29，48的记录进行从小到大排序，写出排序过程和结果。 四、算法设计题(本大题共2小题，每小题7分，共14分) 31.单链表的结点结构定义如下：typedef struct node{ int data; struct node *next; }Node, *LinkList;试编写在带头结点的单链表head中查找第1个素值小于x的结点的实现算法Node *GetLinklist( LinkList head, int x)，若找到，则返回指向该结点的指针，否则返回NULL。 32.假设树采用孩子兄弟链表表示法，其结构定义如下：typedef struct tnode{ DataType data; struct tnode *son, *brother;}*Tree;试编写算法void leveltree(Tree root)实现树的按层次遍历。
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/54884.html
