《数据结构模拟试卷(三)》由会员分享，可在线阅读，更多相关《数据结构模拟试卷(三)（5页珍藏版）》请在金锄头文库上搜索。
1、数据结构模拟试卷三一、单项选择题（40 分，每题 2 分） 1. 在链表中进行操作比在顺序表中进行操作效率高 A顺序查找 B折半查找 C分块查找 D插入 2. 一棵有 124 个叶结点的完全二叉树，最多有（ ）个结点 A247 B248 C249 D251 3. 若有一个栈的输入序列是 1,2,3，.，n，输出序列的第一个元素是 n，则第 i 个输出元素 是（） An-i Bn-i-1 Cn-i+1 D不确定 4. 若某线性表的常用操作是取第 i 个元素及其前趋元素，则采用_。存储方式最 节省时间 A顺序表 B单链表 C双链表 D单向循环 5. 有六个元素 6，5，4，3，2，1 的顺序进栈，
2、请问下列哪一个不是合法的出栈顺序？ （） A543612 B453126 C346521 D234156 6. 一棵二叉树的前序遍历序列为 ABCDEFG,它的中序遍历序列可能是 ACABDEFG BABCDEFG CDACEFBG DADCFEG 7. 在一个单链表中，若删除 p 所指向节点的后续节点，则执行_。 Ap-next=p-next-next; Bp=p-next;p-next=p-next-next; Cp=p-next; Dp=p-next-next; 8. 下列叙述中，正确的是（） A线性链表中的各元素在存储空间中的位置必须是连续的 B线性链表中的表头元素一定存储在其他元素的
3、前面 C线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他 元素的前面 D线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是 任意的 9. 设循环队列的存储空间为 Q(1:35),初始状态为 front = rear = 35。现经过一系列入队与退队 运算后,front = 15,rear = 15,则循环队列中的元素个数为 A15 B16 C20 D0 或 35 10. 设某完全无向图中有 n 个顶点，则该完全无向图中有（ ）条边。 An(n-1)/2 Bn(n-1) Cn2 Dn2-1 11. 二叉树的第 k 层的结点数最多为( ) A2k
4、-1 B2K+1 C2K-1 D2(k-1) 12. 下述哪一条是顺序存储结构的优点?() A插入运算方便 B可方便地用于各种逻辑结构的存储表示 C存储密度大 D删除运算方便 13. 设有一个 n 阶的下三角矩阵 A，如果按照行的顺序将下三角矩阵中的元素（包括对角线 上元素）存放在 n(n+1)个连续的存储单元中，则 Aij与 A00之间有$#$个数据元素 （即不算 Aij和 A00） 。 Aj=i ? i*(i+1)/2 +j-1: i*(i+1)/2+i Cj=i ? i*(i+1)/2 +j: i*(i+1)/2+1 Djx.key) j=j-1; if (irj+1)temp=rj+1
5、;_;rj=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. 已知线性表中的元素以值递增有序排
6、列，并以单链表作存储结构。试写一算法，删除表 中所有大于 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 开始深度优先搜索生成树。
