数据结构考试题库

1、绪论一、填空题1.数据的逻辑结构被分为集合、（线性结构 ）、（树形结构 ）和 （图状结构 ） 四种。2. 物理结构是数据结构在计算机中的表示，又称为（存储结构 ）。3. 数据元素的逻辑结构包括（ 线性 ）、（树）和图状结构 3 种类 型，树形结构和图状结构合称为（非线性结构 ）。4. （数据元素 ）是数据的基本单位， （数据项 ）是数据不可分割的最 小单位。5. 线性结构中元素之间存在（一个对一个 ） 关系，树形结构中元素之间 存在 （一个对多个 ）关系，图状结构中元素之间存在（多个对多个 ）关系。？ 6.数据结构是一门研究非数值计算的程序设计问题中：计算机的（数据元素 ）以及它们之间的 （关

2、系）和（运筹 ）等的学科。7. 算法的五个重要特性为有穷性、确定性、（输入 ）、（输出 ）和（可行性）。二、选择题1. 数据的不可分割的基本单位是（D）。A. 元素B.结点C.数据类型D.数据项*2. 线性表的逻辑顺序与存储顺序总是一致的，这种说法（B）。A.正确B.不正确C.不确定D.无法选择3. 线性结构是指数据元素之间存在一种（D）。A. 一对多关系B.多对多关系C.多对一关系D.一对一关系4. 在数据结构中，从逻辑上可以把数据结构分成（A）。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构5. 线性表若采用链式存储结构时，要求内存中可用存储单

3、元的 地址 （ D）。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的 D.连续不连续都可以三、简答题1. 算法的特性是什么。答：有穷性 确定性 可行性 有 0 或多个输入 有 1 或多个输出线性结构一、填空题1. 在一个长度为n的线性表中删除第i个元素（1< i 01时，需向 前移动（n-i）个元素。2 .从循环队列中删除一个元素时，其操作是（先移动队首指针，后取出元素 ）。3在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为 （p->next） 。4. 在一个单链表中指针 p所指向结点的后面插入一个指针 q所指向 的结点时，首先把（p->

4、next）的值赋给q->next，然后（q->date）的值赋 给 p->next。5. 从一个栈删除元素时，首先取出 （栈顶元素 ），然后再使 （栈顶指 针 ）减 1 。6. 子串的定位操作通常称做串的 （模式匹配 ）。7. 设目标T= abccdcdccbaq模式P= cdc（则第（六）次匹配成功。8. 顺序栈 S 中 ， 出 栈操作时 要执行的 语句序列 中有S->top（-）；进栈操作时要执行的语句序列中有S->top（+）。9. 顺序表中逻辑上相邻元素的物理位置（一定 ）紧邻；单链表中 逻辑上相邻元素的物理位置 （不一定 ）紧邻。10. 在（循环）链表中

