2018年10月自学考试02331《数据结构》试题.docx
2018年10月高等教育自学考试数据结构试题课程代码：02331一、单项选择题1 .下列数据结构中，逻辑结构不同的是A.线性表B.栈C.队列D.二叉树2 .将16个数据元素的线性表按顺序存储方式存储在数组中，若第一个元素的存储地址是1000,第6个元素的存储地址是1040,则最后一个元素的存储地址是A.1112B.1120C.1124D.11283 .设栈的初始状态为空，元素1,2,345依次入栈，不能得到的出栈序列是A.1,2,3,4,5B.4,5,3,2,1C.12,5,4,3D.1,2,5,3,44 .设指针变量P指向非空单链表中的结点，next是结点的指针域，则判断P所指结点为尾结点前一个结点的逻辑表达式中，正确的是A. p->next!=NU11&&p->nex1->next->next=NNU11B. p->next!=NU11&&p->next->next=NU11C. p->next->next=NU11D. p->next=NU115 .已知广义表1S=(a,b,c),d),(e,(f,8),(h,i),1S的深度是A.2B.3C.4D.56 .己知一棵完全二叉树T的第5层上共有5个叶结点，则T中叶结点个数最少是A.5B.8C.10D.277 .已知二叉树T的前序遍历序列为a,b,c,e,d,中序遍历序列为c,e,b,d,a,则T的后序遍历序列为A.c,e,d,b,aB.d,e,c,b,aC.e,c,d,b,aD.e,c,b,a,d8 .有向图G有n个顶点和e条边，G保存在邻接矩阵M中，M中0与1的个数差是A.n(n+1)/2-eB.n(n+1)/2-2eC.n×n-eD.n×n-2e9 .有向图G中所有顶点的度数之和是24,则G中弧的数量是A.10B.12C.14D.1610 .设有向图G含有/1个顶点、e条边，使用邻接表存储，对G进行深度优先搜索遍历算法的时间复杂度是A.O(n)B.O(e)C.O(n+e)D.O(n×e)11 .对数据序列(26,14,17,12,7,4,3)采用二路归并排序进行升序排序，两趟排序后，得到的排序结果为A.14,26,17,12,4,7,3B,12,14,17,26,3,4,7C.14,26,12,17,3,4,7D.14,26,12,17,3,7,412 .下列选项中，不稳定的排序方法是A.希尔排序B.归并排序C.直接插入排序D.冒泡排序13 .一组记录的关键字为(35,48,47,23,44,88),利用堆排序算法进行降序排序,建立的初始堆为A.23,35,48,47,44,88B.23,35,47,48,44,88C.35,23,47,48,44,88D.35,23,47,44,48,8814 .棵二叉排序树中，关键字n所在结点是关键字m所在结点的孩子，则1 .n一定大于mB.n一定小于m2 .n一定等于mD.n与m的大小关系不确定15 .设散列表长m=16,散列函数H(key)=key%15°表中己保存4个关键字：addr(18)=3,addr(35)=5,addr(51)=6,addr(22)=7,其余地址均为开放地址。存储关键字36时存在冲突，采用线性探测法来处理。则查找关键字36时的探查次数是A.1B.2C.3D.4二、填空题16 .数据项是具有独立含义的标识单位。17 .指针P和q分别指向单链表1中的两个相邻结点，即q->next=po若要在q所指结点后插入指针r所指结点，则执行的语句是r->next=p;。18 .递归算法设计中的最小子问题称为递归的o19 .广义表(岫),(娘),鼠£值,1)的表尾是o20 .已知二叉树的前序遍历序列和后序遍历序列，则对应的二叉树确定。21 .如果有向无环图G中仅有一个顶点的入度为0,若要求G的拓扑序列不唯一，则G中必须存在一个出度至少为的顶点。22 .将森林T转换为一棵二叉树T1,在T中结点A是结点B的右邻的兄弟(下一个兄弟)，则在T1中，A是B的0结点。23 .对含个元素的数据序列采用快速排序算法进行排序，平均时间复杂度是o24 .散列存储中，常用的解决冲突的方法有开放地址法和两大类。25 .假设顺序存储的有序表R含有8个关键字，进行二分查找时，平均查找长度为o三、简答题26 .设电文字符集是e1,e2,e3,e4,e5,各字符出现的次数分别为36,13,26,18,23)。现要为该字符集设计哈夫曼编码。请回答下列问题。(1)给出构造的哈夫曼树。(2)给出各字符的哈夫曼编码。(3)计算电文编码总长。27 .已知图G采用邻接矩阵存储，邻接矩阵如题27图所示。ABA01BOOCOODOOCDEFG10000'010000100000101000100000100000题27图(1)根据邻接矩阵画出图G。(2)根据图G写出从顶点A开始图G的1个深度优先搜索遍历序列。(3)根据图G写出从顶点A开始图G的1个广度优先搜索遍历序列。28 .有数据序列(12,17,05,10,20,24,45,11,10,12),使用希尔排序方法将其排成升序序列。请回答下列问题。(1)分别写出增量为3和1的希尔排序结果。(2)计算第一趟希尔排序中数据元素之间的总交换次数(两个元素之间的交换记1次)。29 .设有二叉排序树T如题29图所示。现需在T中删除结点e,请回答下列问题。(1)画出删除后的二叉排序树(仅需画出一棵)。(2)在你实现的删除过程中，指针域更新的次数是多少？四、算法阅读题30 .顺序表类型定义如下：/define1istSize100typedefstructintdata1istSize;int1ength;Seq1ist;阅读下列程序，并回答问题。intpartmin(Seq1ist*S11,Seq1ist*S12)ihtmin1cngth,minva1ue,k=0;min1ength=S12->1ength;minva1ue=S12->data01;whi1e(k<min1ength)if(S11->datak<S12->datak&&S1I->datak<minva1ue)minva1ue=S11->datak;e1seif(S12->datak<minva1ue)minva1ue=S12->datak1;k+;returnminva1ue;)intf30(Seq1ist*S11,Seq1ist*S12)(if(S11->1ength>S12->1ength)returnpartmin(S11,S12);e1sereturnpartmin(S12,S11);J若S11->data中的数据为(15,14,25,8,-28,37,126,56,34),S12->data中的数据为(12,7,-33,15,39,24,42,13),则调用函数t30(&S11&S12)后的返回值是什么?(2)该函数的功能是什么？31 .二叉树的存储结构类型定义如下：typedefcharDataType;typedefstruetnodeDataTypedata;/data是数据域struetnode*Iehi1d,*rehi1d;/分别指向左右孩子JBinTNode;IypedefBinTNode*BinTree;阅读下列程序，并回答问题。void1(BinTreeT)(if(T!=NU11)t31(T->rchi1d);printf(,%0",T->data);f31(T->1chi1d);Ireturn;)(1)设二叉树T如题31图所示，给出执行f31(T)的输出结果。题31图(2)给出该算法的时间免杂度。32 .待排序记录的数据类型定义如下：#defineMAXSIZEIOOtypedefintKeyType;typedefstreetKeyTypekey;RecType;typedefRecTypeSeq1istMAXSIZE;下列函数实现顺序表的直接插入排序，请填上适当内容使算法完整。voidf32(Seq1istR,intn)iti,j；RecTypetemp;fr(i=1;i<=(1)-+temp=Ri;j二i；whi1e(j>0&&temp.key<Rj-1.key)Rj=RU-1;；(3)33 .二叉树的存储结构类型定义如下：typedefintDataType;typedefstructnode(DataTypekey;/data是数据域streetnode*1chi1d,*rchi1d;分别指向左右孩子)BinTNode;IypedefBinTNode*BinTree;阅读下列程序，并回答问题。voidf33(BinTreeroot,int1eft,intright)(if(root=NU11)return;f33(root->1ehi1d,1eft,fight);if(root->key>=1eft&&root->key<right)printf("%d",root->key);f33(root->rehi1d,1eft,right);(1)设二叉树T如题33图所示，bt是指向根结点的指针。给出执行f33和(bt,14,30)的输出结题33图(2)给出该函数的功能。五、算法设计题34 .己知个单链表的表头指针保存在数组A中，单链表中的结点类型及数组类型定义如下，存储形式如题34图所示。#defineMAXSIZE100typedefintDataType;IypedefstructnodeDataTypedata;/data是数据域Stmctnode*next;/指向下一结点的指针(Node;IypedefNode*Seq1istMAXSIZE;题34图试设计算法，在多个链表中查找值为key的数据元素，查找成功返回1,查找失败返回0。函数原型为intf34(Seq1istA,intn,intkey)。
