数据结构考试题库

绪论一、填空题1. 数据的逻辑结构被分为集合、 ( 线性结构 ) 、( 树形结构 ) 和( 图状结构 ) 四种。2. 物理结构是数据结构在计算机中的表示，又称为( 存储结构 ) 。3. 数据元素的逻辑结构包括 ( 线性 ) 、 ( 树) 和图状结构 3 种类 型，树形结构和图状结构合称为( 非线性结构 ) 。4.( 数据元素 ) 是数据的基本单位， ( 数据项 ) 是数据不可分割的最小单位。5. 线性结构中元素之间存在 ( 一个对一个 ) 关系，树形结构中元素之间 存在 ( 一个对多个 ) 关系，图状结构中元素之间存在 ( 多个对多个 ) 关系。？ 6. 数据结构是一门研究非数值计算的程序设计问题中：计算机的( 数据元素 ) 以及它们之间的( 关系 ) 和( 运筹 ) 等的学科。7. 算法的五个重要特性为有穷性、确定性、( 输入 ) 、 ( 输出 ) 和 ( 可行性)。二、选择题1. 数据的不可分割的基本单位是 ( D) 。 A. 元素 B. 结点 C. 数据类型 D. 数据项*2. 线性表的逻辑顺序与存储顺序总是一致的，这种说法( B) 。A. 正确B. 不正确C. 不确定D. 无法选择3. 线性结构是指数据元素之间存在一种( D) 。A. 一对多关系B. 多对多关系C. 多对一关系D. 一对一关系4. 在数据结构中，从逻辑上可以把数据结构分成( A) 。5. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址( D)。A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续不连续都可以三、简答题1. 算法的特性是什么。答：有穷性确定性可行性有 0 或多个输入有 1 或多个输出线性结构一、填空题1. 在一个长度为n 的线性表中删除第i 个元素（1in）时，需向前移动 ( n-i ) 个元素。2. 从循环队列中删除一个元素时，其操作是( 先移动队首指针，后取出元素 ) 。3.在线性表的单链接存储中，若一个元素所在结点的地址为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(-) ；进栈操作时要执行的语句序列中有+S-top() 。9. 顺序表中逻辑上相邻元素的物理位置 ( 一定 ) 紧邻；单链表中 逻辑上相邻元素的物理位置 ( 不一定 ) 紧邻。10. 在 ( 循环 ) 链表中，从任何一结点出发都能访问到表中的所有结点。11. 栈和队列均是 ( 运算受限 ) 的线性表，栈的特点是 ( 先进后出 后进先出) ；队列的特点是 ( 先进先出 后进后出 ) 。12. 通常，在程序中使用的串可分为串常量和串变量；而串按存储方式又可分为 ( 定长顺序存储 ) 和 ( 堆分配存储 ) 。13. 循环队列头指针 front 指向队头元素，队尾指针 rear 指向队 尾元素后的一个空闲元素，队列的最大空间为Queuelen 。在循环队列中，队空标志为 (front=rear) ， 队满标志为（rear+1 ）%max=front) 。(当 rear=front时，队列长度为 ( rear-front) ，当 rearnext=null) 。17. 在一个单链表中删除指针p 所指向结点的后继结点时，需要把( p-next-next) 值赋给 p-next指针域。18. 一个顺序循环队列存于aM 中，假定队首和队尾指针分别为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.若S=(a，)， Tail( S)=(b(为空)。，c)，e ，)， Head(Tail( Sd)，)=(则Head( 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. 对于顺序存储的队列，存储空间大小为n，头指针为 F，尾指针为 R。若在逻辑上看一个环，则队列中元素的个数(A。)A.R-F B.n+R-F C.(R-F+1)mod nD.(n+R-F)mod n3. 如下陈述中正确的是 ( A) 。A. 串是一种特殊的线性表B. 串的长度必须大于零C.串中元素只能是字母D. 空串就是空白串4. 若让元素 1，2， 3 依次进栈，则出栈次序不可能出现()C的情况。A.3 ，2，1B.2 ，1，3 C.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+16. 设目标串 S=abcdef ，模式串 p=de，则第 ( C) 次匹配成功。A.1B.2C.4D.57. 设字符串s1=ABCDEFG， S2=PQRST，T， sub1， sub2 为空串。则 运 算s=Concat(T，SubString(sub1，s1，2，SubLength(s2)， SubString(sub2，s1 ， SubLength(s2) ， 2)后的串TD值为( )。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=head10. 在一个链队中，假设 f 和 r 分别为队首和队尾指针，则删除一个结点的运算时( C) 。A.r=f-next;B.r=r-next;C.f=f-next;D.f=r-next;11. 在一个长度为n 的线性表中，删除值为素和移动元素的总次数为C) 。x 的元素时，需要比较元A.(n+1)/2B.n/2C.nD.n+112. 在一个单链表中，若要在 p 所指向的结点之后插入一个新结 点，则需要相继修改 ( B) 个指针域的值。A.1B.2C.3D.413. 线性结构中，每个结点 ( C) 。A. 无直接前驱B.只有一个直接前驱和个数不受限制的直接后继C.只有一个直接前驱和后继 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.BCDEFB.BCDEFGC.BCPQRST D.BCDEFEF16. 学生成绩表是一种 ( C) 结构。A. 图形B. 树形17. 在一个链队中，假设C. 线性D.集合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.il-length+1B.i=1C.i=l-length+1D.1=ilength+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.edcbaB.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!=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. 向顺序栈中压入新元素时，应当( A) 。A. 先移动栈顶指针，再存入元素B.先存入元素，再移动栈顶指针C.先后次序无关紧要D.同时进行25. 假定一个顺序队列的队首和队尾指针分别为f 和 r ，则判断队空的条件为(D)。f+1=rB.r+1=fC.f=0D.f=r26. 栈的插入和删除操作在 ( A) 进行。A. 栈顶 B. 栈底C. 任意位置 D. 指定位置27.栈和队列的共同点是 ( ) 。A. 都是先进后出CB. 都是先进先出C.只允许在端点处插入和删除元素D. 没有共同点28.若 6 行 8 列的数组以列序为主序顺序存储，基地址为1000， 每个元素占2 个存储单元，则第5 行第 3 列的元素 ( 假定无第0行第 0列)的地B址是( )。A.1086 B.1032C.1068D. 答案 A，B， C 都不对29.设有 50 行的二维数组 A5060 ，其元素长度为2 字节，按 行优先顺序存储，基地址为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. 一棵高度为 5 的二叉树中最少含有 ( 5) 个结点，最多含 有( 31) 个结点。4. 若一棵二叉树中有 8 个度为 2 的结点，则它有 ( 9) 个叶子。5. 一棵深度为 6 的满二叉树有 ( 31) 个非终端结点。6. 树中结点 A 的 ( 子树数 ) 称为结点 A 的度。7. 对一棵二叉排序树进行中序遍历时，得到的结点序列是一个(升序序列)。8.在树型结构中，根结点没有前驱结点，其余每个结点有且仅有个前驱结点；叶子结点( 没有 ) 后继结点，其余每个结点都可以有( 一)一或多个 ) 个后继结点。9. 在最优二叉树中没有度为1 的结点，则一棵有n 个叶子结点的最优二叉树中共有 ( 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. 将含 100 个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为 1。编号为 49 的结点 X 的右孩子编号为 ( B) 。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. 一个具有 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 ， 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+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) 中元素的排 列次序，将所有元素插入一棵初始为空的二叉排序树中，使之 仍是一棵二叉排序树。(1) 试画出插入完成之后的二叉排序树； (2) 若查找元素 2，它将依次与二叉排序树中哪些元素比较大小 ? (3) 对该树进行中序遍历，试写出中序遍历序列。解： (1) 略(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,207. 将如下图的一般树转化为二叉树。8. 将下图中的二叉树转换成森林。BAEGKCFHILJ四、论述题1. 由分别带权为 3，12， 9，2， 5， 7 的叶子结点构造一棵哈夫曼树，并计算该树的带权路径长度。解: 带权路径长度为 :91图状结构一、填空题1. 若一个图的顶点集为a， b，c，d，e，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. 在一个无向图中， 所有顶点的度数之和等于所有边数的( B) 倍。A.3B.2C.1D.1/23. 在一个具有 n 个顶点的无向图中，若具有e 条边，则所有顶点的度数之为D( ) 。A.n B.eC.n+eD.2e三、简答题1. 给出如下图所示的无向图 G的邻接矩阵存储结构。 （答案略）2. 画出下图的邻接表存储结构。（答案略）3. 给出下图从 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 到不能得到 14231432的过程为：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，哈希函数为：H(key)=key MOD9构建哈希表，采用开放定址法解决冲突。（答案略）2. 关键字集合 19 ， 14，23， 01，68， 20，84， 27，55， 11，10，79 ，哈希函数为：H(key)=keyMOD 12 构建哈希表，采用开放定址法解决冲突。（答案略）排序一、填空题1. 快速排序的最坏情况，其待排序的初始排列是(逆序)。2. 假定一组记录的排序码为80， 36，40， 75， 66， 84， 24)(46 ， 79， 56， 38， 40，对其进行归并排序的过程中，第3趟归并后，结果为( 36,38,40,40,46,56,79,8024,66,75,84) 。二、选择题1. 用某种排序方法对关键字序列(25 ， 84， 21， 47，15， 27，68， 35，20) 进行排序时，序列的变化情况如下：20，15， 21，25， 47，27， 68，35， 8415，20， 21，25， 35，27， 47，68， 8415，20， 21，25， 27，35， 47，68， 84则所采用的排序方法是(D)。A. 选择排序B. 希尔排序 C. 归并排序 D. 快速排序三、简答题1. 已知一组记录的排序码为（46， 79 ， 56， 52， 38，40， 80，31， 95，24），写出对其进行快速排序的每一趟划分结果。解：过程如下：一趟： 24,31,40,38,46,52,80,56,75,79二趟： 24,31,40,38,46,52,80,56,95,79三趟：24,31,40,38,46,52,79,56,80,95四趟：24,31,38,40,46,52,56,79,80,952. 一组记录的关键码为（ 46，79， 56，38， 40，84），利用希尔排序方法进行排序。解：如下所示一趟： 38,40,56,46,79,84二趟： 38,40,56,46,79,84三趟： 38,40,46,56,79,843. 一组记录的关键码为（ 49， 38，65， 97， 76， 13，27， 4），利用起泡法进行排序（表示绝对不会考）4. 算法的要求：(1) 正确性（ 2）可读性（ 3）健壮性（ 4）效率和低存储量要求5. 算法的特点：（ 1）有穷性（ 2）确定性（ 3）可行性（ 4）输入（ 5）输出