数据结构考试题库

1、精选欢迎下载绪论一、填空题1.数据的逻辑结构被分为集合、 （线性结构）、（树形结构）和（图状结构）四种。2. 物理结构是数据结构在计算机中的表示，又称为（存储结构）。3. 数据元素的逻辑结构包括 （线性）、（树）和图状结构 3 种类 型，树形结构和图状结构合称为 （非线 性结构）。4. （数据元素）是数据的基本单位， （数据项）是数据不可分割的最小单位。5. 线性结构中元素之间存在 （一个对一个）关系，树形结构中元素之间 存在 （一个对多个）关系，图 状结构中元素之间存在 （多个对多个）关系。？ 6.数据结构是一门研究非数值计算的程序设计问题中：计算机的（数据元素）以及它们之间的 （关系）和（

2、运筹 ）等的学科。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. 线性表若采用链式存

3、储结构时，要求内存中可用存储单元的 地址 (D)。A.必须是连续的 B.部分地址必须是连续的 C. 一定是不连续的 D.连续不连续都可以三、简答题1.算法的特性是什么。精选欢迎下载答：有穷性 确定性 可行性 有0或多个输入 有1或多个输出线性结构一、填空题1.在一个长度为 n 的线性表中删除第 i 个元素（1E冷）时， 需向前移动（n-i）个元素。2 .从循环队列中删除一个元素时，其操作是（先移动队首指针，后取出元素）。3. 在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为（p- next）。4. 在一个单链表中指针 p 所指向结点的后面插入一个指针q 所指向的结点时

4、，首先把（p-next）的值赋给 q-next ，然后 （q-date）的值赋给 p-next 。5. 从一个栈删除元素时，首先取出 （栈顶元素），然后再使 （栈顶指针）减 1 。6. 子串的定位操作通常称做串的（模式匹配）。7. 设目标 T= abccdcdccbaa ，模式 P= cdcc 则第（六）次匹配成功。 。8. 顺序栈 S 中 ， 出 栈操作时 要执行的 语句序列 中有 S-top（-）；进栈操作时要执行的语句 序列中有 S-top（+）。精选欢迎下载9. 顺序表中逻辑上相邻元素的物理位置（一定）紧邻；单链表中 逻辑上相邻元素的物理位置 （不一定）紧邻。10. 在（循环）链表中，

5、从任何一结点出发都能访问到表中的所有结点。11. 栈和队列均是 (运算受限)的线性表，栈的特点是 (先进后出 后进先出)；队列的特点是 (先进先出 后进后出)。12. 通常，在程序中使用的串可分为串常量和串变量；而串按存储方式又可分为(定长顺序存储)和(堆分配存储)。13. 循环队列头指针 front 指向队头元素，队尾指针 rear 指向队 尾元素后的一个空闲元素，队列的 最 大 空间 为 Queuelen 。在 循 环 队 列 中 ，队 空 标 志 为 (front=rear) ，队 满 标 志 为 (rear+1)%max=front)。当 rear=front 时，队列长度为(rear

6、-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) ， 则 H

7、ead( 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-

8、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)mod n D.(n+R-F)mod n3. 如下陈述中正确的是 (A)。A.串是一种特殊的线性表B.串的长度必须大于零C. 串中元素只能是字母 D. 空串就是空白串4. 若让元素 1， 2，3 依次进栈，则出栈次序不可能出现(C)的情况。A.3 ，2，1B.2，1，3 C.3，1

