《数据结构与算法》模拟试卷一

【第1页共3页】《数据结构与算法》模拟试卷一一、填空题（每空2分，共20分）1.在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为______。2.如果入栈序列是1，3，5，…，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为______。3.根据数据元素之间关系的不同特性，通常有下列四类基本结构：集合、_____、树状结构、______。4.线性表的链式存储方式中，每个结点包括两个域，分别是：_____和_____。5.一棵高度为5的二叉树中最少含有_____个结点，最多含有_____个结点；6.在对一组记录(54，38，96，72，60，15，60，45，83)进行直接插入排序时，当把第5个记录60插入到有序表时，为寻找插入位置需比较________次。7.有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的__出度______。二、选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。每小题2分，共10分。）1.对线性表进行折半查找最方便的存储结构是_____。A.顺序表B.有序的顺序表C.链表D.有序的链表2.计算递归函数如不用递归过程通常借助的数据结构是_____。A.线性表B.双向队列C.树D.栈3.如果T2是由有序树T转换来的二叉树，则T中结点的后序排列是T2结点的_____。A.先序排列B.中序排列C.后序排列D.层序排列4.n个结点的线索二叉树中线索的数目为_____。A.(n-1)个B.n个C.（n+1）个D.(n+2)个5.设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是_____。A.(rear-front)%m==1B.front==rearC.(rear-front)%m==m-1D.front==(rear+1)%m6.假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在_____。A.BT[i/2]B.BT[2*i-1]C.BT[2*i]D.BT[2*i+1]7.连通图是指图中任意两个顶点之间_____。A.都连通的无向图B.都不连通的无向图C.都连通的有向图D.都不连通的有向图8.在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为_____。A.nB.n/2C.(n+1)/2D.(n-1)/29.若一个栈的输入序列是1，2，3，4，…，n，输出序列的第一个元素是n，则第i个输出元素是_____。【第2页共3页】A.不确定B.n-iC.n-i+1D.n-i-110.在单链表中插入一个结点，要修改____个结点的指针域。A.1B.2C.3D.4三、简答题（要求写出主要操作步骤及结果。每小题5分,共35分）1.若进栈元素依次为A、B、C、D，写出至少5种可能的出栈顺序。2.已知一棵二叉树先序遍历顺序为ABDEGHJCFI，中序为DBGEHJACIF，试构造该二叉树。3.假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.08,0.18,0.02,0.06,0.35,0.10,0.16,0.05。试为这8个字母设计哈夫曼编码。并计算其平均编码长度（即WPL）。4.将下面森林转换为相应的二叉树。5.给出下图所示的无向图G的邻接矩阵和邻接表两种存储结构。V1V3V4V2V56.使用普里姆算法构造如下图所示的图G的一棵最小生成树。（画出构造过程）V1V4V5V3V2V66551536642ABCDEFGHIJKLMN【第3页共3页】7.对数据元素序列15，13，12，8，22，37，4，33，8，6进行降序排序，用筛选法构造堆排序的初始小顶堆，画出堆形。四、证明题（要求写出证明过程。共8分）一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2，则n0=n2+1,试证明之。五、算法设计题（共17分，第1题8分，第2题9分）1.写出折半查找算法。2.给出二叉树的二叉链表存储结构，并写一算法求二叉树的深度。