《数据结构》模拟试卷及参考答案
模拟试卷一
一、单选题（每题2 分，共20分）
1.以下数据结构中哪一个是线性结构？( )
A. 有向图
B. 队列
C. 线索二叉树
D. B树
2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，
则执行如下( )语句序列。
A. p=q; p->next=q;
B. p->next=q; q->next=p;
C. p->next=q->next; p=q;
D. q->next=p->next; p->next=q;
3.以下哪一个不是队列的基本运算？（）
A. 在队列第i个元素之后插入一个元素
B. 从队头删除一个元素
C. 判断一个队列是否为空
D.读取队头元素的值
4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成
( )个不同的字符串？
A.14
B.5
C.6
D.8
5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。
以下6-8题基于图1。
6.该二叉树结点的前序遍历的序列为( )。
A.E、G、F、A、C、D、B
B.E、A、G、C、F、B、D
C.E、A、C、B、D、G、F
D.E、G、A、C、D、F、B
7.该二叉树结点的中序遍历的序列为( )。
A. A、B、C、D、E、G、F
B. E、A、G、C、F、B、D
C. E、A、C、B、D、G、F
E.B、D、C、A、F、G、E
8.该二叉树的按层遍历的序列为( )。
A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F
C. E、A、G、C、F、B、D
D. E、G、A、C、D、F、B
9.下面关于图的存储的叙述中正确的是( )。
A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关
D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建
堆的结果?( )
A. a，g，h，m，n，p，q，x，z
B. a，g，m，h，q，n，p，x，z
C. g，m，q，a，n，p，x，h，z
D. h，g，m，p，a，n，q，x，z
二、填空题（每空1分，共26分）
1.数据的物理结构被分为_________、________、__________和___________四种。
2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________，
在表尾插入元素的时间复杂度为____________。
3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________;
删除一个结点时，需要执行的操作是______________________________（假设栈不空而
且无需回收被删除结点）。
4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左孩
子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有双
亲，则双亲结点的编号为________。
5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整
到____________位置为止。
6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。
7.表示图的三种常用的存储结构为_____________、____________和_______________。
8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7
作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。
9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为
____________，空间复杂度为___________。
10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________
个，其子树数目最少为________，最多为________。
三、运算题（每题6 分，共24分）
1.写出下列中缀表达式的后缀形式：
（1）3X/(Y-2)+1
（2）2+X*(Y+3)
2.试对图2中的二叉树画出其：
(1)顺序存储表示的示意图；
(2)二叉链表存储表示的示意图。
3.判断以下序列是否是小根堆? 如果不是, 将它调
图2 整为小根堆。
（1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 }
（2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 }
4.已知一个图的顶点集V和边集E分别为：
V={1,2,3,4,5,6,7};
E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,
(4,7)20,(5,6)18,(6,7)25};
按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各
条边。
四、阅读算法（每题7分，共14分）
1.void AE(Stack& S){
InitStack(S);
Push(S,3);
Push(S,4);
int x=Pop(S)+2*Pop(S);
Push(S,x);
int i,a[5]={1,5,8,12,15};
for(i=0;i<5;i++) Push(S,2*a[i]);
while(!StackEmpty(S)) cout< } 该算法被调用后得到的输出结果为： 2.void ABC (BTNode *BT,int &c1,int &c2) { if (BT !=NULL ) { ABC(BT->left,c1,c2); c1++; if (BT->left==NULL&&BT->right==NULL) c2++; ABC(BT->right,c1,c2); }//if } 该函数执行的功能是什么？ 五、算法填空（共8分） 向单链表的末尾添加一个元素的算法。 Void InsertRear(LNode*& HL,const ElemType& item) { LNode* newptr; newptr=new LNode; If (______________________) { cerr<<"Memory allocation failare!"< exit(1); } ________________________=item; newptr->next=NULL; if (HL==NULL) HL=__________________________; else{ LNode* P=HL; While (P->next!=NULL) ____________________; p->next=newptr; } } 六、编写算法（共8分） 编写从类型为List的线性表L中将第i个元素删除的算法，（假定不需要对i的值进行 有效性检查,也不用判别L是否为空表。） void Delete(List& L, int i) 模拟试卷一参考答案 一、单选题（每题2分，共20分） 1.B 2.D 3.A 4.B 5.B 6.C 7.A 8.C 9.B 10.B 二、填空题（每空1分，共26分） 1.顺序链表索引散列 2.O(n) O(1) 3.p->next=HS;HS=p HS=HS->next 4.2i 2i+1 ⎣i/2⎦（或i/2） 5.向上根 6. 2.9 7.邻接矩阵邻接表边集数组 8. 1 4 9.O(n) O(nlog2n) O(n) 10.⎡m/2⎤-1 m-1 ⎡m/2⎤ m 三、运算题（每题6分，共24分） 1.(1) 3 X * Y 2 - / 1 + 图3 (2) 2 X Y 3 + * + 2.（1） 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 （2）见图3所示： 3.(1)不是小根堆。调整为：{12,65,33,70,24,56,48,92,86,33} (2)是小根堆。 4.普里姆算法从顶点1出发得到最小生成树为： (1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20 四、阅读算法（每题7分，共14分） 1.30 24 16 10 2 10 2.该函数的功能是：统计出BT所指向的二叉树的结点总数和叶子总数 五、算法填空（共8分，每一空2分） newptr==NULL newptr->=data newptr p=p->next 六、编写算法（8分） void Delete(List& L, int i) { for(int j=i-1;j L.list[j]=L.list[j+1]; //第i个元素的下标为i-1 L.size--; } 模拟试卷二 一、单选题（每题2 分，共20分） 1.在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结 点，则执行( )。 A. HL=p; p->next=HL; B. p->next=HL->next; HL->next=p; C. p->next=HL; p=HL; D. p->next=HL; HL=p; 2.若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（）个元素. A. n B.n-1 C. n+1 D.不确定 3.下述哪一条是顺序存储方式的优点？（） A．存储密度大 B.插入和删除运算方便 C. 获取符合某种条件的元素方便 D.查找运算速度快 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在 678(10)，每个元素占一个空间，问A[2][3](10)存放在什么位置？(脚注(10)表示用10进制表示,m>3) A．658 B．648 C．633 D．653 5.下列关于二叉树遍历的叙述中，正确的是( ) 。 A. 若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点 B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点 C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点 D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点 6.k层二叉树的结点总数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.对线性表进行二分法查找，其前提条件是( ). A.线性表以链接方式存储，并且按关键码值排好序 B.线性表以顺序方式存储，并且按关键码值的检索频率排好序 C.线性表以顺序方式存储，并且按关键码值排好序 D.线性表以链接方式存储，并且按关键码值的检索频率排好序 8.对n个记录进行堆排序，所需要的辅助存储空间为 A. O（1og2n） B. O（n） C. O（1） D. O（n2） 9.对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K） =K %7作为散列函数，则散列地址为0的元素有（）个， A．1 B．2 C．3 D．4 10.下列关于数据结构的叙述中，正确的是( ). A.数组是不同类型值的集合 B.递归算法的程序结构比迭代算法的程序结构更为精炼 C.树是一种线性结构 D.用一维数组存储一棵完全二叉树是有效的存储方法 二、填空题（每空1分，共26分） 1.数据的逻辑结构被分为_________、________、__________和___________四种。 2.一个算法的时间复杂度为(3n3+2000n log2n+90)/n2，其数量级表示为________。 3.对于一个长度为n的单链存储的队列，在表头插入元素的时间复杂度为_________，在 表尾插入元素的时间复杂度为____________。 4.假定一棵树的广义表表示为A（D（E，G），H（I，J）），则树中所含的结点数为__________ 个，树的深度为___________，树的度为_________。 5.后缀算式79 2 30 + - 4 2 / *的值为__________。中缀算式（3+X*Y）-2Y/3对 应的后缀算式为_______________________________。 6.在一棵高度为5的理想平衡树中，最少含有_______个结点，最多含有_______个结点。 7.在树中，一个结点的直接后继结点称为该结点的________。一个结点的直接前趋结点称 为该结点的________。 8.在一个具有10个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的 有向完全图中，包含有________条边。 9.假定一个线性表为(12,17,74,5,63,49,82,36)，若按Key % 4条件进行划分，使得同一余数 的元素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 10.对一棵B_树进行删除元素的过程中，若最终引起树根结点的合并时，会使新树的高度 比原树的高度___________。 11.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序 过程的时间复杂度为________。 12.在线性表的散列存储中，装填因子α又称为装填系数，若用m表示散列表的长度，n表 示待散列存储的元素的个数，则α等于________。 三、运算题（每题6 分，共24分） 1．在如下数组A中链接存储了一个线性表，表头指针存放在A [ 0].next，试写出该线性表。 A 0 1 2 3 4 5 6 7 data next 2．已知一棵二叉树的前序遍历的结果是ABKCDFGHIJ, 中序遍历的结果是KBCDAFHIGJ, 试画出这棵二叉树。 3．已知一个图的顶点集V为：V={1,2,3,4,5,6,7}; 起点 终点 权 试用克鲁斯卡尔算法依次求出该图的最小生成树中所得到的各条边及权值。 4．画出向小根堆中加入数据4, 2, 5, 8, 3, 6, 10, 1时，每加入一个数据后堆的变化。 四、阅读算法（每题7分，共14分） 1.在下面的每个程序段中，假定线性表La的类型为List，元素类型ElemType为int， 并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。 （1）InitList(La); Int a[]={100,26,57,34,79}; For (i=0;i<5;i++) Insert(La,a[i]); TraverseList(La); （2）DeleteFront(La); InsertRear(La, DeleteFront(La)); TraverseList(La); （3）ClearList(La); For (i=0;i<5;i++) InsertFront(La,a[i]); TraverseList(La); 2.现面算法的功能是什么？ void ABC(BTNode * BT) { if BT { cout< ABC(BT->left); ABC(BT->right); } } 五、算法填空（共8分） 二分查找的递归算法。 Int Binsch(ElemType A[],int low,int high,KeyType K) { if ___________________{ int mid=(low+high)/2; if (_____________________) return mid; //查找成功，返回元素的下标 else if (K return Binsch(A,low,mid-1,K); //在左子表上继续查找 else return_____________________________； //在右子表上继续查找 } else ________________； //查找失败，返回-1 } 六、编写算法（共8分） HL为单链表的表头指针，试写出在该单链表中查找具有给定的元素item的算法。 bool Find(LNode* HL, ElemType &item) 模拟试卷二参考答案 一、单选题（每题2分，共20分） 1.B 2.B 3.A 4.C 5.D 6.A 7.C 8.C 9.D 10.D 二、填空题（每空1分，共26分） 1.集合结构线性结构树结构图结构 2.O(n) 3.O(1) O(1) 4.7 2 2 5.94 3 X Y * + 2 Y * 3 / - 6. 16 31 7. 孩子（或子）结点 双亲（或父）结点 8. 45 n(n-1) 9. （12，36） （17,5,49） （74，82） （63） 10. 减少1（或减少） 11. O(log 2n) O(nlog 2n) 12. n/m 三、 运算题（每题6分，共24分） 1. 线性表为：（90，40，78，50，34，60） 2. 当前序序列为ABKCDFGHIJ ，中序序列为KBCDAFHIGJ 时，逐步形成二叉树的过程如下图4所示： 3. 用克鲁斯卡尔算法得到的最小生成树为： (1,6)1, (2,4)1, (2,5)2, (5,7)2, (2,6)3, (3,5)7 4. 见图5。 图5 四、 阅读算法（每题7分，共14分） 1. (1) La=(26,34,57,79,100) (2)La=(57,79,100,34) (3)La=(79,34,57,26,100) 2. 前序遍历链式存储的二叉树。 五、 算法填空（每空2分，共8 分） (low<=high) K==A[mid].key Binsch(A,mid+1,hight,K) return -1 六、 编写算法（8分） bool Find(LNode* HL, ElemType &item) { LNode* p=HL; while p if (p->data==item){ return true; } else p=p->next; return false; } 模拟试卷三 一、单选题（每题2 分，共20分） 1.对一个算法的评价，不包括如下（）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、运算题（每题6 分，共24分） 1.数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N） 的联系时，称这种结构为_____________________。 2.队列的插入操作是在队列的_________进行，删除操作是在队列的__________进行。 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件 是_____________________。 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j 从0到3 ，则二维数组W 的数据元素共占用＿_____＿个字节。W 中第6 行的元素和第4 列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W ，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。 6. 广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。 7. 二叉树是指度为2的____________________树。一棵结点数为N 的二叉树，其所有结点的度的总和是_____________。 8. 对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。 9. 对于一棵具有n 个结点的二叉树，用二叉链表存储时，其指针总数为_____________个，其中_______________个用于指向孩子，_________________个指针是空闲的。 10. 若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A 中，即编号为0的结点存储到A[0]中。其余类推，则A[ i ]元素的左孩子元素为________,右孩子元素为_______________，双亲元素为____________。 11. 在线性表的散列存储中，处理冲突的常用方法有________________________和_____________________________两种。 12. 当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用_______________排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用________________________排序。 三、 运算题（每题6分，共24分） 1. 已知一个6⨯5稀疏矩阵如右所示，试： （1） 写出它的三元组线性表； （2） 给出三元组线性表的顺序存储表示。 2. 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。 3. 对于图6所示的有向图若存储它采用邻接表，并且每个顶点邻 接表中的边结点都是按照终点序号从小到大的次序链接的，试写出： (1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树； (2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树； 4. 已知一个图的顶点集V 和边集E 分别为： V={1,2,3,4,5,6,7}; E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5 >,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6, 5>}; 若存储它采用邻接表，并且每个顶点 邻接表中的边结点都是按照终点序号从 小到大的次序链接的，按主教材中介绍的 拓朴排序算法进行排序，试给出得到的拓 朴排序的序列。 四、 阅读算法（每题7分，共14分） 1. int Prime(int n) { int i=1; ⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡--007000000520000000100000010000 图6 int x=(int) sqrt(n); while (++i<=x) if (n%i==0) break; if (i>x) return 1; else return 0; } (1)指出该算法的功能； (2)该算法的时间复杂度是多少？ 2.写出下述算法的功能： void AJ(adjlist GL, int i, int n) { Queue Q; InitQueue(Q); cout< visited[i]=true; QInsert(Q,i); while(!QueueEmpty(Q)) { int k=QDelete(Q); edgenode* p=GL[k]; while(p!=NULL) { int j=p->adjvex; if(!visited[j]) { cout< visited[j]=true; QInsert(Q,j); } p=p->next; } } } 五、算法填空（共8分） 如下为二分查找的非递归算法，试将其填写完整。 Int Binsch(ElemType A[ ],int n,KeyType K) { int low=0; int high=n-1; while (low<=high) { int mid=_______________________________； if (K==A[mid].key) return mid; //查找成功，返回元素的下标 else if (K<[mid].key) ______________________________________; //在左子表上继续查找 else __________________________________; //在右子表上继续查找} return -1; //查找失败，返回-1 } 六、编写算法（共8分） HL是单链表的头指针，试写出删除头结点的算法。 ElemType DeleFront(LNode * & HL) 模拟试卷三参考答案 一、单选题（每题2分，共20分） 1.B 2.A 3.B 4.C 5.D 6.B 7.D 8.A 9.D 10.C 二、填空题（每空1分，共26分） 1.联系图（或图结构） 2.尾首 3.top==0 4.O（1）O（n） 5.128 44 108 6. 3 3 7.有序n-1 8.有序序列后缀表达式（或逆波兰式） 9.2n n-1 n+1 10.2i+1 2i+2 (i-1)/2 11.开放定址法链接法 12.快速归并 三、运算题（每题6分，共24分） 1.（1）((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)) (3分) （2）三元组线性表的顺序存储表示如图7示。2.如图8所示。 3.DFS：①②③④⑤ BFS：②③④⑤① 4.拓朴排序为：4 3 6 5 7 2 1 四、阅读算法（每题7分，共14分） 1.(1) 判断n是否是素数（或质数） （2）O（n）6 5 5 1 5 1 3 2 -1 4 5 -2 5 1 5 6 3 7 图7 图8 2.功能为：从初始点v i出发广度优先搜索由邻接表GL所表示的图。 五、算法填空（8 分） (low+high)/2 high=mid-1 low=mid+1 六、编写算法（8分） ElemType DeleFront(LNode * & HL) { if (HL==NULL){ cerr<<"空表"< exit(1); } LNode* p=HL; HL=HL->next; ElemType temp=p->data; delete p; return temp; } 模拟试卷四 一、单选题（每题2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 栈 C. 二叉树 D. B树 2.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采 用( )存储方式最节省时间。 A.单链表 B.双链表 C.带头结点的双循环链表 D.单循环链表 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以 组成( )个不同的字符串？ A.15 B.14 C.16 D.21 5.由权值分别为4,7,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.37 C. 19 D. 53 以下6-8题基于下面的叙述：若某二叉树结点的中序遍历的序列为A、B、C、D、E、 F、G，后序遍历的序列为B、D、C、A、F、 G、E。 6.则该二叉树结点的前序遍历的序列为( ). A. E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7.该二叉树有（）个叶子。 A．3 B.2 C.5 D.4 8.该二叉树的按层遍历的序列为( ) A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面的二叉树中，( )不是完全二叉树。 10.设有关键码序列(q，g，m，z，a)，下面哪一个序列是从上述序列出发建的小根堆的结 果?( ) A. a，g，m，q， z B. a，g，m，z,q C. g，m，q，a，z D. g， m， a，q，z 二、填空题（每空1分，共26分） 1.数据结构是指数据及其相互之间的______________。当结点之间存在1对N（1：N） 的联系时，称这种结构为_____________________。 2.一个广义表中的元素分为________元素和________元素两类。 3.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 4.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是_________________; 删除一个结点时，需要执行的操作是___________________________（假设栈不空而且无需回收被删除结点）。 5.栈又称为_______________表，队列又称为___________表。 6.在稀疏矩阵所对应的三元组线性表中，每个三元组元素按_________为主序、_________ 为辅序的次序排列。 7.若一棵二叉树中只有叶子结点和左、右子树皆非空的结点，设叶结点的个数为K，则左、 右子树皆非空的结点个数是________。 8.以折半（或二分）查找方法从长度为8的有序表中查找一个元素时，平均查找长度为 ________。 9.表示图的三种常用的存储结构为_____________、____________和_______________。 10.对于线性表（78，4，56，30，65）进行散列存储时，若选用H（K）=K %5作为散列 函数，则散列地址为0的元素有________个，散列地址为4的有_______个。 11.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 12.在n个带权叶子结点构造出的所有二叉树中，带权路径长度最小的二叉树称为 ________。WPL称为_____________________。 13.在索引表中，若一个索引项对应主表的一个记录，则此索引为__________索引，若对 应主表的若干条记录，则称此索引为________索引。 三、运算题（每题6 分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2H)+1 （2）2+X*(Y+3) 2.假定一棵二叉树广义表表示为a(b(c),d(e,f))，分别写出对它进行先序、中序、后序、按 层遍历的结果。 先序： 中序： 后序： 按层： 3. 已知一个无向图的顶点集为{a, b, c, d, e} ,其邻接矩阵如下所示 0100110010000110110110110⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥ (1) 画出该图的图形； （2）根据邻接矩阵从顶点a 出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。 4. 已知一个图的顶点集V 和边集E 分别为： V={0,1,2,3,4,5,6,7}; E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10, (4,6)4,(5,7)20}; 按照普里姆算法从顶点0出发得到最小生成树，试写出在最小生成树中依次得到的各条边。 四、 阅读算法（每题7分，共14分） 1. void AE(Stack& S){ InitStack(S); Push(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a[5]={2,5,8,22,15}; for(i=0;i<5;i++) Push(S,a[i]); while(!StackEmpty(S)) cout< } 该算法被调用后得到的输出结果为： 2. int akm ( unsigned m, unsigned n ) { if ( m == 0 ) return n+1; else if ( n == 0 ) return akm ( m-1, 1 ); else return akm ( m-1, akm ( m, n-1 ) ); } 该函数执行的功能是什么？ 五、 算法填空（共8分） 二叉搜索树的查找——非递归算法 bool Find(BTreeNode* BST,ElemType& item) {while(BST(!=NULL){ if (item==______________){ a b c d e item=BST->data;//查找成功 return true;} else if(item BST=BST->_____________; else BST=BST->_____________; }//while return _____________;//查找失败 } 六、编写算法（共8分） 用递归的算法编写出对存入在a[n+1]数组中的n个有序元素进行二分（又称折半）查找（假定a[0]单元不用）的程序。 int halfsearch(SSTable *a, KeyType k,int low,int high) 模拟试卷四参考答案 一、单选题（每题2分，共20分） 1.B 2.C 3.A 4.B 5.B 6.C 7.A 8.C 9.C 10.B 二、填空题（每空1分，共26分） 1.联系树（或树结构） 2.单（子）表 3.O(n) O(1) 4.p->next=HS;HS=p HS=HS->next 5.先进后出先进先出 6.行列 7.k-1 8. 2.625 9.邻接矩阵邻接表边集数组 10.2 1 11.O(n) O(nlog2n) O(n) 12.哈夫曼树带权路径长度 13.稠密稀疏 三、运算题（每题6分，共24分） 1.(1) 3 X * Y 2 H *- / 1 + （2） 2 X Y 3 + * + 2.先序：a,b,c,d,e,f 中序： c,b,a,e,d,f 后序： c,b,e,f,d,a 按层：a,b,d,c,e,f 图9 3.（1）该图的图形如图9示： （2）深度优先遍历序列为：abdce 广度优先遍历序列为：abedc 4.普里姆：(0,3)2, (0,2)5, (0,1)8, (1,5)6, (3,6)10, (6,4)4, (5,7)20 四、阅读算法（每题7分，共14分） 3.15 22 8 5 2 10 4.该函数的功能是： 求：akm m n n m akm m m n akm m akm m n m n (,)(,), (,(,)), = += -≠= --≠≠ ⎧ ⎨ ⎪ ⎩ ⎪ 10 1100 1100 当时 当时 当时 五、算法填空（共8分，每一空2分） BST->data left right false 六、编写算法（8分） 递归算法： int halfsearch(SSTable *a, KeyType k,int low,int high) { if (low>high) return 0; else { int mid=(low+high)/2 if EQ(k,a[mid].key) return mid; else if LT(k,a[mid].key) return halfsearch(a,k,low,mid-1); else return halfsearch(a,k,mid+1,high); } } 模拟试卷五 一、单选题（每题2 分，共20分） 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在 676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二 分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O（1） B. O（n） C. O（1og2n） D. O（n2） 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K） =K %9作为散列函数，则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数 为__________个，树的深度为___________，树的度为_________。 4.后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式 为_______________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有_______个和________个。 7.AOV网是一种___________________的图。 8.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有 向完全图中，包含有________条边。 9.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元 素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 10.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度 ___________。 11.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序 过程的时间复杂度为________。 12.在快速排序、堆排序、归并排序中，_________排序是稳定的。 三、运算题（每题6 分，共24分） 1.在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。 A 0 1 2 3 4 5 6 7 data 60 50 78 90 34 40 next 3 5 7 2 0 4 1 2.请画出图10的邻接矩阵和邻接表。 3.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树图10 中依次得到的各条边。 4.画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。 四、阅读算法（每题7分，共14分） 1.LinkList mynote(LinkList L) {//L是不带头结点的单链表的头指针 if(L&&L->next){ q=L；L=L－>next；p=L； S1：while(p－>next) p=p－>next； S2：p－>next=q；q－>next=NULL； } return L； } 请回答下列问题： （1）说明语句S1的功能； （2）说明语句组S2的功能； （3）设链表表示的线性表为（a1,a2, …,a n）,写出算法执行后的返回值所表示的线性表。 2.void ABC(BTNode * BT) { if BT { ABC (BT->left); ABC (BT->right); cout< } } 该算法的功能是： 五、算法填空（共8分） 二叉搜索树的查找——递归算法: bool Find(BTreeNode* BST,ElemType& item) { if (BST==NULL) return false; //查找失败 else { if (item==BST->data){ item=BST->data;//查找成功 return ___________;} else if(item return Find(______________,item); else return Find(_______________,item); }//if } 六、 编写算法（共8分） 统计出单链表HL 中结点的值等于给定值X 的结点数。 int CountX(LNode* HL,ElemType x) 模拟试卷五参考答案 一、 单选题（每题2分，共20分） 1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A 二、 填空题（每空1分，共26分） 1. 正确性 易读性 强壮性 高效率 2. O(n) 3. 9 3 3 4. -1 3 4 X * + 2 Y * 3 / - 5. 2n n-1 n+1 6. e 2e 7. 有向无回路 8. n(n-1)/2 n(n-1) 9. （12，40） （ ） （74） （23,55，63） 10.增加1 11.O(log 2n) O(nlog 2n) 12.归并 三、 运算题（每题6分，共24分） 1. 线性表为：（78，50，40，60，34，90） 2. 邻接矩阵：⎥⎥ ⎥ ⎥⎥⎥ ⎦ ⎤ ⎢⎢⎢⎢⎢⎢⎣⎡0111010101110111010101110 邻接表如图11所示： 图11 3. 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 数据结构期末十套卷 试卷（一） 一、单选题（每题2 分，共20分） 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在 676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二 分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O（1） B. O（n） C. O（1og2n） D. O（n2） 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K） =K %9作为散列函数，则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数 为__________个，树的深度为___________，树的度为_________。 4.后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式 为_______________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有_______个和________个。 7.AOV网是一种___________________的图。 8.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有 向完全图中，包含有________条边。 贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；j 数据结构试卷（一） (1) 数据结构试卷（二） (4) 数据结构试卷（三） (6) 数据结构试卷（四） (8) 数据结构试卷（五） (11) 数据结构试卷（六） (14) 数据结构试卷（七） (16) 数据结构试卷（八） (18) 数据结构试卷（九） (20) 数据结构试卷（十）................ 23 数据结构试卷（一）参考答案 (26) 数据结构试卷（二）参考答案 (27) 数据结构试卷（三）参考答案 (28) 数据结构试卷（四）参考答案 (30) 数据结构试卷（五）参考答案 (32) 数据结构试卷（六）参考答案 (33) 数据结构试卷（七）参考答案 (36) 数据结构试卷（八）参考答案 (37) 数据结构试卷（九）参考答案 (38) 数据结构试卷（十）参考答案 (39) 数据结构试卷（一） 一、单选题（每题 2 分，共20分） 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在 676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二 分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O（1） B. O（n） C. O（1og 2 n） D. O（n2） 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K） =K %9作为散列函数，则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数 为__________个，树的深度为___________，树的度为_________。 4.后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式 数据结构试题及答案(十套)数据结构试题及答案(十套) 一、选择题 1. 数据结构是指（）。 A. 存储数据的方式 B. 数据的逻辑结构和物理结构 C. 数据的存储结构和存储方式 D. 数据的逻辑结构、存储结构和存储方式 答案：D 2. 在数据结构中，线性表的存储方式包括（）。 A. 顺序存储和链式存储 B. 数组存储和链表存储 C. 顺序存储、链表存储和索引存储 D. 顺序存储、链表存储和树形存储 答案：A 3. 栈是一种（）的数据结构。 A. 先进先出 B. 先进后出 C. 后进先出 D. 后进后出 答案：C 4. 队列是一种（）的数据结构。 A. 先进先出 B. 先进后出 C. 后进先出 D. 后进后出 答案：A 5. 二叉树中，度为0的节点称为（）。 A. 叶子节点 B. 根节点 C. 中间节点 D. 子节点 答案：A 6. 以下哪个排序算法是稳定的？ A. 快速排序 B. 选择排序 C. 插入排序 D. 希尔排序 答案：C 7. 图中表示顶点之间关系的边的数量称为（）。 A. 顶点度数 B. 边数 C. 路径数 D. 网络 答案：B 8. 哈希表通过（）来实现高效的查找操作。 A. 散列函数 B. 排序算法 C. 遍历操作 D. 顺序存储 答案：A 9. 平衡二叉树是一种具有左右子树高度差不超过（）的二叉树。 A. 0 B. 1 C. 2 D. 3 答案：B 10. 在链表中，删除节点的操作时间复杂度是（）。 A. O(1) B. O(logn) C. O(n) D. O(nlogn) 答案：A 二、填空题 1. 在顺序存储结构中，元素之间的逻辑关系由（）表示。 答案：下标 2. 二叉查找树的中序遍历结果是一个（）序列。 答案：递增 3. 哈希表通过散列函数将关键字映射到（）上。 数据结构试卷（一） 三、计算题（每题 6 分，共24分） 1.在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试 写出该线性表。 A 0 1 2 3 4 5 6 7 dat a nex t 2. 3.已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 4.画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的 变化。 四、阅读算法（每题7分，共14分） 1.LinkList mynote(LinkList L) {//L是不带头结点的单链表的头指针 if(L&&L->next){ q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL； } return L； } 请回答下列问题： （1）说明语句S1的功能； （2）说明语句组S2的功能； （3）设链表表示的线性表为（a 1,a 2 , …,a n ）,写出算法执行后的 返回值所表示的线性表。 2.void ABC(BTNode * BT) { if BT { ABC (BT->left); ABC (BT->right); cout< 数据结构试卷（一) 1.栈和队列的共同特点是( ）。 A。只允许在端点处插入和删除元素B。都是先进后出 C。都是先进先出D。没有共同点 2.用链接方式存储的队列，在进行插入运算时（ ). A。仅修改头指针 B。头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构?( ） A. 队列B。栈 C. 线性表D。二叉树 4.设有一个二维数组A[m］［n]，假设A[0］［0]存放位置在644（10），A［2］[2］存放位 置在676（10)，每个元素占一个空间，问A[3][3］(10）存放在什么位置？脚注(10)表示用10进制表示. A．688 B．678 C．692 D．696 5.树最适合用来表示（)。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( )。 A．2k—1 B。2K+1 C.2K—1 D. 2k—1 7.若有18个元素的有序表存放在一维数组A[19］中，第一个元素放A［1］中，现进 行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1,2，3 B。9，5，2,3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A。 O（1） B. O(n） C. O(1og2n) D。 O（n2） 9.对于线性表（7，34，55，25，64，46，20，10)进行散列存储时，若选用H（K）=K ％ 9作为散列函数,则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通图。 A.5 B.6 C。7 D.8 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2.一个算法的时间复杂度为(n3+n2log2n+14n）/n2,其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E,F，G），H(I，J）)，则树中所含的结点数为 __________个，树的深度为___________，树的度为_________。 4.后缀算式9 2 3 +- 10 2 / —的值为__________。中缀算式（3+4X）—2Y/3对应的后缀算 式为_______________________________. 5.若用链表存储一棵二叉树时，每个结点除数据域外,还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有________个指针域,其中有________个指针域是存放了地址,有________________个指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有_______个和________个. 7.AOV网是一种___________________的图。 8.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有 向完全图中,包含有________条边. 9.假定一个线性表为（12，23,74，55,63,40)，若按Key % 4条件进行划分，使得同一余数 的元素成为一个子表,则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 10.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度 ___________。 数据结构试题及答案(10套最新)数据结构试题及答案(10套最新) 第一套试题： 问题一：什么是数据结构？数据结构的作用是什么？ 回答：数据结构是一种组织和存储数据的方式，它关注数据元素之 间的关系以及对数据元素的操作。数据结构的作用包括提供高效的数 据存储和访问方式，减少资源消耗，简化问题的解决方法，提高算法 的性能和程序的可读性。 问题二：请列举几种常见的线性数据结构，并简要介绍它们的特点。 回答：常见的线性数据结构包括数组、链表和栈。数组是一种连续 存储数据元素的结构，具有随机访问的特点；链表是一种通过指针相 连的数据元素，可以灵活地插入和删除元素；栈是一种遵循先进后出 原则的数据结构，常用于解决递归问题。 问题三：请说明二叉树的定义及其性质。 回答：二叉树是一种特殊的树形数据结构，每个节点最多有两个子 节点。二叉树具有以下性质：每个节点最多有两个子节点，分别称为 左子节点和右子节点；左子树和右子树都是二叉树；二叉树的节点个 数为n，边的个数为n-1。 问题四：在数组中查找一个元素的时间复杂度是多少？为什么？ 回答：在数组中查找一个元素的时间复杂度是O(n)，其中n是数组 的长度。因为在数组中查找元素需要按照索引一个一个比较，最坏情 况下需要比较n次才能找到目标元素。 问题五：请解释堆排序算法的原理及时间复杂度。 回答：堆排序算法利用堆这种数据结构进行排序。首先将待排序的 元素构建成一个大顶堆，然后将堆顶元素与最后一个元素交换，继续 调整堆，再取出堆顶元素与倒数第二个元素交换，依次执行，最后得 到从小到大排序的序列。堆排序的时间复杂度为O(nlogn)。 第二套试题： 问题一：请解释图的邻接矩阵和邻接表表示法。 回答：图的邻接矩阵表示法是使用二维数组来表示图的连接关系， 数组中的元素表示相应节点之间的边的关系。邻接表表示法使用链表 来表示图的连接关系，链表中的元素表示相邻节点之间的边的关系。 问题二：请说明深度优先搜索算法的原理及其应用。 回答：深度优先搜索（DFS）算法是一种遍历或搜索图的算法，其 原理是从起始节点开始，依次深入到尽可能远的节点，直到无法继续 深入为止，然后回溯到上一个节点，再继续深入其他未访问过的节点。DFS算法常用于解决连通性、路径查找、拓扑排序等问题。 问题三：请说明广度优先搜索算法的原理及其应用。 十套数据结构试题及答案 1.请设计一个栈结构，满足以下要求： -支持常规的入栈和出栈操作。 -支持获取当前栈中最小元素的操作，并要求时间复杂度为O(1)。 答案：可以使用两个栈，一个用于存储数据，另一个用于维护当前栈 中的最小值。每次入栈时，比较要入栈的元素与当前栈中的最小值，将较 小的值入最小栈。出栈时，同时从数据栈和最小栈中出栈，保持栈的一致性。 2.请用链表实现一个队列结构，满足以下要求： -支持常规的入队和出队操作。 -支持获取队列中的最大值和最小值的操作，并要求时间复杂度为 O(1)。 答案：使用双向链表实现队列，每个结点保存当前最大值和最小值， 入队时更新队列相关结点的最大值和最小值，出队时删除队首结点，并更 新队列最大值和最小值。 3. 设计一个LRU（Least Recently Used）缓存结构，要求如下： -缓存结构内存固定大小。 -当缓存结构满时，插入新的数据时需要剔除最近最少使用的数据。 答案：可以使用哈希表和双向链表来实现。哈希表用于实现快速查找，双向链表用于保存数据的访问顺序。当一些数据被访问时，根据哈希表快 速定位到对应的结点，并将该结点移到链表头部。当需要插入新数据时， 如果缓存容量已满，则将链表尾部的结点剔除。 4.设计一个支持并发访问的并且具有线程安全性的哈希表结构。 答案：可以使用读写锁来保证线程安全性。读操作时，多个线程可以 同时读取，不会产生冲突；写操作时，需要获取写锁，保证同时只能有一 个线程执行写操作。 5.实现一个拓扑排序算法，对有向无环图进行排序。 答案：可以使用DFS和栈结构来实现。从任意一个未被访问的结点开始，递归地进行深度优先，并将访问完毕的结点入栈。最终得到的栈中的 结点顺序即为拓扑排序结果。 6.设计一个支持高效插入与删除的动态数组结构。 答案：可以使用动态平衡二叉树（例如AVL树）来实现。插入与删除 操作的时间复杂度为O(log n)，并保持树的平衡性，避免树的高度过大。 7.设计一个支持高效查找的散列表结构。 答案：可以使用哈希表来实现。通过哈希函数将键映射到散列桶，并 使用链表或红黑树来处理哈希冲突。 8.实现一个快速排序算法。 答案：快速排序使用分治思想，每次选择一个基准元素，将比基准小 的元素放在左边，比基准大的元素放在右边，然后对两边的子数组递归地 进行快速排序。 9.设计一个支持高效查找和修改的二叉树结构。 数据结构试卷(一) 一、单选题（每题2 分，共20分） 1.栈和队列的共同特点是（ a ）。 A。只允许在端点处插入和删除元素 B。都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( d )。 A. 仅修改头指针 B. 头、尾指针都要修改 C。仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构?( d ) A。队列B。栈 C. 线性表 D. 二叉树 4.设有一个二维数组A［m][n]，假设A［0］[0]存放位置在644(10）,A[2］［2］存放位置 在676（10),每个元素占一个空间,问A［3][3]（10）存放在什么位置？脚注(10)表示用10 进制表示。c A．688 B．678 C．692 D．696 5.树最适合用来表示( c )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据D。元素之间无联系的数据 6.二叉树的第k层的结点数最多为( d ). A．2k-1 B。2K+1 C。2K—1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A［19］中,第一个元素放A［1］中，现进 行二分查找，则查找A［3］的比较序列的下标依次为( c d） A. 1，2，3 B。9，5,2，3 C. 9，5，3 D。9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 c A. O（1) B。 O（n） C. O（1og2n） D。 O（n2） 9.对于线性表(7,34,55,25，64，46，20,10）进行散列存储时，若选用H(K)=K ％9 作为散列函数，则散列地址为1的元素有( c d）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有（ a ）条边才能确保是一个连通图。 A.5 B。6 C。7 D。8 二、填空题(每空1分，共26分) 1.通常从四个方面评价算法的质量：____时间正确性_____、____占用内存_易读性____、 ____复杂度__强壮性___和_____准确度_ 高效率___. 2.一个算法的时间复杂度为（n3+n2log2n+14n)/n2，其数量级表示为___3 0（n）_____。 3.假定一棵树的广义表表示为A(C，D（E,F，G），H（I，J）），则树中所含的结点数为 _____9_____个，树的深度为_____3______，树的度为____2_____。 4.后缀算式9 2 3 +— 10 2 / -的值为____3__—1____。中缀算式（3+4X）—2Y/3对应的后 缀算式为______3 4X＊+ 2Y* / -_________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外,还有指向左孩子和右孩子的两个指 针。在这种存储结构中,n个结点的二叉树共有____n_2n___个指针域，其中有_____n—1___个指针域是存放了地址，有________3__n+1______个指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有___e+1_e___个和____e+1__2e__个。 7.AOV网是一种________有向无回路___________的图。 8.在一个具有n个顶点的无向完全图中，包含有____n-1_n（n—1)/2___条边,在一个具有n 个顶点的有向完全图中，包含有____n-1___n(n—1)_条边. 9.假定一个线性表为(12,23,74，55，63,40），若按Key % 4条件进行划分,使得同一余数的 数据结构试卷(一) 三、计算题(每题 6分，共24 分) 3. 已知一个图的顶点集 V 和边集E 分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 4. 画出向小根堆中加入数据 4, 2, 5, 8, 3 时，每加入一个数据后堆的变化。 四、 阅读算法(每题 7分，共14分) 1. LinkList mynote(LinkList L) {//L 是不带头结点的单链表的头指针 if(L&&L-> next){ q=L ； L=L — >next ; p=L ; 51 : while(p — >next) p=p — >next ; 52 : p — >next=q ; q — >next=NULL ; } return L ; } 请回答下列问题： (1 )说明语句S1的功能； (2) 说明语句组S2的功能； (3) 设链表表示的线性表为(a 1,a 2,…,a n ),写出算法执行后的返回值所表示的线 性表。 2. void ABC(BTNode * BT) { if BT { ABC (BT->left); ABC (BT->right); cout< 一、单选题（每题 2 分，共20分） 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点， 则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有 相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n)C．0(n) D．0(n2) 10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、运算题（每题 6 分，共24分） 1.数据结构是指数据及其相互之间的______________。当结点之间存在M对N （M：N）的联系时，称这种结构为_____________________。 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的____首______进行。 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是___top==0___(要超出才为满)_______________。 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。 最新十套数据结构试题及答案 最新十套数据结构试题及答案 数据结构试卷（I）1数据结构试卷（II）4数据结构试卷（III）6数据结构试卷（IV）8数据结构试卷（V）11数据结构试卷（6）14数据结构试卷（VII）16数据结构试卷（8）18数据结构试卷（IX）20数据结构试卷（x）23 数据结构试卷（一）参考答案.........26数据结构试卷（二）参考答案 (27) 数据结构试卷（三）参考答案.........28数据结构试卷（四）参考答案.........30数 据结构试卷（五）参考答案.........32数据结构试卷（六）参考答案.........33数据 结构试卷（七）参考答案.........36数据结构试卷（八）参考答案.........37数据结 构试卷（九）参考答案.........38数据结构试卷（十）参考答案.........39数据结构 试卷（一） 一、单选题（每个问题2分，总共20分）1堆栈和队列的共同特点是（）。a、只 允许在端点插入和删除元素。他们都是先进先出的。他们都是先进先出的 2.用链接方式存储的队列，在进行插入运算时(). a、只修改头指针B.同时修改头指针和尾指针C.只修改尾指针D.同时修改头指针和 尾指针3以下哪种数据结构是非线性的？() a.队列 b.栈 c.线性表 d.二叉树 4.有一个二维数组a[M][n]。假设[0][0]存储在644（10）中，而[2][2]存储在676（10）中。每个元素都占据一个空间。[3][3]（10）在哪里？脚注（10）用小数表示。a、688b.678c.692d.6965。树最好用来表示（）。 a.有序数据元素 b.无序数据元素 c、元素之间具有分支层次关系的数据D.元素之间没有连接的数据6二叉树K层中的最大节点数为（） a．2k-1b.2k+1c.2k-1d.2k-1 7.如果18个元素的有序表存储在一维数组a[19]中，第一个元素被放置在a[1]中， 现在执行二进制搜索，a[3]的比较序列的下标是（）a.1,2,3b 9,5,2,3 《数据结构》期末考试试题及答案 一、单项选择题 1. 数据结构是计算机科学的基础学科之一。下列哪个选项正确描述了数据结构的定义？ A. 数据结构是一种计算机程序 B. 数据结构是一种存储和组织数据的方法 C. 数据结构是一种人工智能技术 D. 数据结构是一种操作系统 答案：B 2. 链表和数组是常见的数据结构，它们之间的主要区别是： A. 数组可以存储不同类型的数据，而链表只能存储相同类型的数据 B. 数组的元素在内存中是连续存储的，而链表的元素在内存中是分散存储的 C. 链表可以随机访问元素，而数组只能顺序访问元素 D. 链表的插入和删除操作更高效，而数组的访问操作更高效 答案：B 3. 在二叉树中，每个节点最多可以有多少个子节点？ A. 1 B. 2 C. 3 D. 无限多个 答案：B 二、填空题 1. 假设有一组数据 [5, 8, 3, 2, 9]，按照从小到大的顺序进行冒泡排 序的过程中，经过三次交换后的结果是__2__，__3__，__5__，__8__，__9__。 2. 请完成以下代码，实现栈的入栈和出栈操作： ```python class Stack: def __init__(self): self.stack = [] def push(self, item): self.stack.append(item) def pop(self): if not self.is_empty(): return self.stack.pop() def is_empty(self): # 示例代码 s = Stack() s.push(1) s.push(2) s.push(3) print(s.pop()) # 输出 3 print(s.pop()) # 输出 2 print(s.is_empty()) # 输出 False ``` 答案： ```python class Stack: def __init__(self): self.stack = [] def push(self, item): self.stack.append(item) def pop(self): if not self.is_empty(): 数据结构试题及答案(10套)数据结构试题及答案(10套) 根据您的需求，我为您准备了10套数据结构试题及答案。每套试题包含以下几个部分：选择题、填空题、编程题及答案解析。下面是试题的具体内容： 第一套试题： 选择题： 1. 在数据结构中，什么是栈？ A. 先进先出（FIFO）的数据结构 B. 后进先出（LIFO）的数据结构 C. 随机访问的数据结构 D. 无序排列的数据结构 2. 以下哪种操作与队列的特性不相符？ A. 入队操作 B. 出队操作 C. 查找操作 D. 获取队首元素 填空题： 1. ______ 是一种动态集合，支持插入、删除和查找等操作。 2. 在二叉搜索树中，中序遍历的结果是________。 编程题： 实现一个栈的数据结构，并包含以下操作： - push(x)：将元素 x 压入栈中 - pop()：删除栈顶的元素并返回该元素 - top()：获取栈顶元素的值 - empty()：检查栈是否为空 答案解析： 选择题：B、C 填空题：1. 集合 2. 升序序列 编程题：略 第二套试题： 选择题： 1. 以下哪个数据结构是一种广度优先搜索的应用？ A. 栈 B. 队列 C. 堆 D. 链表 2. 在链表中，如果要删除一个节点，只给出该节点的指针，那么需要通过什么方式完成删除操作？ A. 直接删除该节点 B. 指向该节点的前一个节点的指针 C. 指向该节点的后一个节点的指针 D. 无法完成删除操作 填空题： 1. 树是一种________的数据结构。 2. 二叉树每个节点最多有______个子节点。 编程题： 实现一个队列的数据结构，并包含以下操作： - enqueue(x)：将元素 x 入队 - dequeue()：删除队首的元素并返回该元素 - peek()：获取队首元素的值 - is_empty()：检查队列是否为空 答案解析： 电大《数据结构》2020-2021期末试题及答案 一、单项选择题 1. 一个数组元素a 与( A )的表示等价。 A. *(a+i) B. a+i C. *a+i D. &a+I 2．执行下面程序段时，执行S语句的次数为( D )。 for(int i=1; i<=n; i++) for(int j=1; j<=i; j++) S; A. n2 B. n2/2 C. n(n+1) D. n(n+1)/2 3. 当一个作为实际传递的对象占用的存储空间较大并可能被修改时，应最好说明为( B )，以节省参数值的传输时间和存储参数的空间。 A. 基本类型 B. 引用型 C. 指针型 D. 常值引用型 4. 输出一个二维数组b[m][n]中所有元素值的时间复杂度为( D )。 A. O(n) B. O(m+n) C. O(n2) D. O(m*n) 5. 某算法仅含程序段1和程序段2，程序段1的执行次数3n2，程序段2的执行次数为 0.01n3，则该算法的时间复杂度为（ C ）。 A. O(n) B. O(n2) C. O(n3) D. O(1) 6. 多维数组实际上是由嵌套的（ A ）实现的。 A. 一维数组 B. 多项式 C. 三元组表 D. 简单变量 7. 在一个长度为n的顺序表中删除第i个元素（0≤i≤n-1）时，需要从前向后依次前移（ C ）个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 8. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ A ）。 A. O(n) B. O(n/2) C. O(1) D. O(n2) 9. 设有一个n´n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A存放于B中（ C ）处。 A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/2 10. 不带头结点的单链表first为空的判定条件是（ A ）。 A. first == NULL; B. first->link == NULL; C. first->link == first; D. first != NULL; 《数据结构》期末考试试卷（ A ） 一、选择题（每小题2分，共24分） 1．计算机识别、存储和加工处理的对象被统称为( A ) A.数据 B.数据元素 C.数据结构 D.数据类型 2．栈和队列都是（A） A．限制存取位置的线性结构B．顺序存储的线性结构 C．链式存储的线性结构D．限制存取位置的非线性结构 3．链栈与顺序栈相比，比较明显的优点是( D ) A.插入操作更加方便 B.删除操作更加方便 C.不会出现下溢的情况 D.不会出现上溢的情况 4．采用两类不同存储结构的字符串可分别简称为( B ) A.主串和子串 B.顺序串和链串 C.目标串和模式串 D.变量串和常量串 5．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是：B A. 110 B .108 C. 100 D. 120 6．串是一种特殊的线性表，其特殊性体现在：B A.可以顺序存储 B .数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符 7．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为：C A. 2h B .2h-1 C. 2h+1 D. h+1 软件开发网https://www.doczj.com/doc/8019142046.html, 8．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确？A A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D. 以上都不对 9．一个有n个顶点的无向图最多有多少边？C A. n B .n(n-1) C. n(n-1)/2 D. 2n 10．在一个图中，所有顶点的度数之和等于所有边数的多少倍?C A. 1/2 B .1 C. 2 D. 4 11．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（A） A．左子树的叶子结点B．左子树的分支结点 C．右子树的叶子结点D．右子树的分支结点 软件开发网https://www.doczj.com/doc/8019142046.html, 12．对于哈希函数H(key)=key%13,被称为同义词的关键字是( D ) A.35和41 B.23和39 C.15和44 D.25和51 二、已知某棵二叉树的前序遍历结果为A,B,D,E,G,C,F,H,I,J，其中中序遍历的结果为 D,B,G,E,A,H,F,I,J,C。请画出二叉的具体结构。（注意要写出具体步骤）（10分） 原理见课本128页 三、有图如下，请写出从顶点c0出发的深度优先及宽度优先遍历的结果。(10分) 深度优先；C0-C1-C3-C4-C5-C2 宽度优先：C0-C1-C2-C3-C4-C5 四、有图如下，按Kruskal算法求出其最小生成树。要求写出完整的步骤。（10分） 原理见课本250页 五、给定线性表（12，23，45，66，76，88，93，103，166），试写出在其上进行二分查找关键字值12，93，166的过程。并写出二分查找的算法。（20分） 0 1 2 3 4 5 6 7 8 12 23 45 66 76 88 93 103 166 过程： 2022年泰山学院计算机科学与技术专业《数据结构与算法》科目期末 试卷A（有答案） 一、选择题 1、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（）方法是哈希文件的关键。 A.哈希函数 B.除余法中的质数 C.冲突处理 D.哈希函数和冲突处理 2、将线性表的数据元素进行扩充，允许带结构的线性表是（）。 A.串 B.树 C.广义表 D.栈 3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。 A.顺序表 B.双链表 C.带头结点的双循环链表 D.单循环链表 4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛ 6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。 A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝2 7、下列叙述中，不符合m阶B树定义要求的是（）。 A．根结点最多有m棵子树 B．所有叶结点都在同一层上 C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接 8、一个具有1025个结点的二叉树的高h为（）。 A.11 B.10 C.11至1025之间 D.10至1024之间 9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。 A.其中任意一个结点均无左孩子 B.其中任意一个结点均无右孩子 C.其中只有一个叶结点 D.其中度为2的结点最多为一个 10、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A 的左孩子的平衡因子为0，右孩子的平衡因子为l，则应作（）型调整以使其平衡 A.LL B.LR C.RL D.RR 二、填空题 11、若用n表示图中顶点数目，则有______条边的无向图成为完全图。 12、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为______次；当使用监视哨时，若查找失败，则比较关键字的次数为______。 13、对于一个具有n个结点的单链表，在已知的结点半p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为______。 14、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是______、______、______、______。 15、索引顺序文件既可以顺序存取，也可以______存取。数据结构期末十套卷(包含答案)
《数据结构》期末考试试题及答案
十套数据结构试题及答案
数据结构试题及答案(十套)
东南大学十套数据结构试题及答案
山东科技大学——十套数据结构试题及答案
数据结构试题及答案(10套最新)
十套数据结构试题及答案
十套数据结构试题及答案
东南大学十套数据结构试题与答案
数据结构试题及答案(十套)
最新 十套数据结构试题及答案
《数据结构》期末考试试题及答案
数据结构试题及答案(10套)
电大《数据结构》2020-2021期末试题及答案
《数据结构》期末考试试卷(含答案)
2022年泰山学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)
相关主题
文本预览