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. 对顺序存储的线性表（ai,臣,）进行插入操作的时间复杂度是C 。 A.0（ n）B. 0（ n-i）C. （n/2）D. 0（ n-1） 6. 链表不具有的特点是丄。 A.可随机访问任一元素B.插入和删除时不需要移动元素 C.不必事先估计存储空间D.所需空间与线性表的长度成正比 7. 线性链表中各链结点之间的地址 _C_ 。 A.必须连续B.部分地址必须连续 8. 以下关于链式存储结构的叙述中，C 是不正确的。

3、 A. 结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构 B. 逻辑上相邻的结点物理上不必邻接 C. 可以通过计算直接确定第i个结点的存储地址 D. 插入、删除操作方便，不必移动结点 9. 设依次进入一个栈的元素序列为 d, a, c, b得不到出栈的元素序列为_D。 A. dcbaB. acdbC. abcdD.cbda 10. 将新元素插入到链式队列中时，新元素只能插入到B 。 A.链头B.链尾C.链中 D. 第i个位置，i大于等于1,大于等于表长加1 11. 设栈S和队列Q的初始状态为空，元素el、e2、e3、e4、e5和e6依次通过栈S, 个元素出栈后即进入队列 Q,若6个元

4、素出队的顺序是e2、e4、e3、e6、e5、和e1， 则栈S容量至少应该是C 。 A. 6B. 4C. 3D. 2 12. 下面D 是 abcd321ABCD的子串。 A. abcdB. 321abC. abc ABCD. 21AB 13. 假设8行10列的二维数组A18, 110分别以行序为主序和以列序为主序顺序存 储时，其首地址相同，那么以行序为主序时元素a3, 5的地址与以列序为主序时C 元素相同。 A. a7 , 3B. a8, 3C. a1, 4D. ABC 都不对 14. 数组A05,0-6的每个元素占5个字节，将其按列优先次序存储在起始地址为1000 的内存单元中，则元素A5 ,

