广工2015数据结构复习题目及答案

1《数据结构-C语言版》第一章绪论单项选择题1．在数据结构中，数据的基本单位是_________。A.数据项B.数据类型C.数据元素D.数据变量2．数据结构中数据元素之间的逻辑关系被称为______。A.数据的存储结构B.数据的基本操作C.程序的算法D.数据的逻辑结构3．在数据结构中，与所使用计算机无关的是数据的_______。A.存储结构B.逻辑和物理结构C.逻辑结构D.物理结构4．在链式存储结构中，数据之间的关系是通过________体现的。A.数据在内存的相对位置B.指示数据元素的指针C.数据的存储地址D.指针5．计算算法的时间复杂度是属于一种_______。A.事前统计的方法B.事前分析估算的方法C.事后统计的方法D.事后分析估算的方法6．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是______。A.n2B.nlognC.nD.logn7．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为_______。A.O(1)B.O(n)C.O(200n)D.O(nlog2n)2CDCBBDD第二章线性表单项选择题1．链表不具有的特点是________。A.可随机访问任一元素B.插入和删除时不需要移动元素C.不必事先估计存储空间D.所需空间与线性表的长度正比2．设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。A.139B.140C.147D.1483．在线性链表存储结构下，插入操作算法。A.需要判断是否表满B.需要判断是否表空C.不需要判断表满D.需要判断是否表空和表满4．在一个单链表中，若删除p所指结点的后继结点，则执行。A.p-next=p-next-next;B.p-next=p-next;C.p=p-next-next;D.p=p-next;p-next=p-next-next;5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为。A.O(n)B.O(1)C.O(m)D.O(m+n)6．需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是。A.单链表B.静态链表C.线性链表D.顺序存储方式ACCABB填空题1．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的_____结点。2．在单链表中，指针p所指结点为最后一个结点的条件是。3．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。4．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动元素的个数是。5．在长度为n的顺序表中插入一个元素的时间复杂度为。1前驱2p-next==NULL33.14.n-i+15.O(n)例题解析【例2-1】编写一个算法将一个单链表逆转，要求在原表上进行，不允许重新建链表。解：该算法可以在遍历原表的时候将各结点的指针逆转，从原表的第一个结点开始，头结点的指针在最后修改成指向原表的最后一个结点，即新表的第一个结点。实现本题功能的函数如下：voidinverse(Lnode*h){s=h-next;if(s==NULL)return;q=NULL;p=s;while(p!=NULL){p=p-next;s-next=q;/*逆转指针*/q=s;/*指针前移*/s=p;}h-next=q;/*头指针h的后继是p*/}【例2-2】编写一算法将两个按元素值递增有序排列的单链表A和B归并成一个按元素值递增有序排列的单链表C。解：对于两个或两个以上的，结点按元素值有序排列的单链表进行操作时，应采用“指针平行移动，依次扫描完成”的方法。从两表的第一个结点开始顺链表逐个将对应数据元素进行比较，复制小的并插入c表尾。当两表中之一已到表尾，则复制另一个链表的剩余部分，插入到c表尾。设pa、pb分别指向两表当前结点，p指向c表的当前表尾结点。若设A中当前所指的元素为a，B中当前所指的元素为b，则当前应插入到C中的元素c为babbaac例如：A=(3,5,8,11)B=(2,6,8,9,11,15,20)则C=(2,3,5,6,8,8,9,11,11,15,20)实现本题功能的函数如下：Lnode*hb(Lnode*pa,Lnode*pb){Lnode*p,*q,*pc;pc=(Lnode*)malloc(sizeof(Lnode));/*建立表c的头结点pc*/4p=pc;/*p指向C表头结点*/while(pa!=NULL&&pb!=NULL){q=(Lnode*)malloc(sizeof(Lnode));/*建立新结点q*/if(pb-datapa-data)/*比较A、B表中当前结点的数据域值的大小*/{q-data=pb-data;/*B中结点值小，将其值赋给q的数据域*/pb=pb-next;/*B中指针pb后移*/}else{q-data=pa-data;/*相反，将A结点值赋给q的数据域*/pa=pa-next;/*A中指针pa后移*/}p-next=q;/*将q接在p的后面*/p=q;/*p始终指向C表当前尾结点*/}while(pa!=NULL)/*若表A比B长，将A余下的结点链在C表尾*/{q=(Lnode*)malloc(sizeof(Lnode));q-data=pa-data;pa=pa-next;p-next=q;p=q;}while(pb!=NULL)/*若表B比A长，将B余下的结点链在C表尾*/{q=(Lnode*)malloc(sizeof(Lnode));q-data=pb-data;pb=pb-next;p-next=q;p=q;}p-next=NULL;p=pc;/*p指向表C的头结点pc*/pc=p-next;/*改变指针状态，使pc指向p的后继*/free(p);/*释放p空间*/return(pc);}此算法的时间复杂度为O(m+n)，其中m，n分别是两个被合并表的表长。5第三章栈和队列单项选择题1．在初始为空的堆栈中依次插入元素f，e，d，c，b，a以后，连续进行了三次删除操作，此时栈顶元素是。A.ｃB.ｄC.ｂD.ｅ2．若某堆栈的输入序列是1，2，3，...，n，输出序列的第一个元素为n，则第i个输出元素为。A.iB.n-iC.n-i+1D.哪个元素无所谓3．向一个栈顶指针为h的带头结点链栈中插入指针s所指的结点时，应执行。A.h-next=s;B.s-next=h;C.s-next=h;h=h-next;D.s-next=h-next;h-next=s;4．一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是。A.edcbaB.decbaC.dceabD.abcde5．栈和队列的共同点是。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点6．对于循环队列。A.无法判断队列是否为空B.无法判断队列是否为满C.队列不可能满D.以上说法都不是7.若用一个大小为6的数组来实现循环队列，且当前队尾指针rear和队头指针front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为。A.1和5B.2和4C.4和2D.5和18.判定一个循环队列QU（最多元素为m0）为满队列的条件是。A.QU-front==QU-rearB.QU-front!=QU-rearC.QU-front==(QU-rear+1)%m0D.QU-front!=(QU-rear+1)%m09.判定一个循环队列QU（最多元素为m0）为空的条件是。A.QU-front==QU-rearB.QU-front!=QU-rearC.QU-front==(QU-rear+1)%m0D.QU-front!=(QU-rear+1)%m0BCDCCDACA填空题1．在求表达式值的算符优先算法中使用的主要数据结构是。2．设有一个空栈，现输入序列为1，2，3，4，5。经过push，push，pop，push，pop，push，pop，push后，输出序列是。3．仅允许在同一端进行插入和删除的线性表称为。7．在顺序栈s中，栈为空的条件是，栈为满的条件是_____。4．用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺6序，相应的S、X操作串为。5．用一个大小为1000的数组来实现循环队列，当前rear和front的值分别为0和994，若要达到队满的条件，还需要继续入队的元素个数是。1.栈2.2343.栈4.s.top==s.base,s.top-s.base=s.stacksizeSXSSXSXX5.993例题解析【例3-1】编程实现：用除法把十进制数转换成二进制数。解：算法思想：用初始十进制数除以2把余数记录下来并且若商不为0则再用商去除以2直到商为0，这时把所有的余数按出现的逆序排列起来（先出现的余数排在后面，后出现的余数排在前面）就得到了相应的二进制数，如把十进制数35转换成二进制数的过程如图3-1所示。图3-1十进制数转换成二进制数的过程由题意可知，我们可以用一个栈来保存所有的余数，当商为0时则让栈里的所有余数出栈则可以得到正确的二进制数，算法可描述如下：voidconversion(){StackS;intn;InitStack(&S);printf(Inputanumbertoconvert:\n);scanf(%d,&n);if(n0){printf(\nThenumbermustbeover0.);35178421011001余数结果：100117return;}if(n==0)Push(S,0);while(n!=0){Push(S,n%2);n=n/2;}printf(theresultis:);while(!StackEmpty(*S)){printf(%d,Pop(S));}}}第四章串单项选择题1．串是一种特殊的线性表，其特殊性体现在。A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符2．设有两个串p和q，求q在p中首次出现的位置的运算称作。A.连接B.模式匹配C.求子串D.求串长3．串是一个B的序列。A.不少于一个字母B.有限个字符C.不少于一个字符D.空格或字母4．已知串s=’ABCDEFGH’，则s的所有不同子串的个数为。A.8B.9C.36D.37BBBD填空题1．两个串相等的充分必要条件是。2．空格串是,其长度等于。3．在串S=’tuition’中，以t为首字符且值不相同的子串有个。4.使用“求子串”substring(S,pos,len)和“联接”concat(S1,S2)的串操作，可从串s=’conduction’中的字符得到串t=’cont’，则求t的串表达式为。81.两个串的长度相等且对应位置的字符相同2.由一个或多个空格字符组成的串其包含的空格个数3.104.concat(subString(s,1,3),substring(s,7,1))第五章数组与广义表单项选择题1．常对数组进行的两种操作是。A.建立与删除B.索引和修改C.查找和修改D.查找与索引2．假设8行10列的二维数组a[1..8,1..10]分别以行序为主序和以列序为主序顺序存储时，其首地址相同，那么以行序为主序时元素a[3][5]的地址与以列序为主序时元素_______的地址相同。A.a[5][3]B.a[8][3]C.a[1][4]D.答案A、B、C均不对3．将一个A[1..100,1..100]的三对角矩阵以行序为主序存入一维数组B[1..298]中，元素A[66，65]在B数组中的位置k等于_______。A.198B.197C.196D.1954．稀疏矩阵一般的压缩存储方法有两种，即。A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表5.