德州学院数据结构期末复习题

数据结构一、单选题1.对关键字序列（21,19,37,5,2），经直接插入排序法由小到大排序，第一趟后所得结果为（）。A.(19，21，37，5，2)B.(19，21，5，2，37)C.(19，21，5，37，2)D.(19，21，2，5，37)答案：A2.经过以下运算后，x的值是_________。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x)A.aB.bC.1D.0答案：A3.在长度为n的顺序表中插入一个元素的时间复杂度为_________。A.O(n)B.O(n2)C.O(log2n)D.O(1)答案：A4.设图G=(V,VR)，其中:V={A,B,C,D,G}，VR={(A,C),(A,D),(B,C),(B,D),(G,C),(B,G)}，则对应的图形为____________。A.B.C.D.答案：A5.已知一个栈的进栈序列是1，2，3，…n，其输出序列的第一个元素是i（1≤i≤n），则第j（1≤j≤n）个出栈元素是_________。A.iB.n-iC.j-i+1D.不确定答案：D6.两个表长都为n、不带表头结点的单链表，结点类型都相同，头指针分别为h1与h2，且前者是循环链表，后者是非循环链表，则_________。A.对于两个链表来说，删除首节点的操作，其时间复杂度都是O(1)B.对于两个链表来说，删除尾节点的操作，其时间复杂度都是O(n)C.循环链表要比非循环链表占用更多的内存空间D.h1和h2是不同类型的变量答案：B7.假设一组待排序的关键字序列为（24,62,36,19），要求从小到大进行排序，（）是归并排序的过程。A.(24，62，19，36)(19，24，36，62)B.(62，24，36，19)(19，24，36，62)‍C.(24，62，36，19)(24，36，62，19)(19，24，36，62)D.(24，19，36，62)(24，19，36，62)(19，24，36，62)答案：A8.与单链表相比，双链表的优点之一是_________。A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针D.访问前后相邻节点更方便答案：D9.求一个单链表长度的算法的时间复杂度为_________。A.O(log2n)B.O(n)C.O(1)D.O(n2)答案：B10.在一个双链表中，在*p节点之后插入节点*q的操作是_________。A.q-＞prior=p；p-＞next=q；p-＞next-＞prior=q；q-＞next=p-＞next；B.q-＞next=p-＞next；p-＞next-＞prior=q；p-＞next=q；q-＞prior=p；C.p-＞next=q；q-＞prior=p；q-＞next=p-＞next；p-＞next-＞prior=q；D.p-＞next-＞prior=q；q-＞prior=p；p-＞next=q；q-＞next=p-＞next；答案：B11.使用三元组顺序表或十字链表作为稀疏矩阵中的物理结构，对元素的访问形式只能是_____________。A.随机访问B.哈希访问C.顺序访问D.索引访问答案：C12.n个顶点的有向图为强连通图时，至少含有__________。A.n-1条弧B.n条弧C.n(n-1)/2条弧D.n(n-1)条弧答案：B13.以行序优先顺序存储数组A[5][5]；假定A[0][0]的地址为1000,每个元素占4个字节，下标变量A[4][3]的地址是_____。A.1023B.1046C.1069D.1092答案：D14.在下列排序方法中，（）排序方法的平均时间复杂度不是O（）.A.直接选择B.快速C.直接插入D.冒泡答案：B15.线性表是_________。A.一个有限序列，可以为空B.一个有限序列不可以为空C.一个无限序列，可以为空D.一个无限序列，不可以为空答案：A16.在一个长度为n（n＞1）的带头节点的单链表上，另设有尾指针r（指向尾节点），执行_________操作与链表的长度有关。A.删除单链表中的第一个元素B.删除单链表的尾节点C.在单链表中第一个元素前插入一个新节点D.在单链表最后一个元素后插入一个新节点答案：B17.设n个元素的进栈序列是p1,p2,…pn，其输出序列是1,2,3，…n，若p3=1，则p1的值是_________。A.可能是2B.一定是2C.不可能是2D.不可能是3答案：C18.对广义表G=((a,((),b)),(((),(c,d)),()))执行tail(head(head(tail(G))))操作的结果是____________。A.()B.cC.(c,d)D.((c,d))答案：D19.对如图所示的无向连通网，从顶点A出发，使用Prim算法得到的最小生成树是__________。A.B.C.D.答案：B20.用13个权值构造哈夫曼树，则该哈夫曼树共有个结点。A.13B.12C.26D.25答案：D21.表达式a*(b+c)-d的后缀表达式是_________。A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd答案：B22.某线性表最常用的操作是在尾元素之后插入一个元素和删除尾元素，则采用_________存储方式最节省运算时间。A.单链表B.循环单链表C.双链表D.循环双链表答案：D23.设有一个10行10列的矩阵A，采用行序优先存储方式。如果A[0][0]为第一个元素，其存储地址为1000，A[2][3]的存储地址为1069，则存储一个元素需要的单元数是____________。A.1B.2C.3D.4答案：C24.给定一棵树的二叉链表存储结构，把这棵树转换为二叉树后，这棵二叉树的形态是。A.唯一的B.有多种C.有多种，但根结点都没有左孩子D.有多种，但根结点都没有右孩子答案：A25.设有n个顶点e条弧的有向图，采用邻接表作为物理结构，则求某顶点Vi度的算法的时间复杂度为____________。A.O(n2)B.O(n*e）C.O(n+e）D.O(n）答案：C26.线性表是具有n个________的有限序列。A.表元素B.字符C.数据元素D.数据项答案：C27.假设待排序的表长为n，那么创建堆需要时间复杂度为（）。A.O(1)B.O(㏒n)C.O(n)D.O(n㏒n)答案：C28.先序遍历序列为ABC，后序遍历序列为CBA的二叉树共有棵。A.1B.2C.3D.4答案：D29.在一个双链表中，删除*p节点的操作是_________。A.p-＞prior–＞next=p-＞next；p-＞next-＞prior=p-＞prior；B.p-＞prior=p-＞prior-＞prior；p-＞prior-＞prior=p；C.p-＞next-＞prior=p；p-＞next=p-＞next-＞next；D.p-＞next=p-＞prior-＞prior；p-＞prior=p-＞prior-＞prior；答案：A30.假设用一个不带表头节点的单链表表示队列，在进行删除操作时，_________。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改答案：D31.设有一个5行4列的矩阵A，采用行序优先存储方式，A[0][0]为第一个元素，其存储地址为1000，A[2][2]的地址为1040，则A[3][0]的地址为____________。A.1024B.1048C.1060D.1096答案：B32.广义表((a,b),(c),(d))的表尾是________。A.(d)B.dC.(a,b)D.((c),(d))答案：D33.广义表((a,()),(b,(c)),(()))的深度是________。A.3B.4C.5D.6答案：A34.一棵二叉树的先序遍历序列为EFHIGJK,中序遍历序列为HFIEJKG,则该二叉树根结点的右孩子为。A.EB.FC.GD.H答案：C35.某无向图的邻接矩阵如下所示，可以得出，该图共有_____________个顶点。A.3B.4C.9D.5答案：A36.对于一个具有n个元素的线性表，建立其单链表的时间复杂度为_________。A.O(log2n)B.O(1)C.O(n)D.O(n2)答案：C37.最小生成树是指__________。A.连通网的所有生成树中权值之和最小的生成树B.由连通网得到的边数最少的生成树C.由连通网得到的顶点数相对较少的生成树D.连通网的极小连通子图答案：A38.使用三元组顺序表作为稀疏矩阵中的物理结构，要求对三元组按行序优先的顺序进行存放，原因是按行序优先能_____________。A.节省存储空间B.方便稀疏矩阵的运算C.提高元素的访问速度D.使元素的摆放形式漂亮一些答案：B39.若一个栈用数组data[1..n]存储，初始栈顶指针top为n+1，则以下元素x进入栈的正确操作是_________。A.top++;data[top]=x;B.data[top]=x;top++;C.top--;data[top]=x;D.data[top]=x;top--;答案：C40.要求线性表采用静态空间分配方式，且插入和删除操作时不需要移动元素，采用的存储结构是_________。A.单链表B.静态链表C.双链表D.顺序表答案：B41.下列叙述中，不正确的是_____________。A.数组是一种线性结构B.数组是一种定长的线性表C.除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等D.数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作答案：C42.对于下列排序，（）的最坏时间复杂度是O(n㏒n)。A.直接插入排序B.直接选择排序C.归并排序D.冒泡排序答案：C43.下列叙述中，不正确的是________。A.对称矩阵只需要存放包括对角线元素在内的下（或上）三角元素即可B.对角矩阵只需要存放其值不一定为0的对角线上元素C.稀疏矩阵中值为0的元素较多，因此可以采用三元组方法存储非零元素D.稀疏矩阵中大量值为0的元素分布有规律，因此可以采用三元组表方法存储答案：D44.最不合适用做链队的不带头节点的链表是_________。A.只带队首节点指针的非循环单链表B.只带队首节点指针的循环双链表C.只带队尾节点指针的循环双链表D.以上都不合适答案：A45.设10*10的对称矩阵下三角保存SA[1．．55]中，其中A[1][1]保存在SA[1]中，A[5][3]保存在SA[k]中，这里k等于____________。A.12B.13C.14D.15答案：B46.在一个双链表中，在*p节点之前插入节点*q的操作是_________。A.p-＞prior=q；q-＞next=p；p-＞prior-＞next=q；q-＞prior=p-＞prior；B.q-＞prior=p-＞prior；p-＞prior-＞next=q；q-＞next=p；p-＞prior=q-＞next；C.q-＞next=p；p-＞next=q；q-＞prior-＞next=q；q-＞next=p；D.p-＞prior-＞next=q；q-＞next=p；q-＞prior=p-＞prior；p-＞prior=q；答案：D47.在一个无向图中所有顶点的度数之和等于所有边数的____________倍。A.1B.2C.3D.1/2答案：B48.对稀疏矩阵进行压缩存储方法一般有两种，分别为__________。A.三元组和对称矩阵B.对角矩阵和散列C.散列和十字链表D.三元组顺序表和十字链表答案：D49.下列四种排序中，（）的辅助空间复杂度是最高的。A.堆排序B.快速排序C.简单选择排序D.直接插入排序答案：B50.循环队列qu的队满条件（front队首指针指向队首元素的前一位置，rear队尾指针指向队尾元素）是_________。A.(qu.rear+1)%maxsize==(qu.front+1)%maxsizeB.(qu.rear+1)%maxsize==qu.front+1C.(qu.rear+1)%maxsize==qu.frontD.qu.rear==qu.front答案：C51.设线性表有n个元素，以下操作中，_________在顺序表上实现比在链表上实现效率高。A.输入第i（1＜=i＜=n）个元素值B.交换第1个元素第2个元素的值C.顺序输出这n个元素的值D.输出与给定值x相等的元素在线性表中的符号答案：A52.对图进行深度优先搜索遍历，需要借助的数据结构为__________。A.栈B.队列C.线索二叉树D.广义表答案：A53.栈和队列的不同点是_________。A.都是线性表B.都不是线性表C.栈只能在一端进行插入删除操作，而队列在不同端进行插入删除操作D.没有不同点答案：C54.设有5个结点的无向图，该图至少应有____________条边才能确保是一个连通图。A.5B.6C.7D.8答案：C55.设有n个顶点e条边的无向图，采用邻接矩阵作为物理结构，则删除与某顶点Vi关联的所有边算法的时间复杂度为____________。A.O(n2)B.O(n*e）C.O(n+e）D.O(n）答案：D56.在下列排序算法中，（）排序算法可以避免在排序过程中移动数据元素。A.折半插入B.表插入C.2-路插入D.希尔答案：B57.以下关于单链表的叙述中，不正确的是_________。A.节点除自身信息外还包括指针域，因此存储密度小于顺序存储结构B.逻辑上相邻的元素物理上不必相邻C.可以通过头节点直接计算第i个节点的存储地址D.插入、删除运算操作简单，不必移动节点答案：C58.下列各项键值（）序列不是堆的。A.(5，23，16，68，94)‍B.(5，16，23，68，94)C.(5，23，16，94，68)D.(5，23，68，16，94)答案：D59.判定一个顺序栈st为（元素个数最多为MaxSize）空的条件为_________。A.st.top==-1B.st.top!=-1C.st.top!=MaxSizeD.st.top==MaxSize答案：A60.广义表(a,(b,c),d)的表长是________。A.3B.4C.5D.6答案：A61.链表不具备的特点是_________。A.可随机访问任一节点B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与其长度成正比答案：A62.不使用栈实现二叉树后序遍历的非递归算法，最佳方案是二叉树的存储结构采用表示。A.二叉链表B.广义表C.三叉链表D.顺序表答案：C63.在下图中，从顶点A出发进行深度优先遍历可得到的序列是____________。A.ADCBGB.ACDBGC.ADGBCD.ABDCG答案：D64.某稀疏矩阵A采用三元组顺序表作为存储结构，对于矩阵元素的赋值运算Assign(A,e,i,j)，不可能____________。（在Assign(A,e,i,j)中，e是矩阵元素Ai,j的值，i和j分别为矩阵元素的行号和列号）。A.修改某个三元组的行号或列号B.插入一个新的三元组C.修改某个三元组的元素值D.删除一个三元组答案：A65.假设待排序的表长为n，那么下列排序算法中，（）排序算法需要O(n)的辅助空间。A.简单选择B.插入C.冒泡D.归并答案：D66.若二叉树采用二叉链表存储结构，要交换所有分支结点的左右子树的位置，利用基于遍历的递归算法最合适。A.逆中序B.中序C.后序D.层次答案：C67.链栈与顺序栈相比有一个明显的优点，即_________。A.插入操作更方便B.通常不会出现栈满的情况C.总是不会出现栈空的情况D.删除操作更加方便答案：B68.在单链表中，要删除某一指定的节点，必须找到该节点的_________节点。A.后继B.头节点C.前驱D.尾节点答案：C69.二叉树采用二叉链表存储结构存储，根指针为t，下列递归算法求其叶子结点的个数,算法的画线处应填的语句是。A.t-＞lchild==NULLB.t-＞lchild==NULL＆＆t-＞rchild!=NULLC.t-＞rchild==NULLD.t-＞lchild==NULL＆＆t-＞rchild==NULL答案：D70.下列关于工程计划的AOE网的叙述中，不正确的是____________。A.关键活动不按期完成，会影响整个工程的完成时间B.任何一个关键活动的提前完成，整个工程的完成时间都会提前C.所有关键活动都提前完成，会提前整个工程的完成时间D.某个关键活动提前完成，可能会提前整个工程的完成时间答案：B71.经过以下栈运算后，StackEmpty(s)的值是_________。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y)A.aB.bC.1D.0答案：C72.由树转换成的二叉树里，一个结点N的左孩子是N在原树里对应结点的。A.最左孩子结点B.最右孩子结点C.最邻近的右兄弟D.最邻近的左兄弟答案：A73.若某循环队列有队首指针front和队尾指针rear，在队不满时进队操作仅会改变_________。A.frontB.rearC.front和rearD.以上都不对答案：B74.设一个栈的输入序列为A.ABCDB.DCBAC.ACDBD.DABC答案：D75.线性表的静态链表存储结构与顺序存储结构相比，优点是_________。A.所有的操作算法实现简单B.便于随机存取C.便于插入和删除D.便于利用零散的存储器空间答案：C76.如果最常用的操作时取第i个元素及前驱元素，则采用_________存储方式最节省时间。A.单链表B.双链表C.循环单链表D.顺序表答案：D77.假设待排序的表长为n，那么快速排序算法需要（）的辅助空间。A.O(1)B.O(㏒n)C.O(n)D.O(n㏒n)答案：B78.已知一个长度为n的单链表中所有节点是递增有序的，以下叙述中正确的是_________。A.插入一个节点使之有序的算法的时间复杂度为O(1)B.删除最大值节点使之有序的算法的时间复杂度为O(1)C.找最小值节点的算法的时间复杂度为O(1)D.以上都不对答案：C79.设10*10三对角矩阵保存SA[1．．28]中，其中A[1][1]保存在SA[1]中，A[5][5]保存在SA[k]中，这里k等于____________。A.10B.11C.12D.13答案：D80.元素A、B、C、D依次进栈后，栈顶元素是_________。A.AB.BC.CD.D答案：D81.在单链表中，增加一个头节点的目的是为了_________。A.使单链表至少有一个节点B.标识链表中重要节点的位置C.方便运算的实现D.说明单链表是线性表的链式存储结构答案：C82.在带头节点的单链表L为空的判定条件是_________。A.L==NULLB.L-＞NEXT==NULLC.L-＞NEXT==LD.L!=NULL答案：B83.设有一个10行10列的矩阵A，采用行序优先存储方式，存储全部数据需要400个字节的空间。如果A[0][0]为第一个元素，其存储地址为1000，则A[3][6]的地址为____________。A.1014B.1144C.1036D.1056答案：B84.下面关于线性表的叙述错误的是_________。A.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现答案：D85.线性表的顺序存储结构和链式存储结构相比，优点是_________。A.所有的操作算法实现简单B.便于随机存取C.便于插入和删除D.节省存储空间答案：B86.设森林F有3棵树，分别有9、8和7个结点，则F此排列次序转换成二叉树后根结点的右子树上结点的个数是。A.16B.15C.7D.17答案：B87.设某有向图中有n个顶点，则该有向图对应的邻接表中有____________个表头结点。A.n-1B.nC.n+1D.n+2答案：B88.线性表采用链表存储时，其存放各个元素的单元地址是_________。A.必须是连续的B.一定是不连续的C.部分地址必须是连续的D.连续与否均可以答案：D89.若一个栈用数组data[1..n]存储，初始栈顶指针top为n，则以下元素x进入栈的正确操作是_________。A.top++;data[top]=x;B.data[top]=x;top++;C.top--;data[top]=x;D.data[top]=x;top--;答案：D90.使用三元组来保存稀疏矩阵中的非零元素，三元组不包括非零元素的_____________。A.个数B.行号C.列号D.元素值答案：A91.对关键字序列（149,138,165,197,176,113,127），采用基数排序的第一趟之后所得结果为（）。A.(149，138，165，197，176，113，127)B.(113，165，176，197，127，138，149)C.(113，165，176，127，197，138，149)D.(113，127，138，149，165，176，197)答案：B92.对特殊矩阵采用压缩存储的目的主要是____________。A.表达变得简单B.对矩阵元素的存储变得简单C.去掉矩阵中的多余元素D.减少不必要的存储空间答案：D93.设某棵二叉树的中序遍历序列为ABCD，先序遍历序列为CABD，则后序遍历该二叉树得到序列为。A.BADCB.BCDAC.CDABD.CBDA答案：A94.设无向图G=(V,E)和G'=(V',E')，如果G'是G的生成树，则下列说法中错误的是______。A.G'是G的子图B.G'是G的一个无环子图C.G'是G的极小连通子图且V=V'D.G'是G的连通分量答案：D95.对关键字序列（21,19,37,5,2），经冒泡排序法由小到大排序，第一趟后所得结果为（）。A.(19，21，37，5，2)B.(19，21，5，2，37)C.(19，21，5，37，2)D.(19，21，2，5，37)答案：B96.使用迪杰斯特拉最短路径算法，求一个源点到其它各顶点的最短路径，该算法的时间复杂度为__________。A.O(n2)B.O(nlogn)C.D.答案：A97.对于下列排序，（）需要额外辅助存储空间达到O(n)。A.直接插入排序B.直接选择排序C.归并排序D.冒泡排序答案：C98.设一组权值集合W=(2，4，5，7)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为。A.36B.46C.35D.34答案：C99.将两个长度为n、m的递增有序表归并成一个有序顺序表，其最少的比较次数是_________。（MIN表示取最小值）A.nB.mC.MIN(m,n)D.不确定答案：C100.在下列排序算法中，（）排序算法可能出现如下情况：在最后一趟排序之前，所有元素均不在其最终的位置上。A.堆B.快速C.冒泡D.插入答案：D二、判断题1.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。答案：正确2.程序一定是算法。答案：错误3.在一个带头结点且头指针为head，长度大于2的双向循环双链表中，交换首尾元素结点需要修改6个指针域。答案：错误4.由二叉树的某种遍历方式产生的结果是一个线性序列。答案：正确5.层次遍历初始堆一定可以得到一个有序的序列。答案：错误6.栈顶元素和栈底有可能是同一元素。答案：正确7.对顺序栈进行进栈、出栈操作，不涉及元素的前、后移动问题。答案：正确8.在哈夫曼树中，权值较大的叶子结点一般离根结点较远。答案：错误9.栈和队列都是限制存取端的。答案：正确10.完全二叉树适合使用顺序存储结构答案：正确11.完全二叉树至多只有一个度为1的结点。答案：正确12.在某种遍历的线索二叉链表中，进行这种遍历时可以直接沿所有右指针一直搜索下去，从而访问所有结点。答案：错误13.树中元素结点是多对多的关系。答案：错误14.顺序栈中元素值的大小是有序的。答案：错误15.树的孩子兄弟表示法是一种二叉链表表示法。答案：正确16.一棵满二叉树中每棵子树都是完全二叉树。答案：正确17.若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。答案：正确18.长度为n，只设尾指针的循环链表作为队列的存储结构时出队操作的时间复杂度为O(n)。答案：错误19.n个元素依次进栈，它们的出栈顺序和进栈顺序一定正好相反。答案：错误20.树有先根遍历与中根遍历两种遍历方法。答案：错误21.对一棵树进行先根遍历与后根遍历，其中叶子结点出现的相对次序是相同的。答案：正确22.若用s[0..m-1]表示顺序栈的存储空间，则对栈的进栈、出栈操作最多只能进行m次；答案：错误23.空栈没有栈顶指针。答案：错误24.用二叉树的先序序列和后序序列可以导出它的中序序列。答案：错误25.基数排序比堆排序的空间复杂度高。答案：正确26.二叉树的先序遍历的递归算法的时间复杂度为线性级。答案：正确27.将一棵含有两个以上结点的树转换成二叉树后，该二叉树的根结点没有左子树。答案：错误28.健壮的算法不会因非法输入数据而出现莫名其妙的状态。答案：正确29.对于任意的二叉树，如果其叶子结点数为n0，度为2的结点数为n2，则n2＝n0＋1。答案：错误30.栈底元素是不能删除的元素。答案：错误三、多选题1.数据结构的三要素指的是（）。A.逻辑结构B.存储结构C.数据元素D.运算答案：ABD2.对于栈，若输出序列为BCAD，则可能的输入序列为（）。A.ACBDB.ABCDC.BCDAD.DBAC答案：ABCD3.一个正确的算法应该具有5个特性，除输入、输出特性外，另外3个特性是（）。A.确定性B.可行性C.有穷性D.稳定性答案：ABC4.关于顺序表与链表，说法正确的是（）。A.对一个表结构，根据其逻辑结构，如果可用顺序表存储，就不能用链表存储B.顺序表中结点依次存储，相邻结点存储在相邻存储单元中C.链表是表结构的一种存储结构D.链表