数据结构与算法复习题.doc

_ 数据结构与算法复习题一、 写出以下各词语对应的中文（英） sequential storge structure 顺序存储结构 Abstract Data Type (ADT) 抽象数据类型 二叉排序树 Binary sort tree queue 队列 storge structure 存储结构 time complexity 时间复杂度 线性表 Linear List 二叉树 Binary Tree Depth_First Search 深度优先搜索 singly linked lists 单链表 二、 单项选择题 1、数据结构是一门研究非数值计算的程序设计问题中数据元素的 、数据信息在计算机中的存储结构以及一组相关的运算等的课程。 A: 操作对象: 计算方法: 逻辑结构: 数据映象 2、某线性表最常用的运算是插入和删除,插入运算是指在表尾插入一个新元素,删除运算是指删除表头第一个元素,那么采用 存储方式最节省运算时间.。A: 仅有头指针的单向循环链表B: 仅有尾指针的单向循环链表C: 单向链表D:双向链表3、一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是_。 A: abcde B: decba C: edcba D: dceab 4、将一个递归算法改为对应的非递归算法时，通常需要使用_。 A: 栈 B: 队列 C: 循环队列 D: 优先队列 5、关于空串，下列说法中正确的有_。A: 空串就是空格串 B: 空串的长度可能不为零C: 空串是零个字符的串 D: 空串的长度就是其包含的空格个数6、二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A74的起始地址为 。A: SA+141 B: SA+144 C: SA+222 D: SA+2257、某二叉树的前序和后序序列正好相反，则该二叉树一定是 的二叉树。A: 空或只有一个结点 B: 高度等于其结点数 C: 任一结点无左孩子 D: 任一结点无右孩子8、下述棵二叉树中，是完全二叉树的是： 。: : : :9、深度为5的二叉树至多有_个结点。A: 16 B: 32 C: 31 D: 1010、在一个无向图中，所有顶点的度数之和等于所有边数的 倍。A: 1/2 B: 1 C: 2 D: 4 11、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为_.。A: (n+1)/2 B: n/2 C: (n-1)/2 D: n 12、对线性表进行折半搜索时，要求线性表必须_。 A: 以数组方式存储且结点按关键码有序排列 B: 以数组方式存储 C: 以链接方式存储且结点按关键码有序排列 D: 以链接方式存储13、下述几种排序方法中，要求内存量最大的是_。A: 插入排序 B: 选择排序 C: 快速排序 D: 归并排序14、采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为_。A: O（n2） B: O(nlog2n) C: O(n) D: O(log2n)15、在一个单链表中，若删除p所指结点的后续结点，则执行_。A: p=p-next;p-next=p-next-next; B: p-next=p-next-next; C: p-next=p-next; D: p=p-next-next16、非线性结构中，每个结点_。A:无直接前趋 B:只有一个直接前驱和后继C:只有一个直接前趋和个数不受限制的直接后继D:有个数不受限制的直接前趋和后继17、设稀疏矩阵按列优先顺序存储于三元组表，则结点(3，2，-5)是三元组表中的第_项。A:2 B:3 C:4 D:118、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则_。A:n0=n2+1 B:n2=n0+1 C:n0=2n2+1 D:n2=2n0+119、下面程序段的时间复杂度是_。s=0；for(i=0；in；i+) for(j=0；jn；j+) s+=Bij；sum=s；A:O(1) B:O(n) C:(n2) D:O(n3)20、以下阐述不正确的是_。 A: 计算机内的数值运算依靠方程式，而非数值运算（如表、树等）则要依靠数据结构 B：数据结构是研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科 C: 数据的逻辑结构和数据的物理结构有时可以不加区分 D：同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异 21、计算机算法指的是，它必须具备输入、输出和_。 A: 计算方法 B: 排序方法 C: 解决问题的有限运算步骤 D: 程序设计方法22、数组与一般线性表的区别主要在_。A: 存储方面 B: 元素类型一致C: 逻辑结构方面 D: 不能进行插入、删除运算23、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个_结构。 A: 栈 B: 队列 C: 数组 D: 树24、在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是_。A: 希尔排序 B: 起泡排序 C: 插入排序 D: 选择排序25、二叉排序树中，键值最小的结点_。A: 左指针一定为空 B: 右指针一定为空C: 左、右指针均为空 D: 左、右指针均不为空三、 在一个C语言程序中，有结构类型STUDENT的定义和结构数组allstudents的声明如下：struct STUDENT char name10; int number;STUDENT allstudents1050; allstudents是一个二维数组，它的每个元素都是包含name和number的结构类型。已知在C语言中，二维数组使用以行序为主序的存储结构，char类型占用1字节，int类型占用4字节。假定allstudents在内存中的起始存储位置是2000，请写出计算allstudentsij的存储位置的算式，并计算allstudents53的存储位置。答: (1) allstudentsij的存储位置=2000+(i*50+j)*14 (2) allstudents53的存储位置=2000(5*50+3)*14=5542四、写出下列程序段的输出结果（栈的元素类型SelemType为char） 输出结果是：五、 构造Huffman树，并求出带权路径的长度及给出Huffman编码假设用于通信的电文由字符集A，B，C，D，E中的字母构成，这些字母在电文中出现的概率分别为27，43，19，3，12，要求：1、 构造一棵Huffman树（左结点的权不大于右结点的权） 2、 求出带权路径的长度（2分）3、 给出Huffman编码（左分支为0，右分支为1） 答： 1、对应的Huffman树 2、带权路径的长度 （27*2+43*1+19*3+3*4+12*4）=2143、Huffman编码字符ABCDEHuffman编码10011111001101六、 图的应用1、应用Prim（普里姆）算法求解下列连通图的最小生成树 要求按如下格式给出在构造最小生成树过程中顺序选出的各条边 ，并画出最小生成树 。始顶点号终顶点号权值 答:始顶点号终顶点号权值0313545223151432、图G(V，E)，其中V=1,2,3,4,5,6，,，请画出图G，并写出其邻接矩阵和邻接表表示。答：图G如下所示，图G的邻接矩阵和邻接表表示分别如图(b)和(c)所示。对于这类问题，只要掌握了图的概念和存储结构就可以做出正确的答案。通常情况下对图的顶点排列顺序和各顶点的邻接点排列顺序并没有特定要求，因此，在写出邻接矩阵和邻接表表示时，只要按照某种排列顺序画出相应的结构图就可以了。但应该注意的是，对于邻接矩阵表示，如果顶点结点的顺序不同，那么邻接矩阵就不相同；对于邻接表表示，如果顶点结点的顺序或者邻接点的顺序不同，那么邻接表就不相同。0 1 1 1 0 00 0 0 0 1 00 1 0 0 1 10 0 0 0 0 10 0 0 0 0 10 0 0 0 0 0(b)图 图及其存储结构1(a)34256(c)126453223545666七、根据二叉树的已知遍历，恢复该二叉树并进行其他遍历操作 已知一棵二叉树的先序遍历为：acbrsedfmlk，中序遍历为：rbsceafdlkm ，试画出该二叉树 ，并写出它的后序遍历 。答:(1) 画出该二叉树:(2)后序遍历:rsbecfklmda八、 构造哈希表并求其成功查找时的ASL 设有一组关键字（19，01，23，14，55，20，84，27，68，11，10，77），采用哈希函数：H（key）= key % 13，若用开放定址法的线性探测法解决冲突，试在013的哈希地址空间中对该关键字序列构造哈希表并求其成功查找时的ASL。1、填写对应的哈希表 哈希地址012345678910111213关键字 比较次数 2、求其成功查找时的ASL 答：依题意，m=13，线性探测法的下一个地址计算公式为：di = H（key）di+1 = （di+1）% m ；i=1，2，1、哈希表如下：（3分）哈希地址012345678910111213关键字11455276819208423111077比较次数1214311311322、共有12个关键字，等概率查找，则成功查找时（2分）ASL=（1+2+1+4+3+1+1+3+1+1+3+2）/12=23/121.9九、建立二叉排序树并作插入和删除操作 已知一组关键字为28,9,32,40,34,22,25,33,7,15,要求：1、建立一棵二叉排序树 2、画出插入结点20后的二叉排序树 3、画出再删除结点32后的二叉排序树 答： 建二叉排序树 插入结点20后的二叉排序树 或 删除结点32后的二叉排序树十、排序算法操作 1、用希尔排序法，对8个数值（4，19，28，29，11，21，74，87）进行排序，增量序列为:5、3、1，并输出前2趟的结果。 答：第1趟排序结果： 4，19，28，29，11，21，74，87第2趟排序结果： 4，11，21，29，19，28，74，872、用快速排序法，对8个数值（46，6，98，19，32，40，60，40）进行排序，并输出前2趟的结果。 答：第1趟排序结果： 40，6，40，19，32，46，60，98第2趟排序结果： 32，6，40，19，40，46，60，983、用冒泡排序法，对 10个数值（46,74,53,14,26,38,86,65, 27,34）进行排序，并输出前2趟的结果。 答：第1趟排序结果： 46 , 53, 14,26,38,74,65,27,34,86 第2趟排序结果： 46,14 ,26,38, 53,65,27,34,74,86十一、 阅读理解算法并回答问题和填充 1、已知二叉树的存储结构为二叉链表，结合下图阅读下列算法。typedef struct node TElemType data; struct node *next;ListNode;typedef ListNode *LinkList;LinkList Leafhead=NULL;void Inorder(BTree T) LinkList s; if(T) Inorder(T-lchild); if(!T-lchild) & (!T-rchild) s=(ListNode*)malloc(sizeof(ListNode); s-data=T-data; s-next=Leafheak; Lerfhead=s; Inorder(T- rchild); 对于上图所示的二叉树：（1）画出执行上述算法后所建立的结构 （2）说明该算法的功能 答：（1）执行上述算法后建立的结构为如下所示的链表 （2）该算法的功能是用中序遍历递归算法对二叉树进行遍历，将二叉树中叶结点数据域的值作为单链表结点的值，并用头插法建立一个以Leafhead为头指针的逆序单链表（即按二叉树中叶结点数据从右至左链接成一个链表。2、下列算法以二叉链表为存储结构，交换二叉树各结点的左右子树。请在有横线的地方填写合适的内容。 typedef char DataType;typedef struct node DataType data; struct node *lchild, *rchild; BinTNode; typedef BinTNode *BinTree; BinTree swap(BinTree T) BinTree t,t1,t2; if (T=NULL) t=_(1);else t=(BinTree)malloc(sizeof(BinTNode);t-data=_(2); t1=swap(T-lchild); t2=swap(T-rchild); t-lchild=_(3);t-rchild=_(4); return(_(5); 答：(1) NULL ;(2) T-data;(3) t2 ;(4) t1 ;(5) _ t_; 3、下列算法的功能是什么？void abct(SqList &L) for ( i=2; inext!=NULL ) p=p-next;len+; return (len);2、写一算法用头插法建立无头结点的单链表，结果返回单链表的头指针 typedef char DataType; typedef struct node DataType data; struct node *next; ListNode; typedef ListNode *LinkList;答：3、已知线性表的元素是无序的，且