《2019年10月自学考试02331《数据结构》试题.docx》由会员分享，可在线阅读，更多相关《2019年10月自学考试02331《数据结构》试题.docx（7页珍藏版）》请在课桌文档上搜索。
1、2019年10月高等教育自学考试数据结构试题课程代码：02331一、单项选择题1 .下列选项中，不宜采用链式存储的是A.无向图B.单链表C.最优二叉树D.数组2 .将10个数据元素保存在顺序栈S中，若栈顶元素的存储地址是100,栈中每个元素占4个存储单元，进栈按S.top=S.lop+l修改栈顶，则栈底元素的存储地址是A.60B.64C.136D.1403 .设指针变量head指向循环链表的头结点，next是结点的指针域，则判断此链表为空的条件是A.head-next=NULLB.head-next=headC.head-next!=NULLD.head-next!=head-next4 .己
2、知广义表LS=(a,b,c),(d,(e),(f,(g),(h,9),i，LS的深度是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)按升序进行希尔排序,增量序列为序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,IOD.58,35,24,13,44,19,1013 .一棵二叉排序树中，关键字n所在结点的层数大于关键字m所在结点的层数，则A.n一定大于mB.n一定小于mC.n一定等于mD.n与m的大小关系不确定14 .设散列表长m=10,散列函数H(key)=key%9表中已保存3个关键字：H(13)=4,H(32)=5,H(15)=6,其余地址均为空。保存关键字23时存在冲突，采用线性探查法来处理。则查找关键字23时的探查次数是Ao1B.2C.3D.415 .下面关于m阶(m
5、23)B树的叙述中，正确的是A.终端结点可位于不同层B.非终端结点至多有m+1棵子树C.若树非空，则根结点至少有2个关键字D.每个非根结点包含n个关键字，-m2-lm-l二、填空题16 .数据的四种基本存储方法是顺序存储、链接存储、和散列存储。17 .指针P和指针q分别指向单链表L中的两个结点，nexl为指针域，则判断这两个结点是否相邻的条件是o18 .递归求解过程中的最小子问题称为o19 .广义表(a,b),(c,d,e),(f,g),h)的表头是。20 .3个结点的不同形状的二叉树有棵。21 .若有向无环图G存在2个入度为O的结点，则G至少存在个不同的拓扑序列。22 .将一棵树T转换为一棵
6、二叉树，则这棵二叉树的右子树o23 .对含n个元素的数据序列采用直接选择排序算法进行排序，最好情况下的时间复杂度是O24 .散列存储中，拉链法(链地址法)是处理的方法。25 .假设顺序存储的有序表R含有14个关键字，进行二分查找时，查找失败时关键字的最大比较次数为。三、解答题26 .设电文字符集是4，,3，e4,e5,ebf它们出现的次数分别为：38,12,17,26,14,20o现要为该字符集设计一种哈夫曼编码。请回答下列问题。(1)画出得到的哈夫曼树。(2)给出各符号的哈夫曼编码。27 .已知图G采用邻接矩阵存储，邻接矩阵如题27图所示。ABCDEFGA0110000B0011000C00
7、01000D0000100E0000011F0010001G0000000题27图(1)写出从顶点A开始到顶点C结束、包含所有顶点的2个深度优先遍历序列。(2)写出从顶点A开始的3个广度优先遍历序列。28 .有以下关键字序列(15,20,24,32,15,7,14,23),使用快速排序方法将其按升序排列。请回答下列问题。(1)若取第一个关键字为基准，写出第一趟快速排序的结果。(2)若取最后一个关键字为基准，写出第一趟快速排序的结果。29 .设有二叉排序树T如题29图所示。请回答下列问题。题29图(1)画出插入新结点f后的二叉排序树T1。(2)在Tl中再删除结点C得到二叉排序树T2,画出T2,并
8、简要说明删除过程。四、算法阅读题30 .顺序表类型定义如下。#defineListSize100typedefstruct(intdatafListSize;intlength;SeqList;voidf30(SeqList*SL,int*pdata,intn)intk,m;for(k=O;kdataSL-length=pdatak;elsefor(m=SL-length;mO;m-)SL-datam=SL-datam-1;SL-dataO=pdatak;)SL-length+;)voidout(SeqList*SLisl)intk=O;while(klength)顺序输出SLiSt中的各个元
9、素printf(%d,SList-datak+J);)intmain()intarray=10,2,9,5,30,3);SeqListMist;Mist,length=O;f30(&slist,array,sizeof(array)sizeof(int);out(&slist);输出slistreturnO;)(1)执行程序后程序的输出是什么？(2)函数DOO的功能是什么？31 .二叉树的存储结构类型定义如下。typedefintDataType;typedefstructnodeDataTypedata;/data:是数据域stmctnode*!child,*rchild;/分别指向左右孩子
10、BinTNode;typedefBinTNode*BinTree;阅读下列函数并回答问题。voidf31(BinTreeBt)if(Bt!=NULL).,if(Bt-lchild=-NULL&Bt-rchild=NULL)Bt-data=Bt-data*2;elsef31(Bt-lchild);f31(Bt-rchild);(1)设二叉树Bt如题31图所示，给出执行f31(Bt)的输出结果。(2)该算法的功能是什么？32.待查找记录的数据类型定义如下。/defineMAXSIZE100typedefintKeyType;typedefstructKeyTypekey;RecType;Iyped
11、efRecTypeSeqListMAXSIZE;下列算法实现对按升序排列的数据进行二分查找。请在空白处填上适当内容使算法完整。ih(BinSearch(SeqListR,KeyTypek,intn)intlow=O,high=n-l,mid;while(lowk)high-(2).;elselow=(3);)return-1;)33.二叉树的存储结构类型定义如下。typedefintDataType;typedefstructnodeDataTypedata;/data是数据域，其值大于0Structnode*Ichild,*rchild;/分别指向左右孩子BinTNode;IypedefBi
12、nTNode*BinTree;下列程序的功能是：将一棵二叉树的顺序存储结构转换为对应的链式存储结构。例如，对如题33图所示的二叉树，二叉树的顺序存储序列如下。intdata=30,20,0,0,90,0,0,0,0,100)；题33图程序如下：BinTreecreate(int*data,intn)BinTNode*Q100,*Bt=NULL,*p;intfront=0,rear=0,k;for(k=0;k(n;k+) p=NULL;if(datak!=0)p=(BinTree)malloc(sizeof(BinTNode);p-data=datakl;p-Ichild=p-rchild=NU
13、LL;)Qrear+=p;if(rear=I)Bt=p;else if(p!=NULL&(1)if(=0)Qfront-lchild=p;elseQfi,ont-rchild=p;if(rear%2!=0)returnBt;)请在程序的空白处填入适当的语句，使程序完整正确。五、算法设计题34.单链表类型定义如下。typedefstructnodeintdata;stmctnode*next;ListNode;typedefListNode*LinkList;请编写一个函数，在带头结点的单链表L中删除数值在指定范围内(XWdataWy)的结点。函数的原型如下。Void04(LinkListL,inty)；例如，对于如下的链表head,f-2+6l+5I3I八要删除链表中data在4到7范围内的结点，可调用函数B4(head,4,7),结果如下。
