数据结构模拟试题-答案

1、数据结构模拟试题、单项选择题（30分）1.在数据结构的讨论中把数据结构从逻辑上分为A. 内部结构与外部结构B. 静态结构与动态结构C. 线性结构与非线性结构D. 紧凑结构与非紧凑结构。2.算法分析的两个主要方面是3.A.正确性和简明性C.数据复杂性和程序复杂性B.D.在存储数据时，通常不仅要存储各数据元素的值,A.数据的处理方法B.可读性和文档性空间复杂性和时间复杂性而且还要存储数据元素的类型C.数据元素之间的关系D.数据的存储方法4.A.5B.6C.7D.95.线性表采用链式存储结构时,要求内存中可用存储单元的地址A.必须是连续的B.必须是部分连续的C. 一定是不连续的D.连续和不连续都可以

2、设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为6.A. 0(1)B. O( n)C. O(n log2n)D. O(n2)7.在单链表中指针 p所指结点之后插入指针为s的结点，正确的操作是A. p-n ext=s;s-n ext= p-n ext;B. s-n ext= p-n ext; p-n ext=s;C. p-n ext=s; p-next = s-nextD. p-n ext=s-n ext; p-n ext=s;8.栈中元素的进出原则是A.先进先出 B.先进后出C.栈空则进D .栈满则出9长度是n的顺序循环队列，front和rear分别指示队首和队尾，判断队列

3、为满队列的条件是_d。.front=0A . rear=0C. rear=front(rear+1 ) %n=front10 .下面说法不正确的是 c。A.广义表的表头总是一个广义表B .广义表的表尾总是一个广义表C .广义表难以用顺序存储结构D .广义表可以是一个多层次的结构11.已知二叉树的先序遍历序列为ABCD中序遍历序列为 BCDA则后序遍历序列为dA. ABCDB . BCDAC. CDBAD. DCBA1的结点个数为d。A. 0 B. 1C. 48D. 4913.折半查找有序表（2,5,20, 25,36, 40, 60),若查找元素 60,需依次与表中元素12 .已知一棵含50个

