1数据结构试卷（一）一、选择题（20 分）1. 组成数据的基本单位是（ 1.C ）。(A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量2. 设数据结构 A=(D，R)，其中 D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构 A 是（ C）。(A) 线性结构(B) 树型结构(C) 图型结构3. 数组的逻辑结构不同于下列（D）的逻辑结构。(A) 线性表(B) 栈(C) 队列4. 二叉树中第 i(i≥1)层上的结点数最多有（C）个。(A) 2i(B) 2i(C) 2i-1(D) 集合(D) 树(D) 2i-125. 设指针变量 p 指向单链表结点 A，则删除结点 A 的后继结点 B 需要的操作为（.A ）。(A) p->next=p->next->next(B) p=p->next(C) p=p->next->next(D) p->next=p6. 设栈 S 和队列 Q 的初始状态为空，元素 E1、E2、E3、E4、E5 和 E6 依次通过栈 S，一个元素出栈后即进入队列 Q，若 6 个元素出列的顺序为 E2、E4、E3、E6、E5 和 E1，则栈 S 的容量至少应该是（.C ）。(A) 6(B) 4(C) 3(D) 27. 将 10 阶对称矩阵压缩存储到一维数组 A 中，则数组 A 的长度最少为（C ）。(A) 100(B) 40(C) 55(D) 808. 设结点 A 有 3 个兄弟结点且结点 B 为结点 A 的双亲结点，则结点 B 的度数数为（8.B(A) 3(B) 4(C) 5(D) 19. 根据二叉树的定义可知二叉树共有（ B）种不同的形态。(A) 4(B) 5(C) 6(D) 710.设有以下四种排序方法，则（ B ）的空间复杂度最大。(A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序二、填空题(30 分)1.设顺序循环队列 Q[0：m-1]的队头指针和队尾指针分别为 F 和 R，其中队头指针 F 指向当前队头元素的前一个位置，队尾指针 R 指向当前队尾元素所在的位置，则出队列的语句为 F = ;。2.设线性表中有 n 个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为 ，在链式存储结构上实现顺序查找的平均时间复杂度为 。3.设一棵二叉树中有 n 个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有 个指针域， 个空指针域。4.设指针变量 p 指向单链表中结点 A，指针变量 s 指向被插入的结点 B，则在结点 A 的后面插入结点 B的操作序列为 。5.设无向图 G 中有 n 个顶点和 e 条边，则其对应的邻接表中有 个表头结点和 个表结点。6.设无向图 G 中有 n 个顶点 e 条边，所有顶点的度数之和为 m，则 e 和 m 有 关系。7.设一...
