数据结构考试题库

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

2、确定性、（输入）、 （输出）和 （可行性）。二、选择题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.部分地址必

3、须是连续的C. 一定是不连续的D.连续不连续都可以三、简答题1. 算法的特性是什么。答：有穷性确定性可行性有 0 或多个输入有 1 或多个输出线性结构一、填空题1 .在一个长度为n的线性表中删除第i个元素（1W而）时，需向前移动（n-i）个元素。2 .从循环队列中删除一个元素时，其操作是（先移动队首指针，后取出元素）。3 .在线性表的单链接存储中，若一个元素所在结点的地址为p,则其后继结点的地址为（p->next）。4 . 在一个单链表中指针p 所指向结点的后面插入一个指针q 所指向的结点时，首先把 （p->next ）的值q->next ，然后 （q->date ）的

4、值赋给p->next 。5 .从一个栈删除元素时，首先取出（栈顶元素），然后再使（栈顶指针）减1。6 .子串的定位操作通常称做串的（模式匹配）。7 .设目标T=abccdcdccbaa ，模式 P= cdcc 则第 （六 ）次匹配成功。8 . 顺序栈 S 中 ， 出 栈操作时要执行的语句序列中有 S->top（ -）；进栈操作时要执行的语句S->top（ +）。9 .顺序表中逻辑上相邻元素的物理位置（一定）紧邻；单链表中逻辑上相邻元素的物理位置（不一定 ）紧邻。10 . 在 （循环）链表中，从任何一结点出发都能访问到表中的所有结点。11.栈和队列均是（运算受限）的线性表，栈的

5、特点是（先进后出后进先出）；队列的特点是（先进先出）。12. 通常，在程序中使用的串可分为串常量和串变量；而串按存储方式又可分为（定长顺序存储）和（堆分配存储）。13. 循环队列头指针front 指向队头元素，队尾指针rear 指向队 尾元素后的一个空闲元素，队列的大 空 间 为 Queuelen 。 在 循 环 队 列 中 ， 队 空 标 志 为 （front=rear ） ， 队 满 标 志 为（ rear+1 ） %max=front ）。当 rear>=front 时，队列长度为（rear-front ），当 rear<front 时，队列长（rear-front+max

6、）。14. 在一个长度为n的线性表中的第i个元素（1W而）之前插入一个元素时，需向后移动（n-i+1）个015. 在具有n 个单元的循环队列中，队满时共有（n-1 ）个元素。16. 带有一个头结点的单链表Head 为空的条件是（Head->next=null ）。17. 在一个单链表中删除指针p 所指向结点的后继结点时，需要把（ p->next->next ）值赋给p->next指针域。18. 一个顺序循环队列存于aM中，假定队首和队尾指针分别为front和rear,则判断队空的条件( a.front=a.rear )，判断队满的条件为( a.rear+1 ) %M=a

7、.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

8、 . 在一个单链表中，若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,尾指针为Ro若在逻辑上看一个环，则队列中元素的个数(A)。A.R-F B.n+R-F C.(R-F+1)mod n D.(n+R-F)mod n3 .如下陈述中

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

10、 de',则第(C)次匹配成功。A.1B.2C.4D.5。 则运算 s=Concat(T ，SubLength(s2) ， 2) 后的串7 .设字符串s1=ABCDEFG ， S2=PQRST ， T， sub1 ， sub2 为空串SubString(sub1 ， s1 ，2 ， SubLength(s2) ， SubString(sub2 ， s1 ，T 值为 ( D)。A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF 8 .一个顺序线性表第一个元素的存储地址是100， 每个元素的长度为2， 则第5个元素的地址是( B)。A.100B.108C.11

11、0D.1209 .非空的循环单链表head 的尾结点(由p 所指向)满足(C)。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/2 C.n D.n+112 .在一个单链表中，若要在p所指向的结点之后插入一个新结 点，则

