数据结构习题

1、1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表示与实现1.4 算法和算法分析1、 数据结构是一门研究_的程序设计问题中，计算机的操作对象以及它们之间的关系和操作等的学科。A: 数据库B: 数值计算C: 高级语言D: 非数值计算2、 数据结构课程属于计算机科学知识体中_领域的综合性专业基础课。A: 离散结构Discrete Structures (DS)B: 程序设计语言Programming Languages (PL)C: 程序设计基础Programming Fundamentals (PF)D: 算法与复杂性Algorithms and Complexity (AL)

2、3、 “数据结构”是介于_、程序设计和代数系统三者之间的核心课程。A: 计算机硬件B: 计算机软件C: 数据库系统D: 计算机操作系统4、 具有相同性质的计算机数据集合及在这个集合上的一组操作，称为_。A: 逻辑结构B: 物理结构C: 数据类型D: 数据结构5、 数据结构可记为DS = D, R，其中D是某一数据对象，R是该对象中所有数据成员之间_的有限集合。A: 算法B: 关系C: 数据元素D: 数据类型 6、 数据结构中，与计算机存储器有关的是数据的_结构。A: 线性B: 非线性C: 物理D: 逻辑7、 _分别属于逻辑结构和物理结构。A: 树和图B: 表和索引C: 顺序和链接D: 顺序表和

3、散列表8、 在问题规模n较大情况下，效率相对较高的时间复杂度T(n)为_。A: O(n2)B: O(2n)C: O(100n)D: O(n*log2n) 9、 判断：科学家尼克劳斯沃斯(Niklaus Wirth)关于数据结构的一个公式是：数据结构程序 算法。10、 判断：数据结构由基本的抽象数据类型组成，并包括一组相关的服务或操作。11、 判断：在数据结构中，算法的每条指令或语句的执行次数是有限的。12、 判断：时间复杂度高的算法，其空间复杂度也高。13、 判断：算法的时间复杂度达到T(n)=O(n2)时，当n增大后，算法的执行时间会急剧增大，这类算法常称为“坏”的算法。14、 判断：算法的

4、健壮性是指：算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 15、 已知某算法如下，其平均时间复杂度T(N)=_。void sub1(int N) int i,j; for (i=1;i=N;+i) for (j=1;j1;-i) /运行1次 for (j=0;jaj+1) /运行 (N-1)+ (N-2)+2)次 temp=aj; aj=aj+1; aj+1=temp; 2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现2.4 一元多项式的表示及相加1、 线性表是由n(n)个_数据元素a1，a2， an组成的有限序列

5、。A: 数值型 B: 非数值型 C: 同种类型 D: 不同类型 2、 顺序表的特点是以元素在计算机内_相邻来表示线性表中数据元素之间的逻辑关系。A: 逻辑位置 B: 物理位置 C: 磁盘位置 D: 扇区位置 3、 链表中结点的逻辑次序和物理次序_。A: 一定相同B: 一定不相同C: 不一定相同D: 与结点的内容有关4、 链表用一组任意的存储单元来依次存放线性表的结点，这组存储单元_。A: 必须是连续的B: 必须是不连续的C: 按结点的前后次序排列D: 即可以是连续的，也可以是不连续的5、 _的插入和删除操作会移动大量的结点。A: 单链表B: 双链表C: 顺序表D: 循环链表6、 在双向链表的结

6、点中有两个指针域，其一指向直接后继，另一指向_ 。A: 尾结点B: 头结点C: 直接前趋D: 结点本身7、 指向双向链表结点d的指针，存在下面的关系：_。A: d-next-prior = d-prior-nextB: d-next- next = d-prior- prior C: d-next- next = dD: d-prior- prior = d8、 顺序表的特点有：_。A: 插入、删除效率高B: 存储空间能动态分配C: 可方便随机存取数据元素D: 逻辑关系与物理位置不一致9、 链表的特点有：_。A: 插入、删除效率低B: 存储空间不能静态分配C: 逻辑关系与物理位置一致D: 随机

