文档介绍：-
. z.
数据构造简答题
简述以下术语：数据，数据元素、数据对象、数据构造、存储构造、数据类型和抽象数据类型。
解：数据是对客观事物的符号表示。在计算机科学中是指所有存储构造可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在存储构造中存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。
-
. z.
3. 对于线性表的两种存储构造，如果有n个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，.
3．应选用存储构造，因为链式存储构造是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的：这种存储构造对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩大。
4. 对于线性表的两种存储构造，假设线性表的总数根本稳定，且很少进展插入和删除操作，但要求以最快的速度存取线性表中的元素，。
4．应选用顺序存储构造，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。因此，只要确定了其起始位置，线性表中的任一个数据元素都可随机存取，因此，线性表的顺序存储构造是一种随机存取的存储构造，而链表则是一种顺序存取的存储构造。
5. "
5．设尾指针比设头指针好。尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开场结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开场结点和终端结点的位置分别是rear->ne*t->ne*t 和 rear, 查找时间都是O(1)。假设用头指针来表示该链表，则查找终端结点的时间为O(n)。
6. 假定有四个元素A, B, C, D依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。
6．共有14种可能的出栈序列，即为：
-
. z.
ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA
7. ，试简述之。
7．在队列的顺序存储构造中，设队头指针为front，队尾指针为rear，队列的容量〔即存储的空间大小〕为ma*num。当有元素要参加队列〔即入队〕时，假设rear=ma*num，则会发生队列的上溢现象，此时就不能将该元素参加队列。对于队列，还有一种“假溢出〞现象，队列余有足够的空间，但元素却不能入队，一般是由于队列的存储构造或操作方式的选择不当所致，可以用循环队列解决。
一般地，要解决队列的上溢现象可有以下几种方法：
〔1〕可建立一个足够大的存储空间以防止溢出，但这样做往往会造成空间使用率低，浪费存储空间。
〔2〕要防止出现“假溢出〞现象可用以下方法解决：
第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。
第二种：每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。
第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出〞的原则。
8. 下述算法的功能是什么"
LinkList *Demo(LinkList *L)
{ // L是无头结点的单链表
LinkList *q,*p;
-
. z.
if(L&&L->ne*t)
{ q=L; L=L->ne*t; p=L;
while (p->ne*t)
p=p->ne*t;
p->ne*t=q; q->ne*t=NULL;
}
return (L);
}
8．该算法的功能是：将开场结点摘下到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开场结点，返回新链表的头指针。
四、应用题
1. 一棵树边的集合为{<i，m>，<i，n>，<e，i>，<b，e>，<b，d>，<a，b>，<g，j>，<g，k>，<c，g>，<c，f>，<h，l>，<c，h>，<a，c>}，请画出这棵树，并答复以下问题：
〔1〕哪个是根结点.