02142数据结构导论复习题

1、数据结构导论模拟试题一、考试题型及分值分布：1、单项选择题(本大题共15小题，每小题2分，共30分)2、填空题(本大题共13小题，每小题2分，共26分)3、应用题(本大题共5小题，每小题6分，共30分)4、算法设计题(本大题共2小题，每小题7分，共14分)二、单项选择题和填空题样题参考(一)单项选择题1 .在二维数组中，每个数组元素同时处于()个向量中。A.0B.1C.2D.n2 .已知单链表A长度为m,单链表B长度为n,它们分别由表头指针所指向，若将B整体连接到A的末尾，其时间复杂度应为()。A.O(1)B.O(m)C.O(n)D.O(m+n)3 .假定一个链式队列的队头和队尾指针分别为fr

2、ont和rear,则判断队空的条件为()。A.front=rearB.front!=NULLC.rear!=NULLD.front=NULL4 .若让元素1,2,3依次进栈，则出栈次序不可能出现()种情况。A.3,2,1B.2,1,3C.3,1,2D.1,3,25 .图的广度优先搜索类似于树的()遍历。A.先根B.中根C.后根D.层次6 .下面程序段的时间复杂度为()。for(inti=0;i<m;i+)for(intj=0;j<n;j+)aij=i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)7 .设有两个串t和p,求p在t中首次出现的位置的运算叫做()。A.

3、求子串B.模式匹配C.串替换D.串连接8利用双向链表作线性表的存储结构的优点是()。A.便于单向进行插入和删除的操作B.便于双向进行插入和删除的操作C.节省空间D.便于销毁结构释放空间9 .设链式栈中结点的结构为(data,link),且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行()操作。A.top->link=s;B.s->link=top->link;top->link=s;C.s->link=top;top=s;D.s->link=top;top=top->link;10 .一棵具有35个结点的完全二叉树的高度

