数据结构复习题

1、数据结构与算法一、选择题1. 组成数据的基本单位是( )。(A) 数据项 (B)数据类型 (C)数据元素 (D)数据变量2. 线性表的链接实现有利于( )运算。(A) 插入 (B)读表元 (C)查找 (D)定位3. 串的逻辑结构与( )的逻辑结构不同。(A) 线性表 (B)栈 (C)队列 (D)树4. 二叉树第i（i1）层最多有( )个结点。(A) 2i (B)2i (C) 2i-1 (D) 2i-15. 设单链表中指针p指向结点A，若要删除A后结点（若存在），则需要修改指针的操作为( )(A) p-next = p-next-next (B)p=p-next (C)p=p-next-next

2、 (D)p-next=p6. 设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为( )(A) 3,2,5,6,4,1 (B) 1,5,4,6,2,3(C) 2,4,3,5,1,6 (D) 4,5,3,6,2,17. 设字符串S1=ABCDEFG，S2=PQRST，则运算S=CONCAT(SUB(S1,2,LENGTH(S2)，SUB(S1,LENGTH(S2),2)的结果为( )(A) BCQR (B) BCDEF (C) BCDEFG (D) BCDEFEF8. 有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占

3、1个地址空间，则a85地址为( )(A)13 (B) 33 (C) 18 (D) 409. 如果结点A有3个兄弟，而且B为A的双亲，则B的度为( )(A) 3 (B) 4 (C) 5 (D) 110. 线索化二叉树中某结点D没有左孩子的必要条件是( )(A) D-Lchild=Null (B) D-ltag=1 (C) D-Rchild=Null (D) D-ltag=0 10. 数据结构是研究数据的( )以及它们之间的相互关系。(A) 理想结构、物理结构 (B) 理想结构、抽象结构(C) 物理结构、逻辑结构 (D) 抽象结构、逻辑结构11. 线性表采用链式存储时，其地址( )。(A) 必须是

4、连续的 (B) 部分地址必须是连续的(C) 一定是不连续的 (D) 连续与否均可以12. 设循环队列Q1.N-1的头尾指针为F，R，当插入元素时尾指针R加1，头指针F总是指向队列中第一个元素的前一个位置，则队列中元素计数为( )。(A) R-F (B) N-(R-F) (C) (R-F+N)%N (D) (F-R+N)%N13. 完成堆排序的全过程需要( )个记录大小的辅助空间。(A) 1 (B) n (C) nlog2n (D) n214. 若给定关键字集合为20,15,14,18,21,36,40,10，一趟快速排序结束时，键值的排列为( )(A) 10,15,14,18,20,36,40

5、,21 (B) 10,15,14,18,20,40,36,21 (C) 10,15,14,20,18,40,36,21 (D) 15,10,14,18,20,36,40,2115. 有一棵二叉树如图1所示，该树是( )。图1(A) 二叉平衡树 (B) 二叉排序树(C) 堆的形状 (D) 以上都不是16. 对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为( ),利用Kruskal的时间复杂度为( )。(A) O(log2n) (B) O(n2) (C) O(ne) (D) O(elog2e)17. 具有n个顶点的完全有向图的边数为( )。(A) n(n-1)/

6、2 (B) n(n-1) (C) n2 (D) n2-118. 设有100个元素，用二分法查找时，最大比较次数是( )，最小比较次数是( )。(A) 25 (B) 7 (C) 10 (D) 119. 在内部排序中，排序时不稳定的有( )。(A) 插入排序 (B) 冒泡排序 (C) 快速排序 (D) 归并排序20. 中序遍历一棵二叉排序树所得的结点访问序列是键值的( )序列。(A) 递增或递减 (B) 递减 (C) 递增 (D) 无序21. Substr(DATA STRUCTURE,5,9) = ( )。(A) STRUCTURE (B) DATA (C) ASTRUCTUR (D) DATA

7、 STRUCTURE22. 下列哪种形态不是树( )。 （A） （B） （C） （D）23. 下列哪种排序需要的附加存储开销最大( )。(A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 插入排序24. 对任何一棵树T，设n0,n1,n2,nm分别是0,1,2,m的结点，则n0=( )。(A) n1+n2+nm (B) 1+n2+2n3+（m-1）nm (C) n2+2n3+3n4+（m-1）nm (D) 2n1+3n2+（m+1）nm 图 125. 在图1中，V4的度为( )。(A) 1 (B) 2 (C) 3 (D) 426. n个顶点的无向图的邻接表中结点总数最多有( )个。(A

8、) 2n (B) n (C) n/2 (D) n(n-1)27. 设连通图G的顶点数为n，则G的生成树的边数为( )。(A) n (B) n-1 (C) 2n (D) 2n-128. 下列哪种排序需要的附加存储开销最小( )。(A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 计数排序29. 若按 ( )列出二叉搜索树中所存储的元素，则恰好是集合中所有元素从小到大的排序。(A) 先序 (B) 中序 (C) 后序 (D) 按层次30. 在图1所示的4棵树中，哪一棵是完全二叉树( )。 （A） （B） （C） （D）图131. 下面程序段的时间复杂度为( )。s=s0;for(i =1 ;

9、i=n-1;j-) s = s+1; (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2)32. 采用链结构存储线性表时，其地址( )。(A) 必须是连续的 （B）连续不连续都可以（C）部分地址必须是连续的 (D) 必须是不连续的33. 具有2000个结点的二叉树，其高度至少为( )。(A) 9 (B) 10 (C) 11 (D) 1234. 下列程序的时间复杂度为( )。for(i=0;im;i+) for(j =0;jt;j+) cij=0; for(i=0;im;i+)for(j=0;jt;j+)for(k=0;k0) (D) 串中所含字符的个数n(n

10、0)38. 若有一个栈的输入序列是1,2,3,n，输出序列的第一个元素是n，则第i个输出元素是( )(A) n-i (B) n-i-1 (C) n-i+1 (D) 不确定39. 设有一个栈，元素的进栈次序A，B，C，D，E，下列( )是不可能的出栈序列。(A) A,B,C,D,E （B）B,C,D,E,A(C) E,A,B,C,D （D）E,D,C,B,A40. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数有( )个。(A) 4 (B) 5 (C) 6 (D) 741. 在一个具有n个结点的无向完全图中，包含有( )条边。(A) n(

11、n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) n242. 采用顺序检索的方法检索长度为n的线性表，则检索每个元素的平均比较次数为( )。(A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/243. 已知一个有序表为（13,18,24,35,47,50,62,83,90,115,134），当二分检索值为90的元素时，需要( )次比较可检索成功。44. 已知8个元素（34,76,45,18,26,54,92,65），按照依次插入结点的方法生成一棵二叉排序树，该树的深度为( )。(A) 4 (B) 5 (C) 6 (D) 745、如某数据结构的数据元素的集

12、合为S=A,B,C,D,E,F,G,数据元素之间的关系为R=,则该数据结构是一种 。(A)线性结构(B)树结构(C)图结构(D)链表结构46、具有20个结点的二叉树，其深度最多为 。(A)4(B)5(C)6(D)2047、在具有N个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为 。(A)front=rear(B)（rear+1）%MAXSIZE=front(C)front-rear=1(D)rear%MAXSIZE=front48、一个55的对称矩阵采用压缩存储，需要存储 个元素。(A)5(B)10(C)15(D)2049、一个无向连通图有5个

13、顶点、8条边，则其生成树将要去掉 条边。(A)3(B)4(C)5(D)650、设一颗二叉树共有50个叶子结点（终端结点），则共有 个度为2的结点。(A)25(B)49(C)50(D)5151、设一棵二叉树共有20个度为2的结点，则叶子结点共有 个。(A)40(B)19(C)20(D)2152、一个元素进入队列的时间复杂度是 。(A)O(1)(B) O(n)(C) O(n2)(D) O(log2n)53、设一颗完全二叉树中根结点的编号为1，而且23号结点有左孩子但没有右孩子，则完全二叉树总共有 个结点。(A)24(B)45(C)46(D)4754、二叉树的第3层最少有 个结点。(A)0(B)1(

14、C)2(D)355、已知某算法的执行时间为（n+n2）+log2(n+2)，n代表问题规模，则该算法的时间复杂是 。(A)O(n)(B)O(n2)(C)O(log2n)(D)O(nlog2n)56、如果一棵树有10个叶子结点，则该树至少有 个结点。(A)10(B)11(C)19(D)2157、设有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主存储，a00的存储地址为100，每元素占1个地址空间，则a32的地址为 。(A)102(B)105(C)106(D)10858、总共3层的完全二叉树，其结点数至少有_个。(A)3(B)4(C)7(D)859、队列操作的原则是_。(A)先进先出 (B)

15、后进先出(C)只能进行插入(D)只能进行删除60、在有n个结点的二叉链表中，值为非空的链域的个数为_.(A)n-1(B)2n-1(C)n+1(D)2n+161、在具有n个结点且为完全二叉树的二叉排序树中查找一个关键值，其平均比较次数的数量级为_。（A）O(n) (B)O(log2n) (C)O(nlog2n) (D)O(n2)62、下列排序算法中，时间复杂度不受数据初始状态影响，恒为O（log2n）的是_。(A)堆排序(B)冒泡排序(C)简单选择排序(D)快速排序63快速排序的记录移动次数（ ）比较次数，其总执行时间为O(nlog2n)。 大于 大于等于 小于等于 小于64栈操作的原则是（）

16、先进先出后进先出栈顶插入栈顶删除65设矩阵A是一对称矩阵(aij=aji,1=i,j=8)，若每个矩阵元素占3个单元，将其上三角部分（包括对角线）按行序为主序存放在数组B中，B的首地址为1000，则矩阵元素a67的地址为（） 1031 1093 1096 103266、设数组Data0.m作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（ ）front=front+1 front=(front+1)% mrear=(rear+1)%m front=(front+1)%(m+1)67、深度为6（根的层次为1）的二叉树至多有（ ）结点。i. 64 32

17、31 6368、将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点X的双亲编号为（ ）24 25 23 无法确定69、堆是一个键值序列k1,k2, kn,对i=1,2,|_n/2_|,满足( )kik2ik2i+1 kik2i+1next=p-next; p-next=s; Bq-next=s; s-next=p;Cp-next=s-next; s-next=p; Dp-next=s; s-next=q;80、一棵深度为k的满二叉树有（ ）个结点。 A2k -1 B2k-1 C2k D2k81、在一个单链表HL中，若要向表头插入一个由指

18、针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;82、在一个单链表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;83、栈的插入与删除操作在 进行。 A、栈

19、顶 B、栈底 C、任意位置 D、指定位置84、在一个循环顺序队列中，队首指针指向队首元素的 位置。 A、前一个 B、后一个 C、当前 D、后面85、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为_。 A、 24 B、 48 C、 72 D、 5386、当利用大小为N的一维数组顺序存储一个栈时，假定用top=1表示栈空，则向这个栈插入一个元素时，首先应执行 语句修改top指针。 Atop+； Btop-； Ctop=NULL ； Dtop；87、线性表采用链式存储时，其地址 。 A必须是连续的 B部分地址必须是连续的 C一定是不连续的 D连续与否均可以88、设有一个

20、广义表为A(a)，其表尾为（ ）。A: a B: ( ) C: （） D: (a)89、与邻接矩阵相比，邻接表更适合于存储 ( )。A: 无向图 B: 连通图 C: 稀疏图 D: 稠密图 90、带头结点的单链表first为空的判定条件是：A. first = NULL; B. first-link = NULL;C. first-link = first; D. first != NULL;91、在一棵树中，（ ）没有前驱结点。 A. 分支结点 B. 叶结点 C. 树根结点 D. 空结点92、在有向图中每个顶点的度等于该顶点的（ ）。A. 入度 B. 出度C. 入度与出度之和D. 入度与出度之

21、差93、已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为（）A a c e f b d B a c b d f e C a c b d e f D a c d b f e 94、已知一组关键字为25，48，36，72，79，82，23，40，16，35，其中每相邻两个为有序子序列。对这些子序列进行一躺两两归并的结果是（）A 25，36，48，72，23，40，79，82，16，35B 25，36，48，72，16，23，40，79，82，35C 25，36，48，72，16，23，35，40，79，82D 16，23，25，35，36，40，48，72，79，82 第 1 页（

22、共 5 页）95、折半查找的时间复杂性为（ ）A. O（n2） B. O（n） C. O（nlog n） D. O（log n）96、按照二叉树的定义，具有3个结点的二叉树有( )种。A3 B4 C5 D6. 97、一个队列的入列序列是，则队列的输出序列是（）A、4,3,2,1B、1,2,3,4C、1,4,3,2D、3,2,1,498、按照二叉树的定义，具有3个结点的二叉树有（ ）种A、3 B、4 C、5 D、699.如图所示的有向无环图可以得到的不同拓扑序列的个数为（）A.1 B.2C.3 D.4100.下列排序方法中，稳定的排序方法为（） A.希尔排序 B.堆排序C.快速排序 D.直接插入

23、排序101、算法设计中，在生成当前结点的孩子结点时，通过一些限界条件即限界函数，帮助避免生成不包含答案结点子树的状态空间的检索方法是（ ）A、分枝界限法B、回溯法C、穷举法 D、递归102、算法设计中，将问题的候选解按某种顺序逐一枚举和检验，直到候选解满足所有要求的检索方法是（ ）A、分枝界限法B、回溯法C、穷举法D、递归法103、算法设计中，不重复，不遗漏地比较所有元素，直到找到需要元素为止，该方法称为( )A、分枝界限法B、回溯法C、穷举法D、递归法二、填空题1. 对于一个以顺序实现的循环队列Q0.m_1，队头、队尾指针分别为f,r,其判空的条件是 ，判满的条件是 。2. 循环链表的主要优

24、点是 。3. 一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为 。4. 具有64个结点的完全二叉树的深度为 。5. 设有一个空栈，现输入序列为1,2,3,4,5,经过Push,Push,Pop,Push,Pop,Push,Pop,Push后，输出序列为 。6. 一个具有n个顶点的有向完全图的弧数为 。7. 设一棵二叉树共用50个叶结点（终端结点），则共有 个度为2的结点 。8. 高度为h（h0）的二叉树，最少有 个结点，最多有 个结点。9、已知某算法的执行时间为（n+n2）/2+log2(2n+1)，n代表问题规模，则该算法的时间复杂度是 。10、数据结构有线性结构、树结构、 、

25、等几种逻辑结构。11、一个无向连通图有6个顶点7条边，则其生成树有 条边。12、在一个长度为n的顺序表中插入一个元素，最少需要移动 个元素，最多需要移动 个元素。13、如果指针p指向一棵二叉树的一个结点，则判断p没有左孩子的逻辑表达式为 。14、一个55的对称矩阵采用压缩存储，需要存储_个元素。15、设单链表中指针P指向结点A，若要删除A之后的结点（假设存在），则需要修改指针的操作为_。16、已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数_。17、图1中v3的入度和出度分别为_。18在带有头结点的单链表L中，若要删除第一个结点，则需执行下列三条语句：；L-next=U-nex

26、t；free(U)；19深度为8（根的层次号为1）的满二叉树有个叶子结点。20将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X，其双亲PARENT（X）的编号为。21设有一个链队，结点结构为data|next，front为队头指针，rear为队尾指针，当执行入队操作时需执行下列语句：malloc(p)；p-data=x; p-next=NULL；22、设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是_；r=s; r-next=null;。23、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有_ 个叶子的结点

27、。24、树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和_ .25在一个带头结点的单向循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head 。26在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为 。27. 若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为 。28. 假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为 。29. 串S=“I am a worker”的长度是 。30.在含100个结点的完

28、全二叉树中，叶子结点的个数为 。31.如果排序过程不改变 之间的相对次序，则称该排序方法是稳定的。32算法有五个特征它们是 、 、可行性、输入和输出。33栈是限定仅在 进行插入和删除的线性表。34具有64个结点的完全二叉树的深度为 。35数据结构讲述的三大关系是 、 、 。36已知二叉树中的叶子树为50，仅有一个孩子的结点数为30，则总结点数为 。37队列的原则是 。38已知某算法的执行时间为n+n2,n代表问题规模，则该算法的时间复杂度是 。39数据结构有线性结构、树结构、 、 等几种逻辑结构。40栈的原则是 。41顺序存储的队列如果不采用循环方式，则会出现 问题。42设一颗完全二叉树共有5

29、0个叶子结点，则它共有_个度为2的结点。43对于一个顺序栈作进栈运算时，应先判断栈是否为 ，判断的条件是 ，作出栈运算时，应先判断栈是否为 ，判断的条件是 。44在一棵二叉树上第5层的结点数最多为 。45.将指向单链表中的某个结点的指针p移动到该结点的后继结点表示为 。46. 总共三层的完全二叉树，其结点数至少有 个，至多有 个。47. 二叉树的遍历方法有 、 、 。48、链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的_域的值。49、一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k (x, y) ) )，结点f的层数为_。假定根结点的层数

30、为0。50、n (n0) 个顶点的无向图最多有_条边，最少有_条边。51、在队列中，允许进行插入操作的一端称为，允许进行删除操作的一端称为。52、设”good”,S2=”book”,则，和依次联接后的结果是。53、若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么当2in,则结点i无 ；若2i+1n，则结点i无 。54、在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为 。55在单链表中设置头结点的作用是_。56设广义表L=（a），则该广义表的长度是 ，深度是 。57若一个二叉树含有n个结点，则它的二叉链表中必有 个空的链域。

31、58、在双链表中，存储一个结点有三个域，一个是数据域；另两个是指针域，分别指向 _和_。 59、在循环列队中，设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么，队空标志为_，队满标志为_。60、设广义表C=( (x,(a,b) ),y ) ), 则C的长度为_,深度为_61、在一棵具有n个结点的完全二叉树中，从树跟起，自上而下、自左而右地给所有结点编号。设跟结点编号为1。若编号为i的结点，有右孩子，那么其右孩子的编号为_；若编号为i的结点，有父结点，那么其父结点的编号为_。62、有一稠密图G，则G采用_存储较省空间。设有一稀疏图G，则采用_存储较省空间。63、数据结构的存储结构包括顺序、_、索引和散列等四种。64、在链表中进行插入和 操作的效率比在顺序存储结构中进行相同操作的效率高。65、对于队列，只能在插入元素，在删除元素。66、当线性表很少做插入删除操作时，应采用存储结构为好。67在二叉树第h层上最多有个结点。68关键路径的长度是完成整个工程所需要的最_时间。69、下面树的先序、中序、后续遍历的结果依次为_、_、_abcfdeea70、cf 将左边的森林转换为二叉树为b_ 71、线性结构中元素之间