数据结构C语言版章节练习题(1-6章)

1、数据结构章节练习题第一章绪论一、单选题1. 一个数组元素ai与的表示等价。A、*(a+i)B、a+iC、*a+iD、&a+i2. 下面程序段的时间复杂度为。for(inti=0;i<m;i+)for(intj=0;j<n;j+)aij=i*j;A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)3. 执行下面程序段时，执行S语句的次数为。for(inti=1;i<=n;i+)for(intj=1;j<=i;j+)S;n(n+1)/2A、n2B、n2/2C、n(n+1)D4. 下面算法的时间复杂度为。intf(unsignedintn)if(n=0|n=1

2、)return1;elsereturnn*f(n-1);A 、 O(1) B 、 O(n) C 二、填空题1. 数据的逻辑结构被分为O(n2) D 、 O(n!)_ 、 和四种5. 数据的存储结构被分为、和两种。6. 在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着和的联系。7. 一种抽象数据类型包括和两个部分。8. 当一个形参类型的长度较大时，应最好说明为，以节省参数值的传输时间和存储参数的空间。9. 当需要用一个形参访问对应的实参时，则该形参应说明为。10. 在函数中对引用形参的修改就是对相应的修改，对形参的修改只局限在该函数的内部，不会反映到对应的实参上。11. 当需要进行

3、标准I/O操作时，则应在程序文件中包含头文件，当需要进行文件I/O操作时，则应在程序文件中包含头文件。12. 包含有头文件的程序文件中，使用能够产生出020之间的一个随机整数。13. 一个数组a所占有的存储空间的大小即数组长度为，下标为i的元素ai的存储地址为，或者为。14. 从一维数组an中顺序查找出一个最大值元素的时间复杂度为，输出一个二维数组bmn中所有元素值的时间复杂度为。15. 在下面程序段中，s=s+p语句的执行次数为，p*=j语句的执行次数为，该程序段的时间复杂度为。inti=0,s=0;while(+i<=n)intp=1;for(intj=1;j<=i;j+)p*

4、=j;s=s+p;16. 一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n),其数量级表示为第二章线性表、单选题1 .在一个长度为n的顺序存储线性表中，向第i个元素(1<i<n+1)之前插入一个新元素时，需要从后向前依次后移个元素。A、n-iB、n-i+1C、n-i-1D、i2 .在一个长度为n的顺序存储线性表中，删除第i个元素(1<i<n+1)时，需要从前向后依次前移元素。A、n-iB、n-i+1C、n-i-1D、i3 .在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度(即x同元素的平均比较次数，假定查找每个元素的概率都相等)为。

5、、n/2 C、(n+1)/2 D 、(n-1)/24 .在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行A、HL=p;p->next=HL;B、p->next=HL;HL=p;C、p->next=HL;p=HL;D、p->next=HL->next;HL->next=p;5 .在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行。A、q->next=p->next;p->next=q;B、p->next=q->next;q=p;C、q->next=p->next;p-&g

6、t;next=q;D、p->next=q->next;q->next=p;6 .在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行。A、p=q->next;p->next=q->next;B、p=q->next;q->next=p;C、p=q->next;q->next=p->next;D、q->next=q->next->next;q->next=q;二、填空题1 .在线性表的单链式存储结构中，每个结点包含有两个域，一个叫域，另一个叫域C2 .在下面数组a中链式存储着一个线性表，表头指针为

7、a0.next,则该线性表为。3 .对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为,在表尾插入元素的时间复杂度为O4 .对于一个长度为n的单链式存储的线性表，在表头插入元素的时间复杂度为，在表尾插入元素的时间复杂度为o5 .在线性表的顺序存储中，若一个元素的下标为i,则它的前驱元素的下标为,后继元素的下标为O6 .在线性表的单链式存储中，若一个元素所在结点的地址为p,则其后继结点的地址为若假定p为一个数组a中的下标，则其后继结点的下标为o7 .在循环单链表中，最后一个结点的指针指向结点。8 在双向链表中每个结点包含有两个指针域，一个指向其结点，另一个指向其结点。9 在循环双向