5、 5的地址为A 。 A. 1175B. 1180C. 1205D.1210 15. 下列广义表中，长度为3的广义表为B_。 A. (a,b,c,( )B. (g),(a,b,c,d,f),( ) C. (a,(b,(d)D.() 16. 以下关于广义表的叙述中，正确的是一A_。 A.广义表是0个或多个单元素或子表组成的有限序列 B. 广义表至少有一个元素是子表 C. 广义表不可以是自身的子表 D. 广义表不能为空表 17若树T有a个度为1的结点，b个度为2的结点，c个度为3的结点，则该树有 D 个 叶结点。 A.1+2b+3cB.a+2b+3cC.2b+3cD.1+b+2c 18. 若一棵二叉

6、树有102片叶子结点，则度二叉树度为 2的结点数是 B 。 A. 100B. 101C. 102D. 103 19. 在有n个叶子结点的霍夫曼树中，其结点总数为： 。 A. nB. 2nC. 2n +1D. 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 o A. x是y的左兄弟B. x是y的右兄弟 C. x是y的祖先D. x是y的后代 22. 先序遍历序列与中序遍历序列相同的二叉树为

7、 o A.根结点无左子树的二叉树B.根结点无右子树的二叉树 C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树 D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树 23. 若二叉树T的前序遍历序列和中序遍历序列分别是bdcaef和cdeabf,则其后序遍历序 列为 A o A. ceadfbB. feacdbC. eacdfbD.以上都不对 24. 设无向图的顶点个数为n,则该图最多有 条边。 A. n-1B. n(n-1)C. n(n-1)/2D. n 25. 对于一个有n个顶点和e条边的无向图，若采用邻接表表示，邻接表中的结点总数是 Co A. e/2 B. e C.n+2e D.

8、 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) 对该图进行深度优先遍历，下面不能得到的序列是D 。 29.对有n个记录的表作快速排序，在最坏情况，算法的时间复杂度是 C. O( nl og2 n)D. O(n2) B.快速排序法 D.堆排序法 A. acfdebB. aebdfc 27. 在下述排序方法中，不属于内排序方法的是 A.插入排序法B.选择排序法 28. 直接插入排序在最好情况下的时间复杂度为 A. O(log2 n)B. 0(n) A. 0( n当线性表的元

9、素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取 线性表中的元素时，应采用 存储结构。 两个字符串相等的充分必要条件是长度相等且对应位置上的字符相等。 字符串“ abed中共有 个长度大于0的字串。 6. 广义表 list= (5，(3，2，(14, 9, 3)，()，4)，2, (6, 3，10)的长度及深度分别 为和。 7. 若二叉树的先序序列和后序序列相反，则该二叉树一定满足只有一个叶子结点 )B. 0(n) 30.下面的排序算法中，稳定是A 。 A.直接插入排序法 C.直接选择排序法 ， 填空题 C. aedfcbD. abecdf C 。 C.拓扑排序法D.归并排序法

10、 B 。 C. O(nl og2n)D. O( n一个算法具有 5 个特性： 、有零个或多个输入, 一个或多个输出。 2.设数组a150 180的基地址为2000,每个元素占2个存储单元，若以行序为主序 顺序存储，则元素a45, 68的存储地址为 9174;若以列序为主序顺序存储，则 元素a45，68的存储地址为 8788。 ) D_。 2 8若无向图满足有n-1条边的连通图，则该图是树。 9若无向图中有n个顶点，则其边数最少为n-1，最多为n（n-1）/2 10堆排序的时间复杂度和空间复杂度分别为O（nlog2n）和 0（1）。 三、名词解释 （1）抽象数据类型（2）算法及其特性（3）串的模

11、式匹配 （4）优先级队列 （5）完全二叉树（6）堆（7） Huffman 编码（8） Huffman 树 （9）连通分量及重连通分量（10）最小生成树（11）克鲁斯卡尔算法 （12）普里姆算法（13）希尔排序（14）快速排序 （15）教材等等相关名次解释题 四、简答题 1请对线性表进行顺序存储和链式存储的特点作比较。（西电2004年考研试题） 2. 单链表为什么要引入头结点？ 3. 线性表的链式存储结构有单链表、循环链表、双向链表，试问它们各有什么优点和缺点？ 参考答案： 单链表的优点是空间动态分配，插入和删除时不需要移动数据，缺点是不 能随机访问数据。和其它两种相比，它还节省了空间。 循环链

12、表除了具有单链表的优点外，它从任意结点出发可以找到其它结 点。缺点同单链表的缺点。 双向链表除了具有循环链表的优点，它还可以方便地找到某个结点的前 驱。缺点是增加了空间开销。 4. 内存中一片连续空间（不妨假设地址从1到m），提供给两个栈使用，怎样分配这部分 存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。 5. 假设有一个适当大小的栈S,输入栈的序列为A，B，C，D，E。 问：（1）能否得到下列的输出序列：B，C, D, E, A;E，A，B，C, D; E, D, C, B, Ao （2）写出所有可能正确的输出序列（至少 5种）。 6. 用向量表示的循环队列的队首和队尾位置分别为

13、1和max_size,试给出判断队列为空和 为满的边界条件。 参考答案： 队空条件为max_size=1; 队满的条件为（max_size+1） %MAXSIZE. 7. 设一棵二叉树后序遍历序列为 DGJHEBIFCA，中序遍历序列为DBGEHJACIF，要求: （2）写出该二叉树的先序遍历序列； （3）画出该二叉树对应的森林。 8. 对二叉树中的结点按层次顺序（每一层自左向右）进行的访问操作称为二叉树的层次遍 历。现已知一棵二叉树的层次序列为 AEBGFDIMH，中序遍历序列为GEFAMDBHI。 请画出该二叉树并写出其先序序列。若将该二叉树看作是一个森林的孩子一兄弟表 示，请画出该森林。

14、（西电2004年考研试题） 9. 已知某通信电文仅由A、B、C、D、E、F这6个字符构成，其出现的频率分别为 23、 5、14、8、25、7,请给出它们的霍夫曼树及其对应的霍夫曼编码。 10给定下列图G用两种不同表示法画出该图的存储结构图。 11. 针对上图分别用卡鲁斯卡尔及普里姆算法给出该图的最小生成树，画出其逻辑结构。 12. 总结直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序、 锦标赛排序、堆排序及归并排序等在最好情况下、 最坏情况及平均的时间复杂度，辅助 空间复杂度及稳定性。 13. 判断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整为堆。 （1）10

15、0，90，80，60，85，75，20，25，10，70，65，50 （2）100，70，50，20，90，75，60，25，10，85，65，80 14. 已知一序列（12, 70，33, 65, 24，56, 48, 92，86, 33），问该序列是否是堆？如果 不是，则把它调整为小顶堆。并问把该序列调整为堆共需要多少次元素间的比较？多少 次元素间的交换。（西电2005年考研试题） 15.试为下列情况选择合适的排序算法：（西电2006年考研试题） (2) n=30,且要求既要快，又要排序稳定； (3) n=2000,要求平均情况下速度最快； (4) n=2000,要求最坏情况下速度最快，又

16、要节省存储空间。 五、算法设计题 1. 实现一个算法，完成在不带表头结点的单链表第i个结点之前插入新元素x的操作。 (教材P74页) 2. ( a)实现一个函数，完成在带表头结点的双向循环链表中，建立一个包含有值value 的新结点并将其插入到当前结点之后。(教材P91页) (b)实现一个函数，完成在带表头结点的双向循环链表中删除当前结点，同时让当前 指针指到链表中下一个结点位置。(教材P91页) 3. (a)实现一个函数完成删除链式栈顶结点，返回被删栈顶元素的值。(教材P107页) (b)实现一个函数完成删除链式队列队头结点，并返回被删对头元素的值。(教材P117 页) 4. 对二叉链表，实

17、现一个函数Pare nt(*Bi nTreeNode*start, *BinTreeNode*curent)从结点start开始，搜索结点current的双亲结点，并返回 其地址，否则返回NULL。(教材P171页) 5. 若用二叉链表作为二叉树的存储表示，试针对下列问题编写递归算法： (1) 统计二叉树中叶子结点的个数； (2) 交换每个结点的左子女和右子女。 6熟练掌握直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序等其它排序的 算法 7若以域变量rear和length分别指示循环队列中队尾元素的位置和队列中元素的个数。请 完成下面的入队列和出队列的算法：(西电2004年考研试题)

18、 #define MAXQSIZE 100 最大队列长度 Type struct Qelemtype *base; /base为队列所在区域的首地址 int len gth;/队列长度 int rear; /队尾元素位置 SqQueue; if () return ERROR; /队列满，无法插入 Q.rear; /计算元素 e的插入位置 = e; 在队尾加入新的元素 Q.le ngth+;/队列长度加1 return OK; Status DeQueue(SqQueue 队列满 e=Q.base ;/取队头元素 Q. length -;/队列长度减1 return OK; 8. 请运用快速排

19、序思想，设计递归算法实现求n (n1)个不同元素集合中的第i (Ki 0 10. 假设以数组seq0m-1存放循环队列中的元素，同时设变量rear和quelen分别指示 循环队列中的队尾元素的位置和内含元素的个数。(西电2006年考研试题) 请给出： (1) 给出循环队列的队满条件和队空条件； (2) 写出相应的入队列和出队列的算法，并分别分析其时间代价; Whe n you are old and grey and full of sleep, And no ddi ng by the fire, take dow n this book, And slowly read, and drea

20、m of the soft look Your eyes had once, and of their shadows deep; How many loved your mome nts of glad grace, And loved your beauty with love false or true, But one man loved the pilgrim soul in you. And loved the sorrows of your cha nging face; And bending dow n beside the glow ing bars, Murmur, a

21、little sadly, how love fled And paced upon the mountains overhead And hid his face amid a crowd of stars. The furthest dista nee in the world Is not betwee n life and death But whe n I sta nd in front of you Yet you dont know that I love you. The furthest dista nee in the world Is not whe n I sta nd

22、 in front of you Yet you cant see my love But whe n un doubtedly knowing the love from both Yet cannot be together. The furthest dista nee in the world Is not being apart while being in love But whe n I pla inly cannot resist the year ning Yet prete nding you have n ever bee n in my heart. The furthest dista nee in the world Is not struggli ng aga i