数据结构复习题.docx

一、单项选择题1、向一个有255个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。A.8B.127.5C.127D.72、带头结点的单链表first为空的判定条件是：（）A.first=NU1.1.B.first->link=NU1.1.C.first->link=firstD.first!=NU1.1.3、设某线性链表的头结点指针为1.,1.->data表示该链表的结点个数，1.->next指向该链表的第一个结点，p指向新建立的结点，其类型与1.相同。在建立该链表的过程中，若希望1.->next始终指向新输入的结点，可采用如下的C语言语句实现：A.p->next=1.->next,1.->next=p>1.->data+;B.->next=NU1.1.t1.->next=,1.->data+;C.1.->data+,1.->next=p->next,->next=1.;D.以上都不是。4、设A、B、C三个字符按先后顺序依次进栈，下面哪个序列为不合法的出栈序列：A.ABCB.ACB5、如下陈述中正确的是（A.串是一种特殊的线性表C.串中元素只能是字母C.BACD.CAB）B.串的长度必须大于零D.空串就是空白串6、在二叉树的第4层上至多有多少个结点：A.10个B.8个C.16个D.以上都不是。7、若一棵二叉树具有8个度为2的结点，则该二叉树的叶子个数是（）A.9B.11C.7D.不确定8、在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为（）A.eB.2eC.n2eD.n2-2e9、5个不同的数据元素进行直接插入排序，最多需要进行（）次比较。A.8B.10C.14D.2510、设有关键码初始序列(Q,H,C,Y,P.A,M,S,R,D,F,X)，新序列F,H.C,D,P,A,M,Q,R,S,Y,X)是采用下列哪种排序方法对初始序列进行第一趟扫描的结果？A,直接插入排序B.二路归并排序C.以第一元素为分界元素的快速排序D.基数排序1、在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。A.0（n）B.0（n2）C.0（1）D,0（n2）2、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）A.n-2B.n-l3、链表表示线性表的优点是:A.便于随机存取C便于插入与删除C.nD.n+1B.花费的存储空间比顺序表少D.数据元素的物理顺序与逻辑顺序相同4、设有两个串P和q,求q在P中首次出现的位置的运算称作（）A.连接B.模式匹配C.求子串D.求串长5、设有一个二元数组Amn,假设A00存放位置在644（10）,A22存放位置在676（10）,每个元素占一个空间，则A45在（）位置，（10）表明用10进数表示。D.724(10)A.692(10)B.626(10)C.709(10)6、在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。D.1C.n-l)D.0A.2B.-1C.07、n个顶点的连通图至少有（）条边A.n+1B.n8、无向图中一个顶点的度是指图中（A.通过该顶点的简单路径数B.与该顶点相邻接的顶点数C.通过该顶点的回路数D.与该顶点连通的顶点数9、在下列排序算法中，（）算法的最坏情况下时间复杂度不高于0（nlog2n）°A,起泡排序B.希尔排序C.归并排序D.快速排序10、下列说法中错误的是（）A. n个结点的树的各结点度数之和为n-1B. n个结点的无向图最多有n*（nT）条边C.用相邻矩阵存储图时所需存储空间大小与图的结点数有关,而与边数无关D.散列表中碰撞的可能性大小与负载因子有关1、向顺序栈中压入新元素时，应当（）oA.先移动栈顶指针，再存入元素B.先存入元素，再移动栈顶指针C.先后次序无关紧要D.同时进行2、设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计毙时间为（）0A.0（nlogje）B.0（n+e）C.0（ne）D.0（n2）3、线性链表不具有的特点是（）0A.随机访问B.不必事先估计所需存储空间大小C.插入与删除时不必移动元素D.所需空间与线性表长度成正比4、设有一个10阶的对称矩阵A10H10,采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B中，A00存入B0中，则A85在B中（）位置。A.32B.33C.41D.655、设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（）个。A.n-lB.nC.n+1D.n+26、具有65个结点的完全二叉树的高度为（）。（根的层次号为0）A.8B.7C.6D.57、若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（）方法比较次数最少。A.直接插入排序B.快速排序C.归并排序D.直接选择排序8、在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。A.3B.2C.1D.1/29、某二叉树进行前序遍历的结果为ABDEFC,中序遍历的结果为DBFEAC,则后序遍历的结果为（A.DBFEACB.DFEBCAC.BDFECD.BDEFAC10、假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行多少次探测？（）A.k-1次B.k次C.k+1次D.k（k+D2次1、用单链表表示的链式队列的队头在锥表的（）位置。A.链头B.链尾C.链中2、只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。A.起泡排序B.快速排序C.简单选择排序D.堆排序3、若待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（）就是不稔定的排序方法。A.起泡排序B.归并排序C.直接插入排序D.简单选择排序4 .数据结构中，与所使用的计算机无关的是数据的（）结构：A.存储B.物理C.逻辑D.物理和存储5 .向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素A.8B.63.5C.63D.76 .设串sl='ABCDEFG',s2='PQRST,函数Con（X,y）返回X和y串的连接串，subs（s,1.j）返回串$的从序号i开始的j个字符组成的子串，len（三）返回串S的长度，则COn（SUbS（S1,2,len（s2）,subs（si,len（s2）,2）的结果串是（）«A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF7 .二叉树是非线性数据结构，所以（A.它不能用顺序存储结构存储；B.它不能用链式存储结构存储；C.顺序存储结构和链式存储结构都能存储；D.顺序存储结构和链式存储结构都不能使用8 .有8个结点的无向连通图最少有（）条边。A.5B.6C.7D.89 .折半查找有序表（4,6,10,12,20,30,50,70,88,100）。若查找表中元素58,则它将依次与表中（）比较大小，查找结果是失败。A.20,70,30,50B.30,88,70,50C.20,50D.30,88,5010 .把棵树转换为二叉树后，这棵二叉树的形态是（）=A.有多种B.唯一的C.有多种,但根结点都没有左孩子D.有多种,但根结点都没有右孩子1、设H为带头结点单向循环链表的头指针，指针域为Iink,P为移动指针，则表尾的判断条件是（）A. 11->link=HB.P=IIC.P->link=NU1.1.D.P->link=H2、若一个栈的输入序列是1,2,3,，n,输出序列的第一个元素是n,则第X个输出元素是（）B. n-B.n-+lC.XD.n-l3、广义表A=（a,（b）,（）,（c,d,e）的长度为（）C. 4B、5Cx6D、74、将一个Al.100,1.100的下三对角矩阵，按以行优先存入一维数组B1.298中，A中元素a依6s（即该元素下标i=66,j=65）在数组中的位置k为（）。A、194B、195C、196D、1975、以4,5,6,7,8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是（）。A、65B、67Cs68D、696、具有200个结点的完全二叉树的深度为（）A、6B、7C、8D、97、有向图的邻接矩阵是一个（）A、对称矩阵B、上三角矩阵C、对角矩阵D、上述说法都不对8、对线性表进行折半查找时，要求线性表必须（）A、以顺序方式存储B、以够接方式存储C、以顺序方式存储，且结点按关键字有序排列D、以链接方式存储，且结点按关键字有序排列9、快速排序在（）情况下最不利于发挥其特长。A被排序的数据量太大B被排序的含有多个相同值C被排序的数据已基本有序D被排序的数据中有实数10、以下序列不是堆的是（）A（100,85,98,77,80,60,82,40,20,10,66）B（100,95,85,82,80,77,66,60,40,20,10）C（10,20,40,60,66,77,80,82,85,98,100）D（100,85,40,77,80,60,66,98,82,10,20）1 .算法分析的两个主要方面是（）A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性2 .链表是一种采用（）存储结构存储的线性表A.顺序B.磅式C星式D.网状3、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（）结构。A堆栈B数组C队列D线性表4 .线性表1.在（）情况下适用于使用锌式结构实现。A.需经常修改1.中的结点值B.1.中结点结构复杂C1.中含有大量的结点D.需不断对1.进行删除插入5、先序遍历能得到A,B,C序列的不同二叉树，最多有几种（）A4B5C6D76、若树中用一条线段把两个结点连接起来，则（）（.A不一定出现环B一定出现环C使树的度数增1D前面说法都不正确7、在一个图中，所有顶点的度数之和等于所有边数的（）倍。A1/2B1C2D48、无向图中定义顶点Vi与Vj之间的路径为从Vi到达Vj的一个（）A顶点和边序列B边的条数C权值总和D边序列9、任何一个无向连通图的最小生成树()A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在10 .折半查找与二叉排序树查找的时间性能()A.相同B.完全不同C.数量级都是O(Iog?n)D.有时不相同11 在下列存储结构中，具备随机存取特性的是().顺序表B.单链表C.单循环链表D.带头结点的双循环链表12 在循环双向链表的P所指结点之后插入q所指结点，可执行()操作来完成。abCA. q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;B. q->prior=p;q->next=p->next;p->next=q