资源描述：
《数据结构模拟题1解析.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构试题1第3页数据结构试题1总共：15题，共100.0分一、单选（共8小题，24.0分）1.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素。（3分）A.8B.63.5C.63D.72.设有一个二维数组A[m][n],假设A[0][0]存放位置在644（10）,A[2][2]存放位置在676（10）,每个元素占一个空间，则A[4][5]在（）位置，（10）表明用10进数表示。（3分）A.672（10）B.626（10）C.709（10）D.724（10）3.一个有序顺序表有255个对象，采用顺序搜索法查表，平均搜索长度为。（3分）A
2、.128B.127C.126D.2554.含5个结点（元素值均不相同）的二叉顺序搜索法查表，平均搜索长度为。（3分）A.54B.42C.36D.655.在分析折半搜索的性能时常加入失败结点，即外结点，从而形成扩充的二叉树。若设失败结点i所在层次为Ii,那么搜索失败到达失败所做的数据比较次数是。（3.0分）A.Ii+1B.Ii+2C.Ii-1D.Ii6.设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均控查次数不超过1.5,则歼列存储空间应容纳个表项。（设搜索成功的平均搜索长度为sm=（1+1/（1-a））/2,其中a为装填因子）A.4
3、00B.526C.624D.6767.n个顶点的连通图至少有条边。（3.0分）A.n-1B.nC.n+1D.08.一个二叉树按顺序方式存储在一个一维数组中，如图01234567891011121314数据结构试题1第3页二、简答（共4小题，46.0分）1.如右所示的连通图，请画出：（1）以顶点①为根的深度优先生成树；（2）如果有关节点，请找出所有的关节点数据结构试题1第3页1.设有13个初始归并段，其长度分别为28,16,37,42,5,9,13,14,20,17,30,12,18。试画出4路归并时的最佳归并树，并计算它路径长度WPL(12.0分)2.设散列表HT[0.
4、.12],,即表的大小为m=13采用双散列法解决冲突。散列函数和再散列函数分别为：H0(Key尸Key%13注：％是求余数运算(=mod)H=(Hi-1+Rev(key+1)%11+1)%13i=1,2,3,…m-101234567891011124.已知一棵二叉树如左，请分别写出按前序、中序、后序和层次遍历时得到的结点序列。其中，函数REV(x)表示颠倒10进制数x的各位，如REV(37)=37,REV⑺=7等。若插入的关键码序列为{2,8,31,20,19,53,27},画出插入这8个关键码后的散列表。三、计算(共1小题，10.0分)1.有一种简单的排序算法，叫做计
5、数排序(countsorting)。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果放入一个新的表中。必须注意的是，表中所有待排序的关键码互不相同。计数排序算法针对表中的第个记录，投其所好待排序的表一趟，统计表中多少个记录的关键码比该记录的关键小。假设针对某一个记录，统计出的计数值为C,那么，这个记录在新的有序表中的合适的存放位置即：(1)给出适用于计数排序的数据表定义；(4分)(2)使用C+邮言编写实现计数排序的算法；(4分)(3)对于有n个记录的表，关键码比较次数是多少？(2分)四、其它(共2小题，20.0分)1.1ntunknown(BinTree
6、Node*t){//指针t是二叉树的根指针if(t==NULL)return0;elseif(t-leftChild)==NULL&&t一rightChild==NULL)return1;elsereturnunknown(tTeftChilk)+unknown(tfrightChild);}(10.0分)2.下面给出的是一个在二叉树中查找值为x的结点，并打印该结点所有祖先结点的算法。在此算法中，假设值为X的结点不多于一个。此算法排序的非递归遍历形式。因退栈时需要区分其左、右子树是否已经遍历，故在结点进栈时附带有一个标志=0,进入左子树，=1,进入右子树栈ST保存结点指
7、针ptr以及标志tag,top是栈顶指针。voidprint(BinTreeNode*t;Type&x){stackST;inti,top;数据结构试题1第3页top=0;//置空栈while(t!=NULL&&tfdata!=x
8、
9、top!=0){//寻找值为X的结点while(t!=NULL&&t一data!=x){①；ST[top].ptr=t;//进栈ST[top].tag=0;②；}if(t!=NULL&&t一data==x)//找到值为X的结点for(i=1;③;i++)cout<
