广西大学数据结构练习题及答案

A. 找套数据结构的题以及答案

数据结构》单元测验(1-5)

一、 选择题
1．数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称，而（ B ）是数据不分割的最小单位。
A． 数据元素 B．数据项
C．数据对象 D．数据结构
2．下面程序段的时间复杂度为（ C ）
for(i=0;i<m;i++)
for(j=0;j<n;j++)
a[i][j]=i*j;
A．O（n2） B．O(m2) C．O(m*n) D．O(m+n)
3．在一个单链表L中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行( D )。
A．q一>next＝p一>next；p一>next＝q；
B．p一>next＝q一>next；q＝p；
C．q一>next＝p一>next；p一>next＝q；
D．p一>next＝q一>next； q一>next＝p；
4．当利用大小为N的一维数组顺序存储一个循环队列时，该队列的最大长度为（ B ）
A．N-2 B．N-1 C．N D．N+1
5．若编号为1，2，3，4，5，6的六节车厢依次通过一段栈形轨道，则在出口处不可能得到（ D ）
A．143562 B．456321 C．145326 D．426531
6．假设一个循环队列的队首和队尾指针分别为f和r，则判断队空的条件是（ D ）
A．f+1==r B．r+1==f C．f==0 D．f==r
7．经过下列栈的运算后栈顶的值是（ A ）
InitStack(s);Push(s,a), Push(s,b);Pop(s);
A．a B．b C．1 D．2
8．单链表中，增加头结点的目的是为了（ C ）
A．链表至少有一个结点
B．标示表结点中首结点的位置
C．方便运算的实现
D．说明单链表是线性表的链式存储结构
二、 填空题
1．数据结构一般包括以下三个方面的内容：（ 逻辑结构 ）、（ 存储结构 ）、（ 运算集合 ）。
2．数据的逻辑结构被分为（ 集合 ）、 （ 线性 ）、 （ 树形 ）和（ 图形 ）四种。
3．假设有二维数组A8×6，每个元素用相邻的4个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为2000，若按行存储时，元素A41的第一个字节地址为（ 2100 ）；若按列存储时，元素A74的第一个字节地址为（ 2156 ）。
4．栈是一种特殊的线性表，允许插入和删除运算的一端称为（ 栈顶 ）。不允许插入和删除运算的一端称为（ 栈低 ）。
5．向一个长度为n的顺序表的第i个元素之前插入一个元素时，需向后移动（ n-i+1 ）个元素。
三、判断题
（ 错 ）1．链表的每个结点都恰好包含一个指针。
（ 错 ）2．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
（ 对 ）3．栈和队列的存储方式既可以是顺序方式，也可以是链接方式。
（ 错 ）4．一个栈的输入序列是12345，则栈的输出序列不可能是12345。
（ 错 ）5．链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。
（ 错 ）6．顺序表适合进行顺序存取，而链表适合进行随机存取。
（ 对 ）7．对矩阵进行压缩存储是为了节省存储空间。
（ 错 ）8．顺序存储方式只能用于存储线性结构。
四、 简述以下算法的功能
1. Status algo1(Stack s,int e)
{ Stack T;int d;
InitStack(T);
While(!StackEmpty(S))
{Pop(S,d);
if(d!=e) Push(T,d);
}
While(!StackEmpty(T))
Pop(T,d);Push(S,d);
答：通过T的帮助将S中的e元素清除
}}
2. void algo2(Queue &Q)
{ Stack S;int d;
InitStack(S);
While(!QueueEmpty(Q))
{DeQueue(Q,d); Push(S,d);}
While(!StackEmpty(S))
{Pop(S,d);
EnQueue(Q,d);}}
答：通过栈S的帮助实现队列Q的逆置
五、 算法设计
编写算法，实现顺序表上的逆置运算。
void reverse(int a[],int n)
{
int i;
for(i=0;i<n/2;i++)
{
push(s,a[i]);
a[i]=a[n-i-1];
pop(s,a[n-i-1]);
}
}

B. 数据结构练习题！求答案！

一．选择题：
1． A 这个题目你是不是写的不完整啊
要是：删除它的第i数据元素 ，需要移动？个的话 你的答案错了。例如：删除第一个，移动N-1个；删除第二个，移动N-2个 ----以此类推 删除第n-1个移动1个 删除第n个移动0 个

要是：删除它的第i数据元素之前的元素，同理 就会选D

