数据结构习题(无答案)

《数据结构习题(无答案)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、试卷一一、简答题：（每小题3分，共15分）1.什么情况下二叉排序树的查找性能较好？什么情况下二叉排序树的查找性能最差？2.比较顺序表与单链表的优缺点。3•请写出栈的链式存储结构的类型定义。4.在起泡排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，试举例说明之。5.简述参数传递的主要方式及其特点。二、判断正误：（每小题1分，共5分）正确在（）内打"，否则打x。（）（I）在拓朴序列中，如果结点Vi排在结点Vj的前面，则一定存在从Vi到Vj的路径。（）（2）在采用线性探测法处理冲突的散列

2、表中，所有同义词在表中一定相邻。（3）在一个小根堆中，具有最大值的元素一定是叶结点。（）（4）索引顺序表的特点是块间可无序，但块内一定要有序。（）（5）哈夫曼树中没有度为1的结点，所以必为满二叉树。三、单项选择题：（每小题1分，共5分）1.对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为：A）顺序表B）用头指针表示的单循环链表C）用尾指针表示的单循环链表D）单链表2.假设以第一个元素为分界元素，对字符序列（Q,H,C，Y,P,A,M,S,R,D,F,X）进行快速排序，则第一次划分的结果是：A

3、)(A,C,D,F,H,M,P,Q,R,S,X,Y)X)C)(F,H,C,D,P,A,M,Q,R,S,Y，X)X)3.下面是二个关于有向图运算的叙述：B)(A,F,H,C,D,P,M,Q,R,S,Y,D)(P,A,M,F,H,C,D,Q,S,Y,R,（1）求有向图结点的拓扑序列，其结果必定是唯一的（2）求两个指向结点间的最短路径，其结果必定是唯一的（3）求AOE网的关键路径，其结果必定是唯一的其中哪个（些）是正确的？A）只有（1）B）（1）和（2）C）都正确D）都不正确4.若进栈序列为a,b,c,则通

4、过入出栈操作可能得到的a,b，c的不同排列个数为：A）4B）5C）6D）75.以下关于广义表的叙述中，正确的是：A）广义表是由0个或多个单元素或子表构成的有限序列B）广义表至少有一个元素是子表C）广义表不能递归定义D）广义表不能为空表Ui填空题:（每小题2分，共20分）1.一棵含有101个结点的完全二叉树存储在数组AE1..101］中，对l

5、ring(subl,s,1,8):SubString(sub2,s,20,5);StrCat(subl,sub2);则最后subl的值为:3.若个算法中的语句频度之和为T(n)二3720n+4nlogn,则算法的时间复杂度为o4.广义表((((a),b),c),d)的表头是,表尾5.是O已知有向图的邻接矩阵，要计算i号结点的入度，计算方法是:将累力口。6・要在一个单链表中p所聶结点之后插入一个子链表，子链表第一个结点的地址为s,子链表最后一个结点的地址为t,则应执行操作:和O7.用带头结点的循环链表表

6、示的队列，若只设尾指针rear,则队空的条件是O8.已知二维数组A[10][20]采用行序为主方式存储，每个元素占2个存储单元，并且A[0][0]的存储地址是1024,则A[6][18]的地址是9.在表示二叉树的二叉链表中，共有个空链域。10・n个顶点的连通无向图至少有条边，至多有条边o五、构造题：(每小题6分，共30分)1・已知二叉树的中序序列为DBGEAFC,后序序列为DGEBFCA,给出对应的二叉树。2.已知一个图的顶点为A、B、C、D,其邻接矩阵的上三角元素全为0（包括主对角线元素），其他元素

7、均为1。请画出该图，并给出其邻接表。3・给定权值{8,12,4,5,26,16,9},构造一棵带权路径长度最短的二叉树，并计算其带权路径长度。4.图2表示一个地区的通讯网，边表示城市间的通讯线路，边上的权值表示架设线路花费的代价，请找出能连通每个城市、且总代价最省的n・l条线路。5.对关键字序列（72,87,61,23,94,16,05,58）进行堆排序,使之按关键字递减次序排列。请写出排序过程中得到的初始堆和一趟排序后的序列状态。六、算法设计题：（共25分）1.设有一个由正整数组成的单链表L（含头结

8、点），编写完成下列功能的算法：找出最小值结点P,若最小值是奇数，则删除结点P。［15分］2.已知树用孩子兄弟链表存储，root指向根结点。编写算法，逐层遍历这棵树。［10分］《数据结构》试卷参考答案与评分标准（2000级）一、简答问题：（每小题4分，共16分）1.集合结构、线性结构、树形结构、网状结构2.线性结构的前驱与后继之间为一对一关系，非线性结构的前驱与后继之间通常为一对多或多对多关系。3.解决特定问题的有限指令序列。有限性、确定性、可行性、有0个