C语言数据结构综合测试题及答案.pdf

第第 10 章章 综合测试综合测试 能力要求能力要求 （1）计算机基础知识：掌握图的概念以及图的基本操作。 （2）分析问题：针对具体的问题，要能够运用图去进行分析，逐步找到解决问题的方法。 （3） 具有概念化和抽象化能力：针对具体的应用和实际的问题，能够运用图对问题进行抽象，提取它 的逻辑结构和存储结构。 （4） 发现问题和表述问题：在具体的工程中，能够发现工程中涉及到图的问题，并能够明确表述。 （5） 建模：在具体的工程中，能够使用图进行建模，设计合理的数据结构和相应的算法。 （6） 解决方法和建议：在具体工程应用中，发现了关于图的问题，要能够解决问题，并提出合理的建 议。 （7） 定义功能，概念和结构：使用图这种逻辑结构处理一些具体问题，实现系统的功能。 （8） 设计过程的分段与方法：采取不同的阶段去设计（概念设计、详细设计）一个具体的图的应用项 目。 （9）软件实现过程：了解系统中各个模块中的关于图的设计；讨论算法（数据结构、控制流程、数据流 程） ；使用编程语言实施底层设计（编程） 。 10.1 综合测试题综合测试题 1 一、判断题 说明：共说明：共 1010 题，每题题，每题 1 1 分，满分分，满分 1010 分分 （）1 有一批数据，经常用来进行插入和删除处理，这样的数据用顺序表存储最合适。 （）2 栈用于实现子程序调用。 （）3 队列可用于表达式的求值。 （）4 队列在队头插入，队尾删除。 （） 5 若二叉树用二叉链表作存贮结构， 则在 n 个结点的二叉树链表中只有 n1 个非空指针域。 （）6 完全二叉树的某结点若无左孩子，则它必是叶结点。 （）7 将一棵树转换成二叉树后，根结点没有左子树。 （） 8 任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找 时间。 （）9 中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。 （）10 如果待排序的数据是有一定顺序的，那么冒泡和简单选择排序法中，简单选择最好。 二、填空题 说明：共说明：共 1010 空，每空空，每空 1 1 分，满分分，满分 1010 分。分。 1 栈的特点是，队列的特点是。 2 深度为 k 的完全二叉树的至少有个节点， 至多有节点。 3 一棵二叉树的前序遍历结点的访问顺序为：abdgcefh， 中序遍历为：dgbaechf， 则其后序遍历 结果为。 4 一组记录元素的关键码为75，84，26，33，92，15，则利用快速排序的方法，以第一个记录为 枢纽值得到的一次划分结果是： 5 n 个顶点的无向连通图中最多边数为，最少边数为。 6 利用冒泡排序处理 n 个数据，最快比较次完成排序，最慢比较次完成排序。 三、选择题 说明：共说明：共 2020 小题，每小题小题，每小题 1 1 分，满分分，满分 2020 分；请将答案填入题后括号中。分；请将答案填入题后括号中。 在本选择题中出现的在本选择题中出现的 frontfront 代表队列的队头指针，代表队列的队头指针，rearrear 代表队列的队尾指针，代表队列的队尾指针，toptop 代表栈顶指针。其中代表栈顶指针。其中， 涉及到单链表的节点定义如下：涉及到单链表的节点定义如下： structlist int data; struct list *next; ; 1 循环队列用数组 Amaxsize 表示，下面哪个选项表示该循环队列队满 （） Arear=maxsize-1Bfront=（rear+1）%maxsize Crear-t=maxsizeDrear-ft=maxsize-1 2 元素的入栈序列是 a，b，c，d，则栈的不可能的输出序列是（） AdcbaBabcdCdcabDcbad 3 高度为 3 的完全二叉树最多有个节点，最少有个节点（） A7，8B4，7C7，4D8，7 4 堆的形状是一颗（） A二叉排序树B 满二叉树 C 完全二叉树 D 平衡二叉树 5 从 n 个未排序的数中，找出处在中间位置的元素的计算时间复杂度为（） A O（1）B O（n）C O（ 2 lognn）D O（ 2 n） 6 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（） 。 A 必须是连续的B 部分地址必须是连续的 C 一定是不连续的D 连续不连续都可以 7 线性表是具有 n 个（）的有限序列（n0） A 表元素B.字符C 数据元素D 数据项 8 设有一个二维数 Amn，假设 A00存放位置在 644（10） ，A22存放位置在 676（10） ， 每个元素占一个空间，则 A45在（）位置， （10）表明用 10 进数表示。 A692（10）B626（10） C709（10）D724（10） 9 不带头结点的单链表 head 为空的判定条件是（） Ahead=NULLBhead-next=NULL Chead-next=headDhead!=NULL 10 在循环双链表的 p 所指结点之后插入 s 所指结点的操作是（） 。 Ap-right=s;s-left=p;p-right-left=s;s-right=p-right; Bp-right=s;p-right-left=s;s-left=p;s-right=p-right; Cs-left=p;s-right=p-right;p-right=s;p-right-left=s; Ds-left=p;s-right=p-right;p-right-left=s;p-right=s; 11 若在线性表中采用折半查找法查找元素，该线性表应该： （） A元素按值有序B采用顺序存储结构 C元素按值有序，且采用顺序存储结构D元素按值有序，且采用链式存储结构 12 下列哪一个程序片断是删除链表中间点。（假设欲删除结点为 Pointer 结点， Back 为前一个结点） （） Afree（Pointer）;Bfree（Back）; CBack=Pointer-next;DBack-next=Pointer-next; free（Pointer）;free（Pointer）; 13 用邻接表存储的图的深度优先遍历（DFS）算法类似于二叉树的（） A先序遍历B中序遍历 C后序遍历D按层次遍历 14 若已知一个栈的入栈序列是 1，2，3，4.，n，其输出序列为 p1，p2，p3，p4，.，pn，若 p1=n，则 pi 为（） 。 AiBn=i Cn-i+1D不确定 15（）排序的比较次数与记录的初始排列状态无关。 A插入B冒泡C选择D快速 16 用链表仿真队列时，队空的条件是（） Afront= =rearBrearnext=p; p-next=s.Bs-next =p-next ; p-next=s. Cs-next =p-next; p=sDp-next=s; s-next=p 10 在双向链表指针 p 的结点前插入一个指针 q 的结点操作是（） Ap-Llink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q； Bp-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink; Cq-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q; Dq-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q; 11 用链表仿真栈时，栈满的条件是（） Atop=0Btop！=0C没有DtopNULL 12 数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置， 假定队列中元素的个数小于，计算队列中元素的公式为（） rf （nfr）% nnrf（nrf）% n 13 下列关键字序列中， （）是堆。 16， 72， 31， 23， 94， 5394， 23， 31， 72， 16， 53 16， 53， 23， 94，31， 7216， 23， 53， 31， 94， 72 14 若需在 O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是 （） A快速排序B 堆排序C 归并排序D直接插入排序 15 关键路径是事件结点网络中（） 。 A从源点到汇点的最长路径B从源点到汇点的最短路径 C最长回路D最短回路 16 设无向图的顶点个数为 n，则该图最多有（）条边。 An-1Bn（n-1）/2Cn（n+1）/2D0En2 17 将下图的二叉树按中序线索化，结点 X 的右指针和 Y 的左指针分别指向（） AA，DBB，CC D，ADC，A B A D CX E Y 图 10.517 题图图 10.618 题图 18 已知一个图如图所示，若从顶点 a 出发按深度优先搜索法进行遍历，则可能得到的一种顶点序 列为 （） Aa，b，e，c，d，fBa，c，f，e，b，d Ca，e，b，c，f，dDa，e，d，f，c，b 19 已知广义表 LS（ （a，b，c） ， （d，e，f） ） ，运用 head 和 tail 函数取出 LS 中原子 e 的运算是 （） Ahead（tail（LS） ）Btail（head（LS） ） Chead（tail（head（tail（LS） ） ）Dhead（tail（tail（head（LS） ） ） ） 20 若串 S1=ABCDEFG， S2=9898 ，S3=#，S4=012345，执行 concat（replace（S1，substr（S1，length（S2） ，length（S3） ） ，S3） ，substr（S4，index（S2， 8） ，length（S2） ） ）其结果为。（） AABC#G0123BABCD#2345CABC#G2345 DABC#2345EABC#G1234FABCD#1234 GABC#01234 四、简答题 说明：共说明：共 5 5 小题，每小题小题，每小题 8 8 分，满分分，满分 4040 分分 1 试求以下稀疏数组压缩后的数组内容。 001080 000000 040300 000000 600000 050000 000000 图 10.71 题图 2 线性表有两种存储结构：一是顺序表，二是链表。试问： （1）如果有 n 个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自 动地改变。在此情况下，应选用哪种存储结构？ 为什么？ （2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素， 那么应采用哪种存储结构？为什么？ 3 将右面的树转换成对应的二叉树，并写出其中序遍历的顺序。 图 10.83 题图 4 下图是带权的有向图 G，求： （1） 用邻接表表示法表示此有向图； （2） 从结点 A 到结点 I 的最短路径； 图 10.94 题图 5 选取哈希函数 H（key）key Mod 11，用线性探测再散列开放定址法解决冲突。试在 010 的散 列地址空间内对关键字序列19、11、31、23、17、27、41、13、91、61构造哈希表，并计算在等概率下 成功查找的平均查找长度。 五、算法题 说明：共说明：共 2 2 小题，每小题小题，每小题 1010 分，满分分，满分 2020 分。分。 以下题目的算法可以用以下题目的算法可以用 C C 语言函数表达，也可以用伪代码描述。语言函数表达，也可以用伪代码描述。 1 试写出一个函数，实现“计算二叉树所有叶子节点个数”。