数据结构与算法复习题及

由天下分享时间：2024/10/7 15:51:43 加入收藏我要投稿点赞

2016《数据结构域算法》复习题

25．如果排序不改变关键字相同的记录之间的相对次序，则称该排序方法是稳定的。

26．如果排序改变了关键字相同的记录之间的相对次序，则称该排序方法是不稳定的。

27．当待排关键字序列基本有序时，快速排序、简单选择排序和直接插入排序三种排序方法中，运行效率最高的是直接插入排序。

28．在一个图中，所有顶点的度数之和是所有边数的 2 倍。

29．无向图中边的数目等于邻接矩阵中非零元素个数的 0.5 倍。

30．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。

31．在有序表（2，4，6，8，10，12，14，16，18）上用

折半查找法查找元素9，其中第二次被比较的元素是 4 。

32．在有序表（2，4，6，8，10，12，14，16，18）上用

折半查找法查找元素9，其中第三次被比较的元素是 6 。

三、简答题

1．对链表设置头结点的作用是什么？（至少说出两条好处）

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

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的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）

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; }