计算机考研数据结构试卷十一(练习题含答案).docx

共25套适用于计算机考研数据结构系统练习（PS：其他正在整理，敬请期待）数据结构试卷11一、填空:设需要对5个不同的记录关键字进行排序，则至少需要比较_____________次，至多需要比较_____________次。设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较_________次。设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有_________个，比较两次查找成功有结点数有_________个。数据结构从逻辑上划分为三种基本类型：___________、__________和___________。在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。在快速排序、堆排序、归并排序中，_________排序是稳定的。在有n个叶子结点的哈夫曼树中，总结点数是_______。一棵树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定_______。二、选择题：队列的特点是【 】。A 先进后出B 先进先出C 任意位置进出D 前面都不正确有n个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行【 】遍分配与收集。A nB dC rD n - d 在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序【 】。A 都不相同B 完全相同C 先序和中序相同，而与后序不同D 中序和后序相同，而与先序不同设有198个初始归并段，如采用K-路平衡归并三遍完成排序，则K值最大为【 】。A 12B 13C 14D 15下面关于广义表的叙述中，不正确的是【 】。A 广义表可以是一个多层次的结构B 广义表至少有一个元素C 广义表可以被其他广义表所共享D 广义表可以是一个递归表设二叉树根结点的层次为0，一棵深度（高度）为k的满二叉树和同样深度完全二叉树各有f个结点和c个结点，下列关系式不正确的是【 】。A f=cB cfC f=2k+1-aD csk-1从L=((apple,pear),(orange,banana))中，取出banana元素的表达式为【 】。A head(tail(L))B head(head(tail(L)))C tail(head(tail(L)))D head(tail(head(tail(L))))下列文件的物理结构中，不利于文件长度动态增长的文件物理结构是【 】。A 顺序结构B 链接结构 C 索引结构D Hash结构在数据结构中，数据元素可由【 】。A 实体B 域C 数据项D 字段对于有n个顶点的有向图，由弗洛伊德（FloyD 算法求每一对顶之间的最短路径的时间复杂度是【 】。A O(1)B O(n)C O(n)D O(n3)计算与算法应用题：已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。先序序列： B F ICEH G中序序列：D KFIA EJC 后序序列： K FBHJ G A四、阅读下列算法，分析它的作用：int AA(LNode *HL , ElemType x){ int n=0; LNode *p=HL;while (p!=NULL){ if (p-data= =x) n++; p=p-next;}return n;}对于结点类型为LNode的单链表，以上算法的功能为：int AA(LNode *HL , ElemType x){ int n=0; LNode *p=HL;while (p!=NULL){ if (p-data= =x) n++; p=p-next;}return n;}对于结点类型为LNode的单链表，以上算法的功能为：算法设计题：编写复制一棵二叉树的非递归算法。假设二叉树中每个结点所含数据元素均为单字母，以二叉链表为存储结构，试编写算法按如下图所示的树状显示二叉树。评卷人得分答案（PS:后15套较难，有不会的可以@我）一、填空题4，10n1，2线性结构，树型结构，图型结构n(n-1)/