资源描述：
《《数据结构教学资料》太原理工大学数据结构试卷》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、4、不笊〉天逢TAIYUANUNIVERSITYOFTECHNOLOGY数据结构试卷（B）一.选择题：（每小题2分，共20分）(1){84,41,62,46,28,58,15,37}(2){84,62,58,46,41,37,28,⑸(3){15,28,46,37,84,41,58,62}(4){15,28,46,37,84,58,62,41}2.深度为71的二叉树:最多有（2)个纟吉点。(1)63(2)64(3)127(4)1.下列关键字序列中，构成人顶堆的是（2）。1283.4个元索al,a2,a3和M依次通过一个栈，在M进栈前，栈的壮
2、态是：可能的出栈序是（2）。（1）a3,al,a4,a2（2）a3,a2,a4,al（3）a4,a.2,a3,al（4）a3,a4,al,a24•对于有N个结点的完全二叉树（结点编号为1到N）,当2*K+1V二N时,编号为K的结点的右子女编号为（2）。(1)2*K(2)2*K+1(3)2*K+2(4)K+25.一棵二叉排序树T,用（3）方法进行遍历，可以得到各结点键值的有序序列。（1）层次遍历（2）后根遍历（3）中根遍历（4）先根遍历6.对于三个结点A、B、C,可构成（3）棵不同的二叉树。（1）4（2）5（3）30（4）67•在下列对顺序表
3、进行的操作中，算法时间复杂度为0（n）的是（1）。（1）删除第i个元素（lWiWn）（2）在第n个元素之后插入一个新元素（n为表长）（3）访问第i个元素的前驱（lWiWn）（4）对顺序表屮元索进行排序8.有二维数组B[l・・10,1・・10]按行优先顺序存放，设B[l,1]的存储地址为300,每个元素占3个单元，则B[3,2]的地址是（4）。（1）372（2）378（3）366（4）3639.组成数据的基本单位是（2）o（1）数据项（2）数据元素（3）数据类型（4）数据变量10.用二叉链表表示具有n个结点的二叉树时，值非空的指针域的个数为（
4、3）。（1）n+1（2）n（3）n-1（4）2n一.判断题：（每小题2分，共20分）1.单链表的每个结点中，都恰好包含一个指针。（X）2.堆栈既可顺序存储又可链接存储。（7）1.对于含有N个顶点的有向图，其邻接矩阵是对称的。（x）4、不絶》天逢TAIYUANUNIVERSITYOFTECHNOLOGY1.在按关键字递增的数组A[29]中，按折半查找方法进行查找时，查找长度为5的元素个数为15。（x）5•给定一棵二叉树的先序和后序序列，可唯一确定这棵二叉树。（x）6.完全二叉树的某结点若无左孩子，则它必是叶结点。（＜）7.二叉树有五种基本形态
5、。（7）8.对于N个顶点的连通图，至少有N*（N-l）/2条边。（x）9.数据的逻辑结构与数据元素的形式无关。（V）10.每一棵树都有唯一的一棵二叉树与之对应。（7）一.应用题：（每小题5分，共35分）1.画出下图所示的二叉树对应的森林，写出对此二叉树后序遍历的结点序列。【P41】2.已知一个无向图的邻接表如下图所示，画出这个图，并给出以A为1A-2—>032B5->nn—>1A3C44：D3■1—>
6、24-*1A5E—►3->
7、2
8、A]出发点对图进行深度优先搜索遍历的顶点序列。3.画出在有序表{12,15,18,20,26,31,35,4
9、0,46,65,90}上进行折半查找关键字26的过程，并指出在查找过程中进行了哪些关键字的比较。1.给定一组关键码{32,28,12,26,53,67,26},画出执行宜接插入排序的过程。2.从空树起，依次插入关键字41,52,46,18,20,12,86,30,21,构造一棵二叉排序树。画出该二叉排序树，并求等概率情况下查找成功的平均查找长度。3.设散列表长度为11,散列函数H(k)=(k的第一个字母在英文字母表中的序号)MOD11,若输入顺序为(Apple,pear,orange,banana,grape,mango,watermelo
10、n),(1)用线性探测开发定址法解决冲突构造散列表；(2)求在等概率情况下查找成功的平均查找长度。4.已知一棵度为5的树。其中度为1的结点6个，度为2的结点5个，度为3的结点4个，度为4的结点2个，度为5的结点3个，试计算该树中叶结点个数。一.算法设计：(第1小题12分，第2小题13分，共25分)1.试编写一个算法•实现单链表的就地逆置。//带头结点的单链表的逆置StatusListOppose_L(LinkList&L)LinkListp,q;p=L;p=p->next;L->next=NULL;while(p){q=p；p=p->nex
11、t;q->next=L->next;L->next=q;}returnOK;}1.编写递归算法，求二叉树中结点个数。//求二叉树中叶子结点的数目StatusPOLeafNodeN
