《太原理工大学_s数据结构》由会员分享，可在线阅读，更多相关《太原理工大学_s数据结构（7页珍藏版）》请在金锄头文库上搜索。
1、 考试类型： 闭卷闭卷 参考答案参考答案太原理工大学太原理工大学 数据结构数据结构(A)(A) 试卷试卷题 号一二三四五六七八九总分得分 一判断题：（每小题一判断题：（每小题 2 2 分，共分，共 2020 分）分）1 1链栈的初始化是指开辟足够多的结点，然后置栈顶指针为链栈的初始化是指开辟足够多的结点，然后置栈顶指针为 NULLNULL。 （ ）2 2数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式 。 （ ）3 3线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。线性表采用链表存储时，结点和结点内部
2、的存储空间可以是不连续的。 （ ）4 4在顺序存储结构中，有时也存储数据结构中元素之间的关系。在顺序存储结构中，有时也存储数据结构中元素之间的关系。 （ ）5 5数据的逻辑结构说明数据元素之间的顺序关系数据的逻辑结构说明数据元素之间的顺序关系, ,它依赖于计算机的储存结它依赖于计算机的储存结 构。构。 （ ）6 6完全二叉树的某结点若无左孩子，则它必是叶结点。完全二叉树的某结点若无左孩子，则它必是叶结点。 （ ）7 7用邻接矩阵表示图时，矩阵元素的个数与边的条数有关。用邻接矩阵表示图时，矩阵元素的个数与边的条数有关。 （ ）8 8二叉树有五种基本形态。二叉树有五种基本形态。 （ ）9 9图的深
3、度优先搜索序列和广度优先搜索序列不是唯一的。图的深度优先搜索序列和广度优先搜索序列不是唯一的。 （ ）1010用简单选择排序算法，只需一趟扫描即可选出键值最大（或最小）的元用简单选择排序算法，只需一趟扫描即可选出键值最大（或最小）的元 素素 。（。（ ）二选择题：（每小题二选择题：（每小题 2 2 分，共分，共 1010 分）分）1 1二维数组二维数组 A A 的成员是的成员是 6 6 个字符（每个字符占一个存储单元）组成的串，行个字符（每个字符占一个存储单元）组成的串，行 下标下标 i i 的范围从的范围从 0 0 到到 8 8，列下标，列下标 j j 的范围从的范围从 1 1 到到 101
4、0，A A 的第的第 8 8 列和第列和第 5 5 行共行共 占占 ( ( 2 2 ）个字节。）个字节。（1 1）108108 （2 2）6060 （3 3）5454 （4 4）1141142 2表达式表达式 a*(ba*(bc)+dc)+d 的后缀表达式是的后缀表达式是( ( 2 2 ）。）。（1 1）abcd*abcd*+ + （2 2）abcabc*d+*d+ （3 3）abc*abc*d+d+ （4 4）+ +*abcd*abcd3 3对于有对于有 N N 个结点高度为个结点高度为 K K 的满二叉树的满二叉树( (结点编号为结点编号为 1 1 到到 N N，根结点的层数，根结点的层数
5、 为为 1)1)，其第，其第 K K 层上最后层上最后 1 1 个结点的编号为个结点的编号为 ( ( 4 4 ) )。（1 1）2 2K K （2 2）2 2K K1 1 （3 3）2 2K K1 11 1 （4 4）2 2K K1 1 4 4一个有一个有 N N 个顶点的无向图最多有（个顶点的无向图最多有（ 3 3 ）条边。）条边。（1 1）N N （2 2）N*(NN*(N1)1) （3 3）N*(NN*(N1)/21)/2 （4 4）2*N2*N5 5有一个长度为有一个长度为 1212 的有序表，按二分查找法对该表进行查找，在表内各元的有序表，按二分查找法对该表进行查找，在表内各元 素等
6、概率情况下查找素等概率情况下查找 成功所需的平均比较次数为（成功所需的平均比较次数为（ 3 3 ）。）。（1 1）43/1243/12 （2 2）39/1239/12 （3 3）37/1237/12 （4 4）35/1235/12 三填空题：（每空三填空题：（每空 2 2 分，共分，共 1010 分）分）1 1对于一个具有对于一个具有 N N 个结点的单链表，在已知个结点的单链表，在已知 P P 所指结点后插入一个新结点的所指结点后插入一个新结点的 时间复杂度是时间复杂度是_O(1)_O(1)_；在给定值为；在给定值为 X X 的结点后插入一个新结点的时间复的结点后插入一个新结点的时间复 杂度
7、是杂度是_O(n)_O(n)_。2 2有如下递归过程：有如下递归过程：VoidVoid print(intprint(int w)w) intint i;i;ifif (w!=0)(w!=0) print(wprint(w1);1);forfor (i=1;ilchild,lptr);/复制左子树到 lptrCopyTree(S-rchild,rptr);/复制右子树到 rptrT=(BiTree)malloc(sizeof（BiNode);T-data=S-data;T-lchild=lptr;T-rchild=rptr;/else/CopyTreeint TwoNodesNum(BiTree T)int i,j;if(T=NULL)return 0;else if(T-lchild!=0elsei=TwoNodesNum(T-lchild);j=TwoNodesNum(T-rchild);return i+j;1 1编写算法编写算法, ,求二叉树中度为求二叉树中度为 2 2 结点个数。结点个数。
