数据结构模拟试卷二

计算机专业基础综合数据结构（排序）模拟试卷2(题后含答案及解析)题型有：1. 单项选择题 2. 综合应用题单项选择题1-40小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

1．采用简单选择排序，比较次数与移动次数分别为( )。

A．O(n)，O(log2n)B．O(log2n)，O(n2)C．O(n2)，O(n)D．O(nlog2n)，O(n)正确答案：C解析：简单选择排序的关键字比较次数KCN与对象的初始排列无关。

第i 趟选择具有最小关键字对象所需的比较次数总是n—i—1次(此处假定整个待排序对象序列有n个对象)。

因此，总的关键字比较次数为：最坏情况是每一趟都要进行交换，总的对象移动次数为RMN=3(n一1)。

知识模块：数据结构2．就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是( )。

A．堆排序＜快速排序＜归并排序B．堆排序＜归并排序＜快速排序C．堆排序＞归并排序＞快速排序D．堆排序＞快速排序＞归并排序正确答案：A解析：此题考查的知识点为排序的空间复杂性。

堆排序辅助空间为O(1)，快速排序为O(log2n)，归并排序为O(n)。

应选A。

知识模块：数据结构3．一组记录的关键码为(25，48，16，35，79，82，23，40，36，72)，其中，含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。

A．16，25，35，48，23，40，79，82，36，72B．16，25，35，48，79，82，23，36，40，72C．16，25，48，35，79，82，23，36，40，72D．16，25，35，48，79，23，36，40，72，82正确答案：A解析：对于(25，48，16，35，79，82，23，40，36，72)，(25，48)和(16，35)归并的结果为(16，25，35，48)。

(79，82)和(23，40)归并后的结果为(23，40，79，82)，余下的两个记录不归并，所以一趟归并后的结果为(16，25，35，48，23，40，79，82，36，72)，本题答案为A。

长沙理工大学数据结构模拟试卷2一、填空题（每空1分，共10分）1．顺序存储结构中数据元素之间的逻辑关系是由存储位置表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

2．非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。

3．n个顶点的连通图用邻接矩阵表示时，该矩阵至少有（）个非零元素。

4．（）可作为实现递归函数调用的一种数据结构。

5．由权值为{3, 8, 6, 2, 5}的叶子结点生成一棵哈夫曼树，其带权路径长度为（）。

6．设S="I_ am_ a_ teacther"，其长度为（）。

7．稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。

8．分块有序是指将文件划分为若干块，（）无序，（）有序。

二、判断题（你认为正确的请打对，错误的打错。

每题2分，共10分）1．线性表的顺序存储结构优于链接存储结构。

2．B—树是一种动态索引结构，它既适用于随机查找，也适用于顺序查找。

3．在线索二叉树中，任一结点均有指向其前趋和后继的线索。

4．用一维数组存储二叉树时，总是以前序遍历存储结点。

5．在索引顺序表上采用分块查找，在等概率情况下，其平均查找长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。

三、单选题（请把你认为正确的答案填入括号内，每小题1分，共10分）1．假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（）。

A 树B 图C 线性表D 集合2．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（）结构。

A 栈B队列 C 数组D线性表3．若某线性表经常的操作是取第i 个元素和找第i个元素的前趋，则采用（）存储方法最节省时间。

A 顺序表B 单链表C 双链表D 单循环链表4．广义表(a, b, (c, (d)))的表尾是（）。

国家二级C语言（数据结构与算法）机试模拟试卷2(题后含答案及解析)题型有：1. 选择题选择题1．算法中，对需要执行的每一步操作，必须给出清楚、严格的规定。

这属于算法的A．正当性B．可行性C．确定性D．有穷性正确答案：C解析：本题考查算法的基本特征。

算法的可行性表示算法中执行的任何步骤都是可以被分解为基本的可执行的操作步：确定性是指算法的每一步骤必须有确切的含义；有穷性是指算法必须能在执行有限个步骤之后终止。

