《西交11秋学期《数据结构》考试复习题》由会员分享，可在线阅读，更多相关《西交11秋学期《数据结构》考试复习题（9页珍藏版）》请在金锄头文库上搜索。
1、数据结构-学习指南一、 单项选择题1. 算法指的是（ ）A.计算机程序 B.解决问题的计算方法C.排序算法 D.解决问题的有限运算序列2.线性表采用链式存储时，结点的存储地址（ ）A.必须是不连续的B.连续与否均可C.必须是连续的D.和头结点的存储地址相连续3.栈和队列的共同特点是( )。A.只允许在端点处插入和删除元素B.都是先进后出 C.都是先进先出D.没有共同点 4.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针 B.头、尾指针都要修改C. 仅修改尾指针 D.头、尾指针可能都要修改5.以下数据结构中哪一个是非线性结构？( d )A. 队列 B. 栈 C. 线性表 D.
2、二叉树6.二叉树的第k层的结点数最多为( )A2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为( )A.n B.n/2 C.(n+1)/2 D.(n-1)/29.在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s 所指的结点,则执行(
3、 )。A.slink=plink; plink=s; B.plink=s; slink=q;C.plink=slink; slink=p; D.q link=s; slink =p;10.栈的插入和删除操作在（ ）进行。A.栈顶 B.栈底 C.任意位置 D.指定位置11. 组成数据的基本单位是（ ）。 A.数据项 B.数据类型 C.数据元素 D.数据变量12设数据结构A=(D，R)，其中D=1，2，3，4，R=r，r=，则数据结构A是（ ）。A.线性结构 B.树型结构 C.图型结构 D.集合13数组的逻辑结构不同于下列（ ）的逻辑结构。A.线性表 B.栈 C.队列 D.树14二叉树中第i(i1
4、)层上的结点数最多有（ ）个。A.2i B.2i C.2i-1 D.2i-115设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ ）。A.p-next=p-next-nextB.p=p-nextC.p=p-next-nextD.p-next=p16. 设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ ）A.6 B.4 C.3 D.217.将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（ ）。A.100 B.40 C.5
5、5 D.8018.设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ ）。A.15，25，35，50，20，40，80，85，36，70B.15，25，35，50，80，20，85，40，70，36C.15，25，35，50，80，85，20，36，40，70D.15，25，35，50，80，20，36，40，70，8519.根据二叉树的定义可知二叉树共有（ ）种不同的形态。A.4 B.5 C.6 D.720.设有以下四种排序方法，则（ ）的空间复杂度最大。A.冒
6、泡排序 B.快速排序 C.堆排序 D.希尔排序21. 数据结构是（）A.一种数据类型B.数据的存储结构C.一组性质相同的数据元素的集合D.相互之间存在一种或多种特定关系的数据元素的集合22. 栈和队列的共同特点是( )。A.只允许在端点处插入和删除元素B.都是先进后出 C.都是先进先出D.没有共同点23. 以下数据结构中哪一个是非线性结构？( )A.队列 B.栈 C.线性表 D.二叉树24. 二叉树的第k层的结点数最多为( ).A.2k-1 B.2K+1 C.2K-1 D. 2k-125. 在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，
7、假定查找每个元素的概率都相等）为 ( )。A.n B.n/2 C.(n+1)/2 D.(n-1)/226. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ ）个A.1 B.2 C.3 D.427. 当待排序列基本有序时，下列排序方法中( )最好A.直接插入排序 B.快速排序 C.堆排序 D.归并排序28. 设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ ）A.3 B.4 C.5 D.129, 设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时
8、间复杂度为（ ）。A.O(log2n) B.O(1) C.O(n2) D.O(n)30, 设连通图G中的边集E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（ ）。A.abedfc B.acfebd C.aebdfc D.aedfcb二、填空题1. 在串S=“structure”中，以t为首字符的子串有 个。2设输入序列为1、2、3，则经过栈的作用后可以得到_种不同的输出序列3设有n个无序的记录关键字，则直接插入排序的时间复杂度为_，快速排序的平均时间复杂度为_。4根据初始关键字序列(19，22，01，3
9、8，10)建立的二叉排序树的高度为_5深度为k的完全二叉树中最少有_个结点。6向量、栈和队列都是_ _结构，可以在向量的任意位置插入和删除元素；对于栈只能在_插入和删除元素；对于队列只能在_插入元素和在_删除元素。7.数据的物理结构主要包括_和_两种情况。8.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为_。9.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_，整个堆排序过程的时间复杂度为_。10.设有向图G用邻接矩阵Ann作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的_，第i列上所有元素之和等于顶点i的_11.设指针变量p指向双向循环链表
10、中的结点X，则删除结点X需要执行的语句序列为_（设结点中的两个指针域分别为llink和rlink）。（此题3分）12.通常从四个方面评价算法的质量：_、_、_和_。13.称算法的时间复杂度为O(f(n)，其含义是指算法的执行时间和_的数量级相同14.设一棵完全二叉树中有500个结点，则该二叉树的深度为_；若用二叉链表作为该完全二叉树的存储结构，则共有_个空指针域15.在快速排序、堆排序、归并排序中，_排序是稳定的16.在一个具有n个顶点的无向完全图中，包含有_条边，在一个具有n个顶点的有向完全图中，包含有_条边。三、 判断题1.设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状
11、()2.层次遍历初始堆可以得到一个有序的序列。 ()3.设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。 ()4.线性表的顺序存储结构比链式存储结构更好。 ()5.快速排序是排序算法中平均性能最好的一种排序。 ()6.散列法存储的基本思想是由关键码的值决定数据的存储地址。 ()7.对于单链表形式的队列，其空队列的front指针和rear指针不相同。 ()8.一般树和二叉树的结点数目都不可以为0。 ()9.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据运算三个方面。 ()10.多维数组元素之间的关系，既不是线性的，也不是树形的。 ()11.线性表的顺序存储表示优于链式存储表示 ()12.线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续()13.线性表的插入和删除总是伴随着大量数据的移动 ()14.队列在程序调用是必不可少，因此递归离不开队列 ()15.字符串aababaaaba的改进函数nextval数组值是0020200320 ()16.若有向图有n个顶点，则其强连通分量最多有n个 ()17.平衡二叉树一定是一棵完全二叉树
