2012年浙江工业大学数据结构

一、 简单题（共100分）

1、 有下列某数据结构的二元组表示，试画出对应的逻辑图形表示，并指出属于何种 据结构类型。（本题10分）

（1）A=(K、R) K={1,2,3,4,5} R={<1，2>，<1,3>，<2,4>，<3，5>，<2，7>，<3，6>}

（2）B=（K，R） K={a，b，c，d，e，f，g，h}

R={<a，b>，<a，d>，<a，f>，<f，e>，<b，c>，<b，d>，<d，e>}

2、 如下图所示的单链表分别执行如下程序段，请画出该单链表及节点指针的结果示意图。（本题10分）

（1） L=P next；

（2） R data=P next—>data；

（3）P next—>next next data=P data；

（4）T=P；while（T）{T data= T data *2；T=T next；}

（5）T=P；while（T next）{ T data= T data *2；T=T next;}

3、假设以S和X分别表示入栈和出栈操作，则可以通过由S和X组成的序列（如SXSSXX）描述出适合种植状态均为空的栈上的操作：（本题10分）

（1）试写出判别初始和终止状态均为空的栈上操作序列是否合法的一般规则：

（2）若入栈的元素序列为1 2 3 4 5 6 ，能否得到出栈序列3 2 5 6 4 1 和1 5 4 6 2 3 ？若能，请用S和X写出栈上对应的操作序列。

4、已知待排序的序列为（503,87,512,61,908,170,897,275,653,462,），试完成：（本题10分）

（1）根据以上序列建立一个堆（画出第一步和最后堆得结果图），希望先输出最小值；

（2）输出最小值后，如何得到次小值。（要求画出相应结果图）。

5、二维数组A中，每个元素占32比特，行下标从-1到5，列下表从1到6，假设起始地址LOC(A[-1][1])=1000，问数组A占用多少字节？若数组行优先储存时，元素A[4][5]的地址是多少？若数组按序列优先存储时，元素A[3][4]的地址是多少？（本题10分）

6、某通信过程中需要使用的编码由8个字符：A、B、C、D、E、F、G、H，各个字符的出现的次数分别为20，6，34，11，9，7，8，5。请构造相应的哈夫曼树，并计算其带权路径长度。（本题10分）

7、已知一个长度为12的线性表{20,6,15,23,35,8,28,11,1,17,25,30}，请根据如下要求画出相应的树：（本题10分）

（1）将线性表中的元素一次插入到一个空的二叉排序树中：

（2）将线性表中的元素一次插入到一个空的平衡二叉树中。

8、假设哈希函数H(k)=k%11，其中k为关键字（整数），%表示取模运算，用链接法冲突，在地址范围0~10散列区中，试用关键字序列{15,36,50,27,19,48}构造一个哈希表：（本题10分）

（1）画出该哈希表的存储结构图：

（2）若查找关键字48，需比较多少次？

9、一关键字序列{11,4,9,20,7,31,25}为例，写出执行（从小到大）简单选择排序算法的各趟

排序结果。（本题10分）

10、如下图所示的有向图，试给出：（本题10分）

（1）每个顶点的入度和出度；

（2）对应的邻接矩阵；

（3）对应的邻接表。

二、 算法设计题（共50分）

1、 假设字符串一单链表方式存储，其中节点类型定义如下：

Typedef struct node{

Char data;

Struct node *next；

} NODE,*STR;

设s和t是表示成单链表的两个字符串，试编写找出s中第一个不在t中出现的字符算法（如果不存在这样的字符，则返回空指针）；（本题10分）

NODE* FIND(STR s，STR t)；

2、 编写用一位数组构建带有头结点的循环链表的函数。假设数组元素的类型为ElemType，要求链表中数据从大到小排列，重复的数据在链表中只保存一个。（本题12分）

3、 编写求解给定关键字在二叉排序树中所载层数的算法（假设根节点所在层数为1，如果不存在该关键字则返回0）。（本题12分）

4、采用单链表表示一元多项式，每个节点中表示多项式的某个次方及其系数，假设次方从大到小排序，请定义相应的节点结构，并编写计算两个（同元）多项式之差的函数。例如下图所表示，多项式f（x）=x3+x2-x+4与g（x）=2x3+3x2-x+1的差为-2x+x5-2x2+3，注意单链表中不保留系数为0的项。（本题16分

）