2010年山西太原科技大学数据结构考研真题.doc

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

第1页 / 共4页

第2页 / 共4页

第3页 / 共4页

第4页 / 共4页

文本预览

2010 年山西太原科技大学数据结构考研真题一. 名词解释（每小题 3 分，共 30 分） 1. 数据元素 2.栈 3. 定长记录文件 4.抽象数据类型 5.森林 6. 拓扑排序 7.连通分量 8. 散列 9.排序 10.赫夫曼（Huffman）树二.选择题。（每题 3 分，共 30 分） 1.求字符串 T 在字符串 S 中首次出现的位置的操作称为（） A. 串的模式匹配 B.求串的长度 C.求子串 D.串的连接 2.如果只想得到 1024 个元素序列中第 5 个最小元素之前的部分排序的序列，用（）方法最快。 A.起泡排序 B.快速排序 C. 简单选择排序 D.堆排序 3.设无向图的顶点个数为 n，则该图最多有（）条边。 A. n-1 B.n(n-1)/2

C. n(n+1)/2 D.n(n+1) 4.具有 128 个结点的完全二叉树的高度为（）。 A.6 B.7 C.8 D.9 5.线性链表不具有的特点是（）。 A.不必事先估计所需存储空间大小 B.所需空间与线性表长度成正比 C.插入与删除时不必移动元素 D. 随机访问 6.设 F 是一个森林，B 是由 F 转换得到的二叉树，F 中有 n 个非叶子结点，则 B 中右指针域为空的结点有（）个。 A.-1 B.n C. n+1 D.n+2 7.对稀疏矩阵进行压缩存储目的是（）。 A.便于进行矩阵运算 B.便于输入和输 C.节省存储空间 D.降低运算的时间复杂度 8.线性表（al，a2，…，an）以链接方式存储时，访问第 i 位置元素的时间复杂度为（） 9.输入序列为 ABC，可以变为 CBA 时，经过的栈操作为（） 10.在有向图中每个顶点的度等于该顶点的（）

A.入度 B.出度 C.入度与出度之和 D.入度与出度之差三.综合题（每题 15 分，共 60 分） 1.写出下图二叉树的先序遍历序列和中序遍历序列，如果该图是由森林转换过来，试画出该森林。 2.下图为一个带权的无向网，针对该图回答下列问题∶ （1）写出从顶点 a 开始访问的深度优先遍历序列和广度优先遍历序列。（2）画出由克鲁斯卡尔算法生成的最小生成树。 3.将关键字 53，78，65，17，83，9，74，45，23，插入到一棵初始为空的二叉排序树中，画出由这些关键字组成的二叉排序树，并计算在该二叉排序树查找时的平均查找长度（只考

虑查找成功的情况）。 4.在堆排序、快速排序和归并排序中∶ （1）.若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法? （2）.若只从排序结果的稳定性考虑，则应选取哪种排序方法? （3）.若只从平均情况下排序最快考虑，则应选取哪种排序方法? （4）.若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法? 四.算法设计题（每题 15 分，共 30 分） 1.设 L 为带头结点的单链表，表中元素无序，试编写算法，删除表中值相同的多余元素。 2.写一算法求二叉树中结点的总个数。（二叉树的数据结构定义 3 分，算法 12 分）

分享到：

赞收藏

资料库

2010年山西太原科技大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料