数据结构(Python)考试题库(含参考答案).docx

《数据结构(Python)考试题库(含参考答案).docx》由会员分享，可在线阅读，更多相关《数据结构(Python)考试题库(含参考答案).docx（11页珍藏版）》请在第一文库网上搜索。

1、杂度为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(n1og2n)D.O(1og2n)4 .在具有n个元素的序列中进行查找，平均查找长度为0(n)的方法是().A.顺序查找方法B.散列查找方法C.分块查找方法D.树形查找方法5 .快速排序是一种()排序。A.插入B.选择C.交换D归并四、简

2、答题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字节，按行先序顺序存

3、储,其首地址为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)

4、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=(

5、1,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答案解析：一、

6、填空题12345数据项顺序表队头F=(r+1)%M长度678910子串42092511判断题12345XX单项选择题12345ACDAC四、简答题1. c,b,aa, b,cb, a,cc, c,aa,c,be1se:returnFa1sedefFindE1ement（Se1f）:Pos=OcNode=se1f.headkey=int（inpC请输入想要查找的元素值：，）ifse1f.IsEmpty（）:Print（当前单链表为空！）returnwhi1ecNode.next!=NoneandcNode.data!=key:cNode=cNode.nextPos=Pos+1ifcNode.da

7、ta=key:Print（查找成功，值为,key,的结点位于该单链表的第,PosJ个位置。e1se:（1分）Print（查找失败！当前单链表中不存在含有元素,key,的结点）3.6 68 8443 7742 35 76 24 57 68 33 56 82 34 61 23 45 16 68 84 47 75 56 64j33 57412 33 75 246468 83 36 62 26 68 84 47 75 56 63 35 56 64 4483 3742 38 73 26 62 26 6 4 4 4 4 3 4 11 11 1 Ix L L L L L L XJr XJZ Jr Jr Jr XJZ 1 2 3 4 5 6 /k l l l l l六、程序设计题1. c1assNode(Object):def_init_(se1f,data):se1f.data=datase1f.next=Nonec1assSing1e1inked1ist(Object):def_init_(se1f):Se1fhead=Node(None)defIsEmpty(se1f):ifseif.Ge11ength()=0:returnTrue