数据结构练习题
邻接表：
0| →6|6| →5|4| →4|2| →1|1|^
1| →0|1| →3|8| →2|5|^
2| →1|5| →3|1|^
3| →1|8| →2|1| →4|1| →5|2|^
4| →0|2| →3|1| →5|2|^
5| →0|4| →4|2| →3|2| →6|7|^
6| →0|6| →5|7|^
0→1
0→1，0→4
0→1，0→4→3
0→1，0→4→3→2
0→1，0→4→3→2，0→4→5
0→1，0→4→3→2，0→4→5，0→6
最小生成树：
0→1,4,6
4→3,5
3→2
《数据结构》复习题（三）(1)
1.X.数据是计算机接收,识别,存储,加工处理的对象的全体.
2.√.最后不知道要不要加上一个"运算及实现"
3.√
4.X.先进后出.
5.X
6.√
7.X.最多有2^h -1个结点
8.X
9.√
10.X
二,
1.数据结构.
2.线性结构和非线性结构.
3.顺序表.
4.队列.
5.2^h -1.
6.顺序表.
7.排序.
8.
三.
1.A
2.A.先进先出.
3.没有学.
4.C.
5.B.一串下去.
寻一份《数据结构》试题及答案
《数据结构》试题
一、选择题（每小题2分，共30分）
1． 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。
A、单链表 B、双链表 C、单向循环 D、顺序表
2． 串是任意有限个（ ）
A、符号构成的序列 B、符号构成的集合
C、字符构成的序列 D、字符构成的集合
3． 设矩阵A（aij ，l≤i,j≤ 10）的元素满足：
aij≠0(i≥j, l≤i, j≤ 10)
aij=0 (i<j, l≤i, j≤ 10)
现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A[9][5]的首址为
A、2340 B、2336 C、2164 D、2160
4． 如果以链表作为栈的存储结构，则退栈操作时（ ）
A、 必须判别栈是否满
B、 对栈不作任何判别
C、 必须判别栈是否空
D、 判别栈元素的类型
5． 设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（ ）
A、front=front+1 B、front=(front+1)% m
C、rear=(rear+1)%m D、front=(front+1)%(m+1)
6． 深度为6（根的层次为1）的二叉树至多有（ ）结点。
A、 64 B、32 C、31 D、63
7． 将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点X的双亲编号为（ ）
A、24 B、25 C、23 D、无法确定
8． 设有一个无向图G=（V，E）和G’=（V’，E’）如果G’为G的生成树，则下面不正确的说法是（ ）
A、G’为G 的子图 B、G’为G 的边通分量
C、G’为G的极小连通子图且V’=V D、G’为G的一个无环子图
9． 用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（ ）
A、 一定都是同义词 B、一定都不是同义词
C、都相同 D、不一定都是同义词
10． 二分查找要求被查找的表是（ ）
A、 键值有序的链接表 B、链接表但键值不一定有序
C、 键值有序的顺序表 D、顺序表但键值不一定有序
11． 当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（ ）
A、n2 B、nlog2n C、log2n D、n-1
12． 堆是一个键值序列{k1,k2,…, kn},对i=1,2,…,|_n/2_|,满足( )
A、ki≤k2i≤k2i+1 B、ki<k2i+1<k2i
C、ki≤k2i且ki≤k2i+1(2i+1≤n) D、ki≤k2i 或ki≤k2i+1(2i+1≤n)
13．一个具有n个顶点的无向完全图的边数为（ ）
A、n(n+1)/2 B、n(n-1)/2 C、n(n-1) D、n(n+1)
14．在索引顺序表中查找一个元素，可用的且最快的方法是（ ）
A、用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找
B、用顺序查找法确定元素所在块，再用二分查找法在相应块中查找
C、用二分查找法确定元素所在块，再用顺序查找法在相应块中查找
D、用二分查找法确定元素所在块，再用二分查找法在相应块中查找
15．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（ ）存储方式最节省运算时间。
A、 单链表 B、双链表
C、带头结点的双循环链表 D、容量足够大的顺序表
二、判断题（每小题1分，共10分）
1．双链表中至多只有一个结点的后继指针为空。（ ）
2．在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。（ ）
3．对链表进行插入和删除操作时，不必移动结点。（ ）
4．栈可以作为实现程序设计语言过程调用时的一种数据结构。（ ）
5．在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧<a,b>。( )i
6．对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。( )
7．“顺序查找法”是指在顺序表上进行查找的方法。（ ）
8．向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（）
9．键值序列{A，C，D，E，F，E，F}是一个堆。
10．二路归并时，被归并的两个子序列中的关键字个数一定要相等。（）
三、填空题（每小题2分，共20分）
1．在带有头结点的单链表L中，若要删除第一个结点，则需执行下列三条语句：＿＿＿＿＿＿＿＿；L->next=U->next；free(U)；
2．有一个长度为20的有序表采用二分查找方法进行查找，共有＿＿＿＿＿＿个元素的查找长度为3。
3．采用冒泡排序对有n个记录的表A按键值递增排序，若L的初始状态是按键值递增，则排序过程中记录的比较次数为＿＿＿＿＿。若A的初始状态为递减排列，则记录的交换次数为＿＿＿＿＿＿＿。
4．在无头结点的双链表中，指针P所指结点是第一个结点的条件是＿＿＿＿＿＿。
5．G为无向图，如果从G的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是＿＿＿＿＿图。
6．如果一个有向图中没有＿＿＿＿＿＿，则该图的全部顶点可能排成一个拓扑序列。
7．深度为8（根的层次号为1）的满二叉树有＿＿＿＿＿＿个叶子结点。
8．将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X，其双亲PARENT（X）的编号为＿＿＿＿＿＿＿。
9．设某闭散列表HT未满，散列函数H（KEY）为键值第一字母在字母表中的序号，处理冲突方法为线性探测法，请在下列算法划线处填上适当内容，以实现按键值第一字母的顺序输出闭散列表中所有键值的算法。
void printword(keytype HT[m])
{ for(i=1;i<=26;i++)
{ j=i;
while(____________________)
{ if (____________________) printf(“datatype”,HT[j]);
j=(j+1)% m;
}
}
}
10．设有一个链队，结点结构为data|next，front为队头指针，rear为队尾指针，当执行入队操作时需执行下列语句：
malloc(p)；p->data=x; p->next=NULL；
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿；
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿；
四、简答题：（每小题4分，共20分）
1. 对于一个有10000个结点的二叉树，树叶最多有多少个？最少有多少个？
2. 已知一棵二叉树的中序序列和后序序列分别为： DBGEACHF和DGEBHFCA，则该二叉树的前序序列是什么？
3. 设有1000个无序的元素，需排出前10个最大（小）的元素，你认为采用哪种排序方法最快？为什么？
4. 在KMP算法中，已知模式串为ADABCADADA ，请写出模式串的next[j]函数值。
5. 中序遍历的递归算法平均空间复杂度为多少？
五、 算法设计题（每小题10分，共20分）
1. 试编写一个算法，判断一给定的整型数组a[n]是不是一个堆。
2. 一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积。试写一高效算法，求二叉树的繁茂度。
参考答案
一、选择题
1、D 2、C 3、D 4、C 5、D 6、D 7、A 8、B 9、D 10、C 11、D 12、C
13、B 14、C 15、D
二、判断题
1. √ 2. × 3. √ 4. √ 5. × 6. × 7. × 8. √ 9. √ 10. ×
三、填空题
1．U=L - > next
2．4。
3．n-1、n(n-1)/2。
4．p - > prior = NULL。
5．连通
6．回路或环
7．28-1 = 27 = 128
8．24
9．HT[j]!=NULL或HT[j]不为空、H(HT[j])=I
10．rear - > next = p、rear = p
四、简答题：
1. 答： 最多是完全二叉树的形态，即5000个叶子；最少是单支树的形态，即1个叶子。
2.答：是：ABDEGCFH
3. 答：用锦标赛排序或堆排序很合适，因为不必等全部元素排完就能得到所需结果，
时间效率为O(nlog2n)； 即O（1000log21000）=O(10000)
锦标赛排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089
堆排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089
若用冒泡排序也较快，最多耗费比较次数为（n-1+n-2+……＋n-10）=10n-55=10000-55=9945（次）
4. 答： 0112112343
5. 答： 要考虑递归时占用了栈空间，但递归次数最多不超过树的高度，所以空间复杂度为O(log2n)
五、 算法设计题
1.解：提示：堆的定义是：ki<k2i和K2i＋1
void SortA(sqlist &A, int n)
{ if(n==0) return(0); //空表
if (a[1]<a[2])
{ for( i=1; i<=n/2; i++) if (a[i]>a[2*i]|| a[i]>a[2*i+1])return(-1);
return(minleap)
};
else
{ for( i=1; i<=n/2; i++) if (a[i]<a[2*i]|| a[i]<a[2*i+1])return(-1);
return(“maxleap”)
};
}
2. 要用层次遍历以及队列来处理，可以增设一个宽度计数器，在统计完每一层的结点个数之后,再从计数器中挑出最大值。
typedef struct {
BTNode node; int layer;
//layer是结点所在层数
} BTNRecord, r ;
int Width(Bitree T ){ //求树宽
int count[ ]; //增开count向量，存放各层对应的结点数
InitQueue(Q); //队列初始化，Q的元素为BTNRecord类型
EnQueue(Q,{T, 0}); //根结点入队, 0 表示count[0]，下标值
while(!QueueEmpty(Q))
{ DeQueue(Q, r); //结点出队
count[r.layer]++; //出队时再把结点对应层的计数器加
if(r.node->lchild) EnQueue(Q,{r.node->lchild, r.layer+1});
if(r.node->rchild) EnQueue(Q,{r.node->rchild, r.layer+1});
} //按层序入队时要随时标注结点所在层号
h=r.layer; //最后一个队列元素所在层就是树的高度
for(maxn=count[0], i=1; h; i++)
if(count[i]>maxn) maxn=count[i]; //求出哪一层结点数最多
return (h*
maxn)} // Width
数据结构试题
一.判断题
（ ）1.某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。
正确。第0个元素地址为100，则第i个元素地址为100+4*i，将12代入得148。
（ ）2.在任何一种线性链表上都无法进行随机访问。
错误。比如只要知道顺序表首地址和每个数据元素所占存储单元的个数，就可以求出第i个数据元素的存储地址来，这也是顺序表具有按数据元素的序号随机存取的特点。
（ ）3.顺序栈是一种规定了元素进栈顺序的栈。
错误。按存储结构来分，堆栈分为顺序栈和链栈，其中栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表，却并没有规定元素进栈顺序。
（ ）4.循环列表中每一个元素都有后继。
正确。注意，这里可能有笔误，应写为“循环链表”而非“循环列表”。
（ ）5.删除一个二叉树中的一个结点，再重新插入上去，一定能得到原来的二叉排序树。
错误。
二.填空题。
6.下面程序的时间复杂度为___________。
for (int i=1; i<=m; i++)
for (int j=1; j<=n; j++ )
S+=i
法则1：for循环：一个for循环的运行时间至多是该for循环内语句（包含测试）的运行时间乘以迭代的次数。
法则2：嵌套循环：从里向外分析这些循环。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有循环的大小的乘积。
对于此处嵌套的for循环，根据以上法则，时间复杂度为O(m*n)。
7.在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数是____________。
从第i个元素（原来的）到第n个元素，每个元素后移一位，一共需要n+1-i次。
8.在一个具有n个结点的有序单链表中插入一个新结点，并让插入后的单链表仍然有序，则该操作的时间复杂性数量级为______。
找到节点位置，O(n)；单链表插入操作，O(n)；总的时间复杂度为O(n+n)=O(n)。
9.若用s[1]～s[n]作为两个顺序栈的共同存储空间，左右两个栈的栈顶分别为t1和t2，则判断某个栈是否可以插入新元素的条件是_________________。
当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。
此处判断某个栈是否可以插入新元素的条件是&t1!=&t2
10.设森林T中有三棵树，第一，二，三棵树的结点个数分别为n1,n2,n3,将森林转换成二叉树后，其根结点的左子树上有____________个结点。
将一个森林转换为二叉树的具体方法是：① 将森林中的每棵树变为二叉树；② 因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。
个人认为此处可以填3个答案，n1-1或者n2-1或者n3-1。
11.在带权值有向图的邻接矩阵中，第i行上非零元素的个数等于_______________。
当节点Vi与某节点Vj相邻接,则A(i,j)取非0值。
12.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是_____________。
散列（Hash）查找。