8、链表中表头结点的左指针域指向结点，最后一个结点的右指针域指向_结点。10 .在以HL为表头指针的带表头结点的单链表和循环单链表中，链表为空的条件分别为和。三、应用题11 在下面的每个程序段中，假定线性表La的类型为List，元素类型ElemType为int，并假定每个程序段是连续执行的，试写出每个程序段执行后所得到的线性表La。(1) InitList(La);inta=48,26,57,34,62,79;for(i=0;i<6;i+)InsertFront(La,ai);TraverseList(La);(2) InitList(La);for(i=0;i<6;i+)Insert

9、(La,ai);TraverseList(La);(3) ClearList(La);for(i=0;i<6;i+)InsertRear(La,ai);Delete(La,a5);Sort(La);Insert(La,a5/2);TraverseList(La);3对于List类型的线性表，编写出下列每个算法。(1) 从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补，若线性表为空则显示出错信息并退出运行。(2) 从线性表中删除第i个元素并由函数返回。(3) 向线性表中第i个元素位置插入一个元素。(4) 从线性表中删除具有给定值x的所有元素。4对于结点类型为LNod

10、e的单链表，编写出下列每个算法。(1) 删除单链表中的第i个结点。(2) 在有序单链表中插入一个元素x的结点。(3) 从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息并停止运行。(4) 统计出单链表中结点的值等于给定值x的结点数。一、单选题1栈的插入与删除操作在A 、栈顶B 、栈底第三章 栈和队列进行。C 、任意位置D 、指定位置精选文档2 当利用大小为N的一维数组顺序存储一个栈时，假定用top=0表示栈空，则向这个栈插入一个元素时，需要执行语句修改top指针。A、top+B、top-C、top=0D、top3若让元素1，2，3依次进栈，则出栈次序不可能出现种情况

11、。A、3，2，1B、2，1，3C、3，1，2D、1，3，2位置。4在一个循环顺序队列中，队首指针指向队首元素的A 、前一个B 、后一个C 、当前D 、后面5当利用大小为N的一维数组顺序存储一个循环队列时，该队列的最大长度为。A、N-2B、N-1C、ND、N+16从一个循环顺序队列删除元素时，首先需要。A、前移一位队首指针B、后移一位队首指针C、取出队首指针所指位置上的元素D、取出队尾指针所指位置上的元素7假定一个循环顺序队列的队首和队尾指针分别为f和r，则判断队空的条件是。A、f+1=rB、r+1=fC、f=0D、f=r8假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件

12、是。A、front=rearB、front!=NULLC、rear!=NULLD、front=NULL二、填空题1队列的插入操作在进行，删除操作在进行。2栈又称为表，队列又称为表。3向一个顺序栈插入一个元素时，首先把待插入元素到这个位置上然后，使后移一个位置。4从一个栈中删除元素时，首先前移一位，然后再取出。5在一个循环顺序队列Q中，判断队空的条件为，判断队满的条件为。6在一个顺序栈中，若栈顶指针等于，则为空栈；若栈顶指针等于，则为满栈。7.在一个链栈中，若栈顶指针等于NULL.,则为;在一个链队中，若队首指针与队尾指针的值相同，则表示该队列为。8向一个链栈插入一个新结点时，首先把新结点的存储

13、位置赋给，然后把栈顶指针指向。9从一个链栈中删除一个结点时，需要把栈顶结点的值赋给。10 向一个顺序队列插入元素时，需要首先向插入新元素，然后再移动。11 当用长度为N的一维数组顺序存储一个栈时，假定用top=0表示栈空，则表示栈满的条件为。12 向一个栈顶指针为HS的链栈中插入一个新结点*P果，应执行和操作。13 从一个栈顶指针为HS的非空链栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行操作。14 假定front和rear分别为一个链队的队首和队尾指针，则该链队中只有一个结点的条件为三、应用题执行下面函数调用后得到的输出结果是什么？voidAF(Queue&Q)InitQu

