中国矿业大学理学院 2012-2013学年。
数据结构》试卷（a卷）（考试时间：100分钟）
-==注意：所有答案都必须写在答题纸上！==
一．单项选择（每小题2分，共20分）
1．栈的元素输入序列为12345，不可能的输出序列是 __
a）23415 （b）54231 （c）23145 （d）15432
2．二叉树（设根在第1层）第i 层结点的结点个数最多是___
a）2i-1b）2ic）2id） 2i-1
3．二叉树（设根在第1层）顺序存储在一维数组中，则g所在层次为___
a）1b）2c）3d）4
4．当利用大小为n的数组存储表示一个循环队列时，其最大长度为___
a）n-2b）n-1 （c）nd）n+1
5．n个顶点的有向完全图中弧的数目为___
a）n2/2b）n-1 （c）n2d）n(n-1)
6．双向循环链表中插入一个节点需要修改___个指针。
a）1b）2c）3d）4
7．计算哈希表查找成功的平均查找长度时可不考虑___的影响。
a）表中记录数 （b）装填因子α （c）表长 （d）哈希函数。
8．在aoe网络中，顶点表示___
a） 时间 （b）事件 （c）活动 （d）次序。
9．广义表x=(a, (b, c, d))的长度为___
a）1b）2c）3d）4
10．一棵完全二叉树具有1000个结点，其中有___个叶子结点。
a）333b）256 （c）500 （d）499
二．填空（每空3分，共30分）
1．根据数据元素间关系的不同特性，通常有4类基本结构。
2．队列的特点是___队列的插入操作在___进行，栈的特点是___删除操作在___进行。
3．n个结点的二叉树，其最小高度为最大高度为。
4．用二叉链表存储n个结点的二叉树，则总共___个指针域中有___个为空指针。
5．以折半查找方法搜索一个线性表时，此线性表必须是___存储的___表。
6．图的最小生成树算法有___和___两种。
7．n个顶点的无向连通图至少有___条边，至多有___条边。
8．在排序过程中需要进行两种基本操作分别是___和。
三．简答（每小题10分，共30分）
1．已知二叉树前序序列为abecdfghij，中序序列为ebcdafhigj，给出逐步形成二叉树的过程。
2．假定通信电文仅由8个字母组成，出现的频率分别为8%, 14%,5%, 7%, 3%, 23%, 29%, 11%，试为这8个字母设计huffman编码（画出huffman树，列出编码表）。
3．给出如下有向图的邻接矩阵。
四、算法设计（20分）
编写c函数计算二叉树叶结点个数，函数原型int fx(bitnode * t)；调用时将二叉树的根指针传入，返回其叶结点个数。二叉树结点类型定义参考如下，可直接引用：
typedef struct bnode{
char data;
bnode * lchild, *rchild;
bitnode;
-==注意：所有答案都必须写在答题纸上！==
中国矿业大学理学院 2012-2013学年。
数据结构》（a卷）答题纸。
专业班级学号姓名。
一．单项选择（每小题2分，共20分）
二．填空（每空3分，共30分）
三．简答（每小题10分，共30分）
四、算法设计（20分）
2019数据结构试卷A
哈尔滨工程大学试卷。考试科目 数据结构a 卷。一 单项选择题 每空1分，共15分 1 以下数据结构中，从逻辑结构看，和其他数据结构不同。a 树b 顺序表 c 链队列d 循环队列。2 对于链式存储的线性表，查找结点和删除结点的时间复杂度为 a o n o n b o n o 1 c o 1 o n d...
数据结构常用算法数据结构算法
void union list la,list lb union void mergelist list la,list lb,list lc else while i la len while j lb len mergelist status initlist sq sqlist l elemt...
数据结构2019级数据结构大作业
2011级数据结构大作业。1 公园导游图。给出一张某公园的导游图，用图的顶点表示各个景点 景点个数大于等于30 每个景点有属性值 h，t，c 其中h表示游览完成这个顶点给游客带来的happiness，t表示游览这个景点需要的时间，c表示游览这个景点需要的费用，顶点之间的边表示路径 边具有属性值w，表...