华中农业大学07数据结构期末考试A卷

数据结构期末考试试卷（A卷）第1页共2页华南农业大学期末考试试卷（A卷）2007年1月考试科目：数据结构考试类型：（闭卷）考试时间：120分钟班级学号姓名考试须知：1．答案必须写在“答题卡”上，写在试卷上不得分。2．考试结束时，只回收答题卡，不回收试卷。3.必须在答题卡上正确填写班级、学号、姓名等内容，否则没有考试成绩一、选择题（每小题2分，共20分）1、下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。2、一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（B）。A.23415B.54132C.23145D.154323、串的长度是指（）A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数4、有n个顶点的有向图最多有(A)条边。A．nB．n(n—1)Cn(n+1)D.n25、就平均性能而言，目前最好的内排序方法是()排序法。A.冒泡排序B.希尔排序C.堆排序D.快速排序6、设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储地址为()。A.BA+141B.BA+180C.BA+222D.BA+2257．若循环队列用数组A[0,m-1]存放元素，其头尾指针分别为front和rear，则当前队列的长度是（）。A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.(rear-front)%m8、以下哪个数据结构，是非线性数据结构（A）。A.树B.字符串C.队列D.栈9、对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为：（1）8447251521（2）1547258421（3）1521258447（4）1521254784则采用的排序是()。A.选择排序B.冒泡排序C.快速排序D.插入排序10、线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）A．O（i）B．O（1）C．O（n）D．O（i-1）二、是非判断题（每小题1分，共10分）数据结构期末考试试卷（A卷）第2页共2页1、排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。错2、线性表的每一个结点都有一个前驱和一个后继。错3、给定一棵树，可以找到唯一的一棵二叉树与之对应。对4、在无向图中，边的条数是结点度数之和。错5、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。错6、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。错7、拓扑排序算法把一个无向图中的顶点排成一个有序序列。错8、排序的时间开销主要取决与算法执行中的比较次数。错9、带权连通无向图不仅可能有多棵生成树，其最小生成树也可能有多棵。对10、归并排序辅助存储为O（1）。错三、应用题（非计算机专业每题10分，计算机专业第一题6分，2-7题每题9分）1、设一棵二叉树的先序、中序遍历序列分别为：先序遍历序列：ABDFCEGH中序遍历序列：BFDAGEHC（1）画出这棵二叉树。（2）写出这颗二叉树的后序遍历序列。2、设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,利用赫夫曼算法设计一套二进制编码，请画出赫夫曼树并给出每个字符的赫夫曼编码。3、写出用Kruskal算法构造下图的一棵最小生成树的过程4、对长度为8的有序表，给出折半查找的判定树，给出等概率情况下的平均查找长度。5、使用哈希函数H(key)=keymod7，把一个整数值转换成哈希表下标，现将{19,24,10,17,15,38,18,40}依次插入到长度为10的哈希表中，使用线性探测法解决冲突。请构造哈希表并计算查找成功时的平均查找长度ASL。6、一组记录关键码为（49，38，65，97，76，13，27，49），使用快速排序，写出以第一个记录为基准的一次划分过程。7、判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。（1）100，85，98，77，80，60，82，40，20，10，66（2）100，98，85，82，80，77，66，60，40，20，10（3）100，85，40，77，80，60，66，98，82，10，20（4）10，20，40，60，66，77，80，82，85，98，100四、算法设计题（计算机专业做，10分）设有一线性表A=（a0,a1,...,ai,...an-1），其逆线性表定义为A'=(an-1,...,ai,...,a1,a0)，设计一个算法，将线性表逆置，要求线性表仍占用原线性表的空间，线性表采用顺序存储结构。