《2022年太原理工大学数据结构试卷.docx》由会员分享，可在线阅读，更多相关《2022年太原理工大学数据结构试卷.docx（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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、是（2 ）；（1）a3,a1,a4,a2 （3）a4,a2,a3,a1 （2）a3,a2,a4,a1 （4）a3,a4,a1,a2 4对于有 N个结点的完全二叉树 结点编号为 1 到 N,当 2*K+1=N时,名师归纳总结 编号为 K的结点的右子女编号为 2 ）；第 1 页,共 5 页（1）2*K （2）2*K+1 （3）2*K+2 （4）K+2 5一棵二叉排序树T,用（3 ）方法进行遍历,可以得到各结点键- - - - - - -精选学习资料 - - - - - - - - - 多练出技巧 巧思出硕果值的有序序列；（1）层次遍历（2）后根遍历（3）中根遍历（4）先根遍历6对于三个结点 ABC
3、,可构成（ 3 ）棵不同的二叉树；（1）4 （2）5 （3）30 （4）6 7在以下对次序表进行的操作中, 算法时间复杂度为 On的是（ 1 ）；（1）删除第 i 个元素 1 i n （2）在第 n 个元素之后插入一个新元素 n 为表长 （3）拜访第 i 个元素的前驱 1 i n （4）对次序表中元素进行排序8有二维数组 B110,110 按行优先次序存放,设 B1,1 的存储地址为 300,每个元素占 3 个单元,就 B3,2 的地址是（ 4 ）；（1）372 （2）378 （3）366 （4）363 9组成数据的基本单位是（ 2 ）；（4）数据变量（3）数据类型（1）数据项（2）数据元素1
4、0 用二叉链表表示具有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*N 1/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_LLinkList &L LinkList p,q; p=L; p=p-next; L-next=NULL; whil
8、ep 名师归纳总结 - - - - - - -第 4 页,共 5 页精选学习资料 - - - - - - - - - 多练出技巧 巧思出硕果q=p; p=p-next; q-next=L-next; L-next=q; return OK; 2编写递归算法 , 求二叉树中结点个数；/ 求二叉树中叶子结点的数目 Status POLeafNodeNumint& i,BiTree& T ifTif.T-lchild & .T-rchild i+; POLeafNodeNumi,T-lchild; POLeafNodeNumi,T-rchild; return OK; 名师归纳总结 - - - - - - -第 5 页,共 5 页