郑大远程数据结构习题

1、.第一章第一题、单项选择题（每题1分， 5道题共 5分）1、在计算机中 , 数据的基本单位是ba、数据b、数据元素c、数据项d、数据结构2、网状数据结构中数据元素之间的对应关系是ca、1:1b、1:nc、m:nd、n:13、一个算法的实现取决于选定的ba、逻辑结构b、存储结构c、时间复杂度d、空间复杂度4、在数据结构的讨论中, 可把数据结构从逻辑上分为 da、静态结构与动态结构b、内部结构与外部结构c、紧凑结构与非紧凑结构d、线性结构与非线性结构5、算法的效率一般用什么来度量aa、时间复杂度b、空间复杂度c、执行的时间d、占用的空间第二题、多项选择题（每题2分， 5道题共 10分）1、数据结构

2、一般有以下几种类型abcda、集合b、线性结构c、树形结构d、图形结构2 、算法的重要特征有abcda、有穷性b、确定性c、可行性d、有输出3 、下列哪写是数据结构的基本操作abcda、插入b、删除c、查找d、修改4 、对于 c 语言而言 , 下列哪些是基本数据类型abcda、整型b、实型c、字符型d、布尔型e、结构体类型5 、非线性结构主要是指acda、集合b、表c、树形结构.d、图形结构第三题、判断题（每题1分， 5道题共 5分）1 、数据是信息的载体, 是对客观事物的符号表示对正确错误2 、数据结构是相互之间存在一种或多种特定关系的数据元素的集合对正确错误3、存储结构是数据结构在计算机中

3、的表示, 也称为数据的物理结构 .对正确错误4、树形结构中的数据元素之间存在一个对一个的关系错正确错误5、图形结构中的元素存在多个对多个的关系. 对正确错误第二章第一题、单项选择题（每题1分， 5道题共 5分）1 、对于一个长度为n 的顺序存储的线性表，在表尾插入元素的时间复杂度为ca、o(n)b、o(n*n)c、o(1)d、o(0)2 、在一个长度为n 的顺序存储的线性表中，删除第i 个元素（ 1i n）时，需要从前向后依次前移几个元素。 aa、n-ib、n-i+1c、n-i-1d、i3 、采用链式结构表示一个线性表时, 要求占用的存储空间地址da、必须是连续的b、部分地址必须是连续的c、一

4、定是不连续的d、可连续可不连续4 、设顺序表第一个元素x 的存储地址loc(x) 为基地址 , 则第 i 个元素 y 的存储地址为aa、loc(x)+(i-1)*l,其中 l为每个元素的大 b、 loc(x)+i*l,其中 l 为每个元素的大小小c、loc(x)+(i+1)*l,其中 l为每个元素的大其中 l 为每个元素的大小小d、 (i-1)*l,5 、单链表插入操作的平均时间复杂度为ba、o(1)b、o(n)c、o(n*n)d、o(n*n*n)第二题、多项选择题（每题2分， 5道题共 10分）1 、在顺序表中删除一个元素的步骤主要有没找到正确答案a、检查线性表是否为空b、检查删除位置是否合

5、法c、使表长减 1d、删除成功 , 返回一个表示成功的值2 、顺序表的特点有abcda、存储结构简单.b、易于实现c、节省空间d、可随机存储3 、单链表的节点一般应包括aba、数据域b、指针域c、节点域d、存储域4 、线性表用链式结构来实现, 可有哪些形式abcda、单链表b、双链表c、循环链表d、双向循环链表5 、下列哪些是线性表的常用操作abcda、插入b、删除c、查找d、判断是否为空第三题、判断题（每题1分， 5道题共 5分）1、对于线性表 l, 当元素个数为0时 , 一般称为空表对正确错误2、在线性表中插入一个元素后, 线性表的长度比插入前增加 1对正确错误3、线性表就是指顺序表错正确

6、错误4、在线性链表中插入一个元素是不会出现无法插入的情况的错正确错误5、单链表中的各个元素如果不存储在连续的空间内, 那么从本质上来看它就不是线性结构错正确错误第三章第一题、单项选择题（每题1分， 5道题共 5分）1、在队列中 , 允许删除元素的一端称为aa、队首b、队尾c、入队d、出队2、一个栈的入栈序列为a1,a2,a3,a4,a5,则此栈不可能的输出序列是 ca、a5,a4,a3,a2,a1b、a4,a5,a3,a2,a1c、a4,a3,a5,a1,a2d、a1,a2,a3,a4,a53、在一个链队列中，假设f 和 r 分别为队首和队尾指针，删除一个结点的运算是ca、r f - next