5、，从任何一结点出发都能访问到表中的所有结 点。1 1 .栈和队列均是 （运算受限 ）的线性表，栈的特点是 （先进后出 后进 先出）；队列的特点是 （先进先出 后进后出 ）。12. 通常，在程序中使用的串可分为串常量和串变量；而串按存储 方式又可分为 （定长顺序存储 ）和（堆分配存储 ）。13. 循环队列头指针 front 指向队头元素，队尾指针 rear 指向队 尾 元素后的一个空闲元素，队列的最大空间为 Queueleno在循环队列中， 队空标志为 （front=rear）， 队满标志为 （ rear+11%max=front ）。 当 rear>=front 时，队列长度为 (rea

6、r-front )，当 rear<front 时，队列 长 度为 (rear-front+max )。14. 在一个长度为n的线性表中的第i个元素(1 < i 之前插入一 个元素时，需向后移动 (n-i+1 )个元素。15. 在具有n个单元的循环队列中，队满时共有(n-1)个元素。16. 带 有 一 个 头 结 点 的 单 链 表 Head 为 空 的 条 件 是 (Head->next=null)。17. 在一个单链表中删除指针p 所指向结点的后继结点时，需要把(p->next->next)值赋给 p->next 指针域。18. 一个顺序循环队列存于aM

7、中，假定队首和队尾指针分别 为front和rear，则判断队空的条件为(a.front=a.rear)，判断队满的条 件为 (a.rear+1 )%M=a.front )。19. 在双向链表中，每个结点有两个指针域，一个指向其(前驱) 结点，另一个指向其 (后继 )结点，最后一个结点的 (后继结点 )指针域为 空。*20. 若 D=(a ，(b ，c) ， e ， a) ， 则 Head( D )=() ， Tail( D )=()， Head(Tail( D )=( ) 。(本人不会)21.在循环链表中，每个结点有(一个)个指针域，指向其 (后继)结点，最后一个结点的指针域 (为空)。*22

8、. 若 S=(a ， (b ， c) ， e ， d) ， 则 Head( S )=() ，Tail( S )=()， Head(Tail( S )=()。 (本人不会)二、选择题1在一个单链表中，若q所指结点是p所指结点的前驱结点，若在q 与 p 之间插入一个 s 所指的结点，则执行 (A)。A.s->link=p->link; p->link=s; B.p->link=s; s->link=q;C.p->link=s->link; s->link=p; D.q->link=s; s->link=p;2. 对于顺序存储的队列，存储空

9、间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数(A)。A.R-F B.n+R-F C.(R-F+1)mod n D.(n+R-F)mod n3. 如下陈述中正确的是 (A)。A.串是一种特殊的线性表B.串的长度必须大于零C.串中兀素只能是字母D.空串就是空白串4. 若让元素 1， 2， 3 依次进栈，则出栈次序不可能出现(C)的情况。A.3，2，1 B.2，1，3 C.3，1，2 D.1，3，25判定一个队列QU (最多元素为m0)为空的条件是(C)。A.QU->rear-QU->front=m0 B.QU->rear-QU->front-1

10、=m0 C.QU->front=QU->rearD.QU->front=QU->rear+16. 设目标串S= abcde,模式串p= de'则第(C)次匹配成功。A.1B.2 C.4 D.57设字符串 s1= ABCDEFG,S2= PQRS'T, subl ,sub2 为空串。 则运算 s=Concat(T ， SubString(sub1 ， s1 ， 2 ， SubLength(s2)， SubString(sub2，s1，SubLength(s2)，2) 后的串 T 值为( D)。A. BCDEF B. BCDEFG C. BCPQRST D.

11、 BCDEFEF8. 一个顺序线性表第一个元素的存储地址是100，每个元素的 长度为2,则第5个元素的地址是(B)。A.100B.108C.110D.1209非空的循环单链表 head的尾结点(由p所指向)满足(C)。A.p->next=NULL B.p=NULLC.p->next=head D.p=head10. 在一个链队中，假设f和r分别为队首和队尾指针，则删除 一个结点的运算时 (C)。A.r=f->next; B.r=r->next;C.f=f->next; D.f=r->next;11. 在一个长度为n的线性表中，删除值为x的元素时，需要比 较

12、元素和移动元素的总次数为 (C)。A.(n+1)/2B.n/2 C.n D.n+112. 在一个单链表中,若要在 p 所指向的结点之后插入一个新结 点, 则需要相继修改(B)个指针域的值。A.1B.2C.3D.413. 线性结构中,每个结点 (C)。A.无直接前驱B.只有一个直接前驱和个数不受限制的直接后继C.只有一个直接前驱和后继D.有个数不受限制的直接前驱和后继14. 队列是限定在(D)进行操作的线性表。A.中间 B.队头 C.队尾D.端点15. 设串 S1= “ABCDEFG , S2= “PQRS” 函数 StrCat(x,y)返回 x 和y串的连接串，函数 StrSub(S, i,

13、j)返回串S的从序号i的字符开始的j个字符组成的子串，StrLen(S)返回串S的长度，则StrCat(StrSub(S1 , 2， StrLen(S2) ， StrSub(S1， StrLen (S2)， 2)的结果串是 (D)。A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF16. 学生成绩表是一种(C)结构。A.图形 B.树形 C.线性 D.集合17. 在一个链队中，假设f和r分别为队首和队尾指针，贝U插入s所 指结点的运算时 (C)。A.f->next=s; f=s; B.r->next=s; r=s; C.s->next=r; r=s;D.s

14、->next=f; f=s;18. 向顺序表中的 i 位置处插入元素，下面哪项能够准确的表明i 的位置是合法的。(D)A.i<=1|i>l->length+1B.i>=1C.i>=l->length+1D.1<=i<=l->length+119. 设线性链表中结点的结构为(data, next)，已知指针q所指 结点是指针p所指结点的直接后继，若在 *q和*p之间插入结点*s，则 应执行(A)操作。A.s->next=p->next; p->next=s; B.q->next=s; s->next=p;

15、C.p->next=s->next; s->next=p; D.p->next=s; s->next=q;20. 一个栈的入栈序列为a, b, c,d, e,则出栈序列不可能的是(C)。A.edcba B.dcbae C.dceab D.abcde21. 如果以链表作为栈的存储结构,则出栈操作时(B)。A.必须判别栈是否满B.必须判别栈是否为空C.必须判别栈元素类型D.可不做任何判断22. 设有两个串p和q,求q在p中首次出现的位置的运算称为(B)。A.连接 B.模式匹配 C.求子串 D.求串长23. p 指向线性链表中的某一结点,则在线性链表的表尾插入结 点 S

16、 的语句序列是 (A)。A. while(p->next!=NULL) p=p->next; p->next=s; s->next=N ULL;B. while(p!=NULL) p=p->next; p->next=s; s->next=NULL;C. while(p->next!=NULL) p=p->next; s->next=p;p->next=NULL;D. while(p!=NULL) p=p->next->next;->next;p->next=s;s->next=p24. 向顺序栈中

17、压入新元素时,应当(A)。A.先移动栈顶指针，再存入元素B.先存入元素，再移动栈顶指针C.先后次序无关紧要D. 同时进行25. 假定一个顺序队列的队首和队尾指针分别为f和，贝U判断队空的条件为 (D)。f+1=rB.r+1=f C.f=0 D.f=r26. 栈的插入和删除操作在(A)进行。A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置27. 栈和队列的共同点是 (C)。A. 都是先进后出B. 都是先进先出C.只允许在端点处插入和删除元素D.没有共同点28. 若 6 行 8 列的数组以列序为主序顺序存储， 基地址为 1000， 每 个元素占 2 个存储单元， 贝第 5 行第 3 列的元素

18、 (假定无第 0行第 0列) 的地址是 ( B) 。A.1086 B.1032C.1068 D.答案 A，B，C 都不对29. 设有 50 行的二维数组 A5060 ，其元素长度为 2 字节，按 行优先顺序存储，基地址为100，贝U元素A1825的存储地址 为(D)。A.1850B.2188C.1950D.2310三、论述题1. 写出线性表的插入算法、删除算法。解：太麻烦 略略略*2.画出主串为 ababcabcacbab子串为 ab的模式匹配 过程。解：四、算法设计题1. 在带头结点的单链线性表 L 中第 i 个位置之前插入新的元素e。略2. 在带头结点的单链线性表 L中，删除第i个元素，并

19、由e返回 其 值。略树形结构一、填空题1. 赫夫曼树，又称最优树，是一类(带权路径 )长度最短的树。2. 在一棵二叉树中，第 5 层上的结点数最多为 (16)个。3. 一棵高度为 5 的二叉树中最少含有 (5)个结点，最多含 有(31) 个结点。4. 若一棵二叉树中有 8 个度为 2 的结点，贝它有 (9)个叶子。5. 一棵深度为 6 的满二叉树有 (31)个非终端结点。6树中结点A的（子树数）称为结点A的度。7. 对一棵二叉排序树进行中序遍历时，得到的结点序列是一个 （升序序列）。8在树型结构中，根结点没有前驱结点，其余每个结点有且仅有（一） 个前驱结点；叶子结点（没有）后继结点，其余每个结

20、点都可以有 （一或 多个）个后继结点。9在最优二叉树中没有度为1的结点，则一棵有n个叶子结点的最优二叉树中共有（2n-1）个结点。10.深度为4 （设根的层数为 1）的二叉树至少有（4）个结点，至多 有（15）个结点，第i层上至多有（2n-1 ）个结点。多有（63）个结点，第二、选择题11. 深度为6 （设根的层数为1）的二叉树至少有（6）个结点，至 4层上至多有（8）个结点。1具有65个结点的完全二叉树的高度为（）oA. 87匸 6D.52.有门（门0）个结点的完全二叉树的深度是（）oA. log2（n）lB. Iog2（n） + 1c. llog2（n + 1）1D. llog2（n）J

21、+ 13.在一棵完全二叉树中，若编号为i的的结点存在左孩子, 左孩子结点的编号为（）OA. 2iB. 2i-1C 2 i +1D.2i+24一棵门个结点的二叉树，其空指针域的个数为（）oA. nB. n+1C. n-1D” 不确定A.n B. N+1C.n-1D.不确定注：1:B 2:D 3:A4:B5下面(A )是对的。A.哈夫曼树中结点的度只可能是0和2。B.二叉树的顺序存储中，是以先序遍历存储结点的。C.完全二叉树实际上就是满二叉树。D.一棵二叉树第i层的最大结点数为 2i-1。6. 将含 100 个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号 为 1。编号

22、为 49 的结点 X 的右孩子编号为 (B)。A.98B.99C.24 D.无法确定7先序为A，B，C且后序为C，B，A的二叉树共有(B)种。A.3B.4C.5D.68. 在一棵度为 3 的树中，度为 3 的结点个数为 2，度为 2 的结点个 数为 1，则度为 0 的结点个数为 (C)。A.4B.5C.6D.79. 由权值分别为 11， 8， 6， 2， 5的叶子结点生成一棵哈夫曼树， 它的带权路径长度为 (B)A.24B.71C.48 D.5310. 一个具有 767 个结点的完全二叉树， 其叶子结点个数为 (B)。A.382B.384C.385D.38611. 在一棵具有 35 个结点的完

23、全二叉树中， 该树的深度为 (A)。A.6B.7C.5D.812. 由三个结点构成的二叉树，共有(B)种不同的结构。A.3B.4C.5D.613. 深度为k的二叉树至多有(2K-1)个结点(k > 1)A.2k B.2k-1 C.2k-1 D.2k三、简答题1. 已知一棵二叉树的先序遍历和中序遍历，则该二叉树的后序 遍历是什么？先序遍历： A ，B，C，D，E，F，G，H，I，J 中序遍历： C，B，A，E，F，D，I，H ，J，G 解：后序遍历： C,B,F,E,I,J,H,G,D,A2. 如下图的森林转化为二叉树。解：此题没法写略略略3. 已知某二叉树的前序序列为EBADCFHGI

24、, 中序序列为ABCDEFGHI ,请给 出二叉树且写出二叉树的后序序列。解：二叉树略后序序列:A,C,D,B,G,I,H,F,E4试用权集合6，4，8，3，7，5，10，8，2，1，11，构造哈夫曼(Huffman)树。(1)画出这棵哈夫曼树；(2)分别计算该哈夫曼树的路径长度和带权路径长度。解：略(2)路径长度为：1x2+2x4+3x8+4x3+5x2=60;带权路径长度为：3x(6+7+8+8+10+11)+4x(3+4+5)+5x(1+2)=2135试按表(10，18，9，2, 20，5, 6，15，19，25)中元素的排列次序，将所有元素插入一棵初始为 空的二叉排序树中，使之仍是一棵

25、二叉排序树。(1)试画出插入完成之后的二叉排序树；若查找元素2，它将依次与二叉排序树中哪些元素比较大小？ (3)对该树进行中序遍历，试写出中序遍历序列。解：略(2) 10,9,2(3) 2,5,6,9,10,15,18,19,20,256已知一棵二叉树的顺序存储表示如下，其中0表示空，请分别写出二叉的先序、中序、后序遍历序列。1234567891011121320846515300001018035解：先序序列：20,8,5,15,10,18,46,30,35 中序序列：5,8,10,15,18,20,30,35,46 后序序列：5,10,18,15,8,35,30,46,20 7将如下图的一

26、般树转化为二叉树。H8将下图中的二叉树转换成森林四、论述题1. 由分别带权为 3，12，9，2，5，7 的叶子结点构造一棵哈夫 曼树，并计算该树的带权路径长度。解 :带权路径长度为 :91图状结构一、填空题1若一个图的顶点集为a , b, c, d, e, f，边集为(a , b), (a, c), (b, c), (d , e),则该图含有(3) 个连通分量。2. 具有 10 个顶点的无向图,边的总数最多为(45)。3. 图的广度优先搜索遍历类似于树的(按层次 )遍历的过程。4. 在无向图 G 的邻接矩阵 A 中,若 Aij 等于 1,则 Aji 等于 (1)。5. 图的 (深度)优先搜索遍

27、历算法是一种递归算法,图的(广度 ) 优先搜索遍历算法需要使用队列二、选择题1. 一个有n个顶点的无向图最多有(C)条边。A.nB.n(n-1)C.n(n-1)/2D.2n2. 在一个无向图中，所有顶点的度数之和等于所有边数的(B)倍。A.3B.2 C.1D.1/23. 在一个具有 n 个顶点的无向图中,若具有 e 条边,则所有顶点的度数之为(D) 。A.n B.e C.n+e D.2e三、简答题1. 给出如下图所示的无向图G 的邻接矩阵存储结构。 (答案略)2. 画出下图的邻接表存储结构（答案略）abcde0 10 0 110 0 100 0 0 1 10 110 110 1103. 给出下

28、图从A点出发的深度优先遍历和广度优先遍历的顶点 序列。解：深度优先遍历：AECDB广度优先遍历：AEBDC5.给出从 V1 点出发的深度优先遍历和广度优先遍历的顶点序列 解：深度优先遍历 ;v1 v2 v3 v4 v5 v6 v7 v8 v9广度优先遍历 ;v1 v2 v3 v4 v7 v5 v6 v8 v9四、论述题1写出下面带权有向图的的关键路径解：(1)1->2->5->8->92. 设将整数1、2、3、4依次进栈，请回答下述问题：1)若入、出栈顺序为 Push(1)，Pop()，Push(2)，Push(3)， Pop()，Pop()，Push(4)，Pop()，则出栈 的数字序列是什么？2)能否得到出栈序列1432和1423 ?并说明为什么不能得到或者如何得到？解：(1):1324(2):可以得到1432 不能得到1423得到 1432 的过程为：Push(1),pop(),push(2),push (3) ,push(4),pop(),pop(),pop(),不能得到1423无法执行此操作3. 求出下图的最小生成树（答案略）答