7、存取数据元素效率低10、 循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向_ 。A: 尾结点B: 头结点C: 前一个结点D: 空 11、 已知某单链表操作的头文件，试写出函数LocatePos(LinkList L,int i,Position &p)实现的算法。12、 已知某单链表操作的头文件试写出函数InsFirst(LinkList &L,ElemType e)实现的算法。13、 已知某单链表操作的头文件，试写出函数DelFirst(LinkList &L,ElemType &e)实现的算法。14、 已知某单链表操作的头文件，试写出函数Append(LinkLi

8、st &L,ElemType e)实现的算法。15、 已知某单链表操作的头文件，试写出函数ListInsert(LinkList &L,int i,ElemType e)实现的算法。16、 已知某单链表操作的头文件，试写出函数ListDelete(LinkList &L,int i,ElemType &e)实现的算法。17、 已知某单链表操作的头文件如下，试写出函数MergeList(LinkList La, LinkList Lb, LinkList &Lc)实现的算法。单链表操作的头文件：List.h/=/= 1. 预定义常量和类型/=#define TRUE1#define FALSE0

9、#define OK1#define ERROR0#define INFEASIBLE-1#define OVERFLOW-2typedef intStatus;/Status是函数的类型，其值是函数结果状态代码。typedef int ElemType;/定义数据元素类型取为 int /=/= 2. 定义数据结构/=/= 2.2 单链表存储结构(带头结点的线性链表)typedef struct LNodeElemType data;struct LNode *next;*Link,*Position;typedef structLink head,tail;int len;LinkList;

10、/=/= 3. 定义基本操作/=/= 3.2 单链表基本操作StatusLocatePos(LinkList L,int i,Position &p);/定位:将单链表中第i个结点位置送至p /=/ The end of List.h /= 3.1 栈3.2 栈的应用举例 3.3 栈与递归的实现*3.4 队列 1、 _是限定仅在表的一端（通常为表尾）进行插入或删除操作的线性表。A: 队列B: 栈C: 串D: 树2、 对栈的操作所具有的特征为_。A: “先进先出” B: “后进后出” C: “先进后出” D: 上面三者都不是3、 _是栈的典型操作。A: Enqueue B: Dequeue C:

11、 SortD: Pop4、 满栈时执行_操作会产生上溢。A: PopB: PushC: Enqueue D: Dequeue 5、 空栈时执行_操作会产生下溢。A: PopB: PushC: Enqueue D: Dequeue 6、 _的一个重要应用是在程序中实现递归调用。A: 栈B: 队列C: 数组D: 生成树7、 在队列中，允许插入的一端叫_。A: 队尾B: 队头C: 顶D: 底8、 对队列的操作所具有的特征为_。A: “先进后出” B: “后进先出” C: “先进先出” D: 上面三者都不是9、 _是队列的典型操作。A: Psh B: PopC: SortD: EnQueue 10、

12、对双端队列_。A: 插入只能在队尾进行B: 删除只能在队头进行C: 插入和删除可以在两端进行D: 插入和删除只能分别在两端进行11、 当队列的最大长度不能预估时，宜采用_。A: 循环队列B: 双端队列C: 顺序队列D: 链队列12、 树的层次遍历和图的广度优先搜索常用到_数据结构。A: 栈B: 队列C: 数组D: 生成树13、 非递归算法比递归算法可读性好。答案:N14、 递归算法总可以转换为非递归算法，此时常需要显式地使用队列结构。答案:N15、 非递归算法一般比递归算法的运行效率要低 。答案:N16、 递归算法的表达相对非递归的算法更简洁，但实际运行效率往往不如后者。答案:Y17、 递归算

13、法属于“好”的算法，即其T(n)已都是关于n的多项式数量级。答案15:N 18、 N已知某循环顺序队列操作的头文件如下，试写出函数QueueInput(SqQueue &Q) 实现的算法，可以调用函数EnQueue(SqQueue &Q,QElemType e)。19、 试写出函数QueueOutput(SqQueue Q) 实现的算法，可以调用函数QueueLength(SqQueue Q,int &len)。20、 试写出函数QueueEmpty(SqQueue Q) 实现的算法。21、 试写出函数QueueLength(SqQueue Q,int &len) 实现的算法。22、 试写出函

14、数 EnQueue(SqQueue &Q,QElemType e)实现的算法。23、 试写出函数DeQueue(SqQueue &Q,QElemType &e) 实现的算法。栈和队列操作的头文件：List_QU.h/=/= 1. 预定义常量和类型/=#define TRUE1#define FALSE0#define OK1#define ERROR0#define INFEASIBLE-1#define OVERFLOW-2typedef intStatus;/Status是函数的类型，其值是函数结果状态代码。typedef int ElemType;/定义数据元素类型取为 int /=/=