7、b、r r - nextc、f f - nextd、f r - next4、在一个具有 n 个单元的顺序栈中，假设栈底是存储地址的低端，现在我们以top 作为栈顶指针，则作退栈操作时， top 的变化是a.a、top top -1 ;b、top top +1 ;c、top不变d、top不确定5 、假溢出现象只会出现在哪种数据结构中da、顺序表b、链表c、栈d、队列第二题、多项选择题（每题2分， 5道题共 10分）1 、栈的常用操作有abcda、入栈b、出栈c、取栈顶元素d、清空栈2 、栈的实现方式主要有aba、顺序方式b、链式方式c、循环方式d、递归方式3 、一个栈的入栈序列为a1,a2,a3

8、,a4,a5,则此栈可能的输出序列是aba、a1,a2,a3,a4,a5b、a5,a4,a3,a2,a1c、a1,a5,a3,a4,a2d、a5,a1,a2,a3,a44 、队列的常用操作有abca、入队b、出队c、取队首元素d、取队尾元素5 、队列的实现方式主要有aba、顺序方式b、链式方式c、循环方式d、递归方式第三题、判断题（每题 1分， 5道题共 5分）1、向栈顶插入一个元素的操作叫入栈对正确错误2、由于顺序栈占用连续的存储空间, 所以可以随机存取栈中的元素错正确错误3、由于队列元素的操作具有 先进先出 的特征 , 因此队列又称为先进先出表对正确错误4、在队列中允许删除的一端称为队首对

