数据结构模拟试卷(三).docx

数据结构模拟试卷三一、单项选择题（40 分，每题 2 分） 1. 在链表中进行操作比在顺序表中进行操作效率高 A．顺序查找 B．折半查找 C．分块查找 D．插入 2. 一棵有 124 个叶结点的完全二叉树，最多有（ ）个结点 A．247 B．248 C．249 D．251 3. 若有一个栈的输入序列是 1,2,3，...，n，输出序列的第一个元素是 n，则第 i 个输出元素 是（） A．n-i B．n-i-1 C．n-i+1 D．不确定 4. 若某线性表的常用操作是取第 i 个元素及其前趋元素，则采用___________存储方式最 节省时间 A．顺序表 B．单链表 C．双链表 D．单向循环 5. 有六个元素 6，5，4，3，2，1 的顺序进栈，请问下列哪一个不是合法的出栈顺序？ （） A．543612 B．453126 C．346521 D．234156 6. 一棵二叉树的前序遍历序列为 ABCDEFG,它的中序遍历序列可能是 A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG 7. 在一个单链表中，若删除 p 所指向节点的后续节点，则执行____。

A．p->next=p->next->next; B．p=p->next;p->next=p->next->next; C．p=p->next; D．p=p->next->next; 8. 下列叙述中，正确的是（） A．线性链表中的各元素在存储空间中的位置必须是连续的 B．线性链表中的表头元素一定存储在其他元素的前面 C．线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他 元素的前面 D．线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是 任意的 9. 设循环队列的存储空间为 Q(1:35),初始状态为 front = rear = 35现经过一系列入队与退队 运算后,front = 15,rear = 15,则循环队列中的元素个数为 A．15 B．16 C．20 D．0 或 35 10. 设某完全无向图中有 n 个顶点，则该完全无向图中有（ ）条边 A．n(n-1)/2 B．n(n-1) C．n2 D．n2-1 11. 二叉树的第 k 层的结点数最多为( ) A．2^k-1 B．2K+1 C．2K-1 D．2^(k-1) 12. 下述哪一条是顺序存储结构的优点?() A．插入运算方便 B．可方便地用于各种逻辑结构的存储表示 C．存储密度大 D．删除运算方便 13. 设有一个 n 阶的下三角矩阵 A，如果按照行的顺序将下三角矩阵中的元素（包括对角线 上元素）存放在 n(n+1)个连续的存储单元中，则 A[i][j]与 A[0][0]之间有[$##$]个数据元素 （即不算 A[i][j]和 A[0][0]） 。

A．j=i ? i*(i+1)/2 +j-1: i*(i+1)/2+i C．j>=i ? i*(i+1)/2 +j: i*(i+1)/2+1 D．jx.key) j=j-1; if (ir[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;} if (exchange==0) return; } }4. 以下函数为链栈的进栈操作，x 是要进栈的结点的数据域，top 为栈顶指针 struct node { ElemType data; struct node *next; }; struct node *top void Push(ElemType x) { struct node *p; p=(struct node*)malloc(___(1)_____); p->data=x; ___(2)_____ ___(3)_____ }四、应用题（6 题，共 66 分，如果是算法设计，请务必添加必要的注释！！） 1. 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。

试写一算法，删除表 中所有大于 x 且小于 y 的元素（若表中存在这样的元素）同时释放被删除结点空间 （10 分）2. 求一个数组的最长递减子序列 比如{9，4，3，2，5，4，3，2}的最长递减子序列为 {9，5，4，3，2}（10 分）3. 求一个矩阵中最大的二维矩阵(元素和最大).如:（12 分） 1 2 0 3 4 2 3 4 5 1 1 1 5 3 0中最大的是: 4 5 5 34. 输入一个整数 n，求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数 （12 分）例如输入 12，从 1 到 12 这些整数中包含 1 的数字有 1，10，11 和 12，1 一共出现了 5 次5.画出下图的邻接矩阵和邻接表（10 分）6. 已知无向图如下所示：（12 分） （1）给出从 V1 开始的广度优先搜索序列； （2）画出它的邻接表； （3）画出从 V1 开始深度优先搜索生成树。