数据结构期末考试试题及答案

《数据结构期末考试试题及答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、贵州大学理学院数学系信息与计算科学专业《数据结构》期末考试试题及答案(2003-2004学年第2学期)一、单项选择题1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。(A)、正确性(B).可行性(C).健壮性(D).输入性2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。for(i=n-1；i>=0；i--)for(j=0；j

2、限制4．顺序存储结构的优势是（）。（A）、利于插入操作（B）、利于删除操作（C）、利于顺序访问（D）、利于随机访问5．深度为k的完全二叉树，其叶子结点必在第（）层上。（A）、k-1（B）、k（C）、k-1和k（D）、1至k6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）（A）、11（B）、13（C）、48（D）、377．图的Depth-FirstSearch(DFS)遍历思想实际上是二叉树（）遍历方法的推广。（A）、先序（B）、中序（C）、后序（D）、层序8．在下列链队列Q中，元素a出队的操作序列为（）bcd∧afrontrearQ（A）、

3、p=Q.front->next;p->next=Q.front->next;（B）、p=Q.front->next;Q.front->next=p->next;（C）、p=Q.rear->next;p->next=Q.rear->next;（D）、p=Q->next;Q->next=p->next;9．Huffman树的带权路径长度WPL等于（）（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和（D）、根结点的值第127页共127页10．线索二叉链表是利用（）域存储后继结点的地址。（A）、lchild（B）、dat

4、a（C）、rchild（D）、root二、填空题1．逻辑结构决定了算法的，而存储结构决定了算法的。2．栈和队列都是一种的线性表，栈的插入和删除只能在进行。3．线性表（a1,a2,…,an）的顺序存储结构中，设每个单元的长度为L，元素ai的存储地址LOC(ai)为4．已知一双向链表如下(指针域名为next和prior)：yxeqp现将p所指的结点插入到x和y结点之间，其操作步骤为：；；；；5．n个结点无向完全图的的边数为，n个结点的生成树的边数为。6．已知一有向无环图如下：BACDFEG任意写出二种拓扑排序序列：、。7．已知二叉树的中序遍历序列为BCA，后序遍历序

5、列为CBA，则该二叉树的先序遍历序列为，层序遍历序列为。三、应用题1．设散列函数H(k)=k%13,设关键字系列为{22,12,24,6,45,7,8,13,21},要求用线性探测法处理冲突。(6分)(1)构造HASH表。(2)分别求查找成功和不成功时的平均查找长度。2．给定表（19,14,22,15,20,21,56,10）.（8分）（1）按元素在表中的次序，建立一棵二叉排序树（2）对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列。第127页共127页（1）画出对(2)中的遍历序列进行折半查找过程的判定树。1．已知二个稀疏矩阵A和B的压缩存储三元组表如下

6、：ABijVijV13-525224633725241342-152-9529558写出A-B压缩存储的三元组表。（5分）2．已知一维数组中的数据为（18,12,25,53,18）,试写出插入排序（升序）过程。并指出具有n个元素的插入排序的时间复杂度是多少？(5分)3．已知一网络的邻接矩阵如下，求从顶点A开始的最小生成树。(8分，要有过程)ABCDEF（1）求从顶点A开始的最小生成树。（2）分别画出以A为起点的DFS生成树和BFS生成树。6．已知数据六个字母及在通信中出现频率如下表：ABCDEF0.150.150.10.10.20.3把这些字母和频率作为叶子结点

7、及权值，完成如下工作(7分，要有过程)。（1）画出对应的Huffman树。（2）计算带权路径长度WPL。（3）求A、B、C、D、E、F的Huffman编码。7．已知有如下的有向网：第127页共127页25364106122AEBDC求顶点A到其它各顶点的最短路径（采用Dijkstra算法，要有过程）。（6分）三、设计题（30分，每题10分,用C语言写出算法，做在答题纸上）1．已知线性表（a1,a2,…,an）以顺序存储结构为存储结构，其类型定义如下：#defineLIST_INIT_SIZE100//顺序表初始分配容量typedefstruct{Elemtype

8、*elem;//顺序存储