华南理工大学《数据结构》课程习题集部分答案.docx 12页

'《数据结构》课程习题集第1页（共25页）一、.选择题.1.算法的计算量的大小称为计算的（B）。A．效率B.复杂性C.现实性D.难度.2.算法的时间复杂度取决于（C）.A．问题的规模B.待处理数据的初态C.A和BD.难确定.3.下面关于算法说法错误的是（D）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的.4．从逻辑上可以把数据结构分为（C）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构.5．以下数据结构中，哪一个是线性结构（D）？A．广义表B.二叉树C.稀疏矩阵D.串.6．下述哪一条是顺序存储结构的优点？（A）A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示.7．下面关于线性表的叙述中，错误的是哪一个？（B）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。.8．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表.9．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(D)最节省时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表.10.链表不具有的特点是（B）.A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比.11.设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（D）。A.51234B.45132C.43125D.32154.12.某堆栈的输入序列为a,b，c，d,下面的四个序列中，不可能是它的输出序列的是（D）。A.a，c，b，dB.b,c，d，aC.c,d，b,aD.d,c，a，b.13.用链接方式存储的队列，在进行删除运算时（D）。A.仅修改头指针B.仅修改尾指针第12页（共25页） C.头、尾指针都要修改D.头、尾指针可能都要修改.14.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时(D)。A．仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改.15．下面关于串的的叙述中，哪一个是不正确的？（B）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储.16．串是一种特殊的线性表，其特殊性体现在(B)A．可以顺序存储B．数据元素是一个字符C．可以链接存储D．数据元素可以是多个字符.17．关于空串与空格串，下面说法正确的是(D)。A．空串与空格串是相同的B．空串与空格串长度是相同的C．空格串中存放的都是空格D．空串中存放的都是NULL.18．图中有关路径的定义是（A）。A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是.19．设无向图的顶点个数为n，则该图最多有（B）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n2.20．一个n个顶点的连通无向图，其边的个数至少为（A）。A．n-1B．nC．n+1D．nlogn；.21．某内排序方法的稳定性是指(D)。A．该排序算法不允许有相同的关键字记录B．该排序算法允许有相同的关键字记录C．平均时间为0（nlogn）的排序方法D．以上都不对22．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（D）方法最快。A．起泡排序B．快速排列C．Shell排序D．堆排序E．简单选择排序.23．排序趟数与序列的原始状态有关的排序方法是(C)排序法。A．插入B.选择C.冒泡D.都不是24．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。(A)A．选择排序法B.插入排序法C.快速排序法D.都不是25．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（C）排序。A.选择B.快速C.希尔D.冒泡26.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（D）A．5B．6C．7D．827．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（E）A．250B．500C．254D．505E．以上答案都不对第12页（共25页） 28.有关二叉树下列说法正确的是（B）.A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为2.29．二叉树的第I层上最多含有结点数为（C）.A．2IB．2I-1-1C．2I-1D．2I-1.30．对于有n个结点的二叉树,其高度为（C）.A．nlog2nB．log2nC．ëlog2nû|+1D．不确定.31．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用(C)次序的遍历实现编号。A．先序B.中序C.后序D.从根开始按层次遍历.32.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为(A)A．（N+1）/2B.N/2C.ND.[（1+N）*N]/2.33.对线性表进行二分查找时，要求线性表必须（B）A.以顺序方式存储B.以顺序方式存储,且数据元素有序C.以链接方式存储D.以链接方式存储,且数据元素有序.34．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度(C).A．必定快B.不一定C.在大部分情况下要快D.取决于表递增还是递减.35.具有12个关键字的有序表，折半查找的平均查找长度（A）.A.3.1B.4C.2.5D.5.36.既希望较快的查找又便于线性表动态变化的查找方法是(C)A．顺序查找B.折半查找C.索引顺序查找D.哈希法查找二、填空题.1.对于长度为255的表，采用分块查找，每块的最佳长度为____16______。.2.顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__n__次；当使用监视哨时，若查找失败，则比较关键字的次数为__n+1__。.3．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为__6.9.11.12____。.4..在一棵二叉树中，第5层上的结点数最多为16个。.5.、n(n>0)个结点构成的二叉树，叶结点最多floor((n+1)/2)个，最少有1个。若二叉树有m个叶结点，则度为2的结点有m-1个。.6．二叉树中某一结点左子树的深度减去右子树的深度称为该结点的平衡因子。.7.假定一棵二叉树的结点数为18，则它的最小深度为5，最大深度为16；.8.在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则有n0=n2+1。.9.现有按中序遍历二叉树的结果为abc，问有__5__种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是____。.10．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_比较_和记录的_移动_。.11．直接插入排序用监视哨的作用是_免去查找过程中每一步都要检测整个表是第12页（共25页） 否查找完毕，提高查找效率。.12.不受待排序初始序列的影响，时间复杂度为O(N2)的排序算法是_简单选择排序_，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_直接插入排序_。.13.判断一个无向图是一棵树的条件是_n个定点，n-1条边的无向连通图。.14．具有10个顶点的无向图，边的总数最多为_45_。.15．若用n表示图中顶点数目，则有_______条边的无向图成为完全图。.16．空格串是指_由空格字符所组成的字符串_，其长度等于_空格个数_。.17．设T和P是两个给定的串，在T中寻找等于P的子串的过程称为_模式匹配，又称P为_模式串_。.18．串的两种最基本的存储方式是_顺序储存_、_链式储存_；两个串相等的充分必要条件是_长度相等对应位置字符也相等__。.19.已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是s=(LinkedList)malloc(sizeof(LNode))；s->data=x;s->next=r->next；r->next=s；r=s；。.20.向栈中压入元素的操作是_移动指针和插入。.21.在具有n个单元的循环队列中，队满时共有_n-1_个元素。.22．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_SXSSXSXX_。.23.单链表是_线性表_的链接存储表示。.24.在双链表中，每个结点有两个指针域，一个指向_前驱_，另一个指向_后继_。.25．链接存储的特点是利用_指针_来表示数据元素之间的逻辑关系。.26.顺序存储结构是通过_相邻位置_表示元素之间的关系的;链式存储结构是通过_指针_表示元素之间的关系的。.27．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_（n-1）/2_。.28．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_单链表_和_多重链表_；而又根据指针的连接方式，链表又可分成_动态链表_和_静态链表_。.29．数据的物理结构包括_顺序储存_的表示和_链式储存_的表示。.30．抽象数据类型的定义仅取决于它的一组_逻辑特性_，而与_在计算机内部如何表示和实现_无关，即不论其内部结构如何变化，只要它的_数学特性_不变，都不影响其外部使用。.31．数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度.32.数据结构是研讨数据的_逻辑结构和_物理结构，以及它们之间的相互关系，并对与这种结构定义相应的操作，设计出相应的算法_。三．程序填空题．1．已知单链表H为一个用带头结点的链表表示的线性表，如下算法是将其倒置。请在下划线处填上正确的语句。templatevoidLine_ListLink：：Reverse(){Line_ListNode*p，*head=newLine_ListNode()；while(_first!=NULL)第12页（共25页） {p=first；first=first–>link；p–>link=head-link;first=head–>link；delete_head;}．2．在顺序表中随机存取的数据，很容易在顺序表中实现按序号查找元素。代码如下所示，请在下划线处填上正确的语句。templateboolLine_ListSqu：：Find(_inti___，T&x)const//在线性表中查找第i个元素并用x返回{if(_i﹤1‖i﹥length；returnfalse；x=elem[i–1]；return__true；}．3．线性表的插入操作是指在线性表的第m–1个数据元素和第m个数据元素之间插入一个新的数据元素x，其结果是使长度为n的线性表(a1,a2,…,am–1,am,…,an)变成长度为n+1的线性表(a1,a2,…,am–1,x,am,…,an)，并且数据元素am–1和am之间的逻辑关系发生了变化。实现步骤如下：(1)合法性判断：插入位置i是否合法?表是否已满?(2)将第i至第n位的元素向后移动一个位置；(3)将要插入的元素写到第i个数据元素的位置；(4)表长加1。具体算法如下，请在下划线处填上正确的语句。templateLine_ListSqu&Line_ListSqu：：Insert(inti，T&x){if(_i〈0‖i〉length+1；throwOutOfBounds()；if(length==MaxSize)throwNoMem()；for(_intj=length-4；j>=i–1；j––)elem[j+1]=elem[j]；elem[i–1]=_x_；length++；return_*this；}.4.-冒泡排序（BubbleSort）的基本思想是：设数组a中存放了n个数据元素，循环进行n趟如下的排序过程，请在下划线处填上正确的语句。voidBubbleSort(DataTypea[],intn){inti,j,flag=1;DataTypetemp;for(i=1;_i〈﹠﹠flag==1_;i++){flag=0;for(j=0;_j〈n-i;j++){if(_a[j].key〉a[j+1].key){flag=1;temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}}.5.按值查找是指在线性表中查找与给定值x相等的数据元素，具体实现代码如下，请在下划线处填上正确的语句。templateintLine_ListSqu：：Search(constT&x)const{int__i=0_；第12页（共25页） if(IsEmpty())return0；//线性表为空时返回0while(_i〈length﹠﹠！(x==elem[i]))i++；if(elem[i]==x)return++i；elsereturn____0___；}.6.线性表的删除操作是使长度为n的线性表(a1,a2,…,am–1,am,…,an)变为长度为n–1的线性表(a1,a2,…,am–1,am+1,,…,an)，并且数据元素am–1、am和am+1之间的逻辑关系也会发生变化，需要把第m+1～n个元素（共n–m个元素）依次向前移动一个位置来反映这种变化。具体实现步骤如下：①判断删除位置i是否合法，合法则将该位置元素放入x中，否则抛出异常；②将第i+1至第n位的元素向前移动一个位置；③表长减1。具体算法如下，请在下划线处填上正确的语句。templateLine_ListSqu&Line_ListSqu：：Delete(_inti_，T&x){if(Find(i，x)){for(_intj=i_；jLine_ListLink&Line_ListLink：：Delete(inti，T&x){if(__i〈1__||!first)throwOutOfBounds()；//删除位置不合法Line_ListNode*p=first；if(_i==1_)first=first–>link；else{Line_ListNode*q=first；intj=1；//查找第i个结点第12页（共25页） while(_q﹠﹠_jlink；++j；}if(!q||_！q-〉link_)throwOutOfBounds()；//没有第i个结点p=q–>link；q–>link=p–>link；}.9.删除运算是将单链表的第i个结点删去。先在单链表中找到第i–1个结点，再删除其后的结点。具体算法代码如下所示：请在下划线处填上正确的语句。templateLine_ListLink&Line_ListLink：：Delete(inti，T&x){if(_i〈1‖！first_)throwOutOfBounds()；//删除位置不合法Line_ListNode*p=first；if(_i==1__)first=first–>link；else{Line_ListNode*q=first；intj=1；//查找第i个结点while(q&&jlink；++j；}if(!q||_！q-〉link_)throwOutOfBounds()；//没有第i个结点p=q–>link；q–>link=p–>link；}x=p–>data；deletep；return*this；}.10.求子串Sub_String已知串S，1≤pos≤Length_Str(S)且0≤len≤Length_Str(S)–pos+1，用串Sub返回S的自第i个字符起长度为j的子串。请在下划线处填上正确的语句。stringSub_String(string&Sub,stringS,inti,intj);{intp;Sub.length=0;if(i<=0||i>S.length||j<=0||i-1+j〉s.lengthreturnSub;//参数错误时，返回空串for(p=i–1;_p〈i-1+j_;p++)//把S.ch[i–1]至S.ch[i–1+j]复制到串Sub中Sub.ch[p–i+1]=S.ch[p];Sub.ch[j]="";sub.length_=j;returnSub;}}．四．阅读理解题(描述算法思路,再综合出其功能)本题说明:算法思路指的是对某种数据结构(如,记录序列),进行操作(如,移动位置),的处理步骤(如,1,2,3….).算法功能指的是要达到的处理目标(如,合并成有序的单链表.).1.阅读如下算法代码：描述算法思路,再综合出其功能.main(){inti,max,a[10];printf(“请输入10个整数:”);for(i=0;i<=10;i++)scanf(“%d”,&a[i]);max=a[0];第12页（共25页） i=1;while(i<10){if(a[i]>max)max=a[i];i++;}printf(“值为:”,max);}答：10个数字找出其最大值.2.阅读如下算法代码：描述算法思路,再综合出其功能.voiddelete(node*head,intx){node*p,*q;q=head;p=head->next;while((p!=NULL)&&(p->data!=x)){q=p;p=p->next;}if(p==NULL)printf("未找到x！n");elseif(q==head)printf("x为第一个结点，无前趋！n");else{q->data=x;q->next=p->next;free(p);}}.3.阅读如下算法代码：描述算法思路,再综合出其功能.intInsertPosList(structList*L,intpos,ElemTypex){inti;if(pos<1||pos>L->size+1)/*若pos越界则插入失败*/return0;if(L->size==L->MaxSize)/*重新分配更大的存储空间*/againMalloc(L);for(i=L->size-1;i>=pos-1;i--)L->list[i+1]=L->list[i];L->list[pos-1]=x;L->size++;return1;}.4.阅读如下算法代码：描述算法思路,再综合出其功能.　　　　voidInsertIncreaseList(Seqlist*L,Datatypex)　　　　　{ 　　　　　　inti;　　　　　　if(L->length>=ListSize)　　　　　　　Error(“overflow");　　　　　　for(i=L->length;i>0&&L->data[i-1]>x;i--)　　　　　　　L->data[i]=L->data[i];//比较并移动元素　　　　　　L->data[i]=x;　　　　　　L->length++;　　　　　}.5.阅读如下算法代码：描述算法思路,再综合出其功能.第12页（共25页） 　　voidDeleteList(LinkListL,DataTypemin,DataTypemax)　　　{　　　　ListNode*p,*q,*s;　　　　p=L;　　　　while(p->next&&p->next->data<=min) 　　　　//找比min大的前一个元素位置　　　　　p=p->next;　　　　q=p->next;//p指向第一个不大于min结点的直接前趋，q指向第一个大于min的结点　　　　while(q&&q->datanext;　　　　　　free(s);//删除结点，释放空间　　　　　}　　　　p->next=q;//将*p结点的直接后继指针指向*q结点　　　}.6.阅读如下算法代码：描述算法思路,再综合出其功能.voidenqueue(intx){inttemp;if(count==n)printf("队列上溢出n");Else{count++;temp=(front+count)%n;Queue[temp]=x;}}intdequeue(){inttemp;if(count==0)printf("队列下溢出n");else{temp=Queue[front];front=(front+1)%n;count--;returntemp;}}.7.．阅读如下算法代码：描述算法思路,再综合出其功能.StatusListInsert_L(LinkList&L,inti,ElemTypee){//在带头结点的单链表L.p=L;k=0;//初始化，p指向头结点，k为计数器while(p&&knext;++k;}//找到第i-1个元素所在结点if(!p||k>i-1)returnERROR;//无法插入if(!(s=(LinkLinst)malloc(sizeof(LNode))))//申请元素e的结点空间returnOVERFLOW;//内存无空闲单元，无法申请到空间s->data=e//申请一个结点s；s->next=p->next;//修改s的指针域指向p的下一结点p->next=s;//修改p的指针域指向sreturnOK;}//LinstInsert_L.8.下阅读如下算法代码：描述算法思路,再综合出其功能.Quicskort(Recordnoder[]，intlow，inthigh)/*low和high为记录序列的下界和上界*/{inti，j；structRecordnodex；i=low；第12页（共25页） j=high；x=r[low]；while(i=x.key)j--;if(i=0&&inext;pb=Lb->next;　　Lc=pc=La;　while(pa&&pb){if(pa->dataif(pa->data<=Pb->data)Pb->data){pc->next=pa;pc=pa;pa=pa->next;}　Else{pc->next=pc->next=pb;pc=pb;pb=pb->next;}}　pc->next=pa?pa:pb;　free(Lb);}五．编程题。.1.设一循环队列Queue，只有头指针front，不设尾指针，另设一个内含元素个数的计数器，用一个循环数组Queue[0,n-1]表示该循环队列,头指针为front,计数器count用来记录队列中结点的个数。请写出其入队、出队操作功能的算法代码。.2.插入运算是将值为x的新结点插入到单链表的第i个结点之前的位置上。先在单链表中找到第i–1个结点，再在其后插入新结点。请写出具体算法代码。.3.假设有n(>=1)个整数a1,a2,…,an.要求对此数列由小到大进行排序。请写出具体算法代码。.4.折半查找的函数算法，其功能是在线性表r中二分查找关键字为k的结点，查找到，则返回其位置i；若找不到返回0。请写出具体算法代码。..5．将一个字符串中的所有字符按相反的次序重新放置。请写出具体算法代码。.6.已知一个线性表中的元素按元素值非递减有序排列，试设计算法删除表中值相同的多余元素。请写出具体算法代码。.7.快速排序（QuickSort）请写出其操作功能的算法代码。其排序的基本思想是：取记录序列中一个合适的关键字(通常选取序列中的第一个)，以此关键字取对应的记录ri作为基准，把一个序列分割成两个独立的子序列，使得基准位置前的所有记录的关键字都小于rikey，而基准位置后的所有记录的关键字都大于ri.key。这里把这样的一次过程称作一次快速排序，在第一次快速排序中，确定了所选取的基准记录ri在序列中的最终排列位置，同时也把剩余的记录分成了两个序列，然后对每个序列再进行分割，重复上述过程，直到所有记录全部排好序为止。.8.以二叉链表为存储结构，设计一个求二叉树高度的算法代码。.9.单链表查找第i个结点，也是从头指针开始，依次后移到第i个结点，请写出具体算法代码。.10.线性表的插入操作是指在线性表的第m–1个数据元素和第m个数据元素之间插入一个新的数据元素x，其结果是使长度为n的线性表(a1,a2,…,am–1,第12页（共25页） am,…,an)变成长度为n+1的线性表(a1,a2,…,am–1,x,am,…,an)，并且数据元素am–1和am之间的逻辑关系发生了变化。请写出具体算法代码。第12页（共25页）'