2. B 你的答案错了，这个题的答案是 B ,注意：题目是 q是p的前驱
3. C 你的答案错了这个题的答案是C， C.d,c,a,b 栈是先进后出 d一个出 说明c ,b,a都还在栈中 而出的序列 只能是c ,b,a
4.C 你的答案错了，这个题的答案是 C 只有根结点没有直接前驱
5. C 给你一个公式： 一棵深度为H（根的层次号为1）的满二叉树共有_2^H-1_____个结点.推到过程：第i层结点数目为：2^(i-1) i取值 从1到树深h，所以，每层的结点数目相加 就是树的总节点数 ，利用等比公式 得到上面给你的公式。
6. 这个没有图啊：
下面二叉树的中序遍历序列为________。( )
A. DBEAFC
B. DEBFCA
C. BDEACF
D. ABCDEF
7. C 因为题目说是联通同 因此是无向图 所以C
8. C
9. B 拓扑排序就是对边和顶点操作 所以与边和顶点的个数相关
10. B
二．填空题：
1.LOC(ai)=__LOC(a1)+(i-1)*k________。
2. 9 （n0=n2+1）
3. log2(n+1)
4. （a,b,c,d）
5. 对称
6. 2
7. 指针
8. 栈空
9. 变成兄弟结点
10.0
三．判断题：
数组是一种没有插入与删除操作的线性结构。(错 )
稀 疏矩阵中值为0的元素分布有规律，因此可以采用三元组方法进行压缩存储。(错 )
空串与由空格组成的串没有区别。( 错 )
完全二叉树就是满二叉树。( 错)
有向图是一种非线性结构。(对 )
带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。( 对 )
AOE 网是一种带权的无环连通图。( 对 )
一个广义表的表尾总是一个广义表。( 错 )
存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。( 对 )
对于有n个对象的待排序序列进行归并排序，所需平均时间为O（nlog2n）。( 对 )

已发送 查收吧

C. 寻一份《数据结构》试题及答案

《数据结构》试题一、选择题（每小题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、21604． 如果以链表作为栈的存储结构，则退栈操作时（ ）A、 必须判别栈是否满 B、 对栈不作任何判别C、 必须判别栈是否空 D、 判别栈元素的类型5． 设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（ ）A、front=front+1 B、front=(front+1)% mC、rear=(rear+1)%m D、front=(front+1)%(m+1)6． 深度为6（根的层次为1）的二叉树至多有（ ）结点。A、 64 B、32 C、31 D、637． 将含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<k2iC、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>。( )i6．对有向图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、B14、C15、D二、判断题 1. √ 2. × 3. √ 4. √ 5. × 6. × 7. × 8. √ 9. √ 10. × 三、填空题1．U=L - > next2．4。3．n-1、n(n-1)/2。4．p - > prior = NULL。5．连通6．回路或环7．28-1 = 27 = 1288．249．HT[j]!=NULL或HT[j]不为空、H(HT[j])=I10．rear - > next = p、rear = p四、简答题：1. 答： 最多是完全二叉树的形态，即5000个叶子；最少是单支树的形态，即1个叶子。2.答：是：ABDEGCFH3. 答：用锦标赛排序或堆排序很合适，因为不必等全部元素排完就能得到所需结果，时间效率为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. 答： 01121123435. 答： 要考虑递归时占用了栈空间，但递归次数最多不超过树的高度，所以空间复杂度为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

D. 《数据结构》复习题（二）(1)

一,
1.X
2.X
3.X
4.√
5.X
6.√
7.√
8.√
9.√
10.
二.
1.
2.队列,队尾.
3.
4.
5.Cn2 (n个中任取2个)
6.AOV网
7.O(n^2)
8.直接插入排序
三.
1.B
2.C
3.2^(i-1)
4.C
5.

E. 《数据结构》复习题（三）(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.一串下去.

F. 《数据结构》复习题 答案 高分求救！

一、选择题（每题2分，共20分）
1、二分查找，要求被查找的表是（ A ）
A 顺序表 B 分块有序表 C 链表 D 无限制
2、一完二叉树有30个接点，则该树有（C ） 层。(根为0层) log2n+1
A 3 B 4 C 5 D 6
3、下列排序算法中，第一趟排序后，其最大的或最小的数一定在最终的位置上的是（ D）
A 归并排序 B 直接插入排序 C 快速排序 D 冒泡排序
4、设八栈序列为A,B,C,D,则栈可能产生的出栈序列是（ A）
A、 A C D B B、 C A D B
C、 D C A B D、 D A B C
5、如有一颗二叉树按先序遍历所得结果为（? ）
A A、C G B E F D A
B D B、A B C G D E F
C E F C、C G B A E D F
G D、G C B E F D A
6、下面哪个结构属于线形结构 （C ）
A 二叉排序树 B 线索树 C 队列 D 图
7、栈和队列都是 （ ）
A 没有限制的线形表 B 没有限制的非线形表
CD
8、在线性表操作中，常对某元素插入或删除。则采用什么存贮结构最节省运算时间（A ）
A、单链表 B、散列表 C、二叉链表 D、顺序表
9、设H为带头结点单向循环链表的头指针，P为移动指针，指针域为link，则表尾的判断条件是（D ）
A、H->link = H B、P = H C、P->link = nil D、P->link = H
10、先序遍历能得到A，B，C序列的不同二叉树，最多有几种（ ）
A、4 B、5 C、6 D、7

二、填空题（每题2分，共20分）
1、在单链表中，欲删除某一指定结点时，必须找到该结点的 结点。 前驱结点
2、 和 是操作点受限的线性表。 栈和队列
3、二分查找的条件是 。 有序顺序存储结构
4、深度为K的二叉树中结点总数最多为 。 2^k-1
5、在有n（n>0）个结点的二叉链表中，空链域的个数为 个。 n+1
6、在对有15个数据的有序表中作二分查找时，有 个结点查找长度为3。
7、在单链表中，若要在指针P所指结点后插入指针S所指结点，则需执行下列语句： 。 s=p->next;p->next=s;
8、举出插入排序的两种排序法： 。
9、快速排序的时间复杂度是 。