数据结构(Python)考试题库(含参考答案).docx
杂度为O(n).()5.内排序的整个排序过程完全在内存中进行。()三、单项选择题1 .连续存储设计中，存储单元的地址()oA.一定连续B.一定不连续C.不一定连续D.部分连续、部分不连续2 .设无向图的顶点个数为n,则该图最多有()条边。A.n-1B.n(n+1)/2C.n(n-1)/2D.n3 .折半查找的平均时间复杂性为(A.O(n2)B.0(n)C.O(nlog2n)D.O(log2n)4 .在具有n个元素的序列中进行查找，平均查找长度为0(n)的方法是().A.顺序查找方法B.散列查找方法C.分块查找方法D.树形查找方法5 .快速排序是一种()排序。A.插入B.选择 C.交换D归并四、简答题1.假设有一个合适大小的栈S,三个元素的进栈顺序为a,b,c,在进栈过程中允许任意的进栈、出栈操作，最终栈S要为空。请写出可能产生的所有出栈序列。填空题1 .构成数据元素的不可分割的最小单位是O2 .以顺序存储结构实现的线性表被称为-3 .队列中允许进行删除元素的端称为.4 .最大容量为M的循环队列，队尾指针是r,队首指针是f,则队满时r,f,M三者之间满足的关系是O5 .串包含的字符个数称为申的。6 .串中任意个连续字符组成的子序列被称为该串的o7 .设一个广义表为(a(),(c.(d).(ef),则其长度为。8 .设有二维数组arrayU010,其每个元索的长度为1字节，按行先序顺序存储,其首地址为2000,则元索A92的存储地址为.9 .由3个结点可以构造出种不同的二叉树。10 .若一棵二叉树有10个度为2的结点，则该二叉树的叶子结点个数是O二、判断题1 .数据元素之间的逻辑结构可以划分为：集合、线性结构、树形结构、图状(或网状)结构。()2 .无向图中的某个顶点的入度称为此顶点度。()3 .对含有n个元素的查找表执行顺序查找时，假定每个元素的查找概率相同，则顺序查找某个元素A的平均时间复杂度为O(n)o()4 .对个长度为n的列衣使用冒泡排序算法进行排序，此排序过程的平均时间复五、综合题1 .设广义表A=(a,b),B=(c(d,e,g),C=(A,B),D=(f.C)o试写出广义表D的长度，深度，表头，表尾。2 .设一颗二叉树的前序和中序遍历分别为:前序遍历序列：A,B,D,F,C,E,GH中序遍历序列：B,F,D,A,GE,H,C,清画出这棵二叉树。2 .请简述队列和线性表之间的区别。3 .设串S="sir”，请写出其所有真子串。4 .请简述空格串和空串的区别。六、程序设计题1.设有一个单链表，请设计算法并编程实现：在这个单链表里查找指定元素a'.要求：(I)采用面向对象的方式编程。(2)需要自己定义单链表的结点类和单链表类。(3)题目要求的功能请在单链表类的一个函数里实现。3 .设有一无向图G=(V,E),其中顶点集合V=",2,3,4,5,6,边集合E=(l,2).(1,3),(1,4),(1,6),(2,3),(3,6),(4,5),(5,6)o请画出这一无向图。4 .已知一组记录为46,74,53,14,26,38,86,65,27,34),给出采用冒泡排序法进行排序时每一趟的排序结果。2 .队列是一种受限的（或者特殊的）线性表：线性表可以在任意位置删除或者插入元素：队列在队尾插入元素；队列在队头删除元素。3 .“”（或空串），飞”，*T,“st”,t4tr,'4 .空格串表示只含空格的串，其长度为串中空格字符的个数;空串表示所含字符数为O的串，其长度为0。五、综合题1 .长度：2深度：4表头：f表尾：（C）2 .A/BC/DE答案解析：一、填空题12345数据项顺序表队头F=(r+1)%M长度678910子串42092511判断题12345XX单项选择题12345ACDAC四、简答题1. c,b,aa, b,cb, a,cc, c,aa,c,belse:returnFalsedefFindElement（Self）:Pos=OcNode=self.headkey=int（inp11C请输入想要查找的元素值：，）ifself.IsEmpty（）:Print（"当前单链表为空！"）returnwhilecNode.next!=NoneandcNode.data!=key:cNode=cNode.nextPos=Pos+1ifcNode.data=key:Print（"查找成功，值为",key,"的结点位于该单链表的第",PosJ个位置。else:（1分）Print（"查找失败！当前单链表中不存在含有元素",key,"的结点"）3.6688443774235 76 2457 68 335682346123451668844775 56 64j3357412 33 752464688336622668844775 56 6335 56 64448337423873266226644443411111IxLLLLLLXJrXJZJrJrJrXJZ123456/klllll>六、程序设计题1. classNode(Object):def_init_(self,data):self.data=dataself.next=NoneclassSingleLinkedList(Object):def_init_(self):Selfhead=Node(None)defIsEmpty(self):ifseif.GelLength()=0:returnTrue
