3.12.35门专业课05试卷数据结构12本a

1、二、填空题（本大题共 10 小题，每小题 2 分，共 20 分）一个数据结构在计算机中的表示(映象)称为 。设长度为 n 的线性表顺序存贮,若在它的第 i-1 和第 i 个元间一个元素, 共需移动 个元素(1next = HL;一个由指针p 指向的结点，则执行B.p-next = HL; HL = p;D.p-next = HL-next; HL-next = p;（）C.p-next = HL;p = HL;3.依次进入一个栈的元素序列为 a,b,c,d,不到出栈的元素序列有C.b,a,d,c（）A.a.b,c,dB.a,d,c,bD.c,d,a,b下列哪棵树是满二叉树 A.二叉排序树C.有

2、 14 个结点的完全二叉树无向完全图的邻接矩阵是什么矩阵（）三、算法应用题（本大题共 5 小题，每小题 6 分，共 30 分）B.深度为 5 有 31 个结点的二叉树D.(Huffman)树21.对于给定的一组关键字：42,20,17,13,28,14,23,15 画出冒泡排序的各趟结果。（）A.对称B.上三角C.下三角D.稀疏6.有n(n0)个结点的完全二叉树的深度（）A.log2(n)+1 7.对有 3600 个A.1800B.log2(n)-1C.log2(n)-1D.log2(n)+1的索引顺序表(分块表)进行查找,最理想的块长为（）D.log2 3600B.60C.1200查找哈希(

3、Hash)表,解决 A.除留余数法C.直接地址法下列数据中，哪个是非线性数据结构的的方法有（）B.线性探测再散列法D.链地址法（）22.已知一个稀疏矩阵如下图具有 6 行7 列的一个稀疏矩阵所示：A.栈B.队列C.完全二叉树D.线性表0084000000-3000000001010.从逻辑上可以把数据结构分为两大类A.动态结构、静态结构（）B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构得分得分评卷人得分评卷人得分评卷人题目一二三四五六七八总分核分人题分2020301020100得分0000-70000506000020000（1）写出它的三元组线性表；（2） 给出它的顺

4、序表示；（3）给出它的转置矩阵的三元组线性表和顺序表示。24.给出图 2 的深度优先搜索遍历方法遍历图，并用 Prim 算法画出最小生成树。A1BF24342CDGH21123.将图 1林转换成二叉树，并中序遍历二叉树。EACE图 2 无向图BGHDF图 1 二叉树得分得分if (s-top=MaxSize-1)return 0;/*栈满的情况，即栈上溢出*/s-datas-top=e;return 1;25.给定权值（2，3，2，1，5，6，7，8），构造相应的WPL。树，并给出带权路径长度27.Pop(SqStack *&s,ElemType &e)if (s-top=-1)return

5、0;e=s-datas-top;/*栈为空的情况，即栈下溢出*/return 1;28.deQueue(Sueue *&q,ElemType &e)if () return 0;q-front=(q-front+1)%MaxSize;return 1;四、程序填空（本大题共 4 小题，每空 2 分，共 10 分）29.enQueue(Sueue *&q,ElemType e)26.Push(SqStack *&s,ElemType e)if ()得分评卷人得分得分得分得分得分return 0;q-rear=(q-rear+1)%MaxSize; q-dataq-rear=e;return 1;五、算法设计（本大题共 2 小题，每小题 10 分，共 20 分）31.假设二叉树采用二叉链子结点的个数。结构，试设计一个算法，统计一棵给定二叉树的所有叶30.将一个单链表的线性