4、结点的二叉树中只有一个叶子结点，该二叉树中度为进行比较。A. 20, 36, 40,60.25, 40C. 25, 40, 60.20, 36, 4014.在有向图的邻接表存储表示中,顶点V在链表结点中出现的次数是A.顶点V的入度B.顶点V的出度C.顶点V的度D.依附于顶点 V的边的数目15.对关键字序列（5,8, 6）进行快速排序时,以第一个元素5为基准的一次划分的结果为A. (1, 2, 3, 4,5,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.数据结

5、构包括数据的物理结构、数据的逻辑结构和数据的运算这形结构中元素之间存在 多对多关系。三个方面的内容。332. 一个算法的时间复杂度为 （3n 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图+2n 7），其数量级表示为 0（n ） 。4.顺序表中逻辑上相邻的元素的物理位置 也相邻或一定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。5. 栈中允许删除元素的一端称为_栈顶_;队列中，允许删除元素的一端称为_队头_。6. 广义表(a,b,c,d)的表头是a 表尾是(b,c,d) 。7. 深度为5的满二叉树共有31 个结点，其中有 16_ 个叶子节点。&用4个权值9, 2,

6、 3, 6构造的哈夫曼树的带权路径长度是 36 。9. 在有向图的邻接矩阵中，第i行中非零元素的个数正好是第i个顶点的 _出度;第i列中非零元素的个数正好是第i个顶点的 入度。10. 折半查找法中要求线性表必须采用 顺序存储结构，且表中元素必须 有序。11. 快速排序在平均情况下的时间复杂度为_0 (nlog 2n),在最环情况下的时间复杂度为_o(n2) _。三、判断题(对的打，错的打 )(10分)()1.数据元素是数据处理的最小单位。()2.线性表的顺序存储结构优于链式存储结构。()3.栈的特点是先进后出，队列的特点是先进先出。()4.串中任意个字符组成的子序列称为该串的子串。()5.树型

7、结构中每个结点都有一个直接前趋。()6.满二叉树中存在度为1的结点。()7. 一棵哈夫曼树有 m个叶子结点，则其结点总数为2m-1。()8.在有向图中每个顶点的度等于该顶点的入度与出度之和。()9.有向图是一种非线性结构。()10.折半查找方法适用于按值有序的线性链表的查找。四、简答题(30分)1.对于一个栈，如果输入项序列由A、B、C组成，试给出全部可能的输出序列。(5分)答：根据栈的操作特点是后进先出，因此输出序列有：输出序列为出，B出，C出,入，A入，B入,CABC;A入，C输出序列为ACB;输出序列为BAC;输出序列为BCA;输出序列为出，B出，A出,入, B入, C入，CCBA;A5

8、分）3 对如下有向图，要求:（7 分）(1)写出该图中每个顶点的度、出度、入度顶点1：度为3，出度为1,入度为顶点2:度为4,出度1，入度3顶点3:度为3,出度为2,入度为顶点4:度为4,出度为2,入度为顶点5:度为出度为2,入度为3,1顶点6:度为5,出度为3,入度为2(2)画出该图的邻接表；该图的邻接表如下图所示：(3)根据邻接表，分别写出从顶点1出发进行深度优先和广度优先搜索得到的顶点序列。深度优先序列：1-2-4-3-6-5广度优先序列：1-2-4-3-6-54. ( 5分)从空树起，依次插入关键字( 构造一棵二叉排序树。(1) 画出该二叉排序树；8, 12, 5, 7, 9, 1,

9、13, 10),81251913710(2) 画出从(1)所得树中插入关键字为6的结点之后的二叉排序树。(插入后6应该是7的左子树)813512197610（3）画出从（2）所得树中删除关键字为 12的结点之后的二叉排序树。（首先中序遍历二叉排序树得到一个线性有序序列：（1，5，6，7，8，9，10，12,中，10就是12的直接前趋，然后用12的直接前趋10代替12，再把12的直接前趋13），在这个序列10删除即可）571381095. ( 8分)已知一组数值序列为(50, 47, 65, 33, 41, 26, 71, 56)，请完成下面的各项操作:(1) 采用直接插入排序法对该组序列作升序

10、排序，并给出每一趟的排序结果。(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

11、,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, 56第趟：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第八

12、趟：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 U, 41第五趟：56, 65 71第六趟：26 , 33, 41, 47, 50, 56, 65, 71五、算法填空题(10分)1 以下算法的功能是在顺序表中第i个位置上插入一个值为x的新元素。顺序表的类型描述：#define MAXSIZE 20typedef stru

13、ct int dataMAXSIZE;int len gth ;SeqList;算法：int Insert_Seqlist(SeqList *L,int i,int x)int j;if (_L-length=MAXSIZE-1 ) printf(表满！ ” ); return (-1); if ( iL- length +1) printf(插入位置错！ ”)； return (0); for (j= L-length； j=i-1 ； j-) L-datai+11=L-datail;L-datai-1=x;L-Length+;return (1);2 以下是先序遍历二叉树的递归算法。二叉树

14、的二叉链表的类型定义为：typedef struct Node char data;struct Node *lchild,*rchild; BiTreeNode, *BiTree;算法：void PreOrder (BiTree bt) if ( bt=NULL ) return ;Visit(bt-data);PreOrder ( bt-lchild);PreOrder ( bt-rchild);Whe n you are old and grey and full of sleep,And no ddi ng by the fire, take dow n this book,And s

15、lowly read, and dream of the soft lookYour eyes had on ce, and of their shadows deep;How many loved your mome nts of glad grace,And loved your beauty with love false or true,But one man loved the pilgrim soul in you.And loved the sorrows of your cha nging face;And bending dow n beside the glow ing b

16、ars,Murmur, a little sadly, how love fledAnd paced upon the mountains overheadAnd hid his face amid a crowd of stars.The furthest dista nee in the worldIs not betwee n life and deathBut whe n I sta nd in front of youYet you dont know thatI love you.The furthest dista nee in the worldIs not whe n I sta nd in front of youYet you cant see my loveBut whe n un doubtedly knowing the love from bothYet cannot be together.The furthest dista nee in the worldIs not being apart while being in loveBut whe n I pla inly cannot