数据结构模拟题目

模拟题1一、填空题1.数据结构的基本单位是。2.从存储结构上讲，线性表的表示可分为和链接两类。3.设顺序表长度为n，则删除第i（i=1,2,…,n）个元素需要移动个元素。4.后缀表达式20105*＋497/－的值为。5.一棵二叉树中，若叶结点的个数为2005，则度为2的结点个数为。6.遍历一棵二叉搜索树，将得到一个以关键字值递增排列的有序序列。7.5阶B树的高度为2时，树中元素个数最少为。8.若有向图的拓扑排序不能输出所有的顶点，则该有向图存在。二、单项选择题1.若用单链表来表示队列,则选用最好。（）A.只带尾指针的非循环链表B.只带尾指针的循环链表C.只带头指针的非循环链表D.只带头指针的循环链表2.设有一个二维数组A[m][n]按行优先顺序存储，假设A[0][0]的地址是644，A[2][2]的地址是676，每个元素占1个单元，则A[4][5]的地址是。（）A.672B.626C.709D.7243.森林的后序遍历等价于其对应二叉树的遍历。（）A.先序B.中序C.后序D.按层4.具有10个顶点的连通图的深度优先搜索生成树，其边的数目为。（）A.9B.10C.11D.85.下列说法错误的是。（）A.已知先序和中序遍历序列能唯一确定一棵二叉树B.已知后序和中序遍历序列能唯一确定一棵二叉树C.已知先序和后序遍历序列能唯一确定一棵二叉树D.已知先序遍历序列能唯一确定一棵二叉搜索树6.下列排序算法中，第一趟排序后能确定某个元素最终位置的算法是。（）A.直接插入排序B.快速排序C.两路合并排序D.以上均不对7.散列表采用线性探查法解决冲突会出现现象。（）A.二次聚集B.探查失败C.假溢出D.线性聚集三、简答题1.给定稀疏矩阵（如下图所示），请写出该矩阵执行快速转置时用到的num[]和k[]的值。0129403000080300201002406001800072.表长为11的散列表采用双散列法解决冲突，散列函数h1(key)=key%11，h2(key)=key%9+1。已知散列表目前如下：下标012345678910关键字122570请问在该散列表中再依次插入关键字80、19、41后，散列表的情况如何？3.写出下图所有可能的拓扑序列。123454.使用普里姆（Prim）算法以A为源点，构造下图的最小代价生成树，要求画出构造过程中各步的结果。CBFEAD1015106857812125.以37，45，25，14，91，43，27，26为输入序列构建二叉搜索树，⑴画出该二叉搜索树；⑵画出该二叉搜索树对应的森林。6.元素序列（60，21，19，7，15，28，4）按两路合并算法进行排序。⑴写出各趟排序结果。⑵两路合并排序平均情况下的渐近时间复杂度为多少？7.下图是一个三阶B-树，请画出依次删除50、10之后B-树。5020356070656755752510368.设字符集合S={A，E，I，O，U}，各字符的使用频率为W={20，10，17，5，25}。⑴画出哈夫曼树；（构建新树时，新树根的左子树根的权值小于等于右子树根的权值，新树根的值是左、右子树根结点权值之和）⑵求该哈夫曼树的带权路径长度。四、程序填空题下面的程序是顺序表的对半搜索的迭代算法，请补充完整。templateclassTintSeqListT::BiSearch1(constT&x)const{inti,low=1,high=length;while(low=high){i=⑴;if(xelements[i-1])⑵;elseif(xelements[i-1])low=i+1;else⑶;}return0;}五、程序阅读题下面的程序是二叉树类的某个成员函数templateclassTvoidBTreeT::A(BTNodeT*p){BTNodeT*q;if(p){q=p-lchild;p-lchild=p-rchild;p-rchild=q;A(p-lchild);A(p-rchild);}}⑴请说明该成员函数的作用是什么？⑵若指针p的指向如右上图所示，请画出执行该函数后的二叉树？六、程序设计题(10分)在单链表类SingleList中增加一个成员函数Print，输出单链表上所有大于x的元素。（提示：单链表上的元素不是有序的；只要写出成员函数即可，注意成员函数的书写格式。）1254367p模拟题2一、填空题1.数据的逻辑结构是指。2.AOV网中的领先关系是一种拟序关系，它具有传递性和。3.队列中，允许插入元素的一端称为。4.后缀表达式532*3＋3/＋的值为。5.一棵有1927个结点的二叉树，所有结点的度之和为。6.具有100个结点的完全二叉树的高度是。7.5阶B树中非失败结点的元素个数最多为。8.10个顶点的无向图中有4条边，若采用邻接矩阵表示，则矩阵中的非0元素个数是个。二、单项选择题1.线性表采用链表存储结构的特点是。（）A.结点的地址必须连续B.可以随机存取C.插入、删除操作不必移动元素D.需要事先估计所需存储空间2.设1、2、3三个元素依次进栈，则不可能是其出栈序列。（）A.1，2，3B.2，3，1C.3，2，1D.3，1，23.对半搜索算法的条件是。（）A.顺序存储，元素有序B.顺序存储，元素无序C.链接存储，元素有序D.链接存储，元素无序4.高度为5的二叉树上，最多有个结点。（）A.5B.16C.31D.325.二叉搜索树中，是关键字值最大的结点。（）A.先序遍历序列中的最后一个结点B.中序遍历序列中的最后一个结点C.后序遍历序列中的最后一个结点D.按层遍历序列中的最后一个结点6.有n个顶点的有向图中最多有条边。（）A.nB.n(n-1)C.n(n+1)D.n27.下列算法中，在最坏情况下的渐近时间复杂度不高于O(nlog2n)。（）A.简单选择排序B.直接插入排序C.快速排序D.两路合并排序三、简答题1.画出对长度为9的有序表进行对半搜索的二叉判定树，并求等概率搜索时成功搜索情况下的平均搜索长度。2.设有向图的邻接表如下所示，请写出该图的邻接矩阵，并且求出各个顶点的出度。0^0^132434550^11^42^0^3.设有向图如下图所示，请画出该图所有的强连通分量。2465314.使用普里姆（Prim）算法以A为源点，构造下图的最小代价生成树，要求画出构造过程中各步的结果。ACBEFD752163195.设一棵二叉树的先序遍历序列是ABDCEF，中序遍历序列是BDAECF，请画出该二叉树。6.已知二叉树如下图所示，请画出该二叉树对应的森林。ABCDFGIEH7.下图是一个3阶B-树，请画出插入37之后的B-树，再画出在此基础上插入38后的B树。20352519368.设字符集合S={A，B，C，D，E}，各字符的使用频率为W={5，7，8，9，10}。⑴画出哈夫曼树；（构建新树时，新树根的左子树根的权值小于等于右子树根的权值）⑵求该哈夫曼树的带权路径长度。四、程序填空题下面是快速排序的程序，请补充完整。templateclassTvoidQSort(TA[],intleft,intright){inti,j;if(leftright){i=left;j=right+1;do{do{i++;}while();do{j--;}while(A[j]A[left]);if(ij)Swap(A[i],A[j]);}while(ij);Swap(A[left],);QSort(A,left,j-1);QSort(A,j+1,);}}五、程序阅读题下面的程序是单链表类的某个成员函数templateclassTvoidSingleListT::A(){NodeT*p=first,*q;first=NULL;while(p){q=p-link;p-link=first;first=p;p=q;}}⑴请说明该成员函数的作用是什么？⑵若有单链表结构如右上图所示，请画出执行该函数后的单链表结构。六、程序设计题在带表头结点的单链表类HeaderList中增加一个成员函数boolHeaderListT::Min(T&result)const实现的功能是，若单链表为空，则函数返回false；否则，函数返回true，并且将所有结点中的最小值保存在引用参数result中。（不用声明HeaderList类，只要实现该成员函数即可。）12345^first