15、 2. 定义数据结构/=/= 2.6 循环顺序队列存储表示#define MAXQSIZE20/最大队列长度typedef struct QElemType *base;/初始化的动态分配存储空间intfront;/头指针，若队列不空，指向队列头元素;intrear;/尾指针，若队列不空，指向队列尾元素的下一个位置;SqQueue;/=/= 3. 定义基本操作/=/= 3.6 循环顺序队列基本操作StatusQueueInput(SqQueue &Q);/通过输入数据建立循环顺序队列StatusEnQueue(SqQueue &Q,QElemType e);/入队/=/ The end of

16、List.h /=4.1 串类型的定义4.2 串的表示和实现4.3 串的模式匹配算法.4.4 串操作应用举例1、 _是一种特殊的线性表，其数据元素最为简单，仅是单个字符。A: 串B: 队列 C: 数组 D: 生成树 2、 子串定位运算又称为_。A: 查找 B: 排序 C: 替换 D: 模式匹配 3、 串的长度表示有多种，PASCAL采用的方法是_。A: 串长用独立的单元存储，通常为第一个元素 B: 串长用独立的单元存储，通常为最后一个元素 C: 在串的末尾设结束标记0 D: 在串的末尾用回车表示 4、 串的长度表示有多种，C语言采用的方法是_。A: 串长用独立的单元存储，通常为第一个元素 B:

17、 串长用独立的单元存储，通常为最后一个元素 C: 在串的末尾设结束标记0 D: 在串的末尾用回车表示 5、 串的长度表示有多种，C语言采用的方法是_。A: 串长用第一个元素存储 B: 在串的末尾设结束标记0 C: 在串的末尾用双引号表示 D: 串长用独立的单元存储，但不一定是第1个元素6、 _不是常见的串表示方法。A: 定长顺序存储表示法 B: 堆分配存储表示法 C: 块链存储表示 D: 循环队列 1、 已知某字符串操作的头文件，试写出函数 StrCompare(HString S,HString T) 实现的算法。2、 已知某字符串操作的头文件，试写出函数 Concat(HString &T

18、,HString S1, HString S2) 实现的算法。3、 已知某字符串操作的头文件，试写出函数 SubString(HString &Sub,HString S,int pos,int len) 实现的算法。4、 已知某字符串操作的头文件，试写出函数 Index(HString S,HString T,int pos) 实现的算法，可以调用函数StrLength(HString &T)。5、 已知某字符串操作的头文件，试写出函数 StrInsert(HString &S,int pos,HString T) 实现的算法，可以调用函数StrAssign(HString &T, char

19、 * chars)和StrLength(HString &T)。6、 已知某字符串操作的头文件，试写出函数 StrDelete(HString &S,int pos,int len) 实现的算法，可以调用函数StrAssign(HString &T, char * chars)和StrLength(HString &T)。串操作的头文件：List_STR.h/=/= 1. 预定义常量和类型/=#define TRUE1#define FALSE0#define OK1#define ERROR0#define INFEASIBLE-1#define OVERFLOW-2typedef intS

20、tatus;/Status是函数的类型，其值是函数结果状态代码。typedef int ElemType;/定义数据元素类型取为 int /=/= 2. 定义数据结构/=/= 2.8 串的定长顺序存储表示/= 2.9 串的堆分配存储表示typedef structchar *ch; /若是非空串,则按串长分配存储区,否则ch为NULLint length; /串长度HString; 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构 5.6 m元多项式的表示*5.7 广义表的递归算法*1、 一维数组可以看成是一个简单的_。A

21、: 串B: 栈C: 队列 D: 线性表 2、 二维数组也可看成是一个线性表，其中每一个元素是_。A: 具有相同长度的一维数组 B: 具有不同长度的一维数组 C: 具有相同长度的队列或栈 D: 具有不同长度的队列或栈 3、 二维数组中的元素最多可有_个直接前驱（边界除外）。A: 1 B: 2 C: 3D: 4 4、 N维数组也可看成是一个线性表，其中每一个元素是_。A: 具有不同长度的N-1维数组B: 具有相同长度的N-1维数组C: 具有不同长度的N-2维数组D: 具有相同长度的N-2维数组5、 _特点是：其矩阵阶数很大，非零元个数较少，零元很多，但非零元的排列没有一定规律。A: 对称矩阵 B:

