资源描述：
《数据结构试题2009秋本科a》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、试题：班号：姓名：一．填空题（共20分，每空1分）1．设单链表的结点结构为（data,next），next为指针域。已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y插入结点x之后，则需执行一下语句：（；）（）。2．设无向图G的顶点数为n，图G最少有（）边；最多有（）边。若G为有向图，有n个顶点，则图G最少有（）边；最多有（）边。3．设有一空栈，现有输入序列1，2，3，4，5，经过push，push，pop，push，pop，push，push后，输出序列是（）。4．由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为（）5．
2、由a，b，c三个结点构成的二叉树，共有（）种不同的结构。6．在线性表的散列存储中，处理冲突有（）和（）方法。7．在对一组记录（50，40，95，20，15，70，60，45，80）进行冒泡排序时，第一趟需进行相邻记录的交换的次数为（），在整个排序过程中共需进行（）趟就可以将排序完成。8．数据结构是研究数据的（）和（ ）以及它们之间的相互关系。9.散列法要解决的两个关键问题是（）和（）。10.外部排序需要考虑的三个关键问题分别是（）、（）和（）。二．判断题（对的填√，错的填×，共10分，每题1分）1．在线性结构中，每个结点都有一个直接前驱和一个直接后继。（）第8页（共8页）
3、试题：班号：姓名：2．在链式存储的栈的头部必须要设头结点。（）3．在二叉树中插入结点，则该项二叉树便不再是二叉树。（）4．由二叉树结点的先序序列和后序序列可以唯一确定一棵二叉树。（）5．树的父链表示就是用数组表示树的存储结构。（）6．任何二叉树都唯一对应一个森林，反之亦然。（）7．顺序存储方式只能用于存储线性结构。()8．用循环链表作为存储结构的队列就是循环队列。()9．算法分析的目的是分析算法的易读性（）。10．一组记录的关键字为（46,79,56,38,40,84）,则利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为40,38,46,56,79,84（）。三．选择题（
4、共10分，每题1分）1．快速分类在___________的情况下不利于发挥其长处。A.待分类的数据量太大B.待分类的数据相同值过多C.待分类的数据已基本有序D.待分类的数据值差过大.2．已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多为。A．39B．52C．111D．1193．设森林中有三棵树，第一、第二和第三棵树中的结点个数分别为m1、m2和m3。那么在由该森林转化成二叉树中根结点的右子树上的结点个数是。A．m1+m2B．m2+m3C．m3+m1D．m1+m2+m34．设结点x和y是二叉树中任意的两个结点。在该二叉树的前序遍历序列中x在y之前，而在
5、其后序遍历序列中x在y之后，则x和y的关系是。A．x是y的左兄弟B．x是y的右兄弟C．x是y的祖先D．x是y的后裔5．采用邻接表存储的图的广度优先遍历类似于二叉树的A．先序遍历B．中序遍历C．后序遍历D．层次遍历6第8页（共8页）试题：班号：姓名：．使用DFS算法递归地遍历一个无环有向图，并在退出递归时输出相应顶点，这样得到的顶点序列是。A．逆拓扑有序B．拓扑有序C．无序的D．都不是7．散列函数有共同的性质，即函数值应当以概率取其值域的每一个值。A．最大B．最小C．平均D．同等8．对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8。查找后面5个元素的概率相同，均为3
6、/40，则查找到表中任一元素的平均查找长度为。A．5.5B．5C．39/8D．4/39．若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序方法只能是。A．起泡排序B．插入排序C．选择排序D．二路归并排序10．堆是一种有用的数据结构，例如排序码序列就是一个堆。A．16，72，31，23，94，53B．94，53，31，72，16，23C．16，53，23，94，31，72D．16，31，23，94，53，72四、简答题（共20分，每题5分）1．什么是线性表？线性表的两种存储结构(顺序存储结构和链接存储结构)各有哪些优缺点?2．
7、输入{23,25,28,10,9,16,12,18,13,20}，给出构造平衡二叉树的过程。第8页（共8页）试题：班号：姓名：3．已知下图所示的无向图，试画出（1）以D为搜索起点的先深生成树；（2）以D为搜索起点的先广生成树。GEBDACHF4．有一份电文中共使用五个字符:a，b，c，d，e，它们的出现频率依次为8，14，10，4，18，请构造出相应的哈夫曼(Huffman)树(约定左子树根结点的权小于等于右子树根结点的权),求出每个字符的哈夫
