数据结构-远程教育习题及答案.pdfVIP

数据结构-远程教育习题及答案--第1页

1、对于一个栈，若输入序列依次为{AAC},试给出所有可能的输出序

列。

答：所有可能的输出序列有：{ABC}、{ACB}、{BAC}、{BCA}、{CBA}

2、从空树开始，画出按以下次序向2_3树中插入关键字的建树过程:

20，30，50，52，60，68，70。画出每一步执行后的树的状态。

3、己知右示有向图，给出该图的：（1)每个顶点的入度及出度；（2)

邻接表

4、设关键字集合为{10，2，14，8，12，13}，写出用希尔排序方法对序列进行从小到大排

序排序时每一趟结束时的关键字状态（设增量序列为3，2，1）。

答：希尔排序：

d1=3:{8213101214}

d2=2:{8212101314}

d3=1:{2810121314}

5、已知某二叉树的先序序列为{ABHFDECKG}，中序序列为{HBDFAEKCG},画出该二叉树。

数据结构-远程教育习题及答案--第1页

数据结构-远程教育习题及答案--第2页

答：二叉树是

a

/\

be

/\\

hfc

//\

dkg

后序是hdfbkgcea

6、设顺序表va中的数据元素递增有序。设计算法，将x插入到顺序表的适当位置上，并仍

保持该表的有序性。

答：

statusinsert_Sq(SqList*va,ElemTypex)

{

inti;

if(va-length==va-listsize)exitOVERFLOW;

for(i=va-length-1;i=0va-elem[i]x;--i)

va-elem[i+1]=va-elem[i];

va-elem[i+1]=x;va-length++;

returnOK;

}

7、基于图的广度优先遍历策略写一算法，判断以邻接表方式存储的无向图中连通分量的个

数。

答：

数据结构-远程教育习题及答案--第2页

数据结构-远程教育习题及答案--第3页

8、在单链表中设置头结点有什么作用？答：头结点就是在单链表的开始结点之前附加的

一个结点，设置头结点的优点有两个：（1）由于开始结点的位置被存放在头结点的指针

域中，所以在链表的第一个位置上的操作就和在表的其他位置上一样，无须进行其他特殊处

理；（2）无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域空），

因此空表和非空表的处理也就一样了。

9、写出在循环链表中设立尾指针而非头指针的好处。答：因为尾指针的下一个就是头指

针，所以通过尾指针可以迅速的找到头指针，但是因为是单链表，所以要通过头指针找到尾

指针就必须遍历整个链表答：12345234564是连通图。

10、设关键字集合为{10，2，14，8，12，13}，写出用希尔排序方法对序列进行从小到大排

序排序时每一趟结束时的关键字状态（设增量序列为3，2，1）。

答：希尔排序：

d1=3:{8213101214}

d2=2:{8212101314}

d3=1:{2810121314}

11、设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，

0.06，0.32，0.03，0.21，0.10，试为这8个字母设计Huffman编码。

数据结构-远程教育习题及答案--第3页

数据结构-远程教育习题及答