 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
数据结构(C语言版)试题 第一章 绪论
下载积分：1800
内容提示：数据结构(C语言版)试题 第一章 绪论
文档格式：DOC|
浏览次数：12|
上传日期： 13:46:51|
文档星级：
该用户还上传了这些文档
数据结构(C语言版)试题 第一章 绪论
官方公共微信急！ 内部堆排序算法的实现！！！包括大根堆的实现和小根堆的实现！！！要完整的！！！_百度知道上传第10章排序习题_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
<span class="g-ico g-ico-star g-ico-star-on" style="width:%">
<span class="g-ico g-ico-star g-ico-star-on" style="width:%">
<span class="g-ico g-ico-star g-ico-star-on" style="width:%">
上传第10章排序习题
上传于||文档简介
&&数​据​结​构​-​-​排​序​习​题
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩17页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢数据结构期末复习题-海文库
全站搜索：
您现在的位置：&>&&>&工学
数据结构期末复习题
00计算机信管《数据结构》期末复习题（一）
一、单选题（每小题2分，共8分）1、在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（
）A、HL=p;p-&next=HL;
B、p-&next=HL;HL=p;C、p-&next=HL;p=HL;
D、p-&next=HL-&HL-&next=p;2、在一个顺序队列中，队首指针指向队首元素的（
）位置。A、前一个
C、当前3、从二叉搜索树中查找一个元素时，其时间复杂度大致为（
）。A、O（n）
C、O（log2n）
D、O（n）4、权值为3、8、6、2、5的叶子结点生成一哈夫曼树，其带权路径长度为（
D、53二、填空题（每空1分，共32分）1、一个算法的时间复杂度为(3n?2nlog2n?4n?7)/(5n)，其数量级表示为（
）。2、在以HL为表头指针的带表头附加结点的单链表和循环链表中，链表为空的条件分别为（
）。3、一个广义表中的元素分为（
）元素和（
）元素两类。4、从一个链栈中删除一个结点时，需要把栈顶结点的（
）域的值赋给（
）。5、在进行函数调用时，需要把每个实参的值和调用后的（
）传送给被调用的函数中。6、对于一棵具有n个结点的二叉树，若一个结点的编号为i (1?i?n)，则它的左孩子结点的编号为（
），右孩子结点的编号为（
），双亲结点的编号为（
）。7、在一棵高度为5的理想平衡树中，最少含有（
）个结点，最多含有（
）个结点。8、在一个堆的顺序存储中，若一个元素的下标为i （1?i?n?1）,则它的左孩子元素的下标为（
），右孩子元素的下标为（
）。9、在一个具有n个顶点的无向完全图中，包含有（
）条边；在一个具有n个顶点的有向完全图中，包含有（
）条边。10、对于一个具有n个顶点和e条边的有向图和无向图，若采用边集数组表示，则存于数组中的边数分别为（
）条。11、以二分查找方法从长度为12的有序表中查找一个元素时，平均查找长度为（
）。12、假定一个线性表为（12，23，74，55，63，40，82，36），若按Key%3条件进行划分，使得同一余数的元素成为一个子表，则得到的三个子表分别为（
）。13、在线性表的散列存储中，装填因子?
又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则?等于（
）。14、在一棵m阶B-树上，每个非树根结点的关键字数目最少为（
）个，最多为（
）个，其子树数目最少为（
）个，最多为（
）个。15、在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为（
），整个堆排序过程的时间复杂度为（
）。16、快速排序在平均情况下的时间复杂度为（
）。221三、运算题（每小题6分，共24分）1、 假定一棵二叉树广义表表示为a(b(c),d(e,f))，分别写出对它进行行先序、中序、后序、按层遍历的结果。先序：中序：后序：按层：2、 已知一个图的顶点集V和边集G分别为：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出发得到最小生成树，试写出在最小生成树中依次得到的各条边。
）3、已知一个图的顶点集Ｖ和边集Ｇ分别为：V={0，1，2，3，4，5，6，7，}；E={（0，2），（1，3），（1，4），（2，4），（2，5），（3，6），（3，7），（4，7），（4，8），（5，7），（6，7），（7，8）}；若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓朴序列（提示：先画出对应的图形，然后再运算）。4、假定一组记录的排序码为（46，79，56，38，40，80，25，34），则对其进行快速排序的第一次划分的结果为（
）。四、阅读算法，回答问题（每小题8分，共16分）1、 void
S){InitStack(S);Push(S,30);push(S,40);Push(S,50);int x=Pop(s)+2*Pop(S);Push(S,x);inti,a[4]={5,8,12,15};for(i=0;i + +)Push(S,a[i];while(!
StackEmpty(S))cout&&Pop(S)&&??;}该算法被调用后得到的输出结果为：（
）2、 void AJ(adjlist GL,int i,int n){Queue Q;InitQueue(Q);cout&&i&&?
?;visited[i]=2QInsert(Q,i);while(!QueueEmpty(Q)){int k=QDelete(Q);edgenode *p=GL[k];while(p!=NULL){int j=p-&if (!visited[j]){cout&&j&&?
?;visited[j]=QInsert(Q,j);}p=p-&}}}该算法的功能为：（
）。五、算法填空，在画有横线的地方填写合适的内容（10分）向以BST为树根指针的二叉搜索树上插入值为item的接点的递归算法：void Insert(BTreeNode *&BST,const ElemType& item){if(BST==NULL){BTreeNode *p=new BTreeNp-&data=______________;BST=p;}else if(item&BST-&data) ______________;else__________________;}六、编写算法（10分）编写向类型为List的线性表L中第i个元素位置插入一个元素的算法，假定不需要对i值进行有效性检查，同时不需要检查存储空间是否用完。
void Insert(List&L,int i,ElemType x)
300双专《数据结构》期末复习题（二）2003年6月
一、单选题（每小题2分，共20分）1、在一个带表头附加结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（
）。A、HL=p;p-&next=HL;
B、p-&next=HL;HL=p;C、p-&next=HL;p=HL;
D、p-&next=HL-&HL-&next=p;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]存放在什么位置？（
D、6965、下列关于二叉树遍历的叙述中，正确的是（
）。A、若一个树叶是某二叉树的中序遍历的最后一个结点，则它必定是该二叉树的前序遍历的最后一个结点B、一个结点是某二叉树的前序遍历的最后一个结点，则它必定是该二叉树的中序遍历的最后一个结点C、若一个结点是某二叉树的中序遍历的最后一个结点，则它必定是该二叉树的前序遍历的最后一个结点D、若一个树叶是某二叉树的前序遍历的最后一个结点，则它必定是该二叉树的中序遍历的最后一个结点6、二叉树的第k层上最多可以有（
）个结点。A、2?1
D、27、对线性表进行二分查找，其前提条件是（
）。A、线性表以链接方式存储，并且按关键码值排好序B、线性表以顺序方式存储，并且按关键码值的检索频率排好序C、线性表以顺序方式存储，并且按关键码值排好序D、线性表以链接方式存储，并且按关键码值的检索频率排好序8、对n个记录进行快速排序，所需要的辅助存储空间为（
）。 kK?1A、O（1）
C、O(log2n)
D、O(n)9、对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（
）个。A、1
D、410、下列关于数据结构的叙述中，正确的是（
）。A、数组是不同类型值的集合；B、递归算法的程序结构比迭代算法的程序结构更为精练；C、树是一种线性结构；D、用一维数组存储一棵完全二叉树是有效的存储方法。二、填空题（每空1分，共26分）1、数据的逻辑结构被分为（
）四种。 242、一个算法的时间复杂度为(3n?2nlog2n?4n)/n，其数量级表示为（
）。3、对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为（
），在表尾插入元素的时间复杂度为（
）。4、假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为（
）个，树的深度为（
），树的度为（
）。5、后缀表达式”9
”的值为（
）；中缀表达式（3+4X）-2Y/3对应的后缀表达式为（
）。6、在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为（
），若假定p为一个数组a的下标，则其后继结点的下标为（
）。7、在树中，一个结点的直接后继结点称为该结点的（
），一个结点的直接前趋结点称为该结点的（
）。8、在初始化一个稀疏矩阵的函数定义中，矩阵形参应说明为（
）参数。9、假定一个线性表为（12，23，74，55，63，40，82，36），若按key%4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为
。10、向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度（
）。11、在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为（
），整个堆排序过程的时间复杂度为（
）。12、在线性表的散列存储中，装填因子?又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则?等于（
）。三、运算题（每小题6分，共24分）1、在如下数组A中链接存储了一个线性表，表头指针为A[0].next，试写出该线性表。A
next 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，6，10，14时，每加入一个数据后堆的变化。四、阅读算法，回答问题（每小题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); 352、
ABC(BTNode
BT {ABC(BT-&left);cout&&BT-&data&&?
?;ABC(BT-&right);}}该算法的功能是：______________________________________
五、算法填空，在画有横线的地方填写合适的内容（8分）二分查找的递归算法：Int Binsch(ElemType A[ ],int low,int high,KeyType K){if______________________{int mid=(low+high)/2;if_____________________//查找成功，返回元素的下标else if(K&A[mid].key)return
Binsch(A,low,mid-1,K);//在左子表上继续查找else return _________________________//在右子表上继续查找}else __________________//查找失败，返回-1}六、编写算法（8分）HL为单链表的表头指针，试写出在该单链表中查找出具有给定的元素item的算法。bool Find(Lnode *HL,ElemType &item)
00双专《数据结构》期末复习题（三）2003年6月
一、单选题（每小题2分，共20分）1、以下数据结构中哪一个是线性结构（
）A、有向图
C、搜索二叉树
D、树2、以下哪一个不是队列的基本运算？（
）A、在队列第i个元素之后插入一个元素
B、从队头删除一个元素C、判断一个队列是否为空
D、读取对头元素的值3、字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（
）个不同的字符串？A、14
D、84、权值为3、8、6、2的叶子结点生成一哈夫曼树，其带权路径长度为（
D、535、在一个长度为n的线性表中顺序查找值为x的元素时，查找成功的平均查找长度为（
C、(n+1)/2
D、(n-1)/26、栈的插入和删除操作在（
）进行。A、栈顶
C、任意位置
D、指定位置7、假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件为（
）。A、front==rear
B、front!=rearC、rear!=null
D、front!=null8、向堆中插入一个元素的时间复杂度为（
）。A、O(log2n)
D、O(nlog2n)9、用链接方式存储的队列，在进行删除运算的时候（
）A、仅修改头指针
B、仅修改尾指针C、头、尾指针都要修改
D、头、尾指针可能都要修改10、如果T2是由有序树T转换而来的二叉树，那么T中结点的前序就是T2中结点的（
）。A、前序
D、层次序11、下面关于图的存储的叙述中正确的是（
）。A、用邻接表法存储图，占用的存储空间大小只与图中边数有关，与结点个数无关B、用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C、用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D、用邻接拒阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关12、设有关键码序列（q,g,m,z,a,n,p,x,h），下面哪一个序列是从上面序列出发建堆的结果？（
）A、a,g,h,m,n,p,q,x,z
B、g,m,q,a,n,p,x,h,zC、a,g,m,h,q,n,p,x,z
D、h,g,m,p,a,n,q,x,z
二、填空题（每空1分，共32分）1、一种抽象数据类型包括（
）两个部分。2、在双向链表中，每个结点包含有两个指针域，一个指向（
）结点，一个指向其（
）结点。3、在稀疏矩阵的带行指针向量的链接存储中，每个结点包含有（
）个域，在相应的十字链接存储中，每个结点包含有（
）个域。4、向一个链栈插入一个新结点时，首先把栈顶指针的值赋给新结点的（
）域，然后把新结点的存储位置赋给（
）。5、在求解迷宫问题的递归算法中，输入一条通路上的每个位置的坐标是按照入口到出口的（
）进行的。6、假定一棵树的广义表表示为A（B（C，D（E，F，G），H（I，J））），则树中所含有的结点数目为（
）个，树的深度为（
），树的度为（
）。7、对于一个具有n个结点的二叉树，对应二叉链表中指针总数为（
）个，其中（
）个用于指向孩子结点，（
）个指针空闲着。8、对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个（
）。9、数据的物理结构被分为（
）四种。10、对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为（
），在表尾插入元素的时间复杂度为（
）。11、对于一棵具有n个结点的完全二叉树，一个结点的编号为i(1?i?n)，若它有左孩子，则左孩子结点的编号为（
），若它有右孩子，则右孩子结点的编号为（
），若它有双亲，则双亲结点的编号为（
712、当向一个大根堆插入一个具有最大值的元素时，需要逐层（
）调整，直到被调整到（
）位置上。13、以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为（
）。14、具有4个顶点的无向完全图有（
）条边，具有6个顶点的无向完全图至少应该有（
）条边才能确保是一个连通图。15、在一棵m阶B_树上，每个非树根结点的关键字数目最少为（
）个，最多为（
）个，其子树数目最少为（
），最多为（
）。三、运算题（每小题6分，共18分）3、 假定一棵二叉树广义表表示为A（B（，D（G）），C（E，F）），画出这棵二叉树，并分别写出对它进行行先序、中序、后序、按层遍历的结果。先序：中序：后序：按层：4、 假定待建立一棵二叉搜索树的一组元素的关键字为：（38，26，62，94，35，50，28，55），按照插入算法画出最后结果的二叉搜索树。5、 有一小根堆其关键字序列为（26，48，35，73，60，50），插入关键字18后，重新调整为堆，写出结果序列，并画出堆图。四、阅读算法，回答问题（每小题4分，共12分）3、 void
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&&Pop(S)&&? ?;}该算法被调用后得到的输出结果为：（
）4、 void AJ(BtreeNode
*BT){if(BT==NULL)
return 0;else
{int depl=AJ(BT-&left);int depr=AJ(BT-&right);if (depl&depr) return depl+1;else return depr+1;}}该算法的功能为：（
）。3、void AK(adjlist GL,int i,int n){cout&&i&&?
? ;visited[i]=edgenode
*p=GL[i];while (p!=NULL){8int j=p-&if( ! visited[j] )
AK(GL,j,n);p=p-&}}该算法的功能是（
）。五、算法填空，在画有横线的地方填写合适的内容（10分）向以BST为树根指针的二叉搜索树上插入值为item的结点的非递归算法：void Insert(BTreeNode *&BST,const ElemType& item){BtreeNode
t=BST,*parent=NULL;While (t !=NULL){parent=t;if(item&t-&data) t=t-&else____________________;}BtreeNode *p=new
BtreeNp-&data=_________________________;if(parent==NULL)____________;else if(item&parent-&data)__________________;else________________________;}向单链表的末尾添加一个元素的算法：void InsertRear(Lnode *&HL,const ElemType &item){Lnode *Newptr=new
LIf____________________________{cerr&&”Memory allocation failare!”&&exit(1);}________________________=newptr-&next=NULL;if (HL==NULL)
HL=_____________________;else {Lnode*p=HL;While (p-&next !=NULL)_________________________________;p-&next=}}六、编写算法（10分）编写从表头指针为HL的单链表中查找出具有最大值的结点的算法，该最大由函数返回，若单链表为空则终止运行。
MaxValue (Lnode
900计算机信管《数据结构》期末复习题（四）2002年6月
一、单选题（每小题2分，共20分）1、在一个长度为n的线性表中顺序查找值为x的元素时，查找成功时的平均查找长度为（
C、(n+1)/2
D、(n-1)/22、栈的插入和删除操作在（
）进行。A、栈顶
C、任意位置
D、指定位置3、假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件为（
）A、front==rear
B、front!=NULLC、rear!=NULL
D、front==NULL4、向堆中插入一个元素的时间复杂度为（
）A、O（log2n）
D、O（nlog2n）5、在一个长度为n的顺序存储的线性表中，删除第i个元素（1?i?n）时，需要从前向后依次前移（
）个元素。A、n-i
B、n- i +1
C、n- i C1
D、i6、设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为（
）A、O（1）
D、O（log2n）7、假定一个顺序队列的队首和队尾指针分别为f和r，则判断队空的条件为（
）A、f+1= =r
B、r+1= =f
D、f= =r8、从堆中删除一个元素的时间复杂度为（
）A、O（log2n）
D、O（nlog2n）二、填空题（每空1分，共32分）1、在一个图中，所有顶点的度数之和等于所有边数的（
）倍。2、对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为（
）条。3、以二分查找方法从长度为n的顺序存储的线性表中查找一个元素时，平均查找长度小于等于（
），时间复杂度为（
）。4、在索引表中，每个索引项至少包含有（
）域这两项。5、在线性表的（
）存储中，无法查找到一个元素的前驱或后继元素；在线性表的（
）存储中，对每一个元素只能采用顺序查找。6、在一棵B_树中，所有叶子结点都处在（
）上，所有叶子结点中空指针数等于该树中所有（
）总数加1。7、在堆排序的过程中，对n个记录建立初始堆需要进行（
）次筛运算，由初始堆到堆排序结束，需要对树根结点进行（
）次筛运算。8、对20个记录进行归并排序时，共需要进行（
）趟归并，在第三趟归并时是把长度为（
）的有序表两两归并为长度为（
）的有序表。9、遍历一棵二叉树包括访问（
）、遍历（
）和遍历（
）三个方面。10、后缀算术表达式8
@的计算结果为（
）。11、在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着（
）的联系。12、栈又称为（
）表，队列又称为（
）表。13、一棵深度为5的满二叉树中的结点数为（
）个，一棵深度为为3的满四叉树中的结点数目为（
）个。21014、对于一棵含有40个结点的理想平衡树，它的高度为（
）。15、从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明（
），若元素的值小于根结点的值，则继续向（
）查找，若元素的值大于根结点的值，则继续向（
）查找。16、当从一个小根堆中删除一个元素时，需要把（
）元素填补到（
）位置，然后再按条件把它逐层（
）调整。17、对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为（
）。18、对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为（
）。19、二分查找过程所对应的判定树既是一棵（
），又是一棵（
）。20、若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个记录的索引，则一级索引表的长度为（
），二级索引表的长度为（
）。21、在一棵20阶的B_树中，每个非树根结点的关键字数目最少为（
）个，最多为（
）个。22、每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换他们的位置，此种排序方法叫做（
）排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做（
）排序。23、在归并排序中，进行每趟归并的时间复杂度为（
），整个排序过程的时间复杂度为（
），空间复杂度为（
）。三、运算题（每小题6分，共18分）1、已知一个有向图的顶点集V和边集G分别为：V={a,b,c,d,e,f,g,h}G={&a,b&,&a,c&,&b,f&,&c,d&,&c,e&,&d,a&,&d,f&,&d,g&,&e,g&,&f,h&}假定该图采用邻接矩阵表示，则分别写出从顶点a出发进行深度优先搜索遍历和广度优先搜索遍历得到的顶点序列。深度优先搜索序列：_____________________________广度优先搜索序列：_____________________________2、假定对线性表（38，25，74，52，48）进行散列存储，采用H（K）=K%7作为散列函数，若分别采用线性探查法和链接法处理冲突，则对应的平均查找长度分别为________________和____________________。3、假定一组记录的排序码为（46，79，56，38，40，80，25，34），则对其进行快速排序的第一次划分后对左、右两个子区间分别进行划分，得到的结果为：___________________________________________________
在对其进行快速排序过程中，对应的二叉搜索树的深度为（
），分支结点数目为（
）。四、阅读算法，回答问题（每小题4分，共12分）5、 void
* &HL){Insert(HL,30);Insert(HL,50);Delete(HL,26);Delete(HL,55);}
假定调用该算法时以HL为表头指针的单链表中的内容为（15，26，37，48，55），则调用返回后该单链表的内容变为：（
）116、 void AB(adjmatrix GA,int i,int n){cout&&i&&?
?;visited[i]=for(int j=0;j&n;j++)if(GA[i][j] ! =0 && GA[i][j] ! =MaxValue&& ! visited[j])AJ(GA,j,n);}该算法的功能为：3、void
*&HL){InitList(HL);InsertRear(HL,30);InsertRear(HL,50);Int
a[5]={15,8,9,26,12};For(int i=0;i&5;i++)InsertFront(HL,a[i]);}该算法被调用执行后，得到的以HL为表头指针的单链表中的数据元素依次为：__________________________________________________4、void AH(Heap
&HBT,const ElemType item)
//HBT为一个小根堆{HBT.heap[HBT.size]=HBT.size++;ElemType
x=Int i=HBT.size-1;While(i ! =0){int j=(i-1)/2;if(x&=HBT.heap[j])HBT.heap[i]=HBT.heap[j];i=j;}HBT.heap[i]=x;}该算法的功能为：________________________________________________
五、算法填空，在画有横线的地方填写合适的内容（10分）从一维数组A[n]中二分查找关键字为K的元素的递归算法，若查找成功则返回对应元素的下标，否则返回-1。Int
Binsch(ElemType A[],int low,int high,KeyType
K){if(low&=high){int mid=(low+high)/2;if(K==A[mid].key)_________________________;else if(K&A[mid].key)_______________________;else______________________________;}else
return C1;}
12六、编写算法（10分）编写在以BST为树根指针的二叉搜索树上进行查找值为item的结点的非递归算法，若查找成功则由item带回整个结点的值并返回true，否则返回false。Bool
Find(BtreeNode
*BST,ElemType& item)00信息管理《数据结构》期末复习题（五）2002年10月
一、单选题（每小题2分，共8分）1、在一个单链表HL中，若要向q所指结点之后插入一个由指针p指向的结点，则执行（
）。A、HL = p；p ―& next = HL；B、p ―& next = HL；HL = p；C、p ―& next = q ―& next ；q ―& next = p；D、p ―& next = q ―& next ；q = p ―& next；2、在一棵深度为5的完全二叉树中，至少含有（
）个结点。A、15
B、16C、30
D、313、从一棵深度为h的二叉搜索树中查找一个元素时，其时间复杂度为（
）。A、O（h）
B、O（h）C、O（log2h）
D、O（n*log2h）4、由权值分别为3，8，10，2，6的叶子结点生成一棵哈夫曼树，该树中双分支结点数为（
D、5二、填空题（每空1分，共32分）1、向一个长度为n的有序单链表中插入一个元素时，为寻找插入位置需要平均比较（
）个元素。2、在以HL为表头指针的单链表和循环链表中，链表为空的条件分别为（
）。3、在一个稀疏矩阵的带行指针向量的链接存储中，每个元素结点共包含有（
）个域，其中（
）个为指针域。4、向一个链栈插入一个p所指向的结点时，需要把栈顶指针的值赋给p所指向的结点的（
），然后把p赋给（
）。5、在用一维数组A[N]存储一个顺序循环队列时，若队列的首、尾指针分别用f和r表示，则队列的长度为（
）。6、对于一棵具有30个结点的二叉树，若一个结点的编号为5，则它的左孩子结点的编号为（
），右孩子结点的编号为（
），双亲结点的编号为（
）。7、在一棵高度为7的理想平衡树中，最少含有（
）个结点，最多含有（
）个结点。8、对于一个具有n个结点的堆，对其进行插入运算的时间复杂度和空间复杂度分别为（
）。9、在一个具有n个顶点的无向连通图中，至少包含有（
）条边，至多包含有（
）条边。10、对于一个具有n个顶点和e条边的有向图和无向图，若采用邻接表表示，则所有顶点单链表中边结点的个数分别为（
）。11、以二分查找方法从长度为20的有序表中查找一个元素时，平均查找长度为（
）。21312、假定一个线性表为（12，23，74，55，63，40，82，36，25，45，64，78），若散列函数为h（K）= K%17，则散列地址分别为4，5，6的元素个数依次为（
）。13、在线性表的散列存储中，装填因子?又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则?等于（
）。14、在一棵m阶的B_树上，树根结点的子树个数最少为（
）个，最多为（
）个，其关键字个数最少为（
）个，最多为（
）个。15、在对n个元素进行堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为（
），空间复杂度为（
）。16、归并排序的时间复杂度为（
），空间复杂度为（
）。三、运算题（每小题6分，共24分）1、假定一棵二叉树广义表表示为：a（b（d），c（e（，g），f（，h））），分别写出对它进行先序、中序、后序、按层编历的结果。先序：中序：后序：按层：
2、已知一个图的顶点集V和边集G分别为：V={0，1，2，3，4，5，6，7}；E={（0，1）3，（0，3）5，（0，5）18，（1，3）7，（1，4）6，（2，4）10，（2，7）20，（3，5）15，（3，6）12，（4，6）8，（4，7）12}；按照普里姆算法从顶点2出发得到最小生成树，试写出在最小生成树中依次得到的各条边。 ，，，，3、已知一个图的顶点集V和边集G分别为：V={0，1，2，3，4，5，6，7，8}E={&0，1&，&0，2&，&1，3&，&1，4&，&2，4&，&2，5&，&3，6&，&3，7&，&4，7&，&4，8&，&5，7&，&6，7&，&7，8&}若采用邻接表存储，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列。（提示：可以先画出对应的图形，然后在运算）。拓扑序列：4、假定一组记录的排序码为（46，79，56，38，40，80，25，34，68，16），则对其进行快速排序的第一次划分后，得到的结果为：
四、阅读算法，回答问题（每小题8分，共16分）1、void
& S){InitStack ( S );Push ( S , 30 );Push ( S , 20 * 2);Push ( S , 15 );int
x = 3 * Pop ( S ) + Pop ( S );Push ( S , x );int
i , a[4] = { 5,9,18,15 };x = 0;14for ( i = 0;i & 4; i ++) {Push (S ,a[i]); x + = a[i]; }Push ( S , x );While (! StackEmpty ( S )) cout &&Pop ( S ) && ?
?;}该算法被调度执行后得到的输出结果为：。
AJ ( adjlist
Q;InitQueue ( Q );Cout && i && ?
?;Visited [ i ] =QInsert ( Q , i );While ( !QueueEmpty ( Q ) ){int
k = Qdelete ( Q ) ;edgenode * p = GL [ k ];while (p ! = NULL){int
j = p ―&if ( ! visited [ j ] ){cout && j && ?
?;visited [ j ] =QInsert (Q , j );}p = p ― &}}}假定形参GL是边集为{（0，1），（0，2），（0，5），（1，3），（1，4），（2，4），（2，5），（3，6），（4，6）}的图所对应的邻接表，形参i和n的值分别为0和7，并且假定邻接表中每个单链表中的边结点都是按照adjvex域的值从大到小的次序链接的，则执行该算法时得到的输出结果为： 输出结果：
。五、算法填空，在画有横线的地方填写合适的内容（10分）//从HBT小根堆中删除堆顶元素并将它返回。ElemType
DeleteHeep(Heap & HBT){if ( HBT.size = = 0 ) { cerr&& ” Heap
null ! ”; exit (1 );}ElemType
temp = HBT.heap [ 0 ];HBT.size― ―;;
x = HBT.heap[HBT.size];int
j = 2 * i + 1;while ( j & = HBT.size C 1 ){
//调整到孩子为空时止
( j & HBT.size C;
( x & = HBT.heap [ j ] )HBT.heap [ i ] = ;15i =}}
六、编写算法（10分）编写一个从数组A[n]中进行二分查找的非递归算法。
( ElemType
A [ ] , int n,KeyType
K )//在A[0]―A[n-1]区间内二分查找关键字为K的元素；//规定使用low和high保存待查区间的下限和上限
00信息管理《数据结构》期末复习题（六）2002年10月
一、单选题（每小题2分，共20分）1、在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（
）A、HL=p;p-&next=HL;
B、p-&next=HL;HL=p;C、p-&next=HL;p=HL;
D、p-&next=HL-&HL-&next=p;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进制数在表示。（
D、6965、下列关于二叉树遍历的叙述中，正确的是（
）。A、若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历的最后一个结点B、若一个结点是某二叉树的前序遍历的最后一个结点，则它必是该二叉树的中序遍历的最后一个结点C、若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历的最后一个结点D、若一个树叶是某二叉树的前序遍历的最后一个结点，则它必是该二叉树的中序遍历的最后一个结点6、二叉树的第k层的结点数最多为（
）。A、2?1
D、27、对线性表进行二分法查找，其前提条件是（
）。A、线性表以链接方式存储，并且按关键码值排好序B、线性表以顺序方式存储，并且按关键码值的检索频率排好序C、线性表以顺序方式存储，并且按关键码值排好序D、线性表以链接方式存储，并且按关键码值的检索频率排好序 KK?1168、对n个记录进行快速排序，所需要的辅助存储空间为（
）。A、O（1）
C、O（log2n）
D、O（n）9、对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（
）个。A、1
D、410、下列关于数据结构的叙述中，正确的是（
）。A、数组是不同类型值的集合B、递归算法的程序结构比迭代算法的程序结构更为精练C、树是一种线性结构D、用一维数组存储一棵完全二叉树是有效的存储方法二、填空题（每空1分，共26分）1、数据的逻辑结构被分为（
）四种。2、一个算法的时间复杂度为(3n?2nlog2n?4n)/n，其数量级表示为（
）。3、对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为（
），在表尾插入元素的时间复杂度为（
）。4、假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为（
）个，树的深度为（
），树的度为（
）。5、后缀算式9
―的值为（
）。中缀算式（3+4X）―2Y/3所对应的后缀算式为（
）。6、在一棵高度为5的理想平衡树中，最少含有（
）个结点，最多含有（
）个结点。7、在树中，一个结点的直接后继结点称为该结点的（
），一个结点的直接前趋结点称为该结点的（
）。8、在一个具有n个顶点的无向完全图中，包含有（
）条边，在一个具有n个顶点的有向完全图中，包含有（
）条边。9、假定一个线性表为（12，23，74，55，63，40，82，36），若按Key%4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为：和
。10、向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度（
）。11、在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为（
），整个堆排序过程的时间复杂度为（
）。12、在线性表的散列存储中，装填因子?又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则?等于（
）。三、运算题（每小题6分，共24分）1、在如下数组A中链接存储了一个线性表，表头指针为A[0].next，试写出该线性表。
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， 3217（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，6，10，14时，每加入一个数据后堆的变化。四、阅读算法，回答问题（每小题7分，共14分）1、在下面的每个程序段中，假定线性表La的类型为List，元素类型ElemType为int，并假定每程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。（1）
( 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、
ABC(BTNode
BT{ABC(BT―&left);Cout&&BT―&data&&?
?;ABC(BT―&right);}}该算法的功能是：
。五、算法填空，在画有横线的地方填写合适的内容（8分）二分查找的递归算法：Int
Binsch ( ElemType
A[ ] , int
high , KeyType
mid = ( low + high ) / 2;//查找成功，返回元素的下标else
if ( K & A[mid].key )return
Binsch ( A,low,mid-1,K );
//在左子表上继续查找else
//在右子表上继续查找}}六、编写算法（8分）HL为单链表的表头指针，试写出在该单链表中查找具有给定的元素item的算法。
Find ( Lnode * HL,ElemType
1800信息管理《数据结构》期末复习题（七）2002年10月
一、单选题（每小题2分，共20分）1、以下数据结构中哪一个是线性结构？（
）A、有向图
C、线索二叉树
D、B树2、在一个单链表HL中，若要向p所指结点之后插入一个由指针q指向的结点，则执行如下（
）语句序列。A、p = q ； = 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
D、85、由权值分别为3，8，6，2的叶子生成一棵哈夫曼树，它的带权路径长度为（
D、53 以下6、7、8题基于下图：
A、EGFACDB
C、EACBDGF
D、EGACDFB7、该二叉树结点的中序遍历的序列为（
）。A、ABCDEGF
B、EAGCFBDC、EACBDGF
D、BDCAFGE8、该二叉树结点的按层遍历的序列为（
）。A、EGFACDB
B、EACBDGFC、EAGCFBD
D、EGACDFB9、下面关于图的存储的叙述中正确的是（
）。A、用邻接表法存储图，占用的存储空间大小只与图中边数有关，与结点个数无关B、用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关）19C、用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D、用邻接拒阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10、设有关键码序列（q,g,m,z,a,n,p,x,h），下面哪一个序列是从上面序列出发建堆的结果？（
）A、a,g,h,m,n,p,q,x,z
B、g,m,q,a,n,p,x,h,zC、a,g,m,h,q,n,p,x,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、试对下图的二叉树画出其：（1） 顺序存储表示的示意图：
（2） 二叉链表存储表示的示意图：
3、判断以下序列是否是小根堆？如果不是，将它调整为小根堆。
20（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 =1; i & 5 ; i ++ )
Push ( S , 2 * a [ i ]);While
( ! StackEmpty ( S )) cout &&Pop( S ) && ?
?;}该算法被调用后得到的输出结果为：2、void
ABC ( BTNode
* BT , int
NULL){ABC ( BT-& left , c1,c2 );c1 ++ ;if ( BT -& left = = NULL
BT -&right = = NULL ) c2 ++;ABC ( BT -& right , c1 ,
c2 );}}该函数执行的功能是什么？五、算法填空，在画有横线的地方填写合适的内容（8分）向单链表的末尾添加一个元素的算法。Void
InsertRear (LNode * & HL , const
ElemType &
item ){LNode
*newptr = new
&& “Memory
allocation
failare!” &&exit (1);}=newptr -& next = NULL;if
(HL = = NULL)HL = ;Else {LNode
* P = HL ;While
(P -& next ! = NULL )21P - & next =}}六、编写算法（8分）编写从类型为List的线性表L中将第i个元素删除的算法，（假定不需要对i的值进行有效性检查，也不用判别L是否为空表。）void
Delete (List
)00信息管理《数据结构》期末复习题（八）2002年10月一、单选题（每小题2分，共20分）1、在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（
）A、HL=p;p-&next=HL;
B、p-&next=HL;HL=p;C、p-&next=HL;p=HL;
D、p-&next=HL-&HL-&next=p;2、用链接方式存储的队列，在进行插入运算时（
）。A、仅修改头指针
B、头、尾指针都要修改C、仅修改尾指针
D、头、尾指针可能都要修改3、下述哪一条是链接存储方式的优点？（
）A、存储密度大B、插入和删除运算方便C、获取符合某种条件的元素方便D、可方便地用于各种物理结构的存储4、一个栈的输入序列为1
5，则下列序列中不可能是栈的输出序列的是（
25、在有n个结点的二叉树链表中，值为非空的链域的个数为（
）。A、n?1
B、2n?1C、n+1
D、2n+16、在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（
B、2eC、n?e
D、n?2e7、对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标依次为（
38、对n个记录的文件进行快速排序，所需要的辅助存储空间为（
）。A、O（1）
B、O（n）C、O（log2n）
D、O（n）9、对于线性表（7，34，55，25，64，46，20，10）进行散列存储的时，若选用H（K）= K % 9作为散列函数，则散列地址为1的元素有（
）个。A、1
D、410、下面的二叉树中，（
）不是完全二叉树。
D 22222二、填空题（每空1分，共26分）1、一个算法的时间复杂度为(3n?2nlog2n?4n)/n，其数量级表示为（
）。2、对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为（
），在表尾插入元素的时间复杂度为（
）。3、设W为一个二维数组，其每个数据元素占用6个字节，行下标i从0到8，列下标j从0到3，则二维数组W的数据元素共占用（
）个字节。W中第6行的元素和第4列的元素共占用（
）个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组W的最后一个数据元素的起始地址为（
）。4、假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为（
）个，树的深度为（
），树的度为（
）。5、后缀算式9
―的值为（
）。中缀算式（3+4X）―2Y/3对应的后缀算式为（
）。6、一个广义表中的元素分为（
）元素和（
）元素两类。7、在有n个叶子结点的哈夫曼树中，总结点数为（
）。8、AOV网是一种（
）的图。9、在一个具有n个顶点的无向完全图中，包含有（
）条边，在一个具有n个顶点的有向完全图中，包含有（
）条边。10、假定一个线性表为（12，23，74，55，63，40，82，36），若按Key%4条件进行划分，使得到的四个子表分别为
。11、向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度（
）。12、在索引表中，若一个索引项对应主表的一个记录，则此索引为（
）索引，若对应主表的若干条记录，则称此索引为（
）索引。13、对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个（
）。14、在快速排序、堆排序、归并排序中，（
）排序是稳定的。三、运算题（每小题6分，共24分）1、在如下数组A中链接存储了一个线性表，表头指针为A[0].next，试写出该线性表。A
data next2、请画出右边无向图的邻接矩阵和邻接表。
3、已知待散列的线性表为（36，15，40，63，
22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）= K % 7，若发生冲突采用线性探查法处理，试：（1）计算出每一个元素的散列地址并在下图中填写出散列表：
323（2）求出在查找每一个元素概率相等情况下的平均查找长度。4、画出向小根堆中加入数据4，2，5，8，3，6，10，14时，每加入一个数据后堆的变化。四、阅读算法，回答问题（每小题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]);
//插入有序表LaTraverseList ( la );
//遍历线性表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 );
ABC (BTNode
BT{ABC(BT―&left);ABC(BT―&right);Cout && BT ―&data && ?
?;}}该算法的功能是：五、算法填空，在画有横线的地方填写合适的内容（8分）二分查找的递归算法。int
Binsch(ElemTye
A[ ] , int
high ,KeyType
mid = (low + high) / 2;if
//查找成功，返回元素的下标else
(K & A[mid].key)return
Binsch(A , low , mid C1 , K );
//在左子表上继续查找else
//在右子表上继续查找
//查找失败，返回 -1}六、编写算法（8分）HL为单链表的表头指针，试写出在该单链表中查找具有给定的元素item的算法。
Find ( LNode
*HL , ElemType
上一篇： 下一篇：
All rights reserved Powered by
copyright ©right 。文档资料库内容来自网络，如有侵犯请联系客服。
