资源描述：
《数据结构填空题.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、一、填空题(每空1分,共156分)1.数据结构的存储结构包括顺序、（）、索引和散列等四种。【答案】链接2.设关键字序列{7,12,26,30,47,58,66,70,82,90}，当用折半查找方法查找时，所需比较的次数为3次的关键字分别是（）。【答案】72658823.假定一个线性表为{12,23,74,55,63,40,82,36}，若按key%3条件进行划分，使得同一余数的元素成为一个子表，则包含74的子表长度为（）。【答案】24.和二分查找相比，顺序查找的优点是除了不要求表中数据元素有序之外，对()结构也无特
2、殊要求。【答案】存储5.设双向循环链表每个结点结构为(data,llink,rlink),则结点*p的前驱结点的地址为()。【答案】p->llink6.n个顶点的连通无向图的生成树含有()条边。【答案】n-17.在一个最大堆中，堆顶结点的值是所有结点中的()。【答案】最大值8.假定对长度n=50的有序表进行折半搜索，则对应的判定树中最底下一层的结点数为（）个。【答案】199.对于带头结点的链栈top，取栈顶元素的操作是（）。【答案】*y=top->next->data10.假定一棵三叉树（即度为3的树）的结点个数为
3、50，则它的最小高度为（）。假定树根结点的深度为0。【答案】411.二维数组是一种非线性结构，其中的每一个数组元素最多有()个直接前驱（或直接后继）。【答案】两个12.在堆排序中，对任意一个分支结点进行调整运算的时间复杂度为()。【答案】O(log2n)13.队列的删除操作在（）进行。【答案】队头（或队首）14.设图G=(V,E)，V={1,2,3,4},E={<1,2>,<1,3>,<2,4>,<3,4>}，从顶点1出发，对图G进行广度优先搜索的序列有()种。【答案】215.向一棵二叉搜索树中插入一个元素时，若元
4、素的值小于根结点的值，则应把它插入到根结点的（）上。【答案】左子树16.快速排序在平均情况下的时间复杂度为()。【答案】O(nlog2n)17.由关键字序列{42,97,75,23,68,34}建成的最大堆是()。【答案】97，68，75，23，42，3418.对于关键字序列（１２,１３,１１,１８,６０,１５,７,１８,２５,１００），用筛选法建堆，必须从关键字为（）的结点开始。【答案】6019.从有序表(12,18,30,43,56,78,82,95)中折半搜索元素56时，其搜索长度为（）。【答案】3万维试题库
5、系统第8页20.设有二叉树根结点的层次为０，一棵高度为h的满二叉树中的叶子结点个数是（）。【答案】2h21.在一个最小堆中，堆顶结点的值是所有结点中的()。【答案】最小值22.在长度为n的顺序表中删除一个元素时,等概率情况下的平均移动元素的次数是（）。【答案】(n-1)/223.由关键字序列（57,24,76,63,18,31,15）生成的一棵二叉排序树，其等查找概率情况下查找成功的平均查找长度为（）。【答案】18/724.数据结构包括逻辑结构、（）和数据的运算三个方面。【答案】存储结构25.在一棵m阶B树上，每个
6、非根结点的关键码数最多为()个。【答案】m-126.在双向链表中,每个结点除了数据域外,还有两个指针域,它们分别指向()。【答案】前趋结点和后继结点27.一般来说,深度优先生成树的高度比广度优先生成树的高度要()。【答案】高28.递归工作栈起到两个作用，其一是将递归调用时的实际参数和返回地址传递给下一层递归；其二是保存本层的形式参数和（）。【答案】局部变量29.在一个堆的顺序存储中，若一个元素的下标为i(0≤i≤n-1)，则它的右子女元素的下标为（）。【答案】2i+230.数据结构的逻辑结构包括线性结构和（）结构两
7、大类。【答案】非线性31.队列是具有()特性的线性表。【答案】先进先出32.基本数据类型是计算机已经实现了的（）。【答案】数据结构33.n个顶点且含有环路的无向连通图中，至少含有()条边。【答案】n34.若设L是指向带表头的单链表,语句L->link=L->link->link的作用是()单链表中的第一个结点。【答案】删除35.已知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为（）。【答案】236.大小为M的顺序存储的循环队列sq
8、队满的条件为（）。【答案】(sq.rear+1)%M==sq.front37.若设顺序栈的最大容量为MaxSize，top==-1表示栈空，则判断栈满的条件是（）。【答案】top==MaxSize-138.假定一个顺序表的长度为40，并假定顺序搜索每个元素的概率都相同，则在搜索成功情况下的平均搜索长度为（）。【答案】20.539.在程序运行过程中不能扩充的数