知识模块：数据结构与算法2．下列叙述中正确的是A．算法就是程序B．设计算法时只需要考虑数据结构的设计C．设计算法时只需要考虑结果的可靠性D．以上三种说法都不对正确答案：D解析：所谓算法是指解题方案的准确而完整的描述。

是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。

算法不等于程序，也不等于计算方法。

设计算法时不仅要考虑对数据对象的运算和操作，还要考虑算法的控制结构。

知识模块：数据结构与算法3．下列叙述中正确的是A．算法的效率只与问题的规模有关，而与数据的存储结构无关B．算法的时间复杂度是指执行算法所需要的计算工作量C．数据的逻辑结构与存储结构是一一对应的D．算法的时间复杂度与空间复杂度一定相关正确答案：B解析：算法的时间复杂度是指执行算法所需要的计算工作量。

算法的工作量用算法所执行的基本运算的次数来度量，而算法所执行的基本运算次数是问题规模的函数；算法的空间复杂度一般是指执行这个算法所需要的内存空间。

算法的时间复杂度与空间复杂度并不相关。

数据的逻辑结构就是数据元素之间的逻辑关系，它是从逻辑上描述数据元素之间的关系，是独立于计算机的；数据的存储结构是研究数据元素和数据元素之问的关系如何在计算机中表示，它们并非一一对应。

算法的执行效率不仅与问题的规模有关，还与数据的存储结构有关。

知识模块：数据结构与算法4．在DOS环境F，代表键盘和显示器的设备文件名为A．PRNB．CONC．NULD．LPT正确答案：B解析：本题考查DOS下面的虚拟设备文件，选项A)的PRN表示打印机，选项B)中的CON表示键盘或屏幕，选项C）的NUL表示虚拟空设备，选项D)的LPT表示并口。

数据结构-试卷二及答案一、判断（每小题 1 分，共 10 分） 1．数据的存储结构是数据的逻辑结构的存储映象，不仅要存储数据元素的值，还要存储元素之间的相互关系。

2．用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系。

3．完全二叉树的叶子结点只能出现在最后一层上。

4．折半查找方法要求待查表必须是有序的顺序表。

5．在有向图 G 中， V 2 ， V 1 和 V 1 ， V 2 是两条不同的边。

6．图的最小生成树是唯一的。

7．从循环单链表的某一结点出发，只能找到它的后继结点，不能找到它的前趋结点。

8．在单链表中，头结点是必不可少的。

9．对快速排序来说，初始序列为正序和反序，都是最坏情况。

10．广义表是特殊的线性表。

二、选择（每题 1 分，共 15 分） 1．设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S 。

若每个元素出栈后立即进入队列 Q ，且 7 个元素出队的顺序是bdcfeag ，则栈 S 的容量至少是（）。

A．1 B．2 C．3 D．4 2．下列线索二叉树1/ 8中（用虚线表示线索），符合后序线索树定义的是( )。

3．已知广义表 A= （（ a,b ） ,(c,d) ） , 则 head(A) 等于 ( )。

A．(a,b) B．((a,b)) C．a,b D．a 4．设字符串s1=‘ABCDEFG’,s2=‘PQRST’, 则运算s=strcat(strsub(s1,2,strlen(s2)),strsub (s1,strlen(s2),2))后结果为（）。

A．BCQR B．BCDEF C．BCDEFG D．BCDEFEF 5．具有 8 个顶点的连通图的深度优先生成树，其边数为（）。

A．8 B．9 C．7 D．6 6．算法分析的两个主要方面是（）。

A．空间复杂性和时间复杂性 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 7．下列四种排序中（）的空间复杂度最大。

模拟试卷二一、选择题（每小题2分，共10分）1．若线性表最常用的操作是存取第i个元素及其前趋的值，则采用存储方式节省时间。

a．单链表 b. 双链表c．单循环链表 d．顺序表2．对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其有孩子的编号，则可采用次序的遍历实现编号。

a．无序 b．中序c．后序 d．从根开始的层次遍历3．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是的二又树。

