2022年haerb大学数据结构期末复习题

1、学习必备欢迎下载数据结构复习题（含部分参考答案版）一、单杜鳌项选择题1. 按照数据逻辑结构的不同，可以将数据结构分成c 。a. 动态结构和静态结构b. 紧凑结构和非紧凑结构c. 线性结构和非线性结构d. 内部结构和外部结构2. 下列关于数据结构的叙述中正确的是a 。a. 数组是同类型值的集合b. 递归算法的程序结构比迭代算法的程序结构更为复杂c. 树是一种线性的数据结构d. 用一维数组存储二叉树，总是以先序顺序遍历各结点3. 在计算机的存储器中表示时，物理地址与逻辑地址相同并且是连续的，称之为b a.逻辑结构b.顺序存储结构c.链式存储结构d.以上都不对4. 以下关于算法特性的描述中，b 是正

2、确的。（1）算法至少有一个输入和一个输出（2）算法至少有一个输出但是可以没有输入（3）算法可以永远运行下去a. （1）b. （2）c. （3）d. （2）和（ 3）5. 对顺序存储的线性表（ a1,a2,an）进行插入操作的时间复杂度是c 。a.o(n) b. o(n-i) c. (n/2) d. o(n-1) 6. 链表不具有的特点是a 。a.可随机访问任一元素b.插入和删除时不需要移动元素c.不必事先估计存储空间d.所需空间与线性表的长度成正比7.线性链表中各链结点之间的地址c 。a.必须连续b.部分地址必须连续c.不一定连续d.连续与否无关精品学习资料 可选择p d f - - - -

3、- - - - - - - - - - 第 1 页，共 9 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 1 页，共 9 页 - - - - - - - - -学习必备欢迎下载8. 以下关于链式存储结构的叙述中，c 是不正确的。a.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构b.逻辑上相邻的结点物理上不必邻接c.可以通过计算直接确定第i 个结点的存储地址d.插入、删除操作方便，不必移动结点9. 设依次进入一个栈的元素序列为d, a, c, b, 得不到出栈的元素序列为d 。a. dcba b. a

4、cdb c. abcd d. cbda 10. 将新元素插入到链式队列中时，新元素只能插入到b 。a. 链头b. 链尾c. 链中d. 第 i 个位置， i 大于等于 1，大于等于表长加1 11. 设栈 s和队列 q 的初始状态为空，元素e1、e2、e3、e4、e5 和 e6依次通过栈 s，一个元素出栈后即进入队列q，若 6 个元素出队的顺序是e2、e4、e3、e6、e5、和 e1，则栈 s 容量至少应该是c 。a. 6 b. 4 c. 3 d. 2 12.下面d 是abcd321abcd的子串。a. abcd b. 321ab c. abc abcd. 21ab13.假设 8 行 10 列的二

