太原理工大学 数据结构(a) 试卷

《太原理工大学 数据结构(a) 试卷》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、考试类型：闭卷太原理工大学数据结构（A）试卷适用专业：计本04考试日期:06.7.14吋间：120分钟共_8_页题号—-二三四五六七八九得分一.判断题：（每小题2分，共20分）1.链栈的初始化是指开辟足够多的结点，然后置栈顶指针为NULLo（）2.数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式。（）3.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（）4.在顺序存储结构中，有时也存储数据结构中元素之间的关系。（）5.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于

2、计算机的储存结构。（）6.完全二叉树的某结点若无左孩子，则它必是叶结点。（）7.用邻接矩阵表示图时，矩阵元素的个数与边的条数有关。（）9.图的深度优先搜索序列和广度优先搜索序列不是唯一的。（）10.用简单选择排序算法，只需一趟扫描即可选出键值最大（或最小）的元二选择题：（每小题2分，共10分）1.二维数组A的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8,列下标j的范围从1到10,A的第8列和第5行共占（）个字节。(1)108(2)60(3)54(4)1141.表达式a*（

3、b-c）+d的后缀表达式是（）。(1)abcd*~+(2)abc-*d+(3)abc*-d+(4)+-*abcd3.对于有N个结点高度为K的满二叉树（结点编号为1到N,根结点的层数为1）,其第K层上最后1个结点的编号为（）。(1)2k(2)2k_1(3)2k_1-1(4)2-14.一个有N个顶点的无向图最多有（）条边。(1)N(3)N*(N—1)/2(4)2*N5.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）。(1)43/12(2)3

4、9/12(3)37/12(4)35/12三•填空题：（每空2分，共10分）1.对于一个具有N个结点的单链表，在已知P所指结点后插入一个新结点的时间复杂度是;在给定值为X的结点后插入一个新结点的时间复杂度是O2.有如下递归过程：Voidprint(intw){inti:if(w!=0){print(w-1);for(i=l;i<=w;i++)printf("%3d”，w);printf("");}}调用语句print(4)的结果是3.深度为5的二叉树最多有彳'结点(根结点层数为1)o4•对N个元素

5、的序列进行起泡排序时，最少的比较次数是四.应用题：（每小题6分，共30分）1.已知一棵二叉树T的先序序列为：EBADCFHGIKJ,中序序列为：ABCDEFGHIJK,试画出该二叉树及其对应的树。2.设散列表长度为11,散列函数H（k）=（k的第一个字母在英文字母表中的序号）MOD11,若输入顺序为（Blue,Dark,Red,White,Yellow,Green,Purple）,（1）用线性探测开发定址法解决冲突构造散列表；（2）求在等概率情况下查找成功的平均查找长度。3.假设用于通信的电文由6个

6、字母组成，字母在电文中出现的频率分别为5,7,9,16,23,18,试为这6个字母设计哈夫曼编码。1.给定一组关键码{18,31,16,22,51,30,24},画出执行直接插入排序的过程及堆排序过程。1.已知带权的无向图的邻接矩阵如下:U0019fioo1912«»888U10U10oo画出该图及其最小生成树。五.算法设计：(每小题10分，共30分)1.编写算法，求二叉树中度为2结点个数。1.试写一算法，对n个关键字取非零整数的记录序列进行整理，使得在尽可能少的时间内将所有取奇数的关键字放在所有取

7、偶数的关键字之前，要求所写算法的时间复杂度为0(n)。2.假设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构。请编写算法将A表和B表归并成一个按元素值递减有序排列的线性表C,并要求利用原表的结点空间。