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}为例，写出执行（从小到大）简单选择排序算法的各趟

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库2012年浙江工业大学数据结构在线全文阅读。