数据结构（b卷）
不含图结构）
一 、简答问题：（每小题4分，16分）
1. 四类基本数据结构的含义和特点。
2. 简述栈和队列的共同点和不同点。它们与线性表有什么关系？
3. 举例说明什么是抽象数据类型。
4. 算法的定义和特性。
二、判断正误，正确在（ ）内打√，否则打 （每小题1分，共5分）
)（1）由树的中序表示和前序表示可以导出树的后序表示。
)（2）将一棵树转换为二叉树表示后，该二叉树的根结点没有右子树。
)（3）采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的前序遍历结果是一样的。
)（4）一棵huffman树是带权路径长度最短的二叉树，权值较大的外结点离根较远。
)（5）用一维数组存储二叉树时，是以先根遍历的次序存储结点。
三、单项选择题(4分， 每小题1分)
1．对线性表，在下列哪种情况下应当采用链表表示？
a）经常需要随机地存取元素 b）经常需要进行插入和删除操作。
c）表中元素需要占据一片连续的存储空间 d）表中元素的个数不变。
2．在待排序文件已基本有序的前提下，下述排序方法中效率最高的是。
a)直接插入排序 b)简单选择排序 c)快速排序 d)归并排序。
3．设有关键码序列(q,g,m,z,a,n,p,x,h),下面哪一个序列是从上述序列出发建堆的结果？
a)a,g,h,m,n,p,q,x,z b)a,g,m,h,q,n,p,x,z
c)g,m,q,a,n,p,x,h,z d)h,g,m,p,a,n,q,x,z
4．以下哪一个术语与数据的存储结构无关？
a)栈 b)散列表 c)穿线树 d)双链表。
四、填空题：(每小题2分，共 20分)
1．字符a、b、c依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成。
个不同的字符串。
2．设仅包含根结点的二叉树的高度为0,则高度为k的二叉树的最大结点数为 。
3．在顺序表(2,5,7,10,14,15,18,23,35,41,52)中，用二分法查找关键码值12，所需的关键码比较次数为： 。
4．快速排序的最坏情况，其待排序的初始排列是 .
5. 二叉树的先序遍历序列为：efhigjk，中序遍历序列为：hfiejkg，则该二叉树根的右子树的根是： 。
6． 顺序表（即顺序存储结构的线性表）中插入一个元素，平均需要移动个元素。
7．已知二维数组a[0..20][0..10]采用行序为主方式存储，每个元素占4个存储单元，并且a[0][0]的存储地址是1016, 则a[9][8]的存储地址是
8．循环单链表la中，指针p所指结点为表尾结点的条件是
9．n个结点的二叉树，采用二叉链表存放，空链域的个数为 .
10．要在一个单链表中p所指结点之后插入s所指结点时，
应执行和的操作。
五、构造题：（25分）
1． 对以下关键字序列建立哈希表：（sun,mon,tue,wed,thu,fri,sat）,哈希函数为h(k)=（k中最后一个字母在字母表中的序号）mod 7。用线性探测法处理冲突，要求构造一个装填因子为0.
7的哈希表，并分别计算出在等概率情况下查找成功与不成功的平均查找长度。
2．已知一棵树如图1所示，请将该树转化为二叉树。
3．给定权值，构造一棵带权路径长度最短的二叉树，并计算基带权路径长度。
4. 已知关键码序列为，试画出逐个插入这8个关键码后的二叉排序树。
5．设有关键码序列(q,g,m,z,a,n,p,x,h),将其筛选为一个堆序列。
六、设计题： （30分）
1． 假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。
2． 编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前。要求：采取顺序存储结构，至多使用一个记录的辅助存储空间，算法的时间复杂度为o(n)；[8分]
数据结构实习报告
精选范文 数据结构实习报告 共2篇 一 需求分析1 程序所实现的功能 2 程序的输入，包含输入的数据格式和说明 3 程序的输出，程序输出的形式 4 测试数据，如果程序输入的数据量比较大，需要给出测试数据 5 合作人及其分工。二 设计说明1 主要的数据结构设计说明 2 程序的主要流程图 3 程序的主要...
2019下数据结构 A
卷号 a 二o一二 二o一三学年第一学期期末考试。数据结构 期中 试题。11电类专业用 闭卷 注意 学号 姓名和所在年级班级不写 不写全或写在密封线外者，试卷作废。一 选择题 每题2分，共10 2 20分 1.一棵树高为k的完全二叉树至少有 个结点。a 2k 1b.2k 1 1 c.2k 1 d.2...
数据结构 I卷
班级学号姓名得分。题目部分，卷面共有45题，100分，各大题标有题量和总分 一 判断正误 11小题，共11分 1 即使对不含相同元素的同意输入序列进行两组不同的 合法的入栈和出栈组合操作，所得的输出序也一定相同。2 栈和队列都是限制存取点的线性结构。3 任何一个非空广义表，其表头可能是单元素或广义表...