2022年太原理工大学数据结构试卷 .pdf

《2022年太原理工大学数据结构试卷 .pdf》由会员分享，可在线阅读，更多相关《2022年太原理工大学数据结构试卷 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、多练出技巧巧思出硕果数据结构试卷（B）一选择题：（每小题 2 分，共 20 分）1下列关键字序列中，构成大顶堆的是( 2 )。（1）84 ，41，62，46，28，58，15，37 （2）84 ，62，58，46，41，37，28，15 （3）15 ，28，46，37，84，41，58，62 （4）15 ，28，46，37，84，58，62，41 2. 深度为 7 的二叉树最多有（ 2 ）个结点。（1）63 （2）64 （3）127 （4）128 34 个元素 a1，a2，a3 和 a4 依次通过一个栈，在a4 进栈前，栈的壮态是：可能的出栈序是（2 ） 。（1）a3，a1，a4，a2 （2）

2、a3，a2，a4，a1 （3）a4，a2，a3，a1 （4）a3，a4，a1，a2 4 对于有 N个结点的完全二叉树 ( 结点编号为 1 到 N)， 当 2*K+1=N时，编号为 K的结点的右子女编号为 ( 2 ） 。（1）2*K （2）2*K+1 （3）2*K+2 （4）K+2 5一棵二叉排序树T，用（3 ）方法进行遍历，可以得到各结点键精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 5 页多练出技巧巧思出硕果值的有序序列。（1）层次遍历（2）后根遍历（3）中根遍历（4）先根遍历6对于三个结点ABC ，可构成（ 3 ）棵不同的二叉树。

3、（1）4 （2）5 （3）30 （4）6 7 在下列对顺序表进行的操作中， 算法时间复杂度为O(n)的是 （ 1 ） 。（1）删除第 i 个元素(1 i n) （2）在第 n 个元素之后插入一个新元素(n 为表长 ) （3）访问第 i 个元素的前驱 (1 i n) （4）对顺序表中元素进行排序8有二维数组 B1 10，1 10按行优先顺序存放，设B1，1 的存储地址为 300，每个元素占 3 个单元，则 B3，2 的地址是（ 4 ） 。（1）372 （2）378 （3）366 （4）363 9组成数据的基本单位是（ 2 ） 。（1）数据项（2）数据元素（3）数据类型（4）数据变量10 用二叉链

4、表表示具有n 个结点的二叉树时，值非空的指针域的个数为( 3 )。（1）n+l （2）n （3）n-1 （4）2n 二判断题： （每小题 2 分，共 20 分）1单链表的每个结点中，都恰好包含一个指针。（）2. 堆栈既可顺序存储又可链接存储。（）3对于含有 N个顶点的有向图，其邻接矩阵是对称的。（）4在按关键字递增的数组A29 中，按折半查找方法进行查找时，查找长度为 5 的元素个数为 15 。（ ）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 5 页多练出技巧巧思出硕果5 给定一棵二叉树的先序和后序序列， 可唯一确定这棵二叉树。（）

5、6完全二叉树的某结点若无左孩子，则它必是叶结点。（）7. 二叉树有五种基本形态。（）8对于 N个顶点的连通图，至少有N*(N1)/2 条边。（）9数据的逻辑结构与数据元素的形式无关。（）10每一棵树都有唯一的一棵二叉树与之对应。（）三应用题：（每小题 5 分，共 35 分）1画出下图所示的二叉树对应的森林，写出对此二叉树后序遍历的结点序列。 【P41】2已知一个无向图的邻接表如下图所示，画出这个图，并给出以A 为出发点对图进行深度优先搜索遍历的顶点序列。3画出在有序表 12 ，15，18，20，26，31，35，40，46，65，90上进行折半查找关键字26 的过程，并指出在查找过程中进行了哪

6、些关键字的比较。4给定一组关键码 32，28，12，26，53，67，26 ，画出执行直接插精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 5 页多练出技巧巧思出硕果入排序的过程。5从空树起，依次插入关键字41，52，46，18，20，12，86，30，21，构造一棵二叉排序树。画出该二叉排序树，并求等概率情况下查找成功的平均查找长度。6设散列表长度为11，散列函数 H（k）（ k 的第一个字母在英文字母表中的序号） MOD 11， 若输入顺序为（Apple， pear， orange， banana，grape，mango ，wate

7、rmelon ） ，（1）用线性探测开发定址法解决冲突构造散列表；(2) 求在等概率情况下查找成功的平均查找长度。7. 已知一棵度为 5 的树。 其中度为 1 的结点 6 个， 度为 2 的结点 5 个，度为 3 的结点 4 个，度为 4 的结点 2 个，度为 5 的结点 3 个，试计算该树中叶结点个数。四算法设计：（第 1 小题 12 分，第 2 小题 13 分，共 25 分）1试编写一个算法 . 实现单链表的就地逆置。/ 带头结点的单链表的逆置Status ListOppose_L(LinkList &L) LinkList p,q; p=L; p=p-next; L-next=NULL;

8、 while(p) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 5 页多练出技巧巧思出硕果q=p; p=p-next; q-next=L-next; L-next=q; return OK; 2编写递归算法 , 求二叉树中结点个数。/ 求二叉树中叶子结点的数目Status POLeafNodeNum(int& i,BiTree& T) if(T)if(!T-lchild & !T-rchild) i+; POLeafNodeNum(i,T-lchild); POLeafNodeNum(i,T-rchild); return OK; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 5 页