数据结构模拟试题-答案

1《数据结构》模拟试题一、单项选择题（30分）1．在数据结构的讨论中把数据结构从逻辑上分为C。A.内部结构与外部结构B.静态结构与动态结构C.线性结构与非线性结构D.紧凑结构与非紧凑结构。2．算法分析的两个主要方面是D。A.正确性和简明性B.可读性和文档性C.数据复杂性和程序复杂性D.空间复杂性和时间复杂性3．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储B。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法4．设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为c。A.5B.6C.7D.95．线性表采用链式存储结构时，要求内存中可用存储单元的地址d。A.必须是连续的B.必须是部分连续的C.一定是不连续的D.连续和不连续都可以6．对具有n个结点的线性表进行插入和删除操作，所需的算法时间复杂度为d。A.O(1)B.O(n)C.O(nlog2n)D.O(n2)7．在单链表中指针p所指结点之后插入指针为s的结点，正确的操作是b。A.p-next=s;s-next=p-next;B.s-next=p-next;p-next=s;C.p-next=s;p-next=s-nextD.p-next=s-next;p-next=s;8．栈中元素的进出原则是b。A．先进先出B．先进后出C．栈空则进D．栈满则出9．长度是n的顺序循环队列，front和rear分别指示队首和队尾，判断队列为满队列的条件是__d____。A．rear=0B．front=0C．rear==frontD．（rear+1）%n==front10．下面说法不正确的是_____c_____。A．广义表的表头总是一个广义表B．广义表的表尾总是一个广义表2C．广义表难以用顺序存储结构D．广义表可以是一个多层次的结构11．已知二叉树的先序遍历序列为ABCD，中序遍历序列为BCDA，则后序遍历序列为____d___。A．ABCDB．BCDAC．CDBAD．DCBA12．已知一棵含50个结点的二叉树中只有一个叶子结点，该二叉树中度为1的结点个数为__d____。A.0B.1C.48D.4913．折半查找有序表（2，5，8，20，25，36，40，60），若查找元素60，需依次与表中元素___a___进行比较。A．20，36，40，60B．25，40C．25，40，60D．20，36，4014．在有向图的邻接表存储表示中，顶点V在链表结点中出现的次数是b。A.顶点V的入度B.顶点V的出度C.顶点V的度D.依附于顶点V的边的数目15．对关键字序列（5，1，4，3，7，2，8，6）进行快速排序时，以第一个元素5为基准的一次划分的结果为c。A．（1，2，3，4，5，6，7，8）B．（1，4，3，2，5，7，8，6）C．（2，1，4，3，5，7，8，6）D．（8，7，6，5，4，3，2，1）二、填空题（20分）1．数据结构包括数据的物理结构、数据的逻辑结构和数据的运算这三个方面的内容。2．一个算法的时间复杂度为(3n3+2n—7)，其数量级表示为O（n3）。3．线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。4．顺序表中逻辑上相邻的元素的物理位置也相邻或一定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。5．栈中允许删除元素的一端称为栈顶；队列中，允许删除元素的一端称为队头。6．广义表(a,b,c,d)的表头是a表尾是(b,c,d)。7．深度为5的满二叉树共有31个结点，其中有16_____个叶子节点。8．用4个权值{9，2，3，6}构造的哈夫曼树的带权路径长度是36。39．在有向图的邻接矩阵中，第i行中非零元素的个数正好是第i个顶点的出度；第i列中非零元素的个数正好是第i个顶点的入度。10．折半查找法中要求线性表必须采用____顺序____存储结构，且表中元素必须___有序_______。11．快速排序在平均情况下的时间复杂度为__O（nlog2n），在最环情况下的时间复杂度为__o(n2)_。三、判断题（对的打，错的打）（10分）（）1.数据元素是数据处理的最小单位。（）2.线性表的顺序存储结构优于链式存储结构。（）3.栈的特点是先进后出,队列的特点是先进先出。（）4.串中任意个字符组成的子序列称为该串的子串。（）5.树型结构中每个结点都有一个直接前趋。（）6.满二叉树中存在度为1的结点。（）7.一棵哈夫曼树有m个叶子结点,则其结点总数为2m-1。（）8.在有向图中每个顶点的度等于该顶点的入度与出度之和。（）9.有向图是一种非线性结构。（）10.折半查找方法适用于按值有序的线性链表的查找。四、简答题（30分）1．对于一个栈，如果输入项序列由A、B、C组成，试给出全部可能的输出序列。（5分）答：根据栈的操作特点是后进先出,因此输出序列有:(1)A入,A出,B入,B出,C入,C出,输出序列为ABC;(2)A入,A出,B入,C入,C出,B出,输出序列为ACB;(3)A入,B入,B出,A出,C入,C出,输出序列为BAC;(4)A入,B入,B出,C入,C出,A出,输出序列为BCA;(5)A入,B入,C入,C出,B出,A出,输出序列为CBA;不可能得到的出序列有:CAB2．将下面的树转换为二叉树，写出转换后二叉树的先序、中序、后序的遍历序列。（5分）转换后二叉树：RABCEFGHIDRADB4先序：RADEBCFGHI中序:DEABGHIFCR后序：EDIHGFCBAR3．对如下有向图，要求：（7分）（1）写出该图中每个顶点的度、出度、入度;顶点1:度为3，出度为1，入度为2顶点2：度为4，出度1，入度3顶点3：度为3，出度为2，入度为1顶点4：度为4，出度为2，入度为2顶点5：度为3，出度为2，入度为1顶点6：度为5，出度为3，入度为2（2）画出该图的邻接表；该图的邻接表如下图所示：（3）根椐邻接表，分别写出从顶点1出发进行深度优先和广度优先搜索得到的顶点序列。深度优先序列：1-2-4-3-6-5广度优先序列：1-2-4-3-6-5ECFGHI54．（5分）从空树起，依次插入关键字（8，12，5，7，9，1，13，10），构造一棵二叉排序树。（1）画出该二叉排序树；（2）画出从（1）所得树中插入关键字为6的结点之后的二叉排序树。（插入后6应该是7的左子树）（3）画出从（2）所得树中删除关键字为12的结点之后的二叉排序树。（首先中序遍历二叉排序树得到一个线性有序序列：（1，5，6，7，8，9，10，12，13），在这个序列中，10就是12的直接前趋，然后用12的直接前趋10代替12，再把12的直接前趋10删除即可）8175129131081791312651065．（8分）已知一组数值序列为(50，47，65，33，41，26，71，56)，请完成下面的各项操作：(1)采用直接插入排序法对该组序列作升序排序，并给出每一趟的排序结果。(2)采用冒泡排序法对该组序列作升序排序，并给出每一趟的排序结果。(3)采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。直接插入排序:47,50,65,33,41,26,71,56这是第一趟的排序结果。要求给出每一趟的排序结果？正确的方法如下：（1）直接插入排序:50，47，65，33，41，26，71，56初始序列：50，47，65，33，41，26，71，56第一趟：47,50,65,33,41,26,71,56第二趟：47,50,65,33,41,26,71,56第三趟：33,47,50,65,41,26,71,56第四趟：33,41,47,50,65,26,71,56第五趟：26,33,41,47,50,65,71,56第六趟：26,33,41,47,50,65,71,56第七趟：26,33,41,47,50,56,65,71下面两种排序按上面的方法完成冒泡排序：50，47，65，33，41，26，71，5681791310657第一趟：47，50，33，41，26，65，56，71第二趟：47，33，41，26，50，56，65，71第三趟：33，41，26，47，50，56，65，71第四趟：33，26，41，47，50，56，65，71第五趟：26，33，41，47，50，56，65，71第六趟：26，33，41，47，50，56，65，71第七趟：26，33，41，47，50，56，65，71快速排序：50，47，65，33，41，26，71，56第一趟：26，47，41，33，50，65，71，56第二趟：26，47，41，33第三趟：33，41，47第四趟：33，41第五趟：56，65，71第六趟：26，33，41，47，50，56，65，71五、算法填空题（10分）1．以下算法的功能是在顺序表中第i个位置上插入一个值为x的新元素。顺序表的类型描述：#defineMAXSIZE20typedefstruct{intdata[MAXSIZE];intlength;}SeqList;算法:intInsert_Seqlist(SeqList*L,inti,intx){intj;if(___L-length=MAXSIZE-1____){printf(“表满!”);return(-1);}if(i1||iL-length+1){printf(“插入位置错!”);return(0);}for(j=L-length；j=i-1；j--)____L-data[j+1]=L-data[j]______;8L-data[i-1]=x;_L-Length++_____;return(1);}2．以下是先序遍历二叉树的递归算法。二叉树的二叉链表的类型定义为：typedefstructNode{chardata;structNode*lchild,*rchild;}BiTreeNode,*BiTree;算法:voidPreOrder(BiTreebt){if(bt==NULL)return;Visit(bt-data);PreOrder(_____bt-lchild__________);PreOrder(______bt-rchild_________);}