已知以二维数组表示的图的邻接矩阵如下图所示 试分别画

数据结构试卷B(总7页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--试题 B一、填空题（18小题，40个空，每空分，共20分）1、数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。

2、线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。

3、在顺序表中插入或删除一个元素，需要平均移动，具体移动的元素个数与有关。

4、在顺序表中访问任意一结点的时间复杂度均为，因此，顺序表也称为的数据结构。

5、顺序表中逻辑上相邻的元素的物理位置相邻。

单链表中逻辑上相邻的元素的物理位置相邻。

6、若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为。

7、求下列广义表操作的结果：（1） GetHead【((a,b),(c,d))】=== ; //头元素不必加括号（2） GetHead【GetTail【((a,b),(c,d))】】=== ;（3） GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== ;（4） GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== ;8、一棵具有２５７个结点的完全二叉树，它的深度为。

9、设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。

10、图有、等存储结构，遍历图有、等方法。

11、n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为；若采用邻接表存储，该算法的时间复杂度为。

12、用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度的次序来得到最短路径的。

13、假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。

{ if (preEnd < preSt) return NULL; char rt = pre[preSt]; for(int j = midSt; j<=midEnd; j++) if(mid[j] == rt) break; if(j>midEnd){cout<<"Wrong input"; return NULL;} TreeNode root = new binTreeNode( ); root->data = rt; int lLen = j - midSt; root->leftChild = treeRecursive(pre, preSt+1, preSt+lLen - 1,
(1+7+1+1+2+1+4+1+1) / 9 = 19/9
得分
5、 程序设计题。（每小题 15 分，本题满分 30 分）
1. 设计一个算法，根据一棵二叉树的前序序列和中序序列，构造出这棵二叉
树。 二叉树的结点都用字符表示。前序序列和中序序列都是字符串。二叉树的结点定
义如下：
struct binTreeNode {char data; binTreeNode *leftChild, *rightChild; }
考试科目名称
数据结构
得分
1、填空题。（每小题 2 分，本题满分 20 分）
（A1 卷）
(1) C++语言中，数组是按行优先顺序存储的，假设定义了一个二维数组 A[20][30]，每个元
素占两个字节，其起始地址为 2140，则二维பைடு நூலகம்组 A 的最后一个数据元素的地址为

一、概念题（每空0.5分，共45分）1．对于集合这逻辑结构来说，其中的数据元素之间也可以有各种各样的非逻辑关系，但任何一对数据元素之间没有________关系，即没有________关系。

2．查找表按其所包括的运算的不同分为________查找表和________查找表。

3．查找表中主关键字指的是________，次关键字指的是________。

4．静态查找表包括________、________、________三种基本运算。

5．动态查找表包括________、________、________、________、________五种基本运算。

6．假定key为主关键字，若顺序表中第n个元素的键值为K，则顺序查找算法的查找长度为1；若第1个元素的键值为K，则查找长度为________；若表中无键值等于K的元素，则查找长度为________。

7．二分查找在查找成功时的查找长度不超过________，其平均查找长度为________，当n较大时约等于________。

8．静态查找表的三种不同实现各有优缺点。

其中，________查找效率最低但限制最少。

________查找效率最高但限制最强。

而________查找则介于上述二者之间。

9.二叉搜索树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值________于其左孩子（及其子孙）的键值且________于其右孩子（及其子孙）的键值。

10. 在表示一棵二叉搜索树的二叉链表上，要找键值比某结点X的键值________的结点，只需通过结点X的左指针到它的左子树中去找。

11.中序遍历一棵二叉搜索树所得的结点访问序列是键值的________序列。

12.二叉搜索树上的查找长度不仅与________有关，也与二叉搜索树的________有关。

13.在随机情况下，含有n个结点的二叉搜索树的平均查找长度为________，其时间效率很高。

14.折半查找的查找效率与树的形态有关。

(完整)图的邻接矩阵和邻接表相互转换编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（(完整)图的邻接矩阵和邻接表相互转换）的内容能够给您的工作和学习带来便利。

同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。

本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快业绩进步，以下为(完整)图的邻接矩阵和邻接表相互转换的全部内容。

图的邻接矩阵和邻接表相互转换图的邻接矩阵存储方法具有如下几个特征：1)无向图的邻接矩阵一定是一个对称矩阵。

2）对于无向图的邻接矩阵的第i行非零元素的个数正好是第i个顶点的度()i vTD。

3）对于有向图，邻接矩阵的第i行非零元素的个数正好是第i个顶点的出度()i vID)。

4）用邻接OD（或入度()i v矩阵方法存储图,很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测,所发费得时间代价大.邻接表是图的一种顺序存储与链式存储相结合的存储方法。

若无向图中有n个顶点、e条边，则它的邻接表需n个头结点和2e个表结点.显然，在边稀疏的情况下，用邻接表表示图比邻接矩阵存储空间。

在无向图的邻接表中，顶点v的度恰好是第i个链表中的结点数，而在有向图i中，第i个链表中结点个数是顶点v的出度。

i在建立邻接表或邻逆接表时，若输入的顶点信息即为顶点的编号，则建立临接表的时间复杂度是)nO。