a．空或只有一个结点 b. 高度等于其结点数C．任一结点无左孩子 d．任一结点无右孩子4．下列排序算法中，时间复杂度不受数据初始状态影响，恒为 O（nlog2n）的是。

a．堆排序 b. 冒泡排序c．直接选择排序 d. 快速排序5. 下列排序算法中，算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。

a．堆排序 b．冒泡排序c．快速排序 d. SHELL排序二、判断题（每小题1分，共10分）1．（）在循环队列中，若尾指针Rear大于头指针Front，则其元素个数为 Rear - Front。

2．（）串是n个字母的有限序列（n >= 0）。

3. ( ）若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。

4．（）二叉树只能采用二又链表来存储。

5.（）有向图用邻接矩阵表示后，顶点i的出度等于第i行中非0且非加的元素个数。

6．（）图G的某一最小生成树的代价一定小于其他生成树的代价。

7.（）给定结点数的平衡二叉树的高度是唯一的。

8.（）9阶B树中，除报以外的任一结点中的关键字个数不少于4。

9．（）只有在初始数据表为倒序时，冒泡排序所执行的比较次数最多。

10.（）堆排序中，在输出一个根之后的调整操作中，“临时根”结点的值将被调到“叶子结点”上。

三、项空（每小题2分，共20分）l. 在单链表中，删除指针P所指结点的后继结点的语句是。

2．取出广义表A = ((x，y，z），（a，b，c，d）)中原子b的函数是。

试卷B一、选择题（本题共20分,每题2分）1．在数据结构中，从逻辑上可以把数据结构分成（ ） 。

A ．动态结构和静态结构 B. 线性结构和非线性结构 C. 紧凑结构和非紧凑结构 D. 内部结构和外部结构 2. 下列程序段的时间复杂度是（ ）count=0;for(k=1;k<=n;k*=2) for(j=1;j<=n;j++) count++;A.O(nlog2n)B.O(n)C.O(log2n)D.O(n2) 3. 以下描述错误的是：（ ）A. 线性表是n 个数据元素的有限非空集合。

B. 栈和队列都是操作受限的线性表。

C. 串（或字符串）是由零个或多个字符组成的有限序列。

D. 非空栈中的栈顶指针top 始终指向栈顶元素的下一个位置。

4. 若采用少用一个队列空间的方法来区分队满队空两种状态，则判定一个顺序循环队列 Q （最大队列长度MAXSIZE ）为满队列的条件是( )。

A. Q.front=Q.rearB. Q.front!=Q.rearC. Q.front=(Q.rear+1) % MAXSIZED. Q.front!=(Q.rear+1) % MAXSIZE 5. 按照二叉树的定义，具有 3 个结点的二叉树有（ ）种。

A. 3 B. 4 C. 5 D. 66. 设矩阵A （如下图所示）是一个对称矩阵，为了节省存储，将其下三角（包括对角线）部分按行序存放在一维数组 B[n(n+1)/2]中，对下三角部分中任一元素 ai,j(i ≥j)，在一维数组 B 的下标位置k 的值是（ ）。

A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j0,01,01,11,01,11,1...............n n n n a a a A a a a ----⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦7. 有一个有序表为｛5, 18，23, 33, 42, 54,56,78｝，当折半查找56时，经过（ ）次比较后查找成功。

计算机专业基础综合数据结构（树与二叉树）模拟试卷2(题后含答案及解析)题型有：1. 单项选择题 2. 综合应用题单项选择题1-40小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

1．设树T的度为4，其中度为1、2、3和4的结点个数分别为4、1、1、1，则T中的叶子数为( )。

A．10B．11C．9D．7正确答案：D解析：根据题中条件可知，1×4+2×1+3+4+1=4+1+1+1+n0，由此可以得出：n0=1×4+2×1+3+4+1一(4+1+1+1)=14—7=7. 知识模块：数据结构2．用下列元素序列(22，8，62，35，48)构造平衡二叉树，当插入( )时，会出现不平衡的现象。

A．22B．35C．48D．62正确答案：C解析：由题中所给的结点序列构造二叉排序树的过程如下图：当插入48后，首次出现不平衡子树，虚线框内即为最小不平衡子树。

知识模块：数据结构3．下面的算法实现了将二叉树中每一个结点的左右子树互换。

addQ(Q，bt)为进队的函数，delQ(Q)为出队的函数，empty(Q)为判别队列是否为空的函数，空白处应填的内容是( )。

typedef struct node{ int data；struct node*lchild，*rchild；}btnode；void exchange(btnode*bt){ btnode*p，*q；if(bt){ addQ(Q，bt)；while(!EMPTY(Q)){ p=delQ(Q)；q=p-＞rchild；p一＞rchild=p一＞lchild；( (1) )=q；if(p-&gt;lchild) ( (2) )；if(p-＞rchild)addQ(Q，p-＞rchild)；} }} A．p-＞lchild，delQ(Q，p一＞lchild)B．p-＞rchild，delQ(Q，p-＞lchild)C．p-＞lchild，addQ(Q，p-＞lchild)D．p-＞rchild，addQ(Q，p-＞lchild)正确答案：C 涉及知识点：数据结构4．已知有一棵二叉树，其高度为n，并且有且只有n个结点，那么二叉树的树形有( )种。

数据结构模拟试卷(一)及参考答案一．单项选择题（本大题共15小题，每小题2分，共30分）1．如果只想得到1024个元素组成的序列中的前5个最小元素，那么用( A )方法最快。

A、起泡排序B、快速排序C、堆排序D、直接选择排序2．算法分析的目的是（B）A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输入与输出的关系D．鉴别算法的可读性3．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（C）A．插入B．删除C．定位D．排序4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（D）A．3，2，6，1，4，5 B．5，6，4，2，3，1C．1，2，5，3，4，6 D．3，4，2，1，6，55．设串sl=″DataStructureswithJava″,s2=″it″，则子串定位函数index(s1,s2)的值为（A）A．15 B．16C．17 D．186．一个顺序存储的线性表的第一个元素的存储地址是100，每个元素的长度为4，则第4个元素的存储地址是（B）。

A. 108B. 112C. 116D. 1207．从一个具有n个结点的单链表中查找其值等于x的结点，在查找成功的情况下，平均需要比较（C）个结点。

A. nB. n/2C. (n+1)/2D. (n-1)/28．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（D）A．不一定相同 B．互为逆序C．都不相同D．都相同9．高度为5的二叉树至多有结点数为（A）A. 63B. 32C. 24D.6410．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（B）A．图中每个顶点的出度B．图中每个顶点的入度C．图中弧的条数D．图中连通分量的数目11．图的邻接矩阵表示法适用于表示（C）A．无向图B．有向图C．稠密图D．稀疏图12．在一个单链表中，若p所指的结点不是最后一个结点，在p之后插入s所指的结点，则执行（D）。

模拟试卷二一、单选题（每题 2 分，共20分）1.在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行(B )。

A. HL=p; p->next=HL;B. p->next=HL->next; HL->next=p;C. p->next=HL; p=HL;D. p->next=HL; HL=p;2.若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（A B ）个元素.A. nB.n-1C. n+1D.不确定3.下述哪一条是顺序存储方式的优点？（C A ）A．存储密度大 B.插入和删除运算方便C. 获取符合某种条件的元素方便D.查找运算速度快4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每个元素占一个空间，问A[2][3](10)存放在什么位置？(脚注(10)表示用10进制表示,m>3) BDA．658 B．648 C．633 D．653 3m+3=78 m=255.下列关于二叉树遍历的叙述中，正确的是( DA ) 。

A. 若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点6.k层二叉树的结点总数最多为( A ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.对线性表进行二分法查找，其前提条件是( ).A.线性表以链接方式存储，并且按关键码值排好序B.线性表以顺序方式存储，并且按关键码值的检索频率排好序C.线性表以顺序方式存储，并且按关键码值排好序D.线性表以链接方式存储，并且按关键码值的检索频率排好序8.对n个记录进行堆排序，所需要的辅助存储空间为A. O（1og2n）B. O（n）C. O（1）D. O（n2）9.对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K %7作为散列函数，则散列地址为0的元素有（）个，A．1 B．2 C．3 D．410.下列关于数据结构的叙述中，正确的是( D ).A.数组是不同类型值的集合B.递归算法的程序结构比迭代算法的程序结构更为精炼C.树是一种线性结构D.用一维数组存储一棵完全二叉树是有效的存储方法二、填空题（每空1分，共26分）1.数据的逻辑结构被分为_________、________、__________和___________四种。

计算机专业基础综合（数据结构）模拟试卷2(总分：70.00，做题时间：90分钟)一、单项选择题(总题数：21，分数：42.00)1.单项选择题1-40小题。

下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

（分数：2.00）__________________________________________________________________________________________ 解析：2.栈和队列的主要区别在于( )。

（分数：2.00）A.它们的逻辑结构不一样B.它们的存储结构不一样C.所包含的运算不一样D.插入和删除运算的限定不一样√解析：解析：栈和队列的逻辑结构都是线性的，都有顺序存储和链式存储，有可能包含的运算不一样，但不是其主要区别。

任何数据结构在针对具体问题时所包含的运算都可能不同。

所以正确答案是D。

3.若循环队列以数组Q[0．．m-1]作为其存储结构，变量rear。

表示循环队列中的队尾元素的实际位置，其移动按rear=(rear+1)MOD m进行，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是( )。

（分数：2.00）A.rear-lengthB.(rear—length+m)MOD mC.(rear—length+1+m)MOD m √D.m-length解析：解析：按照循环队列的定义，因为元素移动按照rect=(rear+1)MOD m进行，则当数组Q[m—1]存放了元素之后，下一个入队的元素将存放到Q[0]中，因此队列的首元素的实际位置是(rear—length+1+m)MOD m。

4.一个以向量V[n]存储的栈，其初始栈顶指针top为n+1，则对于x，其正确的进栈操作是( )。

（分数：2.00）A.top=top+1；V[top]=xB.V[top]=x；top=top+1C.top=top-1；V[top]=x √D.V[top]=x；top=top-1解析：解析：此题考查的知识点是入栈的具体操作。

数据结构模拟题2一、判断题。

判断下列各题是否正确，若正确，在答题卡中涂“A”，否则涂“B”。

1．线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

Χ2．线性表的链式存储结构优于顺序存储结构。

Χ3．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

Χ4．顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

Χ5．链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。

Χ6．两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

√7．在循环队列中，元素的个数为rear-front。

Χ8．完全二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

√9．邻接表存储结构只用于有向图的存储，邻接矩阵对有向图和无向图的存储都适用。

Χ10．连通分量是无向图中的极小连通子图。

Χ11．没有回路的图能进行拓扑排序。

√12．生成树指的是图的极大连通子图。

Χ13．采用折半查找法对有序表进行查找总比采用顺序查找法对其进行查找要快。

Χ14．采用线性探测法处理冲突时，当从哈希表中删除一个记录时，不应将这个记录的所在位置的数据置空，因为这样会影响以后的查找。

√15．对于给定的关键字集合，以不同的次序插入到初始为空的二叉排序树中，得到的二叉排序树是相同的。

Χ二、单选题。

1．数据结构可以分为三大类，它们是【】、树和图。

AA、线性表B、栈和队列C、链表D、顺序表2．下列程序段的时间复杂度为【】。

Afor(i=0；i<m；i++)for(j=0；j<t；j++)c[i][j]=0；for(i=0；i<m；i++)for(j=0；j<t；j++)for(k=0；k<n；k++)c[i][j]=c[i][j]+a[i][k]*b[k][j]；A 、 O(m*n*t)B 、 O(m+n+t)C 、 O(m+n*t)D 、 O(m*t+n)3．若线性表的最常用的操作是存取第i 个元素及其前驱元素的值，则采用【 】存储方式最省时间。

数据结构试题部分题目或答案有问题，现将已经发现的公布如下，同学在作这些模拟题的时候应着重做题方法的理解，遇到问题以教材或课件为准，不确定的地方可找同学商量或问我（1）试卷1第一套填空题第1题，试卷1第2套选择题第3题关于循环队列队头指针和队尾指针的约定与教材不一致，以教材或课件为准，实际上front指向的是队头元素，rear指向当前尚未被占用的第一个队列空间，队慢或队空的判定条件及入队/出队等操作具体可参考课件或教材（2）试卷1第一套应用题第5题，不声明邻接点顺序时默认编号最小的邻接点为第一邻接点，该图的深度优先遍历序列为*****,答案错。

此外，当给定邻接表时则邻接点顺序按照邻接表中的前后顺序确定，如试卷1第二套填空题第8题（3）试卷1第五套应用题第4题，两种方法处理冲突的方法下所求ASL值相等都为7/6（4）试卷1第五套填空题第8题答案给出的是小顶堆需满足的条件，大顶堆满足ki=k2i ki=k2i+1 （5）试卷1第一套填空题第9题模式匹配的BF算法以书中答案为准，两者区别在于，教材中存储字符串的数组的0号单元不存放有效字符，而试卷答案认为0号单元也放数组（6）试卷1第二套填空题第7题给定初始序列建堆未声明建大顶堆还是小顶堆，答案中给出的是小顶堆，大顶堆也要会建（7）试卷1第二套应用题第1题第4趟直接插入排序的结果应为(22，40，45，48，80，78)；答案中给出的实际为第三趟，关键在于首元素自身有序不算一趟（8）试卷1第二套填空题第2题入栈操作以教材为准，教材中top是指向的栈顶(第一个空位置)的指针，与该套试卷中栈顶结构不一样，以教材为准（9）试卷1第三套填空题第12题答案中给出的不是拓扑序列，正确的是1423 （10）试卷1中多处遇到空指针NULL时写的是0而非NULL，实际两者皆可（11）试卷1第4套填空题第2题双向链表的删除答案错，应为p―llink-rlink=p-rlink; p-rlink-llink=p-llink;此外，注意课堂中讲的指针名和操作方法（12）第4套填空题第6题答案错，设哈夫曼树中共有99个结点，则该树中有____50_____个叶子结点；若采用二叉链表作为存储结构，则该树中有__100___个空指针域。

北京语言大学网络教育学院《数据结构》模拟试卷一注意：1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。

请监考老师负责监督。

2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。

3.本试卷满分100分，答题时间为90分钟。

4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。

一、【单项选择题】(本大题共10小题，每小题2分，共20分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。

1、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则采用（）存储方式最节省时间。

[A] 顺序表[B] 双链表[C]带头结点的双循环链表[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、若用数组S[n]作为两个栈S1和S2的共用存储结构，对任何一个栈，只有当S[n]全满时才不能作入栈操作。

为这两个栈分配空间的最佳方案是（）。

[A] S1的栈底位置为0，S2的栈底位置为n[B] S1的栈底位置为－1，S2的栈底位置为n/2[C] S1的栈底位置为0，S2的栈底位置为n－1[D] S1的栈底位置为0，S2的栈底位置为n/27、对一棵二叉排序树进行（）遍历，可以得到该二叉树的所有结点按值从小到大排列的序列。

《数据结构》模拟试题A一、单项选择题（每题 3 分，共24分）1．下面关于线性表的叙述错误的是（）。

(A) 线性表采用顺序存储必须占用一片连续的存储空间(B) 线性表采用链式存储不必占用一片连续的存储空间(C) 线性表采用链式存储便于插入和删除操作的实现(D) 线性表采用顺序存储便于插入和删除操作的实现2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。

(A)2m-1 (B)2m (C) 2m+1 (D) 4m3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）。

(A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。

(A) BADC (B) BCDA (C) CDAB (D) CBDA5．设某完全无向图中有n个顶点，则该完全无向图中有（）条边。

(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-16．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。

(A) 9(B) 10(C) 11(D) 127．设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。

(A) n-1 (B) n (C) n+1 (D) 2n-18．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。

(A) 2，3，5，8，6 (B) 3，2，5，8，6(C) 3，2，5，6，8 (D) 2，3，6，5，8二、填空题（每题2分，共16分）1.为了能有效地应用HASH查找技术，必须解决的两个问题是（）和（）。

2.下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。

模拟试题二模拟试题二一、选择题（28分）1.设一数列的顺序为l，2，3,4，5,通过栈结构不可能排成的顺序数列为( )。

A)3,2，5，4，l B)1，5,4，2，3C）2，4，3,5,l D）4，5，3，2,l2。

二叉树的第3层最少有（)个结点。

A)0 B）1 C)2 D）33。

—个n个顶点的连通无向图，其边的个数至少为( )。

A) n-l B)n C）n+l D）nlogn4。

