数据结构是一门研究在非数值计算的程序设计问题中,计算机的操作对象及对象间的关系和施加于对象的操作等的学科。
2.数据元素之间的关系在计算机中有几种表示方法?各有什么特点? 四种表示方法
(1)顺序存储方式。数据元素顺序存放,每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大,但有些操作(如插入、删除)效率较差。 (2)链式存储方式。每个存储结点除包含数据元素信息外还包含一组(至少一个)指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续,便于动态操作(如插入、删除等),但存储空间开销大(用于指针),另外不能折半查等。
(3)索引存储方式。除数据元素存储在一地址连续的内存空间外,尚需建立一个索引表,索引表中索引指示存储结点的存储位置(下标)或存储区间端点(下标),兼有静态和动态特性。
(4)散列存储方式。通过散列函数和解决冲突的方法,将关键字散列在连续的有限的地址空间内,并将散列函数的值解释成关键字所在元素的存储地址,这种存储方式称为散列存储。其特点是存取速度快,只能按关键字随机存取,不能顺序存取,也不能折半存取。
3.数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处,抽象数据类型的主要特点是什么?使用抽象数据类型的主要好处是什么?
数据类型是程序设计语言中的一个概念,它是一个值的集合和操作的集合。如C语言中的整型、实型、字符型等。整型值的范围(对具体机器都应有整数范围),其操作有加、减、乘、除、求余等。实际上数据类型是厂家提供给用户的已实现了的数据结构。“抽象数据类型(ADT)”指一个数学模型及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型的定义仅取决于它的逻辑特性,而与其在计算机内部如何表示和实现无关。无论其内部结构如何变化,只要它的数学特性不变就不影响它的外部使用。抽象数据类型和数据类型实质上是一个概念。此外,抽象数据类型的范围更广,它已不再局限于机器已定义和实现的数据类型,还包括用户在设计软件系统时自行定义的数据类型。使用抽象数据类型定义的软件模块含定义、表示和实现三部分,封装在一起,对
用户透明(提供接口),而不必了解实现细节。抽象数据类型的出现使程序设计不再是“艺术”,而是向“科学”迈进了一步。sofa燃烧器
4.对于一个数据结构,一般包括哪三个方面:逻辑结构、存储结构、操作(运算)。
5.根据数据元素之间的逻辑关系,一般有哪几类基本的数据结构?
集合、线性结构、树形结构、图形或网状结构。
6.线性表有两种存储结构:一是顺序表,二是链表。试问: (1)如果有 n个线性表同时并存,并且在处理过程中各表的长度会动态变化,线性表的总数也会自动地改变。在此情况下,应选用哪种存储结构? 为什么?
选链式存储结构。它可动态申请内存空间,不受表长度(即表中元素个数)的影响,插入、删除时间复杂度为O(1)。
(2)若线性表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取线性表中的元素,那么应采用哪种存储结构?为什么?
选顺序存储结构。顺序表可以随机存取,时间复杂度为O(1)。
7.线性表的顺序存储结构具有三个弱点:其一,在作插入或删除操作时,需移动大量元素;其二,由于难以估计,必须预先分配较大的空间,往往使存储空间不能得到充分利用;其三,表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点,试讨论之。
链式存储结构一般说克服了顺序存储结构的三个弱点。首先,插入、删除不需移动元素,只修改指针,时间复杂度为O(1);其次,不需要预先分配空间,可根据需要动态申请空间;其三,表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销,当空间不允许时,就不能克服顺序存储的缺点。
8.栈是只准在一端进行插入和删除操作的线性表,允许插入和删除的一端叫栈顶,另一端叫栈底。最后插入的元素最先删除,故栈也称后进先出(LIFO)表。干电池手机
9.队列是允许在一端插入而在另一端删除的线性表,允许插入的一端叫队尾,允许删除的一端叫队头。最先插入队的元素最先离开(删除),故队列也常称先进先出(FIFO)表。
10.什么是循环队列?
用常规意义下顺序存储结构的一维数组表示队列,由于队列的性质(队尾插入和队头删除),容易造成“假溢出”现象,即队尾已到达一维数组的高下标,不能再插入,然而队中元素个数小于队列的长度(容量)。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下,通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。
11.若元素的进栈序列为:A、B、C、D、E,运用栈操作,能否得到出栈序列B、C、A、E、D和D、B、A、C、E?为什么?
能得到出栈序列B、C、A、E、D,不能得到出栈序列D、B、A、C、E。其理由为:若出栈序列以D开头,说明在D之前的入栈元素是电厂生产管理系统A、B和C,三个元素中C是栈顶元素,B和A不可能早于C出栈,故不可能得到D、B、A、C、E出栈序列。
12汽车油箱结构.串?串是零个至多个字符组成的有限序列。从数据结构角度讲,串属于线性结构。与线性表的特殊性在于串的元素是字符。
13.描述以下概念的区别:空格串与空串。
空格是一个字符,其ASCII码值是32。空格串是由空格组成的串,其长度等于空格的个数。空串是不含任何字符的串,即空串的长度是零。
14.数组A[1..8,-2..6,0..6]以行为主序存储,设第一个元素的首地址是78,每个元素的长度为4,试求元素A[4,2,3]的存储首地址。
958
三维数组以行为主序存储,其元素地址公式为:
LOC(Aijk)=LOC(Ac1c2c3)+[(i-c1)V2V3+(j-c2)V3+(k-c3)]*L+1
其中ci,di是各维的下界和上界,Vi=di-ci+1是各维元素个数,L是一个元素所占的存储单元数。
15.数组A中,每个元素A[i,j]的长度均为32个二进位,行下标从-1到9,列下标从1到11,从首地址S开始连续存放主存储器中,主存储器字长为16位。求:
(1)存放该数组所需多少单元?
(2)存放数组第4列所有元素至少需多少单元?
(3)数组按行存放时,元素A[7,4]的起始地址是多少?
(4)数组按列存放时,元素A[4,7]的起始地址是多少?
答:每个元素32个二进制位,主存字长16位,故每个元素占2个字长,行下标可平移至1到11。
(1)242 (2)22 (3)s+182 (4)s+142
16. 从概念上讲,树,森林和二叉树是三种不同的数据结构,将树,森林转化为二叉树的基本目的是什么,并指出树和二叉树的主要区别。 树的孩子兄弟链表表示法和二叉树二叉链表表示法,本质是一样的,只是解释不同,也就是说树(树是森林的特例,即森林中只有一棵树的特殊情况)可用二叉树唯一表示,并可使用二叉树的一些算法去解决树和森林中的问题。
树和二叉树的区别有三:一是二叉树的度至多为2,树无此限制;二是二叉树有左右子树之分,即使在只有一个分枝的情况下, 也必须指出是左子树还是右子树,树无此限制;三是二叉树允许为空,树一般不允许为空(个别书上允许为空)。
17.请分析线性表、树、广义表的主要结构特点,以及相互的差异与关联。
线性表属于约束最强的线性结构,在非空线性表中,只有一个“第一个”元素,也只有一个“最后一个”元素;除第一个元素外,每个元素有唯一前驱;除最后一个元素外,每个元素有唯一后继。树是一种层次结构,有且只有一个根结点,每个结点可以有多个子女,但只有一个双亲(根无双亲),从这个意义上说存在一(双亲)对多(子女)的关系。广义表中的元素既可以是原子,也可以是子表,子表可以为它表共享。从表中套表意义上说,广义表也是层次结构。从逻辑上讲,树和广义表均属非线性结构。但在以下意义上,又蜕变为线性结构。如度为1的树,以及广义表中的元素都是原子时。另外,广义表从元素之间的关系可看成前驱和后继,也符合线性表,但这时元素有原子,也有子表,即元素并不属于同一
数据对象。
18.一棵二叉树中的结点的度或为0或为2,则二叉树的枝数为2(n0-1),其中n0是度为0的结点的个数。
证明:设二叉树度为0和2的结点数及总的结点数分别为n0,n2 和n,则n=n0+n2 … (1)
再设二叉树的分支数为B, 除根结点外,每个结点都有一个分支所指,则 n=B+1… … …(2)
度为零的结点是叶子,没有分支,而度为2的结点有两个分支,因此(2)式可写为
n=2*n2+1 ……………(3)
由(1)、(3)得n2=n0-1,代入(1),并由(1)和(2)得B=2*(n0-1)。 证毕。
19.(1).如果G1是一个具有n个顶点的连通无向图,那么G1最多有多少条边?G1最少有多少条边?
(2).如果G2是一个具有n个顶点的强连通有向图,那么G2最多有多少条边?G2最少有多少条边?
(3).如果G3是一个具有n个顶点的弱连通有向图,那么G3最多有多少条边?G3最少有多少条边?
答:(1)G1最多n(n-1)/2条边,最少n-1条边
(2) G2最多n(n-1)条边,最少n条边
(3) G3最多n(n-1)条边,最少n-1条边 (注:弱连通有向图指把有向图看作无向图时,仍是连通的)
20.n个顶点的无向连通图最少有多少条边?n个顶点的有向连通图最少有多少条边?
n-1,n
21.内部排序(名词解释)
假设含n个记录的序列为{ R1, R2, …,Rn },其相应的关键字序列为{ K1, K2, …,Kn },这些关键字相互之间可以进行比较,即在它们之间存在着这样一个关系Ks1≤Ks2≤…≤Ksn,按此固有关系将n个记录序列重新排列为{ Rs1, Rs2, …,Rsn }。若整个排序过程都在内
存中完成,则称此类排序问题为内部排序。
22.在各种排序方法中,哪些是稳定的?哪些是不稳定的?并为每一种不稳定的排序方法举出一个不稳定的实例。
排序方法 | 平均时间 | 最坏情况 | 辅助空间 | 稳定性 | 不稳定排序举例 |
直接插入排序 | O(n2) | O(n2) | O(1) | 稳定 | |
折半插入排序 | O(n2) | O(n2) | O(1) | 稳定 | |
二路插入排序 | O(n2) | O(n2) | O(n) | 稳定 | |
表插入排序 | O(n2) | O(n2) | O(1) | 稳定 | |
起泡排序 | O(n2) | O(n2) | O(1) | 稳定 | |
直接选择排序 | O(n2) | O(n2) | O(1) | 不稳定 | 2,2’,1 |
希尔排序 | O(n1.3) | O(n1.3) | O(1) | 不稳定 | 3,2,2’陶粒砂过滤,1(d=2,d=1) |
快速排序 | O(nlog2n) | O(n2) | O(log2n) | 不稳定 | 2,2’,1 |
堆排序 | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 | 2,1,1婴儿印泥’(极大堆) |
2-路归并排序 | O(nlog2n) | O(nlog2n) | O(n) | 稳定 | |
基数排序 | O ( d*(rd+n) ) | O ( d*(rd+n) ) | O (rd ) | 稳定 | |
| | | | | |
23.文件