5、维数组 a18，110分别以行序为主序和以列序为主序顺序存储时，其首地址相同，那么以行序为主序时元素a3，5的地址与以列序为主序时c 元素相同。a. a7，3 b. a8，3 c. a1，4 d. abc 都不对14. 数组 a05， 06的每个元素占 5 个字节， 将其按列优先次序存储在起始地址为1000的内存单元中，则元素a5 ，5的地址为a 。a. 1175 b. 1180 c. 1205 d.1210 15.下列广义表中，长度为3 的广义表为b 。a.（a,b,c,( )）b. (g),(a,b,c,d,f),( ) c. (a,(b,(d) d. ( ) 16. 以下关于广义表的叙述

6、中，正确的是a 。a. 广义表是 0 个或多个单元素或子表组成的有限序列b. 广义表至少有一个元素是子表c. 广义表不可以是自身的子表精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 2 页，共 9 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 2 页，共 9 页 - - - - - - - - -学习必备欢迎下载d. 广义表不能为空表17.若树 t 有 a个度为 1的结点，b 个度为 2 的结点，c 个度为 3 的结点，则该树有d 个叶结点。a. 1+2b+3c b.

7、 a+2b+3c c.2b+3c d. 1+b+2c 18.若一棵二叉树有 102片叶子结点，则度二叉树度为2 的结点数是b 。a. 100 b. 101 c. 102 d. 103 19. 在有 n 个叶子结点的霍夫曼树中，其结点总数为：。a. n b. 2n c. 2n +1 d. 2n - 1 20.具有 12个结点的完全二叉树有b 。a. 5 个叶子结点b. 5 个度为 2 的结点c. 7 个分支结点d. 2 个度为 1 的结点21.设结点 x 和 y 是二叉树中的任意两结点， 若在先根序列中 x 在 y 之前，而后根序列中 x在 y 之后，则 x 和 y 的关系是c 。a. x 是

8、y 的左兄弟b. x 是 y 的右兄弟c. x 是 y 的祖先d. x 是 y 的后代22. 先序遍历序列与中序遍历序列相同的二叉树为。a. 根结点无左子树的二叉树b.根结点无右子树的二叉树c. 只有根结点的二叉树或非叶子结点只有左子树的二叉树d. 只有根结点的二叉树或非叶子结点只有右子树的二叉树23.若二叉树 t 的前序遍历序列和中序遍历序列分别是bdcaef和 cdeabf，则其后序遍历序列为a 。a. ceadfb b. feacdb c. eacdfb d. 以上都不对24.设无向图的顶点个数为n，则该图最多有c 条边。a. n-1 b. n(n-1) c. n(n-1)/2 d. n

9、 25.对于一个有n 个顶点和 e 条边的无向图，若采用邻接表表示，邻接表中的结点总数是c 。a. e/2 b. e c. n+2e d. n+e 26. 无向图 g=（v，e） ，其中 v=a,b,c,d,e,f,e=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d) 。精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 3 页，共 9 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 3 页，共 9 页 - - - - - - - - -学

10、习必备欢迎下载对该图进行深度优先遍历，下面不能得到的序列是d 。a. acfdeb b. aebdfc c. aedfcb d. abecdf 27.在下述排序方法中，不属于内排序方法的是c 。a. 插入排序法b. 选择排序法c. 拓扑排序法d. 归并排序法28. 直接插入排序在最好情况下的时间复杂度为b 。a. o(log2n) b. o(n) c. o(nlog2n) d. o(n2) 29.对有 n 个记录的表作快速排序，在最坏情况，算法的时间复杂度是d 。a. o(n3) b. o(n) c. o(nlog2n) d. o(n2) 30.下面的排序算法中，稳定是a 。a. 直接插入排序

11、法b. 快速排序法c. 直接选择排序法d. 堆排序法二、填空题1. 一个算法具有 5 个特性：、有零个或多个输入，一个或多个输出。2. .设数组 a1 50 ，180的基地址为 2000，每个元素占 2 个存储单元，若以行序为主序顺序存储，则元素a45，68的存储地址为9174 ；若以列序为主序顺序存储，则元素 a45，68的存储地址为8788 。3. 当线性表的元素总数基本稳定， 且很少进行插入和删除操作， 但要求以最快的速度存取线性表中的元素时，应采用存储结构。4.两个字符串相等的充分必要条件是长度相等且对应位置上的字符相等。5. 字符串“ abcd ”中共有个长度大于 0 的字串。6.

12、广义表 list=（5， （3，2， （14，9，3） ， （） ，4） ，2， （6，3，10） ）的长度及深度分别为和。7.若二叉树的先序序列和后序序列相反，则该二叉树一定满足只有一个叶子结点。8.若无向图满足有 n-1 条边的连通图，则该图是树。9.若无向图中有 n 个顶点，则其边数最少为n-1 ，最多为n(n-1)/2 。10.堆排序的时间复杂度和空间复杂度分别为o(nlog2n) 和o(1) 。精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 4 页，共 9 页 - - - - - - - - -精品学习资料 可选择p d f - - - -

13、 - - - - - - - - - - 第 4 页，共 9 页 - - - - - - - - -学习必备欢迎下载三、 名词解释（1）抽象数据类型（2）算法及其特性（3）串的模式匹配（4）优先级队列（5）完全二叉树（6）堆（ 7）huffman 编码（ 8）huffman 树（9）连通分量及重连通分量（10）最小生成树（ 11）克鲁斯卡尔算法（12）普里姆算法（ 13）希尔排序（ 14）快速排序（15）教材等等相关名次解释题四、简答题1. 请对线性表进行顺序存储和链式存储的特点作比较。（西电 2004年考研试题）2. 单链表为什么要引入头结点？3.线性表的链式存储结构有单链表、 循环链表、双

14、向链表，试问它们各有什么优点和缺点？参考答案：单链表的优点是空间动态分配，插入和删除时不需要移动数据，缺点是不能随机访问数据。和其它两种相比，它还节省了空间。循环链表除了具有单链表的优点外，它从任意结点出发可以找到其它结点。缺点同单链表的缺点。双向链表除了具有循环链表的优点，它还可以方便地找到某个结点的前驱。缺点是增加了空间开销。4.内存中一片连续空间（不妨假设地址从1 到 m） ，提供给两个栈使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。5. 假设有一个适当大小的栈s，输入栈的序列为a，b，c，d，e。问： （1）能否得到下列的输出序列： b，c，d，e，a；

15、 e，a，b，c，d；e，d，c ，b，a。（2）写出所有可能正确的输出序列（至少5 种） 。6.用向量表示的循环队列的队首和队尾位置分别为1 和 max_size， 试给出判断队列为空和为满的边界条件。参考答案：队空条件为 max_size=1; 队满的条件为（ max_size+1）%maxsize. 7. 设一棵二叉树后序遍历序列为dgjhebifca ，中序遍历序列为dbgehjacif ，要求：（1）画出该二叉树；（2）写出该二叉树的先序遍历序列；（3）画出该二叉树对应的森林。8.对二叉树中的结点按层次顺序（每一层自左向右）进行的访问操作称为二叉树的层次遍历。现已知一棵二叉树的层次序

16、列为aebgfdimh ，中序遍历序列为gefamdbhi 。精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 5 页，共 9 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 5 页，共 9 页 - - - - - - - - -学习必备欢迎下载请画出该二叉树并写出其先序序列。若将该二叉树看作是一个森林的孩子 兄弟表示，请画出该森林。（西电 2004 年考研试题）9. 已知某通信电文仅由a、b、c、d、e、f 这 6 个字符构成，其出现的频率分别为23、5、14、8、25

17、、7，请给出它们的霍夫曼树及其对应的霍夫曼编码。10.给定下列图 g 用两种不同表示法画出该图的存储结构图。11. 针对上图分别用卡鲁斯卡尔及普里姆算法给出该图的最小生成树，画出其逻辑结构。12.总结直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序、锦标赛排序、 堆排序及归并排序等在最好情况下、最坏情况及平均的时间复杂度，辅助空间复杂度及稳定性。13.判断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整为堆。（1）100，90，80，60，85，75，20，25，10，70，65，50 （2）100，70，50，20，90，75，60，25，10，85，65，80

18、 14.已知一序列（ 12，70，33，65，24，56，48，92，86，33） ，问该序列是否是堆？如果不是，则把它调整为小顶堆。 并问把该序列调整为堆共需要多少次元素间的比较？多少次元素间的交换。（西电 2005 年考研试题）15.试为下列情况选择合适的排序算法： （西电 2006年考研试题）（1）n=30，且要求最坏情况下速度最快；（2）n=30，且要求既要快，又要排序稳定；（3）n=2000，要求平均情况下速度最快；（4）n=2000，要求最坏情况下速度最快，又要节省存储空间。五、 算法设计题a b g f e d c 4 8 124 20 12 15 10 精品学习资料 可选择p

19、d f - - - - - - - - - - - - - - 第 6 页，共 9 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 6 页，共 9 页 - - - - - - - - -学习必备欢迎下载1. 实现一个算法，完成在不带表头结点的单链表第i 个结点之前插入新元素x 的操作。（教材 p74 页）2.（a）实现一个函数，完成在带表头结点的双向循环链表中，建立一个包含有值value的新结点并将其插入到当前结点之后。 （教材 p91 页）（b）实现一个函数，完成在带表头结点的双向循环链表中删除当前结点，同时让

20、当前指针指到链表中下一个结点位置。 （教材 p91页）3.（a）实现一个函数完成删除链式栈顶结点，返回被删栈顶元素的值。（教材 p107页）（b）实现一个函数完成删除链式队列队头结点，并返回被删对头元素的值。（教材 p117页）4.对二叉链表，实现一个函数parent(*bintreenode*start, *bintreenode*curent)从结点 start 开始，搜索结点 current的双亲结点， 并返回其地址，否则返回 null 。 （教材 p171页）5. 若用二叉链表作为二叉树的存储表示，试针对下列问题编写递归算法：（1）统计二叉树中叶子结点的个数；（2）交换每个结点的左子女

21、和右子女。6.熟练掌握直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序等其它排序的算法7.若以域变量 rear和 length 分别指示循环队列中队尾元素的位置和队列中元素的个数。请完成下面的入队列和出队列的算法： （西电 2004年考研试题）#define maxqsize 100 /最大队列长度type structqelemtype *base; /base为队列所在区域的首地址int length; /队列长度int rear; /队尾元素位置sqqueue; status enqueue(sqqueue &q, qelemtype e) if ( ) return e

22、rror; / 队列满，无法插入q.rear= ; /计算元素 e 的插入位置= e; /在队尾加入新的元素q.length+; /队列长度加 1 return ok; status dequeue(sqqueue &q, qelemtype &e) / 删除对头元素，并用e带回其值精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 7 页，共 9 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 7 页，共 9 页 - - - - - - - - -学习必备

23、欢迎下载if ( )return error; /队列满e=q.base ; /取队头元素qlength -; /队列长度减 1 return ok; 8.请运用快速排序思想，设计递归算法实现求n（n1）个不同元素集合中的第i（1in）小元素。（西电 2004 年考研试题）9.阅读下列函数说明及相应代码，在空白处填入相应语句。(西电 2005年考研试题 ) 函数 1 函数 palinddrome(char s)的功能是：判断字符串s 是否为回文字符串，若是，则返回0， 否则返回 -1。 若一个字符串顺读和倒读都一样时， 称该字符串是回文字符串， 例如：“level ”是回文字符串，而“ leval”不是。int palindrome (char s) char *pi, *pj; pi = s; pj =s + strlen(s) 1; /*strlen(s)函数用于求得串s的串长while（pip