下列排序方法中，( ）的比较次数与记录的初始排列状态无关。

A）直接插入排序 B）起泡排序C）快速排序 D）直接选择排序5.-棵哈夫曼树总共有II个结点，则叶子结点有( ）个。

A）5 B）6 C）7 D)96.已知某算法的执行时间为（n+n2)+log2(n+2)，n为问题规模,则该算法的时间复杂度是( ）。

A)O（n）B）O（n2) C）O（log2n）D）O(nlog2n)7。

如果一棵树有10个叶子结点，则该树总共至少有( )个结点。

A）lO B）11 C）19 D) 218。

—个100×100的三角矩阵a采用行优先压缩存储后，如果首元素a[0]［0]是第一个元素，那么a[4] [2］是第( )个元素。

A）13 B) 401 C) 402 D）4039.有一棵二叉树如题图1,该树是（）。

A）二叉平衡树B)二叉排序树C)堆的形状D)以上都不是10。

对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树，其时间复杂度为（)，利用Kruska算法的时间复杂度为（).A）O（log2n) B）0(n2) C)O（ne) D）O（elog2ne)11.具有n个顶点的完全有向图的边数为( ）.A）n（n—l)/2 B）n（n-l） C) n2 D）n2—112。

设有100个元素，用折半查找时,最大比较次数为（)，最小比较次数为（）。

