资源描述：
《《数据结构》(本)模拟试题一》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、《数据结构》（本）模拟试题一一、填空题（每小题2分，共24分）1.一棵二叉树没有单分支结点，有6个叶结点，则该树总共有个结点。2.栈和队列的操作特点分別是和o3.设一棵完全二叉树，其最高层上最右边的叶结点的编号为奇数，该叶节点的双亲结点的编号为10,该完全二义树一共有个结点。4.结构中的数据元素存在多对多的关系称为结构。5.按照二叉树的递归定义，对二叉树遍历的常用算法冇、、三种。6.根据数据元素间关系的不同特性，通常可分为集合、线性、、四类基本结构。7.数据结构屮的数据元素存在一对多的关系称为结构。8.要求在n个数据元
2、素中找其中值最大的元索，设基木操作为元素间的比较。则比较的次数和算法的时间复杂度分别为和。9.把数据存储到计算机中，并具体体现数据之间的逻辑结构称为结构。10.在一个单向链表中p所指结点Z后插入一个s所指向的结点时，应执行—和p->next=s;的操作。11.结构中的数据元素存在一对一的关系称为结构。12.在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是值域、二、单项选择题（每小题2分，共30分）1・针对线性表，在存储示如果最常用的操作是取第i个结点及其前驱，则采用（）存储方式最节省时间。A.单链表B.双链表
3、C.单循环链表D.顺序表2.数据结构中，与所使用的计算机无关的是数据的（）结构。A.物理B.存储C.逻辑与物理D.逻辑3.以下特征中，（）不是算法的特性。A.冇穷性B.确定性C.可行性D.冇0个或多个输出4.设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），则移动元素个数为（）oA.rri+lB.n-iC.n-iTD.i5.栈的插入删除操作在（）进行。A.栈底B.任意位置C.指定位置D.栈顶6.以下说法正确的是（）oA•栈的特点是先进先出，队列的特点是先进后出B.栈和队列的特点都是先进
4、后出C-栈的特点是先进后出，队列的特点是先进先出D.栈和队列的特点都是先进先出7.元素2,4,6,8按顺序依次进栈，则该栈的不可能输岀序列是（）（进栈出栈可以交替进行）。A.8,6,4,2B.2,4,6,8C.4,2,8,6D.8,6,2,42.设有一个15阶的对称矩阵A,采川压缩存储的方式，将具下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素缶.6在一维数组B中的下标是（）0A.42B.13C.279.串函数StrCmp（“d”，“D”）的值为（）。A-0B-1C.-1D・32D.310.在
5、一棵二叉树屮，若编号为i的结点存在右孩子，则右孩子的顺序编号为（）o得到的一种顶点序列为（A.abcedf)oB.abcefdC.aebcfdD.acfdeb:d:——•fZ树共有（）个指针域为空。A.2iB.2i-lC.2i+2D.2i+l11.设一棵有n个结点采用链式存储的二叉树，除叶结点外每个结点度数都为2,则该A.2nB.2n+lC.2n+2D.n+112.已知如图1所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能13.在有序表｛1,3,8,13,33,42,46,63,76,78,86,97
6、,100｝中,用折半查找值86时，经（）次比较后查找成功。A.6B.3C.8D.414.有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。A.29/10B.31/10C.26/10D.29/915.一组记录的关键字序列为（37,70,47,29,31,85）,利用快速排序，以第一个关键字为分割元索，经过一次划分后结果为（）。A.31,29,37,47,70,85B.29,31,37,47,70,85C.31,29,37,70,47,85D.31,29,37,85,47,70
7、三、综合题1.（1）利用筛选过程把序列｛42,82,67,102,16,32,57,52｝建成堆（小根堆）,画出该堆（不要求中间过程）。（2）写出对上述堆对应的完全二叉树进行屮序遍历得到的序列。2.（1）以2,3,4,7,8,9作为叶结点的权，构造一棵哈夫曼树（要求每个结点的左子树根结点的权小于等于右了树根结点的权)，给出相应权重值叶结点的哈夫曼编码。(2)一棵哈夫曼树侑n个叶结点，它一共有多少个结点？简述理由？3.设查找表为(16,15,20,53,64,7),⑴用冒泡法对该表进行排序(要求升序排列)，要求写出每一趟
8、的排序过程。(2)在排序后的冇序表的基础上，価出对其进行折半查找所对应的判定树.(要求以数据元索作为树结点)(3)求在等概率条件下,对上述冇序表成功查找的平均查找长度.四、程序填空题(每空2分，共16分)1.以下冒泡法程序对存放在a[l],a[2],……,a[n]中的序列进行排序，完成程序中的空格部分，其中n是元素个数，要求按升序