22、 对角矩阵 C: 三角矩阵 D: 稀疏矩阵 6、 _不是稀疏矩阵的存储方法。A: 循环队列 B: 三元组表 C: 带行指针的链表 D: 十字链表 7、 广义表是线性表的推广，其表中的元素_。A: 是多个线性表 B: 是多个数组 C: 可以具有不同的结构 D: 不可以有不同的结构 8、 _在人工智能等领域得到了广泛的应用，通常其第一个元素称为表头，其余元素组成表尾。A: 链表 B: 散列表 C: 顺序表 D: 广义表 1.有一个二维数A，行下标的范围是0到8，列下标的范围是1到5，每个数组元素用相邻的2个字节存储。存储器按字节编址。 假设存储数组元素A0，1的第一个字节的地址是0。若按列存储，则

23、A1，3的地址是_。2.有一个二维数A，行下标的范围是1到10，列下标的范围是0到5，每个数组元素用相邻的2个字节存储。存储器按字节编址。 假设存储数组元素A1，0的第一个字节的地址是1。若按列存储，则A2，3的地址是_。编程题1、/= 稀疏矩阵三元组的相加操作Status AddSMatrix(TSMatrix A,TSMatrix B,TSMatrix &C);/矩阵相加A+B-C2、 /= 稀疏矩阵三元组的相减操作Status SubSMatrix(TSMatrix A,TSMatrix B,TSMatrix &C);/矩阵相减A-B-C3、 /= 稀疏矩阵三元组的转置操作Status

24、TransposeSMatrix(TSMatrix S,TSMatrix &T);/求矩阵S的转置矩阵T4、 /= 稀疏矩阵三元组的相乘操作Status MulSMatrix(TSMatrix A,TSMatrix B,TSMatrix &C);/矩阵相乘A=B*C 6.1 树的定义和基本术语6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林6.5 树与等价问题6.6 赫夫曼树及其应用6.7 回溯法与树的遍历6.8 树的计数 1、 对非完全二叉树而言，采用_存储结构会浪费许多存储空间。A: 顺序B: 链式C: 索引D: 散列2、 对完全二叉树而言，采用顺序存储结构_。A: 遍历算法效

25、率低B: 删除算法效率低C: 会浪费许多存储空间D: 不会浪费许多存储空间3、 采用双亲表示的树的存储结构，其特点是：从当前结点出发_。A: 容易找到双亲和其孩子B: 容易找到双亲和根结点C: 容易找到孩子，但不易找到其双亲D: 容易找到双亲，但不易找到其孩子4、 树的度是指树内各结点_。A: 度的最小值B: 度的最大值C: 度的平均值D: 度的累加值5、 树是n(n=0)个结点的有限集。在任意一棵非空树中：有且仅有一个特定的称为_的结点。根6、 树是n(n=0)个结点的有限集。当n1时,其余结点可分为m(m0)个互不相交的有限集T1,T2,.Tm,其中每一个集合称为根的_。子树7、 多棵互不

26、相交的树的集合称为_。森林8、 _常用于二叉树的存储结构，其特点是：从当前结点出发能马上找到其左右子树，也能直接找到其双亲。三叉链表9、 _常用于二叉树的存储结构，其特点是：从当前结点出发能马上找到其左右子树，但不能直接找到其双亲。二叉链表10、 树中的终端结点又称_。叶结点11、 树中的非终端结点又称_。分支结点12、 树中的叶结点是指度为_的结点。013、 树中结点的_是指该结点拥有子树的数目。度14、 一棵树从根到某结点所经分支上的所有结点都是该结点的_。祖先15、 以某结点为根的子树中的任一结点都称为该结点的_。子孙16、 通常规定树中根的孩子为第_层结点。217、 _的逻辑特征是：每

27、个数据元素至多有一个直接前趋和二个直接后继。二叉树18、 树的逻辑特征是：每个数据元素至多有一个直接前趋和_个直接后继。多19、 树中的_结点没有直接前趋，但有多个直接后继。根20、 树中的_结点没有直接后继，但有一个直接前趋。叶21、 二叉树可有_种不同的形态。522、 二叉树的度不大于_。223、 二叉树的第3层上至多有个_结点。424、 深度为3的二叉树至多有_个结点。725、 二叉树的第_层上至多有个4结点。326、 二叉树的第_层上至多有个8结点。427、 深度为_的二叉树至多有15个结点。428、 二叉树的第_层上至多有个32结点。629、 先序遍历二叉树算法的时间复杂度T(n)为

