大数据结构考精彩试题库

实用文档绪论一、填空题数据的逻辑结构被分为集合、(线性结构)、(树形结构)和(图状结构)四种。物理结构是数据结构在计算机中的表示，又称为(存储结构)。3.数据元素的逻辑结构包括 ( 线性)、(树)和图状结构 3种类 型，树形结构和图状结构合称为(非线性结构)。4.(数据元素)是数据的基本单位， (数据项)是数据不可分割的最小单位。线性结构中元素之间存在(一个对一个)关系，树形结构中元素之间存在(一个对多个)关系，图状结构中元素之间存在(多个对多个)关系。？6.数据结构是一门研究非数值计算的程序设计问题中：计算机的(数据元素)以及它们之间的(关系)和(运筹)等的学科。算法的五个重要特性为有穷性、确定性、(输入)、(输出)和(可行性)。二、选择题数据的不可分割的基本单位是(D)。A.元素B.结点C.数据类型D.数据项*2.线性表的逻辑顺序与存储顺序总是一致的，这种说法 (B)。A.正确 B.不正确 C.不确定 D.无法选择线性结构是指数据元素之间存在一种(D)。A.一对多关系 B.多对多关系 C.多对一关系 D.一对一关系文案大全实用文档在数据结构中，从逻辑上可以把数据结构分成(A)。A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.线性结构和非线性结构 D.内部结构和外部结构线性表若采用链式存储结构时，要求内存中可用存储单元的地址(D)。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以三、简答题算法的特性是什么。答：有穷性 确定性 可行性 有0或多个输入 有1或多个输出线性结构一、填空题1.在一个长度为 n的线性表中删除第 i个元素（1≤i≤n）时， 需向前移动(n-i)个元素。从循环队列中删除一个元素时，其操作是(先移动队首指针，后取出元素)。在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为(p->next)。4.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把(p->next)的值赋给q->next，然后(q->date)的值赋给p->next。从一个栈删除元素时，首先取出(栈顶元素)，然后再使(栈顶指针)减1。子串的定位操作通常称做串的(模式匹配)。文案大全实用文档7.设目标T=‘abccdcdccbaa’，模式 P=‘cdcc’则第(六)次匹配成功。。8. 顺序栈S中，出栈操作时 要执行的 语句序列 中有S->top( --)；进栈操作时要执行的语句序列中有 S->top(++)。顺序表中逻辑上相邻元素的物理位置(一定)紧邻；单链表中逻辑上相邻元素的物理位置(不一定)紧邻。在(循环)链表中，从任何一结点出发都能访问到表中的所有结点。栈和队列均是(运算受限)的线性表，栈的特点是(先进后出后进先出)；队列的特点是(先进先出后进后出)。12.通常，在程序中使用的串可分为串常量和串变量；而串按存储方式又可分为 (定长顺序存储)和(堆分配存储)。循环队列头指针front指向队头元素，队尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为 Queuelen。在循环队列中 ， 队空标志为(front==rear )， 队满标志为(（rear+1）%max==front)。当rear>=front时，队列长度为(rear-front)，当rear<front时，队列长度为(rear-front+max)。14.在一个长度为n的线性表中的第i个元素（1≤i≤n）之前插入一个元素时，需向后移动(n-i+1)个元素。15.在具有n个单元的循环队列中，队满时共有(n-1)个元素。带有一个头结点的单链表Head为空的条件是(Head->next==null)。17.在一个单链表中删除指针 p所指向结点的后继结点时，需要把 (p->next->next )值赋给文案大全实用文档p->next 指针域。18.一个顺序循环队列存于 a[M]中，假定队首和队尾指针分别 为front 和rear，则判断队空的条件为(a.front==a.rear)，判断队满的条件为(（a.rear+1）%M==a.front)。19.在双向链表中，每个结点有两个指针域，一个指向其 (前驱) 结点，另一个指向其 (后继)结点最后一个结点的 (后继结点)指针域为空。*20. 若D=((a ，(b ，c)) ，e ，a) ，则Head(D)=( ) ，Tail(D)=( ) ，Head(Tail(D))=( )。（本人不会）在循环链表中，每个结点有(一个)个指针域，指向其(后继)结点，最后一个结点的指针域(为空)。*22. 若S=(a ，(b ，c) ，e ，d) ，则Head(S)=( ) ，Tail(S )=( ) ，Head(Tail(S))=( ) 。（本人不会）二、选择题1.在一个单链表中，若 q所指结点是 p所指结点的前驱结点，若在 q与p之间插入一个 s所指的结点，则执行(A)。A.s->link=p->link;p->link=s;B.p->link=s;s->link=q;C.p->link=s->link;s->link=p;D.q->link=s;s->link=p;对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数 (A)。A.R-F B.n+R-FC.(R-F+1)modn D.(n+R-F)modn3.如下陈述中正确的是 (A)。文案大全实用文档A.串是一种特殊的线性表 B.串的长度必须大于零C.串中元素只能是字母 D.空串就是空白串4.若让元素1，2，3依次进栈，则出栈次序不可能出现 (C)的情况。A.3，2，1B.2，1，3 C.3，1，2 D.1，3，2判定一个队列QU（最多元素为m0）为空的条件是(C)。A.QU->rear-QU->front==m0B.QU->rear-QU->front-1==m0C.QU->front==QU->rear D.QU->front==QU->rear+1设目标串S=‘abcdef’，模式串p=‘de’，则第(C)次匹配成功。A.1B.2C.4D.57.设字符串s1=‘ABCDEFG’，S2=‘PQRST’，T，sub1，sub2为空串。则运算s=Concat(T，SubString(sub1，s1，2，SubLength(s2))，SubString(sub2，s1，SubLength(s2)，2))后的串T值为( D)。A.‘BCDEF’ B. ‘BCDEFG’ C. ‘BCPQRST’ D. ‘BCDEFEF’8.一个顺序线性表第一个元素的存储地址是 100，每个元素的 长度为 2，则第 5个元素的地址是(B)。A.100 B.108 C.110 D.120非空的循环单链表head的尾结点（由p所指向）满足(C)。A.p->next==NULL B.p==NULLC.p->next==head D.p==head文案大全实用文档在一个链队中，假设f和r分别为队首和队尾指针，则删除一个结点的运算时 (C)。A.r=f->next; B.r=r->next;C.f=f->next; D.f=r->next;11.在一个长度为 n的线性表中，删除值为 x的元素时，需要比 较元素和移动元素的总次数为(C)。A.(n+1)/2 B.n/2 C.n D.n+112.在一个单链表中，若要在 p所指向的结点之后插入一个新结 点，则需要相继修改 (B)个指针域的值。A.1 B.2 C.3 D.4线性结构中，每个结点(C)。A.无直接前驱 B. 只有一个直接前驱和个数不受限制的直接后继C.只有一个直接前驱和后继D.有个数不受限制的直接前驱和后继队列是限定在(D)进行操作的线性表。A.中间B.队头C.队尾D.端点15.设串S1=“ABCDEFG”，S2=“PQRST”，函数StrCat(x,y) 返回x和y串的连接串，函数 StrSub(Si，j)返回串 S的从序号 i 的字符开始的 j 个字符组成的子串， StrLen(S) 返回串 S的长度， 则StrCat(StrSub(S1 ，2，StrLen(S2)) ，StrSub(S1，StrLen(S2) ，2))的结果串是(D)。A.BCDEF B.BCDEFG C.BCPQRSTD.BCDEFEF文案大全实用文档学生成绩表是一种(C)结构。A.图形 B.树形 C.线性 D.集合17.在一个链队中，假设 f和r分别为队首和队尾指针，则插入 s所指结点的运算时 (C)。A.f->next=s; f=s; B.r->next=s;r=s;C.s->next=r; r=s; D.s->next=f;f=s;向顺序表中的i位置处插入元素，下面哪项能够准确的表明i的位置是合法的。 (D)A.i<=1||i>l->length+1 B.i>=1C.i>=l->length+1 D.1<=i<=l->length+1设线性链表中结点的结构为（data，next），已知指针q所指结点是指针p所指结点的直接后继，若在*q和*p之间插入结点*s，则应执行(A)操作。A.s->next=p->next; p->next=s; B.q->next=s; s->next=p;C.p->next=s->next; s->next=p; D.p->next==s; s->next=q;一个栈的入栈序列为a，b，c，d，e，则出栈序列不可能的是(C)。A.edcba B.dcbaeC.dceabD.abcde如果以链表作为栈的存储结构，则出栈操作时(B)。A.必须判别栈是否满 B. 必须判别栈是否为空C.必须判别栈元素类型 D.可不做任何判断22.设有两个串 p和q，求q在p中首次出现的位置的运算称为 (B)。A.连接 B. 模式匹配 C. 求子串 D.求串长23.p指向线性链表中的某一结点，则在线性链表的表尾插入结文案大全实用文档点S的语句序列是(A)。A.while(p->next!=NULL)p=p->next;p->next=s;s->next=NULL;B.while(p!=NULL)p=p->next;p->next=s;s->next=NULL;C.while(p->next!=NULL)p=p->next;s->next=p;p->next=NULL;D.while(p!=NULL)p=p->next->next;->next;p->next=s;s->next=p向顺序栈中压入新元素时，应当(A)。A.先移动栈顶指针，再存入元素 B. 先存入元素，再移动栈顶指针C.先后次序无关紧要 D. 同时进行25.假定一个顺序队列的队首和队尾指针分别为 f和r，则判断队空的条件为 (D)。f+1==r B.r+1==f C.f==0 D.f==r栈的插入和删除操作在(A)进行。A.栈顶B.栈底C.任意位置D.指定位置栈和队列的共同点是(C)。A.都是先进后出 B.都是先进先出C.只允许在端点处插入和删除元素 D.没有共同点28.若6行8列的数组以列序为主序顺序存储，基地址为 1000，每个元素占 2个存储单元，则第 5行第3列的元素(假定无第0行第0列)的地址是(B)。A.1086B.1032 C.1068 D.答案A，B，C都不对29.设有50行的二维数组 A[50][60] ，其元素长度为 2字节，按 行优先顺序存储，基地址为 100，则元素A[18][25] 的存储地址 为(D)。文案大全实用文档A.1850 B.2188 C.1950 D.2310三、论述题写出线性表的插入算法、删除算法。解：太麻烦 略略略*2.画出主串为‘ababcabcacbab’，子串为‘abc’的模式匹配 过程。解：四、算法设计题1.在带头结点的单链线性表 L中第i个位置之前插入新的元素 e。略在带头结点的单链线性表L中，删除第i个元素，并由e返回其值。略树形结构一、填空题赫夫曼树，又称最优树，是一类(带权路径)长度最短的树。在一棵二叉树中，第5层上的结点数最多为(16)个。一棵高度为5的二叉树中最少含有(5)个结点，最多含有(31)个结点。若一棵二叉树中有8个度为2的结点，则它有(9)个叶子。一棵深度为6的满二叉树有(31)个非终端结点。文案大全实用文档树中结点A的(子树数)称为结点A的度。7.对一棵二叉排序树进行中序遍历时，得到的结点序列是一个 (升序序列)。8. 在树型结构中，根结点没有前驱结点，其余每个结点有且仅有 (一)个前驱结点；叶子结点 (没有后继结点，其余每个结点都可以有 (一或多个)个后继结点。在最优二叉树中没有度为1的结点，则一棵有n个叶子结点的最优二叉树中共有(2n-1)个结点。10.深度为4（设根的层数为1）的二叉树至少有415()个结点，至多有()个结点，第i层上至多有(2n-1)个结点。深度为6（设根的层数为1）的二叉树至少有(6)个结点，至多有(63)个结点，第4层上至多有(8)个结点。文案大全实用文档A.n B.N+1C.n-1D. 不确定注：1:B2:D3:A 4:B下面(A)是对的。A.哈夫曼树中结点的度只可能是 0和2。B.二叉树的顺序存储中，是以先序遍历存储结点的。C.完全二叉树实际上就是满二叉树。 D. 一棵二叉树第 i层的最大结点数为 2i-1。将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点X的右孩子编号为(B)。A.98 B.99 C.24 D.无法确定先序为A，B，C且后序为C，B，A的二叉树共有(B)种。A.3B.4 C.5 D.6在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为(C)。A.4B.5C.6D.7B9.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为()。A.24B.71C.48D.53一个具有767个结点的完全二叉树，其叶子结点个数为(B)。A.382 B.384 C.385 D.386在一棵具有35个结点的完全二叉树中，该树的深度为(A)。A.6B.7 C.5 D.812.由三个结点构成的二叉树，共有 (B)种不同的结构。文案大全实用文档A.3 B.4 C.5 D.6深度为k的二叉树至多有(2K-1)个结点(k≥1)。A.2k B.2k-1 C.2k-1 D.2k三、简答题已知一棵二叉树的先序遍历和中序遍历，则该二叉树的后序遍历是什么？先序遍历：A，B，C，D，E，F，G，H，I，J中序遍历：C，B，A，E，F，D，I，H，J，G解：后序遍历：C,B,F,E,I,J,H,G,D,A如下图的森林转化为二叉树。文案大全实用文档解：此题没法写 略略略3.已知某二叉树的前序序列为EBADCFHGI，中序序列为ABCDEFGHI，请给出二叉树且写出二叉树的后序序列。解：二叉树略后序序列:A,C,D,B,G,I,H,F,E试用权集合{6，4，8，3，7，5，10，8，2，1，11}，构造哈夫曼(Huffman)树。画出这棵哈夫曼树；(2)分别计算该哈夫曼树的路径长度和带权路径长度。解：(1)略路径长度为：1x2+2x4+3x8+4x3+5x2=60;带权路径长度为：3x(6+7+8+8+10+11)+4x(3+4+5)+5x(1+2)=2135.试按表(10，18，9，2，20，5，6，15，19，25)中元素的排列次序，将所有元素插入一棵初始为空的二叉排序树中，使之仍是一棵二叉排序树。试画出插入完成之后的二叉排序树；(2)若查找元素2，它将依次与二叉排序树中哪些元素比较大小?(3)对该树进行中序遍历，试写出中序遍历序列。文案大全实用文档解：(1)略(2)10,9,2(3)2,5,6,9,10,15,18,19,20,256.已知一棵二叉树的顺序存储表示如下，其中0表示空，请分别写出二叉的先序、中序、后序遍历序列。1234567891011121320846515300001018035解：先序序列：20,8,5,15,10,18,46,30,35中序序列：5,8,10,15,18,20,30,35,46后序序列：5,10,18,15,8,35,30,46,20文案大全实用文档将如下图的一般树转化为二叉树。文案大全实用文档将下图中的二叉树转换成森林。BAEGKCFHILJ文案大全实用文档四、论述题由分别带权为3，12，9，2，5，7的叶子结点构造一棵哈夫曼树，并计算该树的带权路径长度。解:带权路径长度为:91图状结构一、填空题1.若一个图的顶点集为 {a，b，c，d，e，f}，边集为{(a，b)，(a，c)，(b，c)，(d，e)}, 则该图含有(3)个连通分量。452.具有10个顶点的无向图，边的总数最多为()。图的广度优先搜索遍历类似于树的(按层次)遍历的过程。4.在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]1等于()。图的(深度)优先搜索遍历算法是一种递归算法，图的(广度)优先搜索遍历算法需要使用队列二、选择题一个有n个顶点的无向图最多有(C)条边。A.n B.n(n-1) C.n(n-1)/2 D.2n2. 在一个无向图中， 所有顶点的度数之和等于所有边数的 (B)倍。文案大全实用文档A.3 B.2 C.1 D.1/23.在一个具有 n个顶点的无向图中，若具有 e条边，则所有顶点的度数之为 (D)。A.n B.e C.n+e D.2e三、简答题给出如下图所示的无向图G的邻接矩阵存储结构。（答案略）画出下图的邻接表存储结构。（答案略）文案大全实用文档给出下图从A点出发的深度优先遍历和广度优先遍历的顶点序列。解：深度优先遍历：AECDB广度优先遍历：AEBDC文案大全实用文档给出从V1点出发的深度优先遍历和广度优先遍历的顶点序列。解：深度优先遍历;v1v2v3v4v5v6v7v8v9广度优先遍历;v1v2v3v4v7v5v6v8v9文案大全实用文档四、论述题写出下面带权有向图的的关键路径。解：(1)1->2->5->8->9设将整数1、2、3、4依次进栈，请回答下述问题：1）若入、出栈顺序为Push(1)，Pop()，Push(2)，Push(3)，Pop()，Pop()，Push(4)，Pop()，则出栈的数字序列是什么？2）能否得到出栈序列1432和1423？并说明为什么不能得到或者如何得到？解：(1):1324(2):可以得到1432 不能得到1423得 到 1432 的 过 程 为 ：Push(1),pop(),push(2),push(3),push(4),pop(),pop(),pop(),不能得到1423无法执行此操作文案大全实用文档求出下图的最小生成树。求出下图的最小生成树。

（答案略）（答案略）文案大全实用文档查找一、简答题1.关键字集合{19，01，23，14，55，68，11，82，36}，哈希函数为：H(key)=keyMOD9构建哈希表，采用开放定址法解决冲突。（答案略）2.关键字集合