资源描述：
《西南民族大学数据结构考试模拟卷答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、题号—'二三四五六七八九十总分得分请判断下列说法的是否正确：（10分）（1）若某堆栈的输入序列为1，2,3,4,则4,3，1，2不可能是堆栈的输出序列之一。（）（2）队列逻辑上是一个表头和表尾既能插入又能删除的线性表。（）（3）若一个叶子结点是某子树的中序遍历序列的最后一个结点，则它必是该子树的先序遍历中的最后一个结点。（）（4）在索引顺序表上实现分块查找，在等概率查找情况下，其查找长度只与表中元素个数有关,而与每块中元素个数无关。（）（5）二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值，小于其右孩子的值。（）（6
2、）在10万个随机排列的数据中，要选出5个最小的数，采用快速排序比采用Shell排序、堆排序及各种直接排序法都快。（）（7）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中的结点的个数有关，而与图的边数无关。（）o-（8）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。（（9）二分査找法不仅适用于顺序存储的有序表，而且适合于链接表。（（10）按中序遍历一棵二叉排序树所得到的遍历序列是一个递增序列。（二、填空（20分）（1）数据结构有如下四种基本结构:（2）在一个算法中的语句频度之和为T（n）=37
3、20n+4nlogn,则算法的时间复杂度为o（3）己知某二叉树的叶子结点的个数为10个，度为1的结点个数为8个，则该二叉树的结点总数为，个。(4)己知一个有序表为(13,18,24,35,47,50,62,83,90,115,134),当二分检索值为90的元素时，需次比较可检索成功。（5）、图的遍历方法主要有两个，一个是，另一个是（6）在哈希造表过程中，处理冲突的方法主要有：（7）在一个单链表中p所指结点（p所指不是最后结点）之后插入一个由指针s所指结点，应执行!§->next=;和p->next=的操作◊（8）.己知一棵二叉树的先序
4、序列为ABCD,中序序列为BCAD,则它的后序序列为。（9）有N个顶点组成的无向连通图，最多可以条边。（10）、若某序列的初始状态为{49,13,42,8,65,55,79},若以49为枢轴，则经过一趟快速排序之后的序列为：O三、单项选择题（每小题2分，共20分））个元1.从一个长度为n的顺序表中删除第i个元素ClSiSn）时，需向前移动（素。A）.n-iB）.n-i+1C）.n-i-1D）.i2）、队列操作的原则是：（）A）先进先出B）后进先出C）只能进行插入D）只能进行删除3）下列算法中，（）算法用来求图中每对顶点之间的最短路径。
5、A).DijkstraB).FloyedC).PrimD).Kruskal4、下面关于线性表的叙述中，错误的是（）A）线性表采用顺序存储，必顺占用一片连续的存储单元。B）线性表采用顺序存储，便于进行插入和删除操作。C）线性表采用链接存储，不必占用一片连续的存储单元D）线性表采用链接存储，便于插入和删除操作。5、对下面的有向图进行拓扑排序，其排序结果不正确的是：（）。A)1、4、2、6、5、3B)1、2、4、6、3、5C)1、4、2、5、6、36、带头结点的单链表head为空的判定条件是：()A).head==NULLB.)head->
6、next==NULLB)、.head->next==headD).head!=NULL7、在所有排序方法中，关键字的比较次数与记录的初始排列无关的是。A)Shell排序B)冒泡排序C.)直接插入排序D)直接选择排序8、设有两个串p和q,求q在p中首次出现的位置的运算叫。A).模式匹配B).求子串C.)定位D).查找9、将长度为n的单链表链接到长度为m的单链表之后的算法的时间复杂度为()A.)O(m)B.)0(1)C.)O(n)D).O(m+n)10、用线性探测法査找散列表，可能要探测多个散列地址，这些位置上的关键值()A.)一定都是同
7、义词B).一定都不是同义词C).都相同D)不一定都是同义词四、解答题(30分)1、对于给定的一组权值w={3,6,9,11,13,15,17,19}}画出Huffman树(要求结点左小右大)，并给出每个结点的Huffman编码，计算该树的WPL。(6分)2、考虑下图：（10分）1）从顶点A出发，求它的深度优先生成树。2）从顶点E出发，求它的广度优先生成树。3）根据普里姆（Prim）算法，求它的最小生成树。（从顶点A出发，要求给出计算过程）3、己知待散列的线性表为（36,15,40,63,22）,散列用的一维地址空间为[0..6],假定
8、选用的散列函数是H（K）=K%7,若发生冲突采用线性探查法处理，试：（1）计算出每一个元素的散列地址并在下图中填写出散列表；<2）求出在查找每一个元素概率相等情况下的平均查找长度。（6分）01234564、对关键字序列（
