发布时间 : 星期一 文章数据结构与算法复习题及更新完毕开始阅读ee8216e5580102020740be1e650e52ea5418ce59
2016《数据结构域算法》复习题
答：其好处有：（1）对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一个结点的指针域，因为任何元素结点都有前驱结点（若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点和删除该结点时操作复杂些）。
（2）对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。
2.写出下列程序段的输出结果（队列中的元素类型QElem Type为char）。 void main( ){
Queue Q; Init Queue (Q); Char x=’e’; y=’c’;
EnQueue (Q,’h’); EnQueue (Q,’r’); EnQueue (Q, y);
DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,’a’);
while(!QueueEmpty(Q)){ DeQueue (Q,y); printf(y); };
Printf(x); } 解：char
17
2016《数据结构域算法》复习题
3. 简述以下算法的功能（栈和队列的元素类型均为int）。 void algo3(Queue &Q){
Stack S; int d; InitStack(S);
while(!QueueEmpty(Q)){
DeQueue (Q,d); Push(S,d); };
while(!StackEmpty(S)){
Pop(S,d); EnQueue (Q,d); } }
解：
利用栈S作为缓存空间，将队列Q中的元素进行逆置（即相对于原顺序进行倒排）。
4. 描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？
答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）
18
2016《数据结构域算法》复习题
的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。
头结点
head ?
data link 头指针 首元结点 简而言之，
头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；
头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针！！！）
首元素结点是指链表中存储线性表中第一个数据元素a1的结点。
5. 对以下单链表执行下列语句，简述代码的功能，并画L 2 5 3 ^ 7 8 出单链表结果示意图。
T = L;
while(T->next != NULL) {
T->data = 2 * T->data; T = T->next; }
19
2016《数据结构域算法》复习题
解：
代码功能：除最后一个结点之外，每个结点的数值部分改变为原值的2倍。 单链表结果示意图如下： L 1 1 6 8 4 ^
6. 请画出下图的邻接矩【本题较简单，不提供答
7．假设二叉树采用顺序存储结构，如图所示。 （1） 画出二叉树表示；
（2） 写出先序遍历、中序遍历和后序遍历的结果； （3） 写出结点值c 的双亲结点，其左、右孩子； 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 e a f
8. 树和二叉树之间有什么样的区别与联系？
20
阵和邻接表 案】
d g c j h i b