闽江学院2014 12级 数据结构与算法试卷b卷

2013—2014学年第一学期闽江学院考试试卷考试课程：数据结构与算法试卷类别：B卷考试形式：闭卷适用专业年级：12电子信息工程、12电子科学与技术、12电子信息科学与技术装订线装订线题号一二三四五总分得分一、选择题（共15小题，每题2分）30%得分选择题答案填写处1234567891011121314151、栈和队列都是（）A．限制存取点的线性结构B．限制存取点的非线性结构C．顺序存储的线性结构D．链式存储结构的线性结构2、（）又称为FIFO表A．队列 B．散列表 C．栈 D．哈希表3、设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。A．O(n) B．O(nlog2n) C．O(1) D．O(n2)4、设一数列3,5,7,9通过栈结构，不可能的出栈序列为（）。A）7,5,3,9B）7,5,9,3C）9,7,5,3D）9,5,7,35、以顺序存储方式将完全二叉树中的所有结点逐层存放于数组A中，结点A[i]若有左孩子，则左孩子是结点（）。A.A[2*i]B.A[2*i+1]C.A[2*i+2]D.A[idiv2]6、某二叉树如图所示，对该二叉树进行先序遍历，结点的访问序列为（）。A.1,2,3,4,5,6,7B.1,2,4,6,7,3,5C.2,6,4,7,1,5,3D.6,7,4,2,5,3,17、在下列存储结构中，（）不是树的存储形式。A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法8、已知Huffman树的总结点数为m，叶子数为n。则m与n的关系是（）。A．m=2n+1B．m=n+1 C．m=2n–1 D．m=n–19、若从二叉树的任意结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是（）。A.满二叉树B.哈夫曼树C.堆D.二叉排序树10、对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵中元素的个数为（）。A.nB.(n-1)2C.(n+1)2D.n211、对图所示的无向图G，从顶点A开始，深度优先遍历，可能的顶点访问顺序为（）。A.A,B,E,C,D,FB.A,C,F,E,B,DC.A,B,C,D,E,FD.A,C,F,D,E,B12、有n个顶点的有向完全图中，具有（）条边。A.n(n-1)/2B.n(n-1)C.n(n+1)/2D.n213、用折半查找方法从长度为11的有序表中查找一个元素时，平均查找长度为（）。A.3B.4C.5D.614、以下序列中，（）才可能是执行第一趟快速排序后得到的序列。A．{8，6，18}19{6，10，50}B．{6，4，8}18{81，19，36，18}C．{81，1，2}36{99，81，69}D．{2，3，4}89{78，98，68}15、以下4种排序算法中，时间复杂度最小的是（）。A.插入排序B.选择排序C.冒泡排序D.归并排序二、填空题（共8小题，每空2分）20%得分1、实现函数递归调用的数据结构是。2、在一个单链表中，在指针p所指向的结点之后插入指针s所指向的结点时，应执行如下操作：s->next=；p->next=。3、栈中的第一个元素称为。队列的最后一个元素称为。4、n个结点的二叉链表中，共有2n个指针，其中有个指针用于指向左、右孩子，剩余的个指针为空。5、深度为5的二叉树至多有个结点。6、在n个顶点的有向图中，每个顶点的度最大可达。7、对于一个具有n个顶点e条边的无向图，若采用邻接表表示，则它的邻接表需n个表头结点和_______________个表结点。三、判断题（共10小题，每题1分）10%得分1、（）线性表的链式存储结构优于顺序存储结构。2、（）顺序存储结构不仅能用于表示完全二叉树，也能表示一般的二叉树。3、（）逆邻接表只能用于有向图的存储。4、（）n个带权叶子结点构成的哈夫曼树（最优二叉树）是唯一的。5、（）算法就是程序。6、（）对长度为n的线性表进行分块查找，其ASL的最小值是O()。7、（）对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。8、（）对n个元素的集合进行堆排序时，需要的辅助存储空间为O(n)。9、（）对链表进行插入和删除操作时不必移动链表中结点。10、（）堆是完全二叉树，完全二叉树不一定是堆。四、应用题（共5小题）30%得分1、已知一棵二叉树的层次遍历序列为ABCDEFGHIJ，中序遍历序列为DBGEHJACIF，试画出该二叉树。(5分)2、已知顺序表中存储的序列{19,14,22,1,66,21,83,27,56,13}，将元素按其在表中的次序依次插入到一棵初始为空的二叉排序树中，要求：（1）画出插入完成后的二叉排序树。(5分)（2）设各数据元素的查找概率相等，给出该二叉排序树的平均查找长度。（2分）3、设数据元素关键字序列为{475,137,481,219,382,674,350,326,815,506}，写出执行希尔排序（增量d=5,3,1）算法时，各趟排序后的关键字序列（最后结果为升序））。（3分）4、假设用于通信的电文仅由8个字母a，b，c，d，e，f,g,h组成，各字母的使用频率分别为16，3，9，8，4，10,5,6请画出本问题的哈夫曼树，并为这8个字母设计哈夫曼编码。（8分）5、设哈希表的长度为13，哈希函数为H(k)=k%13，关键字序列为（19,14,23,1,68,20,84,27,55,11,10,79）（1）试画出用线性探查法消解地址冲突时所构造的哈希表。（6分）（2）并求出以上哈希表的平均检索长度。（1分）五、编程题（共2小题，每题5分）10%得分1、以二叉链表为存储结构，写出求二叉树中叶子结点数的算法的递归函数。二叉链表的结点定义如下：typedefstructBiTNode{//结点结构TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;2、试写出直接插入排序的实现算法（最后结果为升序）。(5分)待排序文件中记录结构类型定义如下：typedefstruct{in