对比单链表双向链表循环链表的相同点，不同点及特点
访问方式：
顺序表SqList：随机选取表中元素。寻找元素简单，但是插入删除时要移动表中的元素。
单链表LinkList：如果访问任意结点每次只能从头开始顺序向后访问。插入删除简单，寻找元素麻烦。
单循环链表CirLinkList：可以从任何一个结点开始，顺序向后访问到达任意结点。特点：最后一个结点的指针域指向头结点。
双向链表DuLinkList：可以从任何结点开始任意向前向后双向访问。
插入和删除操作（先查找元素，再进行插入或删除）：
单链表和单循环链表：只能在当前结点后插入和删除。
双链表：可以在当前结点前面或者后面插入，可以删除前趋和后继（包括结点自己）。
存储：
单链表和单循环链表存储密度大于双链表。
其他总结
在顺序表中插入或删除一个数据元素，平均约需移动表中一般元素(在第i个元素之前插入或删除时，需将第i+1至第n个元素依次向后（向右）或向前（向左）移动一个位置)；还要预先分配内存空间。
链表与顺序表相比，他增加了指针空间开销。
进行插入或删除操作时应考虑的方面：1、空间是否够用。2、插入或删除的位置是否合法。链表的插入式时应创建新的结点，删除时应释放被删除的结点的空间。
注意：链表的数据元素有两个域，所以每个结点至少有两个分量，数据类型不一致，所以要采用结构数据类型。
第一类题目选择题 1．从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 2．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。 A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表3．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 4．执行下面程序短的时间复杂度为（）。 for(i=0;i
创建双向循环链表的源代码： #include
L->Length ++; } } //结点的输出 void Display( DuLinkList L) { DuLinkList p; printf("双向循环链表中的结点的数据为:"); for(p=L->next ;p->next !=L;) { printf("%d",p->data); printf(" 、"); p=p->next ; } printf("%d\n",p->data ); } int main() { DuLinkList L; int n,i; InitList(&L) ; printf("你想创建几个循环节点就输入几就行啦，请输入:"); scanf("%d",&n); Create(L,n); Display(L); } 双向循环链表插入源代码： #include
第2章自测卷答案 一、填空 1.顺序表中逻辑上相邻的元素的物理位置相互相邻。单链表中逻辑上相邻的元素的物理位置不 相邻。 2.在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点值域指示。 3．在n个结点的单链表中要删除已知结点*p，需找到它的地址。 二、判断正误（在正确的说法后面打勾，反之打叉） 1. 链表的每个结点中都恰好包含一个指针。X 2. 链表的物理存储结构具有同链表一样的顺序。X 3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。X 4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。Y 5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。Y 6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。X 7. 线性表在物理存储空间中也一定是连续的。X 8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。X 9. 顺序存储方式只能用于存储线性结构。X 10. 线性表的逻辑顺序与存储顺序总是一致的。X 三、单项选择题 （A）1. 链接存储的存储结构所占存储空间： （A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 （B）只有一部分，存放结点值 （C）只有一部分，存储表示结点间关系的指针 （D）分两部分，一部分存放结点值，另一部分存放结点所占单元数 （B）2. 链表是一种采用存储结构存储的线性表； （A）顺序（B）链式（C）星式（D）网状 （D）3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址: （A）必须是连续的（B）部分地址必须是连续的 （C）一定是不连续的（D）连续或不连续都可以 （B）4．线性表Ｌ在情况下适用于使用链式结构实现。 （Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入 （Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂 （C）5．单链表的存储密度 （Ａ）大于1；（Ｂ）等于1；（Ｃ）小于1；（Ｄ）不能确定 （A）6、在单链表的一个结点中有个指针。
2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构 D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C 。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。 （1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。 s ＝0；
for（ I ＝0； i＜n； i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝ s ； 9．下面程序段的时间复杂度是O（n*m）。 for（ i ＝0； i＜n； i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝ 0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝ 0； while（i＜＝n） i ＝ i * 3； 11．在以下的叙述中，正确的是 B 。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出（先进后出） D．队列的操作方式是先进后出（先进先出，尾进首出） 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是 A 。（顺序表是随机访问的，只要知道首元素的地址，就可以知道任意的第i个元素的地址） A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是 A 。
#include
int i=-1; List *p,*data1,*q,*Last; data1=(List *)malloc(sizeof(List)); p=(List *)malloc(sizeof(List)); q=(List *)malloc(sizeof(List)); data1=head->next;//记住第一个数据地址 p=head->next; while(p->next!=NULL) { q=p; //q是前一个节点 p=p->next; //p是后一个节点 p->pre=q; //后一个节点的【前继指针】指向前一个节点的地址} Last=p; //p 就是【最后一个数据】的地址 data1->pre=Last; //【第一个元素】的【前继指针】指向【最后一个元素】的地址Last->next=data1; //【最后一个元素】的【后继指针】指向【第一个元素】的地址//双向链表构成 p=Last; printf("\n\n"); while(p->data!=1) { printf("%d ",p->data); p=p->pre; } printf("%d \n",p->data); }
习题3(链表)
习题3（链表） 一、选择题 （1）链接存储的存储结构所占存储空间（ A ）。 A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B）只有一部分，存放结点值 C）只有一部分，存储表示结点间关系的指 针 D）分两部分，一部分存放结点值，另一部分存放结点所占单元数 （2）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。 A）必须是连续的 B）部分地址必须是连续的 C）一定是不连续的 D）连续或 不连续都可以 （3）线性表Ｌ在（ B ）情况下适用于使用链式结构实现。 A）需经常修改结点值 B）需不断删除插入 C）含有大量的结点 D）结点 结构复杂 （4）单链表的存储密度（ C ）。 A）大于1 B）等于1 C）小于1 D）不能确定 （5）若指定有n个元素的向量，则建立一个有序单链表的时间复杂性的量级是（ C ）。 A）O(1) B）O(n) C）O(n2) D）O(nlog2n) （6）在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（ D ）。 A）s->next=p+1; p->next=s; B）(*p).next=s; (*s).next=(*p).next; C）s->next=p->next; p->next=s->next; D）s->next=p->next; p->next=s; （7）在双向链表存储结构中，删除p所指的结点时须修改指针（ A ）。
A）p->next->prior=p->prior; p->prior->next=p->next; B）p->next=p->next->next; p->next->prior=p; C）p->prior->next=p; p->prior=p->prior->prior; D）p->prior=p->next->next; p->next=p->prior->prior; （8）在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（ C ）。 A）p->next=q; q->prior=p; p->next->prior=q; q->next=q; B）p->next=q; p->next->prior=q; q->prior=p; q->next=p->next; C）q->prior=p; q->next=p->next; p->next->prior=q; p->next=q; D）q->prior=p; q->next=p->next; p->next=q; p->next->prior=q; （9）链表可以带表头结点，也可以不带表头结点，前者最主要的好处是（ B ）。 A）加快表的遍历 B）使空表和非空表的处理统一 C）节省存储空间 D）提高存取元素的速度 （10）在单链表指针p所指向的结点后面插入一个新结点q的操作语句序列为（ A ）。 A）q->next=p->next; p->next=q; B）p=p->next; p->next=q->next; C）q=p->next; q->next=p->next; D）p->next=q; q->next=p->next; （11）在一个单链表中,若要删除p个结点的后继结点,则执行( A ) A）p->next=p->next->next; B）p=p->next; p->next->next; C）free（p->next）; D）p＝p->next->next； （12）设rear是指向非空带头结点的循环单链表的尾指针，则删除表首结点的操作可表示为( B ) A）p＝rear; B）p= rear->next->next; Rear=rear->next; rear->next->next＝p->next;
list是双向循环链表，，每一个元素都知道前面一个元素和后面一个元素。在STL 中，list和vector 一样，是两个常被使用的容器。和vector不一样的是，list不支持 对元素的任意存取。list中提供的成员函数与vector类似，不过list提供对表首元素的操作 push_front、pop_front，这是vector不具备的。禾口vector另一点不同的是，list的迭代器不会存在失效的情况，他不像vector会保留备份空间，在超过容量额度时重新全部分配内存，导致迭代器失效；list没有备份空间的概念，出入一个元素就申请一个元素的空间，所以它的迭代器不会失效。还是举《C++之vector》中的 例子： int data[6]={3,5,7,9,2,4}; list< int> lidata(data, data+6); lidata.push_back(6); list初始化时，申请的空间大小为6，存放下了data中的6个元素，当向lidata插入第7个元素“6”，list申请新的节点单元，插入到list链表中，数据存放结构如图1所示： 插入节点"6拆之后的list 图1 list的存储结构 list每次增加一个元素，不存在重新申请内存的情况，它的成本是恒定的。而vector每当增加关键元素的时候，都需要重新申请新的更大的内存空间，会调用元素的自身的复制构造函数，存在构造成本。在销毁旧内存的时候，会调用析构函数, 存在析构成本。所以在存储复杂类型和大量元素的情况下，list比vector更有优势！ List是一个双向链表,双链表既可以向前又向后链接他的元素。
实验一 要求：①建立双向循环链表 ②实现链表的插入、删除 运行程序点此处Demo_1.exe 实验程序源代码： #include "stdafx.h" #include
p->next =q; q->prior=p; q->next=L; L->prior =q; p=q; L->Length ++; } } //查找元素的位置 DuLinkList GetElemP(DuLinkList h,int i) { int j; DuLinkList p=h; for(j=1;j<=i;j++) p=p->next ; return p; } //结点的插入 status Listinsert(DuLNode *m,int i,int e) { //在带头结点的双链循环线性表L中第i个位置之前插入元素e，i的合法值为1≤i≤表长 DuLinkList p,q; if(i<1||i>(m->Length)) // i值不合法 return ERROR; p=GetElemP(m,i); if(!p) return ERROR; q=(DuLinkList)malloc(sizeof(DuLNode)); if(!q) return OVERFLOW; q->data=e; q->prior=p->prior; p->prior->next=q; q->next=p; p->prior=q; m->Length++; printf("您在双向循环链表第%d个位置之前插入了一结点元素:%d\n",i,e); return OK; } //结点的删除 status ListDelete(DuLinkList L,int i) { //删除带头结点的双链循环线性表L的第i个元素，i的合法值为1≤i≤表长
数据结构期末复习题 一、选择题 1.以下说法中不正确的是（D）。 A.数据元素是数据的基本单位 B.数据项是不可分割的最小可标识单位 C.数据可由若干个数据元素构成 D.数据项可由若干个数据元素构成 2.计算机所处理的数据一般具备某种在联系，这是指（B）。 A.数据和数据之间存在某种关系 B.元素和元素之间存在某种关系 C.元素部具有某种结构 D.数据项和数据项之间存在某种关系 3.在数据结构中，与所使用的计算机无关的是数据的（A）结构。 A.逻辑 B.存储 C.逻辑和存储 D.物理 4.数据的逻辑结构可以分为（C）两类。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.部结构和外部结构 5.数据的逻辑结构是指（A）关系的整体。 A.数据元素之间逻辑 B.数据项之间逻辑 C.数据类型之间 D.存储结构之间 6.以下数据结构中（D）属非线性结构。
A.栈 B.串 C.队列 D.平衡二叉树 7.以下属于逻辑结构的是（C）。 A.顺序表 B.哈希表 C.有序表 D.单链表 8.以下不属于存储结构的是（A）。 A.栈 B.线索二叉树 C.哈希表 D.双链表 9.在计算机中存储数据时，通常不仅要存储个数据元素的值，而且还要存储（C）。 A.数据的处理方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 10.数据结构在计算机存中的表示是指（A）。 A.数据的存储结构 B.数据结构 C.数据的逻辑结构 D.数据元素之间的关系 11.在数据的存储结构中，一个结点通常存储一个（B）。 A.数据项 B.数据元素 C.数据结构 D.数据类型 12.在决定选择何种类型的存储结构时，一般不多考虑（A）。 A.各结点的值如何 B.结点个数的多少 C.对数据有哪些运算 D.所用编程语言实现这种结构是否方便
模拟试题1 一、选择题（20分） 1. 组成数据的基本单位是( )。 (A) 数据项(B)数据类型(C)数据元素(D)数据变量 2. 线性表的链接实现有利于( )运算。 (A) 插入(B)读表元(C)查找(D)定位 3. 串的逻辑结构与( )的逻辑结构不同。 (A) 线性表(B)栈(C)队列(D)树 4. 二叉树第i（i≥1）层最多有( )个结点。 (A) 2i(B)2i (C) 2i-1(D) 2i-1 5. 设单链表中p指向结点A，若要删除A后结点（若存在），则需要修改p的操作为( ) (A) p.Next = p.Next.Next (B)p=p.Next (C)p=p.Next.Next (D)p.Next=p 6. 设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为( ) (A) 3,2,5,6,4,1 (B) 1,5,4,6,2,3 (C) 2,4,3,5,1,6 (D) 4,5,3,6,2,1 7. 设字符串S1=’ABCDEFG’，S2=’PQRST’，则运算S=CONCA T(SUB(S1,2,LENGTH(S2))，SUB(S1,LENGTH(S2),2))的结果为( ) (A) ‘BCQR’(B) ‘BCDEF’(C) ’BCDEFG’(D) ‘BCDEFEF’ 8. 有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占1个地址空间，则a85地址为( ) (A)13 (B) 33 (C) 18 (D) 40 9. 如果结点A有3个兄弟，而且B为A的双亲，则B的度为( ) (A) 3 (B) 4 (C) 5 (D) 1 10. 线索化二叉树中某结点D没有左孩子的必要条件是( ) (A) D.Lchild=null (B) D.ltag=1 (C) D.Rchild=null (D) D.ltag=0 二、填空题（20分） 1. 对于一个以顺序实现的循环队列Q[0..m_1]，队头、队尾指针分别为f,r,其判空的条件是 ，判满的条件是。 2. 循环链表的主要优点是。 3. 给定一个整数集合{3,5,6,9,12}，画出其对应的一棵Huffman树。 4 双向循环链表中，在p所指的结点之后插入f所指的结点，其操作为。 5. 下列为朴素的模式匹配算法，请在算法的处填入正确的子句。 public int insert(string s, string t) { int i = 0; int j = 0; while (i < s.Length && j < t.Length) {
#include
typedef struct node { ElemType data; struct node *prior, *next; }DLink; void InitList(DLink **L); //初始化运算 int GetLength(DLink *L); //求表长运算 int GetElem(DLink *L, int num, ElemType *e); //求线性表中第i个元素运算int Locate(DLink *L, ElemType x); //按值查找运算 int InsElem(DLink *L, ElemType x, int i); //插入节电运算 int DelElem(DLink *L, int num); //删除结点运算 void DispList(DLink *L); //输出线性表 #endif [cpp] view plaincopyprint? #include
一． 1．数据的不可分割的基本单位是( D )。 A．元素B．结点C．数据类型D．数据项 2．算法是指( C )。 A．计算方法B．排序方法 C．解决问题的有限运算步骤D．查找方法 3．顺序存储结构中数据元素之间的逻辑关系是由（C ）表示的 A 线性结构 B 非线性结构 C 存储位置 D 指针 4．单循环链表的主要优点是（B ）。 A 不再需要头指针了 B 从表中任一结点出发都能扫描到整个链表； C 已知某个结点的位置后，能够容易找到它的直接前趋； D 在进行插入、删除操作时，能更好地保证链表不断开。 5．一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是(C )。 A 54321 B 45321 C 43512 D 12345 6．常对数组进行的两种基本操作是( B ) A．建立和删除B．索引和修改C．插入和修改D．插入和索引7．算法分析的两个主要方面是（A ）。 A空间性能和时间性能B正确性和简明性C 可读性和文档性D 数据复杂性和程序复杂性 8．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（B ）结构。 A 栈 B 队列 C 数组 D 线性表 9．二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（D）个字节。 A 90 B 180 C 240 D 540 10．下面（C）不属于特殊矩阵。 A 对角矩阵 B 三角矩阵 C 稀疏矩阵 D 对称矩阵 13．算法在发生非法操作时可以作出处理的特性称为（A ）。 A 健壮性 B 确定性 C 可行性 D 正确性 16．算法指的是（A）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 17．算法分析的目的是( C )。 A．找出数据结构的合理性B．研究算法中输入和输出的关系 C．分析算法的效率以求改进D．分析算法的易读性和文档性 18．若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋，则采用（A）存储方法最节省时间。(随机存储) A 顺序表 B 单链表 C 双链表 D 单循环链表 19．在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p 之间插入s所指结点，则执行（B ）操作。 A s->next=p->next; p->next=s; B q->next=s; s->next=p; C p->next=s->next; s->next=p; D p->next=s; s->next=q; 20．若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（D ）。
郑州大学现代远程教育 《数据结构》课程（本科） 学习指导书 郭纯一编
?课程内容与基本要求 “数据结构”在计算机科学中是一门综合性的专业基础课。本课程将主要介绍数据结构的基本概念和术语、非数值计算中常用的数据结构（线性表、栈和队列、串、树和图）和基本技术（查找和排序方法）三大部分。 本课程要求学生在掌握线性表、栈和队列、串、树和二叉树、图等基本数据类型的基础上，会分析各种数据结构的特性，会根据应用需求为所涉及的数据合理选择适当的逻辑结构和存储结构，并能据此设计实现问题的算法；还应初步掌握算法的时间和空间效率的分析方法。 ?课程学习进度与指导
第一章绪论 一、章节学习目标与要求 1、理解数据抽象和信息隐蔽原则 2、掌握所有的基本概念和术语、掌握时间复杂度的计算方法、会用C语言描述抽象数据类型和算法；能够熟练使用C语言编写程序 二、本章重点、难点 重点：基本概念和术语，C语言描述算法的方式，简单程序的时间复杂度的求法。难点：时间复杂度的计算方法和原则。 三、章节练习 （一）选择题： 1．具有线性结构的数据结构是__________。 A.图 B. 树 C. 集合 D. 栈 2．计算机算法是指________。 A.计算方法和运算结果 B.调度方法 C. 解决某一问题的有限运算系列 D. 排序方法 3．线性结构中，最后一个结点有________个后继结点。 A. 0 B. 1 C. 任意多 4. 算法分析的目的是________。 A. 找出数据结构的合理性 B. 研究算法中输入和输出的关系 C. 分析算法的效率以求改进 D.分析算法的可读性和可行性 5. 具有非线性结构的数据结构是__________。 A.图 B. 线性表 C. 串 D. 栈 6．算法具有5个特性：________、________、________、输入和输出。 A. 稳定性、确定性、可行性 B. 有穷性、确定性、可行性 C. 有穷性、安全性、可行性 D. 有穷性、确定性、可移植性 7．设n为正整数。则下面程序段的时间复杂度为________。 i=1; k=0; while(i<=n-1){ @ k+=10*i;
一、选择题（每小题2分，共20分） 1、下列程序段的算法复杂度为（） s=1; while(s 1、下列程序段的算法复杂度为（） I=0; s=0; while(s List-DuLinkedList-双向循环链表-Locate(L,x) 2.38 设有一个双向循环链表，每个结点中除了有prior、data和next三个域外，还增设了一个访问频度域freq。在链表被启用之前，频度域freq的值均初始化为零，而每当对链表进行一次Locate(L, x)的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值便增加1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的Locate操作的算法。#include 电大数据结构复核习题（简答题） 1、简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？ 答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构。可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。 2、解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。 答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的。优点：一般情况下，存储密度大，存储空间利用率高。缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。 链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。优点：插入和删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。 3、什么情况下用顺序表比链表好？ 答：顺序表适于做查找这样的静态操作，链表适于做插入和删除这样的动态操作。如果线性表的变化长度变化不大，且其主要操作是查找，则采用顺序表；如果线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。 4、解释头结点、第一个结点（或称首元结点）、头指针这三个概念的区别？ 答：头结点是在链表的开始结点之前附加的一个结点；第一个结点（或称首元结点）是链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。 5、解释带头结点的单链表和不带头结点的单链表的区别。 答：带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上。 在结构上，带头结点的单链表，不管链表是否为空，均含有一个头结点，不带头结点的单链表不含头结点。 在操作上，带头结点的单链表的初始化为申请一个头结点。无论插入或删除的位置是地第一个结点还是其他结点，算法步骤都相同。不带头结点的单链表，其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点。因为两种情况的算法步骤不同。 6、与单链表相比，双向循环链表有哪些优点？ 答：双向循环链表设置了指向前驱和后继的指针，所用的地址空间增加，以空间复杂度代价换取时间复杂度的提高。双向循环链表可以从任一结点开始遍历整个链表。在动态内存管理中，应用双向循环链表可以从上次查找过的结点开始继续查找可用结点，而单链表却每次都需要从表头开始查找。相比之下，双向循环链表的时间效率更高。 7、简述栈和一般线性表的区别。 答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。 8、简述队列和一般线性表的区别。 答：队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。 9、链栈中为何不设头结点？ 答：因为链栈只在链头插入和删除结点，不可能在链表中间插入和删除结点，算法实现很简单，所以一般不设置头结点。 10、利用一个栈，则： （1）如果输入序列由A，B，C组成，试给出全部可能的输出序列和不可能的输出序列。 （2）如果输入序列由A，B，C，D组成，试给出全部可能的输出序列和不可能的输出序列。 答：（1）栈的操作特点是后进先出，因此输出序列有： A入，A出，B入，B出，C入C出，输出序列为ABC。 A入，A出，B入，C入，C出，B出，输出序列为ACB。 A入，B入，B出，A出，C入，C出，输出序列为BAC。 A入，B入，B出，C入，C出，A出，输出序列为BCA。 A入，B入，C入，C出，B出，A出，输出序列为CBA。 由A，B，C组成的数据项，除上述五个不同的组合外，还有一个C，A，B组合。但不可能先把C出栈，再把A出栈，（A不在栈顶位置），最后把B出栈，所以序列CAB不可能由输入序列A，B，C 通过栈得到。 （2）按照上述方法，可能的输出序列有：ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，List-DuLinkedList-双向循环链表-Locate(L,x)
电大数据结构复核习题(简答题)
相关主题
文本预览