数据结构考试

第一章3、下面程序的时间复杂度为。for(i=0;im;i++)for(j=0;jn;j++)A[i][j]=i*j;A.O(m2)B.O(n2)C.O(m×n)D.O(m+n)4、下面算法的时间复杂度为。intf(intn){if(n==0||n==1)return1;elsereturnn*f(n-1);}A.O(1)B.O(n)C.O(n2)D.O(logn)第二章4、等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为。A.nB.(n-1)/2C.n/2D.(n+1)/25、在一个长度为n的顺序存储的线性表中查找值为x的元素时，平均查找长度(及x同元素的平均比较次数，假定查找每个元素的概率都相等)为。A.nB.n/2C.(n+1)/2D.(n-1)/29、下面关于线性表的描述中，错误的是。A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作C.线性表采用链式存储，不必占用一片连续的存储单元D.线性表采用链式存储，便于插入和删除操作11、在一个带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行的语句是。A.HL=p;p-next=HL;B.p-next=HL;HL=p;C.p-next=HL;p=HL;D.p-next=HL-next;HL-next=p;12、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行的语句是。A.p=q-next;p-next=q-next;B.p=q-next;q-next=p;C.p=q-next;q-next=p-next;D.q-next=q-next-next;q-next=q;14、4个元素按A,B,C,D顺序进入S栈，执行两次Pop(S,x)运算后，栈顶元素的值是。A.AB.BC.CD.D15、从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列命令。A.x=top;top=top-next;B.top=top-next;x=top-data;C.x=top-data;D.x=top-data;top=top-next;17、设有一个顺序栈，元素A,B,C,D,E,F依次进栈，如果6个元素出栈的顺序是B,D,C,F,E,A，则栈的容量至少为。A.3B.4C.56.620、设栈S和队列Q的初始状态为空,元素e1，e2，e3，e4，e5和e6依次通过栈，一个元素出栈后即进入队列Q,若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是。A.6B.4C.3D.221、队列通常采用的两种存储结构是()。A.顺序存储结构和链式存储结构B.散列方式和索引方式C.链表存储结构和线性存储结构D.线性存储结构和非线性存储结构24、链栈与顺序栈相比，有一个较为明显的优点是。A.通常不会出现满栈的情况B.通常不会出现栈空的情况C.插入操作更加方便D.删除操作更加方便25、设用一个大小为M=60的顺序表A[M]表示一个循环队列，如果当前的尾指针rear=32，头指针front=15，则当前循环队列的元素的个数为。A.42B.16C.17D.4132、某队列允许在两端进行入队操作，但仅允许在一端进行出队操作（称为输出受限的双端队列），若a,b,c,d,e元素依次进队，则不可能得到的顺序是。A.bacdeB.dbaceC.dbcaeD.ecbad33、在双向链表中间插入一个结点时，需要修改修改个指针域。A.1B.2C.3D.435、在稀疏矩阵的三元组表示法中，每个三元组表示。A.矩阵中非零元素的值B.矩阵中数据元素的行号和列号C.矩阵中数据元素的行号、列号和值D.矩阵中非零数据元素的行号、列号和值36、对特殊矩阵采用压缩存储的目的主要是为了。A.表达变得简单B.对矩阵元素的存取变得简单C.去掉矩阵中的多余元素C.减少不必要的存储空间7、链式存储的特点是利用来表示数据元素之间的逻辑关系。8、静态链表(线性表的游标实现)是指用表示单链表的指针。13、对于循环向量的循环队列，求队列长度的公式为。19、字符串“ababaab“的Next数组值是。22、广义表(a,(a,b),d,e,((i,j),k))的长度是，深度是。23、设广义表A(((),(a,(b),c)))，则Cal(Cdr(Cal(Cdr(Cal(A))))=四、已知一个单向链表，试给出复制该链表的算法。要求：1、定义线性表的节点的结构以及节点的型和位置的型。2、定义线性表的基本操作3、在1，2的基础上，完成本题。4、在main函数中进行测试：先构建一个线性表，并定义一个空线性表，然后进行复制。五、写出从一个带表头的单链表中删除其值等于给定值x的结点的算法函数：intdelete(LIST&L,intx);如果x在该链表中，则删除对应结点，并返回其在链表中的位置（逻辑位置，第一个结点的逻辑位置为1），否则返回-1。要求：1、定义线性表的节点的结构以及节点的型和位置的型。2、定义线性表的基本操作3、在1，2的基础上，完成本题。4、在main函数中进行测试：先构建一个线性表，然后调用函数删除值等于给定值的节点。第三章3、具有n个结点的满二叉树有个叶结点。A.n/2B.(n-1)/2C.(n+1)/2D.n/2+16、具有10个叶结点的二叉树中有个度为2的结点。A.8B.9C.10D.118、在线索二叉树中，t所指结点没有左子树的充要条件是。A.t-left=NULLB.t-ltag=TRUEC.t-ltag=TRUE且t-left=NULLD.以上都不对9、n个结点的线索二叉树上含有的线索数为。A.2nB.n-1C.n+1D.n18、设F是一个森林，B是由F变换得到的二叉树。若F中有n个非终端结点，则B中没有右孩子的结点有个。A.n-1B.nC.n+1D.n+219、将一棵树T转换为二叉树B，则T的后根序列是B的。A.先根序列B.中根序列C.后根序列D.层次序列3、含有4个度为2的结点和5个叶子结点的完全二叉树，有个度为1的结点。4、具有100个结点的完全二叉树的叶子结点数为。9、在定义堆时，通常采用方式定义相应的二叉树，这样可以很容易实现其相关操作。17、设有数据WG={7,19,2,6,32,3,21,10}叶节点权重集合，则所构建哈夫曼树的高是，带权路径长度WPL为。18、设有一份电文中共使用6个字符a,b,c,d,e,f，其中出现频率依次为2，3，4，7，8，19，则字符c的哈夫曼编码是，电文编码的总长度为。五、已知非空二叉树T，写一个算法，求度为2的结点的个数。要求：1、定义二叉树的抽象数据类型和型BTREE，并定义基本操作。2、编写函数count2(BTREET)，返回度为2的节点的个数。3、在主函数中，构建一个二叉树，并验证所编写的算法。六、用递归方法写一个算法，求二叉树的叶子结点数intleafnum(BTREET)。要求：1、定义二叉树的抽象数据类型和型BTREE，并定义基本操作。2、编写函数leafnum(BTREET)，返回树T的叶子节点的个数。在主函数中，构建一个二叉树，并验证所编写的算法。十六、画出表达式(A+B*C/D)*E+F*G所对应的树结构，并写出该表达式的波兰表示式和逆波兰表示式。第四章4、有n个顶点的图的邻接矩阵使用数组存储的。A.一维B.n行n列C.任意行n列D.n行任意列5、对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头数组大小至少为（假设下标为0的数组参与使用）。A.n-1B.n+1C.nD.n+e10、在如下图所示的图中，从顶点a出发，按深度优先遍历，则可能得到的一种顶点的序列为。A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b11、在如上图所示的图中，从顶点a出发，按广度优先遍历，则可能得到的一种顶点的序列为。A.a,b,e,c,d,fB.a,b,e,c,f,dC.a,e,b,c,f,dD.a,e,d,f,c,b15、下面关于工程计划的AOE网的叙述中，不正确的是。A.关键活动不按期完成就会影响整个工程的完成时间。B.任何一个关键活动提前完成，那么整个工程将会提前完成。C.所有关键活动都提前完成，那么整个工程将会提前完成。D.某些关键工程若提前完成，那么整个工程将会提前完成。16、在AOE网中，始点和汇点的个数为。A.1个始点，若干个汇点B.若干个始点，若干个汇点C.若干个始点，1个汇点C.1个始点，1个汇点19、在下图所示的AOE网中，活动a9的最早开始时间为。A.13B.14C.15D.1620、在上图所示的AOE网中，活动a4的最迟开始时间为A.4B.5C.6D.721、设图有n个顶点和e条边，当用邻接矩阵表示该图时，则求解最短路径的Floyd算法的时间复杂度为。A.O(n)B.O(n+e)C.O(n2)D.O(n3)2、图的存储结构主要有两种，分别是和。4、已知一个图的邻接矩阵表示，计算第j个顶点的入度的方法是，计算第j个顶点的出度的方法是。9、创建一个邻接矩阵图的复杂度是；创建一个链接表图的复杂度是。14、连通而且无环路的无向图称为。19、求每一对顶点之间的最短路径，可以用两种方法，一种是分别对每个顶点采用算法，另一种方法是。九、下图是一个无向带权图，请给出该图的邻接矩阵，并分别按Prim算法和Kruskal算法求最小生成树（画图）。十二、如下图所示的有向网络，利用Dijkstra算法求从顶点v1到其他各顶点的最短路径(要求写出如教材P155表4-2所示的Dijkstra算法的执行过程)，并编程验证。第五章2、分别以下列序列构造二叉排序数（二叉查找树），与用其他3个序列所构造的结果不同的是：A.(100,80,90,60,120,110,130)B.(100,120,110,130,80,60,90)C.(100,60,80,90,120,110,130)D.(100,80,60,90,120,130,110)3、不可能生成下图所示的二叉排序树的关键字的序列是。A.45312B.42531C.45213D.42315425135、一棵高度为k的二叉平衡树，其每个非叶结点的平衡因子均为0，则该树共有个结点。A.2k-1-1B.2k-1+1C.2k-1D.2k+16、具有5层结点的平衡二叉树至少有个结点。A.12B.11C.10D.911、有一组关键字{8,24,16,3,12,32,51}，采用除留余数法构造散列函数：H(key)=keymod12，则将发生次冲突。A.3B.4C.5D.63、对于一棵二叉排序树，按方法遍历得出的结点序列是从小到大排列的。4、对二叉排序树进行查找的方法是用待查找的值与根结点的键值进行比较，若比根结点的值小，则继续在子树中查找。5、AVL树为在构造二叉排序树时，为确保搜索的性能而保持树的平衡，保持平衡的方法为在构建AVL树时根据特定条件而进行LL,RR,LR,RL四种旋转操作，如对于下图的树，应该进行旋转。251932274026新插入结点251932274045新插入结点9、在散列排序法中，处理冲突的折叠法有可分为和两种类型。10、散列法的填充因子=/。六、试画出从空树开始，有字符序列(t,d,e,s,u,g,b,j,a,k,r,i)构成的二叉平衡树，并为每一次平衡处理指明旋转类型。八、设有三阶B-树（如下图所示），1、画出依次插入18、33、97后的B-树2、分别画出删除66、16、43后的B-树4326556016354148576688