数据结构习题(覆盖面全,难度大).doc

习题一绪论一、单项选择题1数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。A.数据元素B.计算方法C.逻辑存储D.数据映象A.结构B.关系C.运算D.算法答：AB2数据结构被形式地定义为(K,R),其中K是的有限集，R是K上的有限集。A.算法B.数据元素C.数据操作D.逻辑结构A.操作B.映象C.存储D.关系答：BD3在数据结构中，从逻辑上可以把数据结构分成_。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构答：C4算法分析的目的是，算法分析的两个主要方面是。A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性A.空间复杂度和时间复杂度B.正确性和简单性C.可读性和文档性D.数据复杂性和程序复杂性答：AA5计算机算法指的是，它必须具备输入、输出和等5个特性。A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法A.可执行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性易读性、稳定性和安全性答：CB二、简述下列概念数据，数据元素，数据类型，数据结构，逻辑结构，存储结构，线性结构，非线性结构。答：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中边被计算机程序处理的符号的总称。数据元素数据的基本单位，在计算机程序中通常做为一个整体进行考虑和处理。数据类型是具有相同性质的计算机数据的集合及在这个数据上的一组运算，是和数据结构密切相关的概念。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。逻辑结构数据元素之间的逻辑关系的描述，称为数据的逻辑结构。存储结构数据结构在计算机中的表示称为数据的物理结构，又称存储结构。线性结构结构中的数据元素之间存在一个对一个的关系。非线性结构我们也可以将树形结构、集合和网状结构归纳为非线性结构。三、填空题1下面程序段的时间复杂度是_。For(i=0;in;i+)For(j=0;jm;j+)Aij=0;答：O(m*n)2下面程序段的时间复杂度是_。i=s=0While(sn)i+;s+=i;答：O(n开根号)3下面程序段的时间复杂度是_。s=0;for(i=0;in;i+)for(j=0;jn;j+)s+=Bij;sum=s;答：O（n2)4下面程序段的时间复杂度是_。i=1;While(inext=NULL;C.head-next=head;D.head!=NULL;答：A23.带头结点的单链表head为空的判定条件是_。A.head=NULL;B.head-next=NULL;C.head-next=head;D.head!=NULL;答：B24.在循环双链表的p所指结点之后插入s所指结点的操作是_。A.p-right=s;s-left=p;p-right-left=s;s=-right=p-right;B.p-right=s;p-right-left=s;s-left=p;s-right=p-right;C.s-left=p;s-right=p-right;p-right=s;p-right-left=s;D.s-left=p;s-right=p-right;p-right-left=s;p-right=s;答：D25.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行_。A.s-next=p-next;p-next=s;B.p-next=s-next;s-next=p;C.q-next=s;s-next=p;D.p-next=s;s-next=q;答：C26.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_个结点。(参见网上讲义：1.4.2例1_5)A.n;B.n/2;C.(n-1)/2;D.(n+1)/2;答：D27.给定有n个结点的向量，建立一个有序单链表的时间复杂度_。A.O(1);B.O(n);C.O(n);D.O(nlogn);答：C三、填空题28.在一个长度为n的向量中的第i个元素(1in)之前插入一个元素时，需向后移动_个元素。答：n-i+129.在一个长度为n的向量中删除第i个元素(1in)时，需向前移动_个元素。答：n-i30在一个单链表中p所指结点之前插入一个由指针s所指结点，可执行以下操作：s-next=_p-next_;p-next=s;t=p-data;p-data=_s-data_;s-data=_t_;四、算法设计题：31.有一个单链表（不同结点的数据域值可能相同），其头指针为head，编写一个函数计算数据域为x的结点个数。解：本题是遍历通过该链表的每个结点，每遇到一个结点，结点个数加1，结点个数存储在变量n中。实现本题功能的函数如下：intcount(head,x)node*head;ElemTypex;node*p;intn=0;p=head;while(p!=NULL)if(p-data=x)n+;p=p-next;return(n);32.有一个有序单链表（从小到大排序），表头指针为head，编写一个函数向该单链表中插入一个元素为x的结点，使插入后该链表仍然有序。解：本题算法的思想是先建立一个待插入的结点，然后依次与链表中的各结点的数据域比较大小，找出该结点的位置，最后插入该结点。实现本题功能的函数如下：node*insertorder(head,x)node*head;ElemTypex;node*s,*p,*q;s=(node*)malloc(sizeof(node);s-data=x;s-next=NULL;if(head=NULLxdata)s-next=head;head=s;elseq=head;p=q-next;while(p!=NULL&xp-data)if(xp-data)q=p;p=p-next;s-next=p;q-next=s;return(head);33编写一个函数将一个头指针为a的单链表A分解成两个单链表A和B，其头指针分别为a和b，使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。解：其函数是将单链表A中的所有偶数序号的结点删除，并在删除时把这些结点链接起来构成单链表B。实现本题功能的函数如下：voiddisa(a,b)node*a,*b;node*r,*p,*q;p=a;b=a-next;r=b;while(p!=NULL&p-next!=NULL)q=p-next;p-next=q-next;r-next=q;r=qp=p-next;r-next=NULL;34.假设有两个已排序的单链表A和B，编写一个函数将它们合并成一个链表C而不改变其排序性。解：这里采用链表合并的方法，设原两链表的头指针分别为p和q，每次比较p-data和q-data的值，把值较小的结点作为新链表的结点，这一过程直到一个链表为空为止。当一个链表为空而另一个链表不为空时，只要将不空的链表指针赋给新链表中最后一个结点的指针即可。实现本题功能的函数如下：node*mergelink(p,q)node*p,*q;node*h,*r;h=(node*)malloc(sizeof(node);h-next=NULL;r=h;while(p!=NULL&q!=NULL)if(p-datadata)r-next=p;r=p;p=p-next;elser-next=q;r=q;q=q-next;if(p=NULL)r-next=q;if(q=NULL)r-next=p;/*下面三句要去掉链表C的头结点，如果不想去掉，则不要这三句*/p=h-next;h=h-next;free(p);returnh;35设A=（a,a）和B=（b,bn）均为顺序表，A和B分别为A和B中除去最大共同前缀后的子表（例如，A=（x，y，y，z，x，z），B=（x，y，y，z，y，x，x，z），则两者中最大的共同前缀为（x,y,y,z），在A=B=空表，则A=B；若A=空表，而B空表，或者两者均不为空表，且A的首元小于B的首元，则AB。（词典次序）试写一个比较A，B大小的算法（在算法中，不要破坏原表A和B，并且不一定先求得A和B才进行比较）。36.设有一个用向量表示的线性表L，要求写出一个将该表逆置的过程，并允许在原表的存储空间外再增加一个附加的工作单元。(朱儒荣,C语言版数据结构考研例题)解：用数据类型描述Seqlist顺序存储结构：voldconverts(seqlistL)k=L.length;m=k/2;for(i=0;im;i+)x=L.elementi;L.elementi=L.elementk-i-1;L.elementk-i-1=x;/converts讨论：这个算法过程只须进行数据元素的交换操作，其主要时间花费在for循环上，整个算法的时间复杂度为O(k)。37.已知两个整数集合A和B，它们的元素分别依元素值递增有序存放在两个单链表HA和HB中，编写一个函数求出这两个集合的并集C,并要求集合C的链表的结点仍依元素值递增有序存放。(提示：求并集不是归并!)38已知两个顺序表A和B分别表示两个集合，其元素递增排列，编写一个函数求出A和B的交集C，要求C同样以元素递增的顺序表形式存储。voidSqList_Intersect(SqListA,SqListB,SqList&C)/求元素递增排列的线性表A和B的元素的交集并存入C中i=0;j=0;k=0;while(A.elemi&B.elemj)if(A.elemiB.elemj)j+;if(A.elemi=B.elemj)C.elemk+=A.elemi;/当发现了一个在A,B中都存在的元素,i+;j+;/就添加到C中/while/SqList_Intersect算法设计题：27假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队列和出队列的算法。解：void InitCiQueue(CiQueue &Q)/初始化循环链表表示的队列Q Q=(CiLNode*)malloc(sizeof(CiLNode); Q-next=Q;/InitCiQueuevoid EnCiQueue(CiQueue &Q,int x)/把元素x插入循环链表表示的队列Q，Q指向队尾元素，Q-next指向头结点，Q-next-next指向队头元素 p=(CiLNode*)malloc(sizeof(CiLNode); p-data=x; p-next=Q-next;/直接把p加在Q的后面 Q-next=p; Q=p;/修改尾指针Status DeCiQueue(CiQueue &Q,int x) /从循环链表表示的队列Q头部删除元素x if(Q=Q-next) return INFEASIBLE;/队列已空 p=Q-next-next;x=p-data;Q-next-next=p-next;free(p);return OK;/DeCiQueue28利用两个栈s1，s2模拟一个队列时，如何用栈的运算来实现该队列的运算：enqueue:插入一个元素；dequeue:删除一个元素；queue_empty:判定队列为空。解：由于栈的特点是先进后出，为了模拟先进先出的队列，必须用两个栈，一个栈s1用于插入元素，另下栈s2用于删除元素，每次删除元素时应将前一个栈的所有元素读出然后进入第二个栈中，这样才能达到模拟队列的效果，这里使用栈的一些基本操作如下：push(ST,x):栈的压入ptop(ST,x):退出栈顶元素赋给xsempty(ST):判定栈是否为空 void enqueue(s1,x) stack s1;int x; if(s1-top= m0) printf(“队列上溢出！n”); else push(s1,x); void dequeue(s1,s2,x) stack s1,s2;int x; s2-top=0; while(!sempty(s1) push(s2,ptop(s1); ptop(s2,x); while(!sempty(s2) push(s1,ptop(s2); int queue_empty(s1) stack s1; if sempty(s1) return(1); else return(0);29假设称正读和反读都相同的字符序列为“回文” (即回文是指一个字符序列以中间字符为基准两边字符完全相同)，例如，abba和abcba是回文，ababab则不是回文。试编写一个判断读入的一个以为结束符的字符序列是否“回文”的算法。解：解题思路：判断回文算法Palindrome_Test()的思想是：把字符串中的字符逐个分别存入队列和堆栈，然后逐个出队列和退栈并比较出队列的数据元素和退栈的数据元素是否相等，若全部相等则该字符序列是回文，否则就不是回文。实现本题功能的函数如下(类C编写)： int Palindrome_Test() /判别输入的字符串是否是回文序列，是则返回1，否则返回0 Initstack(S); InitQueue(Q); while ( (c =getchar() !=) Push(S,c); EnQueue(Q,c); /同时使用栈和队列两种结构 while(!StackEmpty(S) Pop(S,a); DeQueue(Q,b); if(a!=b) return ERROR;return OK;/Palindrome_Test数据结构-串（上）(2010-07-02 02:05:15)标签：校园判断题：1空串是由空白字符组成的串（FALSE）2.串的定长顺序结构是用一组地址连续的存储单元存储串值的字符序列，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。(TRUE)3串的堆分配存储表示是用一组地址连续的存储单元存储串值的字符序列，但它们的存储空间是在程序执行过程中动态分配得到的。（TRUE）4串中StrInsert(&S,pos,T)基本操作是最小的操作子集（FALSE）5.串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中字符构成的有限序列。(FALSE)(错：子串是主串中连续的字符构成的有限序列)(题源：胡元义，C版数据结构课程辅导与习题解析，p80，4.2.1(判断题)_1)6.如果一个串中的所有字符均在另一串中出现，那么则说明前者是后者的子串。(FALSE)(错：是否连续是关键)(题源：陈明，C版实用数据结构基础，p109，(判断题)_2)7.串类型的最小操作子集不能利用其他串操作来实现，反之，其他串操作均可在最小操作子集上实现。(TRUE)(题源：根据教材p72自编)单项选择题：8下列那些为空串（）A）S=“”B）S=“”C）S=“”D）S=“”答案：B9S1=“ABCD”，S2=“CD”则S2在S3中的位置是（）A）1B）2C）3D）4答案：C10.假设S=“abcaabcaaabca”，T=“bca”，Index(S,T,3)的结果是（）A）2B）6C）11D）0答案：B11.在串中，对于SubString(&Sub,S,pos,len)基本操作，pos和len的约束条件是（）A）0posStrLength(S)+1且1=len=StrLength(S)-pos+1B）0posStrLength(S)+1且0=len=StrLength(S)-pos-1C）1=pos=StrLength(S)且0=len=StrLength(S)-pos+1D）1=pos=StrLength(S)且1=len=StrLength(S)-pos-1答案：C12.串是一种特殊的线性表，其特殊性体现在()。(题源：李春葆，C版题解，p102，4.2.1(单选)_2)A可以顺序存储B.数据元素是一个字符C可以链接存储D.数据元素可以是多个字符答：B13.串是()。(题源：陈明，C版实用数据结构基础，p109，习题(单选)_1)A少于一个字母的序列B.任意个字母的序列C不少于一个字符的序列D.有限个字符的序列答：D14.串的长度是()。(题源：陈明，C版实用数据结构基础，p109，习题(单选)_3)A串中不同字母的个数B.串中不同字符的个数C串中所含的字符的个数D.串中所含字符的个数，且大于0答：C15.设有S1=ABCDEFG，S2=PQRST，函数con(x，y)返回x和y串的连接串，subs(I，j)返回串S的从序号I的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(S1，2，len(S2)，subs(S1，len(S2)，2)的结果是()。(题源：李春葆，C版题解，p102，4.2.1(单选)_4)ABCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF答：D16.若某串的长度小于一个常数，则采用()存储方式最为节省空间。(题源：胡元义，C版数据结构课程辅导与习题解析，p90，4.3.1习题(4.3)A链式B.堆结构C.顺序表答：C填空题：17串是每个结点仅由一个字符组成的（）。答：线性表18在串中，SubString(“student”,5,0)的结果是（）答：“”19假设S=“abcaabcaaabca”，T=“bca”，V=“x”，Replace(S,T,V)结果是（）答：“axaxaax”20在串中，对于StrCompare(S,T)基本操作，若ST，返回值（）答：021在串顺序存储结构中，实现串操作的原操作为（）答：字符序列的复制22. 串与线性表在逻辑结构上极为相似，区别仅在于 ；在基本操作上差别很大，线性表的基本操作大多数以 作为操作对象，而串的基本操作通常以 作为操作对象。(题源：根据教材p71页自编)答：串的数据对象约束为字符集 “单个元素” “串的整体”23两个串相等的充分必要条件是 且 。(题源：根据教材p70页自编)答：两个串的串长相等 各个对应位置的字符都相等24.空串是指_，空格串是指_。(题源：宁正元C版题解p40(4.1(填空)_5 )答：不含任何字符的串 仅含空格字符的串 简答题：25已知串s=(xyz)*，t=(x+z)*y，试利用串的基本运算将s串转化为t串，t串转化为s串。(题源：宁正元，C版题解，p40，4.2_3)答：concat ( replace (substring (sub,s,1,5),y,+), replace (substring (sub,s,6,1),*，*y)concat(replace(substring(sub,t,1,5),+,y),replace(substring(sub,t,6,2),*y,*)26串是字符组成的，长度为1的串和字符是否概念相同？为什么？(题源：朱战立，C版题解，p86，4.2.1(典型题解)_2)答：由于字符的长度固定为1，长度概念可以隐含，所以存储时只需存储该字符即可；而长度为1的串其长度概念不能隐含，必须显示地表示出来，所以存储时要同时存储该字符和值为1的长度值。 算法设计题：27设串s和串t采用顺序存储结构，编写函数实现串s和串t的比较操作，要求比较结果包括大于、小于和等于三种情况。解：int StrCompare(SStrType s,SStrType t) int n=s.length, m=t.length, i,j,tag; i=0; j=0; while(in &jt.strj) tag=1; return tag; else tag=-1; return tag; if(n=m) tag=0; else if(nm) tag=1; else if(nm) tag=-1; return tag;28输入一个由若干单词组成的文本行，每个单词之间用若干个空格隔开，统计此文本中单词的个数。 解：int count(r) char r80; char prec,nowc; int num,j; prec= ; num=0; for(j=0;j80;j+) nowc=rj; if(nowc!= )&(prec= ) num+; prec=nowc; return num;29编写算法，求串s所含不同字符的总数和每种字符的个数。(题源：严蔚敏，C版习题集，p29，4.18)解：typedef structchar ch;int num;mytype; void StrAnalyze(Stringtype S) /统计串S中字符的种类和个数 mytype TMAXSIZE; /用结构数组T存储统计结果 for(i=1;i= st.stacksize D st.top = st.base 12.假设顺序栈的定义同上题，变量st为sqstack型，则栈st为满的判断条件为（C ）。A st.base = NULL B st.top = st.stacksizeC st.top-st.base= st.stacksize D st.top = st.base 13判断一个循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 ) 为空队列的条件是( A )。AQU-front = QU-rear BQU-front != QU- rearCQU-front = (QU-rear+1) % m0 DQU-front != (QU-rear+1) % m023.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( B )个。A15 B. 16 C. 17 D.4724. 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组R1.n中，结点Ri若有左子女，则左子女是结点( B )。 AR2i+1 B. R2i C. Ri/2 D. R2i-1(参见严蔚敏(c语言版)数据结构P.124 125,二叉树的性质,性质5)25.设a、b为一棵二叉树上的两个结点。在中序遍历时，a在b前面的条件是( B )。Aa在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙26.以下说法正确的是( C )。A 若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点。B 若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个结点。C 在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点。(