数据结构总复习题(da-an)

1、数据结构总审查问题一、填空1.数据结构研究数据的_ _逻辑结构_和_物理结构，定义这些结构中的相关运算，设计实现这些运算的算法，并分析算法的效率。算法的效率由两个方面组成：_ _ _时间复杂性_ _和_ _空间复杂性_ _ _ _时间和空间。学号2.数据的默认单位是_ _数据元素，数据的最小单位是_ _数据项。3.算法是特定故障诊断_ _ _ _步骤_ _ _ _ _的说明，是说明的有限序列。4.算法的时间复杂性为(3n3 2n-7)，其数量表示为O(n3)。5.算法有五个特性：确定性、可行性、贫困、输入和输出。6.算法的性能分析和测量可以评估算法在时间复杂性和空间复杂性方面的优缺点。学号7.

2、数据的逻辑结构有四种类型：集合结构、线性结构、树结构和图形结构。8.数学模型(例如交通、道路问题)通常是称为图形结构的数据结构。9.计算机可以使用两种存储方法-_ _ _序列存储为物理结构，称为数据_ _ _序列存储_ _ _或_链存储_ _。10.折线图有两种存储结构：顺序存储和链存储。11.链式存储的特点是使用指针表示数据元素之间的逻辑关系。名字12.如果经常插入和删除线性表，则线性表必须使用_链存储_ _ _ _存储结构。13.行表中的数据元素之间存在一对一的线性关系，除第一个元素和最后一个元素外，其他数据元素只有直接后继者和直接后继者。14.顺序表格中逻辑相邻元素的物理位置_也相邻_

3、_ _ _ _ _。15.在单个链接列表l中，指针p是具有后续节点的节点的条件是_p-next！=NULL_ _。16.在按顺序存储的线性表中，插入或删除一个元素的平均移动表_50%_(或一半)_中的元素。17.如果在单个列表中p指向的节点后插入s指向的节点，则必须执行s-next=_p-next_和p-next=_s_中的操作。18.如果从单个链接列表中删除p的后续节点q，则必须执行p-next=q-next。19.针对前导节点head的单个链接列表，验证为null的条件是否为head-next=NULL。20.为进退刀节点head的循环单链接尾部节点(指向p)指定非空条件p-next=he

4、ad。21.堆栈结构允许插入的一端称为堆栈顶部。队列结构允许插入的一端称为队列尾部。22.堆栈是特殊的线性表，可以在表的一端插入和删除_，堆栈中元素的出入策略是_ _ FIFO _ _。23.入队和出队队列中的元素遵循_ FIFO _ _ _ _原理，在数据元素1，2，3，4，5按顺序入队后遵循_ 1 _ _ _ _。24.在循环队列中，存储空间为0-n-1。如果将队列头指针front设置为指向队列头元素前面的空闲元素，将页脚指针设置为指向队列尾元素，则相应的组空标志为rear=front，组范围标志为(rear 1)% n=front。25.假定顺序队列的对标题和后缀分别为f和r，确定队列为

5、空的条件是_ f=r _ _ _ _ _。26.顺序表由19个元素组成，第一个元素的地址为200，每个元素占用3个字节，则第14个元素的存储地址为239。27.要从长度为n的顺序表中删除第I元素(1In)，必须向前移动n-i元素。28.在长度为n的顺序表中，如果要在I元素之前插入(1In)元素，则必须向后移动n-i 1元素。29.线性表使用最大长度为1000、每个数据元素占用3个存储设备的顺序存储结构时，如果第一个数据元素的存储地址为2000，则第11个元素的存储地址为_ _ _ _ _ _ _ _ _ 2030 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _30.二维