在邻(eO+；否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为)(en*接表上容易找到任意一顶点的第一个邻接点和下一个邻接点，但要判断任意两个顶点之间是否有边或弧，则需要搜索第i个或第j个链表，因此，不及邻接矩阵方便。

邻接矩阵和邻接表相互转换程序代码如下：#include〈iostream。

图习题（三）
• 1.如图所示是一个无向网图，请分别按Prim 算法和Kruskal算法求最小生成树。
查找习题（一）
1．已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134）， 当折半查找值为 90 的元 素时，经过（ ）次比较后查找成功。 A2 B3 C4 D5 2．已知 10 个元素（54，28，16，73，62，95，60，26，43），按照依次插入 的方法生成一棵二叉排序树，查找值为 62 的结点所需比较次数为（ ）。 A2 B3 C4 D5 3．已知数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点 的方法生成一棵二叉排序树，则该树的深度为（ ）。 A4 B5 C6 D7 4．按（ ）遍历二叉排序树得到的序列是一个有序序列。 A 前序 B 中序 C 后序 D 层次 5．在散列函数 H(k)= k mod m 中，一般来讲，m 应取（ ）。 A 奇数 B 偶数 C 素数 D 充分大的数
8.设链栈中结点的结构：data为数据域，next为指针域，且top是栈顶指针。若想 在链栈的栈顶插入一个由指针s所指的结点，则应执行下列（ ）操作。 A．s->next=top->next；top->next=s； B．top->next=s； C．s->next=top；top=top->next； D．s->next=top；top=s；
D．根据元素查找
线性表习题（二）
1.链表相对于顺序表的优点是： 插入、删除 方便。 2.顺序表中访问任意一个结点的时间复杂度均为 O(1) 。 3.在单链表中要在已知结点*P之前插入一个新结点，需找到 *P的直接前趋结点的地址，其查找的时间复杂度为 O(n) 。 4.单链表中需知道 头指针 才能遍历整个链表。 5.在一个长度为n的顺序表中删除第i个元素，要移动 n-i 个元 素。 6.在一个长度为n的顺序表中，如果要在第i个元素前插入一 个元素，要后移 n-i+1 个元素。 7.双链表中，设p是指向其中待删除的结点，则需要执行的操 作为： p->prior->next=p->next 。

2024年研究生考试考研计算机学科专业基础(408)复习试题(答案在后面)一、单项选择题（本大题有40小题，每小题2分，共80分）1、下列关于冯·诺依曼体系结构的叙述中，正确的是：A. 计算机由运算器、控制器、存储器、输入设备和输出设备五大部件组成。

B. 指令和数据存放在不同的存储器中。

C. 冯·诺依曼体系结构的计算机硬件系统分为运算器、显示器和键盘三大部分。

D. 程序指令存储在内存中，但数据不能存储在内存中。

2、在计算机内部，数据通常采用哪种形式表示？A. 十进制B. 八进制C. 十六进制D. 二进制3、CPU可以直接访问的存储器是哪一个？A. 软盘B. 硬盘C. 内存D. 光盘4、在计算机网络中，以下哪项不是TCP/IP模型的层次结构之一？A. 网络接口层B. 网络层C. 应用层D. 物理层5、以下哪个算法是用于查找非平衡二叉搜索树中某个特定节点的最坏情况时间复杂度？A. 二分查找B. 中序遍历C. 平衡二叉搜索树查找D. 二叉树遍历6、以下哪个语言是用于实现编译原理的？A. JavaB. C++C. PythonD. Haskell7、在计算机系统中，地址总线的宽度决定了CPU可以直接寻址的内存空间大小。

如果某计算机系统的地址总线宽度为32位，则该CPU的最大直接寻址空间为：A. 4GBB. 8GBC. 16GBD. 32GB8、在数据结构中，队列是一种特殊的线性表，其特点是先进先出（FIFO）。

若在一个初始为空的队列中按照顺序插入元素A、B、C、D，然后执行两次删除操作，再插入元素E、F，接着再次执行两次删除操作，此时队列的队首元素是：A. AB. BC. CD. F9、在关系数据库中，两个表之间的连接是一种生成新表的操作，它将第一个表中的行与第二个表中的行匹配。

如果连接操作没有找到匹配项，则返回NULL。

假设我们有两个表：Table1(A, B)，Table2(C, D)，其中A与C是连接字段。

数据结构与算法张铭课后答案【篇一：第3章栈和队列数据结构张铭复习题】一、填空题（每空1分，共15分）1. 向量、栈和队列都是栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。

不允许插入和删除运算的一端称为栈底。

3.4. 在一个循环队列中，队首指针指向队首元素的位置。

5. 在具有n个单元的循环队列中，队满时共有个元素。

6. 向栈中压入元素的操作是先，后。

7. 从循环队列中删除一个元素时，其操作是先移动队首指针，后。

8. 带表头结点的空循环双向链表的长度等于。

解：head二、判断正误（判断下列概念的正确性，并作出简要的说明。

）（每小题1分，共10分）错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。

错，不一定吧？调用子程序或函数常用，cpu中也用队列。

（√）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（√）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。

错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

（√）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。

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

错，有可能。

三、单项选择题（每小题1分，共20分）（b）1.栈中元素的进出原则是Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出（c）2.若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若p1=n，则pi为Ａ．i Ｂ．n=iＣ．n-i+1 Ｄ．不确定解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，?，n，则出栈的序列是n，?，3，2，1。

第7章 图 自测卷解答 姓名 班级一、单选题（每题1分，共16分） 前两大题全部来自于全国自考参考书！（ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。

A ．1/2 B. 1 C. 2 D. 4 （B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。

A ．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有 条边。

A ．14 B. 28 C. 56 D. 112 （ C ）4. 有8个结点的无向连通图最少有 条边。

A ．5 B. 6 C. 7 D. 8 （ C ）5. 有8个结点的有向完全图有 条边。

A ．14 B. 28 C. 56 D. 112 （B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。

A ．栈 B. 队列C. 树D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。

A ．栈 B. 队列C. 树D. 图 （ ）8. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ D ）9. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是A ． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 3 4 2 5 6 （ ）10. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是A ． 0 2 4 3 6 5 1 B. 0 1 3 6 4 2 5 C. 0 4 2 3 1 5 6 D. 0 1 3 4 2 5 6 （建议：0 1 2 3 4 5 6） （ C ）11. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是A ． 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1 2 3 4 5 6A ．0 2 4 3 1 5 6B. 0 1 3 6 5 4 2C. 0 4 2 3 1 6 5D. 0 3 6 1 5 4 2建议：先画出图，再深度遍历⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡0100011101100001011010110011001000110010011011110（ A ）12. 已知图的邻接表如下所示，根据算法，则从顶点0出发不是深度优先遍历的结点序列是A．0 1 3 2 B. 0 2 3 1C. 0 3 2 1D. 0 1 2 3（A）14. 深度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（D）15. 广度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（A）16. 任何一个无向连通图的最小生成树A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）二、填空题（每空1分，共20分）1. 图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历、广度优先遍历等方法。

2
7、 分析对比 AVL 树和 Hash 的时空特性，并讨论它们的适合场合。(6 分)
第 7 页
时空特性： AVL 树是高度平衡的二叉查找树，查找时间复杂度为 O(logn)，Hash 的查找时间复杂度为 O(1)。 存储开销 Hash 往往比 AVL 树小。 适合场合： Hash 必须处理冲突，而 AVL 树不存在这种问题。对于删除操作，AVL 树的时间开销很稳定，为 O(logn)，而 Hash，如果采用拉链法处理冲突，则删除操作易于实现，如果采用开放定址法，则 删除操作很难实现，因此开放定址法的 Hash 不适合更新频繁的数据存储。另外，AVL 树对数据 的存储是有序的，而 Hash 对数据的存储并不能反映数据之间的大小关系。因此，AVL 树适用于 有序的数据存储，而 Hash 适用于数据量比较大且分布比较均匀，对数据排序无要求的数据存储。
专业
题号 得分
学号
一 二 三
姓名
四 总分
成绩
一、填空题（25%,1~8 题每题 2 分）
（ 装 订 线 内 不 要 答 题 ） 1、 设 W 为一个二维数组，其每个数据元素占用 4 个字节，行下标 i 从 0 到 7 ，列下标 j 从 0 到 3 ，则二维数组 W 的数据元素共占用 个字节。若按行顺序存放二维数组 W，其起 始地址为 100(10 进制)，则二维数组元素 W[6，3]的起始地址为 （10 进制表示） 。 答：128, 208。 2、 后缀算式 9 2 3 + - 10 2 / - 的值为__________。中缀算式（3+4X）-2Y/3 对应的后缀算 式为_______________________________。 答：-1, 3 4 X * + 2 Y * 3 / -。

第7章图自测卷解答姓名班级题号一二三四五总分题分1620241030100得分一、单选题（每题1分，共16分）（C）1.在一个图中，所有顶点的度数之和等于图的边数的倍。

A．1/2B.1C.2D.4（B）2.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。

A．1/2B.1C.2D.4（B）3.有8个结点的无向图最多有条边。

A．14B.28C.56D.112（C）4.有8个结点的无向连通图最少有条边。

A．5B.6C.7D.8（C）5.有8个结点的有向完全图有条边。

A．14B.28C.56D.112（B）6.用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。

A．栈B.队列C.树D.图（A）7.用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。

A．栈B.队列C.树D.图（C）8.已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是01111011001001A．02431561000100B.0136542C.042316511001101011010D.03615420001101建议：01342561100010（D）9.已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是A．0243156B.0135642C.0423165D.0134256（B）10.已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是A．0243651B.0136425C.0423156D.0134256（建议：0123456）（C）11.已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是A．0243165B.0135642C.0123465D.01234561（D）12.已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是A．0132B.0231C.0321D.0123（A）13.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是A．0321B.0123C.0132D.0312（A）14.深度优先遍历类似于二叉树的A．先序遍历B.中序遍历C.后序遍历D.层次遍历（D）15.广度优先遍历类似于二叉树的A．先序遍历B.中序遍历C.后序遍历D.层次遍历（A）16.任何一个无向连通图的最小生成树A．只有一棵B.一棵或多棵C.一定有多棵D.可能不存在（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）二、填空题（每空1分，共20分）1.图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历、广度优先遍历等方法。

《数据结构》单元测试1一、选择题（每题2分，共40分）1．数据的最小单位是（ A）。

(A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量2. 栈和队列的共同特点是( A )。

(A)只允许在端点处插入和删除元素(B)都是先进后出(C)都是先进先出(D)没有共同点3. 用链接方式存储的队列，在进行插入运算时( D )。

(A)仅修改头指针(B)头、尾指针都要修改(C)仅修改尾指针 (D)头、尾指针可能都要修改4. 以下数据结构中哪一个是非线性结构？( D )(A)队列(B)栈(C)线性表(D)二叉树5．函数substr(“DATASTRUCTURE”，5，9)的返回值为（ A ）。

(A) “STRUCTURE”(B) “DATA”(C) “ASTRUCTUR”(D) “DATASTRUCTURE”6．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ D）。

(A) O(log2n) (B) O(1) (C) O(n2) (D) O(n)7．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（ B）。

(A) Nl+N2+……+Nm(B) 1+N2+2N3+3N4+……+(m-1)Nm(C) N2+2N3+3N4+……+(m-1)Nm (D) 2Nl+3N2+……+(m+1)Nm 8．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ B）次。

(A) 25 (B) 10 (C) 7 (D) 19. 二叉树的第k层的结点数最多为( D )。

(A)2k-1 (B) 2K+1 (C) 2K-1 (D)2k-110. 树最适合用来表示( C )。

(A)有序数据元素(B)无序数据元素(C)元素之间具有分支层次关系的数据 (D)元素之间无联系的数据个权构成一棵Huffman树，其节点总数为( A )。

数据结构导论自考题模拟6(总分100,考试时间90分钟)一、单项选择题在每小题列出的四个备选项中只有一个是符合题目要求的1. 能正确地实现预定的功能，满足具体问题的需要是指算法的______A. 正确性B. 易读性C. 健壮性D. 时空性2. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是______A. 单链表B. 仅有头指针的单循环链表C. 双链表D. 仅有尾指针的单循环链表3. 已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为d，则第i个结点的地址为______A. d+(i-1)*mB. d+i*mC. d-i*mD. d+(i+1)*m4. 如果以链表作为栈的存储结构，则退栈操作时______A. 必须判别栈是否满B. 必须判别栈是否空C. 判别栈元素的类型D. 对栈不作任何判别5. 若用一个有6个单元的数组来实现循环队列，rear和front的初值分别为0和3。

则从队列中删除一个元素，再添加两个元素后，rear和front的值分别为______A. 1和5B. 2和4C. 4和2D. 5和16. 根据定义，树的叶子结点的度数______A. 必大于0B. 必等于0C. 必等于1D. 必等于27. 在一棵深度为H的完全二叉树中，所含结点的个数不少于______A.2H-1-1******8. 二叉树若采用二叉链表结构表示，则对于n个结点的二叉树一定有______A. 2n个指针域，其中n个指针为NULLB. 2n个指针域，其中n+1个指针为NULLC. 2n-1个指针域，其中n个指针为NULLD. 2n-1个指针域，其中n+1个指针为NULL9. 下列有关图的遍历的说法中不正确的是______A. 连通图的深度优先搜索是一个递归过程B. 图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C. 非连通图不能用深度优先搜索法D. 图的遍历要求每一结点仅被访问一次10. 判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用______A. 求关键路径的方法B. 求最短路径的Dijkstra方法C. 广度优先遍历方法D. 深度优先遍历方法11. 散列表中由于散列到同一个地址而引起的“堆积”现象，是由______A. 同义词之间发生冲突引起的B. 非同义词之间发生冲突引起的C. 同义词之间或非同义词之间发生冲突引起的D. 散列表“溢出”引起的12. 数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为______A. 索引存储方法B. 顺序存储方法C. 链式存储方法D. 散列存储方法13. 下列说法中不正确的是______A. 无向图的极大连通子图称为连通分量B. 连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C. 连通图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D. 有向图的遍历不可采用广度优先搜索算法14. 一组记录的键值为(46，74，18，53，14，20，40，38，86，65)，利用堆排序的方法建立的初始堆为______A. (14，18，38，46，65，40，20，53，86，74)B. (14，38，18，46，65，20，40，53，86，74)C. (14，18，20，38，40，46，53，65，74，86)D. (14，86，20，38，40，46，53，65，74，18)15. 对序列(22，86，19，49，12，30，65，35，18)进行一趟排序后得到的结果如下：(18，12，19，22，49，30，65，35，86)，则可以认为使用的排序方法是______A. 选择排序B. 冒泡排序C. 快速排序D. 插入排序二、填空题请在每小题的空格中填上正确答案。

第七章 图一、单选题（ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。

A ．1/2 B. 1 C. 2 D. 42. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。

A ．1/2 B. 1 C. 2 D. 4 （B ）3. 有8个结点的无向图最多有 条边。

A ．14 B. 28 C. 56 D. 112 （ A ）一个n 个顶点的连通无向图，其边的个数至少为（ ）。

A ．n-1B ．nC ．n+1D ．nlogn ； （ C ）5. 有8个结点的有向完全图有 条边。

A ．14 B. 28 C. 56 D. 112 （B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。

A ．栈 B. 队列 C. 树 D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。

A ．栈 B. 队列 C. 树 D. 图8. 下面关于求关键路径的说法不正确的是（ C ）。

A ．求关键路径是以拓扑排序为基础的B ．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C ．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D ．关键活动一定位于关键路径上9. 已知图的邻接矩阵如下，根据算法思想，则从顶点0出发，按深度优先遍历的结点序列是（ D ）A ． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 ⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡01000111011000010110101100110010001100100110111101 3 42 5 610、设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>，<4,2>}，则数据结构A是（C ）。

最新国家开放大学电大《数据结构(本)》期末题库及答案考试说明：本人针对该科精心汇总了历年题库及答案，形成一个完整的题库，并且每年都在更新。

该题库对考生的复习、作业和考试起着非常重要的作用，会给您节省大量的时间。

做考题时，利用本文档中的查找工具，把考题中的关键字输到查找工具的查找内容框内，就可迅速查找到该题答案。

本文库还有其他网核及教学考一体化答案，敬请查看。

《数据结构》题库及答案一一、单项选择题（每小题3分，共30分）试题答案及评分标准（供参考）一、单项选择题（每小题3分，共30分）1．C 2．B 3．A 4．C 5．B6．C 7．A 8．D 9．A 10．D二、填空题（每小题2分，共24分）11.先出 12．树形 13．行下标列下标数组元素 14.3 15．存储位置 16. 1017. 20 18．二叉排序树 19.叶20.4 21. 2,4,3;5,6,8,7,9 22. a2《数据结构》题库及答案二一、单项选择题（每小题3分，共30分）二、填空题（每小题2分，共24分）三、综合题【每小题中每问5分，共30分）四、程序填空题（每空2分，共16分）试题答案及评分标准（供参考）一、单项选择题（每小题3分，共30分）1．A 2．D 3．C 4．B 5．B6．C 7．B 8．C 9．A 10.C二、填空题（每小题2分，共24分）11．图状 12. n-j 13．二叉排序树 14. 1,2,4,8,3,5,915. 4 16. 3 17. 5 18. 319. 9 20. 12 21. 32 22. 7《数据结构》题库及答案三一、单项选择题，在括号内填写所选择的标号1．输出一个二维数组b[m][n]中所有元素的时间复杂度为( )。

A．（）(n) B．（）(m十n)C．（）(n2) D．（）(m*n)2．在一个长度为n的顺序存储的有序表中搜索值为x元素时，其时间效率最高的算法的时间复杂度为( )。

3．当利用大小为n的数组顺序存储一个栈时，假定用top= =n表示栈空，则向这个栈插入一个元素时，首先应执行( )语句修改top指针。

数据结构试卷（一）一、单选题（每题 2 分，共20分）1.栈和队列的共同特点是( A )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( D ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( D )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

CA．688 B．678 C．692 D．6965.树最适合用来表示( C )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( D ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( D )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为CA. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ D ）个A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( A )条边才能确保是一个连通图。

A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：正确性易读性强壮性和_高效率。

2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为___0(n)_____。

择：
( A)
A. 利用最小堆存储边
B. 利用栈存储结点
C. 利用二维数组存储结点
D. 利用并查集存储边
(8) 已知一算术表达式的后缀形式为 ABC*+DE/-，其前缀形式为：( D )
A. -A+B*C/DE
B. -A+B*CD/E
C. -+*ABC/DE
D. -+A*BC/DE
(9) n 个关键码排序，如果选用直接插入排序方法，则元素的移动次数在最坏情况下可以达
如果使用别的办法，参考其效率，酌情给分。只要效率过得去，也可以得满分。 但是纯粹枚举则得分不高。
2. 设计非递归算法实现图的深度优先遍历。（图用邻接表表示，已经定义了一个顺序栈 stack[top]，top 为栈顶指针，使用 visit(node)来表示对顶点 node 的访问。） 图的邻接表结构定义如下： struct Edge { int dest; Edge *link; //下一条边链指针 } struct Vertex { int data; Edge *adj; //边链表的头指针 } class Graph { private: Vertex *Nodetable; //顶点表 int cnt ｝
得分
2、选择题。（每小题 2 分，本题满分 20 分）
(1) 如果能够在只知道指针 p 指向链表中任一结点，不知道头指针的情况下，将结点*p 从链
表中删除，则这个链表结构应该是： ( B,C )（多选题）
A. 单链表 B. 循环链表 C. 双向链表 D. 带头结点的单链表
(2) 以下哪种矩阵压缩存储后会失去随机存取的功能?( A )
解： Graph : : DFS(int v)//从 v 开始搜索； {

邻接矩阵法邻接矩阵法是图论中一种常用的表示图结构的方法。

它通过一个二维矩阵来表示图中各个顶点之间的连接关系。

在邻接矩阵中，矩阵的行和列分别代表图中的顶点，而矩阵中的元素则表示对应顶点之间是否存在边。

邻接矩阵的定义假设有一个无向图G=(V,E)，其中V为顶点集合，E为边集合。

邻接矩阵A是一个n×n的方阵，其中n为图中顶点的个数。

邻接矩阵A满足以下条件：•如果顶点i和顶点j之间存在边，则A[i][j]=1；•如果顶点i和顶点j之间不存在边，则A[i][j]=0。

对于有向图来说，邻接矩阵也可以用来表示其连接关系，只是在有向图中，边具有方向性。

邻接矩阵的应用邻接矩阵作为一种常见的图表示方法，在许多算法和应用中都得到了广泛的应用。

下面介绍一些常见的应用场景：1. 图遍历通过邻接矩阵，我们可以方便地遍历图中的顶点和边。

对于一个顶点i，我们只需要遍历邻接矩阵的第i行（或第i列），就可以获取到与该顶点直接相连的所有顶点。

2. 最短路径算法邻接矩阵常被用于求解最短路径问题，例如Dijkstra算法和Floyd-Warshall算法。

在这些算法中，通过邻接矩阵来表示各个顶点之间的距离或权重，然后根据具体的算法逻辑来计算最短路径。

3. 最小生成树邻接矩阵也可以用于求解最小生成树问题，例如Prim算法和Kruskal算法。

在这些算法中，邻接矩阵用来表示图中各个顶点之间的连接关系，并根据具体的算法逻辑选择合适的边来构建最小生成树。

4. 图的连通性判断通过邻接矩阵，我们可以判断一个图是否是连通图。

如果一个无向图的邻接矩阵是对称且连通的，则说明该图是一个连通图。

如果一个有向图的邻接矩阵是强连通的，则说明该有向图是强连通图。

邻接矩阵的优缺点邻接矩阵作为一种图的表示方法，具有以下优点：•表示简单：邻接矩阵直观地表示了图中各个顶点之间的连接关系，易于理解和实现。

•查询高效：通过邻接矩阵，可以快速判断两个顶点之间是否存在边，时间复杂度为O(1)。