湖北汽车工业学院数据结构试题

数据结构试一、单项选择题1•若一个算法的时间复杂度用T（n）表示，其中n的含义是（）问题规模B.语句条数C.循环层数D.数量2．具有线性结构的数据结构是（）A.树B.图C.栈和队列D.广义表TOC\o"1-5"\h\z3•将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（）A.O（1）B.O（m）C.O（n）D.O（m+n）在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（）A.2个B.3个^C.4个D.6个假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（）A.3B.37C.50D.97若栈采用链式存储结构，则下列说法中正确的是（）需要判断栈满且需要判断栈空不需要判断栈满但需要判断栈空需要判断栈满但不需要判断栈空不需要判断栈满也不需要判断栈空TOC\o"1-5"\h\z若串str二”Software”，其子串的数目是（）A.8B.9C.36D.37设有一个10阶的下三角矩阵A,采用行优先压缩存储方式，aii为第一个元素，其存储地址为1000，每个元素占一个地址，则a的地址为（）85A.1012B.1017C.1032D.1039允许结点共享的广义表称为（）A.纯表B.线性表C.递归表D.再入表下列数据结构中，不属于二叉树的是（）C.二叉排序树D.哈夫曼树对下面有向图给出了四种可能的拓扑序列，其中错误的是（）C.5，1，6，3，4，2D.5，1，2，6，4，3以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（A.v1，v2，v3,v4,v5,v6.v6C.v1，v2，v3,v4，v7,v5，v6下列排序算法中不稳定的是（A•快速排序C.冒泡排序D.v1,v2,v5,v6,v7,v3,v4)B•归并排序D.直接插入排序14.一个有序表为（1,3,9,12,32,41,45,62,75,77,82,95,100），当米用折半查找方法查找值32时，查找成功需要的比较次数是（)A.2B.3C.4D.815.,米用ISAM组织文件的方式属于（)A.链组织B.顺序组织C.散列组织D.索引组织二、填空题数据元素及其关系在计算机存储器内的表示称为。长度为n的线性表采用单链表结构存储时，在等概率情况下查找第i个元素的时间复杂度是下面是在顺序栈上实现的一个栈基本操作，该操作的功能。typedefstruct{DataTypedata[100]；inttop；}SeqStack；DataTypefl8(SeqStack*S){if(StackEmpty(S))Error("Stackisempty")；returnS-〉data[S-〉top]；}TOC\o"1-5"\h\z在串匹配中，一般将主串称为目标串，将子串称为。已知广义表C=(a(b,c),d),则:tail(head(tail(C)))=。用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树的带权路径长度为。已知有向图如下所示，其中顶点A到顶点C的最短路径长度是。对序列{55,46，13，05，94，17,42}进行基数排序，第一趟排序后的结果是24•高度为3的3阶B-树最少的关键字总数是。VSAM通常作为大型索引顺序文件的组织，其动态索引结构采用的是__三、解答题假设二叉树的RNL遍历算法定义如下:若二叉树非空，则依次执行如下操作:遍历右子树；访问根节点；遍历左子树。已知一棵二叉树如图所示，请给出其}27.已知一个无向图G=(V,E),其中V-{A,B,C,D,E,F},邻接矩阵表示如下所示。<0101010111001000111001001010101010请回答下列问题：(1)请画出对应的图G。(2)画出图G的邻接表存储结构。已知一组待排记录的关键字序列为(16,12,18,60,15,36,14,18,25,85)，用堆排序方法建小根堆，请给出初始建堆后的序列。已知一棵二叉排序树如图所示。请回答下列问题：画出插入元素23后的树结构；请画出在原图中删除元素57后的树结构。四、算法阅读题已知下列程序，Ls指向带头结点的单链表。Typedefstructnode{DataTypedata;structnode*next;}*LinkList;voidf30(LinkListLs){LinkListp,q;q=Ls—〉next;if(q&&q-〉next){Ls—>next二q—〉next;p=qwhile(p—>next)p=p—>next;p—>next二q;q—>next二NULL;}}请回答下列问题：(1)当Ls指向的链表如下图所示，请画出执行本函数之后的链表的结果。(2)请简述算法的功能。已知字符串处理函数f31程序如下。intf31(char*strl，char*str2){while(*strl==*str2&&(*strl!='\O')){strl++；str2++；}return(*strl-*str2?l：0)；}请回答下列问题：若调用语句是f31(”abcde”,”abcdf'),则函数的返回值是什么？若调用语句是f31(”abcde”，”abcde”)，则函数的返回值是什么？简述该函数的功能。数组A[]中存储有n个整数，请阅读下列程序。voidf32(intA[]，intn){inti，j，k，x；k=n-l；while(k>0){i=k；k=0；for(j=O；jA[j+1]){x=A[j]；A[j]=A[j+l]；A[j+1]=x；k=j；}／／endofif}／／endofwhilereturn；}请回答下列问题：当A[]={10,8,2,4,6,7}时，执行f32(A,6)后，数组A中存储的结果是什么？说明该算法的功能。33．下面程序实现二分查找算法。Typedefstruct{KeyTypekey；InfoTypeotherinfo；}SeqList[N+1]；intBinSearch(SeqListR,intn,KeyTypeK){intlow=1，high=n；while(⑴){mid=(1ow+high)／2；if((2))returnmid；if(R[mid]．key>K)high=mid-1；else⑶：}returnO：}／／BinSearch请在空白处填写适当内容，使该程序功能完整。(1)(2)(3)五、算法设计题34．已知二叉树采用二叉链表存储，其结点结构定义如下：typedefstructNode{ElmTypedata：structNode*lchild，*rchild：}*BiTree：请编写递归函数SumNodes(BiTreeT),返回二叉树T的结点总数。