2019年10月自学考试02331《数据结构》试题.docx

《2019年10月自学考试02331《数据结构》试题.docx》由会员分享，可在线阅读，更多相关《2019年10月自学考试02331《数据结构》试题.docx（8页珍藏版）》请在第一文库网上搜索。

1、2019年工O月高等教育自学考试数据结构试题课程代码：02331一、单项选择题1 .下列选项中，不宜采用链式存储的是A.无向图B.单链表C.最优二叉树D.数组2 .将10个数据元素保存在顺序栈S中，若栈顶元素的存储地址是100,栈中每个元素占4个存储单元，进栈按S.top=S.top+1修改栈顶，则栈底元素的存储地址是A.60B.64C.136D.1403 .设指针变量head指向循环链表的头结点，next是结点的指针域，则判断此链表为空的条件是A.head-next=NU11B.head-next=headC.head-next!=NU11D.head-next!=head-next4 .己

2、知广义表1S=(a,b,c),(d,(e),(f,(g),(h,9),i，1S的深度是A.4B.3C.2D.15 .己知一棵完全二叉树T共有7个分支结点，则T中叶子结点个数最少是A.7B.8C.9D,106 .在一棵非空二叉树的后序遍历序列中，所有列在根结点前面的是A.左子树中的部分结点B.右子树中的全部结点C.左右子树中的全部结点D.左右子树中的部分结点7 .用邻接表保存有n个顶点和e条边的无向图，邻接表中指针个数是A.eB.n-eC.n+eD.n+2e8 .有向图G中某个顶点的出度和入度均为2,则G中的顶点个数最少是A.2B.3C.4D.59 .在带权图的最短路径问题中，路径长度是指A.路

3、径上边的数目B.路径上结点的数目C.路径上边的权值之和D.到达终点的最短路径数目.10 .对数据序列(15,10,8,12,15,8,10)按升序进行希尔排序，增量序列为5,3,两趟排序后，得到的排序结果为A.8,8,10,10,15,15,12B.8,8,10,10,12,15,15C.8,10,8,10,15,15,12D.8,10,8,10,12,15,1511 .下列排序方法中，不稳定的排序方法是A.直接选择排序B.归并排序C.直接插入排序D.基数排序12 .一组记录的关键字为(35,58,24,13,44,19,10),利用堆排序算法进行降序排序，要求空间复杂度为0(，建立的初始堆为

4、A.10,13,19,58,44,35,24B.10,13,35,58,44,19,24C.58,44,24,13,35,19,10D.58,35,24,13,44,19,1013 .一棵二叉排序树中，关键字n所在结点的层数大于关键字m所在结点的层数，则A.n一定大于mB.n一定小于mC.n一定等于mD.n与m的大小关系不确定14 .设散列表长m=10,散列函数H(key)=key%90表中已保存3个关键字：H(13)=4,H(32)=5,H(15)=6,其余地址均为空。保存关键字23时存在冲突，采用线性探查法来处理。则查找关键字23时的探查次数是Ao1B.2C.3D.415 .下面关于m阶(

5、m23)B树的叙述中，正确的是A.终端结点可位于不同层B.非终端结点至多有m+1棵子树C.若树非空，则根结点至少有2个关键字D.每个非根结点包含n个关键字，m2-1nm-1二、填空题16 .数据的四种基本存储方法是顺序存储、链接存储、和散列存储。17 .指针P和指针q分别指向单链表1中的两个结点，next为指针域，则判断这两个结点是否相邻的条件是。18 .递归求解过程中的最小子问题称为o19 .广义表(包力),(娘),(8),11)的表头是o20 .3个结点的不同形状的二叉树有棵。21 .若有向无环图G存在2个入度为。的结点，则G至少存在个不同的拓扑序列。22 .将一棵树T转换为一棵二叉树，则

6、这棵二叉树的右子树o23 .对含n个元素的数据序列采用直接选择排序算法进行排序，最好情况下的时间复杂度是o24 .散列存储中，拉链法(链地址法)是处理的方法。25 .假设顺序存储的有序表R含有14个关键字，进行二分查找时，查找失败时关键字的最大比较次数为。三、解答题26 .设电文字符集是,G，/，/，%，.，它们出现的次数分别为：38,12,17,26,14,20o现要为该字符集设计一种哈夫曼编码。请回答下列问题。(1)画出得到的哈夫曼树。(2)给出各符号的哈夫曼编码。.已知图G采用邻接矩阵存储，邻接矩阵如题27图所示。写出从顶点A开始到顶点C结束、包含所有顶点的2个深度优先遍历序列写出从顶点

7、A开始的3个广度优先遍历序列。27 .有以下关键字序列(15,20,24,32,15,7,14,23),使用快速排序方法将其按升序排列。请回答下列问题。(1)若取第一个关键字为基准，写出第一趟快速排序的结果。(2)若取最后一个关键字为基准，写出第一趟快速排序的结果。.设有二叉排序树T如题29图所示。请回答下列问题。题29图(1)画出插入新结点f后的二叉排序树T1o(2)在T1中再删除结点c得到二叉排序树T2,画出T2,并简要说明删除过程。四、算法阅读题28 .顺序表类型定义如下。#define1istSize100typedefstructintdata1istSize;int1ength;S

8、eq1ist;voidf30(Seq1ist*S1,int*pdata,intn)intk,m;for(k=O;kdataS1-1ength=pdatak;e1sefor(m=S1-1ength;mO;m)S1-datam=S1-datam-1;S1-dataO=pdatak;S1-1ength+;voidout(Seq1ist*S1ist)intk=O;whi1e(k1ength)/顺序输出S1ist中的各个元素printf(%d,S1ist-datak+);)intmain()intarray=10,2,9,5,30,3;Seq1istMist;Mist,1ength=O;(&s1ist,

9、array,sizeof(array)sizeof(int);out(&s1ist);输出s1istreturnO;(1)执行程序后程序的输出是什么？(2)函数DOO的功能是什么？29 .二叉树的存储结构类型定义如下。/data:是数据域typedefintDataType;typedefstructnodeDataTypedata;stmctnode*1chi1d,*rchi1d;/分别指向左右孩子BinTNode;typedefBinTNode*BinTree;阅读下列函数并回答问题。voidf31(BinTreeBt)if(Bt!=NU11).,if(Bt-1chi1d=-NU11&Bt

10、-rchi1d=NU11)Bt-data=Bt-data*2;e1sef31(Bt-1chi1d);1(Bt-rchi1d);设二叉树Bt如题31图所示，给出执行f31(Bt)的输出结果。(2)该算法的功能是什么？32.待查找记录的数据类型定义如下。/defineMAXSIZEIOOtypedefintKeyType;typedefstructKeyTypekey;RecType;typedefRecTypeSeq1istMAXSIZE;下列算法实现对按升序排列的数据进行二分查找。请在空白处填上适当内容使算法完整。ihtBinSearch(Seq1istR,KeyTypek,intn)int1

11、ow=O,high=n-1,mid;whi1e(1owk)high(2).;e1se1ow=(3);)return-1;)33.二叉树的存储结构类型定义如下。/data是数据域，其值大于0typedefintDataType;typedefstructnodeDataTypedata;Structnode*1chi1d,*rchi1d;/分别指向左右孩子BinTNode;typedefBinTNode*BinTree;下列程序的功能是：将一棵二叉树的顺序存储结构转换为对应的链式存储结构。例如，对如题33图所示的二叉树，二叉树的顺序存储序列如下。intdata=30,20,0,0,90,0,0,

12、0,0,100；题33图程序如下：BinTreecreate(int*data,intn)BinTNode*Q100,*Bt=NU11,*p;intfront=0,rear=0,k;for(k=0;k(n;k+)p=NU11;if(datak!=0)p=(BinTree)ma11oc(sizeof(BinTNode);p-data=datak;p-Ichi1d=p-rchi1d=NU11;)Qrear+=p;if(rear=1)Bt=p;if(p!=NU11&(1)if(2)=0)Qfront-1chi1d=p;e1seQfi,ont-rchi1d=p;if(rear%2!=O)returnBt;)请在程序的空白处填入适当的语句，使程序完整正确。五、算法设计题34.单链表类型定义如下。typedefstructnodeintdata;stmctnode*next;1istNode;typedef1istNode*1ink1ist;请编写一个函数，在带头结点的单链表1中删除数值在指定范围内(XWdataWy)的结点。函数的原型如下。Vbidf34(1ink1ist1,inty)；例如，对于如下的链表head,要删除链表中data在4到7范围内的结点，可调用函数C4(head,4,7),结果如下。