A）25 B)7 C) 10 D)l13。

在内部排序中，排序时不稳定的有（).A）插入排序B）冒泡排序C）快速排序D）归并排序14.串是一种特殊的线性表，其特殊性体现在（)。

国家二级C语言机试（数据结构与算法）模拟试卷2(题后含答案及解析)题型有：1. 选择题选择题1．对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为（）。

A．9B．10C．45D．90正确答案：C解析：在最坏情况下，冒泡排序的时间复杂度为n(n-1)/2，为45，答案选C。

知识模块：数据结构与算法2．下列叙述中正确的是（）。

A．算法的效率只与问题的规模有关，而与数据的存储结构无关B．算法的时间复杂度是指执行算法所需要的计算工作量C．数据的逻辑结构与存储结构是一一对应的D．算法的时间复杂度与空间复杂度一定相关正确答案：B解析：算法的时间复杂度是指执行算法所需要的计算工作量，与数据的存储结构有关，与算法的空间复杂度没有关系。

数据的逻辑结构与存储位置无关，即与存储结构无关，所以选择B。

知识模块：数据结构与算法3．下列叙述中正确的是（）。

A．线性表链式存储结构的存储空间一般要少于顺序存储结构B．线性表链式存储结构与顺序存储结构的存储空间都是连续的C．线性表链式存储结构的存储空间可以是连续的，也可以是不连续的D．以上说法都不对正确答案：C解析：在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的，所以选择C。

