数据结构考试题库Word下载.docx
《数据结构考试题库Word下载.docx》由会员分享，可在线阅读，更多相关《数据结构考试题库Word下载.docx（16页珍藏版）》请在冰点文库上搜索。
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），当rear<
front时，队列长度为（rear-front+max）。
14.在一个长度为n的线性表中的第i个元素（1≤i≤n）之前插入一个元素时，需向后移动（n-i+1）个元素。
15.在具有n个单元的循环队列中，队满时共有（n-1）个元素。
16.带有一个头结点的单链表Head为空的条件是（Head->
next==null）。
17.在一个单链表中删除指针p所指向结点的后继结点时，需要把（p->
next->
next）值赋给p->
next指针域。
18.一个顺序循环队列存于a[M]中，假定队首和队尾指针分别为front和rear，则判断队空的条件为（==，判断队满的条件为（（+1）%M==。
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;
>
s->
link=q;
>
link=s->
link=p;
2.对于顺序存储的队列，存储空间大小为n，头指针为F，尾指
针为R。
若在逻辑上看一个环，则队列中元素的个数（A）。
+R-FC.（R-F+1）modnD.（n+R-F）modn
3.如下陈述中正确的是（A）。
A.串是一种特殊的线性表B.串的长度必须大于零
C.串中元素只能是字母D.空串就是空白串
4.若让元素1，2，3依次进栈，则出栈次序不可能出现（C）
的情况。
，2，1，1，3，1，2，3，2
5.判定一个队列QU（最多元素为m0）为空的条件是（C）。
rear-QU->
front==m0>
front-1==m0
front==QU->
rear>
rear+1
6.设目标串S=‘abcdef’，模式串p=‘de’，则第（C）次匹配成功。
7.设字符串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）。
9.非空的循环单链表head的尾结点（由p所指向）满足（C）。
next==NULL==NULL
next==head==head
10.在一个链队中，假设f和r分别为队首和队尾指针，则删除
一个结点的运算时（C）。
=f->
next;
=r->
11.在一个长度为n的线性表中，删除值为x的元素时，需要比较元素和移动元素的总次数为（C）。
A.（n+1）/22+1
12.在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（B）个指针域的值。
13.线性结构中，每个结点（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）。
16.学生成绩表是一种（C）结构。
A.图形B.树形C.线性D.集合
17.在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算时（C）。
next=s;
f=s;
r=s;
>
next=r;
next=f;
18.向顺序表中的i位置处插入元素，下面哪项能够准确的表明
i的位置是合法的。
（D）
<
=1||i>
l->
length+1>
=1
=l->
length+1<
=i<
length+1
19.设线性链表中结点的结构为（data，next），已知指针q所指结点是指针p所指结点的直接后继，若在*q和*p之间插入结点*s，则应执行（A）操作。
next=p->
next=p;
next=s->
next==s;
next=q;
20.一个栈的入栈序列为a，b，c，d，e，则出栈序列不可能的是（C）。
21.如果以链表作为栈的存储结构，则出栈操作时（B）。
A.必须判别栈是否满B.必须判别栈是否为空
C.必须判别栈元素类型D.可不做任何判断
22.设有两个串p和q，求q在p中首次出现的位置的运算称为（B）。
A.连接B.模式匹配C.求子串D.求串长
指向线性链表中的某一结点，则在线性链表的表尾插入结
点S的语句序列是（A）。
（p->
next!
=NULL）p=p->
next=NULL;
（p!
next=NULL;
p->
->
s->
next=p
24.向顺序栈中压入新元素时，应当（A）。
A.先移动栈顶指针，再存入元素B.先存入元素，再移动栈顶指针
C.先后次序无关紧要D.同时进行
25.假定一个顺序队列的队首和队尾指针分别为f和r，则判断队空的条件为（D）。
f+1==r+1==f==0==r
26.栈的插入和删除操作在（A）进行。
A.栈顶B.栈底C.任意位置D.指定位置
27.栈和队列的共同点是（C）。
A.都是先进后出B.都是先进先出
C.只允许在端点处插入和删除元素D.没有共同点
28.若6行8列的数组以列序为主序顺序存储，基地址为1000，每个元素占2个存储单元，则第5行第3列的元素（假定无第0行第0列）的地址是（B）。
D.答案A，B，C都不对
29.设有50行的二维数组A[50][60]，其元素长度为2字节，按行优先顺序存储，基地址为100，则元素A[18][25]的存储地址为（D）。
三、论述题
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.在树型结构中，根结点没有前驱结点，其余每个结点有且仅有
（一）个前驱结点；
叶子结点（没有）后继结点，其余每个结点都可以有（一或多个）个后继结点。
9.在最优二叉树中没有度为1的结点，则一棵有n个叶子结点的最优二叉树中共有（2n-1）个结点。
10.深度为4（设根的层数为1）的二叉树至少有（4）个结点，至多有（15）个结点，第i层上至多有（2n-1）个结点。
11.深度为6（设根的层数为1）的二叉树至少有（6）个结点，至多有（63）个结点，第4层上至多有（8）个结点。
B.N+1D.不确定
注：
1:
B2:
D3:
A4:
B
5.下面（A）是对的。
A.哈夫曼树中结点的度只可能是0和2。
B.二叉树的顺序存储中，是以先序遍历存储结点的。
C.完全二叉树实际上就是满二叉树。
D.一棵二叉树第i层的最大结点数为2i-1。
6.将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。
编号为49的结点X的右孩子编号为（B）。
D.无法确定
7.先序为A，B，C且后序为C，B，A的二叉树共有（B）种。
8.在一棵度为3的树中，度为3的结点个数为2，度为2的结点个
数为1，则度为0的结点个数为（C）。
9.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（B）。
10.一个具有767个结点的完全二叉树，其叶子结点个数为（B）。
11.在一棵具有35个结点的完全二叉树中，该树的深度为（A）。
12.由三个结点构成的二叉树，共有（B）种不同的结构。
13.深度为k的二叉树至多有（2K-1）个结点（k≥1）。
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,A
2.如下图的森林转化为二叉树。
此题没法写略略略
3.已知某二叉树的前序序列为EBADCFHGI，中序序列为ABCDEFGHI，请给出二叉树且写出二叉树的后序序列。
二叉树略
后序序列:
A,C,D,B,G,I,H,F,E
4.试用权集合{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）=213
5.试按表（10，18，9，2，20，5，6，15，19，25）中元素的排列次序，将所有元素插入一棵初始为空的二叉排序树中，使之仍是一棵二叉排序树。
（1）试画出插入完成之后的二叉排序树；
（2）若查找元素2，它将依次与二叉排序树中哪些元素比较大小?
（3）对该树进行中序遍历，试写出中序遍历序列。
（2）10,9,2
（3）2,5,6,9,10,15,18,19,20,25
6.已知一棵二叉树的顺序存储表示如下，其中0表示空，请分
别写出二叉的先序、中序、后序遍历序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
20
46
15
30
18
35
先序序列：
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
7.将如下图的一般树转化为二叉树。
8.将下图中的二叉树转换成森林。
四、论述题
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中，若A[i][j]等于1，则A[j][i]等于
（1）。
5.图的（深度）优先搜索遍历算法是一种递归算法，图的（广度）优先搜索遍历算法需要使用队列
1.一个有n个顶点的无向图最多有（C）条边。
（n-1）（n-1）/2
2.在一个无向图中，所有顶点的度数之和等于所有边数的（B）倍。
2
3.在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之为（D）。
+e
1.给出如下图所示的无向图G的邻接矩阵存储结构。
（答案略）
2.画出下图的邻接表存储结构。
3.给出下图从A点出发的深度优先遍历和广度优先遍历的顶点
序列。
深度优先遍历：
AECDB
广度优先遍历：
AEBDC
5.给出从V1点出发的深度优先遍历和广度优先遍历的顶点序列。
深度优先遍历;
v1v2v3v4v5v6v7v8v9
广度优先遍历;
v1v2v3v4v7v5v6v8v9
1.写出下面带权有向图的的关键路径。
（1）1->
2->
5->
8->
2.设将整数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）=keyMOD9
构建哈希表，采用开放定址法解决冲突。
2.关键字集合{19，14，23，01，68，20，84，27，55，11，
10，79}，哈希函数为：
H（key）=keyMOD12构建哈希表，采用开放定址法解决冲突。
排序
1.快速排序的最坏情况，其待排序的初始排列是（逆序）。
2.假定一组记录的排序码为（46，79，56，38，40，80，36，40，75，66，84，24），对其进行归并排序的过程中，第3趟归并后，结果为（[36,38,40,40,46,56,79,80][24,66,75,84]）。
1.用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：
20，15，21，25，47，27，68，35，84
15，20，21，25，35，27，47，68，84
15，20，21，25，27，35，47，68，84
则所采用的排序方法是（D）。
A.选择排序B.希尔排序C.归并排序D.快速排序
三、简答题
1.已知一组记录的排序码为（46，79，56，52，38，40，80，31，95，24），写出对其进行快速排序的每一趟划分结果。
过程如下：
一趟：
24,31,40,38,{46},52,80,56,75,79
二趟：
{24},31,40,38,{46},{52},80,56,95,79
三趟：
{24},{31},40,38,{46},{52},79,56,{80},95
四趟：
{24},{31},38,{40},{46},{52},56,{79},{80},95
2.一组记录的关键码为（46，79，56，38，40，84），利用希尔排序方法进行排序。
如下所示
38,40,56,46,79,84
38,40,46,56,79,84
3.一组记录的关键码为（49，38，65，97，76，13，27，4），利用起泡法进行排序（表示绝对不会考）
4.算法的要求：
（1）正确性
（2）可读性（3）健壮性（4）效率和低存储量要求
5.算法的特点：
（1）有穷性
（2）确定性（3）可行性（4）输入（5）输出
升级会员 