数据结构考试习题.doc

第章 绪论1简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。3简述逻辑结构的四种基本关系并画出它们的关系图。4存储结构由哪两种基本的存储方法实现？5选择题（1）在数据结构中，从逻辑上可以把数据结构分成（ ）。A动态结构和静态结构 B紧凑结构和非紧凑结构C线性结构和非线性结构 D内部结构和外部结构（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）A存储结构 B存储实现 C逻辑结构 D运算实现（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）。A数据具有同一特点B不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C每个数据元素都一样D数据元素所包含的数据项的个数要相等（4）以下说法正确的是（ ）。A数据元素是数据的最小单位B数据项是数据的基本单位C数据结构是带有结构的各数据项的集合D一些表面上很不相同的数据可以有相同的逻辑结构（5）以下与数据的存储结构无关的术语是（ ）。A顺序队列 B. 链表 C. 有序表 D. 链栈（6）以下数据结构中，（ ）是非线性数据结构A树 B字符串 C队 D栈6试分析下面各程序段的时间复杂度。（1）x=90; y=100; while(y0) if(x100) x=x-10;y-; else x+;（2）for (i=0; in; i+) for (j=0; jm; j+) aij=0;（3）s=0; for i=0; in; i+) for(j=0; jn; j+) s+=Bij; sum=s;（4）i=1; while(i=n) i=i*3;（5）x=0; for(i=1; in; i+) for (j=1; j1 y=0; while(x(y+1)* (y+1) y+;第2章 线性表1选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。A110 B108 C100 D120（2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（ ）。A访问第i个结点（1in）和求第i个结点的直接前驱（2in） B在第i个结点后插入一个新结点（1in）C删除第i个结点（1in）D将n个结点从小到大排序（3） 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 的元素个数为（ ）。A8 B63.5 C63 D7（4）链接存储的存储结构所占存储空间（ ）。A分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B只有一部分，存放结点值C只有一部分，存储表示结点间关系的指针D分两部分，一部分存放结点值，另一部分存放结点所占单元数（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。A必须是连续的 B部分地址必须是连续的C一定是不连续的 D连续或不连续都可以（6）线性表在（ ）情况下适用于使用链式结构实现。A需经常修改中的结点值 需不断对进行删除插入 C中含有大量的结点 中结点结构复杂（7）单链表的存储密度（ ）。A大于1 B等于1 C小于1 D不能确定（8）将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。An B2n-1 C2n Dn-1（9）在一个长度为n的顺序表中，在第i个元素（1in+1）之前插入一个新元素时须向后移动（ ）个元素。An-i Bn-i+1 Cn-i-1 Di(10) 线性表L=(a1，a2,an)，下列说法正确的是（ ）。A每个元素都有一个直接前驱和一个直接后继B线性表中至少有一个元素C表中诸元素的排列必须是由小到大或由大到小D除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。(11) 若指定有n个元素的向量，则建立一个有序单链表的时间复杂性的量级是（ ）。AO(1) BO(n) CO(n2) DO(nlog2n)(12) 以下说法错误的是（ ）。A求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B顺序存储的线性表可以随机存取C由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活D线性表的链式存储结构优于顺序存储结构(13) 在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（ ）。As-next=p+1; p-next=s;B(*p).next=s; (*s).next=(*p).next;Cs-next=p-next; p-next=s-next;Ds-next=p-next; p-next=s; (14) 在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。Ap-next-prior=p-prior; p-prior-next=p-next;Bp-next=p-next-next; p-next-prior=p;Cp-prior-next=p; p-prior=p-prior-prior;Dp-prior=p-next-next; p-next=p-prior-prior;(15) 在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（ ）。Ap-next=q; q-prior=p; p-next-prior=q; q-next=q;Bp-next=q; p-next-prior=q; q-prior=p; q-next=p-next;Cq-prior=p; q-next=p-next; p-next-prior=q; p-next=q;Dq-prior=p; q-next=p-next; p-next=q; p-next-prior=q;2算法设计题（1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。（4）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。（5）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。（7）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。 第3章 栈和队列1选择题（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（ ）种情况。A5，4，3，2，1 B2，1，5，4，3 C4，3，1，2，5 D2，3，5，4，1（2）若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为（ ）。 Ai Bn-i Cn-i+1 D不确定（3）数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素个数的公式为（ ）。Ar-f B(n+f-r)%n Cn+r-f D（n+r-f)%n（4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（ ）。Ax=top-data;top=top-link； Btop=top-link;x=top-link； Cx=top;top=top-link； Dx=top-link；（5）设有一个递归算法如下 int fact(int n) /n大于等于0 if(n=0) return 1; else return n*fact(n-1); 则计算fact(n)需要调用该函数的次数为（ ）。An+1 Bn-1 C n D n+2（6）栈在（ ）中有所应用。A递归调用 B函数调用 C表达式求值 D前三个选项都有（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。A队列 B栈 C 线性表 D有序表（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。A2 B3 C4 D 6（9）在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top作为栈顶指针，则当作进栈处理时，top的变化为（）。 Atop不变 Btop=0 Ctop- Dtop+（10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A线性表的顺序存储结构 B队列 C. 线性表的链式存储结构 D. 栈（11）用链接方式存储的队列，在进行删除运算时（）。A. 仅修改头指针 B. 仅修改尾指针C. 头、尾指针都要修改 D. 头、尾指针可能都要修改（12）循环队列存储在数组A0.m中，则入队时的操作为（）。A. rear=rear+1 B. rear=(rear+1)%(m-1) C. rear=(rear+1)%m D. rear=(rear+1)%(m+1) （13）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。 A. (rear+1)%n=front B. rear=front Crear+1=front D. (rear-l)%n=front（14）栈和队列的共同点是（）。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点（15）一个递归算法必须包括（）。A. 递归部分 B. 终止条件和递归部分C. 迭代部分 D. 终止条件和迭代部分2.算法设计（1）回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)（2）设从键盘输入一整数的序列：a1, a2, a3，an，试编写算法实现：用栈结构存储输入的整数，当ai-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。（3）假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO通过对的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。（4）已知Ackermann函数定义如下: 写出计算Ack(m,n)的递归算法，并根据此算法给出出Ack(2,1)的计算过程。（5）已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的算法： 求链表中的最大整数； 求链表的结点个数； 求所有整数的平均值。第4章 串1选择题（1）串是一种特殊的线性表，其特殊性体现在（ ）。 A可以顺序存储 B数据元素是一个字符 C可以链式存储 D数据元素可以是多个字符若 （2）串下面关于串的的叙述中，（ ）是不正确的？ A串是字符的有限序列 B空串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储（3）串“ababaaababaa”的next数组为（ ）。A012345678999 B012121111212 C011234223456 D0123012322345（4）串“ababaabab”的nextval为（ ）。A010104101 B010102101 C010100011 D010101011 （5）串的长度是指（ ）。A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数2简答题（1）已知模式串t=abcaabbabcab写出用KMP法求得的每个字符对应的next函数值。第5章 数组与广义表一、选择题（1）假设以行序为主序存储二维数组A=array1.100,1.100，设每个数据元素占2个存储单元，基地址为10，则LOC5,5=（ ）。A808 B818 C1010 D1020（2）设有数组Ai,j，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5,8的存储首地址为（ ）。ABA+141 BBA+180 CBA+222 DBA+225（3）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。A13 B33 C18 D40（4）若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B1.(n(n+1)/2中，则在B中确定aij（ij）的位置k的关系为（ ）。Ai*(i-1)/2+j Bj*(j-1)/2+i Ci*(i+1)/2+j Dj*(j+1)/2+i（5）AN，N是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组TN(N+1)/2中，则对任一上三角元素aij对应Tk的下标k是（ ）。Ai(i-1)/2+j Bj(j-1)/2+i Ci(j-i)/2+1 Dj(i-1)/2+1（6）设二维数组A1. m，1. n（即m行n列）按行存储在数组B1. m*n中，则二维数组元素Ai,j在一维数组B中的下标为（ ）。A(i-1)*n+j B(i-1)*n+j-1 Ci*(j-1) Dj*m+i-1（7）数组A0.4,-1.-3,5.7中含有元素的个数（ ）。A55 B45 C36 D16（8）广义表A=(a,b,(c,d),(e,(f,g)，则Head(Tail(Head(Tail(Tail(A)的值为（ ）。A(g) B(d) Cc Dd（9）广义表(a,b,c,d)的表头是（ ），表尾是（ ）。Aa B( ) C(a,b,c,d) D(b,c,d)（10）设广义表L=(a,b,c)，则L的长度和深度分别为（ ）。A1和1 B1和3 C1和2 D2和3 二、问答题（1）数组A中，每个元素Ai,j的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。求： 存放该数组所需多少单元？ 存放数组第4列所有元素至少需多少单元？ 数组按行存放时，元素A7,4的起始地址是多少？ 数组按列存放时，元素A4,7的起始地址是多少？(2)请将香蕉banana用工具 H( )Head( )，T( )Tail( )从L中取出。L=(apple,(orange,(strawberry,(banana),peach),pear)第6章 树和二叉树1选择题（1）把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。 A唯一的 有多种C有多种，但根结点都没有左孩子 有多种，但根结点都没有右孩子（2）由3 个结点可以构造出多少种不同的二叉树？（ ）A2 B3 C4 D5 （3）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。A250 B 500 C254 D501 （4）一个具有1025个结点的二叉树的高h为（ ）。A11 B10 C11至1025之间 D10至1024之间（5）深度为h的满m叉树的第k层有（ ）个结点。(1=k=h) Amk-1 Bmk-1 Cmh-1 Dmh-1（6）利用二叉链表存储树，则根结点的右指针是（ ）。A指向最左孩子 B指向最右孩子 C空 D非空（7）对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）遍历实现编号。A先序 B. 中序 C. 后序 D. 从根开始按层次遍历（8）若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适。A前序 B中序 C后序 D按层次（9）在下列存储形式中，（ ）不是树的存储形式？A双亲表示法 B孩子链表表示法 C孩子兄弟表示法 D顺序存储表示法（10）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）。A所有的结点均无左孩子 B所有的结点均无右孩子C只有一个叶子结点 D是任意一棵二叉树（11）某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。A空或只有一个结点 B任一结点无左子树 C高度等于其结点数 D任一结点无右子树（12）若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（ ）。AX的双亲 BX的右子树中最左的结点 CX的左子树中最右结点 DX的左子树中最右叶结点（13）引入二叉线索树的目的是（ ）。A加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲 D使二叉树的遍历结果唯一（14）线索二叉树是一种（ ）结构。A逻辑 B 逻辑和存储 C物理 D线性（15）设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。A n-1 Bn C n+1 D n+22应用题（1）试找出满足下列条件的二叉树 先序序列与后序序列相同 中序序列与后序序列相同 先序序列与中序序列相同 中序序列与层次遍历序列相同（2）设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C画出这棵二叉树。画出这棵二叉树的后序线索树。将这棵二叉树转换成对应的树（或森林）。（3） 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 试为这8个字母设计赫夫曼编码。 试设计另一种由二进制表示的等长编码方案。 对于上述实例，比较两种方案的优缺点。第7章图1选择题（1）在一个图中，所有顶点的度数之和等于图的边数的（ ）倍。 A1/2 B1 C2 D4 （2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A1/2 B1 C2 D4 （3）具有n个顶点的有向图最多有（ ）条边。 An Bn(n-1) Cn(n+1) Dn2 （4）n个顶点的连通图用邻接距阵表示时，该距阵至少有（ ）个非零元素。An B2(n-1) Cn/2 Dn2 （5）G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。A7 B8 C9 D10 （6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ ）图。A非连通 B连通 C强连通 D有向（7）下面（）算法适合构造一个稠密图G的最小生成树。A Prim算法 BKruskal算法 CFloyd算法 DDijkstra算法（8）用邻接表表示图进行广度优先遍历时，通常借助（ ）来实现算法。A栈 B. 队列 C. 树 D图 （9）用邻接表表示图进行深度优先遍历时，通常借助（ ）来实现算法。A栈 B. 队列 C. 树 D图 （10）深度优先遍历类似于二叉树的（ ）。A先序遍历 B中序遍历 C后序遍历 D层次遍历（11）广度优先遍历类似于二叉树的（ ）。A先序遍历 B中序遍历 C后序遍历 D层次遍历（12）图的BFS生成树的树高比DFS生成树的树高（ ）。A小 B相等 C小或相等 D大或相等A0 2 4 3 1 5 6B0 1 3 6 5 4 2C0 1 3 4 2 5 6D0 3 6 1 5 4 2（13）已知图的邻接矩阵如图7.1所示，则从顶点0出发按深度优先遍历的结果是（ ）。图7.1 邻接矩阵（14）已知图的邻接表如图7.2所示，则从顶点0出发按广度优先遍历的结果是（ ），按深度优先遍历的结果是（ ）。A0 1 3 2 B0 2 3 1 C0 3 2 1 D0 1 2 3图7.2 邻接表（15）下面（ ）方法可以判断出一个有向图是否有环。A深度优先遍历 B拓扑排序 C求最短路径 D求关键路径2应用题（1）已知如图7.3所示的有向图，请给出： 每个顶点的入度和出度； 邻接矩阵； 邻接表； 逆邻接表。 图7.3 有向图 （2）已知如图7.4所示的无向网，请给出： 邻接矩阵； 邻接表； 最小生成树图7.4 无向网 （3）已知图的邻接矩阵如7.5所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。图7.5 邻接矩阵（4）有向网如图7.6所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表7.1。 图7.6 有向网终点i=1i=2i=3i=4i=5i=6bcdefgvjS终点集 （5）试对图7.7所示的AOE-网： 求这个工程最早可能在什么时间结束； 求每个活动的最早开始时间和最迟开始时间；图7.7 AOE-网 确定哪些活动是关键活动第9章 查找1选择题（1）对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）。A(n-1)/2 B n/2 C(n+1)/2 Dn （2）适用于折半查找的表的存储方式及元素排列要求为（ ）。 A链接方式存储，元素无序 B链接方式存储，元素有序C顺序方式存储，元素无序 D顺序方式存储，元素有序（3）当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ ）。 A必定快 B不一定 C在大部分情况下要快 D取决于表递增还是递减（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（ ）比较大小，查找结果是失败。A20，70，30，50 B30，88，70，50 C20，50 D30，88，50（5）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（ ）次关键字。A3 B4 C5 D6（6）折半搜索与二叉排序树的时间性能（ ）。 A相同 B完全不同 C有时不相同 D数量级都是O(log2n)（7）分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（ ）。 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)（8）在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应作（ ）型调整以使其平衡。ALL BLR CRL DRR（9）下列关于m阶B-树的说法错误的是（ ）。 A根结点至多有m棵子树 B所有叶子都在同一层次上C非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树 D根结点中的数据是有序的（10）下面关于B-和B+树的叙述中，不正确的是（ ）。 AB-树和B+树都是平衡的多叉树 BB-树和B+树都可用于文件的索引结构CB-树和B+树都能有效地支持顺序检索 DB-树和B+树都能有效地支持随机检索（11）m阶B-树是一棵（ ）。Am叉排序树 Bm叉平衡排序树 Cm-1叉平衡排序树 Dm+1叉平衡排序树（12）下面关于哈希查找的说法，正确的是（ ）。 A哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B除留余数法是所有哈希函数中最好的 C不存在特别好与坏的哈希函数，要视情况而定D哈希表的平均查找长度有时也和记录总数有关（13）下面关于哈希查找的说法，不正确的是（ ）。 A采用链地址法处理冲突时，查找一个元素的时间是相同的 B采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的 C用链地址法处理冲突，不会引起二次聚集现象 D用链地址法处理冲突，适合表长不确定的情况（14）设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（ ）。 A8 B3 C5 D9 （15）采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字 ( )。A不一定都是同义词 B一定都是同义词 C一定都不是同义词 D都相同2应用题（1）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题： 画出描述折半查找过程的判定树； 若查找元素54，需依次与哪些元素比较？ 若查找元素90，需依次与哪些元素比较？ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。（2）在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。（3）已知如下所示长度为12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec） 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。 按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 （4）对下面的3阶B-树，依次执行下列操作，画出各步操作的结果。 插入90 插入25 插入45 删除60 （5）设哈希表的