知识模块：数据结构与算法4．某二叉树共有12个结点，其中叶子结点只有1个。

则该二叉树的深度为（根结点在第1层）（）。

A．3B．6C．8D．12正确答案：D解析：根据二叉树的性质，叶子结点比度为2的结点个数多一个，叶子结点只有1个，那么度为2的结点为0个，可以得出共有11个度为1的结点，那么该二叉树每一层上只能有一个结点，共12层，即深度为12。

知识模块：数据结构与算法5．对长度为n的线性表作快速排序，在最坏情况下，比较次数为（）。

A．nB．n-1C．n(n-1)D．n(n-1)/2正确答案：D解析：在最坏情况下，快速排序需要比较n(n-1)/2次。

国家电网招聘考试计算机类专业知识（数据结构与算法）模拟试卷2(题后含答案及解析)题型有：1. 单项选择题单项选择题1．采用顺序查找法查找长度为n的顺序表时，查找成功的平均查找长度为( )。

A．(n－1)／2B．(n+1)／2C．nD．n／2正确答案：B解析：在查找成功的前提下，查找的最好情况是查找的第一个元素即想要查找的元素，最坏情况是查找的最后一个元素即想要查找的元素，所以查找成功的平均查找长度是(n+1)／2。

2．在循环队列中用数组A[0．．m－1]存放队列元素，其队头指针和队尾指针分别为front和rear，则当前队列中的元素个数是( )。

