数据结构期末复习题答案.doc

数据结构复习题（含部分参考答案版）一、 单项选择题1. 按照数据逻辑结构的不同，可以将数据结构分成 C 。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构C. 线性结构和非线性结构 D. 内部结构和外部结构2. 下列关于数据结构的叙述中正确的是 A 。 A. 数组是同类型值的集合 B. 递归算法的程序结构比迭代算法的程序结构更为复杂 C. 树是一种线性的数据结构D. 用一维数组存储二叉树，总是以先序顺序遍历各结点 3. 在计算机的存储器中表示时，物理地址与逻辑地址相同并且是连续的，称之为 B A.逻辑结构 B.顺序存储结构C.链式存储结构 D.以上都不对4. 以下关于算法特性的描述中， B 是正确的。 （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.连续与否无关8. 以下关于链式存储结构的叙述中， C 是不正确的。 A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构B.逻辑上相邻的结点物理上不必邻接C.可以通过计算直接确定第i个结点的存储地址D.插入、删除操作方便，不必移动结点9. 设依次进入一个栈的元素序列为d, a, c, b,得不到出栈的元素序列为 D 。A. dcba B. acdb C. abcd D. cbda10. 将新元素插入到链式队列中时，新元素只能插入到 B 。A. 链头 B. 链尾 C. 链中 D. 第i个位置，i大于等于1，大于等于表长加111. 设栈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. 212.下面 D 是abcd321ABCD的子串。A. abcd B. 321ab C. abc ABC D. 21AB13.假设8行10列的二维数组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. 以下关于广义表的叙述中，正确的是 A 。 A. 广义表是0个或多个单元素或子表组成的有限序列B. 广义表至少有一个元素是子表C. 广义表不可以是自身的子表D. 广义表不能为空表17.若树T有a个度为1的结点，b个度为2的结点，c个度为3的结点，则该树有 D 个叶结点。A. 1+2b+3c B. a+2b+3c C.2b+3c D. 1+b+2c18.若一棵二叉树有102片叶子结点，则度二叉树度为2的结点数是 B 。A. 100 B. 101 C. 102 D. 103 19. 在有n 个叶子结点的霍夫曼树中，其结点总数为： 。 A. n B. 2n C. 2n +1 D. 2n - 120.具有12个结点的完全二叉树有 B 。A. 5个叶子结点 B. 5个度为2的结点C. 7个分支结点 D. 2个度为1的结点21.设结点x和y是二叉树中的任意两结点，若在先根序列中x在y之前，而后根序列中x在y之后，则x和y的关系是 C 。A. x是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 25.对于一个有n个顶点和e条边的无向图，若采用邻接表表示，邻接表中的结点总数是 C 。A. e/2 B. e C. n+2e D. n+e26. 无向图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 。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. 直接插入排序法 B. 快速排序法 C. 直接选择排序法 D. 堆排序法二、 填空题1. 一个算法具有5个特性： 、 、 、有零个或多个输入，一个或多个输出。2. .设数组a150，180的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a45，68的存储地址为 9174 ；若以列序为主序顺序存储，则元素a45，68的存储地址为 8788 。3. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 存储结构。4.两个字符串相等的充分必要条件是 长度相等且对应位置上的字符相等 。5. 字符串“abcd”中共有 个长度大于0的字串。6. 广义表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) 。三、 名词解释（1）抽象数据类型 （2）算法及其特性 （3）串的模式匹配 （4）优先级队列（5）完全二叉树 （6）堆（7）Huffman编码（8）Huffman树（9）连通分量及重连通分量（10）最小生成树（11）克鲁斯卡尔算法（12）普里姆算法（13）希尔排序（14）快速排序（15）教材等等相关名次解释题四、 简答题1. 请对线性表进行顺序存储和链式存储的特点作比较。（西电2004年考研试题）2. 单链表为什么要引入头结点？3.线性表的链式存储结构有单链表、循环链表、双向链表，试问它们各有什么优点和缺点？参考答案：l 单链表的优点是空间动态分配，插入和删除时不需要移动数据，缺点是不能随机访问数据。和其它两种相比，它还节省了空间。l 循环链表除了具有单链表的优点外，它从任意结点出发可以找到其它结点。缺点同单链表的缺点。l 双向链表除了具有循环链表的优点，它还可以方便地找到某个结点的前驱。缺点是增加了空间开销。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，A。（2）写出所有可能正确的输出序列（至少5种）。6.用向量表示的循环队列的队首和队尾位置分别为1和max_size，试给出判断队列为空和为满的边界条件。l 参考答案： 队空条件为max_size=1; 队满的条件为（max_size+1）%MAXSIZE.7. 设一棵二叉树后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，要求： （1）画出该二叉树； （2）写出该二叉树的先序遍历序列；（3）画出该二叉树对应的森林。8.对二叉树中的结点按层次顺序（每一层自左向右）进行的访问操作称为二叉树的层次遍历。现已知一棵二叉树的层次序列为AEBGFDIMH，中序遍历序列为GEFAMDBHI。请画出该二叉树并写出其先序序列。若将该二叉树看作是一个森林的孩子 兄弟表示，请画出该森林。（西电2004年考研试题）9. 已知某通信电文仅由A、B、C、D、E、F这6个字符构成，其出现的频率分别为23、5、14、8、25、7，请给出它们的霍夫曼树及其对应的霍夫曼编码。10.给定下列图G用两种不同表示法画出该图的存储结构图。ABGFEDC4812242012151011. 针对上图分别用卡鲁斯卡尔及普里姆算法给出该图的最小生成树，画出其逻辑结构。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，8014.已知一序列（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，要求最坏情况下速度最快，又要节省存储空间。五、 算法设计题1. 实现一个算法，完成在不带表头结点的单链表第i个结点之前插入新元素x的操作。 （教材P74页）2.（a）实现一个函数，完成在带表头结点的双向循环链表中，建立一个包含有值value的新结点并将其插入到当前结点之后。（教材P91页）（b）实现一个函数，完成在带表头结点的双向循环链表中删除当前结点，同时让当前指针指到链表中下一个结点位置。（教材P91页）3.（a）实现一个函数完成删除链式栈顶结点，返回被删栈顶元素的值。（教材P107页） （b）实现一个函数完成删除链式队列队头结点，并返回被删对头元素的值。（教材P117页）4.对二叉链表，实现一个函数Parent(*BinTreeNode*start, *BinTreeNode*curent)从结点start开始，搜索结点current的双亲结点，并返回其地址，否则返回NULL。（教材P171页）5. 若用二叉链表作为二叉树的存储表示，试针对下列问题编写递归算法： （1）统计二叉树中叶子结点的个数； （2）交换每个结点的左子女和右子女。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 ERROR; / 队列满，无法插入Q.rear= ; /计算元素e的插入位置 = e; /在队尾加入新的元素Q.length+; /队列长度加1return OK;Status DeQueue(SqQueue &Q, Qelemtype &e) /删除对头元素，并用e带回其值 if ( )return ERROR; /队列满e=Q.base ; /取队头元素Qlength -; /队列长度减1return 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（pipj & ）Pi +; pi - - ; if ( )return - 1;else return 0;函数2 函数insert_sort(int a,int count)是用直接插入排序法对指定数组的前count个元素从小到大排序。 Void insert_sort(int a, int count) int i, j, t;for (i=1;icount;i+)/控制ai，acount-1的比较和插入t = ai;j= ;while (j0&taj) /在有序部分寻找元素ai的插入位置 ;j - -; ;10. 假设以数组seq0m-1存放循环队列中的元素，同时设变量rear和quelen分别指示循环队列中的队尾元素的位置和内含元素的个数。(西电2006年考研试题)请给出：（1）给出循环队列的队满条件和队空条件；（2）写出相应的入队列和出队列的算法，并分别分析其时间代价；（3）如果用数组sequmn来存放循环队列中的元素，则（2）中的入队列和出队列的算法中的哪些语句要修改？如何修改？