数据结构样题.docVIP

数据结构样题 单项选择题 1、若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为 A、顺序存储结构 B、链式存储结构 C、索引存储结构 D、散列存储结构 2、在长度为n的顺序表的第I（1=I=n+1）个位置插入一个元素，元素的移动次数为 A、n-i+1 B、n-i C、i D、i-1 3、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为 A、顺序表 B、用头指针表示的单循环链表 C、用尾指针表示的单循环链表 D、单链表 4、若进栈序列为a、b、c，则通过入出栈操作可能得到的a、b、c的不同排列个数为 A、4 B、5 C、6 D、7 5、为查找某个特定的单词在文本中出现的位置，可应用的串运算是 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 B、358 C、360 D、362 8、下列叙述中正确的是 二叉树是度为2的有序树 B、二叉树中结点只有一个孩子时无左右之分 C、二叉树中必有度为2的结点 D、二叉树中最多只有两棵子树，并且有左右之分。 9、n个顶点的有向图中含有有向边的数目最多为 A、n-1 B、n C、n(n-1)/2 D、n(n-1) 10、已知一个有向图如右所示，则从顶点A出发进行深度优先遍历，不可能得到的DFS序列为 ADBEFC . B ADCEFB ADCBFE A C E F ADEFBC D 11、在最好和最坏情况下的时间复杂度均为O(n log n)且稳定的排序方法是 A、快速排序 B、堆排序 C、归并排序 D、基数排序 12、不可能生成右图所示二叉排序树的输入序列是 45312 . 4 42531 45213 2 5 42315 1 3 填空题 1、若一个算法中的语句频度之和为T(n) = 3730n+4nlogn，则算法的时间复杂度为 2、若要在链表中由指针p所指结点之后插入由指针q所指结点，则应用的语句是 3、假设以S和X分别表示进栈和退栈操作，则对输入序列A，B，C，D，E进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为 BCEDA 4、串s = “I am a student!”的长度是 5、在n个结点的线索二叉树中，线索指针的个数是 n+1 6、若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为 O(n2) 7、对关键字序列（52、80、63、44、48、91）进行一趟快速排序之后得到的结果为 48,44,52,63,80,91 8、由10000个结点构成的二叉排序树，在等概率查找的假设下，查找成功的平均查找长度可能达到 10001/2 解答题 1、已知树T的先序遍历序列为ABCDEFGHIJKL，后序遍历序列为CBEFDJIKLHGA，试画出树T 2、已知二叉树有50个叶结点，且只有一个孩子的结点数是30个，则二叉树的结点总数有多少个。 3、设二叉树的后序为A、C、D、B、G、I、H、F、E；中序为A、B、C、D、E、F、G、H、I。试给出这棵二叉树的前序。 4、试指出散列方法中，发生冲突的主要因素。 5、试画出以下有向图的邻接表（设顶点序号按顶点名的字母顺序从0开始顺序编号，出边表按按顶点的序号从小到大链接），并给出从顶点（E）为起点的深度优先遍历的顶点序列和广度优先编历的顶点序列。 6、试应用普里姆（Prim）算