14、eue(Q);inta4=5,8,12,15;for(inti=0;i<4;i+)QInsert(Q,ai);QInsert(Q,QDelete(Q);QInsert(Q,30);QInsert(Q,QDelete(Q)+10);while(!QueueEmpty(Q)printf(“%d”,QDelete(Q);第四章稀疏矩阵和广义表一、单选题1. 在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的。A、行号B、列号C、元素值D、地址二、填空题2. 在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的、和三项。3. 在稀疏矩阵所对应的三元组线性表中，每个三元组元

15、素按为主序、为辅序的次序排列。4. 在初始化一个稀疏矩阵的函数定义中，矩阵形参应说明为参数。5. 在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应对应三元组线性表的长度。第五章树和二叉树(一)一、填空题1对于一棵具有n个结点的树，该树中所有结点的度数之和为。2假定一棵三叉树的结点个数为50，则它的最小深度为，最大深度为。3在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有个。个，一棵深度为 3 的满三叉树中的结点数为4一棵深度为5的满二叉树中的结点数为个。个，则度为3、 2、1、 0 的结点数分别为，则结点H 的双亲结点为

16、，5假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)树的深度为，树的度为。6假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)、和个。7假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)孩子结点为。8在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为个。9对于一棵二叉树，若一个结点的编号为i，则它的左孩子结点的编号为，右孩子结点的编号为，双亲结点的编号为。10在一棵二叉树中，第5层上的结点数最多为。11 假定一棵二叉树的结点数为12 一棵二叉树的广义表表示为结点为，右孩子结点为13 一棵二叉树的广义表表示为个，叶子结点个