28、_（设二叉树的结点数为n）。O(n)30、 中序遍历二叉树算法的时间复杂度T(n)为_（设二叉树的结点数为n）。O(n) 31、 中序遍历二叉树算法在最坏情况下的空间复杂度S(n)为_（设二叉树的结点数为n）。O(n) 32、 后序遍历二叉树算法的时间复杂度T(n)为_（设二叉树的结点数为n）。O(n)33、 *将下面的森林转化成一棵二叉树。34、 *将下面的二叉树转化成树或森林35、 *已知一棵二叉树结点的前序序列和中序序列，请构造出这棵二叉树。前序序列：A-B-D-H-I-E-J-C-F-G 中序序列：H-D-I-B-E-J-A-F-C-G36、 *某通信电文由5 个字母组成，它们的出现概

29、率如下表所示，将这些概率大小作为5个字母结点所对应的权，试画出相应的赫夫曼树和赫夫曼编码。要求概率较小的结点作为左孩子结点，概率较大的结点作为右孩子结点;连接左孩子的连线对应编码0，连接右孩子的连线对应编码1。字母 A B C D E 概率 0.18 0.3 0.32 0.05 0.15 37、 *有5个带权的结点A、B、C、D和E，它们的权分别如为：20、5、10、60和15。试构造一棵拥有这5个叶结点的最优二叉树，并求出相应的带权路径长度WPL。38、 *已知某二叉树采用顺序存储结构，其图示如下（其中“”表示该结点不存在），请画出相应的二叉树。 编号 0 1 2 3 4 5 6 7 8 9

30、 10 11 12 13 14 15 结点 A B C D E F G H 39、 已知某二叉树如下,现采用一维数组的顺序存储结构来表示，请填写出该二叉树各结点在一维数组中的位置（结点不存在的单元可用“”或空来表示）。 40、 判断：满二叉树必定是完全二叉树或顺序二叉树41、 判断：完全二叉树必定是满二叉树或顺序二叉树42、 判断：顺序二叉树不一定是满二叉树。43、 判断：森林至少有三棵树组成。44、 判断：森林至少有两棵以上的二叉树组成。45、 判断：一般的树可以转换成二叉树，而森林可以转换成两棵以上的二叉树。46、 判断：一棵二叉树可以转换成一棵普通的树，但不能转换成森林。47、 判断：双

