内容发布更新时间 : 2024/12/23 20:49:34星期一 下面是文章的全部内容请认真阅读。
第10章 综合测试
[能力要求]
（1） 计算机基础知识：掌握图的概念以及图的基本操作。
（2） 分析问题：针对具体的问题，要能够运用图去进行分析，逐步找到解决问题的方法。
（3） 具有概念化和抽象化能力：针对具体的应用和实际的问题，能够运用图对问题进行抽象，提取它
的逻辑结构和存储结构。
（4） 发现问题和表述问题：在具体的工程中，能够发现工程中涉及到图的问题，并能够明确表述。 （5） 建模：在具体的工程中，能够使用图进行建模，设计合理的数据结构和相应的算法。
（6） 解决方法和建议：在具体工程应用中，发现了关于图的问题，要能够解决问题，并提出合理的建
议。
（7） 定义功能，概念和结构：使用图这种逻辑结构处理一些具体问题，实现系统的功能。
（8） 设计过程的分段与方法：采取不同的阶段去设计（概念设计、详细设计）一个具体的图的应用项
目。
（9）软件实现过程：了解系统中各个模块中的关于图的设计；讨论算法（数据结构、控制流程、数据流
程）；使用编程语言实施底层设计（编程）。
10.1综合测试题1
一、判断题
说明：共10题，每题1分，满分10分
（ ）1① 有一批数据，经常用来进行插入和删除处理，这样的数据用顺序表存储最合适。 （ ）2① 栈用于实现子程序调用。 （ ）3① 队列可用于表达式的求值。 （ ）4① 队列在队头插入，队尾删除。
（ ）5② 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （ ）6② 完全二叉树的某结点若无左孩子，则它必是叶结点。 （ ）7② 将一棵树转换成二叉树后，根结点没有左子树。
（ ） 8② 任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间。
（ ）9② 中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。
（ ）10③ 如果待排序的数据是有一定顺序的，那么冒泡和简单选择排序法中，简单选择最好。
二、填空题
说明：共10空，每空1分，满分10分。
1① 栈的特点是 ，队列的特点是 。 2③ 深度为k的完全二叉树的至少有 个节点， 至多有 节点。
3② 一棵二叉树的前序遍历结点的访问顺序为：abdgcefh， 中序遍历为：dgbaechf， 则其后序遍历结果为 。
4② 一组记录元素的关键码为{75，84，26，33，92，15}，则利用快速排序的方法，以第一个记录为枢纽值得到的一次划分结果是：
5② n 个顶点的无向连通图中最多边数为 ，最少边数为 。 6② 利用冒泡排序处理n个数据，最快比较 次完成排序，最慢比较 次完成排序。
三、选择题
说明：共20小题，每小题1分，满分20分；请将答案填入题后括号中。
在本选择题中出现的front代表队列的队头指针，rear代表队列的队尾指针，top代表栈顶指针。其中，涉及到单链表的节点定义如下： struct list {
int data; struct list *next; };
1② 循环队列用数组A[maxsize] 表示，下面哪个选项表示该循环队列队满 （ A rear==maxsize-1 C rear-t==maxsize
B front==（rear+1）%maxsize D rear-ft==maxsize-1
）
2② 元素的入栈序列是a，b，c，d，则栈的不可能的输出序列是 （ ） A dcba
B abcd
C dcab
D cbad
3② 高度为3的完全二叉树最多有 个节点，最少有 个节点 （ ） A 7，8
B 4，7
C 7，4
D 8，7
4① 堆的形状是一颗（ ）
A 二叉排序树 B 满二叉树 C 完全二叉树 D 平衡二叉树
5③ 从n个未排序的数中，找出处在中间位置的元素的计算时间复杂度为（ ） A O（1）
B O（n）
C O（nlog2n）
D O（n）
26① 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。 A 必须是连续的 C 一定是不连续的
B 部分地址必须是连续的 D 连续不连续都可以
7① 线性表是具有n个（ ）的有限序列（n≠0） A 表元素 B.字符
C 数据元素 D 数据项
8② 设有一个二维数A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676（10），每个元素占一个空间，则A[4][5]在（ ）位置，（10）表明用10进数表示。
A 692（10） C 709（10）
B 626（10） D 724（10）
9① 不带头结点的单链表head为空的判定条件是（ ）
A head==NULL
B head->next==NULL D head!=NULL
C head->next==head
10② 在循环双链表的p所指结点之后插入s所指结点的操作是（ ）。 A p->right=s;s->left=p;p->right->left=s;s->right=p->right; B p->right=s;p->right->left=s;s->left=p;s->right=p->right; C s->left=p;s->right=p->right;p->right=s;p->right->left=s; D s->left=p;s->right=p->right;p->right->left=s;p->right=s; 11① 若在线性表中采用折半查找法查找元素，该线性表应该：（ ） A 元素按值有序
B 采用顺序存储结构
D 元素按值有序，且采用链式存储结构
C 元素按值有序，且采用顺序存储结构
12② 下列哪一个程序片断是删除链表中间点。（假设欲删除结点为Pointer结点，Back为前一个结点）
（ ）
A free（Pointer）; B free（Back）;
C Back=Pointer->next;
D Back->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为 （ ）。
A i
B n=i D 不确定
C n-i+1
15②（ ）排序的比较次数与记录的初始排列状态无关。 A 插入 B 冒泡 C 选择 D 快速 16② 用链表仿真队列时，队空的条件是（ ） A front= =rear B rear<0 C 没有 D front= =NULL 17③ 有一子函数如下： n）
{ if（n<=2）
return 1; else
int X（int