12、需要相继修改(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， StrLe

13、n(S2) ， StrSub(S1 ， StrLen (S2) ， 2)的结果串是(D)。A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF16 .学生成绩表是一种(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;18 . 向顺序表中的i 位置处插入元素，下面哪项能够准确的表明i 的位置是合法的。(D)A.i<=

14、1|i>l->length+1B.i>=1C.i>=l->length+1D.1<=i<=l->length+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 .

15、一个栈的入栈序列为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. 求子串D. 求串长23 .p 指向线性链表中的某一结点，则在线性链表的表尾插入结点 S 的语句序列是(A)。A.while(p->next!=NULL) p=p->next; p->next=s;

16、 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. 假

17、定一个顺序队列的队首和队尾指针分别为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 个存储单元，则第53 列的元素(假定无第0 行第 0 列 )的地址是(B)。A.1086 B.1032 C.1068 D.答案 A, B, C 都不对29. 设有 50 行的二维数组A5060 ，

18、其元素长度为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 .一棵高度

19、为5 的二叉树中最少含有（5）个结点，最多含有 （31 ）个结点。4 .若一棵二叉树中有8 个度为 2 的结点，则它有（9）个叶子。5 .一棵深度为6 的满二叉树有（31）个非终端结点。6 .树中结点A的（子树数）称为结点A的度。7 .对一棵二叉排序树进行中序遍历时，得到的结点序列是一个（升序序列）。8 . 在树型结构中，根结点没有前驱结点，其余每个结点有且仅有（一 ）个前驱结点；叶子结点（没有）（一或多个）个后继结点。欢迎下载精选9 .在最优二叉树中没有度为1的结点，则一棵有n个叶子结点的最优二叉树中共有 （2n-1）个结点。10 .深度为4（设根的层数为1）的二叉树至少有（4）个结点，至多

20、有（15）个结点，第i层上至多有（2n-1） 个结点。11 .深度为6 （设根的层数为1）的二叉树至少有（6）个结点，至多有（63）个结点，第4层上至多 有（8）自点选择题1 .具有65个结点的完全二叉树的高度为（）。A. 8B, 7C. 60. 52 .有n （n>0）个结点的完全二叉树的深度是（）。A Jog2（MB. log2（n） + 1C. llog2（n + 1）1D. Llog2（n）J + 13 .在一棵完全二叉树中，若编号为i的的结点存在左孩子，则左孩子结点的编号为（）。A. 2iB. 2i-1C. 2i+1 D. 2i+24 . 一棵n个结点的二叉树，其空指针域的个数

21、为（）。A.n B. N+1C.n-1 D.不确定注： 1:B2:D 3:A4:B5 .下面(A)是对的。A. 哈夫曼树中结点的度只可能是0 和2。B. 二叉树的顺序存储中，是以先序遍历存储结点的。C. 完全二叉树实际上就是满二叉树。D. 一棵二叉树第i 层的最大结点数为2i-1 。6.将含 100 个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号1 。编号为49 的结点 X 的右孩子编号为(B)。A.98B.99 C.24D.无法确定7 .先序为A, B, C且后序为C, B, A的二叉树共有(B)种。A.3 B.4C.5D.68 .在一棵度为3 的树中，度为3

22、的结点个数为2，度为2 的结点个数为 1 ，则度为0 的结点个数为(C)。A.4 B.5C.6D.79 .由权值分别为11 ， 8， 6， 2， 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为(B)。A.24B.71 C.48 D.5310 . 一个具有767 个结点的完全二叉树，其叶子结点个数为（B）。A.382 B.384C.385D.38611 . 在一棵具有35 个结点的完全二叉树中，该树的深度为（A）。A.6 B.7C.5D.812 .由三个结点构成的二叉树，共有（B）种不同的结构。A.3B.4C.5D.613 .深度为k的二叉树至多有（2K-1）个结点（k当）。A.2k B.2

23、k-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,I,J,H,G,D,A2 .如下图的森林转化为二叉树。欢迎下载精选欢迎下载精选解：此题没法写略略略3 . 已 知 某 二 叉 树 的 前 序 序 列 为 EBADCFHGI ， 中 序 序 列 为 ABCDEFGHI ， 请给 由二叉树且写生二叉树的后序序列。解：二叉树略后序序列:A,C,D,B,G,I,H,F,E4 .试用权集合6， 4， 8， 3， 7

24、， 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) 对该树进行中序遍历，试写出中序遍历序列。解：

25、(1)略(2)10,9,2(3)2,5,6,9,10,15,18,19,20,25欢迎下载精选6 .已知一棵二叉树的顺序存储表示如下，其中0表示空，请分别写生二叉的先序、中序、后序遍历序列。12345678910n121320846515300001018035解：先序序列：20,8,5,15,10,18,46,30,35中序序歹 U: 5,8,10,15,18,20,30,35,46后序序歹 U: 5,10,18,15,8,35,30,46,207 .将如下图的一般树转化为二叉树。精选欢迎下载8.将下图中的二叉树转换成森林四、论述题1.由分别带权为3， 12， 9， 2， 5， 7 的叶子结

26、点构造一棵哈夫曼树，并计算该树的带权路径长度。解 :带权路径长度为: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）

27、条边。A.nB.n（n-1）C.n（n-1）/2D.2n2 .在一个无向图中，所有顶点的度数之和等于所有边数的（B）倍。A.3B.2C.1D.1/23 .在一个具有n 个顶点的无向图中，若具有e 条边，则所有顶点的度数之为（D） 。A.n B.e C.n+e D.2e三、简答题1. 给出如下图所示的无向图G 的邻接矩阵存储结构。（答案略）2.画由下图的邻接表存储结构（答案略）a b c d e0 1 01 0 00 0 00 1 11 0 10 11 01 10 1 '1 0 13.给由下图从A点生发的深度优先遍历和广度优先遍历的顶点 序列。解：深度优先遍历：AECDB广度优先遍历：A

28、EBDC5.给由从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得至U 1432 的过程为：Push(1),pop(),push(2),push(3),push(4),pop(),pop(),pop(),不能得到1423 无法执行此操作精选3.求生下图的最小生成树。（答案略）4.求生下图的最小生成树。（答案略）精选欢迎下载查找、简答题MOD 91 .关键字集合19， 01 ， 23， 14， 55， 68， 11 ， 82， 36，哈希函数为：H(key)=key构建哈希表，采用开放定址法解决冲突。(答案略)20， 84， 2