数据结构考试习试题库完整

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. 动态结构

3、和静态结构 B. 紧凑结构和非紧凑结构C.线性结构和非线性结构 D. 内部结构和外部结构5. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址( D)。A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续不连续都可以三、简答题1. 算法的特性是什么。.答：有穷性 确定性 可行性 有 0 或多个输入 有 1 或多个输出线性结构一、填空题1. 在一个长度为n 的线性表中删除第i 个元素（ 1i n）时，需向前移动 ( n-i ) 个元素。2. 从循环队列中删除一个元素时，其操作是( 先移动队首指针，后取出元素 ) 。3.在线性表的单链接存储中，若一个元素所在结点

4、的地址为p，则其后继结点的地址为 ( p->next ) 。4.在一个单链表中指针 p 所指向结点的后面插入一个指针q 所指向的结点时，首先把 ( p->next ) 的值赋给 q->next ，然后 ( q->date ) 的值赋给 p->next 。5. 从一个栈删除元素时，首先取出 ( 栈顶元素 ) ，然后再使 ( 栈顶指针)减 1。6. 子串的定位操作通常称做串的 ( 模式匹配 ) 。7. 设目标 T=abccdcdccbaa，模式 P=cdcc则第 ( 六) 次匹配成功。8. 顺序栈 S 中 ， 出 栈操作时 要执行的 语句序列 中有S->top(

5、 - ) ；进栈操作时要执行的语句序列中有S->top( +) 。9. 顺序表中逻辑上相邻元素的物理位置 ( 一定 ) 紧邻；单链表中 逻辑上相邻元素的物理位置 ( 不一定 ) 紧邻。10. 在 ( 循环 ) 链表中，从任何一结点出发都能访问到表中的所有结点。11. 栈和队列均是 ( 运算受限 ) 的线性表，栈的特点是 ( 先进后出 后进先出) ；队列的特点是 ( 先进先出 后进后出 ) 。12. 通常，在程序中使用的串可分为串常量和串变量；而串按存储方式又可分为 ( 定长顺序存储 ) 和 ( 堆分配存储 ) 。13. 循环队列头指针 front 指向队头元素，队尾指针 rear 指向队

