资源描述：
《数据结构复习题tjuci0604》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、数据结构复习题一、填空题1.数据结构是一门研究非数值计算的程序设计问题屮计算机的以及它们之间的关系和运算等的学科。2.数据结构包括数据的、数据的和数据的等三个方面的内容。3.数据结构按逻辑结构可分为两大类，它们分别是和o4.从逻辑关系上讲，数据结构主要分为—、—、和-5.线性结构屮元素之间存在关系，树形结构屮元素之间存在关系。6.在线性结构中，第一个结点前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点后续结点，其余每个结点有且只有1个后续结点。7.在树形结构中，树根结点没冇结点，其余每个结点冇月•只有个
2、前驱结点；叶子结点没有结点，其余每个结点的后续结点数可以o&在图形结构屮，每个结点的前驱结点数和示续结点数可以O9.数据的存储结构常用的冇两种，它们分别是存储结构和存储结构。10.在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。11.在顺序表中访问任意一结点的时间复杂度均为,因此顺序表也称为的数据结构。12.顺序表中逻辑上相邻的元索的物理位置相邻。单链表中逻辑上相邻的元素的物理位置相邻。在双链表中，每个结点设置了两个指针域，其中一个指向—结点，另一个指向结点。13•线性表、栈和队列都是
3、结构，可以在线性表的位置插入和删除元素;对于栈只能在插入和删除元素;对于队列只能在插入和删除元素。14.栈是一种特殊的线性表，允许插入和删除运算的一端称为°不允许插入和删除运算的一端称为。15.是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。16.栈和队列是两种特殊的线性表，栈的操作特性是示进先出,队列的操作特性是,栈和队列的主要区别在于。17.顺序栈或链栈进行插入和删除操作的吋间复杂度分别是，顺序队列或链队列进行插入和删除操作的时间复杂度都是018.称为空串；称为空口串。19.T串的定
4、位运算称为串的模式匹配；称为目标串，称为模式。14.两个串相等的充分必要条件是o15.三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元索的、和o16.—棵深度为6的满二叉树有个分支结点和个叶了结点。17.设一棵完全二叉树具冇1000个结点，则此完全二叉树冇个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。18.—棵具有257个结点的完全二叉树，它的深度为。19.设一棵完全二叉树有700个结点，则共有个叶子结点。20.一棵二叉树的第i(i$l)层最多
5、冇贮个结点；一棵有n(n>0)个结点的满二叉树共有个叶了结点和个非终端结点。21.深度为k的二叉树中，所含叶子的个数最多为o22.在具有n个结点的二义链表中，共有个指针域，其中个指针域用于指向其左右孩了,剩下的个指针域则是空的。23.图的存储结构主要有两种，分别是、等存储结构，遍历图方、等方法。24.有向图G用邻接表矩阵存储，具第i行的所有元索之和等于顶点i的。25.设有一稀疏图G,则G采用存储较省空间。26.设冇一稠密图G,则G采用存储较省空间。27.设无向图G中顶点数为n,则图G至少有条边，至多有条边；若G
6、为有向图，则至少有_条边，至多有条边。28.图的深度优先遍历类似于树的编历，它所用到的数据结构是—；图的广度优先遍历类似于树的遍历，它所用到的数据结构是—o29.数据的存放无规律而言的线性表小进行检索的最佳方法是o30.假设在有序线性表a[20]±进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为:比较四次查找成功的结点数为;平均查找长度为c31.折半查找有序表(4,6,12,20,28,38,50,70,88,100),若杏找表屮元素20,它将依次与表中元素比较大小。32.在各种查找方法
7、中，平均查找长度M结点个数n无关的查找方法是。33.散列法存储的基本思想是由决定数据的存储地址。34.大多数排序算法都有两个基本的操作：和o35.在对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序时,当把第7个记录60插入到冇序表时，为寻找插入位置至少需比较—次。36.在插入和选择排序中，若初始数据基木正序，则选用:若初始数据基本反序，则选用o37.在堆排序和快速排序中，若初始记录接近正序或反序，贝燧用；若初始记录基木无序，则最好选用o38.对于n个记录的集合进行冒泡排序，在绘
8、坏的情况下所需要的时间是o若对其进行快速排序，在最坏的情况下所需要的吋间是。14.对于n个记录的集合进行归并排序，所需要的平均时间是,所需要的附加空间是。15.设要将序列(Q,H,C,Y,P,A,M,S,R,D,F,X)屮的关键码按字母序的升序重新排列,则:冒泡排序一趟扫描的结果是;初始步长为4的希尔(shell)排序一趟的结果是:二路归并排序一趟扫描的结果是:快速排序一趟扫描的结果是
