数据结构考试习题库

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 时n），需向前移动 (n-i )个元素。2.从循环队列中删除一个元素时，其操作是(先移动队首指针，后取出元素 )。3.在线性表的单链接存储中，若一个元素所在结点的地址为p ，则其后继结点的地址为(p-next)。4.在一个单链表中指针p 所指向结点的后面插入一个指针q 所指向的结点时，首先把 (p-nex

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

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

6、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)=() ， t

7、ail( 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-link; p-link=s; b.p-link=s; s-link=q;c.p-link=s-li

8、nk; 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)modn d.(n+r-f)modn3.如下陈述中正确的是 (a )。a.串是一种特殊的线性表b.串的长度必须大于零c.串中元素只能是字母d.空串就是空白串4.若让元素1， 2， 3 依次进栈，则出栈次序不可能出现(c)的情况。a.3 ， 2， 1b.2 ， 1， 3c.3 ，1， 2 d.1 ， 3，25.判定一个队列qu （最多元素为m0 ）为空的条件是(c)

9、。a.qu-rear-qu-front=m0b.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)后的串t 值为 ( d )。a. bcdef

10、 b. bcdefg c. bcpqrst d. bcdefef 8.一个顺序线性表第一个元素的存储地址是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 的线性表中，删除值为x 的元素

11、时，需要比较元素和移动元素的总次数为(c)。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 串的连接串，函数 s

12、trsub(s ， i， j)返回串 s 的从序号 i 的字符开始 的 j 个 字 符 组 成 的 子 串 ， strlen(s) 返 回 串 s 的 长 度 ， 则 strcat(strsub(s1 ， 2，strlen(s2) ，strsub(s1 ， strlen (s2) ， 2) 的结果串是 (d )。a.bcdefb.bcdefgc.bcpqrstd.bcdefef16. 学生成绩表是一种 (c)结构。a.图形b.树形c.线性d.集合17. 在一个链队中，假设f 和 r 分别为队首和队尾指针，则插入s 所指结点的运算时 (c)。a.f-next=s;f=s;b.r-next=s;r

13、=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

14、;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-ne

15、xt=s;s-next=null;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

16、.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 字节，按行优先顺序存储，基地址为100 ，则元素 a1825的存储

17、地址为 (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.若一棵二

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

19、层上至多有 (2 n -1 )个结点。11. 深度为 6（设根的层数为 1）的二叉树至少有 (6 )个结点，至多有 (63 )个结点，第 4 层上至多有 (8) 个结点。;.a.nb. n+1c.n-1d. 不确定注： 1:b2:d3:a4:b5.下面 (a )是对的。a.哈夫曼树中结点的度只可能是0 和 2。 b.二叉树的顺序存储中，是以先序遍历存储结点的。c.完全二叉树实际上就是满二叉树。d. 一棵二叉树第i 层的最大结点数为2i-1 。6.将含 100 个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为 1。编号为 49 的结点 x 的右孩子编号为 (b)。a

20、.98b.99 c.24d. 无法确定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.48d.53;.10. 一个具有 767 个结点的完全二叉树， 其叶子结点个数为 (b)。a.382b.384c.385d.38611. 在一棵具有 35 个结点的完全二叉树中，该树的深度为 (a )。

21、a.6b.7c.5d.812. 由三个结点构成的二叉树，共有 (b )种不同的结构。a.3b.4c.5d.613. 深度为 k 的二叉树至多有(2 k-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. 已 知 某 二 叉 树 的 前 序 序 列 为 e

22、badcfhgi ， 中 序 序 列 为 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 ，

23、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,

24、35中序序列： 5,8,10,15,18,20,30,35,46后序序列： 5,10,18,15,8,35,30,46,207.将如下图的一般树转化为二叉树。;.8.将下图中的二叉树转换成森林。aebcfhgklji;.四、论述题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 个顶点的无向图，边的总数最多为

25、(45 )。3.图的广度优先搜索遍历类似于树的(按层次 )遍历的过程。4.在无向图g 的邻接矩阵a 中，若 aij 等于 1，则 aji 等于 (1 )。5.图的 (深度 )优先搜索遍历算法是一种递归算法，图的(广度 ) 优先搜索遍历算法需要使用队列二、选择题1.一个有 n 个顶点的无向图最多有c( )条边。a.n b.n(n-1)c.n(n-1)/2d.2n;.2. 在一个无向图中， 所有顶点的度数之和等于所有边数的(b)倍。a.3b.2c.1d.1/23.在一个具有 n 个顶点的无向图中，若具有 e 条边，则所有顶点的度数之为 (d ) 。 a.n b.e c.n+e d.2e三、简答题1

26、.给出如下图所示的无向图g 的邻接矩阵存储结构。（答案略）2.画出下图的邻接表存储结构。（答案略）;.3.给出下图从a 点出发的深度优先遍历和广度优先遍历的顶点序列。解：深度优先遍历： aecdb广度优先遍历： aebdc;.5.给出从 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

27、(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 ，哈希函数为：h(key)=keymod 9构建哈希表，采用开放定址法解决冲突。（答案略）2.关键字集合 19 ， 14 ，23 ， 01 ， 68 ， 20 ，84 ，27 ， 55 ， 11 ，10 ， 79 ，哈希函数为：h(key)=key mod12 构建哈希表，采用开放定址法解决冲突。（答案略）;.排序一、填空题1.