数据结构模拟试卷和答案

1、北京语言大学网络教育学院数据结构模拟试卷一注意：1 .试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。2 .请各位考生注意考试纪律，考试作弊全部成绩以零分计算。3 .本试卷满分100分，答题时间为 90分钟。4 .本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。一、【单项选择题】（本大题共10小题，每小题2分，共20分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。1、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则采用（）存储方式最节省时间。A顺序表B双链表C带头结

2、点的双循环链表D单循环链表2、队列操作的原则是（）。A只能进行删除B后进先出C只能进行插入D先进先出3、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A空或只有一个结点B高度等于其结点数C任一结点无左孩子D任一结点无右孩子4、在下列排序方法中，（）方法平均时间复杂度为 0（nlogn）,最坏情况下时间复杂度为0（n2）。A插入排序B希尔排序C快速排序D堆排序5、对二叉树从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一个结点的左、右孩子中，其左孩子编号小于右孩子编号。则可采用（）次序的遍历实现编号。A先序B中序C后序D从根开始的层次遍历6、若用数组Sn作

3、为两个栈S1和S2的共用存储结构，对任何一个栈，只有当Sn全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。A S1的栈底位置为0, S2的栈底位置为nB S1的栈底位置为1, S2的栈底位置为n/2C S1的栈底位置为0, S2的栈底位置为n-1D S1的栈底位置为0, S2的栈底位置为n/27、对一棵二叉排序树进行（）遍历，可以得到该二叉树的所有结点按值从小到大排列的序列。 A 前序 B 后序 C 中序 D 按层次8、在下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。 A 堆排序 B 冒泡排序 C 快速排序 D 插入排序9、采用邻接表

4、存储的图的广度优先算法类似于二叉树的（） 。 A 先序遍历 B 中序遍历 C 后序遍历 D 层次遍历10 、具有 6 个顶点的无向图至少应有（）条边才能保证图的连通性。A 4B 5C 6D 7二、【判断题】（本大题共10小题，每小题2分，共20分）正确的填T,错误的填F,填 在 答题卷相应题号处。11 、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。（）12 、任何二叉树都唯一对应一个森林，反之亦然。（）13 、有向图的邻接矩阵一定是对称的。（）14 、线性表的链式存储结构优于顺序存储结构。（）15 、关键路径可能不只一条，但缩短某一关键路径一定能够缩短工期。（）16 、

5、 直接选择排序是一种不稳定的排序方法。（）17 、 顺序表用一维数组作为存储结构，因此顺序表是一维数组。（）18 、 栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。（）19 、 闭散列法通常比开散列法时间效率更高。（）20、一棵m阶B树中每个结点最多有 m个关键码，最少有2个关键码。（）三、 【填空题】（本大题共10 小空，每小空2 分，共 20 分）请将答案填写在答题卷相应题号处 。21、 、 数据结构课程讨论的主要内容是数据的逻辑结构、存储结构和（） 。22、若要在单链表结点*P后插入一结点*S,执行的语句（）。23、折半搜索只适合用于（） 。24、栈结构允许进行删除操作的一

6、端为（） 。25、设一行优先顺序存储的数组A56 ， A00 的地址为1100，且每个元素占2 个存储单元，则A23 的地址为（） 。26、 若某二叉树有20 个叶子结点，有 30 个结点仅有一个孩子，则该二叉树的总结点个数为（） 。27、一棵具有5层满二叉树中节点总数为（） 。28、从树中一个结点到另一个结点之间的分支构成这两个结点之间的（） 。29、在无向图中，若从顶点 A到顶点B存在（），则称A与B之间是连通的。30、若图的邻接矩阵是对称矩阵，则该图一定是（）。四、【应用题】（本大题共5小题，每小题8分，共40分）请将答案填写在 答题卷相应 题号处。31、已知序列（12, 4, 17,

7、10, 7, 30）,用直接选择排序法对其进行递增排序，写出 每一趟的排序结果。32、单链表结点的类型定义如下：typedef struct LNode int data;struct LNode *next; LNode, *Linklist;写一算法，将带头结点的有序单链表A和B合并成一新的有序表 Co （注：不破坏A和B的原有结构）33、已知一棵非空二叉树，其按中序和后序遍历的结果分别为：中序：CGBAHEDJFI后序：GBCHEJIFDA请画出这棵二叉树，并写出其前序遍历的结果。34、已知字符：C1, C2, C3, C4, C5, C6的权分别为：17, 5, 16, 4, 8, 1