A．(front－rear+1)％mB．(rear－front+1)％mC．(front－rear+m)％mD．(rear－front+m)％m正确答案：D3．算法分析的目的是( )。

A．找出数据结构的合理性B．研究算法中输入和输出的关系C．分析算法的效率，以求改进D．分析算法的易懂性和文档性正确答案：C4．下列关于栈的叙述，正确的是( )。

A．只要确定了入栈序列，就可以确定出栈序列B．栈是一种操作受限的线性表，只允许在其两端进行操作C．采用非递归方式重写递归程序时，必须使用栈D．函数调用时，可以使用栈来保存必要的信息解析：确定了入栈序列无法确定出栈序列，因为各个元素出栈的时间是不确定的；栈是一种操作受限的线性表，只允许在其一端进行操作；采用非递归方式重写递归程序时，除了栈还可以使用循环结构算法。

5．若允许表达式中多种括号混合嵌套，则检查表达式中括号是否正确配对的算法，通常选用的辅助结构是( )。

A．栈B．线性表C．队列D．二叉排序树正确答案：A解析：由于栈具有先进后出的特点，因此选用辅助结构栈可以实现表达式中多种括号混合嵌套的配对。

例如，使用3个栈，就可以同时解决表达式中的“{”与“}”、“[”与“]”、“(”与“)”的配对问题。

