计算机科学与技术专业数据结构试题 下载答案

《计算机科学与技术专业数据结构试题 下载答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、计算机科学与技术专业数据结构试题　　　　　　下载答案总共：15题，共100.0分一、单选（共8小题，24.0分）1.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动______个元素。（3分）A.8　　　　　　　B.63.5C.63　　　　　　D.72.设有一个二维数组A[m][n],假设A[0][0]存放位置在644(10),A[2][2]存放位置在676(10)，每个元素占一个空间，则A[4][5]在（）位置，(10)表明用10进数表示。（3.0分）A.672(10)　　

2、　　　　　B.626(10)C.709(10)　　　　　　　D.724(10)3.一个有序顺序表有255个对象，采用顺序搜索法查表，平均搜索长度为________。（3.0分）A.128　　　　　B.127C.126　　　　　D.2554.含5个结点（元素值均不相同）的二叉顺序搜索法查表，平均搜索长度为_______。（3.0分）A.54　　　　　B.42C.36　　　　　D.655.在分析折半搜索的性能时常加入失败结点，即外结点，从而形成扩充的二叉树。若设失败结点i所在层次为Ii，那么搜索失败到达失

3、败所做的数据比较次数是__________。（3.0分）A.Ii+1　　　　B.Ii+2C.Ii-1　　　　D.Ii6.设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均控查次数不超过1.5，则歼列存储空间应容纳________个表项。（设搜索成功的平均搜索长度为sm=(1+1/(1-α))/2，其中α为装填因子）A.400　　　　B.526C.624　　　　D.6767.n个顶点的连通图至少有______条边。（3.0分）A.n-1　　　　B.nC.n+1　　　　

4、D.08.一个二叉树按顺序方式存储在一个一维数组中，如图01234567891011121314ABCDEFGHIJ二、简答（共4小题，46.0分）1.如下所示的连通图，请画出：（1）以顶点①为根的深度优先生成树；（2）如果有关节点，请找出所有的关节点。2.设有13个初始归并段，其长度分别为28，16，37，42，5，9，13，14，20，17，30，12，18。试画出4路归并时的最佳归并树，并计算它路径长度WPL。（12.0分）3.设散列表HT[0..12]，，即表的大小为m=13。采用双散列法解决

5、冲突。散列函数和再散列函数分别为：H0(Key)=Key%13注：％是求余数运算（=mod)Hi=(Hi-1+Rev(key+1)%11+1)%13i=1,2,3,...m-1其中，函数REV（x）表示颠倒10进制数x的各位，如REV（37）=37，REV(7)=7等。若插入的关键码序列为{2,8,31,20,19,53,27}，画出插入这8个关键码后的散列表。　0　1　2　3　4　5　6　7　8　9　10　11　12             4.已知一棵二叉树如下，请分别写出按前序、中序、后序和层次

6、遍历时得到的结点序列。三、计算（共1小题，10.0分）1.有一种简单的排序算法，叫做计数排序（countsorting）。这种排序算法对一个待排序的表（用数组表示）进行排序，并将排序结果放入一个新的表中。必须注意的是，表中所有待排序的关键码互不相同。计数排序算法针对表中的第个记录，投其所好待排序的表一趟，统计表中多少个记录的关键码比该记录的关键小。假设针对某一个记录，统计出的计数值为C，那么，这个记录在新的有序表中的合适的存放位置即：（1）给出适用于计数排序的数据表定义；（4分）（2)使用C++语言编

7、写实现计数排序的算法；（4分）（3）对于有n个记录的表，关键码比较次数是多少？（2分）四、其它（共2小题，20.0分）1.intunknown(BinTreeNode*t){　　//指针t是二叉树的根指针　　if(t==NULL)return0;　　elseif(t→leftChild)==NULL&&t→rightChild==NULL)return1;　　　　　elsereturnunknown(t→leftChilk)+unknown(t→rightChild);}(10.0分)2.下面给出的是

8、一个在二叉树中查找值为x的结点，并打印该结点所有祖先结点的算法。在此算法中，假设值为X的结点不多于一个。此算法排序的非递归遍历形式。因退栈时需要区分其左、右子树是否已经遍历，故在结点进栈时附带有一个标志=0，进入左子树，=1，进入右子树栈ST保存结点指针ptr以及标志tag,top是栈顶指针。voidprint(BinTreeNode*t;Type&x){　　　stackST;inti,top;　　　top=0;//置空栈　　　while(t!=NULL