数据结构试题1 第 1 页数据结构试题1 总共： 15 题，共 100.0 分一、单选（共 8 小题， 24.0 分）1. 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动______个元素。（ 3 分）A.8 B.63.5 C.63 D.7 2. 设有一个二维数组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.128 B.127 C.126 D.255 4. 含 5 个结点（元素值均不相同） 的二叉顺序搜索法查表，平均搜索长度为_______。（3 分）A.54 B.42 C.36 D.65 5. 在分析折半搜索的性能时常加入失败结点，即外结点，从而形成扩充的二叉树。若设失败结点 i 所在层次为 I i ，那么搜索失败到达失败所做的数据比较次数是__________。（3.0 分）A.I i +1 B.Ii +2 C.I i -1 D.I i6. 设有一个含 200 个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均控查次数不超过1.5 ，则歼列存储空间应容纳 ________个表项。（设搜索成功的平均搜索长度为 sm=(1+1/(1- α ))/2 ，其中 α 为装填因子）A.400 B.526 C.624 D.676 7.n 个顶点的连通图至少有 ______条边。（ 3.0 分）A.n-1 B.n C.n+1 D.0 8. 一个二叉树按顺序方式存储在一个一维数组中，如图01234567891011121314ABCDEFGHIJ二、简答（共 4 小题， 46.0 分）1. 如右所示的连通图，请画出：（1）以顶点①为根的深度优先生成树；（2）如果有关节点，请找出所有的关节点。数据结构试题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。采用双散列法解决冲突。散列函数和再散列函数分别为： H0(Key)=Key%13 注：％是求余数运算（ =mod) Hi =(Hi-1 +Rev(key+1)%11+1)%13 i=1,2,3,...m-1 其中，函数 REV（x）表示颠倒 10 进制数 x 的各位，如 REV（37）=37，REV(7)=7 等。若插入的关键码序列为 {2,8,31,20,19,53,27}，画出插入这 8 个关键码后的散列表。01234567891011124....
