2023年数据结构_期中试卷含超详细解析答案.pdf

《2023年数据结构_期中试卷含超详细解析答案.pdf》由会员分享，可在线阅读，更多相关《2023年数据结构_期中试卷含超详细解析答案.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-欢迎下载 一、选择题（每小题 1 分，共 10 分）1、队列是插入和删除受限的线性表，其删除操作是在线性表的 （1）进行。A表头 B表尾 C任意位置 D指定位置 2、下述哪一条是顺序存储结构的优点？（2）。A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示 3、设有一个栈，元素的进栈次序为 A,B,C,D,E，下列哪个是不可能的出栈序列 （3）。AA,B,C,D,E BB,C,D,E,A CE,A,B,C,D DE,D,C,B,A 4、若二叉树的根结点所在的层次为第 1 层，则该二叉树的第 k 层上至多有 （4）个结点。A.12k B2k C2k-1 D2k+

2、1 5、设单链表中指针 p 指向结点 m，若要删除 m 的后继结点（假设该后继结点存在），则需修改指针的操作为 （5）。Ap-next=p-next-next;Bp=p-next;Cp=p-next-next;Dp-next=p;6、下面程序段的时间复杂度为 （6）。for(int i=0;im;i+)for(int j=0;jnext=head Dp-next=NULL 8、已知二维数组 A0.9,0.9 中，元素 a20 的地址为 560，每个元素占 4 个字节，则元素a10 的地址为 （8）。A.518 B.520 C.522 D.524 9、在具有 n 个单元的顺序存储的循环队列中，假

3、定 front 和 rear 分别为队头指针和队尾指针，则判断队满的条件为 （9）。Arearn=front B（front+l）n=rear Crearn-1=front D(rear+l)n=front 10、假设在一棵二叉树中，度为 2 的结点数为 15，度为 1 的结点数为 10 个，则该二叉树的分支总数为 （10）个。A.41 B.40 C.30 D.25-欢迎下载 二、填空题（每空 2 分，共 20 分）1.一棵深度为 k 的完全二叉树（假定根结点所在的层次为第 1 层），则其结点总数的最小值为 （1），最大值为 （2）。2对于一个具有 n 个结点的单链表（n1），在指针变量 p

4、指向的结点后插入一个新结点的时间复杂度为 （3），在给定值为 x 的结点后插入一个新结点的时间复杂度为 （4）。3.设有一空栈，现有输入序列 A，B，C，D，E，经过 push,push,pop,push,pop,push,push后，此时的输出序列为 （5）。4.有一个 100*90 整型数据的稀疏矩阵，非 0 元素有 10 个，设每个整型数据占 2 字节，则用三元组表示该矩阵时，所需的字节数是 （6）。5.设栈 S 和队列 Q 初始为空。6 个元素依 a,b,c,d,e,f 的顺序通过栈 S，一个元素出栈后立即进入队列 Q。若这 6 个元素出队的序列为 d,c,b,f,e,a，则栈 S 的

5、最小容量需 （7）。6.若对 n 阶对称矩阵 A0.n-1,0.n-1 以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组 B1.(n(n+1)/2 中，则在 B 中确定 aij（ij）的位置 k 的关系为 （8）。7.表达式 a+(b*c-d)/e+f*g/h)+x/y 对应的后缀表达式是 （9）。8.若 INDEX（S，T）表示求 T 在 S 中的位置的操作，则对于 S=BeijingNanjing，T=jing，INDEX（S，T）=（10）。三、判断题（每小题 2 分，共 10 分，错误打，正确打）1 二叉树结构中，任何一个结点都有一个且仅有一个直接前驱和直

6、接后继。.()2在一棵二叉树中，假定每个结点只有左孩子，没有右孩子，对它分别进行中序遍历和后序遍历，则具有相同的结果。.()3.对线性链表来说，从任意结点开始均能扫描表中全部结点。.()4.线性表的特点是每个元素都有一个前驱和一个后继。.()5.栈和队列都是限制存取点的线性结构。.()四、简答题(本大题有 5 小题，共 40 分，每小题分值见各题标注)1（6 分）已知一棵二叉树如下，请分别写出按前序、中序、后序遍历时得到的字符序列。A B C-欢迎下载 D E F G H I J 2（6 分）设 x，n 为整型变量，且 n0，下面程序片段中语句 x/=2 执行次数的数量级是多少？试进行分析。用

7、“O”记号表示。x=n*n;while(x=1)x/=2;3（8 分）用栈实现将中缀表达式：8*(3+5)+5/3#转换成后缀表达式，画出栈的变化过程图（符号“#”为表达式结束符）。4（10 分）已知一棵二叉树的中序序列和后序序列分别是 BDCEAFHG 和 DECBHGFA，请画出这棵二叉树，并写出对其先序遍历的序列。5.（10 分）线性表有两种常用存储结构：一是顺序表，二是线性链表。试问：（1）如果有 n 个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动的改变。在此情况下，应选用哪种存储结构？为什么？（2）若线性表的总数基本稳定，且很少进行插入和删除操作，但要求

8、以最快的速度存取线性表中的元素，那么应采取哪种存储结构？为什么？五、算法题(本大题有 2 小题，每题 10 分，共 20 分)1.以下算法利用栈的基本操作将一个十进制正整数转换成二进制正整数，填空完善之。void conversion()InitStack(S);scanf(%d,&x);while(x!=0)push(S,（1）);x=x/2;while(!StackEmpty(S)（2）;printf(%d,x);注：栈的基本操作如下：-欢迎下载 InitStack(s)：初始化一个栈；Push(s,x)：元素 x 进栈；Pop(s,x)：栈顶元素出栈；GetTop(s,x)：读出栈顶元素

9、；StackEmpty(s)：判栈是否为空。2.编写二叉树（以二叉链表存储）先序遍历的递归算法。-欢迎下载 答案 一、选择题(每小题 1 分，共 10 分)15.A A C A A 6.10.D C B D B 二、填空题（每空 2 分，共 20 分）1.【1】2k-1+1 【2】2k-1 2.【3】O(1)【4】O(n)3.【5】B C 4.【6】60 5.【7】4 6.【8】7.【9】8.【10】4 三、判断题（每小题2 分，共 10 分，错误打，正确打）1 2 3 4 5 四、简答题(本大题有 5 小题，共 40 分，每小题分值见各题标注)1（6 分）解：前序遍历：A，B，D，E，G，H

10、，J，C，F,I .(2 分)中序遍历：D，B，G，E，J，H，A，C，I，F .(2 分)后序遍历：D，G，J，H，E，B，I，F，C，A .(2 分)-欢迎下载 2（6 分）解：根据题意，可知：第 1 次循环时，21*2xn；.(1 分)第 2 次循环时，221*2xn；第 3 次循环时，231*2xn；由此可作如下假设：当 x=1 或接近 1 时，已经循环了 k 次，则必有：21*12kxn，.(2 分)=22kn =22lognk =22lognk;所以，x/=2 执行次数的数量级是2(log)nO .(3 分)3（8 分）解：后缀式为：835+*53/+，(3 分)；栈的结构变化如下

11、图所示（每图 1 分）：(#*+(1)#*(2)/#+(3)#(4)(5)4（10 分）解：该二叉树如下：-欢迎下载 AHGEDCFB 先序遍历：A B C D E F G H .5 分 .5 分 5（10 分）解：（1）在此情况下，应该选择线性链表的存储结构，应为各表的长度经常动态变化，意味着此表经常进行插入和删除的操作，而对于链表来说，插入一个元素或删除一个元素的算法复杂度为 O(1)，比顺序存储结构的算法复杂度要小很多。.5 分（2）由于顺序存储结构对数据的存取方式是随机存取的，算法复杂度为 O(1)；而链表对数据的存取方式是顺序存取的，算法复杂度为 O(n)，所以应该选择顺序存储结构。.5 分 五、算法题(本大题有 2 小题，每题 10 分，共 20 分)1解：（1）x%2 .5 分 (2)Pop(S,x).5 分 2解：先序遍历递归算法如下：Status PreOrderTraverse(BiTree T,Status(*Visit)(TelemType e).2 分 If(T).2 分 If(Visit(T-data).2 分 If(PreOrderTraverse(T-lchild,Visit).2 分 If(PreOrderTraverse(T-rchild,Visit).2 分 return OK;Return ERROR;Else return OK;