6．设线性表的长度为15，采用冒泡排序，在最坏的情况下需要比较的次数为( )。

《数据结构》（本）模拟试题二一、填空题（每小题2分，共24分）1．结构中的数据元素存在多对多的关系称为_____ ___结构。

2．要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。

则比较的次数和算法的时间复杂度分别为________和。

3．设有一个头指针为head的单向循环链表，p指向链表中的结点，若p->next= =_______，则p所指结点为尾结点。

4．向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行s->next=h和。

5．在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为________和r=s; (结点的指针域为next)6．设有n阶对称矩阵A，用数组S进行压缩存储，当i<j时，A的数组元素a ij相应于数组S的数组元素的下标为_______。

（数组元素的下标从1开始）7．一棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左、右孩子编号分别为_____ _、___ _____。

8．一棵有2n-1个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有_______个叶结点。

9．________遍历二叉排序树可得到一个有序序列。

10．如图1所示的二叉树，其前序遍历序列为_______ __。

图111．二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。

这种说法是__________的。

(回答正确或不正确)12．按某关键字对记录序列排序，若在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。

二、单项选择题（每小题2分，共30分）1．在C语言中，顺序存储长度为3的字符串，需要占用（）个字节。

A．4 B．3 C．6 D．122．数据的物理结构（）。

A．与数据的逻辑结构无关 B．仅仅包括数据元素的表示C．只包括数据元素间关系的表示 D．包括数据元素的表示和关系的表示3．串函数StrCat（a,b）的功能是进行串（）。