数据结构与算法复习题222.doc

数据结构与算法一、选择题1. 组成数据的基本单位是( C )。(A) 数据项 (B)数据类型 (C)数据元素 (D)数据变量2. 线性表的链接实现有利于( A )运算。(A) 插入 (B)读表元 (C)查找 (D)定位3. 串的逻辑结构与( D )的逻辑结构不同。(A) 线性表 (B)栈 (C)队列 (D)树4. 二叉树第i（i1）层最多有( C )个结点。(A) 2i (B)2i (C) 2i-1 (D) 2i-15. 设单链表中指针p指向结点A，若要删除A后结点（若存在），则需要修改指针的操作为( D )(A) p-next = p-next-next (B)p=p-next (C)p=p-next-next (D)p-next=p6、栈和队列的共同特点是( D )。(A)只允许在端点处插入和删除元素 (B)都是先进后出 (C)都是先进先出 (D)没有共同点7、二叉树的第k层的结点数最多为( D). (A)2k+1 (B)2K+1 (C)2K-1 (D) 2k-18、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ A ）。(A) BADC (B) BCDA (C) CDAB (D) CBDA9、对线性表，在下列哪种情况下应当采用链表表示？( A ) (A)经常需要随机地存取元素 (B)经常需要进行插入和删除操作 (C)表中元素需要占据一片连续的存储空间 (D)表中元素的个数不变10、下面程序的时间复杂为（ D）for（i=1,s=0; i=n; i+） t=1;for(j=1;j=i;j+) t=t*j;s=s+t;(A) O(n) (B) O(n2) (C) O(nlog2n)(D) O(n3)11、设某强连通图中有n个顶点，则该强连通图中至少有（ A）条边。(A) n(n-1) (B) n+1 (C) n (D) n(n+1)12、下面关于算法说法错误的是（ D ） A算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的13、i层（i1）二叉树最多有( C )个结点。(A) 2i (B)2i (C) 2i-1 (D) 2i-114、对稀疏矩阵进行压缩存储目的是( C )。A便于进行矩阵运算 B便于输入和输出 C节省存储空间 D降低运算的时间复杂度 15、数据结构是研究数据的( C )以及它们之间的相互关系。(A) 理想结构、物理结构 (B) 理想结构、抽象结构(C) 物理结构、逻辑结构 (D) 抽象结构、逻辑结构16、设数据结构A=(D，R)，其中D=1，2，3，4，R=r，r=，则数据结构A是（ C ）。(A) 线性结构(B) 树型结构 (C) 图型结构(D) 集合17、线性表采用链式存储时，其地址( D )。(A) 必须是连续的 (B) 部分地址必须是连续的(C) 一定是不连续的 (D) 连续与否均可以18、设循环队列Q1.N-1的头尾指针为F，R，当插入元素时尾指针R加1，头指针F总是指向队列中第一个元素的前一个位置，则队列中元素计数为( C )。(A) R-F (B) N-(R-F) (C) (R-F+N)%N (D) (F-R+N)%N19、链表不具有的特点是( C )。(A)插入、删除不需要移动元素 (B)可随机访问任一元素 (C)不必事先估计存储空间 (D)所需空间与线性长度成正比20、设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为( C )(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,121、一个55的对称矩阵采用压缩存储，需要存储（ C ）个元素。(A)5 (B)10 (C)15 (D)2022、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B ）A9 B11 C15 D不确定23、从一个长度为n的顺序表中删除第i个元素（1in），需向前移动( A )个元素。(A) n-i (B) n-i+1 (C) n-i-1 (D) i24、函数substr(“DATASTRUCTURE”，5，9)的返回值为（ A ）。(A) “STRUCTURE” (B) “DATA”(C) “ASTRUCTUR” (D) “DATASTRUCTURE”25、设连通图G中的边集E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（ A ）。(A) abedfc (B) acfebd (C) aebdfc (D) aedfcb26、3个结点可构成（ D ）个不同形态的二叉树。(A)2 (B)3 (C)4 (D)527、下列哪一种图的邻接矩阵是对称矩阵？（ B ）(A)有向图 (B)无向图 (C)AOV网 (D)AOE网28、（ B ）二叉排序树可以得到一个从小到大的有序序列。(A) 先序遍历(B) 中序遍历(C) 后序遍历(D) 层次遍历29、设有6个结点的无向图，该图至少应有( B )条边才能确保是一个连通图。 A.5 B.6 C.7 D.830、对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为( B ),利用Kruskal的时间复杂度为( D )。(A) O(log2n) (B) O(n2) (C) O(ne) (D) O(elog2e)31、一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( D ) A. 2 3 1B. 3 2 1 C. 3 1 2 D. 1 2 332、树最适合用来表示( C )。(A)有序数据元素 (B)无序数据元素 (C)元素之间具有分支层次关系的数据 (D)元素之间无联系的数据33、具有2000个结点的二叉树，其高度至少为( C )。(A) 9 (B) 10 (C) 11 (D) 1234、设有1000个元素，用二分法查找时，最小比较次数为( D )。(A)0(B)1(C)10(D)50035、栈操作的原则是( B )（A）先进先出 （B）后进先出 （C）栈顶插入 （D）栈顶删除36、一个栈的入栈序列是，则栈的输出序列有（C）种(A)3 (B)2 (C)5 (D)437、当利用大小为N的一维数组顺序存储一个栈时，假定用top=1表示栈空，则向这个栈插入一个元素时，首先应执行（ A ）语句修改top指针。(A)top+ (B)top- (C)top=NULL (D)top38、线性表采用顺序存储时，结点的存储地址（ C ）（A）必须是不连续的 （B）连续与否均可 （C）必须是连续的 （D）和头结点的存储地址有关39、已知完全二叉树有26个结点，则整棵二叉树有多少个度为1的结点？（ D ）（A）1 （B）0 （C）2 （D）不确定40、在一个具有n个结点的单链表中查找其值等于x的结点，在查找成功的情况下，需平均比较( D )个元素结点。(A) n/2 (B) n (C) (n+1)/2 (D) (n-1)/241、串的长度是( D )。(A) 串中不同字符的个数 (B) 串中不同字母的个数(C) 串中所含字符的个数n(n0) (D) 串中所含字符的个数n(n0)42、若有一个栈的输入序列是1,2,3,n，输出序列的第一个元素是n，则第i个输出元素是( A )(A) n-i (B) n-i-1 (C) n-i+1 (D) 不确定43、设有一个栈，元素的进栈次序A，B，C，D，E，下列( A )是不可能的出栈序列。(A) A,B,C,D,E （B）B,C,D,E,A(C) E,A,B,C,D （D）E,D,C,B,A44、具有20个结点的二叉树，其深度最多为 B 。(A)4(B)5(C)6(D)2045、在一个具有n个结点的无向完全图中，包含有( A )条边。(A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) n246、采用顺序检索的方法检索长度为n的线性表，则检索每个元素的平均比较次数为( B )。(A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/247、二维数组A45按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A00的存储地址为1000，则数组元素A32的存储地址为（D） (A) 1012 (B) 1017 (C) 1034 (D) 103648、已给下图，哪一项是该图的拓扑排序？（ A ）abcde (A)a，b，c，d，e (B)a，c，b，d，e(C)a，b，d，c，e (D)a，b，c，e，d49、下面程序段的时间复杂度为（ D ）。 for(i=0;im;i+) for(j=0;jnext=p-next; p-next=s; （B）q-next=s; s-next=p;（C）p-next=s-next; s-next=p; （D）p-next=s; s-next=q;51、设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（ C ）。(A) 40，42，45，55，80，83(B) 42，40，45，80，85，88(C) 42，40，45，55，80，85(D) 42，40，45，85，55，8052、设某哈夫曼树中有199个结点，则该哈夫曼树中有（ B）个叶子结点。(A) 99(B) 100(C) 101(D) 10253、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行 A 。 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;54、栈的插入与删除操作在 A 进行。 A、栈顶 B、栈底 C、任意位置 D、指定位置55、在一个循环顺序队列中，队首指针指向队首元素的 A 位置。 A、前一个 B、后一个 C、当前 D、后面56、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为_A_。 A、 24 B、 48 C、 72 D、 5357、当利用大小为N的一维数组顺序存储一个栈时，假定用top=1表示栈空，则向这个栈插入一个元素时，首先应执行 A 语句修改top指针。 Atop+； Btop-； Ctop=NULL ； Dtop；58、线性表L在(B)情况下适合使用链式结构实现。(A)需经常修改L中的结点值(B)需不断对L进行删除、插入(C)L中含有大量的结点(D)L中结点结构复杂59、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（ A）。(A) 第i行非0元素的个数之和(B) 第i列非0元素的个数之和(C)第i行0元素的个数之和(D) 第i列0元素的个数之和60、设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（ C）。(A) 1(B) 2(C) 3(D) 461、设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（ B）个。(A) 4(B) 5(C) 6(D) 762、在内部排序中，排序时不稳定的有（ B ）。（A）插入排序（B）冒泡排序（C）快速排序（D）归并排序63、设字符串S1=ABCDEFG，S2=PQRST，则运算S=CONCAT(SUB(S1,2,LENGTH(S2)，SUB(S1,LENGTH(S2),2)的结果为( A )(A) BCQR (B) BCDEF (C) BCDEFG (D) BCDEFEF64、在计算机存储器内表示数据时，物理地址与逻辑地址相同并且是连续的，称之为(C)。(A)存储结构 (B)逻辑结构 (C)顺序存储结构 (D)链式存储结构65、链接存储的存储结构所占存储空间(A)。(A)分为两部分，一部分存放结点值，另一部分存放表示结点之间关系的指针(B)只有一部分，存放结点值(C)只有一部分，存储表示结点之间关系的指针(D)分为两部分，一部分存放结点值，另一部分存放结点所占单元数66、下列排序方法中，(D)是稳定的排序方法。(A)希尔排序 (B)直接选择排序 (C)快速排序 (D)直接插入排序67、一组记录的关键字序列为(46,79,56,38,40,84)，则利用堆排序的方法建立的初始堆为(C)。(A)79,46,56,38,40,84 (B)84,79,56,38,40,46(C)84,79,56,46,40,38 (D)84,56,79,40,46,3868、AOV网是一种（ B ）。A有向图 B无向图 C无向无环图 D有向无环图69、当采用分快查找时，数据的组织方式为 ( C ) A数据分成若干块，每块内数据有序B数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D. 数据分成若干块，每块（除最后一块外）中数据个数需相同70、对线性表进行二分查找时，要求线性表必须（ A）A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序71、对于一个不带权的无向图的邻接矩阵而言，（ C ）。 A矩阵中非零元素的数目等于图中边的数目 B矩阵中非全零的行的数目等于图中顶点的数目 C. 第i行的非零元素的数目与第i列的非零元素的数目相等 D。第i行与第i列的非零元素的总数等于第i个顶点的度数72、具有3个结点的二叉树有( D )种。A.3 B.4 C.6 D.573、广义表的长度是指( D )。 A广义表中元素的个数 B广义表中原子元素的个数 C广义表中表元素的个数 Di广义表中括号嵌套的层数75、输入序列为ABC，可以变为CBA时，经过的栈操作为( B )。A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop76、一个队列的入队序列是1，2，3，4，则队列的输出序列是( A )。A.4，3，2，1 B.1，2，3，4 C.1，4，3，2 D.3，2，4，177、数据结构在计算机内存中的表示是指( D )。A. 数据的存储结构B. 数据结构C. 数据的逻辑结构 D. 数据元素之间的关系78、已知一组关键字为25，48，36，72，79，82，23，40，16，35，其中每相邻两个为有序子序列。对这些子序列进行一躺两两归并的结果是（A ）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，8279、已知一个图如下所示，从顶点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 80、在一棵树中，（ C ）没有前驱结点。 A. 分支结点 B. 叶结点 C. 树根结点 D. 空结点81、在一个循环顺序队列中，队首指针指向队首元素的 A 位置。 A、前一个 B、后一个 C、当前 D、后面82、栈的插入与删除操作在 A 进行。 A、栈顶 B、栈底 C、任意位置 D、指定位置83、在一个单链表中，已知*q结点是*p结点的前趋结点，若在*q和*p之间插入*s结点，则需执行（ A）。As-next=p-next; p-next=s; Bq-next=s; s-next=p;Cp-next=s-next; s-next=p; Dp-next=s; s-next=q;84、在关键字序列（12，23，34，45，56，67，78，89，91）中二分查找关键字为45，89和12的结点时，所需进行的比较次数分别为（ D ）A.4，4，3 B.4， 3， 3 C.3，4，4 D.3，3，485、若结点的存储地址与其关键字之间存在的某种映射关系，则称这种存储结构为（ B ）A.顺序存储结构 B.链式存储结构C.索引存储结构 D.散列存储结构 86、算法分析的目的是( A )。A 找出数据结构的合理性B 研究算法中输入和输出的关系C 分析算法的效率以求改进D 分析算法的易懂性和文档性87、将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点X的双亲编号为（ A ）A、24 B、25 C、23 D、无法确定88、总共3层的完全二叉树，其结点数至少有_B_个。(A)3(B)4(C)7(D)889、一个无向连通图有5个顶点、8条边，则其生成树将要去掉 A 条边。(A)3(B)4(C)5(D)690、 已知8个元素（34,76,45,18,26,54,92,65），按照依次插入结点的方法生成一棵二叉排序树，该树的深度为( B )。(A) 4 (B) 5 (C) 6 (D) 791、采用顺序检索的方法检索长度为n的线性表，则检索每个元素的平均比较次数为( D )。(A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/292、 如果结点A有3个兄弟，而且B为A的双亲，则B的度为( C )(A) 3 (B) 4 (C) 5 (D) 193、Substr(DATA STRUCTURE,5,9) = ( A )。(A) STRUCTURE (B) DATA (C) ASTRUCTUR (D) DATA STRUCTURE94、设连通图G的顶点数为n，则G的生成树的边数为( A )。(A) n (B) n-1 (C) 2n (D) 2n-195、具有2000个结点的二叉树，其高度至少为( C )。(A) 9 (B) 10 (C) 11 (D) 1296、采用顺序检索的方法检索长度为n的线性表，则检索每个元素的平均比较次数为( D )。(A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/297、在具有N个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为 A 。(A)front=rear(B)（rear+1）%MAXSIZE=front(C)front-rear=1(D)rear%MAXSIZE=front98、设一颗完全二叉树中根结点的编号为1，而且23号结点有左孩子但没有右孩子，则完全二叉树总共有 C 个结点。(A)24(B)45(C)46(D)4799、判定一个栈ST（最多元素为MaxSize）栈满的条件是( D )。(A)ST-top!=1 (B)ST-top= =1(C)ST-top!=MaxSize-1 (D)ST-top= =MaxSize-1100、设有1000个元素，用二分法查找时，最小比较次数为( B )。(A)0(B)1(C)10(D)500101、设某完全无向图中有n个顶点，则该完全无向图中有（ A ）条边。(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1102、 若给定关键字集合为20,15,14,18,21,36,40,10，一趟快速排序结束时，键值的排列为( A )(A) 10,15,14,18,20,36,40,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,21103、具有n个顶点的完全有向图的边数为( B )。(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1104、下列排序算法中，其中（ D ）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序105、设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的平均查找长度为（ C ）。(A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1)106、设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ A）条有向边。(A) n (B) n-1 (C) m (D) m-1二、填空题1、数据结构有线性结构和 。2、对于一个以顺序实现的循环队列Q0.m-1，队头、队尾指针分别为f,r,其判空的条件是_，判满的条件是_。3、数据结构包括数据的逻辑结构、数据的以及对数据的操作运算。4、假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为 。5、算法有五个特征它们是 、 、可行性、输入和输出。6. 具有64个结点的完全二叉树的深度为 。7. 设有一个空栈，现输入序列为1,2,3,4,5,经过Push,Push,Pop,Push,Pop,Push,Pop,Push后，输出序列为 。8.数据的逻辑结构是从逻辑关系上描述数据，它与数据的 无关，是独立于计算机的。9. 设一棵二叉树共用50个叶结点（终端结点），则共有 个度为2的结点 。10. 高度为5的二叉树，最少有 个结点，最多有 个结点。11、已知某算法的执行时间为（n+n2）/2+log2(2n+1)，n代表问题规模，则该算法的时间复杂度是 。12、数据结构有集合、线性结构、 、 等几种逻辑结构。13、在一个长度为n的顺序表中插入一个元素，最少需要移动 个元素，最多需要移动 个元素。14、数据的物理结构主要包括_和_两种情况。15、深度为k的完全二叉树中最少有_个结点。16、栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为_表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_表。17、设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是_。18、中序遍历二叉排序树所得到的序列是_序列（填有序或无序）。19、设一棵完全二叉树中有500个结点，则该二叉树的深度为_；若用二叉链表作为该完全二叉树的存储结构，则共有_个空指针域。20、不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为_。21、高度为h（h0）的二叉树，最少有 个结点，最多有 个结点。22、设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是_；r=s; r-next=null;。23、具有10个顶点的无向图，边的总数最多为_。24、一个55的对称矩阵采用压缩存储，需要存储_个元素。25、设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有_个结点数。26、设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是_；r=s; r-next=null;。27、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有_ 个叶子的结点。28、稀疏矩阵进行表示时，有三种方式，分别是三元组、 和 。29在一个带头结点的单向循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head 。30采用折半查找方法查找长度为n的线性表时，查找的时间复杂度为_ 。31、设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_。32、链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的_ _ 域的值。33、设广义表C=( ( (a,(b,c,d) ,e ) ), 则C的长度为_,表尾为_。34、在单链表中，除了首元结点之外，任一结点的存储位置由_指示。35在单链表中设置头结点的作用是_。36设广义表L=（a），则该广义表的长度是_，深度是_ 。37若一个二叉树含有n个结点，则它的二叉链表中必有 个空的链域。38、在双链表中，存储一个结点有三个域，一个是数据域；另两个是指针域，分别指向 _和_。 39、在循环列队中，设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么，队空标志为_，队满标志为_。40、在顺序表中插入或删除一个元素，需要平均移动_元素，具体移动的元素个数与_有关。41、当向一个长度为n的顺序表的第i(1in1)个元素之前插入一个元素时，需要向后移动_个元素。42、顺序表中逻辑上相邻的元素的物理位置_相邻。单链表中逻辑上相邻的元素的物理位置_相邻。43、树中任意结点允许有_个孩子结点，除根结点外，其余结点有_个双亲结点。44、已知二叉树有42个结点，度为1的结点个数有19个，则叶子结点有_个，度为2的结点有_个。45、一棵完全二叉树共有47个结点，5号结点的双亲是_ ，左孩子是_ ；25号结点的双亲是_ ，右孩子是_ 。46、对于n个顶点e条边的无向图，其邻接矩阵中有_个数据，邻接表中有_个边结点。47、判断一个有向图是否存在环的方法是使用 。48、排序是指将无序的数据元素序列转变成一个有序序列，把序列中的记录，通过某些方法整理成按照_递增或递减次序排列的处理过程。49、静态查找表和动态查找表的主要区别是_。50. 一个具有n个顶点的有向完全图的弧数为 。51在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为 。52、在一个具有n个顶点的无向完全图中，包含有_条边，在一个具有n个顶点的有向完全图中，包含有_条边。53、广义表A= (a,(a,b),(a,b),c),则它的深度为_，它的长度为_。54、对于n个顶点e条弧的有向图，其邻接矩阵中有_个数据，邻接表中有_个弧结点。55、树有三种常用的存储结