数据结构试题试题及答案1VIP专享VIP免费

1 一、 单选题（每小题2 分，共8 分） 1.在一个长度为n 的线性表中顺序查找值为x 的元素时，查找成功时的平均查找长度（即x 同元素的平均比较次数，假定查找每个元素的概率都相等）为 C 。 A.n B.n/2 C.(n+1)/2 D.(n-1)/2 2 。以下数据结构中哪一个是非线性结构？( D ) A. 队列 B. 栈 C. 线性表 D. 二叉树 3.若有18 个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( D ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 4.设有6 个结点的无向图，该图至少应有( A)条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 5．在下列排序方法中，（ c ）方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)；（ d ）方法所有情况下时间复杂度均为0(nlogn)。 a. 插入排序 b. 希尔排序 c. 快速排序 d. 堆排序 6．具有m 个结点的二叉排序树，其最大深度为（ f ），最小深度为（ b ）。 a. log 2 m b. └ log2 m ┘ +1 c. m/2 d .┌ m/2 ┐ -1 e. ┌ m/2 ┐ f. m 7．下列排序方法中，属于不稳定的排序方法是(A ) A.直接插入排序法 B.冒泡排序法 C.基数排序法 D.归并排序法 8 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是( C ) A.快速排序 B.堆排序 C.归并排序 D.基数排序 9 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10 进制表示。 A．688 B．678 C．692 D．696 10 由权值分别为11，8，6，2，5 的叶子结点生成一棵哈夫曼树，它的带 权路 径长度为（ ） A 24 B 71 C 48 D 53 2 11，某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（B ）的 二叉 树。 A、空或只有一个结点 B、高度等于其结点数 D、任意结点无右孩子 C、任意结点无左孩子 12 将 一 棵 有100 个 结 点 的 完 全 二 叉 树 从 上 到 下 ， 从 左 到 右 依 次 对 结 点 进 行 编 号 ， 根 结 点 的编 号 为 1， 则 编 号 为 49 的 结 点 的 左 孩 子 的 编 号 为 ___A___。 A.98 B.99 C.50 D.48 13.设 有 100 个 元 素 ， 用 折 半 查 找 法 进 行 查 找 时 ，...