31、亲在同一层的结点互为兄弟结点。48、 判断：双亲在同一层的结点互为堂兄弟结点。49、 判断：树的深度是指树中最大的分支数。50、 判断：树中结点的最大层次数就是树的高度。51、 判断：二叉树是一种无序树。52、 判断：有序树是指所有结点的孩子有先后之分的树。53、 判断：森林是m(m=0)棵互不相交的树的集合。 54、 已知某二叉树操作的头文件，试写出函数 PreOrderTraverse(BiTree T,Status (*Visit)(TElemType e) 实现的算法，访问结点可调用函数Visit(TElemType e)。Status PreOrderTraverse(BiTree

32、T,Status (*Visit)(TElemType e)/=先序遍历二叉树T,对每个结点调用函数Visit一次且仅一次if(T!= _(_)_)Visit(T-data);PreOrderTraverse(_(_)_);_(_)_ (T-rchild,Visit); return OK;/PreOrderTraverse 55、 已知某二叉树操作的头文件，试写出函数 InOrderTraverse(BiTree T,Status (*Visit)(TElemType e) 实现的算法，访问结点可调用函数Visit(TElemType e)。56、 已知某二叉树操作的头文件，试写出函数 Po

33、stOrderTraverse(BiTree T,Status (*Visit)(TElemType e) 实现的算法，访问结点可调用函数Visit(TElemType e)。57、 已知某二叉树操作的头文件如下，试写出函数 leaf(BiTree T) 实现的算法。int leaf(BiTree T)/=求二叉树T的叶结点if (T = NULL) return (_(_)_);/形态0if (T-lchild = NULL)& (T-rchild = NULL)return (_(_)_);/形态1else return (_(_)_);/形态2-4/leaf58、 已知某二叉树操作的头文

34、件，试写出函数 branch(BiTree T) 实现的算法。59、 已知某二叉树操作的头文件，试写出函数 node(BiTree T) 实现的算法。60、 已知某二叉树操作的头文件，试写出函数 depth(BiTree T) 实现的算法。7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径 1、 _适用于表示稠密图。A: 散列表B: 双链表C: 邻接表D: 邻接矩阵2、 _适用于表示稀疏图。A: 邻接矩阵B: 二叉链表C: 散列表D: 邻接表3、 有向图的邻接矩阵_。A: 可能是不对称的B: 一定是三角矩阵C:

35、一定是不对称D: 一定是对称4、 邻接表是图的一种链式存储结构。其中采用_表示顶点及有关信息，称为顶点表。A: 数组B: 矩阵C: 单链表D: 双链表5、 数据结构中，无向图的边_。A: 总是与两个顶点相连接B: 可以与多个顶点相连接C: 可以与一个顶点相连接，另一端不与其他顶点相连D: 可以同时与一个顶点相连接，形成环6、 采用普里姆算（Prim）法构造最小生成树时，_。A: 只能从某一个顶点出发B: 可以从任意一个边出发C: 只能从最小权的边开始D: 只能从最大权的边开始7、 求解最小生成树的问题可与_的实际问题相关联。A: N个城市间建立通信网络B: 一个城市到N个城市间的交通运输C:

36、学生选修多门相关课程安排D: 一个工程项目进度计划安排8、 求解关键路径的问题可与_的实际问题相关联。A: N个城市间建立通信网络B: 一个城市到N个城市间的交通运输C: 学生选修多门相关课程安排D: 一个工程项目进度计划安排9、 用有向边表示一个工程中的各项活动，边上的权值表示活动持续时间的有向无环图，简称为_。A: 拓扑网络B: 关键路径C: AOV网D: AOE网10、 AOV网中的顶点表示_。A: 最短路径B: 活动C: 活动的前后次序D: 活动的持续时间11、 AOE网中有向边的权值表示_。A: 活动B: 事件C: 活动的前后次序D: 活动的持续时间12、 判断：网络是一种有向图。N

37、13、 判断：完全图中任何二个结点间都有一条边。Y14、 判断：图中任何结点都应该有一条边或弧与其相连。N15、 判断：图中有些边可以只有一个端点。N16、 判断：起点和终点相同的路径称为简单回路或简单环。N17、 判断：无向图的极大连通子图叫做连通分量。Y18、 图是由_集合及其之间的关系集合组成的一种数据结构。Vertex19、 图的数据结构G( V, E )，其中E = (x, y) | x, y V 是_的集合。edge 20、 _相对较少的图称为稀疏图。edge 21、 在一个有向图中，一个顶点v的入度就是与它相关联的_的个数。弧头(Head) 22、 _的邻接矩阵是对称的。无向图2

38、3、 邻接表是图的一种链式存储结构。其中依附于顶点vi的边由vi指向的一个_表示。单链表24、 用顶点表示活动，有向边 表示活动的前后次序的有向无环图，简称为_。AOV25、 图的逻辑特征是每个数据元素可以有_个直接前趋和多个直接后继。多26、 有10个顶点的连通图至少有_条边。927、 已知无向图G1如下，列出相应的邻接矩阵。 G1.arcs= 28、 已知有向图G的邻接矩阵1如下，请画出相应图。G1.arcs= 29、 根据下面给定的网，试按Prim算法，写出从V1出发构建最小代价生成树的过程（要求画出开始的两个中间过程和最终的最小代价生成树）。30、 根据下面给定的网，试按Kruskal

39、算法，写出构建最小代价生成树的过程（要求画出开始的两个中间过程和最终的最小代价生成树）。31、 已知某无向图的邻接表如下所示，基于该邻接表按深度优先搜索，写出从V1出发遍历各结点的次序，并画出该无向图。遍历各结点的次序：V1,V4,V5,V3,V2,V7,V8,V6 32、 已知某无向图的邻接表如下所示，基于该邻接表按广度优先搜索，写出从V1出发遍历各结点的次序，并画出该无向图。 遍历各结点的次序：V1,V3,V4,V5,V7,V6,V8,V2 编程题33、 已知某图的基本操作的头文件如下，试写出函数 Get_Degree(ALGraph &G) 实现的算法。/= 1. 预定义常量和类型/=

40、2. 定义数据结构/= 2.2 邻接表存储表示#define MAX_VERTEX_NUM 20typedef enumDG,DN,AG,AN GraphKind;/有向图，有向网，无向图，无向网typedef struct ArcNodeint adjvex;/该弧所指向的顶点的位置struct ArcNode *nextarc;/指向下一条弧的指针int Weight;/该弧相关信息:权重ArcNode;typedef struct VNodeVertexType data;/顶点信息int InDegree,OutDegree;/顶点的入度和出度ArcNode *firstarc;/指向

41、第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum,arcnum; /图的当前顶点数和弧数GraphKind kind; /图的种类标志ALGraph;/= 3. 定义基本操作/= 3.2 图的邻接表存储表示的基本操作Status Get_Degree(ALGraph &G);/计算入度和出度Status Get_Degree(ALGraph &G)/计算入度和出度int i;ArcNode*t;for(i=0; iadjvex.InDegree+;while (t-nexta

42、rc!= _(_)_) t= t-nextarc;G.verticesi.OutDegree+;G.verticest-adjvex.InDegree+;return OK;/Get_Degree 9.1 静态查找表 9.2 动态查找表 9.3 哈希表 1、 在查找操作中，如查找成功，则结果给出的是_。A: 查找表的长度B: 成功比较的次数C: 失败比较的次数D: 关键字等于给定值的记录2、 查找操作的功能是：在查找表中确定一个_等于给定值的记录或数据元素。A: 关键字B: 数据项C: 结点D: 指针4、 静态查找表_。A: 仅能完成查询和检索操作，不能进行插入和删除操作B: 不仅能完成查询和

43、检索操作，也能进行插入和删除操作C: 不能完成查询和检索操作，但能进行插入和删除操作D: 不能完成查询和检索操作，也不能进行插入和删除操作5、 动态查找表_。A: 仅能完成查询和检索操作，不能进行插入和删除操作B: 不仅能完成查询和检索操作，也能进行插入和删除操作C: 不能完成查询和检索操作，但能进行插入和删除操作D: 不能完成查询和检索操作，也不能进行插入和删除操作6、 _的特点是：查找效率与查找对象的规模N无直接关系，而与装填因子、解决冲突的方法有关。A: 链表B: 顺序表C: 索引表D: 散列表7、 哈希表的平均查找长度与_。A: 与装填因子和表的长度有关B: 与装填因子和表的长度都无关

44、C: 与装填因子、解决冲突的方法有关，而与表的长度无关D: 与装填因子、解决冲突的方法无关，而与表的长度有关8、 _需要有解决冲突的方法。A: 顺序查找B: 二分查找C: 散列表查找D: 二叉树查找 9、 顺序查找不适用于单链表。N10、 二分查找不适用于单链表。Y11、 顺序查找要求查找表有序。N12、 二分查找要求查找表有序。Y13、 顺序表既可适用二分查找又可适用顺序查找。Y14、 双链表既可适用二分查找又可适用顺序查找。N表中位置 0 1 2 3 4 5 6 7 8 9 10 关键字k 25 H(k) 3 查找次数 1 15、 设有一组关键字，其出现次序为：25、37、9、35、21、

45、36、45、31。要求用哈希(Hash)方法将存入长度为11个位置的表中。取哈希函数H(k)= k mod 11。试求出各关键字的哈希函数H(k)的值。假定采用步长为1的线性探测再散列法解决冲突(增量序列di=1,2,3,)，写出关键字在表中的位置和相应的查找次数，并求出平均查找长度ASL。表中位置 0 1 2 3 4 5 6 7 8 9 10 关键字k 25 H(k) 3 查找次数 1 平均查找长度ASL=(3+1+1+1+1+3+1+1)/8=1.5 16、 设有一组关键字，其出现次序为：41、23、18、47、30、19、37、5、40。要求用哈希(Hash)方法将存入长度为13个位置的

46、表中。取哈希函数H(k)= k mod 13。试求出各关键字的哈希函数H(k)的值。假定采用二次探测再散列法解决冲突(增量序列di=1,1，22,22,)，写出关键字在表中的位置和相应的查找次数，并求出平均查找长度ASL。 表中位置 0 1 2 3 4 5 6 7 8 9 10 11 12 关键字k 41 H(k) 2 查找次数 1 表中位置 0 1 2 3 4 5 6 7 8 9 10 11 12 关键字k 41 H(k) 2 查找次数 1 平均查找长度ASL=(8*1+4)/9=12/9=1.56 10.1概述10.2插入排序10.3快速排序10.4选择排序10.5归并排序10.6基数排序

47、10.7各种内部排序方法的比较讨论 1、 起泡排序属于_。A: 插入排序B: 交换排序C: 选择排序D: 归并排序2、 快速排序属于_。A: 插入排序B: 交换排序C: 选择排序D: 归并排序3、 堆排序属于_。A: 插入排序B: 交换排序C: 选择排序D: 归并排序4、 _是稳定的。A: 堆排序B: 希尔排序C: 快速排序D: 二路归并排序5、 _是不稳定的。A: 快速排序B: 冒泡排序C: 直接插入排序D: 二路归并排序6、 _需要占用的存储空间相对较大。A: 快速排序B: 直接选择排序C: 直接插入排序D: 二路归并排序7、排序算法的稳定性是指：是否允许出现关键字相同的数据元素。N8、排

48、序算法的稳定性是指：关键字相同的数据对象在排序过程中是否保持前后次序不变。Y9、 内排序是指排序过程全部在内存中进行。Y10、 外排序的排序过程要使用到外部存储器，而不使用内部存储器。N11、 有n个关键字的序列K1,K2,Kn称为小根堆，当且仅当KiK2i 且 _。12、 有n个关键字的序列K1,K2,Kn称为大根堆，当且仅当KiK2i 且 _。13、 顺序查找的平均时间复杂度T(n)为_。14、 二分查找的平均时间复杂度T(n)为_。15、 直接插入排序的空间复杂度S(n)为_。16、 快速排序的时间复杂度T(n)为_。 17、 快速排序的空间复杂度S(n) 为_。18、 直接选择排序的时

49、间复杂度T(n)为_。19、 直接选择排序的空间复杂度S(n) 为_。20、 堆排序的时间复杂度T(n)为_。21、 堆排序的空间复杂度S(n) 为_。22、 二路归并的时间复杂度T(n) 为_。 23、 二路归并的空间复杂度S(n) 为_。24、 冒泡排序的时间复杂度T(n)为_。25、 起泡排序的空间复杂度S(n) 为_。26、 树形选择排序的时间复杂度T(n) 为_。27、 锦标赛排序的时间复杂度T(n) 为_。28、 后序遍历二叉树算法在最坏情况下的空间复杂度S(n)为_（设二叉树的结点数为n）。 已知关键字序列，画出快速排序第一次递归划分后的结果。i r1 r2 r3 r4 r5 r

50、6 r7 r8 57 49 32 86 12 65 57* 28 1 28 49 32 12 57 65 57* 86 2 12 28 32 49 57 57* 65 86 已知关键字序列，画出选择排序前两次排序后的结果i r1 r2 r3 r4 r5 r6 r7 r8 57 49 32 86 57* 65 12 28 1 12 49 32 86 57* 65 57 282 12 28 32 86 57* 65 57 49 .已知关键字序列，画出堆排序第一次的建堆过程i r1 r2 r3 r4 r5 r6 r7 r8 28 49 32 86 12 65 77 511 86 51 77 49 1

51、2 65 32 28已知关键字序列，画出堆排序第二次的建堆过程i r1 r2 r3 r4 r5 r6 r7 r8 28 49 32 86 12 65 77 512 77 51 65 49 12 28 32 86 已知关键字序列，画出链式基数排序的2次分配和收集过程编程题29、 已知某排序基本操作的头文件如下，试写出插入排序函数 InsertSort(SqList &L) 实现的算法。/= 1. 预定义常量和类型/= 2. 定义数据结构/= 2.1 待排序的数据表的存储表示#define MAXSIZE 20/数据表的最大长度typedef struct KeyType key;/关键字Info

52、Type otherinfo;/其他数据项RcdType;/记录类型typedef struct RcdType rMAXSIZE+1;/r0闲置或用作哨兵单元int length;/顺序表长度SqList;/顺序表类型/= 2.2 采用顺序表存储表示的堆typedef SqList HeapType;/= 3. 定义基本操作/= 3.1 插入排序void InsertSort(SqList &L) /直接插入排序int i,j;for(i=2;i=L.length;i+)/=比较if(LT(L.ri.key,L.ri-1.key) L.r0= L.ri;L.ri= _(_)_;/=后移for(j=i-2;LT(L.r0.key,L.rj.key);-j)L.rj+1= _(_)_;/=插入L.rj+1= _(_)_;Output_Data_List1(L,i);/=输出中间结果/InsertSort 30.已知某排序基本操作的头文件，试写出快速排序函数 QSort(SqList &L,int low,int high)实现的算法，可以调用Partition(SqList &L,int low,i