下载文档原格式
《数据结构》习题库之三：判断题1. 程序就是算法，但算法不一定是程序。
（）2. 线性表只能采用顺序存储结构或者链式存储结构。
（）3. 线性表的链式存储结构是通过指针来间接反映数据元素之间逻辑关系的。
（）4. 除插入和删除操作外，数组的主要操作还有存取、修改、检索和排序等。
（）5. 稀疏矩阵中0元素的分布有规律，因此可以采用三元组方法进行压缩存储。
（）6. 不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。
（）7. 确定串Ｔ在串Ｓ中首次出现的位置的操作称为串的模式匹配。
（）8. 深度为h的非空二叉树的第i层最多有2i-1 个结点。
（）9. 满二叉树就是完全二叉树。
（）10. 已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。
（）11. 非空二叉排序树的任意一棵子树也是二叉排序树。
（）12. 对一棵二叉排序树进行前序遍历一定可以得到一个按值有序的序列。
（）13. 若有向图G=(V,E)的拓扑序列不唯一，则图中必须有两条弧和。
（）14. 散列表的查找效率主要取决于所选择的散列函数与处理冲突的方法。
（）15. 序列初始为逆序时，泡排序法所进行的元素之间的比较次数最多。
（）16. 算法一定要有输入和输出。
（）17. 算法分析的目的旨在分析算法的效率以求改进算法。
（）18. 非空线性表中任意一个数据元素都有且仅有一个直接后继元素。
（）19. 数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。
（）20. 线性链表中各个链结点之间的地址不一定要连续。
（）21. 若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适。
（）22. 若线性表采用顺序存储结构，每个数据元素占用4个存储单元，第12个数据元素的存储地址为144，则第1个数据元素的存储地址是101。
（）23. 若长度为n的线性表采用顺序存储结构，删除表的第i个元素之前需要移动表中n-i+1个元素。
（）24. 符号link(p)出现在表达式中表示p所指的那个结点的内容。
一、单项选择题（本大题共71小题，每小题2分，共142分）1、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（）。
（）A．{38，46，79，56，40，84}B．{38，79，56，46，40，84}C．{40，38，46，56，79，84}D．{38，46，56，79，40，84}标准答案：C2、广义表（（a）,a）的表头是（）。
（）A．aB．bC．(a)D．((a))标准答案：C3、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是（）。
（）A．80B．100C．240D．270标准答案：C4、在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（）。
（）A．HL=p；p->next=HL；B．p->next=HL；HL=p；C．p->next=HL；p=HL；D．p->next=HL->next；HL->next=p；标准答案：B5、一个具有n个顶点的无向完全图的边数为（）。
（）A．(n+1)/2B．n(n-1)/2C．n(n-1)D．n(n+1)标准答案：B6、如果待排序序列中两个数据元素具有相同的值，在排序后它们的位置发生颠倒，则称该排序是不稳定的。
下列选项中，（）就是不稳定的排序方法。
（）A．起泡排序B．归并排序C．直接插入法排序D．简单选择排序标准答案：D7、按照二叉树的定义，具有3个结点的二叉树有（）种。
（）A．3B．4C．5D．6标准答案：C8、设有1000个元素，用二分法查找时，最大比较次数是（）。
（）A．1B．7C．10D．25标准答案：C9、树适合用来表示（）。
（）A．有序数据元素B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据标准答案：C10、设有两个串p和q，求p在q中首次出现的位置的运算称作（）。
953网络空间安全基础综合考试大纲（研招考试主要考察考生分析问题与解决问题的能力，大纲所列内容为考生需掌握的基本内容，仅供复习参考使用，考试范围不限于此）一、总体要求《953网络空间安全基础综合》要求考生比较系统地掌握网络空间安全相关基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。
二、知识要点数据结构：（一）数据结构基本概念1.数据结构的概念、名词和术语2.数据结构的逻辑结构3.数据结构的物理结构（二）线性表1.线性表的概念和基本运算2.线性表的顺序存储表示及算法3.顺序表的基本运算4.单链表、循环链表、双向链表的基本运算，5.线性表的链式存储表示及算法6.顺序表及链表的应用（三）栈和队列1.栈和队列的基本概念和基本操作2.栈和队列的顺序存储结构3.栈和队列的链式存储结构4.栈和队列的应用（四）串和数组1.串的基本概念和基本操作2.串的存储结构3.模式匹配算法4.数组的概念5.数组的存储结构6.矩阵压缩存储（五）树1.数、二叉树、森林的基本概念2.二叉树的性质和存储表示。
3.二叉树的遍历及递归算法的运用4.树和森林的转换方法5.二叉树的应用（六）图1.图的基本概念、术语2.图的存储方法3.图的遍历4.生成树和最小生成树5.最短路径6.拓扑排序7.关键路径（七）索引结构与散列技术1.索引结构的表示2.索引结构的应用3.散列表的概念4.散列表的构造5.散列表的查找（八）缩小规模算法1.递归与分治算法2.动态规划算法3.掌握贪心算法计算机网络:（一）计算机网络体系结构1.计算机网络概述（1）计算机网络的概念、组成与功能（2）计算机网络的分类（3）计算机网络与互联网的发展历史（4）计算机网络的标准化工作及相关组织2.计算机网络体系结构与参考模型（1）计算机网络分层结构（2）计算机网络协议、接口、服务等概念（3）ISO/OSI参考模型和TCP/IP模型（二）物理层1.通信基础（1）信道、信号、宽带、码元、波特、速率、信道容量等基本概念（2）奈奎斯特定理与香农定理（3）编码与调制、多路复用与扩频（4）电路交换、报文交换与分组交换（5）数据报与虚电路2.传输介质（1）双绞线、同轴电缆、光纤与无线传输介质（2）物理层接口的特性3.物理层设备（1）中继器（2）集线器（三）数据链路层1.数据链路层的功能2.组帧3.差错控制（1）检错编码（2）纠错编码4.流量控制与可靠传输机制（1）流量控制、可靠传输与滑轮窗口机制（2）停止-等待协议（3）后退N帧协议（4）选择重传协议5.典型数据链路层协议（1）HDLC协议（2）PPP协议（3）ADSL协议6.介质访问控制（1）信道划分介质访问控制频分多路复用、时分多路复用、码分多路复用的概念和基本原理。
数据逻辑的三要素
数据结构的三要素是：逻辑结构，物理结构，数据的运算。
逻辑结构：
分为线性结构个非线性结构。
线性结构就是有一一对应的关系的，如A-B-C，这三个字母就符合线性结构。
非线性结构就是集合，树，图。
集合就是一些元素共同归位一类，如自然数集合；树就是有层次关系结构，如家族谱系树；图就是每个元素之间会有联系，如一座城市的地铁图。
物理结构：
也就是元素如何存储的，即存储结构。
又分为顺序结构，链式结构，索引结构，散列结构。
这四种结构各有优缺点：顺序虽然可以实现直接存取，但是对于空间的利用不充分；链式虽然很好利用了空间，但是得到元素只能顺序存取，这样很不方便，并且还要有额外的空间给指针；索引虽然是结合了上面两种的优缺点，但额外的索引表增加了内存损耗；散列结构不可避免会有冲突的危险。
数据运算：
运算包括定义和实现。
运算的定义是针对逻辑结构的，运算的实现是针对存储结构的。
数据结构试题一、单选题1、在数据结构的讨论中把数据结构从逻辑上分为（C ）A 内部结构与外部结构B 静态结构与动态结构C 线性结构与非线性结构D 紧凑结构与非紧凑结构。
2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ）A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。
A nB n/2C (n-1)/2D (n+1)/24、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。
A s→link = p→link;p→link = s;B p→link = s; s→link = q;C p→link = s→link;s→link = p;D q→link = s;s→link = p;5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。
A 起泡排序B 堆排序C 锦标赛排序D 快速排序6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。
A 求子串B 模式匹配C 串替换D 串连接7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。
所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ C ）。
A 80B 100C 240D 2708、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。
A 栈B 队列C 循环队列D 优先队列9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。
10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。
A ( front - rear + 1) % mB ( rear - front + 1) % mC ( front - rear + m) % mD ( rear - front + m) % m11、一个数组元素a[i]与（ A ）的表示等价。
顺序存储结构、链式存储结构、索引存储结构、散列存储结构介绍存储结构是指数据在计算机内存或磁盘等存储介质中的组织方式。
在数据结构中，常见的存储结构有顺序存储结构、链式存储结构、索引存储结构和散列存储结构。
下面将分别对这四种存储结构进行详细介绍。
一、顺序存储结构（Sequential Storage Structure）：顺序存储结构是将数据元素按照其逻辑次序依次存储在一片连续的存储空间中，即在内存或磁盘上连续存放数据元素。
数据元素之间的逻辑关系通过其在存储空间中的物理位置来表示。
特点：顺序存储结构的存取速度较快，可以通过下标直接访问元素。
插入和删除操作需要移动大量元素，效率较低。
适用于元素数量固定、随机访问频繁的场景，如数组。
二、链式存储结构（Linked Storage Structure）：链式存储结构通过使用指针将数据元素存储在不连续的存储空间中，并通过指针将它们连接起来。
每个数据元素中都包含一个指向下一个元素的指针，从而构成了一个链表结构。
特点：链式存储结构的插入和删除操作效率较高，只需要修改指针的指向。
访问某个元素需要从头节点开始遍历，效率较低。
适用于元素数量不固定、插入和删除频繁的场景，如链表。
三、索引存储结构（Indexed Storage Structure）：索引存储结构是在顺序存储结构的基础上，为数据元素建立一个索引表，该索引表中的每个索引项包含了一个关键字和对应数据元素在存储空间中的地址。
特点：索引存储结构可以通过索引表快速定位数据元素，减少了遍历的时间。
插入和删除操作需要同时修改索引表和存储空间，效率相对较低。
适用于大型数据库等场景，可以提高查询效率。
四、散列存储结构（Hash Storage Structure）：散列存储结构是通过将数据元素的关键字映射到一个散列地址来进行存储和访问的。
具体的映射函数称为散列函数，它将关键字转换为一个固定长度的散列地址。
特点：散列存储结构可以快速定位数据元素，查找效率高。
顺序存储结构、链式存储结构、索引存储结构、散列存储结构顺序存储结构：顺序存储结构是一种将数据元素依次存放在一块连续的存储空间中的存储方式。
在顺序存储结构中，每个数据元素都占用一个连续的存储单元，而且数据元素之间的逻辑关系与物理位置相对应。
顺序存储结构适用于插入和删除操作较少、查找操作频繁的场景。
顺序存储结构的主要优点是存取元素的速度快、空间利用率高，但是它无法很好地应对元素的插入和删除操作。
当需要在顺序存储结构中插入和删除元素时，需要移动大量的数据元素，因此时间复杂度较高。
另外，顺序存储结构的存储空间需要在初始化时就确定，不能动态扩展，这对于元素数量不确定的情况下有一定的限制。
链式存储结构：链式存储结构是一种将数据元素存储在任意的存储单元中，并通过指针来表示它们之间关系的存储方式。
链式存储结构中的每个存储单元都包含两部分，一部分是实际的数据元素，另一部分是指向下一个存储单元的指针。
链式存储结构适用于插入和删除操作频繁、查找操作较少的场景。
链式存储结构的主要优点是插入和删除操作的时间复杂度为O(1)，只需要修改指针的指向就可以完成操作。
同时，链式存储结构的容量可以动态扩展，不受存储空间的限制。
然而，链式存储结构对于查找操作的时间复杂度为O(n)，需要遍历整个链表才能找到目标元素。
此外，链式存储结构需要额外的存储空间来存储指针，会占用较多的内存空间。
索引存储结构：索引存储结构是一种通过建立索引来提高查找效率的存储方式。
在索引存储结构中，除了存储数据元素外，还会建立一个索引表，索引表中包含了数据元素的关键字和相应的指针。
通过查找索引表，可以快速定位到目标数据元素的存储位置，从而提高查找效率。
索引存储结构适用于查找操作频繁、插入和删除操作较少的场景。
索引存储结构的主要优点是在查找操作时的时间复杂度为O(logn)，比顺序存储结构和链式存储结构的O(n)要小。
同时，在插入和删除操作时，索引存储结构只需调整索引表和指针的指向，操作效率较高。
“数据结构”期末考试试题一、单选题（每小题2分,共12分)1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点,则执行( )。
A． HL＝ps p一〉next＝HLB． p一>next＝HL；HL＝p3C． p一>next＝Hl;p＝HL；D． p一〉next＝HL一>next;HL一〉next＝p；2．n个顶点的强连通图中至少含有( ）。
A。
n—l条有向边 B.n条有向边C.n(n-1)／2条有向边 D。
n（n一1）条有向边3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( ）。
A。
O（1) B.O（n)C.O（1Ogzn)D.O（n2）4．由权值分别为3，8,6,2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( ）。
A．24 B．48C． 72 D． 535．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为（ )参数，以节省参数值的传输时间和存储参数的空间。
A。
整形 B。
引用型C。
指针型 D。
常值引用型·6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为（）。
A．O(n） B．O(1)C．O（n2） D．O(10g2n）二、填空题（每空1分，共28分）1．数据的存储结构被分为——、——、——和-—四种.2．在广义表的存储结构中,单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。
3．—-中缀表达式 3十x*(2.4／5—6）所对应的后缀表达式为—-——。
4．在一棵高度为h的3叉树中,最多含有—-结点。
5．假定一棵二叉树的结点数为18,则它的最小深度为-—，最大深度为——·6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定-—该结点的值，右子树上所有结点的值一定-—该结点的值。
7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层—-调整,直到被调整到——位置为止。
数据的四种基本存储结构是指数据的四种基本存储结构是指顺序结构、链式结构、索引结构和散列结构。
这四种存储结构在数据存储和检索中起着重要的作用，下面将对它们进行详细介绍。
首先是顺序结构，顾名思义，顺序结构是将数据按照一定的顺序存储在连续的存储单元中。
这种结构的优点是存取速度快，适合于对数据频繁进行查找和遍历的场景。
比如，在一个有序数组中查找特定的元素，可以使用二分查找算法，时间复杂度为O(logn)，效率非常高。
但顺序结构的缺点是插入和删除操作比较耗时，需要移动大量的数据。
接下来是链式结构，链式结构是通过节点之间的指针链接来实现数据的存储和访问。
每个节点包含数据和指向下一个节点的指针。
链式结构的优点是插入和删除操作方便快捷，只需修改指针的指向即可。
而查找操作则需要从头节点开始依次遍历，时间复杂度为O(n)。
链式结构适用于频繁进行插入和删除操作的场景，比如链表、树等数据结构。
第三种存储结构是索引结构，索引结构是通过建立索引表来加快数据的检索速度。
索引表包含关键字和指向实际数据的指针。
通过在索引表中进行查找，可以快速定位到实际数据所在的位置。
索引结构的优点是检索速度快，适用于对大量数据进行频繁检索的场景。
常见的索引结构有B树、B+树等。
例如，在数据库中创建索引可以大大提高查询性能。
最后是散列结构，散列结构是根据关键字直接计算出数据所在的位置，而无需进行比较和遍历。
散列结构通过散列函数将关键字映射到存储位置，这个存储位置称为散列地址。
散列结构的优点是存取速度快，适用于对数据进行快速查找的场景。
然而，散列结构的缺点是可能会存在散列冲突，即不同的关键字映射到相同的散列地址，需要采取冲突解决方法，如链地址法、开放地址法等。
散列结构在哈希表、哈希函数等方面有广泛应用。
数据的四种基本存储结构分别是顺序结构、链式结构、索引结构和散列结构。
它们各自适用于不同的场景和需求，选择合适的存储结构可以提高数据存储和检索的效率。