4、为()。假定空树的高度为-1。A.5B.6C.7D.811 .一个有n个顶点和n条边的无向图一定是()的。A连通B.不连通C.无回路D.有回路12 .在一个长度为n的顺序表的任一位置插入一个新元素的时间复杂度为()。A.O(n)B.O(n/2)C.O(1)D.O(n2)13 .已知广义表为A(a,b,c),(d,e,f)，从A中取出原子e的运算是()。Head(Tail(A)ATail(Head(A)CHead(Tail(Head(Tail(A)D.Head(Head(Tail(Tail(A)14 .在一棵树的静态双亲表示中，每个存储结点包含()个域。A1B2C3D415 .有向图中的一个顶点

5、的度数等于该顶点的()。A入度B.出度C.入度与出度之和D.(入度+出度)/216 .与邻接矩阵相比，邻接表更适合于存储()。A无向图B.连通图C.稀疏图D.稠密图17 .较快的数据搜索方法是()搜索方法。A.顺序B.折半C.单链D.散列18 .在闭散列表中，散列到同一个地址而引起的“堆积”问题是由于()引起的。A.同义词之间发生冲突B.非同义词之间发生冲突C.同义词之间或非同义词之间发生冲突D.散列表“溢出”19 .根据n个元素建立一个有序单链表的时间复杂度为()。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)20 .假定一个顺序存储的循环队列的队头和队尾指针分别为front和

6、rear,则判断队空的条件为()。A.front+1=rearB.rear+1=frontC.front=0D.front=rear21 .假定一棵二叉树的第i层上有3i个结点，则第i+1层上最多有()个结点。A.3iB.6iC.9iD.2i22 .对于具有e条边的无向图，它的邻接表中共有()个边结点。Ae-1B.e+1C.2eD.3e23 .图的深度优先搜索遍历类似于树的()次序遍历。A.先根B.中根C.后根D.层次24 .栈S最多能容纳4个元素。现有6个元素按A、BC、DE、F的顺序进栈，问下列哪一个序列是可能的出栈序列?()A. E、DCBA、FB.B、CE、F、A、DC.CBEDAFD

7、.ADFEBC25 .将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1,则编号为49的结点的左孩子的编号为：()A.98B.99C.50D.4826 .对下列关键字序列用快速排序法进行排序时，速度最快的情形是：()A. 21、255、17、9、23、30B. 25、23、30、17、21、5、9B. 219173025235D.59172123253027 .对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为()A.顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表28 .假设以第一个元素为分界元素，对字符序列(Q,

8、H,C,Y,P,A,M,S,R,D,F,X)进行快速排序，则第一次划分的结果是：()A. (A,C,D,F,H,M,P,Q,R,S,X,Y)B. (A,F,H,C,D,P,M,Q,R,S,Y,X)C. (F,H,C,D,P,A,M,Q,R,S,Y,X)D. (P,A,M,F,H,C,D,Q,S,Y,R,X)29 .下面是三个关于有向图运算的叙述：()（1）求有向图结点的拓扑序列，其结果必定是唯一的（2）求两个指向结点间的最短路径，其结果必定是唯一的（3）求AOE网的关键路径，其结果必定是唯一的其中哪个（些）是正确的？A.只有（1）B.（1）和（2）C,都正确D.都不正确30 .若进栈序列为a,

9、b,c,则通过入出栈操作可能得到的a,b,c的不同排列个数为（）A.4B.5C.6D.731 .以下关于广义表的叙述中，正确的是：（）A.广义表是由0个或多个单元素或子表构成的有限序列B.广义表至少有一个元素是子表C.广义表不能递归定义D）广义表不能为空表32 .排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？（）C. 快速排序D.冒泡排序要删除所有从第i个结点发出的边，应该：（）B.将邻接矩阵的第i行元素全部置为0D. 将邻接矩阵的第i列元素全部置为0头指针为head,则其为空的条件是：（）A.堆排序B.直接插入排序33 .已知一个有向图

10、的邻接矩阵表示,A.将邻接矩阵的第i行删除C.将邻接矩阵的第i列删除34.有一个含头结点的双向循环链表,A.head->priro=NULLB.head->next=NULLC.head->next=headD.head->next->priro=NULL35 .在顺序表（3,6,8,10,12,15,16,18,21,25,30）中，用折半法查找关键码值11,所需的关键码比较次数为：（）A.2B.3C.4D.536 .以下哪一个不是队列的基本运算？（）A.从队尾插入一个新元素B.从队列中删除第i个元素C.判断一个队列是否为空D.读取队头元素的值37 .对包含n个

11、元素的哈希表进行查找，平均查找长度为：（）A.O（log2n）B.O（n）C.O（nlog2n）D不直接依赖于n38 .将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1,则编号最大的非叶结点的编号为：（）A.48B.49C.50D.5139 .某二叉树结点的中序序列为A、B、C、DE、F、G后序序列为B、D、CA、FGE,则其左子树中结点数目为：（）A.3B.2C.4D.540 .下面是顺序存储结构的优点。A.存储密度大B.插入运算方便C.查找方便D.适合各种逻辑结构的存储表示41 .下面关于串的叙述中，是不正确的。A.串是字符的有限序列B.空串

12、是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储42 .的邻接矩阵是对称矩阵。A.有向图B.无向图C.AOV网D.AOE网43 .用链式方式存储的队列，在进行删除运算时，。仅修改尾指针头、尾指针可能都要修改A.仅修改头指针B.C.头、尾指针都要修改D.44 .二叉树的先序遍历和中序遍历如下，则该二叉树右子树的树根是.先序序列：EFHIGJK中序序列：HFIEJKGA.EB.FC.GD.H45 .下面方法可以判断出一个有向图中是否有环。A.深度优先遍历B.拓朴排序C.求最短路径D.求关键路径46 .从未排序序列中依次取出一个元素与已排序序列中的元素依次进

13、行比较，然后将其放在已排序序列的合适位置，该排序方法称为排序法。A.插入B.选择C.冒泡D.都不是47 .一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是。A.edcbaB.decbaC.dceabD.abcde48 .n个节点的完全二叉树，编号为i的节点是叶子结点的条件是。A.i<nB.2*i<=nC.2*i+1>nD.2*i>n49 .向一个有128个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素。A.64.5B.64C.63D.6550 .在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行。A.q-&

14、gt;next=p->next;p->next=q;B.p->next=q->next;q=p;C.p->next=p->next;q->next=q;D.p->next=q->next;q->nxet=p;51 .对一个满二叉树，m个树叶，n个结点，深度为h,则有。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-152 .在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是A.选择排序B.冒泡排序C.插入排序D.希尔排序53 .用链式方式存储的队列，在进行插入运算时，。A.仅修改头指针B.仅修改尾指针C.头、尾指

15、针都要修改D.头、尾指针可能都要修改54 .在一个长度为n的顺序存储的线性表中，向第i个元素（1WiWn+1）插入一个新元素时，需要从后向前依次后移个元素。A.n-iB.n-i-1C.n-i+1D.i55 .一个栈的入栈序列是12345,则栈的不可能的输出序列是。A.23415B.54132C.23145D.1543256 .5个顶点的有向图最多有条弧。A.5B.20C.4D.2557 .假定一个链队的队首和队尾指针分别为front和rear,则判断队空的条件为。A.front=rearB.front!=NULLC.rear!=NULLD.front=NULL58 .若某线性表中最常用的操作是

16、提取第i个元素及找第i个元素的前驱元素，则采用（）存储方式最省时间。A.单链表B.双链表C.单向循环链表D.顺序表59 .将含有100个结点的完全二叉树从根开始自上向下，每层从左到右依次编号，且设根结点的编号为1,则编号69的结点的双亲的编号为（）。A.34B.35C.33D.无法确定60 .单循环链表的主要优点是（）。A.不再需要头指针了B.已知某结点的位置后，很容易找到其前驱C.在进行插入、删除运算时，能更好地保证链表不断开D.从表中任一结点出发都能扫描到整个链表61 .一个栈的入栈顺序是1、2、3、4、5,则此栈不可能的输出顺序为（）。A.5、4、3、2、1B.4、5、3、2、1C.4、

17、3、5、1、2D.1、2、3、4、562 .串是一种特殊的线性表，其特殊性表现在（）。A.可以顺序存储B.数据元素是一个字符C可以链式存储D.数据元素是多个字符63 .n个顶点的无向图中最多有（）条边。A.n（n-1）/2B.n（n-1）C.n（n+1）D.n（n+1）/264 .6个顶点的无向图中，至少有（）条边才能保证是一个连通图。A.5B.6C.7D.865 .若某线性表中最常用的操作是删除第1个元素，则不宜采用（）存储方式。A.单链表B.双链表C.单向循环链表D.顺序表66 .在一棵完全二叉树的顺序存储方式中，若编号i的结点有右孩子，则其右孩子的编号为（）。A.2iB.2i-1C.2i

18、+1D.i/267 .按照二叉树的定义，具有3个结点的二叉树有（）种不同形态。A.3B.4C.5D.668 .在长为n的顺序表中，删除第i个元素（1wiwn+1）需要向前移动（）个元素。A.n-iB.n-i+1C.n-i-1D.i69 .一个队的入队顺序是1、2、3、4、5,则此队的出队顺序为（）。A.5、4、3、2、1B.4、5、3、2、1C.4、3、5、1、2D.1、2、3、4、570 .栈是一种特殊的线性表，其特殊性表现在（）。A.可以顺序存储B.只能从端点进行插入和删除C.可以链式存储D.可以在任何位置进行插入和删除71 .一棵二叉树中，第k层上最多有（）个结点。A.2kB.2k-1C

19、.2kD.2k-172 .一棵有18个结点的二叉树，其高度最小为（）层。A.4B.5C.6D.1873 .有向图中，所有顶点入度和是所有顶点出度和的（）倍。A.0.5B.1C.2D.4（二）填空题1 .数据元素之间存在的相互关系称为。2 .数据结构从逻辑上分为结构和结构。3 .线性表的顺序存储结构称为。4 .所有插入在表的一端进行，而所有删除在表的另一端进行的线性表称为5 .深度为h的二叉树，最少有个结点。6 .折半查找要求待查表为表。7 .n个记录按其关键字大小递增或递减的次序排列起来的过程称为8 .存储数据时，不仅要存储数据元素的,还要存储元素之间的相互。9 .将一棵有100个结点的完全二

20、叉树按层编号，则编号为49的结点X,其双亲PARENRX)的编号为。10、一个字符串相等的充要条件是和。11、在有向图的邻接表和逆邻接表表示中，每个顶点的边链表中分别链接着该顶点的所有和结点。11、在一个长度为n的顺序表中向第i个元素(0<iwn+1)之前插入一个新元素时，需要向后移动个元素。12、是只允许在表的一端进行插入，而在另一端进行删除的线性表。13、设主串T="abxxyxyxxbaa:模式串P="xyxx”则第次匹配成功。14、在一棵二叉树中，第5层上的结点数最多为。(根的层次为1)15、假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组中，其中B0

21、存储矩阵中第1个元素a1,1,则B31中存放的元素是。16、有n个结点的二叉链表中，其中空的指针域为n+1,指向孩子的指针个数为。17、二叉树后序遍历的顺序是ABCDE则该二叉树的根结点是。18、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则整个邻接表中的结点总数是。19、在单链表上难以实现的排序方法有和。20、查找法的平均查找长度与元素个数n无关。21、在有n个元素的顺序表的任意位置插入一个元素所需移动结点的平均次数为22、是插入和删除元素都在表的同一端进行的线性表。23、广义表L=(a,b,c,L)，则其长度为。24、在树中，除跟结点外，其他结点都有且只有一个结点。26、在串s

22、="structure"中，以t为首字符的子串有个。27、广度优先搜索遍历类似于树的按遍历的过程。28、已知一棵完全二叉树中共有768个结点为，则该树中共有个叶子结点。29、在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数为。30、两个长度分别m和n(m>n)的排好序的表归并成一个排好序的表，至少要进行次键值比较。通常从四个方面评价算法的质量：、和。31、 一个算法的时间复杂度为(n3+n210g2n+14n)/n2,其数量级表示为。32、 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针

23、。在这种存储结构中，n个结点的二叉树共有个指针域，其中有个指针域是存放了地址，有个指针是空指针。33、 对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有个和个。34、 在一个具有n个顶点的无向完全图中，包含有条边，在一个具有n个顶点的有向完全图中，包含有条边。35、 36.在快速排序、堆排序、归并排序中，排序是稳定的。36、 37.中序遍历二叉排序树所得到的序列是序列。38 .快速排序的最坏时间复杂度为,平均时间复杂度为。39 .设一组初始记录关键字序列为(55,63,44,38,75,80,31,56),则利用筛选法建立的初始堆为。40 .数据的物理结构主要

24、包括和两种情况。41 .设一棵完全二叉树中有500个结点，则该二叉树的深度为;若用二叉链表作为该完全二叉树的存储结构，则共有个空指针域。42、设输入序列为1、2、3,则经过栈的作用后可以得到种不同的输出序列。43、设有向图G用邻接矩阵Ann作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的，第i列上所有元素之和等于顶点i的。设哈夫曼树中共有n个结点,则该哈夫曼树中有个度数为1的结点。44、 设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d,则e和d的关系为45、 遍历二叉排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序)。46、 设查找表中有100个元素，如果

25、用二分法查找方法查找数据元素X,则最多需要比较次就可以断定数据元素X是否在查找表中。47、 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为48、 设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为,右孩子结点的编号为。49、 设一组初始记录关键字为(72,73,71,23,94,16,5),则以记录关键字72为基准的一趟快速排序结果为。50、 设有向图G中有向边的集合E=<1,2>,<2,3>,<1,4>,<4,2>,<4,3>,则该图的一种拓扑序列为。5

26、1、 下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。structrecordintkey;intothers;inthashsqsearch(structrecordhashtable,intk)inti,j;j=i=k%p;while(hashtablej.key!=k&&hashtablej.flag!=0)j=()%m;if(i=j)return(-1);if()return(j);elsereturn(-1);j+1,hashtablej.key=k52、 下列算法实现在二叉排序树上查找关键值k,请在下划线处填上正确的语句。typedefst

27、ructnodeintkey;structnode*lchild;structnode*rchild;bitree;bitree*bstsearch(bitree*t,intk)if(t=0)return(0);elsewhile(t!=0)if(t->key=k);elseif(t->key>k)t=t->lchild;else;return(t),t=t->rchild53、 设有n个无序的记录关键字，则直接插入排序的时间复杂度为，快速排序的平均时间复杂度为。54、 设指针变量p指向双向循环链表中的结点X,则删除结点X需要执行的语句序列为(设结点中的两个指针域分别为llink和rlink)。根据初始关键字序列(19,22,01,38,10)建立的二叉排序树的高度为3。55、 深度为k的完全二叉树中最少有2k-1个结点。56、 设初始记录关键字序列为(K1,K2,Kn),则用筛选法思想建堆必须从第_n/2_个元素开始进行筛选。59、设哈夫曼树中共有99个结点，则该树中有个叶子结点；若采用二叉链表作为存储结构，则该树中有个空指针域。60、设有一个顺序循环队列中有M个存储单