2013年云南昆明理工大学数据结构考研真题A卷.doc

发布时间：2022-09-16 发布人：admin 分类：说明书资料大小：0.07M 资料格式：doc 举报版权申诉

第1页 / 共3页

第2页 / 共3页

第3页 / 共3页

文本预览

2013 年云南昆明理工大学数据结构考研真题 A 卷一、单项选择题：（每题 3 分，共 30 分） 1．若进栈序列为 1，2，3，4，则不可能得到的出栈序列为______。 A：3，2，1，4 B：3，2，4，1 C：4，2，3，1 D：2，3，4，1 2．深度为 K 的完全二叉树所含叶结点的个数最多为_________。 A：2 k B：2 k-1 C：k D：2k 3．衡量查找算法效率的主要标准是_________。 A：元素个数 B：所需的存储量 C：平均查找长度 D：算法难易程度 4. 与线性表的链接存储相符的特性是________。 A：插入和删除操作灵活 B：需要连续存储空间 C：便于随机访问 D：存储密度大 5. 6 个顶点的连通图的深度优先生成树，其边数为____。 A：6 B： 5 C：7 D： 4 6．n 个结点的二叉树，若用二叉链表作为存储结构，则空闲的左、右孩子链域数为。 A：n B：2n C：n-1 D：n+1 7．在下列排序算法中，最坏的情况下，时间复杂度为 O(n2)的排序算法是______。 A：堆排序 B：希尔排序 C：归并排序 D：快速排序 8. 在单向循环链表中，若头指针为 h，那么 p 所指结点为尾结点的条件是______。 A：p=NULL B：p->next=NULL C：p=h D：p->next=h

9. 设有如下遗产继承规则：夫妻可以互相继承遗产，子女可以继承父母遗产，子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是______。 A：树 B：图 C：数组 D：二叉树 10. 对于顺序存储的队列，存储空间大小为 n，头、尾指针分别为 F 和 R，若将其看成一个首尾相接的圆环，则队列中的元素个数为______。 A：R-F B：n+R-F C：(R-F+1)%n D：(n+R-F)%n 二、判断题（每题 2 分，共 20 分） 1．数据的存储结构是数据的逻辑结构的存储映像。（） 2. 用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系（） 3. 非线性结构中，至少存在一个元素不止一个直接前驱或不止一个直接后继。（） 4. 树的最大特点是一对多的层次结构。（） 5. 队列的特点是先进先出。（） 6. 图的最小生成树是唯一的。（） 7. 线性表是广义表的特殊形式。（） 8. 由后序遍历序列和中序遍历序列能唯一地确定一棵二叉树。（） 9. 散列表是一种链式存储结构。（） 10. 快速排序并非在任何情况下都比其他排序方法速度快。（）三、简答题（共 60 分） 1．线性表有两种存储结构：一是顺序表，二是链表，请简述各自的优缺点（共 12 分） 2. 假设有 n 个关键字，具有相同的散列函数值，如果用线性探测法把这 n 个关键字放到散列表中，则一共要做多少次探测？（共 12 分） 3. 对 n 个顶点的无向图，采用邻接矩阵表示，试回答下列有关问题：(共 18 分) (1)：图中有多少条边？（6 分）

(2)：如何判断任意两个顶点 i 和 j 是否有边相连？(6 分) (3): 任意一个顶点的度是多少？(6 分) 4. 下图一为无向图，1）请写出它的邻接矩阵；（8 分） 2）按 Prim（普里姆）算法求其最小生成树（10 分）。（共 18 分） 5 1 4 5 6 2 3 6 0 4 3 5 1 6 5 2 图一四、已知表(K1,K2,K3,…，Kn)，其中 Ki 为正整数。设计一个算法，能在 O(n)的时间内将线性表划分成两部分，其左半部分的每个关键字均小于 K1，右半部分的关键字值均大于等于 K1。算法可用 C 或 pascal 语言进行描述。（共 20 分）五、已知一个单链表中每个结点存放一个整数，并且其结点数不少于 2。试设计算法以判断该链表中从第二项起的每个元素值是否等于其序号的平方减去其前驱的值。若全部满足，返回真值，否则返回假值。（共 20 分）

分享到：

赞收藏

资料库

2013年云南昆明理工大学数据结构考研真题A卷.doc

相关推荐

考研

热门标签

最新资料