9、正确错误5、队列只能用顺序方式来实现错正确错误.第四章第一题、单项选择题（每题1分， 5道题共 5分）1、设串 s1 abcdefg,s2pqrst,函数 con(x,y)返回 x 和 y 串的连接串， subs(s,i,j)返回串 s 的从序号 i 的字符开始的j 个字符组成的字符， len(s) 返回串 s 的长度，则 con(subs(s1,2,len(s2),subs(s1,len(s2),2) 的结果串是da、bcdefb、bcdefgc、bcpqrstd、bcdefef2、空格串的长度为da、0b、1c、大于 1d、大于等于 13、设 s1 good， s2 -,s3 bye！ ，

10、则 s1 、s2和 s3连接后的结果是aa、good-bye！b、goodbye！ c、good bye！d、goodbye4、数组 a 中，每个元素 a 的长度为 3个字节，行下标i 从 1到 8，列下标 j从1到 10 ，从首地址 sa 开始连续存放在存储器内，该数组按行存放时，元素a85的起使地址为 ca、sa+141b、sa+180c、sa+222d、sa+2255、稀疏矩阵一般的压缩存储方法有两种，即ca、二维数组和三维数组b、三元组和散列c、三元组和十字链表d、散列和十字链表第二题、多项选择题（每题2分， 5道题共 10分）1 、在一般的程序设计语言中, 串中的元素可以是abcda

11、、字母b、阿拉伯数字c、一些特殊符号d、汉字2 、下列说法正确的是abcda、数组也是一种线性数据结构b、一维数组从本质上看就是线性表c、二维数组是数据元素为一维数组的线性表d、数组是由值与下标组成的数偶的有序集合3 、常见的特殊矩阵有abca、对称矩阵b、三角矩阵c、对角矩阵d、二维矩阵4 、稀疏矩阵的存储方法一般有aba、三元组表法b、十字链表法c、循环链表法d、堆方法5 、串的基本操作包括abcdea、连接.b、求串长c、串比较d、子串定位e、串复制第三题、判断题（每题1分， 5道题共 5分）1、长度为零的串称为空串对正确错误2、串中任意个连续的字符组成的子序列称为该串的子串对正确错误3

12、、串既可以用顺序方式表示, 也可以用链式方式表示对正确错误4、数组的存储结构一般都采用顺序存储结构对正确错误5、 c 语言中 , 数组的实现采用列优先的存储方式错正确错误第五章第一题、单项选择题（每题1分， 5道题共 5分）1、在一棵二叉树中，度为零的结点的个数为n0，度为 2的结点的个数为n2，则有 n0 ba、n2b、n2+1c、n2-1d、n2+22、现有按中序遍历二叉树的结果为abc，问有几种不同形态的二叉树可以得到这一遍历结果da、2b、3c、4d、53、带权路经长度最小的树称为ca、满二叉树b、完全二叉树c、哈夫曼树d、线索二叉树4、若用 10,6,20,23,8,1,5做为权值

13、, 构造一棵哈夫曼树 , 该树的深度为ba、4b、5c、6d、75、将一棵树转换为一个二叉树后, 该二叉树必定 ba、没有左子树b、没有右子树c、所有的节点都没有左子树d、所有的节点都没有右子树第二题、多项选择题（每题2分， 5道题共 10分）1、二叉树的遍历方法有abcda、前序法b、中序法c、后序法d、层次遍历法2 、树的逻辑结构表示法有abcda、树形表示法b、文氏图表示法.c、凹入表示法d、括号表示法3 、二叉树的基本操作主要有abcda、遍历b、求二叉树的深度c、求某个节点的左子女d、求某个节点的左子女4 、二叉树的实现方法主要有aba、顺序方式b、链式方式c、循环方式d、递归方式5

14、 、树的实现方式主要有aba、顺序方式b、链式方式c、循环方式d、递归方式第三题、判断题（每题1分， 5道题共 5分）1、由树转换成二叉树，其根结点的右子树总是空的对正确错误2、后根遍历树和中序遍历与该树对应的二叉树，其结果不同错正确错误3、后序遍历森林和中序遍历与该森林对应的二叉树，其结果不同错正确错误4、用二叉树的前序遍历和中序遍历可以导出二叉树的后序遍历对正确错误5、在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点错正确错误第六章第一题、单项选择题（每题1分， 5道题共 5分）1、具有 6个顶点的无向图至少应有条边才能确保是一个连通图aa、5b、6c、7d、82、对

15、于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是da、nb、(n-1)*(n-1)c、n-1d、n*n3、采用邻接表存储的图的深度优先遍历算法类似于二叉树的aa、先序遍历b、中序遍历c、后序遍历d、按层遍历4、关键路径是事件结点网络中aa、从源点到汇点的最长路径b、从源点到汇点的最短路径c、最长的回路d、最短的回路.5 、一个图中包含有k 个连通分量，若按深度优先搜索的方法访问所有结点，则必须调用次深度优先算法aa、kb、1c、k-1d、k+1第二题、多项选择题（每题2分， 5道题共 10分）1 、完全图包括aba、无向完全图b、有向完全图c、连通图d、完全连通图2 、图的

16、常用存储方法有bca、散列方法b、邻接矩阵法c、邻接表法d、顺序方法3 、图的遍历方法有aba、深度优先方法b、广度优先方法c、先根方法d、后根方法4 、拓扑排序的主要步骤有abca、在 aov网中 , 选一个没有后继的节点, 并输出b、在网中删去该顶点, 并删去所有指向该顶点的弧c、重复上述两步, 直到网中不再有出度为0的顶点为止d、删除网中的回路5 、常用的最小生成树算法有aba、普里姆算法b、克鲁斯卡尔算法c、哈夫曼算法d、拓扑算法第三题、判断题（每题1分， 5道题共 5分）1、在 n 个结点的无向图中，若边数大于n-1，则该图必是连通图错正确错误2、任何 aov网的拓扑序列都是唯一的错

17、正确错误3、邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图错正确错误4、无向图的邻接矩阵是对称的，因此可只存储邻接矩阵的下（或上）三角阵对正确错误5、强连通分量是有向图中的极大强连通子图对正确错误第七章.aadab对错对对错第一题、单项选择题（每题1分， 5道题共 5分）1 、如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用查找方法aa、分块b、顺序c、二分d、散列2 、一个有序顺序表有255个元素，采用顺序查找法查找，查找长度为aa、128b、127c、126d、2553 、在散列函数h（key ） key p 中， p 一般取 da、大于 1000的数b、小于

18、 1000的数c、随机数d、素数4 、对于二叉排序树的查找，若根结点元素的键值大于被查找元素的键值，则应该在二叉树的上继续查找 aa、左子树b、右子树c、左右两棵子树d、根接点5 、在一棵二叉排序树上实施遍历后，其关键字序列是一个有序表ba、先序b、中序c、后序d、深度第二题、多项选择题（每题2分， 5道题共 10分）1 、根据对查找表中的数据所执行的操作, 可将查找表分为aba、静态查找表b、动态查找表c、树表d、链表2 、下列哪些是哈希函数的构造方法abcda、直接地址法b、除留余数法c、平方取中法d、折叠法3 、下面哪些是处理冲突的方法aba、开发地址法b、链地址法c、索引法d、二分法4

19、 、哈希表的缺点主要有abca、根据哈希函数计算关键字的地址的过程占用一定的计算时间b、占用的存储空间多c、在哈希表中只能按关键字查找d、不能进行删除操作5 、开发地址法可进一步分为aba、线性探测法.b、二次探测法c、随机探测法d、链地址法第三题、判断题（每题 1分， 5道题共 5分）1、哈希表的查找效率主要取决于哈希表建立时选取的哈希函数和处理冲突的方法对正确错误2、直接定址法构造的哈希函数会发生冲突错正确错误3、折半查找是一种在有序表上进行查找的方法对正确错误4、由二叉排序树的定义可知 , 中序遍历二叉树所得到的序列是非递减有序的对正确错误5、从哈希表中删除一个数据元素时是不需要使用哈希

20、函数的错正确错误第八章第一题、单项选择题（每题1分， 5道题共 5分）1 、一组记录的排序码为46 ，79，56，38，40，84 ，则利用堆排序的方法建立的初始堆为ba、79，46，56，38，40，84b、84,79 ， 56， 38， 40， 46c、84,79 ，56，46，40，38d、84，56，79，40，46，382 、排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为 da、希尔排序b、归并排序c、插入排序d、选择排序3 、一组记录的排序码为 25 ， 48， 16， 35，79，82，23，40，36，72 ，其中含有 5个长度为 2的有序表，按归并排序的方法对该序列进行一次归并后的结果为aa、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