数据结构样题.doc

《数据结构样题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构样题一、单项选择题1、若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为A、顺序存储结构B、链式存储结构C、索引存储结构D、散列存储结构2、在长度为n的顺序表的第I（1<=I<=n+1）个位置插入一个元素，元素的移动次数为A、n-i+1B、n-iC、iD、i-13、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为A、顺序表B、用头指针表示的单循环链表C、用尾指针表示的单循环链表D、单链表4、若进栈序列为a、b、c，则通过入出栈操作可能得到的a、b、c的不同排列个数为A、4B、5C、6D、75、为查找某个特定的单词在文本中出

2、现的位置，可应用的串运算是A、插入B、删除C、串联接D、子串定位6、已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=”SCIENCESTUDY”，则调用函数Scopy(P,Sub(S,1,7))后得到A、P=”SCIENCE”B、P=”STUDY”C、S=”SCIENCESTUDY”D、S=”STUDY”7、三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A[3][4][5]的存储地址为A、356

3、B、358C、360D、3628、下列叙述中正确的是A、二叉树是度为2的有序树B、二叉树中结点只有一个孩子时无左右之分C、二叉树中必有度为2的结点D、二叉树中最多只有两棵子树，并且有左右之分。9、n个顶点的有向图中含有有向边的数目最多为A、n-1B、nC、n(n-1)/2D、n(n-1)10、已知一个有向图如右所示，则从顶点A出发进行深度优先遍历，不可能得到的DFS序列为A、ADBEFC.BB、ADCEFBC、ADCBFEACEFD、ADEFBCD11、在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是A、快速排序B、堆排序C、归并排序D、基

4、数排序12、不可能生成右图所示二叉排序树的输入序列是A、45312.4B、42531C、4521325D、4231513一、填空题1、若一个算法中的语句频度之和为T(n)=3730n+4nlogn，则算法的时间复杂度为2、若要在链表中由指针p所指结点之后插入由指针q所指结点，则应用的语句是3、假设以S和X分别表示进栈和退栈操作，则对输入序列A，B，C，D，E进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为BCEDA4、串s=“Iamastudent!”的长度是5、在n个结点的线索二叉树中，线索指针的个数是n+16、若采用邻接矩阵结构存储具有n个顶点的

5、图，则对该图进行广度优先遍历的算法时间复杂度为O(n2)7、对关键字序列（52、80、63、44、48、91）进行一趟快速排序之后得到的结果为48,44,52,63,80,918、由10000个结点构成的二叉排序树，在等概率查找的假设下，查找成功的平均查找长度可能达到10001/2二、解答题1、已知树T的先序遍历序列为ABCDEFGHIJKL，后序遍历序列为CBEFDJIKLHGA，试画出树T2、已知二叉树有50个叶结点，且只有一个孩子的结点数是30个，则二叉树的结点总数有多少个。3、设二叉树的后序为A、C、D、B、G、I、H、F、E；中序为A、B、C、D、E

6、、F、G、H、I。试给出这棵二叉树的前序。4、试指出散列方法中，发生冲突的主要因素。5、试画出以下有向图的邻接表（设顶点序号按顶点名的字母顺序从0开始顺序编号，出边表按按顶点的序号从小到大链接），并给出从顶点（E）为起点的深度优先遍历的顶点序列和广度优先编历的顶点序列。6、试应用普里姆（Prim）算法为下图构造最小生成树。17137.试按Dijkstra算法，给出下图从顶点（0）出发到其它各顶点最短路经的求解过程。708．简述有向无环图上的拓朴排序的算法。9．试写出以下序列的选择排序过程。5，4，7，2，610、简述B_树和B+树的区别。11、对关键字序列（7

7、2、87、61、23、94、16、5、58）进行堆排序，使之按关键字递减次序排序。画出初始堆和排序过程的前三趟序列。12、在关键字序列（7，12，15，18，27，32，41，92）中用二分查找法查找与92相等的关键字，试给出依次与92比较的关键字。四、读程序或函数，回答问题1、设链接存储顺序表的数据类型定义如下，试指出以下函数完成什么工作。如指针为L的链表有10个表元，按链接顺序，它们的值依次为4、3、4、5、3、6、4、7、3、5，则经函数调用Demo(L)后，链表L中的元素依次是什么？typedefcharDataType;typedefstructno

8、de{DataTypedata;Str