17、。18，则它的最小深度为，最大深度为。a(b(c,d),e(f(,g)，则e结点的双亲结点为，左孩子。a(b(c,d),e(f(,g)，它含有双亲结点个，单分支结点14假定一棵二叉树顺序存储在一维数组a中，则ai元素的左孩子元素为，右孩子元素为，双亲元素(i>1)为。15 假定一棵二叉树顺序存储在一维数组a中，但让编号为1的结点存入a0元素中，让编号为2的结点存入a1元素中，其余类推，则编号为i结点的左孩子结点对应的存储位置为，若编号为i结点的存储位置用j表示，则其左孩子结点对应的存储位置为16 若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组a中，即编号为0的结点存

18、储到a0中，其余类推，则ai元素的左孩子元素为，右孩子元素为，双亲元素(i>0)为。17 对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为个，其中个用于指向孩子结点，个指针空闲着。18 一棵二叉树广义表表示为a(b(d(,h),c(e,f(g,i(k)，该树的结点数为个，深度为。19 假定一棵二叉树广义表表示为a(b(c),d(e,f)，则对它进行的先序遍历结果为，中序遍历结果为，后序遍历结果为，按层遍历结果为20 假定一棵普通树的广义表表示为a(b(e),c(f(h,i,j),g),d)，则先根遍历结果为，按层遍历结果为。二、应用题1已知一棵具有n个结点的完全二叉树被顺序存储于一

19、维数组的A1An元素中，试编写一个算法打印出编号为i的结点的双亲和所有孩子。2.编写一算法，求出一棵二叉树中所有结点数和叶子结点数，假定分别用变参C1和C2统计所有结点数和叶子结点数，初值均为0。第六章二叉树的应用(二)一、单选题1. 从二叉搜索树中查找一个元素时，其时间复杂度大致为。A、O(n)B、O(1)C、O(log2n)D、O(n2)2. 向二叉搜索树中插入一个元素时，其时间复杂度大致为。A、O(1)B、O(log2n)C、O(n)D、O(nlog2n)3. 根据n个元素建立一棵二叉搜索树时，其时间复杂度大致为。A、O(n)B、O(log2n)C、O(n2)D、O(nlog2n)4.

20、从堆中删除一个元素的时间复杂度为。A、O(1)B、O(n)C、O(log2n)D、O(nlog2n)5. 向堆中插入一个元素的时间复杂度为。A、O(log2n)B、O(n)C、O(1)D、O(nlog2n)6. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为。A、24B、48C、72D、53二、填空题1.在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定该结点的值，右子树上所有结点的值一定该结点的值。2对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个。3从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明，若元素的值小于根结点的值，则继续

21、向查找，若元素的大于根结点的值，则继续向查找。4在一个堆的顺序存储中，若一个元素的下标为i，则它的左孩子元素的下标为，右孩子元素的下标为。5.在一个小根堆中，堆顶结点的值是所有结点中的，在一个大根堆中，堆顶结点的值是所有结点中的。6当从一个小根堆中删除一个元素时，需要把元素填补到位置，然后再按条件把它逐层调整。三、应用题画出按元素排列顺序输入生成的一棵二叉搜索1. 已知一组元素为(46,25,78,62,12,37,70,29)树。2. 空堆开始依次向堆中插入线性表(38,64,52,15,73,40,48,55,26,12)中的每个元素，请以线性表的形式给出每插入一个元素后堆的状态。3. 已

22、知一个堆为(12,15,40,38,26,52,48,64)，若需要从堆中依次删除四个元素，请给出每删除一个元素后堆的状态。4. 有七个带权结点，其权值分别为3,7,8,2,6,10,14，试以它们为叶子结点构造一棵哈夫曼树，并计算出带权路径长度WPL。数据结构期末复习练习题答案(仅供参考)第一章绪论一、单选题1. A2.C3.B4.C5.D6.B二、填空题I. 集合结构、线性结构、树型结构、图形结构2.顺序、链式3.1:1、1:N、M:N4.数据定义、操作声明5.引用形参(或指针形参)6.引用类型(或指针类型)7.实参、值8.stdio.h、file.h9.stdlib.h、rand()%2

23、110.sizeof(a)、a+i*sizeof(a0)、a+iII. 参数类型、数量、次序12.2、用户自定义13.=、ra、rb14.O(n)、O(m*n)15.n、n(n+1)/2、O(n2)16.O(n)第二章线性表一、单选题1.B2.A3.C4.B5.D6.C二、填空题1.元素值、指针2.(38,56,25,60,42,74)3.O(n)、O(1)4.(1)、O(n)5.i-1、i+1p->next、ap.next7.表头8.前驱、后继9.表尾、表头10HL->next=NULL、HL->next=HL三、应用题(1) 1)(79,62,34,57,26,48)(2

24、) (26,34,48,57,62,79)(3) (26,34,39,48,57,62)2 12，26，9，8，15，30，50)3 (1)ElemTypeDMValue(List&L)if(ListEmpty(L)/空线性表cerr<<"ListisEmpty!"<<endl;exit(1);ElemTypex;/xx=L.list0;intk=0;/kfor(inti=1;i<L.size;i+)/if(L.listi<x)x=L.listi;L.listk=L.listL.size-1;/L.size-;/returnx;/

25、2)ElemTypeDelete(List&L,inti)if(i<1|i>L.size)/printf("Indexisoutrange!nexit(1);ElemTypex=L.listi-1;/for(intj=i-1;j<L.size-1;j+)/L.listj=L.listj+1;L.size-;/returnx;/(3)voidInsert(List&L,inti,ElemTypex)if(i<1|i>L.size+1)/printf("Indexisoutrange!n");exit(1);if(L.si

26、ze=MaxSize)/printf("Listoverflow!n");exit(1);for(intj=L.size-1;j>=i-1;j-)/L.listj+1=L.listj;L.listi-1=x;/L.size+;/(4)voidDelete(List&L,ElemTypex)inti=0;while(i<L.size)if(L.listi=x)/for(intj=i+1;j<L.size;j+)L.listj-1=L.listj;L.size-;elsei+;/存放最小元素存放最小元素的下标查找最小元素k=i;最后一个元素填补最小元素

27、位置线性表长度减1返回最小元素判断i的合法性保存被删除元素元素向前移动长度减1返回被删元素判断i的合法性判断线性表满元素后移，产生插入位置元素插入长度加1删除x元素寻找下一个x元素的位置4(1)voidDelete(LNode*&HL,inti)if(i<1|HL=NULL)/cerr<<"indexisoutrange!"<<endl;exit(1);LNode*ap,*cp;ap=NULL;cp=HL;/cpintj=1;while(cp!=NULL)/if(j=i)/break;/cp指向的结点即为第else/ap=cp;cp=c

28、p->next;j+;if(cp=NULL)/判断i的合法性或空链表指向当前结点，ap指向其前驱结点查找第i个结点找到第i个结点i个结点继续向后寻找没有找到第i个结点cerr<<"Indexisoutrange!"<<endl;exit(1);if(ap=NULL)/HL=HL->nextl删除第1个结点（即i=1）elseap->next=cp->next;/deletecp;/删除第i个结点释放被删除结点的空间(2)voidInsert(LNode*&HL,constElemType&x)LNode*new

29、ptr=newLNode;/if(newptr=NULL)/cerr<<"Memoryallocationfailare!"<<endl;exit(1);newptr->data=x;if(HL=NULL|x<HL->data)/申请一个新结点分配失败空表或x小于表头结点，newptr->next=HL;/作为新表头结点插入用 cp 指向当前结点（即待查结点）用 ap 作为指向当前结点的前驱结点指针找到插入位置继续查找插入位置HL=newptr;return;/查找插入位置LNode*cp=HL->next;/LNode

30、*ap=HL;/while(cp!=NULL)if(x<cp->data)break;/elseap=cp;cp=cp->next;/插入新结点newptr->next=cp;ap->next=newptr;/(3)ElemTypeMaxValue(LNode*HL)if(HL=NULL)/空表cerr<<"Linkedlistisempty!"<<endl;exit(1);ElemTypemax=HL->data;LNode*p=HL->next;while(p!=NULL)/寻找最大值if(max<

31、p->data)max=p->data;p=p->next;returnmax;(4)intCount(LNode*HL,ElemTypex)intn=0;LNode*p=HL;while(p!=NULL)if(p->data=x)n+;p=p->next;returnn;第三章稀疏矩阵和广义表一、单选题1.A2.B二、填空题1.行号、列号、元素值2.行号、列号3.引用(或指针)4.等于5.4、56.列号、行号7.单、表8.括号9.310.元素值、子表指针11.true、NULL三、应用题1(1)(1,2,4),(2,4,-3),(2,7,1),(3,1,8),(

32、4,4,5),(5,2,-7),(5,6,2),(6,4,6)12234556247142644-3185-726(2)(3)(1,3,8),(2,1,4),(2,5,-7),(4,2,-3),(4,4,5),(4,6,6),(6,5,2),(7,2,1)122444673152465284-7-356212(1)A：长度：1深度：2(2)B：长度：3深度：1(3)C：长度：2深度：3(4)D：长度：2深度：2(5)E：长度：3深度：3(6)F：长度：1深度：4第四章栈和队列一、单选题1.A2.B3.C4.A5.B6.B7.D8.D、填空题1.队尾、队首2.后进先出(LIFO)、先进先出(FI

33、FO)3.栈顶指针、存储4.栈顶元素、栈顶指针5.front=rear、(rear+1)%QueueMaxSize=front6.-1、StackMaxSize-17.栈空、空队、队列只有一个元素8.新结点的指针域、栈顶指针9.指针域、栈顶指针10.队尾指针、存储11.top=012.p->next=HS、HS=p13.HS=HS->next14.(front=rear)&&(front<>NULL)15.3425615+-/8*+16.(24+8)*3/(4*(10-7)、8三、应用题121553018四、编程题递归算法：longFib(intn)if

34、(n=1|n=2)/终止递归条件return1;elsereturnFib(n-1)+Fib(n-2);long Fib( int n ) int a , b , c; / c a = b = 1;非递归算法：代表当前项，a和b分别代表当前项前面的第2项和第1项if(n=1|n=2)return1;elsefor ( int i = 3 ; i<=n ; c = a+b; /a = b;/b = c;/return c; /i+)求当前项产生第2项产生第1项返回所求的第n项递归算法的时间复杂度为O(2n)，空间复杂度为O(n)；非递归算法的时间复杂度为O(n)，空间复杂度为O(1)。第五

35、章树和二叉树一、填空题1.n-12.5、503.64.31、215.10、4、36.2、1、1、67.B、I和J8.69.2i、2i+1、?i/2?10.1611.5、1812.a、f、空结点(即无右孩子结点)13.4、2、314.a2*i、a2*i+1、ai/215.2i-1、2j+116.A2*i+1、a2*i+2、ai/217.2n、n-1、n+118.10、519.abcdef、cbaedf、cbefda、abdcef20.abecfhijgd、abcdefghij二、应用题1voidRequest(intA,intn,inti)if(i>n)cerr<<"编号为"<<i<<"的结点不存在！"<<endl;exit(1);cout<<"当前结点为"<<Ai<<