搜索
一、是非题1.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。.......................(T)2.线性表的逻辑顺序与物理顺序总是一致的........(F)3.线性表中的每个结点最多只有一个前驱和一个后继。......(T)4.线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。.......................(F)5.栈和队列逻辑上都是线性表。..........................(T)6.单链表从任何一个结点出发，都能访问到所有结点........(F)7.单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。.................................................(T)8.在用单链表表示的链式队列中，队头在链表的链尾位置。....(F)9.多维数组是向量的推广。..............................(T)10.栈是一种先进先出的线性表。....(F)11.凡是递归定义的数据结构都可以用递归算法来实现它的操作。......(T)12.设串S的长度为n,则S的子串个数为n(n+1)/2。...........(F)13.一般树和二叉树的结点数目都可以为0。................(F)14.按中序遍历二叉树时，某结点的直接后继是它的右子树中第1个被访问的结点。....(T)15.后序序列和中序序列能唯一确定一棵二叉树。....(T)16.对于一棵具有n个结点，其高度为h的二叉树，进行任—种次序遍历的时间复杂度为O(n).............(T)17.网络的最小代价生成树是唯一的。...(T)18.图的拓扑有序序列不是唯一的。...(T)19.进行折半搜索的表必须是顺序存储的有序表。...(T)二、单选题1.算法指的是（D）A．计算机程序B．解决问题的计算方法C．排序算法D．解决问题的有限运算序列2.线性表采用链式存储时，结点的存储地址（B）A．必须是不连续的B．连续与否均可C．必须是连续的D．和头结点的存储地址相连续3.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（C）A．O（1）B．O（n）C．O（m）D．O（m+n）4.在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为(B)。A．O(n)B．O(1)C．O(n2)D．O(log2n)T5.线性表L在(B)情况下适用于使用链式结构实现。A.需经常修改Ｌ中的结点值B.需不断对Ｌ进行删除插入C.L中含有大量的结点D.L中结点结构复杂6.设单链表中结点的结构为(data，1ink)。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作?(B)A．s一1ink=p一1ink；p一1ink＝sB．q一1ink＝s；s一link=pC．p一link＝s一1ink；s一1ink＝pD．p一1ink＝s；s一1ink＝q7.已知指针p所指不是尾结点，若在*p之后插入结点*s，应执行下列哪个操作(B)A.s-link=p；p-link=s；B.s-link=p-link；p-link=s；C.s-link=p-link；p=s；D.p-link=s；s-link=p；8.非空的循环单链表first的尾结点（由p所指向）满足：(C)A.p-link==NULL；B.p==NULL；C.p-link==first；D.p==first；9.若让元素1，2，3依次进栈，则出栈次序不可能出现(C)种情况。A．3，2，1B．2，1，3C．3，1，2D．1，3，210.若进栈序列为1234，则不可能得到的出栈序列是C。A）3，2,1，4B）3,2，4,1，C）4,2，3,1D）2,3，4,111.由两个栈共享一个向量空间的好处是：（B）A．减少存取时间，降低下溢发生的机率B．节省存储空间，降低上溢发生的机率C．减少存取时间，降低上溢发生的机率D．节省存储空间，降低下溢发生的机率12.对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为......................(D)A．R-FB.n+R-FC.(R-F+1)modnD.(n+R-F）modn13.在一个链队列中,假定front和rear分别为队首和队尾指针，则插入指针s所指的结点的操作为C。A）front-next=s;B)s-next=rear;rear=s;C)rear-next=s;rear=s;D)s-next=front;front=s;14.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（D）A．front=front+1B．front=(front+1)%(m-1)C．front=(front-1)%mD．front=(front+1)%m15.如下陈述中正确的是（A）A．串是一种特殊的线性表B．串的长度必须大于零C．串中元素只能是字母D．空串就是空白串16.一个非空广义表的表头（D）A．不可能是子表B．只能是子表C．只能是原子D．可以是子表或原子17.一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程(B)。A.较快B.较慢C.相同D.不一定18.树中所有结点的度等于所有结点数加(C)。A.0B.1C.一1D.219.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于(C)。A.nB.n一1C.n+1D.2*n20.某二叉树的前序序列和后序序列正好相反，则该二叉树一定是B的二叉树。A）空或只有一个结点。B）高度等于其结点数。C）任一结点无左孩子。D）任一结点无右孩子。21.n个结点的二叉树，若用二叉链表存贮则非空闲的左、右孩子链域为C。A）nB)2nC)n-1D)n+122.在有n个叶子结点的哈夫曼树中，其结点总数为D。(性质3)A）不确定B）2nC）2n+1D）2n-123.已知二叉树叶子数为50，仅有一个孩子的结点数为30，则总结点数为B。A130B129C131D不确定24.在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为(C)A．4B．5C．6D．725.假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是(C)A．O(n)B．O(e)C．O(n+e)D．O(n*e)26.在无向图中定义顶点vi与vj之间的路径为从vi到达vj的一个(A)。A、顶点序列B、边序列C、权值总和D、边的条数27.用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是（D）A．选择排序B．希尔排序C．归并排序D．快速排序28.适于对动态查找表进行高效率查找的组织结构是（C）A．有序表B．分块有序表C．三叉排序树D．线性链表29.如果只想得到1024个元素组成的序列中的前5个最小元素，那么用(D)方法最快。A、起泡排序B、快速排序C、堆排序D、直接选择排序三、填空题1.数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储结构无关，是独立于计算机的。2.评价数据结构的两条基本标准是：存储需要量和运算的时间效率。3.算法的五个特性是指有穷性、确定性、可行性、输入和输出。4.在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=p－next－next。5.设单链表中指针P指向结点m，若要删除m之后的结点（若存在），则需修改指针的语句是：P-next=p-next-next6.设有一个顺序栈S，元素sl，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，sl，则顺序栈的容量至少应为3。7.栈的特点是：后进先出，栈顶的位置是随着进栈和出栈_操作而变化的。8.若有一个栈的输入序列为1,2,3,….n，输出序列的第一个元素为n，则第i个输出元素是n-i+19.队列的特点是：先进先出，其插入操作在队尾进行，删除操作在队头进行。10.有数据元素1、2、3，依次进队列，其出队列序列为123。11.已知广义表A=(a,(b,(c,d))),则表尾是((b,(c,d)))，深度为3。12.广义表A((a，b，c)，(d，e，f))的表头为(a，b，c)，长度为2。13.在串S=“stud”中，子串有11个。14.设s1=”study”,s2=”hard”,则调用函数strcat(s1,s2)后得到studyhard。15.将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中。对于任意给定数组元素A[I][J]，如果它能够在数组B中找到，则它应在2*I+J位置。16.通常程序在调用另一个程序时，都需要使用一个栈来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。17.假定一棵树的广义表表示为A（B（E（K，L），C（G），D(H(M),I,J)））,则该树的度为3，树的深度为3。18.深度为n的二叉树最多有2n-1个结点。19.设二叉树的根为第一层，则第i层上的结点数最多有2i-1。(性质1)20.在一棵二叉树中，度为2的结点的个数是5，则叶结点的个数为6。(性质3)21.n个结点的完全二叉树，其深度h=[log2n]+1。22.在一棵树中，有且仅有一个结点没有前驱，称为根结点;非根结点有且仅有一个双亲。23.在一棵度为二叉树中,度为2的结点个数为8,则叶结点个数为924.已知一颗完全二叉树中共有767结点，则该树中共有384个叶子结点。25.200个结点的完全二叉树，其深度h=8。26.对有n个结点的完全二叉树，编号为i(i1)结点的双亲结点的编号为i/2，当i%2==0时，该结点是其双亲的左孩子。27.一颗有6个结点的完全二叉树，其结点按编号存放数据为：A、B、C、D、E、F，若按中根遍历该树得到的数据序列为：DBEAFC。28.n个顶点的无向完全图具有n(n-1)/2条边，n个顶点的有向完全图具有n(n-1)条弧。29.在一个图中，所有顶点的度之和等于所有边数的2倍。30.n个顶点的连通图的生成树具有n-1条边。31.关键路径是指AOE-网中从源点到汇点路径长度最大的路径。32.顺序查找的平均查找长度为O(n)折半查找只适用于有序表，且限于顺序存储结构，其平均查找长度为：O(log2n)。34.设有100个元素，用折半查找时，最大比较次数是7。35.若按中序遍历二叉排序树可得到一个关键字的有序序列。36.在对一组记录（10,50,25,70,35,22,30,85,40）进行直接插入排序时，当把第6个记录22插入到有序表时，为寻找插入位置需比较2次。37.希尔排序是属于直接插入排序的改进方法。38.对一组记录（50,40,95,20,15,70,60,45,80）进行简单选择排序时，第4次交换和选择后，未排序记录（即无序数）为50，70，60，95，80。39.在单链表上难以实现的排序方法有快速排序、堆排序、希尔排序40.在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为___2__。四、解答题1.线性表的顺序存储表示和链式存储表示的特点比较。2.什么是子串?空串和空格串有什么区别？串有哪几种机内表示方法,通常采用哪一种？3.已知广义表A=（（a,b）,c,（d,e,f）)试画出它的存贮结构图。4.已知