9、，2 D.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.2 C.4 D.57. 设字符串 s1= A BCDEFG ，S2= PQRST ， T ， sub1 ，sub2 为空。 则运算 s=Concat(T ，SubLength(s2) ，2) 后的串精选欢迎下载串 SubString(sub1 ， s1 ，

10、 2 ， SubLength(s2) ， SubString(sub2 ，s1 ，T 值为 (D) 。A.BCDEF B.BCDEFG C. BCPQRST D.BCDEFEF 8.一个顺序线性表第一个元素的存储地址是100 ，每个元素的长度为 2，则第 5 个元素的地址是 (B)。A.100 B.108 C.110 D.1209.非空的循环单链表 head 的尾结点(由 p 所指向)满足 (C)。 A.p-next=NULLB.p=NULLC.p-next=headD.p=head10.在一个链队中，假设 f 和 r 分别为队首和队尾指针，则删除 一个结点的运算时 (C)。A.r=f-nex

11、t; B.r=r-next;C.f=f-next; D.f=r-next;11.在一个长度为 n 的线性表中， 删除值为 x 的元素时， 需要比 较元素和移动元素的总次数为 (C)。A.(n+1)/2B.n/2 C.n D.n+1精选欢迎下载12.在一个单链表中，若要在 p 所指向的结点之后插入一个新结点，则需要相继修改 侣)个指针域的A.1 B.2 C.3 D.413. 线性结构中，每个结点 (C)。A.无直接前驱B.只有一个直接前驱和个数不受限制的直接后继C. 只有一个直接前驱和后继D. 有个数不受限制的直接前驱和后继14. 队列是限定在(D)进行操作的线性表。A. 中间 B. 队头 C.

12、 队尾 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.BCPQRST D.BCDEFEF16. 学生成绩表是一种(C)结构。精选欢迎下载A. 图形B. 树形C. 线性 D. 集合17.

13、 在一个链队中，假设 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;18.向顺序表中的 i 位置处插入元素，下面哪项能够准确的表明i 的位置是合法的。 (D)A.il-length+1 B.i=1C.i=l-length+1 D.1=ilength+119.设线性链表中结点的结构为(data ，next )，已知指针 q 所 指结点是指针 p 所指结点的直接后继，若在*q 和*p 之间插入结点*s，则应执行(A)操作。A.s-next=

14、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.dcbae C.dceab D.abcde21. 如果以链表作为栈的存储结构，则出栈操作时(B)。精选欢迎下载A. 必须判别栈是否满B. 必须判别栈是否为空C. 必须判别栈元素类型 D. 可不做任何判断22. 设有两个串 p 和 q ，求 q 在 p 中首次出现的位置的运算称为 (B)。A. 连接 B. 模式匹配 C.

15、求子串 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.先移动栈顶指针，再

16、存入元素B.先存入元素，再移动栈顶指针C. 先后次序无关紧要D. 同时进行25. 假定一个顺序队列的队首和队尾指针分别为f 和 r,则判断队空的条件为(D)。f+1=rB.r+1=f C.f=0 D.f=r26. 栈的插入和删除操作在(A)进行。精选欢迎下载A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置27. 栈和队列的共同点是 (C)。A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点28.若 6 行 8 列的数组以列序为主序顺序存储，基地址为 1000， 每个元素占 2 个存储单元，则第 5 行第 3列的元素 (假定无第 0 行第 0 列)的地址

17、是 (B)。A.1086 B.1032C.1068 D.答案 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 个元素

18、，并由 e 返回 其值。略树形结构一、填空题1.赫夫曼树，又称最优树，是一类 （带权路径）长度最短的树。2.在一棵二叉树中，第 5 层上的结点数最多为 （16）个。3. 一棵高度为 5 的二叉树中最少含有 （5）个结点，最多含 有 （31）个结点。4. 若一棵二叉树中有 8 个度为 2 的结点，则它有 （9）个叶子。5. 一棵深度为 6 的满二叉树有 （31）个非终端结点。精选欢迎下载6. 树中结点 A 的（子树数）称为结点 A 的度。7.对一棵二叉排序树进行中序遍历时，得到的结点序列是一个（升序序列）。8.在树型结构中，根结点没有前驱结点，其余每个结点有且仅有（一）个前驱结点；叶子结点（没有

19、）后继结点，其余每个结点都可以有 （一或多个）个后继结点。精选欢迎下载9. 在最优二叉树中没有度为 1 的结点，则一棵有 n 个叶子结点的最优二叉树中共有(2n-1)个结点。10. 深度为 4(设根的层数为 1 )的二叉树至少有(4)个结点，至多有(15)个结点，第 i 层上至多有(2n-1) 个结点。1 具有65个结点的完全二叉树的高度为()o2.有门(n0)个结点的完全二叉树的深度是()QA- log2(n)lB. Iog2(n) + 1c. llog2(n + 1)1D. Llog2(n)J + 13.在一棵完全二叉树中，若编号为i的的结点存在左孩子，则 左孩子结点的编号为()。A.2i

20、B. 2i-1C.2i+1D.2i+211.深度为 6 (设根的层数为有(8)个结点。1 )的二叉树至少有(6)个结点，至多有(63)个结点，第 4 层上至多A. 8B 7C.D.精选欢迎下载4一棵门个结点的二叉树，其空指针域的个数为()o精选欢迎下载A.n B. N+1 C.n-1 D. 不确定 注： 1:B 2:D 3:A 4:B 5下面(A)是对的。A. 哈夫曼树中结点的度只可能是 0 和 2C. 完全二叉树实际上就是满二叉树。6.将含 100 个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为 1。编号为 49 的结点 X 的右孩子编号为 (B)。A.98B

21、.99C.24D.无法确定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.71 C.48 D.5310. 一个具有 767 个结点的完全二叉树， 其叶子结点个数为 (B)。 A.382 B.384 C.385 D.386B. 二叉树的顺序存储中，是以先序遍历存储结点的D. 一

22、棵二叉树第 i 层的最大结点数为 2i-1 。精选欢迎下载11. 在一棵具有 35 个结点的完全二叉树中， 该树的深度为 (A)。 A.6 B.7 C.5 D.812. 由三个结点构成的二叉树，共有(B)种不同的结构。A.3B.4 C.5D.613. 深度为 k 的二叉树至多有(2K-1)个结点(k)。A.2k B.2k-1C.2k-1 D.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

23、,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;带权路径长度为

24、：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,25精选欢迎下载6.已知一棵二叉树的顺序存储表示如下，其中0 表示空，请分别写出二叉的先序、中序、后序遍历序列。1234567

25、891011121320846515300001018035解：先序序列：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.将下图中的二叉树转换成森林精选欢迎下载四、论述题1.由分别带权为 3，12，9，2，5，7 的叶子结点构造一棵哈夫 曼树，并计算该树的带权路径长度。解:带权路径长度为:91图状结构一、填空题1. 若一个图的顶点集为a , b, c, d, e, f，边集为(a , b), (a , c), (b,

26、c), (d , e),则该图含有 (3)个连通分量。2. 具有 10 个顶点的无向图，边的总数最多为(45)。3. 图的广度优先搜索遍历类似于树的(按层次)遍历的过程。4. 在无向图 G 的邻接矩阵 A 中，若 Aij 等于 1，则 Aji 等于(1)。精选欢迎下载5.图的 （深度）优先搜索遍历算法是一种递归算法，图的（广度） 优先搜索遍历算法需要使用队列二、选择题1. 一个有 n 个顶点的无向图最多有（C）条边。A.nB.n（n-1）C.n（n-1）/2 D.2n2. 在一个无向图中，所有顶点的度数之和等于所有边数的（B）倍。A.3B.2 C.1D.1/23. 在一个具有 n 个顶点的无向

27、图中，若具有 e 条边，则所有顶点的度数之为（D）。A.n B.e C.n+e D.2e三、简答题1.给出如下图所示的无向图 G 的邻接矩阵存储结构。（答案略）精选欢迎下载精选欢迎下载3.给出下图从 A 点出发的深度优先遍历和广度优先遍历的顶点a 01001 1序列。b10010解：深度优先遍历：AECDB匚0001 1d广度优先遍历：AEBDC己0110110110精选欢迎下载5.给出从 V1 点出发的深度优先遍历和广度优先遍历的顶点序列解：深度优先遍历;v1 v2 v3 v4 v5 v6 v7 v8 v9广度优先遍历；v1 v2 v3 v4 v7 v5 v6 v8 v9四、论述题1.写出下

28、面带权有向图的的关键路径精选欢迎下载解：(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无法执行此操作精选4.求出下图的最小生成树。（答案略）3.求出下图的最小生成树。（答案略）精选欢迎下载查找一、简答题1.关键字集合 19 ，01，23，14，55，68，11，82，36 ，哈希函数为： H(key)=key 构建哈希表，采用开放定址法解决冲突。(答案略)2.关键字集合 19 ，14，23，01，68，20，84，27，55，11，