数据结构习题集答案

郑州航空工业管理学院《数据构造》习题集第1章绪论1、填空题常见的数据构造有集合、_线性__构造，__树___构造，__图__构造等三种。常见的存储构造有__次序存储___构造，__链式存储___构造等两种。数据的基本单位是_数据元素__，它在计算机中是作为一种整体来解决的。数据构造中的构造是指数据间的逻辑关系，常见的逻辑构造可分为两大类：__线性构造____和__非线性构造___。2、选择题数据构造是一门研究非数值计算的程序设计中计算机的A以及它们之间的C和运算等的学科。（A）数据元素（B）计算办法（C）关系（D）数据映像在数据构造中，与所使用的计算机无关的是数据的A构造。（A）逻辑（B）存储（C）物理（D）逻辑与存储3、应用题(1)、给出下列算法的时间复杂度.voidfun(intn){ inti=1,k=100; while(i<n) { k=k+1; i=i+2; }}上述算法的时间复杂度为：___O(n)_____。(2)、给出下列算法的时间复杂度.voidfun2(intn){ inti=1,k=100; while(i<n) { i=i*10; k=k+1; }}上述算法的时间复杂度为：___O(log10n)______。第2章线性表1、填空题线性表按照存储构造不同重要有两种实现方式，一种是__次序_表，另一种是___链___表。次序表采用__随机___访问机制对数据元素进行访问。若在单链表结点p的背面插入一种新的结点s，则其操作序列为:____s->next=p->next_____________；___p->next=s___________________；在单向链表中，若要删除某个结点p，普通要找到__p的直接前驱__结点，才干实现该操作。2、选择题将两个各有n个元素的有序表归并成一种有序表，其最少的比较次数是A。(A)n(B)2n－1(C)2n(D)n-1在单链表中，如果在结点p之后插入一种新结点s，其操作为A。（A）s->next=p->next;p->next=s;（B）p->next=s;s->next=p->next;（C）s->next=p;p->next=s->next;（D）p->next=s;s->next=p;若长度为n的线性表采用次序存储构造，在其第i个位置删除一种元素的算法的平均时间复杂度为(C)。(1≤i≤n)(A)．O(0)(B)．O(1)(C).O(n)(D)．O(n2)若长度为n的线性表采用次序存储构造，在其第i个位置插入一种新元素需要移动的元素个数为(B)。(1≤i≤n+1)(A)．n-i(B)．n-i+1(C).I(D)．n-i-13、判断题(1).线性表中每一种元素都有一种前驱和一种后继。（错）第3章栈和队列1、填空题(1).栈和队列在本质上都是操作受限的_线性表__________。(2).栈的操作特点是__后进先出_。队列的操作特点是_先进先出__。2、选择题(1).消除递归不一定需要使用栈，此说法__A____。(A).对的(B).错误(2).一种栈的进展序列为（1，2，3，4），则不可能得到的输出序列是__D____。(A)（1，2，3，4）(B)（4，3，2，1）(C)（1，3，4，2）(D)（3，1，2，4）(3).用单循环链表表达队列，对的的说法是B。(A)可设一种头指针使入队、出队都方便；(B)可设一种尾指针使入队、出队都方便；(C)必须设头尾指针才干使入队、出队都方便；(D)无论如何,只可能使入队方便。3、判断题(1).栈的特点是先进先出。（错）(2).能够在队列的任意位置插入元素。（错）(3).递归程序化非递归程序必须用到栈。（错）(4).如果进栈的序列为（1，2，3，4），则（4，2，3，1）不可能是出栈序列。（对）(5).在用次序表表达的循环队列中，能够设一种变量L作为标志位来分辨队空或队满的条件，当L==0时表达队列为空，等L的值为空间的大小时表达队列为满。（对）(6).当用数组做为栈的存储构造时，应把栈顶设在高地址哪一端，这样入栈、出栈不需要移动其它元素。（对）(7).当用单链表作为栈的存储构造时，应把栈顶设立链表的头部，这样入栈、出栈不需要移动其它元素。（对）第4章串1、选择题(1).串是任意有限个（D）(A).符号构成的序列 (B).符号构成的集合(C).字符构成的集合 (D).字符构成的序列(2).串是一种特殊的线性表，其特殊性体现在（B）(A).能够次序存储(B).数据元素是一种字符(C).能够连接存储(D).数据元素能够是多个字符(3).下列（D）是“abcd321ABCD”的子串。(A).abcd (B).321AB(C).“abcABC”(D).“21AB”(4).两个串相等必有串长度相等且（B）。(A).串的各位置字符任意(B).串中各位置字符均对应相等(C).两个串含有相似的字符(D).两个所含字符任意(5).设有两个串p和q，求q在p中初次出现的位置的运算称作（B）(A)．连接(B)．模式匹配(C)．求子串(D)．求串长(6).若串s=“software”，其子串的个数是（C）。(A).8 (B).37(C).36 (D).92、判断题(1).空串和空格串是同一种概念，两者没有区别。（错）(2).空格串就是由空格构成的串。（对）第5章数组和广义表1、填空题(1).二维数组在内存中存储能够有两种存储方式，一种是__按行__优先存储，一种是按列优先存储。(2).设广义表L＝(（），（），（（））)。则head(L)是（）；tail(L)是(（），（（））)；L的长度是3；L的深度是3。(3).设广义表L＝(（a），（b），（（c））)，则head(L)是__（a）__；tail(L)是__(（b），（（c））)__。2、选择题(1).在C语言中，如果有数组定义intA[8][9]；假定每个整型数据占2字节，则数组元素A[4][4]的地址是（A）。(A).A+80 (B).A+76 (C).A+82 (D).以上都不对(2).广义表A=（a,b,(c,d),(e,(f,g))）,则下面式子的值为(D)；Head(Tail(Head(Tail(Tail(A)))))(A)．（g） (B).(d) (C).c (D).d3、判断题在C语言中，多维数组的存储采用的是行优先的方式。（对）广义表在本质上也是线性表，这种说法是错误的。（对）广义表L的取表头操作是Head(L)，得到的是L中的第一种元素。（对）广义表L的取表尾操作是Tail(L)，得到的是L中的除了第一种元素外全部元素构成的表。（对）能够用三元组存储法来压缩存储稀疏矩阵。（对）已知广义表A=((a,b,c),(d,e,f)),从A中取出原子e的运算是head(tail(head(tail(A))))。(对)第6章树和二叉树1、填空题一棵62个叶结点的完全二叉树,最多有__125______个结点。若规定仅有根的二叉树的高度为1，那么高为h的完全二叉树最多有2h-1___个结点，最少有__2h-1_个结点。设只包含有根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为___2k+1-1____________，最小结点数为__k+1_____。设仅包含根结点的二叉树的高度为1，则高度为k的二叉树的最大结点数为___2k-1___，最小结点数为__k___。在一棵二叉树中，如果度为2的结点个数为100，则叶子结点个数为101。在一棵哈夫曼树中，如果叶子结点个数为100，则度为1的结点总个数为0。在一棵哈夫曼树中，如果叶子结点个数为100，则度为2的结点总个数为99。在一棵哈夫曼树中，如果叶子结点个数为100，则结点总个数为199。2、选择题含有N个结点的完全二叉树的深度是_B___。(A)⌊log2N⌋(B)⌊log2N⌋+1(C)⌊log2(N)⌋(D)⌊log2N⌋-1设二叉树的树根为第一层，则第i层上至多有__C____结点。(A)1(B)2(C)2i-1(D)2i-13、判断题二叉树的左右子树次序是严格的，不能够任意变化。（对）若根为第一层，则深度为k的满二叉树的结点数为2^k-1。（对）二叉树的三叉链表存储构造能够方便的访问到双亲结点。（对）4、应用题(1).请证明对于任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。见教材P123ABECFGABECFGDHIJ图1先：ABCDEFGHIJ中：BCDAFEHJIG后：DCBFJIHGEA(3).写出如图2所示二叉树的中序遍历成果。DDACFGEHB图2中：ADBCHFEG(4).已知某二叉树的前序遍历序列为：ABCDEFG和中序遍历序列为：CBEDAFG。请画出该二叉树并写出它的后序遍历序列。见教材P154例6-5(5).设一棵二叉树的先序遍历序列为abcde，中序遍历序列为badce，请画出对应的二叉树，并写出对应后序遍历序列。bbedca图3二叉树见图3后：bdeca(6).在一段文字中，共出现a、b、c、d、e、f六种字符，每种字符出现的频率分别为7,9,12,22,23,27。请回答下列问题：（a）什么是哈夫曼树？带权途径长度最小的二叉树。2828121627239457图42255100（b）根据题目所给频率值，画出对应的哈夫曼树。哈夫曼树见图4（c）给出各个字符对应的哈夫曼编码。7：11109：111112：11022：0023：0127：105、读程序写成果ABABCDEstructNode{ intdata; Node*lchild,*rchild;};某棵二叉树的形态如右图：根据规定解答下题：1、intfun1(Node*root){ if(root==0)return0; intl,r; l=fun1(root->lchild); r=fun1(root->rchild); if(l>=r)returnl+1; elsereturnr+1;}(1)当root是指向结点A的指针时，函数fun1的返回值是：3。(2)函数fun1的功效是：求二叉树的叶子个数。2、intfun2(Node*root){ if(root==0)return0; intl=fun2(root->lchild); intr=fun2(root->rchild); returnl+r+1;}（1）当root是指向结点A的指针时，函数fun2的返回值是：3。（2）函数fun2的功效是求二叉树的高度第7章图1、填空题有n个顶点的有向连通图最多有n(n-1)条边，最少有n条边。含有n个顶点的完全无向图有__n(n-1)/2__条边，完全有向图有__n(n-1)______条边。____拓扑排序_____办法能够判断出一种有向图中与否有环（回路）。含有n个顶点的有向图最多有__n(n-1)__条边。4、应用题（1）、已知某图的存储构造以下，试写出该图从顶点A开始的深度优先、广度优先遍历序列。ABCDEFGHIJKA01111100000B00000010000C00000001000D00000000100E00000000010F00000000001G01000000000H00100000000I00010000000J00001000000K00000100000图1深度优先遍历：ABGCHDIEJFK广度优先遍历：ABCDEFGHIJK（2）.请给出图2的全部最小生成树。aaebdfc1238665图2 答案：有两个aaebdfc12365答案一aaebdfc12365答案二（3）.请给出图3的全部拓扑排序序列。图图3abdfgceh答案：有两个(1)abcdefgh(2)acbdefgh（4）、对于有向无环图（如图4），写出它的全部不同的拓扑有序序列。112435678图4答案：有两个3245678（2）31245678（5）.已知某图采用如图5所示的邻接矩阵表达法，请回答下列问题。01234561A10110002B21001103C31000114D40100005E50110006F6001000图5(a)请画出该图。DBDBEAEACFCF（b）对其从顶点A开始进行深度优先遍历，写出遍历序列。深度优先遍历：ABDECF(7)、构造图6的最小生成树。aaefgdbhc21111222243图6bgebge22222211da11da11chf11chf第9章查找1、选择题若在线性表中采用二分查找法查找元素，该线性表应当C。（A）．元素按值有序（B）．采用次序存储构造（C）．元素按值有序，且采用次序存储构造（D）．元素按值有序，且采用链式存储构造对二叉排序树进行___B______遍历，能够得到该二叉树全部结点构成的有序序列。(A).前序 (B).中序 (C).后序 (D).按层次运用逐点插入法建立序列(51，71，43，81，74，20，34，45，64，30)对应的二叉排序树后来，查找元素34要进行(A)元素间的比较。（A）．4次 （B）．5次 （C）．7次 (D)．10对二叉排序树进行___B_____遍历，能够得到该二叉树全部结点构成的有序序列。(A)．前序 (B)．中序 (C)．后序 (D).按层次散列函数有一种共同性质，即函数值应按___C_____取其值域的每一种值。(A).最大概率 (B).最小概率 (C).同等概率 (D).平均概率一种哈希函数被认为是“好的”，如果它满足条件__A____。(A)哈希地址分布均匀(B)确保不产生冲突(C)全部哈希地址在表长范畴内(D)满足(B)和(C)哈希表的平均查找长度是____D_____的函数。（A）哈希表的长度（B）表中元素的多少（C）哈希函数（D）哈希表的装满程度平均查找长度最短的查找办法是__C___。（A）折半查找（B）次序查找（C）哈希查找（4）其它2、判断题在有序表的查询过程中，设立“哨兵”的作用是为了减少比较次数，提高查询效率。（对）对于折半查找，其前提条件是待查找序列只要是有序的即可。（错）3、应用题（1）.输入一种正整数序列（53,17,12,66,58,70,87,25,56,60），试完毕下列各题。(a)按输入次序构造一棵二叉排序树（一步一步画出构造二叉排序树的过程，每插入一种结点，画一棵二叉排序树）。5353176658701287256056(b)依此二叉排序树，如何得到一种从小到大的有序序列？对二叉排序树进行中序遍历（2）、若一棵排序二叉树的核心字输入序列为{80，6，10，7，8，25，100，90}，请画出该二叉树。80680610090710825（3）.已知一组核心字为{1,14,27,29,55,68,10