数据构造C语言版章节练习题.docx

《数据构造C语言版章节练习题.docx》由会员分享，可在线阅读，更多相关《数据构造C语言版章节练习题.docx（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据构造C语言版章节练习题数据构造章节练习题第一章绪论一、单项选择题1.一个数组元素ai与_的表示等价。A、*(a+i)B、a+iC、*a+iD、&a+i2.下面程序段的时间复杂度为_。for(inti=0;ifor(intj=1;jnext=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-next=q;D

2、、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在线性表的单链式存储构造中，每个结点包含有两个域，一个叫_域，另一个叫_域。2在下面数组a中链式存储着一个线性表，表头指针为a0.next，则该线性表为_。3对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_，在表尾插入元素的时间复杂度为_。4对于一个长度

3、为n的单链式存储的线性表，在表头插入元素的时间复杂度为_，在表尾插入元素的时间复杂度为_。5在线性表的顺序存储中，若一个元素的下标为i，则它的前驱元素的下标为_，后继元素的下标为_。6在线性表的单链式存储中，若一个元素所在结点的地址为p，则其后继结点的地址为_，若假定p为一个数组a中的下标，则其后继结点的下标为_。7在循环单链表中，最后一个结点的指针指向_结点。8在双向链表中每个结点包含有两个指针域，一个指向其_结点，另一个指向其_结点。9在循环双向链表中表头结点的左指针域指向_结点，最后一个结点的右指针域指向_结点。10在以HL为表头指针的带表头结点的单链表和循环单链表中，链表为空的条件分别

4、为_和_。三、应用题1在下面的每个程序段中，假定线性表La的类型为List，元素类型ElemType为int，并假定每个程序段是连续执行的，试写出每个程序段执行后所得到的线性表La。(1)InitList(La);inta=48,26,57,34,62,79;for(i=0;i5当利用大小为N的一维数组顺序存储一个循环队列时，该队列的最大长度为。A、N-2B、N-1C、ND、N+16从一个循环顺序队列删除元素时，首先需要。A、前移一位队首指针B、后移一位队首指针C、取出队首指针所指位置上的元素D、取出队尾指针所指位置上的元素7假定一个循环顺序队列的队首和队尾指针分别为f和r，则判定队空的条件是

5、。A、f+1=rB、r+1=fC、f=0D、f=r8假定一个链队的队首和队尾指针分别为front和rear，则判定队空的条件是。A、front=rearB、front!=NULLC、rear!=NULLD、front=NULL二、填空题1队列的插入操作在_进行，删除操作在_进行。2栈又称为_表，队列又称为_表。3向一个顺序栈插入一个元素时，首先把待插入元素_到这个位置上然后，使_后移一个位置。4从一个栈中删除元素时，首先前移一位_，然后再取出_。5在一个循环顺序队列Q中，判定队空的条件为_，判定队满的条件为_。6在一个顺序栈中，若栈顶指针等于_，则为空栈；若栈顶指针等于_，则为满栈。7在一个链

6、栈中，若栈顶指针等于NULL，则为_；在一个链队中，若队首指针与队尾指针的值一样，则表示该队列为_。8向一个链栈插入一个新结点时，首先把新结点的存储位置赋给_，然后把栈顶指针指向_。9从一个链栈中删除一个结点时，需要把栈顶结点_的值赋给_。10向一个顺序队列插入元素时，需要首先向_插入新元素，然后再移动_。11当用长度为N的一维数组顺序存储一个栈时，假定用top=0表示栈空，则表示栈满的条件为_。12向一个栈顶指针为HS的链栈中插入一个新结点*P果，应执行_和_操作。13从一个栈顶指针为HS的非空链栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行_操作。14假定front和rear分别

7、为一个链队的队首和队尾指针，则该链队中只要一个结点的条件为_。三、应用题执行下面函数调用后得到的输出结果是什么voidAF(Queue&Q)InitQueue(Q);inta4=5,8,12,15;for(inti=0;i一、单项选择题1.在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有一样的_。A、行号B、列号C、元素值D、地址二、填空题1.在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的_、_和_三项。2.在稀疏矩阵所对应的三元组线性表中，每个三元组元素按_为主序、_为辅序的次序排列。3.在初始化一个稀疏矩阵的函数定义中，矩阵形参应讲明为_参数。4.在稀疏矩阵的顺序

8、存储中，利用一个数组来存储非零元素，该数组的长度应_对应三元组线性表的长度。第五章树和二叉树一一、填空题1对于一棵具有n个结点的树，该树中所有结点的度数之和为_。2假定一棵三叉树的结点个数为50，则它的最小深度为_，最大深度为_。3在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有_个。4一棵深度为5的满二叉树中的结点数为_个，一棵深度为3的满三叉树中的结点数为_个。5假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)，则树中所含的结点数为_个，树的深度为_，树的度为_。6假定一棵树的广义表表示为A(B(C,D(E,F,G),

9、H(I,J)，则度为3、2、1、0的结点数分别为_、_、_和_个。7假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)，则结点H的双亲结点为_，孩子结点为_。8在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为_个。9对于一棵二叉树，若一个结点的编号为i，则它的左孩子结点的编号为_，右孩子结点的编号为_，双亲结点的编号为_。10在一棵二叉树中，第5层上的结点数最多为_。11假定一棵二叉树的结点数为18，则它的最小深度为_，最大深度为_。12一棵二叉树的广义表表示为a(b(c,d),e(f(,g)，则e结点的双亲结点为_，左孩子结点为_，右孩子结点为_。1

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

11、子元素为_，双亲元素(i0)为_。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个结点的完全二叉树被顺序存储于一维数组的A1An元素中，试编写一个算法打

12、印出编号为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.从堆中删除一个元素的时间复杂度为_。A、O(

13、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从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明_，若元素的值小于根结点的值，则继续向_查找，若元素的大于根结点的值，

14、则继续向_查找。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.已知一个堆为12,15,4

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

16、次序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)、i+1p-next、ap.next7.表头8.前驱、后继9.表尾、表头10HL-next=NULL、HL-next=HL三、应用题1.(1)(79,62,34,57,26,48)(2)(26,34,48,57,62,79)(3)(26,34,39,48,57,62)212，26，9，8，15，30，5

17、03(1)ElemTypeDMValue(List&L)if(ListEmpty(L)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),(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

18、)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)、先进先出(FIFO)3.栈顶指针、存储4.栈顶元素、栈顶指针5.front=rear、(rear+1)%QueueMaxSize=front6.-1、StackMaxSize-17.栈空、空队、队列只要一个元素8.新结点的指针域、栈顶指针9.指针域、栈顶指针10

19、.队尾指针、存储=0next=HS、HS=p13.HS=HS-next14.(front=rear)&(frontNULL)15.3425615+-/8*+16.(24+8)*3/(4*(10-7)、8三、应用题121553018四、编程题递归算法：longFib(intn)if(n=1|n=2)6、21、4、3、1、1、6、I和J9.2i、2i+1、i/2、18、f、空结点(即无右孩子结点)13.4、2、314.a2*i、a2*i+1、ai/215.2i-1、2j+116.A2*i+1、a2*i+2、ai/2、n-1、n+1、519.abcdef、cbaedf、cbefda、abdcef20

20、.abecfhijgd、abcdefghij二、应用题1voidRequest(intA,intn,inti)if(in)cerr三、应用题1.2.初态：空堆()插入38后：(38)插入64后：(38,64)插入52后：(38,64,52)插入15后：(15,38,52,64)插入73后：(15,38,52,64,73)插入40后：(15,38,40,64,73,52)插入48后：(15,38,40,64,73,52,48)插入55后：(15,38,40,55,73,52,48,64)插入26后：(15,26,40,38,73,52,48,64,55)插入12后：(12,15,40,38,26,52,48,64,55,73)3.初态堆：(12,15,40,38,26,52,48,64)删除第1个元素后堆：(15,26,40,38,64,52,48)删除第2个元素后堆：(26,38,40,48,64,52)删除第3个元素后堆：(38,48,40,52,64)删除第4个元素后堆：(40,48,64,52)4.哈夫曼树：WPL=3*4+7*3+8*3+2*4+6*3+10*2+14*2=131