数据结构(Python)考试题库(含参考答案).docx
一、填空题1 .构成数据元素的不可分割的最小单位是。2 .以顺序存储结构实现的线性表被称为 03 .队列中允许进行删除元素的一端称为。4 .最大容量为M的循环队列，队尾指针是r,队首指针是f,则队满时r, f, M三者之间满足的关系是 05 .串包含的字符个数称为串的 o6 .串中任意个连续字符组成的子序列被称为该串的 o7 .设一个广义表为(a, (), (c, (d), (e, f),则其长度为 o8 .设有二维数组array其每个元素的长度为1字节，按行先序顺序存储，其首地址为2000,则元素A|92的存储地址为 o9 .由3个结点可以构造出 种不同的二叉树。10 .若一棵二叉树有10个度为2的结点，则该二叉树的叶子结点个数是 o二、判断题1 .数据元素之间的逻辑结构可以划分为：集合、线性结构、树形结构、图状(或网状)结构。()2 .无向图中的某个顶点的入度称为此顶点度。()3 .对含有n个元素的查找表执行顺序查找时，假定每个元素的查找概率相同，则顺序查找某个元素A的平均时间复杂度为O(n)。()4 .对一个长度为n的列表使用日泡排序算法进行排序，此排序过程的平均时间复杂度为0(n)。5 .内排序的整个排序过程完全在内存中进行。三、单项选择题1 .连续存储设计中，存储单元的地址()0A. 一定连续B. 一定不连续C.不一定连续D.部分连续、部分不连续2 .设无向图的顶点个数为n,则该图最多有()条边。A. n-1B. n(n+l)/2C. n(n-1 )/2D. n3 .折半查找的平均时间复杂性为()<,A. O (n2)B. O(n)C. O(nlog2n)D. O(Iog2n)4 .在具有n个元素的序列中进行查找，平均查找长度为O(n)的方法是()。A.顺序查找方法B.散列查找方法C.分块查找方法D.树形查找方法5 .快速排序是一种()排序。A.插入B.选择C.交换D.归并四、简答题I.假设有一个合适大小的栈S,三个元素的进栈顺序为a, b,c,在进栈过程中允许任意的进栈、出栈操作，最终栈S要为空。请写出可能产生的所有出栈序列。2 .请简述队列和线性表之间的区别。3 .设串S= "sir”，请写出其所有真子串。4 .请简述空格串和空串的区别。五、综合题I.设广义表 A=(a,b), B=(c,(d,e,g), C=(A,B), D=(f,C)。试写出广义表 D 的长度，深度，表头，表尾。2 .设一颗二叉树的前序和中序遍历分别为:前序遍历序列：A, B, D, E C, E, G, H中序遍历序列：B,F,D,A,GE,H,C.请画出这棵二叉树。3 .设有一无向图G=(V, E),其中顶点集合V= 1,2,3,4,5,6,边集合E=(1, 2),(1,3), (1,4), (1,6), (2, 3), (3,6), (4, 5), (5,6)° 请画出这一无向图。4 .已知一组记录为46, 74, 53, 14, 26, 3& 86, 65, 27, 34,给出采用冒泡排序法进行 排序时每一趟的排序结果。六、程序设计题1.设有一个单链表，请设计算法并编程实现：在这个单链表里查找指定元素'a'。要求：（1）采用面向对象的方式编程。（2）需要自己定义单链表的结点类和单链表类。<3）题目要求的功能请在单链表类的一个函数里实现。答案解析:一、填空题12345数据项顺序表队头F=(r+1)%M长度678910子串420925li二、判断题12345JXJXV三、单项选择题12345ACDAC四、简答题1. c, b, aa, b, cb, a, c b, c, aa, c, b2 .队列是种受限的（或者特殊的）线性表；线性表可以在任意位置删除或者插入元素；队列在队尾插入元素：队列在队头删除元素。3 .“”（或空串），“s，,腕，,，tr”4 .空格串表示只含空格的串，其长度为串中空格字符的个数; 空串表示所含字符数为0的串，其长度为0。五、综合题I.长度：2 深度：4 表头：f 表尾：（C）2.A/ B C /D E3.6 68 84143 7742 35 76 24 57 68 33 56 82 34 61 23 45 16 68 84 47 75 56 6 433 57412 33 75 26 64 48 83 36 62 26 68 84 47 75 56 63 35 56 64 44183 37412 38 73 26 62 26 6 4 4 4 4 4 4 1111 rL rL rL )z )/ x)z )7 )< 1 2 3 4 5 6 4 z(x z( z(x z(x >(v /(V六、程序设计题1. ciass Node(object):def _init_(self,data):self.data=dataself.ncxt=Nonc class SingleLinkedList(object): def_init_(self)：sei f.head=Node( None)def IsEmpty(self):if self.GetLength()=O: return Trueelse:retum Falsedef FindElement（se）O：Pos=0cNode=self.headkey=int（input（，请输入想要查找的元素值：）if self.IsEmptyO：print（"当前单链表为空!"）returnwhile cNode.next!=None and cNode.data!=key:cNode=cNode.nextPos=Pos+1if cNodc.data=kcy:print（"查找成功,值为",key,”的结点位于该单链表的第",Pos,"个位置。"）else:（I 分）prim（"查找失败！当前单链表中不存在含有元素",key,"的结点"）