6、 尾元素后的一个空闲元素， 队列的最大空间为 Queuelen 。在循环队列中 ，队空标志为 (front=rear) ， 队满标志为（rear+1 ）%max=front) 。 当(rear>=front时，队列长度为 ( rear-front) ，当 rear<front时，队列 长度为 ( rear-front+max ) 。14. 在一个长度为n 的线性表中的第i 个元素（ 1i n）之前插入一.个元素时，需向后移动( n-i+1 ) 个元素。15. 在具有 n 个单元的循环队列中，队满时共有( n-1 ) 个元素。16.带 有 一 个 头 结 点 的 单 链 表Head为

7、 空 的 条 件 是( Head->next=null) 。17. 在一个单链表中删除指针p 所指向结点的后继结点时，需要把( p->next->next ) 值赋给 p->next 指针域。18. 一个顺序循环队列存于aM 中，假定队首和队尾指针分别为front 和 rear ，则判断队空的条件为 ( a.front=a.rear) ，判断队满的条件为 ( （a.rear+1 ）%M=a.front ) 。19. 在双向链表中， 每个结点有两个指针域， 一个指向其 ( 前驱 ) 结点，另一个指向其 ( 后继 ) 结点，最后一个结点的( 后继结点 ) 指针域为空。*20

8、.若 D=(a， (b， c)， e， a)，则 Head( D )=()，Tail( D )=() ，Head(Tail( D )=() 。（本人不会）21. 在循环链表中， 每个结点有 ( 一个 ) 个指针域， 指向其 ( 后继 ) 结点，最后一个结点的指针域 ( 为空 ) 。*22.若S=(a，(b，c)，e ，d)，则Head( S )=()， Tail( S)=()， Head(Tail( S)=()。（本人不会）二、选择题1. 在一个单链表中，若q 所指结点是p 所指结点的前驱结点，若在q与 p 之间插入一个 s 所指的结点，则执行 ( A) 。 A.s->link=p-&g

9、t;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. 对于顺序存储的队列，存储空间大小为n，头指针为 F，尾指针为 R。若在逻辑上看一个环，则队列中元素的个数( A) 。A.R-FB.n+R-F C.(R-F+1)mod nD.(n+R-F)mod n3. 如下陈述中正确的是 ( A) 。A. 串是一种特殊的线性表B. 串的长度必须大于零C.串中元素只能是字母D. 空串就是空白串4. 若让元素1，2， 3

10、依次进栈，则出栈次序不可能出现C( )的情况。A.3 ，2，1B.2 ，1，3C.3，1，2D.1 ，3，25. 判定一个队列 QU（最多元素为 m0）为空的条件是 ( C) 。A.QU->rear-QU->front=m0 B.QU->rear-QU->front-1=m0C.QU->front=QU->rearD.QU->front=QU->rear+1.6. 设目标串 S=abcdef ，模式串 p=de，则第 ( C) 次匹配成功。A.1B.2C.4D.57. 设字符串s1=ABCDEFG， S2=PQRST，T， sub1， sub2

11、为空串。则 运 算s=Concat(T，SubString(sub1，s1，2，SubLength(s2)， SubString(sub2，s1 ， SubLength(s2) ， 2)后的串T值为( D)。A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF8. 一个顺序线性表第一个元素的存储地址是100，每个元素的 长度为2，则第 5 个元素的地址是(B) 。A.100B.108C.110D.1209. 非空的循环单链表 head 的尾结点（由 p 所指向）满足 ( C) 。A.p->next=NULLB.p=NULLC.p->next=headD.p=head1

12、0. 在一个链队中，假设 f 和 r 分别为队首和队尾指针，则删除一个结点的运算时 ( C) 。A.r=f->next;B.r=r->next;C.f=f->next;D.f=r->next;11. 在一个长度为n 的线性表中，删除值为x 的元素时，需要比较元素和移动元素的总次数为C() 。A.(n+1)/2B.n/2C.nD.n+112. 在一个单链表中，若要在 p 所指向的结点之后插入一个新结点，则需要相继修改( B) 个指针域的值。A.1B.2C.3D.413. 线性结构中，每个结点 ( C) 。A. 无直接前驱 B. 只有一个直接前驱和个数不受限制的直接后继C.

13、只有一个直接前驱和后继 D. 有个数不受限制的直接前驱和后继14. 队列是限定在 ( D) 进行操作的线性表。A. 中间B.队头C. 队尾D. 端点15. 设串 S1=“ABCDEFG”， S2=“PQRST”，函数 StrCat(x,y) 返回 x和 y 串的连接串，函数 StrSub(S ， i ，j) 返回串 S 的从序号 i 的字符开始的 j 个 字 符 组 成 的 子 串 ， StrLen(S) 返 回 串 S 的 长 度 ， 则StrCat(StrSub(S1， 2， StrLen(S2)， StrSub(S1 ， StrLen (S2)，2) 的.结果串是 ( D) 。A.BCD

14、EFB.BCDEFGC.BCPQRST D.BCDEFEF16. 学生成绩表是一种 ( C) 结构。A. 图形B. 树形C. 线性D.集合17. 在一个链队中，假设f 和 r 分别为队首和队尾指针，则插入s 所指结点的运算时( C) 。A.f->next=s;f=s;B.r->next=s; r=s; C.s->next=r;r=s;D.s->next=f; f=s;18. 向顺序表中的 i 位置处插入元素，下面哪项能够准确的表明i 的位置是合法的。( D)A.i<=1|i>l->length+1B.i>=1C.i>=l->lengt

15、h+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;C.p->next=s->next;s->next=p;D.p->next=s;s->next=q;20. 一个栈的入栈序列为 a，b，c，d，e，则出栈序列不可能的是 ( C) 。A.edc

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

17、LL) 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. 向顺序栈中压入新元素时，应当 ( A) 。A. 先移动栈顶指针，再存入元素B.先存入元素，再移动栈顶指针C.先后次序无关紧要D.同时进行25. 假定一个顺序队列的队首和队尾指针分别为f 和 r ，则判断队空

18、的条件为 (D)。.f+1=rB.r+1=fC.f=0D.f=r26. 栈的插入和删除操作在 ( A) 进行。A. 栈顶 B. 栈底C. 任意位置 D. 指定位置27. 栈和队列的共同点是 ( C) 。A. 都是先进后出B. 都是先进先出C.只允许在端点处插入和删除元素D. 没有共同点28. 若 6 行 8 列的数组以列序为主序顺序存储，基地址为1000， 每个元素占 2 个存储单元，则第5 行第 3 列的元素 ( 假定无第 0 行第 0 列) 的地B址是( )。A.1086B.1032C.1068D. 答案 A，B， C 都不对29. 设有 50 行的二维数组A5060 ，其元素长度为 2字

19、节，按 行优先顺序存储，基地址为100，则元素 A1825 的存储地址D为( )。A.1850B.2188C.1950D.2310三、论述题1. 写出线性表的插入算法、删除算法。解：太麻烦略略略*2. 画出主串为 ababcabcacbab，子串为 abc的模式匹配过程。解：四、算法设计题1. 在带头结点的单链线性表L 中第 i 个位置之前插入新的元素e。略2. 在带头结点的单链线性表L 中，删除第i 个元素，并由e 返回其值。略树形结构一、填空题1. 赫夫曼树，又称最优树，是一类 ( 带权路径 ) 长度最短的树。2. 在一棵二叉树中，第 5 层上的结点数最多为 ( 16) 个。3. 一棵高度

20、为 5 的二叉树中最少含有 ( 5) 个结点，最多含 有( 31) 个结点。4. 若一棵二叉树中有 8 个度为 2 的结点，则它有 ( 9) 个叶子。5. 一棵深度为 6 的满二叉树有 ( 31) 个非终端结点。.6. 树中结点 A 的 ( 子树数 ) 称为结点 A 的度。7. 对一棵二叉排序树进行中序遍历时， 得到的结点序列是一个 ( 升序序列)。8. 在树型结构中，根结点没有前驱结点，其余每个结点有且仅有 ( 一)个前驱结点；叶子结点 ( 没有 ) 后继结点， 其余每个结点都可以有 ( 一或多个) 个后继结点。9. 在最优二叉树中没有度为 1 的结点，则一棵有 n 个叶子结点的最优二叉树中

21、共有 ( 2n-1 ) 个结点。10. 深度为 4（设根的层数为 1）的二叉树至少有 ( 4) 个结点，至多有( 15) 个结点，第i 层上至多有 ( 2n-1 ) 个结点。11. 深度为 6（设根的层数为 1）的二叉树至少有 ( 6) 个结点，至多有 ( 63) 个结点，第 4 层上至多有 (8) 个结点。.A.nB. N+1 C.n-1 D.不确定注： 1:B 2:D 3:A4:B5. 下面 ( A) 是对的。A. 哈夫曼树中结点的度只可能是0 和 2。 B. 二叉树的顺序存储中，是以先序遍历存储结点的。C. 完全二叉树实际上就是满二叉树。D.一棵二叉树第i 层的最大结点数为2i-1 。6

22、. 将含 100 个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为 1。编号为 49 的结点 X 的右孩子编号为 ( B) 。A.98B.99C.24D. 无法确定7. 先序为 A， B， C 且后序为 C， B， A 的二叉树共有 ( B) 种。A.3 B.4C.5D.68. 在一棵度为 3 的树中，度为 3 的结点个数为 2，度为 2 的结点个数为 1，则度为 0 的结点个数为 ( C)。A.4 B.5C.6D.79. 由权值分别为 11， 8， 6，2， 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为B( ) 。A.24B.71C.48D.5310. 一

23、个具有 767 个结点的完全二叉树， 其叶子结点个数为 ( B) 。A.382B.384C.385D.38611. 在一棵具有 35 个结点的完全二叉树中，该树的深度为 ( A) 。A.6 B.7C.5D.812. 由三个结点构成的二叉树，共有B( ) 种不同的结构。.A.3B.4C.5D.613. 深度为 k 的二叉树至多有 ( 2K-1 ) 个结点 (k 1) 。A.2kB.2k-1C.2k-1D.2k三、简答题1. 已知一棵二叉树的先序遍历和中序遍历，则该二叉树的后序遍历是什么？先序遍历： A，B， C， D， E， F，G， H， I ，J中序遍历： C，B， A， E， F， D，I

24、 ， H， J，G解：后序遍历： C,B,F,E,I,J,H,G,D,A2. 如下图的森林转化为二叉树。.解：此题没法写略略略3. 已 知 某 二 叉 树 的 前 序 序 列 为 EBADCFHGI ， 中 序 序 列 为 ABCDEFGHI，请给出二叉树且写出二叉树的后序序列。解：二叉树略后序序列 :A,C,D,B,G,I,H,F,E4. 试用权集合 6 ， 4， 8， 3， 7，5， 10， 8， 2， 1，11 ，构造 哈夫曼 (Huffman) 树。(1) 画出这棵哈夫曼树； (2) 分别计算该哈夫曼树的路径长度和带权路径长度。解： (1) 略(2) 路径长度为： 1x2+2x4+3x

25、8+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) 中元素的排 列次序，将所有元素插入一棵初始为空的二叉排序树中，使之 仍是一棵二叉排序树。(1) 试画出插入完成之后的二叉排序树； (2) 若查找元素 2，它将依次与二叉排序树中哪些元素比较大小 ? (3) 对该树进行中序遍历，试写出中序遍历序列。解： (1) 略(2)10,9,2(3)2,5,6,9,10,15,18,19,20,256. 已知一棵二叉树的顺序存储表示如下，其中0 表示空，请分别写出二叉

26、的先序、中序、后序遍历序列。12345678910111213.20846515300001018035解：先序序列： 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,207. 将如下图的一般树转化为二叉树。.8. 将下图中的二叉树转换成森林。BAEGKCFHILJ.四、论述题1. 由分别带权为 3，12， 9，2， 5， 7 的叶子结点构造一棵哈夫曼树，并计算该树的带权路径长度。解: 带权路径长度为 :91图状结构一、填空题1. 若一个图的顶点集为a ， b， c， d， e，

27、f ，边集为 (a ， b) ， (a ，c) ， (b ，c) ， (d ，e),则该图含有 (3) 个连通分量。452. 具有 10 个顶点的无向图，边的总数最多为( ) 。3. 图的广度优先搜索遍历类似于树的( 按层次 ) 遍历的过程。4. 在无向图 G的邻接矩阵 A 中，若 Aij等于 1，则 Aji1等于( )。5. 图的 ( 深度 ) 优先搜索遍历算法是一种递归算法，图的 ( 广度 ) 优先搜索遍历算法需要使用队列二、选择题1. 一个有 n 个顶点的无向图最多有 ( C) 条边。A.nB.n(n-1)C.n(n-1)/2D.2n2. 在一个无向图中， 所有顶点的度数之和等于所有边数

28、的( B) 倍。A.3B.2C.1D.1/23. 在一个具有 n 个顶点的无向图中，若具有e 条边，则所有顶点的度数之为D( ) 。A.n B.eC.n+eD.2e三、简答题.1. 给出如下图所示的无向图 G的邻接矩阵存储结构。 （答案略）2. 画出下图的邻接表存储结构。（答案略）.3. 给出下图从 A 点出发的深度优先遍历和广度优先遍历的顶点序列。解：深度优先遍历： AECDB广度优先遍历： AEBDC.5. 给出从 V1 点出发的深度优先遍历和广度优先遍历的顶点序列。解：深度优先遍历 ;v1 v2 v3 v4 v5 v6 v7 v8 v9 广度优先遍历 ;v1 v2 v3 v4 v7 v5

29、 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. 求出下图的最小生成树。4. 求出下图的最小生成树。（答案略）（答案略）.查找一、简答题1. 关键字集合 19 ， 01，23， 14，55， 68，11， 82，36 ，哈希函数为：