数据结构考试题库.doc

绪论一、填空题1.数据的逻辑结构被分为集合、(线性结构树形结构)和(图状结构)四种。)、 (2.物理结构是数据结构在计算机中的表示，又称为(存储结构)。非线3.数据元素的逻辑结构包括(线性树)、 ( )和图状结构 3 种类 型，树形结构和图状结构合称为 (性结构 )。数据项4.(数据元素)是数据的基本单位，)是数据不可分割的最小单位。(5.线性结构中元素之间存在(一个对一个 )关系，树形结构中元素之间存在 (一个对多个 )关系，图多个对多个)关系。状结构中元素之间存在 (数据元素关？ 6.数据结构是一门研究非数值计算的程序设计问题中：计算机的()以及它们之间的(系 )和 (运筹 )等的学科。7.算法的五个重要特性为有穷性、确定性、(输入 )、(输出 )和 (可行性 )。二、选择题1.数据的不可分割的基本单位是(D)。A.元素 B.结点C.数据类型D.数据项*2. 线性表的逻辑顺序与存储顺序总是一致的，这种说法(B)。A.正确B.不正确C.不确定D.无法选择3.线性结构是指数据元素之间存在一种(D)。A.一对多关系 B.多对多关系C.多对一关系D.一对一关系4.在数据结构中，从逻辑上可以把数据结构分成(A)。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构5.线性表若采用链式存储结构时，要求内存中可用存储单元的地址 ( D)。A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以三、简答题1.算法的特性是什么。答：有穷性确定性可行性有 0 或多个输入有 1 或多个输出线性结构一、填空题n-i1.在一个长度为 n 的线性表中删除第 i 个元素（ 1 i n）时， 需向前移动 ()个元素。2.从循环队列中删除一个元素时，其操作是(先移动队首指针，后取出元素)。p-next3.在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为()。4.在一个单链表中指针 p 所指向结点的后面插入一个指针q 所指向的结点时，首先把 (p-next)的值赋给 q-next ，然后 (q-date)的值赋给 p-next 。5.从一个栈删除元素时，首先取出(栈顶元素 )，然后再使 (栈顶指针 )减 1。6.子串的定位操作通常称做串的(模式匹配 )。7.设目标 T= abccdcdccbaa，模式 P= cdcc则第 (六)次匹配成功。8. 顺序栈 S 中 ， 出 栈操作时 要执行的语句序列中有 S-top(-)；进栈操作时要执行的语句序列中有 S-top(+)。9.顺序表中逻辑上相邻元素的物理位置 (一定 )紧邻；单链表中 逻辑上相邻元素的物理位置 (不一定紧邻。10.在 (循环 )链表中，从任何一结点出发都能访问到表中的所有结点。11. 栈和队列均是 ( 运算受限 ) 的线性表，栈的特点是 ( 先进后出 后进先出 ) ；队列的特点是 ( 先进先出 后进后出 )。12.通常，在程序中使用的串可分为串常量和串变量；而串按存储方式又可分为(定长顺序存储 )和(堆分配存储 )。13.循环队列头指针front 指向队头元素，队尾指针rear 指向队尾元素后的一个空闲元素，队列的最大空间为Queuelen 。 在 循 环 队 列 中，队空标志为(front=rear队满标志为) ，(（rear+1）%max=front)。 当 rear=front时，队列长度为 (rear-front)，当 rearnext=null)。17.在一个单链表中删除指针p 所指向结点的后继结点时，需要把(p-next-next指)值赋给 p-next针域。18.一个顺序循环队列存于aM 中，假定队首和队尾指针分别为 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 )=()。（本人不会）21.在循环链表中，每个结点有( 一个 )个指针域，指向其 (后继 )结点，最后一个结点的指针域(为空)。*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;2.对于顺序存储的队列，存储空间大小为n，头指针为 F，尾指针为 R。若在逻辑上看一个环，则队列中元素的个数A( )。A.R-F B.n+R-F C.(R-F+1)modn D.(n+R-F)mod n3.如下陈述中正确的是(A)。A.串是一种特殊的线性表B.串的长度必须大于零C.串中元素只能是字母D.空串就是空白串4.若让元素 1，2， 3 依次进栈，则出栈次序不可能出现(C)的情况。A.3， 2， 1 B.2， 1， 3C.3， 1， 2D.1，3， 25.判定一个队列QU（最多元素为m0 ）为空的条件是(C)。A.QU-rear-QU-front=m0B.QU-rear-QU-front-1=m0C.QU-front=QU-rearD.QU-front=QU-rear+16.设目标串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. BCDEFEF8.一个顺序线性表第一个元素的存储地址是100，每个元素的长度为2，则第 5个元素的地址是(B)。A.100B.108C.110D.120C9.非空的循环单链表 head 的尾结点（由p 所指向）满足 ( )。A.p-next=NULLB.p=NULLC.p-next=headD.p=head10.在一个链队中，假设 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)/2B.n/2C.nD.n+112.在一个单链表中，若要在p 所指向的结点之后插入一个新结点，则需要相继修改(B)个指针域的值。A.1B.2C.3D.413.线性结构中，每个结点(C)。A.无直接前驱B.只有一个直接前驱和个数不受限制的直接后继C.只有一个直接前驱和后继 D.有个数不受限制的直接前驱和后继14.队列是限定在 (D)进行操作的线性表。A.中间B.队头C.队尾D.端点15.设串 S1=“ ABCDEFG，”S2=“ PQRST，”函数 StrCat(x,y)返回 x 和 y 串的连接串，函数StrSub(S， i， j)返回串 S的从序号 i 的字符开始的j 个字符组成的子串，StrLen(S)返回串 S的长度，则 StrCat(StrSub(S1，2， StrLen(S2)， StrSub(S1，StrLen (S2)， 2)的结果串是 (D)。A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF16.学生成绩表是一种(C)结构。A.图形B.树形C.线性D.集合17.在一个链队中，假设f 和 r 分别为队首和队尾指针，则插入s 所指结点的运算时A.f-next=s;f=s;B.r-next=s; r=s;C.s-next=r; r=s;D.s-next=f; f=s;18.向顺序表中的i 位置处插入元素，下面哪项能够准确的表明(C)。i 的位置是合法的。(D)A.il-length+1B.i=1C.i=l-length+1D.1=ilength+119.设线性链表中结点的结构为 （ 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;20.一个栈的入栈序列为a， b， c， d， e，则出栈序列不可能的是 (C)。A.edcba B.dcbaeC.dceab D.abcdeB21.如果以链表作为栈的存储结构，则出栈操作时( )。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=N ULL; 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=p24.向顺序栈中压入新元素时，应当(A)。A.先移动栈顶指针，再存入元素B.先存入元素，再移动栈顶指针C.先后次序无关紧要D.同时进行25.假定一个顺序队列的队首和队尾指针分别为f 和 r ，则判断队空的条件为(D)。f+1=rB.r+1=f C.f=0D.f=r26.栈的插入和删除操作在(A)进行。A.栈顶 B.栈底C.任意位置D.指定位置27.栈和队列的共同点是C( )。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点28.若 6 行 8 列的数组以列序为主序顺序存储，基地址为1000， 每个元素占2 个存储单元，则第 5行第 3 列的元素 (假定无第 0行第 0列 )的地址是 (B)。A.1086 B.1032C.1068D.答案 A， B，C 都不对29.设有 50 行的二维数组A5060 ，其元素长度为 2字节，按 行优先顺序存储，基地址为100，则元素 A1825 的存储地址 为(D)。A.1850B.2188C.1950D.2310三、论述题1.写出线性表的插入算法、删除算法。解：太麻烦略略略*2. 画出主串为 ababcabcacbab，子串为 abc的模式匹配过程。解：四、算法设计题1.在带头结点的单链线性表L 中第 i 个位置之前插入新的元素e。略2.在带头结点的单链线性表L 中，删除第i 个元素，并由e 返回其值。略树形结构一、填空题1.赫夫曼树，又称最优树，是一类(带权路径 )长度最短的树。2.在一棵二叉树中，第5 层上的结点数最多为(16)个。3.一棵高度为5 的二叉树中最少含有(5)个结点，最多含有(31)个结点。4.若一棵二叉树中有8 个度为 2 的结点，则它有(9)个叶子。5.一棵深度为6 的满二叉树有 (31)个非终端结点。6.树中结点A 的 (子树数 )称为结点 A 的度。7.对一棵二叉排序树进行中序遍历时，得到的结点序列是一个(升序序列 )。8.在树型结构中，根结点没有前驱结点，其余每个结点有且仅有(一 )个前驱结点；叶子结点(没有 )后继结点，其余每个结点都可以有(一或多个 )个后继结点。2n-19.在最优二叉树中没有度为1 的结点，则一棵有n 个叶子结点的最优二叉树中共有()个结点。10.深度为 4（设根的层数为4)个结点，至多有15)个结点，第2 -11）的二叉树至少有 (i 层上至多有 ( n)个结点。6634 层上至多有11.深度为 6（设根的层数为 1）的二叉树至少有 ( )个结点，至多有( )个结点，第(8)个结点。A.nB. N+1C.n-1D.不确定注： 1:B2:D3:A5.下面 (A)是对的。4:BA.哈夫曼树中结点的度只可能是0 和 2。 B.二叉树的顺序存储中，是以先序遍历存储结点的。C.完全二叉树实际上就是满二叉树。D.一棵二叉树第i 层的最大结点数为2i-1。6.将含 100 个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为 1。编号为 49 的结点 X 的右孩子编号为 (B)。 A.98 B.99 C.24 D.无法确定7.先序为 A， B，C 且后序为 C， B， A 的二叉树共有 (B)种。A.3B.4C.5D.68.在一棵度为 3 的树中，度为 3 的结点个数为 2，度为 2 的结点个数为 1，则度为 0 的结点个数为 (C)。A.4B.5C.6D.79.由权值分别为 11， 8，6， 2， 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为B( )。A.24B.71C.48D.5310. 一个具有 767 个结点的完全二叉树， 其叶子结点个数为 (B)。 A.382 B.384 C.385 D.38611. 在一棵具有 35 个结点的完全二叉树中，该树的深度为 (A)。A.6 B.7C.5 D.812. 由三个结点构成的二叉树，共有 (B)种不同的结构。A.3B.4 C.5 D.613.深度为k 的二叉树至多有(2K-1)个结点(k 。1)A.2kB.2k-1C.2k-1D.2k三、简答题1.已知一棵二叉树的先序遍历和中序遍历，则该二叉树的后序遍历是什么？先序遍历： 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,A2.如下图的森林转化为二叉树。解：此题没法写略略略3. 已 知 某 二 叉 树 的 前 序 序 列 为 EBADCFHGI， 中 序 序 列 为 ABCDEFGHI，请给出二叉树且写出二叉树的后序序列。解：二叉树略后序序列 :A,C,D,B,G,I,H,F,E4.试用权集合 6， 4， 8，3， 7， 5，10， 8， 2， 1， 11，构造哈夫曼 (Huffman) 树。(1)画出这棵哈夫曼树；(2)分别计算该哈夫曼树的路径长度和带权路径长度。解： (1)略(2)路径长度为： 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)中元素的排 列次序，将所有元素插入一棵初始为空的二叉排序树中，使之 仍是一棵二叉排序树。(1)试画出插入完成之后的二叉排序树； (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,207.将如下图的一般树转化为二叉树。8.将下图中的二叉树转换成森林。BAEGKCFHILJ四、论述题1.由分别带权为 3， 12，9， 2， 5，7 的叶子结点构造一棵哈夫曼树，并计算该树的带权路径长度。解:带权路径长度为 :91图状结构一、填空题1.若一个图的顶点集为a， b， c，d， e， f，边集为 (a， b)， (a， c)， (b， c)， (d，e),则该图含有 (3个连通分量。2.具有 10个顶点的无向图，边的总数最多为(45)。3.图的广度优先搜索遍历类似于树的(按层次 )遍历的过程。4.在无向图 G 的邻接矩阵 A 中，若 Aij 等于 1，则 Aji 等于 (1)。深度)优先搜索遍历算法是一种递归算法，图的(广度) 优先搜索遍历算法需要使用队列5.图的 (二、选择题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.nB.eC.n+eD.2e三、简答题1.给出如下图所示的无向图G 的邻接矩阵存储结构。（答案略）2.画出下图的邻接表存储结构。（答案略）3.给出下图从 A 点出发的深度优先遍历和广度优先遍历的顶点序列。解：深度优先遍历： AECDB广度优先遍历： AEBDC5.给出从 V1 点出发的深度优先遍历和广度优先遍历的顶点序列。解：深度优先遍历 ;v1 v2 v3 v4 v5 v6 v7 v8 v9 广度优先遍历 ;v1 v2 v3 v4 v7 v5 v6 v8 v9四、论述题1.写出下面带权有向图的的关键路径。解： (1)1-2-5-8-92.设将整数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 无法执行此操作3.求出下图的最小生成树。4.求出下图的最小生成树。（答案略）（答案略）查找一、简答题1.关键字集合 19， 01， 23， 14， 55， 68， 11， 82， 36，哈希函数为： H(key)=key MOD 9 构建哈希表，采用开放定址法解决冲突。 （答案略）2.关键字集合 19， 14， 23， 01， 68， 20， 84， 27， 55， 11，10，79，哈希函数为：H(key)=k