![数据结构与实训[张红霞等主编]习题答案](https://img.doczj.com/imgea/071ft4534e11nsgb74a4-a1.webp)
![数据结构与实训[张红霞等主编]习题答案](https://img.doczj.com/imgea/071ft4534e11nsgb74a4-a2.webp)
第1章习题答案
1. 填空题
（1）在计算机中的存储映像（是逻辑结构在计算机中的实现或存储表示）数据元素的表示元素之间关系的表示数据元素。
（2）已经实现是一个概念分离分离
（3）时、空效率指人对算法阅读理解的难易程度对于非法的输入数据，算法能给出相应的响应，而不是产生不可预料的后果。
（4）软硬件环境问题规模的
（5）最坏
（6）O（n4）O（n2）
（7）时间复杂度
（8）n 2)
1(n
n+
O（n2）
2. 判断题
（1）×（2）×（3）√（4）√（5）√（6）√（7）×（8）×（9）×（10）×3. 简答题
（1）略（见教材第3页的1.2数据结构的基本概念）
（2）（a）n-1，O（n）（b）n-1 , O（n）
（c）11* n+1, O（n）（n为初始值100）
（d）
??n, O（n）（e）n , O（n）
第2章习题及答案
1、填空题
（1）address+m*i
（2）顺序顺序顺序链式存储链式存储
（3）亦相邻不一定
（4）n-i+1
（5）0≤i≤la的长度-1≤j≤lb的长度-1 0≤k≤lc的长度-1
（6）2)
1(n
n+
插入的位置，节点数n（顺序表长度n）
（7）其前驱O(n) O（1）
（8）其前驱O(n) O（1）
（9）p→next=p→next →next
（10）head→next==Null head==Null head→next==head head==Null （11）head→next=head→next→next head=head→next
（12）x=p→prior→data; p→prior→data=p→next→data; p→next→data=x; （13）p==head→prior(或p→next==head)
2．判断题
（1）×（2）√（3）×（4）×（5）×（6）×（7）√（8）×（9）×（10）×3．简答题
(1)
单向循环链表双向循环链表存储密度高低
查找后继的时间复杂度O(1) O(1)
查找前驱的时间复杂度O(n) O(1)
（2）在带头结点的单链表上，查找指针p所指结点的前驱。
（3）交换指针p与指针q所指结点的值。
4．算法设计题
(1)
void reverse(SeqList l)
{ for (i=0; i<=(l.listlength-1)/2; i++)
l.elem[i]<—>l.elem[l.listlength-1-i];
}
(2)
void delete(SeqList, int i, int k)
/*从顺序表中删除自第i个元素开始的k个元素*/
{ if (i<0 || i>l.listlength-1|| k<0)
{ printf(“Error”);
return;
}
if (i+k<=l.listlength) /*表中从i个元素起到最后一个元素有k个元素*/ { for ( j=i+k; j l.elem[j-k]=l.elem[j]; l.listlengt=l.listlength-k; } else /*表中从i个元素起直到最后一个元素不足k个元素*/ l.listlength=i; } (3) void insert(LinkList h, ElementType x) /*将x插入到递增链表h中，插入后的链表有序性不变*/ { if (h→next==Null) /*空表时*/ { q=(linklist) malloc (sizeof(ListNode)); q→next=Null; q→data=x; h→next =q; } p1=h→next; p2=h; while (p1→next != Null && p1→data { p2=p1; p1=p1→next; } if ( p1→next==Null && p1→data { q=(linklist) malloc (sizeof(ListNode)); q→next=Null; q→data=x; p1→next=q; } else /* (p1→next==Null && p1→data>=x) || (p1→next!=Null && p1→data>=x)*/ { q=(LinkList) malloc (sizeof(ListNode); q→data=x; p2→next=q; q→next=p1; } } (4) void delete (LinkList p) /*在不带头结点且长度大于1的单向循环链表中，p指向某结点，删除p的前驱结点*/ { ppp=p→next; while (ppp→next→next != p) ppp =ppp→next; /*删除p的前驱结点*/ pp=ppp→next; ppp→next=pp→next; free(pp); } (5) void delete (LinkList h) /*h为带头结点的，非降序排列的单链表的头指针，删除表中值相同的结点，使之只保留一个*/ { p=h→next; if (!p) return; x=p→data; while (p→next) if (x != p→next→data) { x = p→next→data; p = p→next } else { q=p→next; p→next=p→next→next; free(q); } } void delete (LinkList h) /*删除带头结点的单链表h（指向头结点）中值为x的结点的前驱结点*/ { if (!(h→next )) return; if (!(h→next→next)) return; p1=h→next→next; p2=h; while (p1→next && p1→data != x ) { p1=p1→next; p2=p2→next; } if (p1→data == x) { q=p2→next; p2→next=p1; free(q); } } (7) Linklist subtraction (LinkList la, LinkList lb) /*la,lb分别为表示集合A,B的带头结点的单链表的头指针，A-B由la链表返回*/ { if (!(la→next)) return (la); else { pa1=la→next ; pa2=la; } if (!(lb→next)) return (la); while (pa1) { pb=lb→next ; while (pb && pa1→data!=pb→data) pb=pb→next; if (pb) /*pa1→data==pb→data*/ { pa2→next=pa1→next; free(pa1); pa1=pa2→next; } else { pa1=pa1→next; pa2=pa2→next; } } return (la); } LinkList intersection(LinkList la, LinkList lb) /*la,lb,lc分别为表示集合A,B,C的带头结点的递增有序的单链表的头指针，C=A∩B由lc链表返回*/ { lc=(LinkList) malloc (sizeof(LinkNode)); lc→next=null; tail=lc; /*tail指向lc链的尾结点*/ if (!(la→next)) return(lc); else pa=la→next; if (!(lb→next)) return(lc); while (pa) { pb=lb→next; while (pb && pa→data != pb→data) pb=pb→next; if (pb) insert(lc, tail, pa→data); pa=pa→next; } return(lc); } void insert (LinkList l, LinkList tail, ElemenType x) /*将值x插入到单链表l的尾部*/ { p=(LinkList) malloc (sizeof(LinkNode)) p→data=x; p→next=null; tail→next=p; tail=p; } SeqList intersection(SeqList la, SeqList lb) /*集合A,B,C对应的顺序递增表为la,lb,lc，C=A∩B由lc表示*/ { lc.listlength=0; if (la.listlength==0 || lb.listlength==0) return(lc) for ( a=0; a { for ( b=0; b if (b { lc.elem[lc.listlength]=la.elem[a]; lc.listlength++; } } retuen(lc); } void delete(LinkList h,ElementType min ElementType max) /*h是带头结点的无序单链表的头指针，删除结点值大于min小于max的结点*/ { if (!(h→next)) return; p1=h→next; p2=h; while (p1) if (p1→data>min && p1→data { p2→next=p1→next; free(p1); p1=p2→next; } else { p1=p1→next; p2=p2→next; } } (10) void separation(LinkList h, LinkList *ph1, LinkList *ph2) /*h为带头结点的单链表的头指针，该表中含有两类字符数据元素：字母与数字，拆分h为两条带头结点的单项循环链表*ph1、*ph2，其中*ph1链中存放字母，*ph2链中存放数字*/ { if (!(h→next)) return; p=h→next; free (h); *ph1=(LinkList) malloc (sizeof(LinkNode)); (*ph1)→next=*ph1; *ph2=(LinkList) malloc (sizeof(LinkNode)); (*ph2)→next=*ph2; while (p) { h=p; p=p→next; if ( h→data>=?0? && h→data<=?9?) /*数字字符插入到*ph2链*/ { h→next=(*ph2)→next; (*ph2)→next=h; } else /*字母字符插入到*ph1链*/ { h→next=(*ph1)→next; (*ph1) →next=h; } } } (11) void merge(DoubleList head1, DoubleList head2) /*head1、head2分别为两个带头结点的双向循环链表的头指针，将head1链接到head2*/ { if (head1→next == head1) return; /*head1为空链表*/ head2→prior→next=head1→next; head1→next→prior=head2→prior; head1→prior→next=head2; head2→prior=head1→prior; free (head1); } (12) void delete(DoubleList head, DoubleNode *p) /*head为带头结点的双向循环链表的头指针，p指向head链中的某一个结点，删除p的前驱结点*/ { if (p→prior==head) return; /*p结点无前驱结点*/ q=p→prior; /*q指向p的前驱结点*/ p→prior→prior→next=p; p→prior=p→prior→prior; free (q); } 第3章习题及答案 1．填空题 （1）1，3，5 1 （2）push, pop, push, push, pop, push, pop, pop （3）栈空栈满 （4）O(1) O(1) （5）=s.top-1 =s.top+1 （6）s （7）空 （8）栈底栈顶 （9）队尾队首（头） （10）是否为空是否为满 （11）21 （12）front→next==rear （13）front==rear (rear+1)%MAX==front rear+MAX-frort 2．判断题 （1）√（2）×（3）√（4）√（5）×（6）√（7）√（8）×（9）√（10）√ 3．简答题 （1）当进行入队操作时，队尾指针的值已经到达数组空间的最大下标（MaxSize-1），而队首指针的值却大于0，这时就产生了假溢出现象。 （2）使栈s中的元素顺序置逆。 （3）借助于另一链栈t，使得链栈s去掉指定的元素e。 4．算法设计题 （1） int maxvalue(SeqStack s) /*s是存有整数序列a1,a2,…,an的堆栈，用递归求其中的最大值*/ { if (s.top != -1) if (s.top==0) return(Pop(s)); else { e=Pop(s); return( max(e, maxvalue(s)) ); } } (2) int g( int n) /*递归计算g(n)的值g(n)=1(当n=0)，g(n)=n*g(n/2) (当n>0)*/ { if (n>=0) if (n == 0) return(1); else return( n*g(n/2) ); } (3) 11 11g(5) n g 5 5g(2) 11 11g(5) n g 5 5g(2) 11 11g(5) n g 2 2g(1) 5 5g(2) 11 11g(5) n g 2 2g(1) 1 1g(0) 5 5g(2) 11 11g(5) n g 2 2g(1) 1 1g(0) 0 1 5 5g(2) 11 11g(5) n g 2 2 5 10 11 11g(5) n g 11 110 n g 5 5g(2) 11 11g(5) n g 2 2g(1) 1 1 int akm( int m, int n) /*递归计算akm( m, n)的值*/ { if (m>=0 && n>=0) if (m==0) return(n+1); else if (n==0) return( akm(m-1,1) ); else return( akm(m-1,akm(m,n-1)) ); } (4) (5) 对于输入序列1,2,3,4,对应的24种排列是： 1,2,3,4 1,2,4,3 1,3,2,4 1,3,4,2 1,4,2,3 1,4,3,2 $ stackd stackr $ stackd 3 stackr $ stackd 3 * stackr $ stackd stackr $ stackd 3 stackr $ stackd 3 * stackr $ stackd 3 * * ( 5 * ( - ( 5 - ( 3 5 2 stackr $ stackd * ( 3 3 stackr $ stackd * 3 3 stackr $ stackd 9 stackr $ stackd + 9 stackr $ stackd 9 (a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k) (l) (m) stackr + 7 stackr $ stackd 16 2,1,3,4 2,1,4,3 2,3,1,4 2,3,4,1 2,4,1,3 2,4,3,1 3,1,2,4 3,1,4,2 3,2,1,4 3,2,4,1 3,4,1,2 3,4,2,1 4,1,2,3 4,1,3,2 4,2,1,3 4,2,3,1 4,3,1,2 4,3,2,1 无下划线的序列可以通过相应的入、出栈得到。可以通过入、出栈得到的输出序列中的每一个数，在它后面的比它小的数应是降序排列的。 (6) void AddQueue(Queue q, ElementType e) /*入队*/ { if (q.count == maxsige) { printf (“\n overflow”); return; } q.elem[(q.front+q.count) % MaxSize]=e; q.count++; } ElementType DeleteQueue(Queue q) /*出队*/ { if (q.count==0) return(nil); e=q.elem[q.front]; q.front=(q.front+1) % MaxSize; q.count--; return(e); } (7) ①A,D是合法的 ② int legality(SeqList l) /*入、出栈序列存放在l.elem[]数组中，该序列合法返回1，否则返回0*/ { count=0; for (i=0; i if (l.elem[i]==?I? count++; else { count--; if (count<0) return(0); /*栈空时出栈*/ } if (count==0) return(1); else return(0); /*栈不空（没有回到初始状态*/ } （8） typedef struct Qnode { ElementType data; Struct Qnode *next; } QueueNode; typedef QueueNode *LinkQueue; void AddQueue(LinkQueue rear, ElementType e) /*带头结点的循环链表队列，只有指向尾结点的指针rear，对其实现入队操作*/ { p=(LinkQueue) malloc (sizeof(QueueNode)); p→data=e; p→next=rear→next; rear→next=p; rear=p; } Elementype DeleteQueue(LinkQueue rear) /*带头结点的循环链表队列，只有指向尾结点的指针rear，对其实现出队操作*/ { if( rear→next==rear) { printf(“\n empty”); return(nil); } p=rear→next→next; e=p→data; rear→next→next=rear→next→next→next; free(p); return(e); } (9) ① void AddQueue(CirQueue q, ElementType e) /*借助于堆栈s1、s2实现队列q的入队*/ { Push (s1,e); } ② ElementType DeleteQueue(CirQueue q) /*借助于堆栈s1、s2实现队列q的出队*/ { if (Empty(s1) && Empty(s2)) { printf(“\n empty”); return(nil); } else if ( !Empty(s2) ) Pop (s2); else { while( !Empty(s1) ) Push (s2, Pop(s1) ); Pop(s2); } } 第4章 习题及答案 1. 填空题 （1）字符 （2）0 空格的个数 （3）14 “bc cad cabcadfabc ” “abc ” 8 1(true) “bc cad cbcadf ” “abcbc cad cabcadf ” “bcad cabcadf ” （4）197 （5）三维数组arr[6][2][3]的每个元素的长度为4个字节，如果数组以行优先的顺序存储，且第1个元素的地址是4000，那么元素arr[5][0][2]的地址是4000+4*（5*2*3+0*3*2）=4128 2. 判断题 （1）×（2）√（3）×（4）√（5）√（6）√（7）×（8）√（9）×（10）√ 3. (1) 0(1)1(i j 2i j-1i j u =+= = =?? ???当 当 ）（当 ） v=j (2) 符号表 堆 0 1 2 3 4 5 6 7 8 9 10 11 a b c x a b c y z x a b c y z ↑ free （3）最坏情况下的时间复杂度为O （m*n ），其中m 为串s 的长度，n 为串t 的长度 （4）三维数组arr[6][2][3]的每个元素的长度为4个字节，该数组要占6*2*3*4=144个字节，若数组以列优先的顺序存储，设第一个元素的首地址是4000，则元素arr[5][0][2]的存储地址是4029。 （5） s 3 0 t 5 3 u 7 8 … ① (5)()5 j l k l i j == -+ --∑ ② ((0,0,1),(0,3,2),(1,1,3),(2,3,5),(3,0,2),(3,2,5)) (6) 行优先： a 0,0,0,0 a 0,0,0,1 a 0,0,0,2 a 0,0,1,0 a 0,0,1,1 a 0,0,1,2 a 0,1,0,0 a 0,1,0,1 a 0,1,0,2 a 0,1,1,0 a 0,1,1,1 a 0,1,1,2 a 0,2,0,0 a 0,2,0,1 a 0,2,0,2 a 0,2,1,0 a 0,2,1,1 a 0,2,1,2 a 1,0,0,0 a 1,0,0,1 a 1,0,0,2 a 1,0,1,0 a 1,0,1,1 a 1,0,1,2 a 1,1,0,0 a 1,1,0,1 a 1,1,0,2 a 1,1,1,0 a 1,1,1,1 a 1,1,1,2 a 1,2,0,0 a 1,2,0,1 a 1,2,0,2 a 1,2,1,0 a 1,2,1,1 a 1,2,1,2 列优先： a 0,0,0,0 a 1,0,0,0 a 0,1,0,0 a 1,1,0,0 a 0,2,0,0 a 1,2,0,0 a 0,0,1,0 a 1,0,1,0 a 0,1,1,0 a 1,1,1,0 a 0,2,1,0 a 1,2,1,0 a 0,0,0,1 a 1,0,0,1 a 0,1,0,1 a 1,1,0,1 a 0,2,0,1 a 1,2,0,1 a 0,0,1,1 a 1,0,1,1 a 0,1,1,1 a 1,1,1,1 a 0,2,1,1 a 1,2,1,1 a 0,0,0,2 a 1,0,0,2 a 0,1.0,2 a 1,1,0,2 a 0,2,0,2 a 1,2,0,2 a 0,0,1,2 a 1,0,1,2 a 0,1,1,2 a 1,1,1,2 a 0,2,1,2 a 1,2,1,2 (7) 稀疏矩阵压缩存储后会失去随机存取的功能，因为稀疏矩阵不能根据元素在矩阵中的位置求得在其在三元组顺序表中的位置，而特殊矩阵则可以。 (8)当3t n m t < 时，三元组的表示才有意义。 (9) ① i=j 或 i+j=n+1 ② 2(1)()2(1)1i j 1i i j k i n - =?=? -+ +=+?当 （当 ） 4、算法设计题 （1） void Assign(BlockLink *s, char t[]) /*将存放在字符数组t 中常量赋给s*/ { ss=s; for(i=0; t[0]!=?\0?; i++) { if ( i % NodeNum == 0 ) { j=0; p=(BlockLink*) malloc (sizeof(BlockLink)); p →next=Null; ss →next=p; ss=p; } p →data[j]=t[i]; j++; } while (j!=NodeNum-1) { p→data[j]=?#?; j++; } } （2） void frequency(int num[]) /* 统计输入字符串中数字字符和字母字符的个数。*/ ｛ for（i＝0；i<26；i++）num[i]＝０；/* 初始化*/ while（（ch＝getchar（））!=‘#’）/* ‘#’表示输入字符串结束。*/ if（ch >= …a’&& ch <= …z’）/* 小写字母*/ ｛i=ch－97; num[i]++； ｝ else if（ch >= …A’&& ch <= …Z’）/* 大写字母*/ ｛i=ch-65+10; num[i]++； ｝ ｝ （3） ① int JudgEqual(ing a[][],int m,int n) /*判断二维数组中所有元素是否互不相同，如是，返回1；否则，返回0。*/ { for(i=0; i for(j=0; j { for(p=j+1; p if(a[i][j]==a[i][p]) return(0); for(k=i+1; k for(p=0; p if(a[i][j]==a[k][p]) return(0); } return(1); /*元素互不相同*/ } ② 二维数组中的每一个元素同其它元素都比较一次，数组中共m*n个元素，第1个元素同其它m*n-1个元素比较，第2个元素同其它m*n-2 个元素比较，……，第m*n-1个元素同最后一个元素(m*n)比较一次,所以在元素互不相等时总的比较次数为(m*n-1)+(m*n-2)+…+2+1=（m*n）(m*n-1)/2。在有相同元素时,可能第一次比较就相同,也可能最后一次比较时相同,设在每个位置上均可能相同,这时的平均比较次数约为（m*n）(m*n-1)/4，总的时间复杂 度是O(m2*n2)。 （4） #define MaxSize 线性表可能的最大长度 typedef struct { int row, column; } element typedef struct { element elem[MaxSize]; int listlength; } SeqList; void GetSaddle(int A[]，int m，int n, SeqlList s[]) /*求矩阵A m×n中的鞍点，鞍点的位置存放在顺序表s中*/ { s.listlength=0; for(i=0; i { for(min=A[i][0], j=0; j if(A[i][j] for(j=0; j if(A[i][j]==min) /*判断这个(些)最小值是否鞍点*/ { for(flag=1, k=0; k if(min if(flag) /*是鞍点*/ { s.elem[listlength].row=i; s.elem[listlength].column=j; s.listlength ++; } } } } （5） [题目分析]矩阵中元素按行和按列都已排序，要求比较次数不超过m+n，因此不能采用常规的二层循环的查找。可以先从右上角（i=0,j=n）元素与x比较，只有三种情况：一是A[i,j]>x，这情况下向j 小的方向继续查找；二是A[i,j] void search(ElementType A[][],int m,int n,ElementType x,int *row,int *column) /* m*n的矩阵b,本算法查找x在矩阵b中的位置（*row,*column）*/ { i=0; j=n; flag=0; /*flag是成功查到x的标志*/ while(i<=m && j>=0 && !flag) if(b[i][j]==x) flag=1; else if (b[i][j]>x) j--; else i++; if(flag) { *row=i; *column=j; } else { *row=-1; *column=-1; } } [算法讨论]算法中查找x的路线从右上角开始，向下（当x>b[i,j]）或向左（当x （6） void TSMatrix_Addto(TSMatrix &A,TSMatrix B)//将三元组矩阵B加到A上 { for(i=0;i /*把A的所有元素都移到尾部以腾出位置*/ A.data[MaxSize-A.nums+i]=A.data[i]; pa=MaxSize-A.nums; pb=0; pc=0; for(x=0; x { while(A.data[pa].r pa++; while(B.data[pb].r pb++; while(A.data[pa].r==x && B.data[pb].r==x)/*行值相等的元素*/ { if(A.data[pa].c==B.data[pb].c) /*列值也相等*/ { ne=A.data[pa].d+B.data[pb].d; if(ne) /*和不为0*/ { A.data[pc].r=x; A.data[pc].c=A.data[pa].c; A.data[pc].d=ne; pa++; pb++; pc++; } } else if(A.data[pa].c>B.data[pb].c) { A.data[pc].r=x; A.data[pc].c= B.data[pb].c; A.data[pc].d= B.data[pb].d; pb++; pc++; } else { A.data[pc].r=x; A.data[pc].c=A.data[pa].c; A.data[pc].d=A.data[pa].d pa++; pc++; } } while(A.data[pa]==x) /*插入A中剩余的元素(第x行)*/ { A.data[pc].r=x; A.data[pc].c=A.data[pa].c; A.data[pc].d=A.data[pa].d pa++; pc++; } while(B.data[pb]==x) /*插入B中剩余的元素(第x行)*/ { A.data[pc].r=x; A.data[pc].c= B.data[pb].c; A.data[pc].d= B.data[pb].d; pb++; pc++; } } A.nums=pc; for(i=A.nums; i /*清除原来A中的元素*/ { A.data[i].r=-1; A.data[i].c=-1; A.data[i].d=nil; } } 第5章习题答案 1.填空题 (1) a a m,n,d,j,k,l,f c a,c j,k i,m,n d g,h 2 5 5 3 3 (2)非线性 根 双亲 (3)5 (4)n 2+1 (5)完全 log 2n +1 最大 n (6)2k -1 2k-1 2k -1 (7)2n n-1 n+1 (8)a 在b 的左边 (9)2m-1 (10)58 2.判断题 （1）×（2）×（3）×（4）√（5）√（6）√（7）√（8）√（9）√（10）√ 3.简答题 （1）双亲数组表示法： 孩子链表表示法： data parent 0 a -1 1 b 0 2 c 0 3 d 1 4 e 1 5 f 2 6 g 2 7 h 2 8 i 4 9 j 6 10 k 6 11 l 7 12 m 8 13 n 8 孩子兄弟表示法： （2）能唯一确定这棵二叉树。二叉树为： 若给定先序序列和后序序列无法唯一确定一棵二叉树，因为根据先序序列虽可以确定根，但不可以根据后序序列确定左子树和右子树。如下面两棵二叉树，它们的先序序列和后序序列相同，但却确定了两棵不同的二叉树。 1 2 Λ 0 a 1 b 2 c 3 d Λ 4 e 5 f Λ 6 g 7 h 8 i 9 j Λ 10 k Λ 11 l Λ 12 m Λ 13 Λ n 3 4 Λ 5 6 7 Λ 8 Λ 9 10 Λ 12 13 Λ 11 Λ a Λ b c Λ root Λ d e Λ i Λ Λ m Λ n Λ Λ f g h Λ Λ j Λ l Λ Λ k Λ A C B D E I F G H J （3）总结点数n= n 0+ n 1+ n 2+…+ n m-1+ n m ① 因为度为1的结点发出1个分支，度为2的结点发出2个分支，…，度为m 的结点发出m 个分支，叶结点不发出分支，所以，总分支数B 为：B= n 1+ 2n 2+…+ m* n m ② 又因除根之外，其它结点有且仅有一个分支进入，因此，总分支数应等于总结点数减1，即 B=n-1 ③ 由②③得：n= n 1+ 2n 2+…+ m* n m +1 ④ 由①④得叶结点数：n 0= n 2+2n 3…+ （m-1）*n m 非终端结点数为：n 1+ n 2+…+ n m-1+ n m （4）①a.空二叉树； b.只有一个根结点的二叉树 c.任一结点均无左子树的非空二叉树 ②a.空二叉树； b.只有一个根结点的二叉树 c.任一结点均无右子树的非空二叉树 ③a.空二叉树； b.只有一个根结点的二叉树 （5）①第i 层的结点数为k i -1（其中i=1，2，…，h ） ②当i 不等于1时，i 的双亲为 （i-2）/k +1（其中k>=2） ③编号为i 的非叶子结点的第j 个孩子结点的编号是(i-1)*k+j+1。 ④编号为i 的结点有右兄弟的条件是(i-1)%k<>0，其右兄弟的编号是i+1。 （6）（a ）先序序列：12345 中序序列：24531 后序序列：54321 （b ）先序序列：12345 中序序列：13542 后序序列：54321 （c ）先序序列：123578624 中序序列：17583624 后序序列：78563421 （d ）先序序列：124735689 中序序列：472153869 后序序列：742589631 先序线索树：中序线索树：后序线索树： （7）①a 的先序序列：ABCDEF a 的后序序列：BDEFCA b 的先序序列：GHIJK b 的后序序列：IJKHG A B B A C C 1 3 2 4 7 6 5 9 8 1 3 2 4 7 6 5 9 8 NULL 1 3 2 4 7 6 5 9 8 NULL NULL NULL 先序线索树 中序线索树 后序线索树 第一章绪论 选择题 1.组成数据的基本单位是（） （A）数据项（B）数据类型（C）数据元素（D）数据变量 2.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（） （A）动态结构和静态结构（B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ①（A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ②（A）结构（B）关系（C）运算（D）算法 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5个特性。 ①（A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法 ②（A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性 二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 3.数据元素是数据的最小单位。（） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。 3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。 4.在图形结构中,每个结点的前驱结点数和后续结点数可以_________。 5.线性结构中元素之间存在________关系,树形结构中元素之间存在______关系,图形结构中元素之间存在_______关系。 6.算法的五个重要特性是_______、_______、______、_______、_______。 7.数据结构的三要素是指______、_______和________。 8.链式存储结构与顺序存储结构相比较,主要优点是________________________________。 9.设有一批数据元素,为了最快的存储某元素,数据结构宜用_________结构,为了方便插入一个元素,数据结构宜用____________结构。 四、算法分析题 1.求下列算法段的语句频度及时间复杂度参考答案： 选择题1. C 2.C 3. C 4. A、B 5. C 6.C、B 栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 第一章 1．在数据结构中，从逻辑上可以把数据结构分为（C ） A．动态结构和静态结构 B. 紧凑结构和非紧凑结构 C．线性结构和非线性结构 D. 内部结构和外部结构 ● 2.在数据结构中,与所使用的计算机无关的是( A ) A. 逻辑结构 B. 存储结构 C. 逻辑和存储结构 D. 物理结构 3.下面程序的时间复杂度为____O（mn）_______。 for (int i=1; i<=m; i++) for (int j=1; j<=n; j++ ) S+=i 第二章线性表 ●链表不具备的特点是（A） A 可以随机访问任一结点（顺序） B 插入删除不需要移动元素 C 不必事先估计空间 D 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件为（A ），带头结点的单链表head为空的判定条件为（B ） A head==null B head->next==null C head->next==head D head!=null ●3.在线性表的下列存储结构中，读取元素花费时间最少的是（D） A 单链表 B 双链表 C 循环链表 D 顺序表 ● 4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为(C) A 顺序表 B 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 D 单链表 ● 5.在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序， 则操作的时间复杂度为( D ) A O(1) B O(log2n) C O(n2) D O(n) ● 6.在一个长度为n (n>1)的单链表上，设有头和尾两个指针，执行(B)操作与链表的长 度有关 A 删除单链表中第一个元素 B 删除单链表中最后一个元素 C 在第一个元素之前插入一个新元素 D 在最后一个元素之后插入一个新元素 ●7.与单链表相比，双向链表的优点之一是(D) A 插入删除操作更简单 B 可以进行随机访问 C 可以省略表头指针或表尾指针 D 顺序访问相邻结点更容易 ●8.若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域 (头结点的地址)中存放的是( B ) A list的地址 B list的内容 C list指的链结点的值 D 链表第一个链结点的地址 ●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针，则( B ) A list2比list1占用更多的存储单元 B list1与list2占用相同的存储单元 C list1和list2应该是相同类型的指针变量 D 双向链表比单链表占用更多的存储单元 10.链表中的每个链结点占用的存储空间不必连续，这句话正确吗？ (不正确) 11. 某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。V 100+4*12=148 11.在顺序表的（最后一个结点之后）插入一个新的数据元素不必移动任何元素。 12.若对线性表进行的操作主要不是插入删除，则该线性表宜采用（顺序）存储结构，若频繁地对线性表进行插入和删除操作，则该线性表宜采用( 链 )存储结构。 数据结构模拟卷(含答案)经典习题 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( ) 填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/ 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2 第一章绪论 一、选择题 1.组成数据的基本单位是（） （A）数据项（B）数据类型（C）数据元素（D）数据变量 2.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（） （A）动态结构和静态结构（B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ② （A）结构（B）关系（C）运算（D）算法 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5 个特性。 ① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法 ② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性 二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 3.数据元素是数据的最小单位。（） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。 3.在树形结构中,树根结点没有_______结点,其余每个结点有且只 有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。 4.在图形结构中,每个结点的前驱结点数和后续结点数可以 _________。 5.线性结构中元素之间存在________关系,树形结构中元素之间存 在______关系,图形结构中元素之间存在_______关系。 6.算法的五个重要特性是_______、_______、______、_______、 数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i 第 1 章绪论 课后习题讲解 1、填空 ⑴( )就是数据的基本单位,在计算机程序中通常作为一个整体进行考虑与处理。 【解答】数据元素 ⑵( )就是数据的最小单位,( )就是讨论数据结构时涉及的最小数据单位。 【解答】数据项,数据元素 【分析】数据结构指的就是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲,数据结构主要分为( )、( )、( )与( )。 【解答】集合,线性结构,树结构,图结构 ⑷数据的存储结构主要有( )与( )两种基本方法,不论哪种存储结构,都要存储两方面的内容:( )与( )。 【解答】顺序存储结构,链接存储结构,数据元素,数据元素之间的关系 ⑸算法具有五个特性,分别就是( )、( )、( )、( )、( )。 【解答】有零个或多个输入,有一个或多个输出,有穷性,确定性,可行性 ⑹算法的描述方法通常有( )、( )、( )与( )四种,其中,( )被称为算法语言。 【解答】自然语言,程序设计语言,流程图,伪代码,伪代码 ⑺在一般情况下,一个算法的时间复杂度就是( )的函数。 【解答】问题规模 ⑻设待处理问题的规模为n,若一个算法的时间复杂度为一个常数,则表示成数量级的形式为( ),若为 n*log25n,则表示成数量级的形式为( )。 【解答】Ο(1),Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度,需要将低次幂去掉,将最高次幂的系数去掉。 2、选择题 ⑴顺序存储结构中数据元素之间的逻辑关系就是由( )表示的,链接存储结构中的数据元素之间的逻辑关系就是由( )表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C,D 【分析】顺序存储结构就就是用一维数组存储数据结构中的数据元素,其逻辑关系由存储位置(即元素在数组中的下标)表示;链接存储结构中一个数据元素对应链表中的一个结点,元素之间的逻辑关系由结点中的指针表示。 《数据结构》课程设计题目 (程序实现采用C语言) 题目1：猴子选王（学时：3） 一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == n) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; 第八章查找 一、判断题 1.用二分查找法对一个顺序表进行查找，这个顺序表可以是按各键值排好序的，也可以是没有按键值排好序的。（） 2.哈希表的查找不用进行关键字的比较。（） 3.哈希表的定义函数H（key）=key%p(p<=m)这种方法是直接定址法。（） 4.装填因子α的值越大，就越不容易发生冲突。( ) 5.选择hash函数的标准为：随机性好、均匀性好和尽量避免冲突。( ) 参考答案：1、×2、×3、×4、×5、√ 二、填空题 1.顺序查找法的平均查找长度为__________，二分查找法的平均查找长度为________，分块查找法(以顺序查找确定块)的平均查找长度为__________，分块查找法(以二分查找确定块〉的平均查找长度为_________，哈希表查找法采用链接法处理冲突时的平均查找长度为_________。 (n+1)/2；((n+1)*log2(n+1))/n-1；(s2+2s+n)/2s；log2(n/s+1)+s/2；1+α 2.在各种查找方法中,平均查找长度与结点个数n无关的查法方法是_________ 哈希表查找 3.二分查找的存储结构仅限于_________,且是__________。 顺序；有序的 4.在分块查找方法中,首先查找__________,然后再查找相应的___________。 索引；块 5.长度为255的表,采用分块查找法,每块的最佳长度是____________。 15 6.在散列函数H(key)=key%p中,p应取_______________。 小于表长的最大素数 7.假设在有序线性表A[1..20]上进行二分查找,则比较一次查找成功的结点数为 _________,则比较二次查找成功的结点数为__________,则比较三次查找成功的结点数为 _________,则比较四次查找成功的结点数为________,则比较五次查找成功的结点数为 _________,平均查找长度为_________。 ①1 ②2 ③4 ④8 ⑤5 ⑥3.7 数据结构经典例题 1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。 void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; //p指向第1个数据节点 L1=L; //L1利用原来L的头节点 r1=L1; //r1始终指向L1的尾节点 L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点 L2->next=NULL; //置L2的指针域为NULL while (p!=NULL) { r1->next=p; //采用尾插法将*p(data值为ai)插入L1中 r1=p; p=p->next; //p移向下一个节点(data值为bi) q=p->next; //由于头插法修改p的next域,故用q保存*p的后继节点 p->next=L2->next; //采用头插法将*p插入L2中 L2->next=p; p=q; //p重新指向ai+1的节点 } r1->next=NULL; //尾节点next置空 } 2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。 typedef struct LNode {int data; struct LNode *link; } *LinkList; int Searchk(LinkList list,int k) { LinkList p,q; int count=0; p=q=list->link; while (p!=NULL) { if (count 第1章算法 一、选择题 1.算法的时间复杂度是指（）。 A）执行算法程序所需要的时间 B）算法程序中的指令条数 C）算法执行过程中所需要的基本运算次数 D）算法程序的长度 2.算法的空间复杂度是指（）。 A）算法程序的长度 B）算法程序所占的存储空间 C）算法执行过程中所需要的存储空间 D）算法程序中的指令条数 3.下面（）的时间复杂度最好（即执行时间最短）。 log) A）O(n ) B）O(n 2 log ) D）O(n2) C）O(n n 2 4.下面累加求和程序段的时间复杂度为（）。 int sum(int a[],int n) { int i, s=0; for (i=0;i int i=0,s1=0,s2=0; while(i 基本概念典型例题 一、单项选择题 [例6-1]数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是( ①)的有穷集合，R是D上( ②)的有限集合。 ①A.算法B. 数据元素C. 数据操作D. 逻辑结构 ②A. 操作B. 映像C. 存储D．关系 解析：由数据结构的集合形式化定义可知，本题答案为：①B；②D。 [例6-2]数据的常用存储结构中不包括( )。 A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。 [例6-3] 算法指的是( ①)，它必须具备( ②)这三个特性。 ①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法 ②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性D．易读性、稳定性、安全性 解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它 必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本 题答案为：①㈠②B。 [例6-4] 在下面的程序段中，对x的赋值语句的执行频度为( )。 for(i=0；i 1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998 三、1 （5分）】 LinkedList Union(LinkedList la,lb) { pa=la->next; pb=lb->next; la->next=null; while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data) { r=pa->next; pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。 la->next=pa; pa=r; } else {r=pb->next; pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb; pb=r; } while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb!=null) {r=pb->next; pb->next=la->next; la->next=pb; pb=r; } } 1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997 四、3（15分）】 LinkedList Union(LinkedList ha, hb)∥ha和hb是两个无头结点的数据域值递增有序的单链 ｛LinkedList 表，本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏hb链表。 la; la=(LinkedList)malloc(sizeof(LNode)); la->next=ha; pa=ha; pb=hb; pre=la; while(pa&&pb) if(pa->data 习题八查找 一、单项选择题 1．顺序查找法适合于存储结构为（）的线性表。 A．散列存储 B. 顺序存储或链式存储 C. 压缩存储 D. 索引存储 2.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 3．适用于折半查找的表的存储方式及元素排列要求为( ) A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 4．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( ) A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减5．当采用分块查找时，数据的组织方式为 ( ) A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 6．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（）。 A．正确 B. 错误 7. 二叉查找树的查找效率与二叉树的(（1） )有关, 在 (（2） )时其查找效率最低。 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 8．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。 A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性 9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。 A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110) 10．下图所示的4棵二叉树,( )是平衡二叉树。 （A）（B）（C）（D） 11．散列表的平均查找长度（）。 A．与处理冲突方法有关而与表的长度无关 B．与处理冲突方法无关而与表的长度有关 C．与处理冲突方法有关且与表的长度有关 D．与处理冲突方法无关且与表的长度无关 12. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（）个 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i数据结构习题及答案——严蔚敏_课后习题答案 精品
经典数据结构面试题(含答案)
数据结构习题及答案精编版
数据结构模拟卷(含答案)经典习题培训讲学
数据结构课后习题及答案
数据结构模拟卷(含答案)经典习题
数据结构习题及答案——严蔚敏
经典数据结构上机题_答案解析
数据结构习题与答案
数据结构经典题目c语言代码
数据结构习题及答案 (1)
数据结构经典例题
数据结构习题及答案概论
数据结构典型例题
数据结构经典算法试题
数据结构习题及答案
数据结构课后习题详解(超完整,超经典)
数据结构试题及答案
相关主题
文本预览