数据结构和算法复习题集

...wd......wd......wd...数据构造与算法复习题写出以下各词语对应的中文〔英〕sequentialstorgestructure顺序存储构造AbstractDataType(ADT)抽象数据类型二叉排序树Binarysorttreequeue队列storgestructure存储构造timecomplexity时间复杂度线性表LinearList二叉树BinaryTreeDepth_FirstSearch深度优先搜索singlylinkedlists单链表单项选择题1、数据构造是一门研究非数值计算的程序设计问题中数据元素的、数据信息在计算机中的存储构造以及一组相关的运算等的课程。A:操作对象Ｂ:计算方法Ｃ:逻辑构造Ｄ:数据映象2、某线性表最常用的运算是插入和删除,插入运算是指在表尾插入一个新元素,删除运算是指删除表头第一个元素,那么采用存储方式最节省运算时间.。 A:仅有头指针的单向循环链表B:仅有尾指针的单向循环链表C:单向链表D:双向链表3、一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是____。A:abcdeB:decbaC:edcbaD:dceab4、将一个递归算法改为对应的非递归算法时，通常需要使用_____。A:栈 B:队列 C:循环队列D:优先队列5、关于空串，以下说法中正确的有____。A:空串就是空格串B:空串的长度可能不为零C:空串是零个字符的串D:空串的长度就是其包含的空格个数6、二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开场连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为。A:SA+141B:SA+144C:SA+222D:SA+2257、某二叉树的前序和后序序列正好相反，则该二叉树一定是的二叉树。 A:空或只有一个结点B:高度等于其结点数 C:任一结点无左孩子D:任一结点无右孩子8、下述４棵二叉树中，是完全二叉树的是：。Ａ:Ｂ:Ｃ:Ｄ:9、深度为5的二叉树至多有____个结点。A:16B:32C:31D:1010、在一个无向图中，所有顶点的度数之和等于所有边数的倍。A:1/2B:1C:2D:411、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为____.。A:(n+1)/2B:n/2C:(n-1)/2D:n12、对线性表进展折半搜索时，要求线性表必须______。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:2B:3C:4D:118、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则______。A:n0=n2+1B:n2=n0+1C:n0=2n2+1D:n2=2n0+119、下面程序段的时间复杂度是________。s=0；for(i=0；i<n；i++)for(j=0；j<n；j++)s+=B[i][j]；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的声明如下：structSTUDENT{charname[10];intnumber;}STUDENTallstudents[10][50];allstudents是一个二维数组，它的每个元素都是包含name和number的构造类型。在C语言中，二维数组使用以行序为主序的存储构造，char类型占用1字节，int类型占用4字节。假定allstudents在内存中的起始存储位置是2000，请写出计算allstudents[i][j]的存储位置的算式，并计算allstudents[5][3]的存储位置。答:(1)allstudents[i][j]的存储位置=2000+(i*50+j)*14(2)allstudents[5][3]的存储位置=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〕=2142、带权路径的长度〔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}，Ｅ＝{<1,2>,<1,3>,<1,4>,<2,5>,<3,2>,<3,5>,<3,6>,<4,6>,<5,6>}，请画出图G，并写出其邻接矩阵和邻接表表示。答：图G如下所示，图G的邻接矩阵和邻接表表示分别如图(b)和(c)所示。对于这类问题，只要掌握了图的概念和存储构造就可以做出正确的答案。通常情况下．对图的顶点排列顺序和各顶点的邻接点排列顺序并没有特定要求，因此，在写出邻接矩阵和邻接表表示时，只要按照某种排列顺序画出相应的构造图就可以了。但应该注意的是，对于邻接矩阵表示，如果顶点结点的顺序不同，那么邻接矩阵就不一样；对于邻接表表示，如果顶点结点的顺序或者邻接点的顺序不同，那么邻接表就不一样。011100011100000010010011000001000001000000(b)图图及其存储构造1(a)34256(c)12645322354∧5∧6∧∧6∧6∧七、根据二叉树的遍历，恢复该二叉树并进展其他遍历操作一棵二叉树的先序遍历为：acbrsedfmlk，中序遍历为：rbsceafdlkm，试画出该二叉树，并写出它的后序遍历。答:(1)画出该二叉树:(2)后序遍历:rsbecfklmda八、构造哈希表并求其成功查找时的ASL设有一组关键字〔19，01，23，14，55，20，84，27，68，11，10，77〕，采用哈希函数：H〔key〕=key%13，假设用开放定址法的线性探测法解决冲突，试在0～13的哈希地址空间中对该关键字序列构造哈希表并求其成功查找时的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/12≈1.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、二叉树的存储构造为二叉链表，结合以以下图阅读以下算法。typedefstructnode{TElemTypedata;structnode*next;}ListNode;typedefListNode*LinkList;LinkListLeafhead=NULL;voidInorder(BTreeT){LinkLists;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、以下算法以二叉链表为存储构造，交换二叉树各结点的左右子树。请在有横线的地方填写适宜的内容。typedefcharDataType;typedefstructnode{DataTypedata;structnode*lchild,*rchild;}BinTNode;typedefBinTNode*BinTree;BinTreeswap(BinTreeT){BinTreet,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、以下算法的功能是什么voidabct(SqList&L){for(i=2;i<=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key)){L.r[0]=L.r[i];L.r[i]=L.r[i-1];for(j=i-2;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}}//InsertSort答：直接插入排序十二、算法设计1.在单链表上实现线性表的求表长ListLength(L)运算。答：由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法描述如下：intListLength(LinkList*L){//求带头结点的单链表的表长intlen=0;ListList*p;p=L;while(p->next!=NULL){p=p->next;len++;}return(len);}2、写一算法用头插法建设无头结点的单链表，结果返回单链表的头指针typedefcharDataType;typedefstructnode{DataTypedata;structnode*next;}ListNode;typedefListNode*LinkList;答：3、线性表的元素是无序的，且以带头结点的单链表作为存储构造；设计一个删除表中所有值小于max但大于min的元素的算法。算法描述如下：delete(LinkList*head,intmax,intmin){}答：delete(LinkList*head,intmax,intmin){LinkList*p,*q;