还剩10页未读，继续阅读
本资源只提供10页预览，全部文档请下载后查看！喜欢就下载吧，查找使用更方便
文本内容:
模拟试题
3.当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（）12A.n-1B.log2n C.2log2n D.n冒泡排序2nn选择排序2n插入排序2堆排序nlog n归并排序nlog2nn快速排序2n希尔排序
2.以下时间复杂性不是（的排序方法是（）2O nj直接插入排序二路归并排序.冒泡排序直接选择排序A,B.C D.对采用二分查找法进行查找运算的查找表，要求按（）方式进行存储
3..顺序存储链式存储A.B顺序存储且结点按关键字有序链式存储且结点按关键字有序C.D..设有序表的关键字序列为｛）当用二分查找法查找健值为的结点时，经41,4,6,10,18,35,42,53,67,71,78,84,92,99,84（）次比较后查找成功A.2B.3C,4D.
6.n
（2）（）（）（）A.O nB.O nlog2n C.O n D.O log2n.设有个结点的无向图，该图至少应有（）条边能确保是一个连通图76A.5B.6C,7D
8.在无向图中，所有顶点的度数之和是所有边数的（）倍8A.
0.5B.l C,2D,
4.深度为的二叉树最多有（）个结点.96A.64B.63C.32D.
31.将含有个结点的完全二叉树从根结点开始编号，根为号，后面按从上到下、从左到右的顺序对结点编号，那10831么编号为的双亲结点编号为（）41A.42B.40C.21D.
20.已知某二叉树的后序遍历序列是中序遍历序列是它的前序遍历序列是（）11dabec,deabc,A.acbed B.deabc C.decab D.cedba.设二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序（）
12.都不相同完全相同A B.先序和中序相同，而与后序不同.中序和后序相同，而与先序不同C.D如果以链表作为栈的存储结构，做退栈操作时（）
13.必须判别栈是否满必须判别栈是否空A.B..判别栈元素的类型对栈不做任何操作C D.链栈与顺序栈相比，有一个比较明显的优点即
14.插入操作更方便通常不会出现栈满的情况A.B.不会出现栈空的情况删除操作更方便C.D..线性结构中的一个结点代表一个15数据元素数据项数据数据结构A,B.C,D,二.填空题.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是的，1否则称为的.按照排序过程涉及的存储设备的不同，排序可分为排序和排序
2.直接插入排序是稳定的，它的时间复杂性为空间复杂度为3o.对于个记录的集合进行冒泡排序，其最坏情况下所需的时间复杂度是4n o.二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值于其左孩子及其子孙5的键值且于其右孩子及其子孙的键值.中根遍历一棵二叉排序树所得的结点访问序列是键值的序列
6.平衡二叉排序树上任一结点的平衡因子只可能是、或
7.采用散列技术时需要考虑的两个主要问题是
一、
二、
8.一个具有个顶点的完全无向图的边数为一个具有个顶点的完全有向图的弧度数为9n on o
10.遍历图的基本方法有优先搜索和___________优先搜索两种
11.在无向图中，如果从顶点v到顶点V，有路径，则称v和V，是的如果对于图中的任意两个顶点VIMEV,且和％都是连通的，则称为Vi Go.二叉树第层上至多有个结点12ii=l.深度为的二叉树至多有个结点13kk=l.具有个结点的二叉树中一共有个指针域，其中只有个用来指向结点的左右孩子，其余的个指14n针域为NULLo.有个叶子结点的哈夫曼树，其结点总数为15m o需要压缩存储的矩阵可分为矩阵和矩阵两种
16.队称为线性表
17..从某种意义是说，数据、数据元素和数据项实际反映了数据组织的三个层次，数据可由若干个构成，数据18元素可由若干个构成.常见时间复杂性的量级有常数阶、对数阶线性阶、平方阶、和指数阶
190000.线性结构的基本特征是若至少含有一个结点，则除起始结点没有直接外，其他结点有且仅有一个直接；20除终端结点没有直接外，其它结点有且仅有一个直接.三.名词解释题排序.堆..查找长度.无向完全图.有向完全图L
23.
456.二叉树
7.满二叉树
8..栈
9..队列10・链表.简答题什么是二叉排序树？
1.什么是顺序表？
2.什么叫稀疏矩阵？
3.静态查找表与动态查找表的区别是什么
4.什么叫无向图
5.五.解答题判断下列两序列是否为堆？若不是，按照建堆的思想把它调整为堆，并用图表示建堆的过程
1.；13,10,12,22,36,18,28,4025,8,11,15,23,20,32,7o.已知数据序列为对该数据序列进行排序，试写出插入排序和冒泡排序每趟的结果212,
5.9,20,6,31,24,.对长度为的有序表进行二分查找，请画出它的一棵判定树，并求等概率情况下的平均查找长度320六.算法设计题.找出数组中元素的最大值和次最大值本小题以数组元素的比较为标准操作1o..在数组中查找值为的元素，若找到则输出其位置〈=否则输出作为标志2A[L.n]K ili=n,
0.设有数组试设计一个算法,求数组的逆序3A[n],nL A[n]模拟试题
4、单项选择题下面程序段的时间复杂度是Lfori=0;in;i++forj=l;jm;j++；A[i][j]=0A.On B,Om+n+l C,Om+nD,Om*n.在单链表中，指针指向元素为的结点，实现“删除的后继”的语句是2p xxA.p=p-next;B.p-next=p-next-next;C.p-next=p;D.p=p-next-next;.在头指针为且表长大于的单循环链表中，指针指向表中某个结点，若3head1p p-next-next=head^lj指向头结点指向尾结点A.p B.p的直接后继是头结点的直接后继是尾结点C.*p D.*P.判定“带头结点的链队列为空”的条件是4二二二二A.Q.front NULLB.Q.rear NULLC.Q.front==Q.rear D.Q.front!=Q.rear.设有两个串和求在中首次出现的位置的串运算称作5T P,P T联接求子串字符定位子串定位A.B.C.D..广义表的长度为6A=a,b,,cdeA.4B.5C.6D,7一棵含个结点的二叉树的身度至少为718A.3B.4C.5D.
68.已知二叉树的先序序列为ABDECF,中序序列为DBEAFC,则后序序列为C.DEBCFA D.DEBFCAA.DEBAFC B.DEFBCA.无向图中一个顶点的度是指图中
9.通过该顶点的简单路径数通A C.过该顶点的回路数与该顶点相邻接的顶点数B.与该顶点连通的顶点数在有向图中，所有顶点的入度之和是所有顶点出度之和的倍D.
10.A.O.5B.1C.2D.4在下列排序方法中，平均时间复杂度为（）且空间性能最好的是（）IL Onlogn.快速排序堆排序归并排序基数排序A B.C.D..已知一组关键字为其中每相邻两个为有序子序列对这些子序列进行一趟两两归并12{25,48,36,72,79,82,23,40,16,35},的结果是（））A.{25,36,48,72,23,40,79,82,16,35}B.{25,36,48,72,16,23,40,79,82,35C.{25,36,48,72,16,23,35,40,79,82}D.{16,23,25,35,36,40,48,72,79,82}.设有序表的关键字序列为）当用二分查找法查找健值为的结点时，经13{1,4,6,10,18,35,42,53,67,71,78,84,92,99,84（）次比较后查找成功A.2B.3C.4D.12以下说法正确的是（）
14.查找表中数据元素的任何数据项都可以作为关键字A.采用二分查找法对有序表进行查找总比采用顺序查找法对其进行查找要快B.二叉排序数的查找和二分查找时间的性能相同C.最佳二叉排序树一定是平衡二叉树D..倒排文件的主要优点是（）15便于进行插入和删除运算便于进行文件的恢复A.B.便于进行多关键字查询节省存储空间C.D.
二、填空题.抽象数据类型的特点是将和封装在一起，从而现实信息隐藏
1.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需一个位置
2.在队列中，允许进行插入操作的一端称为允许进行删除操作的一端称为3o.对于顺序栈而言，在栈满状态下，如果此时再做进栈运算，则会发生“4，，则和依次联接后的结果是5SlHgoocT,S2=”,S3Hbook SI,S2S
3.假设三维数组按行优先顺序存储，若每个元素占个存储单元，且首地址为则元素的存储地址是6A
[10]
[9]
[8]3100,A[9H8]
[7].已知在一棵含有个结点的树中，只有度为的分支结点和度为的叶子结点，则该树中含有的叶子结点的数目为7n k
0.能够成功完全拓扑排序的图一定是一个8o.如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排序两者之中，选用较为适当
9.散列文件删除记录时，仅需对被删记录即可10
三、解答题.假设通信电文使用的字符集为）名字符在电文中出现的频度分别为试为这个字符设计哈1{a,b,cde,f,34,5,12,23,8,18,6夫曼编码请先画出你所构造的哈夫曼树（要求树中左孩子结点的权值小于右孩子结点的权值），然后分别写出每个字符对应的编码.已知两个的稀疏矩阵的三元组表分别如下24x514161132221822-22请画出这两个稀疏矩阵之和的三元组表.从空树起，依次插入关键字构造一棵二叉排序树340,8,90,15,62,95,12,23,56,32,⑴画出该二叉排序树⑵画出删去该树中元素值为的结点之后的二叉排序树90
四、算法设计题假设以带头结点的单循环链表作非递减有序线性表的存储结构请设计一个时间复杂度为的算法，删除表中所有数值L On相同的多余元素，并释放结点空间例如7,10,10,21,30,42,42,42,51,70经算法操作后变为7,10,21,30,42,51,70稀疏矩阵用三元组的表示形式，试写一算法实现两个稀疏矩阵相加，结果仍用三元组表示
2..假设一个算术表达式中可以包含三中括号圆括号和“尸，方括号和以及花括号与和且这三种括号可按任意的次序3T T嵌套试用，如试利用栈的运算编写判断给定表达式中所含括号是否正确配对出现的算法可设表达式已存入字符型数组中内蒙古财经学院期末考试《数据结构》试卷A
一、单项选择题分1x10=
10、对于一个个顶点的图，若采用邻接矩阵存储贝矩阵的大小为1N J2A NB NC N+l DN-
1、每次从无序表中取一个元素把它插到有序表的合适位置，此种排序为；2每次从无序表挑选出一个最大或最小的，把它与第一个位置或最后一个位置交换，此种排序为；每次比较两个相邻的元素，若出现逆序，则交换这两个元素的位置，此种排序为；每次把相邻的两个有序表合成一个有序表的方法是.堆排序快速排序插入排序交换排序A BC D基数排序冒泡排序希尔排序归并排序E FG H、解决散列中出现冲突问题的常采用的方法是3（）数字分析法、除留余数法、平方取中法（）数字分析法、除留余数法、线性探测法（）数字分析法、线性A BC探测法、双散列法（）线性探测法、二次探测法、链地址法D、已知某二叉树先序遍历序列为则它可能的中序遍历序列为4ABDCE o（）（）A BCADEB CBADE（）（）C BEACDD BDAEC、若树中用一个分支把两个结点连接起来，则5o（）不一定出现环（）一定出现环A B（）使树的度数增一（）前面说法都不正确C D、设散列地址空间为-为表项的关键码，散列函数采用除留余数法，（）为减少冲突的频率，一6-M-L KHASH K=K%P般为P（）（）小于的最大质数（）大于的最大质数（）小于的最大合数A MB MC MD M、在一般情况下，将递归转化为非递归算法应该设置（）7（）栈（）队列（）栈或队列（）数组A BC D
二、判断题（二分）1x
1010、若有一个结点是二叉树中某个子树的中序遍历的最后一个结点，则它一定是该子树的子树前序遍历的最后一个结点（）
1、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用.2（）、设为哈夫曼树的叶子结点数目，则该哈夫曼树共有个结点（）3N2*N+
1、二叉树的中序遍历的和后序遍历可以唯一决定一棵二叉树（）
4、线性表的逻辑顺序与物理顺序总是一致的（）
5、带表头的单链表比不带表头的单链表操作更简单（）
6、有（）个顶点的无向连通图至少有条边.（）7N N1N-
1、外部排序只能选用归并排序（）
8、快速排序和冒泡排序都是不稳定排序（）
9、二叉树是特特殊的树（）10
四、简答题（分）
30、线性表有两种存储结构一是顺序表，二是链表试问1（）如果有个线性表同时存在，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变在此情况下，1n应选用哪种存储结构？为什么？（）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应选用哪种存储2结构？为什么？（分）
5、采用折半查找方法进行查找的数据文件应满足什么条件？（分）
25、设双向循环链表中结点的结构为（），且不带表头结点若想在指针所指结点之后插入指针所指结点，3data,llink,rllink ps则应执行怎样的操作？（分）
5、已知一棵二叉树的前序便历的结果是中序便历的结果是试画出这棵二叉树（分）构4ABECDFGHIJ,EBCDAFHIGJ,
5、给定权值集合｛）
五、造相应的霍夫曼树，并计算它的带权外部路径长度（分）（515,03,14,02,06,09,16,17,57由如下的网络邻接矩阵，画出一棵最小生成树分）
六、给定一个关键字序列{请写出快速排序第一趟的结果，堆排序时所建的初始堆，归并排24,19,32,43,38,6,
13.22},序的全过程然后回答上述三种排序方法中哪一种使用的辅助空间最少？在最坏情况下哪一种方法的时间复杂度最差？（10分）
七、编写程序（分）
33、统计二叉树结点的个数的算法（分）
111、设一个带表头结点的单链表中所有元素结点的数据值无序排列，试编写一个函数，删除表中值为的元素（若存在）2X（分）
12、写出冒泡排序算法.（分）310注试卷与答题纸一起交内蒙古财经学院期末考试《数据结构》试卷（A）
一、单项选择题、（）、（）、、、、、
二、1A2CDFH3D4D5C6B7A判断题
1、X
2、X
3、
4、X
5、V
6、、、8V
9、7V四简答题、（）链表（）顺序表
12、1顺序存储,且有序、2s-rlink=p-rlink;s-llink=p;、3p-rlink-llink=s;p-rlink=s;、
45、wpl=229树的根权值为82
五、包含
六、快速67111012COST=46排序的第一趟结果小顶堆大221961324324338顶堆归并结果132238326192414332222464338338193243619241322323843192224613
七、
1、templateclass Type class friendBinTreeNode{class BinTreeType;Type data;BinTreeNode*leftchild/rightchild;;templateclass Typeclass BinTree{BinTreeNode*root;public:BinTree;；int numyeziO;templateclass Typeint BinTree::numyezi{if root==NULL return0;else ifroot-leftchild==NULLroot-righchild==NULL return1;else{int m=numyeziroot-leftchild;int n=numyeziroot-righchild;return m+n+l;}、2template classTypeclass ListNode{friend classListType;type data;ListNodeType*link;;template classTypeclassList{ListNode*first;public:List;void deleint min,int max;;template classType voidList::deleintmin,int max{ifminmaxreturn;ListNode*p=first-link,*pre=first;whilep{ifp-datamaxp-datamin{pr-link=p-link;delete p;p=pre-link;else{pre=p;p=p-link;}、}3template classTypevoid dataListType::BubbleSort{int pass=1;int exchange=1;whilepassCurrentsizeexchange{〃标志置为假定未交换exchange=0;0,for intj=CurrentSize-1;j=pass;j--〃逆序ifVector|j-1]Vectorfj]{SwapVector[j-1],Vectorfj];〃交换exchange=1;〃标志置为1,有交换pass++;。
个人认证
优秀文档
获得点赞 0