8、1,请构造 相应的赫夫曼树，并给出相应字符的赫夫曼编码。35、已知如下图所示二叉树，分别写出其前序、中序和后序序列。 AB Z数据结构模拟试卷一答案一、【单项选择题】（本大题共10小题，每小题2分，共20分）题号12345678910答案CDBCCCCDDB、【判断题】（本大题共10小题，每小题2分，共20分）题号11121314151617181920答案TTFFFTFTFF三、【填空题】（本大题共10小空，每小空2分，共20分）21、（ 运算）；22、 （ s->next=p->next;p->next=s ）23、（ 有序表）；24、（栈顶）；25、（1130 ）;26

9、、（ 69 ）;27、 （ 31 ）;28、（路径）；29、（路径）；30、（ 无向图）； 四、【应用题】（本大题共5小题，每小题8分，共40分）31、标准答案：第 1 趟：4 12 17 10 7 30第 2 趟：4 7 17 10 12 30第 3 趟：4 7 10 17 12 30第 4 趟：4 7 10 12 17 30第 5 趟：4 7 10 12 17 30复习范围或考核目标：课件第十章第二节。32、标准答案:Merge(Linklist A, Linklist B, Linklist &C ) void Merge(Linklist A, Linklist B, Link

10、list &C) C=(Linklist)malloc(sizeof(LNode);pa=A->next; pb=B->next; pc=C; while(pa&&pb) pc->next=(Linklist)malloc(sizeof(LNode); pc=pc->next;if(pa->data<=pb->data) pc->data=pa->data; pa=pa->next; else pc->data=pb->data; pb=pb->next; if(!pa) pa=pb;whil

11、e(pa) pc->next=(Linklist)malloc(sizeof(LNode);pc=pc->next;pc->data=pa->data; pa=pa->next;pc->next=NULL;复习范围或考核目标：课件第二章第三节。33、标准答案：前序遍历结果：ACBGDEHFJI复习范围或考核目标：课件第六章第四节。34、标准答案:c1:10c2:1111c3:01c4:1110c5:110c6:00复习范围或考核目标：课件第六章第八节。35、标准答案：前序：ABDECF 中序：DBEACF 后序：DEBFCA复习范围或考核目标：课件第六章第四

12、节。北京语言大学网络教育学院数据结构模拟试卷二注意：1 .试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。2 .请各位考生注意考试纪律，考试作弊全部成绩以零分计算。3 .本试卷满分100分，答题时间为 90分钟。4 .本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。、【单项选择题】（本大题共10小题，每小题2分，共20分）在每小题列出的四个选答题卷相应题号处。项中只有一个选项是符合题目要求的，请将正确选项前的字母填在1、程序段：sum=0; for (i=1;i<n*n;i+) Sum+;的平均情况下时间代价的表达式是（）AB2、数据结构

13、通常是研究数据的（A存储和逻辑结构C理想和抽象C（n2）及它们之间的联系。B存储和抽象D理想与逻辑D (nlogn)3、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1,则编号为49的结点的左孩子的编号为（A 98B 994、在有 n个叶结点的 Huffman树中,A 2n-1B2n+1C 50其结点总数为（C 2nD 485、设有100个元素，用折半查找法进行查找时，最大比较次数是（D不确定）°A 25B 50C 106、若需要利用形参直接访问实参，则应把形参变量说明为（D 7)参数A指针7、已知单链表杂度应为（A 0（1）8、在一棵高度为（

14、）。A 2 h-1B引用A长度为m,单链表 ）°C传值D常值B长度为n,若将B联接在A的末尾，其时间复B O（m）h（假定树根结点的层号为C O(n)D O(m+n)0）的完全二叉树中，所含结点个数不小于B 2 h+19、假定一个链式队列的队头和队尾指针分别为 （ ）。C 2 h-1front 和 rear,D 2 h则判断队空的条件为A front = rearC rear != NULL10、在一棵树中,A分支结点B front != NULLD front = NULL）没有前驱结点。B叶结点C树根结点D空结点二、【判断题】（本大题共10小题，每小题2分，共20分）正确的填T,

15、错误的填F,填 在 答题卷相应题号处。11 、线性表的逻辑顺序与物理顺序总是一致的。（）12 、在链式存储的栈的头部必须要设头结点。（）13 、在二叉树中插入结点，则该项二叉树便不再是二叉树。（）14 、由二叉树结点的先序序列和后序序列可以唯一确定一棵二叉树。（）15 、栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。（）16 、用树的前序遍历序列和中序遍历序列可以导出树的后序遍历序列。（）17 、 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得到的序列也一定相同。（）18、哈夫曼（Huffman） 树是带权路径长度最短的树。路径上权值较大的结点离根

16、较近。（）19 、 对于任一个图，从某顶点出发进行一次深度或广度优先搜索，可以访问图中每一个顶点。（）20、带权的无向连通图的最小生成树是唯一的。（）三、 【填空题】（本大题共10 小空，每小空2 分，共 20 分）请将答案填写在答题卷相应题号处 。21 、如果 n 个顶点的图是一个环，则它有（）棵生成树。22 、 设在等概率情形下, 对有 n 个元素的顺序表进行插入（插入位置i 取 0 到 n 范围内的整数）, 平均需要移动（）个元素。23、具有96 个结点的完全二叉树的高度为（） 。24、如果一棵树有 ni个度为1的结点，有作个度为2的结点，nm个度为m的结点 , 则度为 0 的结点有（）

17、个。25、若二叉树的中序序列与后序序列相同，则该二叉树是空树或（） 。26、若一棵完全二叉树有500 个结点，则该二叉树的深度为（） 。27、用邻接矩阵表示无向图时，若图中有1000 个顶点，1000 条边，则形成的邻接矩阵有（）矩阵元素。28、给定序列100 ， 86， 48， 73， 35， 39， 42， 57， 66， 21，按堆结构的定义，则它一定是（）堆。29、 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用（）存储结构。30、向一个长度为n的顺序表的第i个元素（1 < i wn+1）之前插入一个元素时，需向后移动（）个元素

18、。四、 【应用题】（本大题共5 小题，每小题8 分，共 40 分）请将答案填写在答题卷相应题号处 。31、已知某二叉树中序遍历的结果是 ABC试画出其可能的二叉树五种形态。32、一个一维整数数组 Am中有n （n Wm件非空整数，它们相继存放于数组的前端并 已按非递减顺序排列，在数组Am中插入一个新的整数 x,并使得插入后仍保持非递减有序。要求x 插在值相等的整数后面。编写相应的函数实现。33、假设字符A,B,C,D,E,F 的使用频率分别是0.07,0.09,0.12,0.22,0.23,0.27 ，写出A,B,C,D,E,F 的 Huffman （哈夫曼）编码。34、一颗二叉树的中序序列和

19、后序序列分别是DCBAEFG口 DCBGFEA,请画出该二叉树并给出先序序列。35、设有一个输入数据的序列是 46, 25, 78, 62, 12, 37, 70, 29 ,试画出从空树起，逐个输入各个数据而生成的二叉搜索树。数据结构模拟试卷二答案一、【单项选择题】（本大题共10小题，每小题2分，共20分）题号12345678910答案CAAADBCDDC二、【判断题】（本大题共10小题，每小题2分，共20分）题号11121314151617181920答案FFFFFTFTFF三、【填空题】（本大题共10小空，每小空2分，共20分）21、 （ n ）;22、（ n/2 ）23、 （ 7 ）;2

20、4、（ n2+2n3+ .+（m-1）nm+1 ）25、（只有根节点的二叉树）；26、 （ 9 ）;27、 （ 1000000 ）;28、（ 大顶）；29、（ 顺序）；30、（ n i +1 ）;四、【应用题】（本大题共5小题，每小题8分，共40分）31、标准答案：二叉树图形如下图1:复习范围或考核目标：课件第六章第四节。32、标准答案：插入函数如下：void InsertSort (int A , int m , int & n , int x) if (n<m) int I,j ;for (i=0 ; i<n&&Ai<= ; i+ ;)for (j

21、=n-1 ; j>=I ; j- )Aj+1 = A j ;A I =x ;n+;elsecerr<< 数组已满，不能插入！ ” <<end;l exit () ; 复习范围或考核目标：课件第五章第一节。33、标准答案：Huffman 编码如下：A 1110B 1111C 110D 00E 01F 10复习范围或考核目标：课件第六章第八节。34、标准答案：先序遍历：ABCDEFG复习范围或考核目标：课件第六章第四节。35、标准答案:复习范围或考核目标：课件第六章第五节。北京语言大学网络教育学院数据结构模拟试卷三注意：1 .试卷保密，考生不得将试卷带出考场或撕页，否

22、则成绩作废。请监考老师负责监督。2 .请各位考生注意考试纪律，考试作弊全部成绩以零分计算。3 .本试卷满分100分，答题时间为 90分钟。4 .本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。、【单项选择题】（本大题共10小题，每小题2分，共20分）在每小题列出的四个选答题卷相应题号处。项中只有一个选项是符合题目要求的，请将正确选项前的字母填在1、在一个图中，所有顶点的度数之和等于图的边数的（）倍。A 1/2B 1C 2D 42、采用顺序查找方法查找长度为n的线性表，平均查找长度为（）。A nB n/23、线性链表不具有的特点是（A随机访问C插入与删除时不必移动元素4、

23、删除长度为n的非空顺序表的第 元素。C (n+1)/2D (n-1)/2)°B不必事先估计所需存储空间大小D所需空间与线性表长度成正比i个数据元素之前需要移动表中（）个数据A n-i B n+i C n-i+1D n-i-15、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。A不发生改变B发生改变C不能确定D以上都不对6、一个栈的进栈序列是a, b, c, d, e,则栈的不可能的输出序列是（）。A edcba B decba C dceab D abcde7、若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为（ ）。A 4 B 5C 8D

24、98、由同一关键字集合构造的各棵二叉排序树（）。A其形态不一定相同，但平均查找长度相同。B其形态不一定相同，平均查找长度也不一定相同。C其形态均相同，但平均查找长度不一定相同。D其形态均相同，平均查找长度也都相同。9、具有n个顶点的无向连通图最少有（）条边。A n B n+1 C n-1 D 2n10、若某文件经内部排序得到 100个初始归并段，若使用K路归并三趟完成，则（ ）。A K>=2 B K>=3C K>=4D K>=5二、【判断题】（本大题共10小题，每小题2分，共20分）正确的填T,错误的填F,填 在 答题卷相应题号处。11 、树的父链表示就是用数组表示树的

25、存储结构。（）12 、栈和队列逻辑上都是线性表。（）13 、单链表从任何一个结点出发，都能访问到所有结点。（）14、AOE网中，只有一个入度为 0的顶点（起始点），只有一个出度为 0的顶点（结束点） 。（）15 、关键路径可能不只一条，但缩短某一关键路径一定能够缩短工期。（）16 、有向图的邻接矩阵一定不是对称的。（）17、在AOER中，关键路径是唯一的。（）18 、若将一株树转换成二叉树，则该二叉树的根结点一定没有右子树。（）19 、索引顺序存取方法ISAM 是一种专门为磁盘存取设计的索引顺序文件的组织方法。（）20、基数分类只适用于以数字为关键字的情形，不适用以字符串为关键字的情形。（）三

26、、 【填空题】（本大题共10 小空，每小空2 分，共 20 分）请将答案填写在答题卷相应题号处 。21 、数据结构算法中，通常用时间复杂度和（）两种方法衡量其效率。22、若频繁地对线性表进行插入与删除操作，该线性表应采用（）存储结构。23、 （）链表从任何一个结点出发，都能访问到所有结点。24、某带头结点的单链表的头指针head,判定该单链表非空的条件（）。25、已知指针p 指向单链表中某个结点，则语句p->next=p->next->next 的作用是（）。26、在栈的顺序实现中，栈顶指针top ，栈为空条件（） 。27、在长度为n的循环队列中，删除其节点为x的时间复杂度为

27、（）。28、有三个结点的二叉树，最多有（）种形状。29、深度为90 的满二叉树，第11 层有（）个结点。30、设有10 个值，构成哈夫曼树，则该哈夫曼树共有（）个结点。四、 【应用题】（本大题共5 小题，每小题8 分，共 40 分）请将答案填写在答题卷相应题号处 。31 、已知一棵二叉树的先序序列是ABCDEFG ，中序序列为CBEDAFG ，请构造出该二叉树。32、有一组关键码序列(38，19，65，13，49，41，1，73)，采用冒泡排序方法由小到大进行排序，请写出每趟排序的结果。33、设图 G = <V, E>, V = 1 , 2, 3, 4, 5, 6, E=<1

28、 , 2>, <1, 3>, <2, 5>, <3, 6>， <6， 5>， <5， 4>， <6， 4>。画出该图，并写出所有的拓扑序列。34、一个一维整数数组 Am中有n (n wm)"非空整数，它们相继存放于数组的前端并已按非递减顺序排列，要求删除数组中多余的值相等的整数(只保留第一次出现的那个整数) 。编写相应的函数实现。35、试编写一个函数，在一个顺序表A 中查找出具有最大值和最小值的整数。函数的原型如下所示，原型的参数表中给出顺序表对象为A， 通过算法执行，从参数表中的引用参数 Max 中得到表中的最大整数，Min 中得到表中的最小整数。注意，函数中可使用顺序表的如下两个公有函数：int Length( ); 求表的长度；int getData(int k); 提取第k 个元素的值。#include “ SeqList.h ”template <class T>void FindMaxMin(SeqList<int>& A, int& Max, int& Min);数据结构模拟试