6、阵列可以通过两种方式保存：第一个按_ _ _ _行_ _主顺序保存，第二个按_ _ _列_ _主顺序保存。现有二维阵列A67，以第一种方式存储，A00的存储地址为1000，并且每个元素占用5个字节，则元素A35的存储地址为_1115_ _ _。1000 (3*7 5)*531.有二维阵列A54，按行顺序优先存储，A00的存储地址为10，并且每个阵列元素占用两个字节，则A32的存储地址为_128(10 (3*4)32.如果现有二维阵列A68按动作主顺序存储，则A00的存储地址为2000，并且每个元素占用两个字节，则元素A35的存储地址为_ _ _ 2046 _。如果列按主要顺序存储，则元素A35

7、的存储地址为_ 2086。33.如果两个字符串相同，则对应于_和_的字符(如：_系列的外观)为_ _ _ _ _。34.不带字符的字符串称为零长度空字符串。35.对于稀疏矩阵的压缩存储，一组三元，通常表示有关非零元素的信息，其中包含具有非零元素的行、列及其值。36.如果二进制树包含20个叶节点，则该二进制树包含19个度为2的节点。37.如果二进制树具有15个中间点，则二进制树具有_ _ _ 16 _ _ _ _ _个叶节点。38.深度为h且包含_ _ _ 2 h-1 _ _节点的二进制树称为完整的二进制树。39.深度为k的二进制树最多包含2 k-1个节点，最少包含k个节点，层I最多包含_ _

8、_ 2 (I-1) _ _个节点。深度为5的整个二进制树共有31个节点，并具有_ _ 16 _ _叶节点。41.如果深度为6的完整二进制树的第6层包含3个叶节点，则此二进制树总共包含34个节点。42.深度为15的整个二叉树，第11层有1024个节点。43.具有100个深度为7的节点的完整二叉树。其中度为1的节点为1。44.如果二进制树的最后一个根遍历序列是Abd，中间根遍历序列是ADB，则第一个根遍历序列是dab。45.Huffman树是具有最小权重路径长度的二进制树，为具有确定权重的一组叶节点配置。46.具有m个叶节点的huff man树包含2m-1个节点。47.据悉，霍夫曼树有60片叶子，

9、这棵树有59个不是叶子的节点。48.仅半树，由5个叶节点组成，权重为9，2，3，5，14。此树的权重路径长度是_67_。49.具有n(n-1)/2个角的n个顶点的完整插图。在具有n个顶点的完整插图中，有n(n-1)边。具有4个顶点的全向图有6条边。50.在直接图形中，一个节点的度表示该节点的_ _度_ _和_ _度_ _之和。51.具有n个顶点的连接图形需要至少n-1个边。52.连通图的生成树是图的最小连通子图。如果此连接图中有n个顶点，则结果树中有n-1个边。53.在具有直接布线图的相邻矩阵中，I行中非零元素的数量正好是第I顶点的出图。在I列中，非零元素的数量正好是第I个顶点的入口度。54.

10、在一幅图中，所有顶点的度数之和等于所有变量的两倍。55.在无向图g的相邻矩阵a中，如果a I j为1，则a j I等于1。56.如果连接图g具有n个顶点，则g的跨度树必须具有n-1个面。57.具有拓扑排序的直接图形不能有环(循环)。拓扑排序顺序中的第一个顶点必须是粒度为零的顶点。58.Dijkstra算法是按照路径长度增加的顺序生成从一个顶点到其他顶点的最短路径的算法。59.通过按中间顺序遍历二进制排序树，可以从最小关键字到最大关键字得到节点序列。60.排序后的表是1，3，9，12，32，41，45，62，75，77，82，95，100，在4次比较后成功查找半净额搜索值为82的节点。61.使用

11、直线表中的半查找方法查找数据元素。在线表中，元素必须按值顺序排序，_ _存储方法必须按_顺序存储。62.如果键码序列为(18，25，63，50，42，32，9)，则散列函数为H(key)=key MOD 9，与18冲突的元素为_ _ _ 2 _ _ _ _ _。63.在查找线表格的半截断中，线表格的存储结构必须是_连续的_ _ _ _，表格的元素必须是_ _有序的_ _ _ _。64.在以下四种排序方法中，排序方法为_合并排序_:简单选择排序、堆排序、快速排序、合并排序。65.冒泡排序是稳定的排序方法，在n个元素的序列冒泡时按顺序排序，最多n-1次。排序方法的时间复杂度为O(n2)。66.给定

12、序列100，86，48，73，35，39，42，57，66，21无疑是堆中定义的大堆。67.对于快速排序，平均时间复杂性为_O(nlog2 n)，最常用的时间复杂性为_O(n2)_。68.数据结构是指数据及其相互之间的_ _ _ _一个或多个关系_ _ _ _ _。如果节点之间有m-n (m: n)连接，则此结构称为_ _ _ _图形结构_ _ _ _ _。69.队列的插入操作在队列的_ _ _ _ _ _ _团队结束_ _ _ _中执行，删除操作在队列的_ _团队头_ _ _中执行。70.从无序表格中依次获取元素(一次一个)，并将它们插入有序表格中的适当位置。此排序方法称为_ _ _直接插入

13、_ _ _排序。每次从未排序的表中选择最小或最大元素时，将其交换为称为_ _ _简单选择_ _ _排序的已排序表的一端。71.二进制树的上一遍历序列为a、b、c、e、f、d、g、h，中间遍历序列为a、e、c、f、b、g、d、h，下一个遍历序列为_ _ _ _72.对于包含n个节点的二进制树，如果节点编号为I (o I n-1)，则左侧的子节点编号为2i，右侧的子节点编号为2i 1，父节点编号为i/2。73.具有6个顶点的“无向完全”图形具有15个角，具有6个顶点的“有向完全”图形具有30个角。74.如果散列函数为H(key)=key%7，并且使用线性探测处理冲突，则散列表长度为_ _ hi=(

14、hash(key)di)mod m _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _75.对于快速排序，平均时间复杂性为_O(nlog2n)_ _ _，最坏情况下，时间复杂性为_O(n2)_ _ _ _。76.在二进制排序树中查找元素时，如果元素的值与根节点的值相同，_ _将查找成功_ _ _ _ _ _ _ _ _ _ _，如果元素的值小于根节点的值，则_ _ _ _左子树77.如图所示，已知从顶点1到顶点4的最短路径长度为_55_ _。78.循环单链路列表中最后一个节点的指针域指向_ _ _第一个_ _节点。79.在具有将HL用作标题指针的添加标题节点的单个和循环单个列表

15、中，确定连接的表为空的条件是_HL-next=NULL_和_ _ HL-next=HL _ _ _ _ _。80.假设二维数组A810按行优先级存储，并且每个元素占用两个存储单位，元素A00的存储地址为100，则元素A45的存储地址为_ _17481.假定具有1，000个节点的完全二进制树的中间节点数为_ _ _ _ _ _ _ _ 499 _ _ _ _ _。82.算法的时间复杂性为(3n3 2n-7)/(5n)，其计数显示为O(n2)。83.在快速排序、堆排序和合并排序中，最差时间复杂度为O(n2)的排序算法为_ _ _ _快速排序_ _ _ _ _。84.没有n个顶点的方向的完整图形包含

16、_n(n-1)/2_ _个边，而有n个顶点的直接完整图形包含_n(n-1)85.合并排序中每个合并的时间复杂性为_O(n)_ _ _ _ _ _ _，整个排序过程的时间复杂性为_ _ _ _ O(nll86.如果二进制树包含10个叶节点，则二进制树中通常2的连接数量为_ _ _ _ _ _ _ _ 9 _ _ _ _ _。87.通过n个点和e个边的相邻矩阵的图形的时间复杂性为_ _ _ _ _ _ _ O(N2)_ _ O _ _，显示为相邻表的图形的时间复杂性为_ _ O(n e)_ _ _ _ _ _ _ _ _ _ _ _ _ _ _88.如果在已排序的表格(12，18，30，43，56，78，82，95)中找到元素43和56，则查询长度分别为_ _ _ 1 _ _和_ _ 3 _ _ _ _。89.对于包含n个节点的二进制树，如果保存为辅助链接列表，则指针总数为_ _ _ _(n 1)_ _ _。其中_ _用于(n-1) _指向孩子，_ _ _ _ _ _ _处于空闲状态。90.在逻辑结构中，线性表是典型的_ _线性结构