数据结构复习题及答-数据结构“”.docx

数据结构****题
一、 名词解释
数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、
算法、时间复杂度、空间复杂度 。
线性表、顺序表、单链表 、双向链表 、循环链表 、双向循环链表 、三个概念的区别：头
指针、头结点、首元结点（第1个元素结点 ）。
栈（顺序栈、链栈）、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。
树、叶子结点、结点的度、树的度、树的高 （深）度、二叉树、遍历、满二叉树、完全二叉树 、
哈夫曼树、WPL哈夫曼编码。
图（有向、无向）、网、边、弧、度、入度、出度、完全图（有向、无向） 、（强）连通图（分量）、
（最小）生成树、邻接矩阵、邻接表、 DFS BFS
查找表、关键字、静态查找、动态查找、 ASL、顺序查找、折半查找、分块查找、二叉排序树。
排序、内（外）排序、稳定性、插入（直接、希尔） ，交换（起泡、快速），选择（直接、堆），2 路归并。
填空题
数据结构是研究数据的 _逻辑结构_和—物理结构_，并在这种结构上定义相关的运算， 设计实
现这些运算的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为 —时间
复杂度 和空间复杂度—。
数据的基本单位是 数据元素 ，数据的最小单位是 数据项 。
算法是对特定问题求解 —步骤___的一种描述，是指令的有限序列。
一个算法的时间复杂度为 （3n3+2n — 7），其数量级表示为_0 （ n3）__。
一个算法具有5个特性：_确定性、—可行性_、_有穷性_、输入和输出。
算法性能的分析和度量，可以从算法的 时间复杂度一和—空间复杂度—来评价算法的优劣。
数据的逻辑结构包括集合结构、 _线性结构 _、—树形结构_和_图型结构—四种类型。
数据结构在计算机中的表示称为数据的 物理结构，它可以采用 _顺序存储_ 或_链式存储_
两种存储方法。
线性表有两种存储结构，分别为 _顺序存储 _ 和 链式存储_。
链式存储的特点是利用 指针—来表示数据元素之间的逻辑关系。
若频繁地对线性表进行插入和删除操作，该线性表宜采用 链式存储—存储结构。
线性表中的数据元素之间具有 _一对一_的线性关系，除第一个和最后一个元素外，其他数据
元素有且只有一个_直接后继和直接前趋。
在一个单链表中 p所指结点之后插入一个 s所指结点时，应执行 s->next=_ p->next 和
p->next=_ s 的操作。
在一个单链表中删除 p的后继结点q时，应执行以下操作 p->next= q->next 。
head-〉next=NULL
对带头结点head的单链表，则判断其为空的条件为
对带头结点head的循环单链表尾结点(由p所指向)判非空的条件为 _p->next=head 。
在栈结构中，允许插入的一端称为 _栈顶 ;在队列结构中，允许插入的一端称为_队尾 。
队列中元素的入队和出队应遵循 一先进先出_ _原则，数据元素1，2, 3, 4，5按照次序入队
后，第一个出队的是 _1 。
在循环队列中，存储空间为 0〜n-1。设队头指针front指向队头元素前一个空闲元素，队尾指
针指向队尾元素，那么其队空标志为 rear=front ，队满标志为_(rear+1)% n=front _。
设顺序表有19个元素，第一个元素的地址为 200,且每个元素占3个字节，则第14个元素的存
储地址为_239 。
在一个长度为n的顺序表中删除第i个元素(K i < n),需向前移动 n-i 个元素。
在一个长度为 n的顺序表中第 i个元素前(K i < n),插入一个元素，需向后移动 n-i+1
个元素。
在顺序存储的线性表中插入或删除一个元素平均约移动表中 __50%_ (或一半)_的元素。
在顺序表中访问任意一结点的时间复杂度均为 0(1),因此，顺序表也称为 随机存取 的数据
结构。
在n个结点的单链表中要删除已知结点 *p，需找到它的前驱结点的地址，其时间复杂度为 O(n)。
一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度为 __5___，深度为 3 。
已知广义表 A=((a,b,c),( d,e,f))，则运算 tail (head (tail(A)))= (e,f) __。
已知广义表 Ls=(a,(b,c,d),e) ，运用 head和tail 函数取出 Ls中的原子 b的运算是
_ 。
广义表((a,b),c,d)的表头是 _(a,b) _ 表尾是_( c,d)_。
广义表(a,b,c,d)的表头是_a 表尾是 (b,c,d)_ 。
两个串相等的充分必要条件是 : 串