c语言数据结构

一、单选题（共有题目5题,共计50.0分）

1. 在一个长度为n的顺序存储的线性表中，向第i个元素（1 i n+1）位置插入一个新元素时，需要从后向前依次后移（ ）个元素。

A. n-I B. n-i+1 C. n-i-1 D. i 答案: B

2. 在一个长度为n的顺序存储的线性表中，删除第i个元素（1 i n）时，需要从前向后依次前移（ ）个元素。 A. n-I B. n-i+1 C. n-i-1 D. i 答案: A

3. 在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（ ）。

A. HL=p;p->next=HL; B. p->next=HL;HL=p; C. p->next=HL;p=HL; D. p->next=HL->next;HL->next=p; 答案: B

4. 在一个单链表HL中，若要在指针q所指向结点的后面插入一个由指针p所指向的结点，则执行（ ）。 A. q->next=p->next;p->next=q; B. p->next=q->next;q=p; C. q->next=p->next;q->next=p; D. p->next=q->next;q->next=p; 答案: D

5. 在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行（ ）。 A. p=q->next;p->next=q->next; B. p=q->next;q->next=p;

C. p=q->next;q->next=p->next;

D. q->next=q->next->next;q->next=q; 答案: C

二、填空题（共有题目11题,共计50.0分）

1. 线性表是具有________的数据元素的一个________。 答案: 相同属性 有限序列;序列;

2. 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为________，在表尾插入元素的时间复杂度为________。

答案: o(n);O(n);O（n）;线性阶 o(1);O(1);O（1）;常数阶;

3. 在线性表的顺序存储结构中，若一个元素的下标为i，则它的前驱元素的下标为________，后继元素的下标为________。 答案: i-1;I-1 i+1;I+1;

4. 在线性表的单链接存储结构中，每个结点包含有两个域，一个叫________，另一个叫________域。 答案: 值;数据;指针 指针;数据;

5. 对于一个单链接存储的线性表，在表头插入结点的时间复杂度为________，在表尾插入元素的时间复杂度为________。

答案: o(1);O(1);O（1）;常数阶 o(n);O(n);O（n）;O（N）;线性阶;

6. 在线性表的单链接存储结构（结点）中，若一个元素所在结点的地址为p，则其后继结点的地址为________，后继结点的值为________。 答案: p->next;P->next;P->NEXT p->next->data;P->NEXT->DATA;

7. 在线性表的单链接存储结构（结点）中，若一个元素所在结点的地址为p，p为一个数组a中的下标，则其后继结点的一标为________。 答案: a[p].next;

8. 在循环单链表中，最后一个结点的指针域指向________结点。

1

答案: 表头;头;表头附加结点;第一个;

9. 在双向链表中，每个结点包含两个指针域，一个指向其________结点，另一个指向其________结点。 答案: 前驱;双亲;父;父亲;后继 后继;孩子;前驱;

10. 在循环双向链表中表头结点的左指针域指向________结点，最后一个结点的右指针域指向________结点。 答案: 表尾;尾

表头;头;表头附加结点;

11. 在以HL为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为________和________。

答案: HL->next==NULL;HL->next==null HL->next==HL;

一、单选题（共有题目3题,共计3.0分）

1. 从堆中删除一个元素的时间复杂度为（ ）。 A. O(1) B. O(n) C. O(Log2n) D. O(nLog2n) 答案: C

2. 向堆中插入一个元素的时间复杂度是（ ）。 A. O(1) B. O(Log2n) C. O(n) D. O(nLog2n) 答案: B

1. 利用n个值作为叶子结点的权生成的哈夫曼树中共包含（ ）结点。 A. n B. n+1 C. 2n D. 2n-1 答案: D

2. 利用n个值作为叶子结点的权生成的哈夫曼树中共包含（ ）个双分支结点。 A. n B. n-1 C. n+1 D. 2n-1 答案: B

3. 利用3、6、8、12为4个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为（ ）。

A. 18 B. 16 C. 12 D. 30 答案: A

1. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(Log2n) D. O(n 2) 答案: C

2. 向二叉搜索树中插入一个元素时，其时间复杂度大致为（ ）。 A. O（1） B. O（Log2n) C. O(n) D. O(nLog2n) 答案: B

3. 根据n个元素建立一棵二叉搜索树时，其时间复杂度大致为（ ）。 A. O（n) B. O(Log2n) C. O(n 2) D. O(nLog2n) 答案: D

二、填空题（共有题目5题,共计4.0分） 1. 堆是一棵________二叉树。 答案: 完全;

2. 在一个小根堆中，堆顶结点的值是所有结点中的________；在一个大根堆中，堆顶结点的值是所有结点中的________。

答案: 最小值 最大值;

3. 堆的存储结构适宜采用________，这样能够充分利用存储空间。 答案: 顺序存储;

4. 在一个堆的顺序存储结构中，堆中结点的编号是从________开始的，若一个元素的下标为i，则它的左孩子元素的下标是________，右孩子元素的下标是________。

2

答案: 0 2i+1 2i+2;

5. 当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层________调整，直到被调整到________位置为止。

答案: 向上 堆顶;

6. 在一个堆中，除编号为0的堆顶结点外，对于其他编号为i的结点，其双亲结点的编号为________。 答案: (i-1)/2;

7. 当从一个小根堆中删除一个元素时，需要把________元素填补到________位置，然后再按条件把它逐层________调整。

答案: 堆尾 堆顶 向下;

8. 若有两棵树T 1和T 2均为小根堆，当以它们作为一棵树T的左、右子树，并用一个比这两棵子树的根都小的值作为整个树T的根结点，则树T是一个________。 答案:;小根堆;

1. 在一棵树中，两个结点之间如果有路径的话，路径的个数是________的。 答案: 唯一;

2. 在一棵树中，结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的________。 答案: 乘积;

3. 在任何一棵哈夫曼树中，单支结点的个数为________。 答案: 0;

4. 不管一棵哈夫曼树中有偶数或奇数个叶子结点，则树中总结点的个数必为________个。 答案: 奇数;

5. 有7个带权结点，其权值分别为3、7、8、2、6、10、14，若依它们为叶子结点构造一棵哈夫曼树，给出其广义表，并计算出其带权路径长度WPL＝________。 答案: 131;

1.二叉搜索树又名________。 答案: 二叉排序树;

2.在一棵非空的二叉搜索树中，以每个分支结点为根的子树都是一棵________。 答案: 二叉搜索树;

3.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个________。 答案: 有序序列;

4.在一棵二叉搜索树中，其左子树上结点的关键字值________根结点的关键字值。 :小于;

5.在一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明________；若元素的值小于根结点的值，则继续向________查找；若元素的值大于根结点的值，则继续向________查找。 答案: 查找成功 左子树 右子树;

三、程序填空题（共有题目1题,共计3.0分）

1. 下面是在一棵二叉搜索树上进行查找的非递归算法，请根据程序填空： ElemType *Find1(struct BTreeNode *BST,ElemType x) {

while( BST!=NULL) {

if(________) return &(BST->data); else if( xdata) ________; else BST=BST->right; }

________; }

3

答案: x==BST->data BST=BST->left return NULL;

一、单选题（共有题目18题,共计54.0分）

1. 在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为（ ）。 A. s B. s-1 C. s+1 D. n 答案: A

2. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为（ ）。 A. s B. s-1 C. s+1 D. 2s 答案: D

3. 在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为（ ）。 A. n B. e C. n+e D. 2e 答案: D

4. 在一个具有n个顶点的无向完全图中，所含的边数为（ ）。 A. n B. n(n-1) C. n(n-1)/2 D. n(n+1)/2 答案: C

5. 在一个具有n个顶点的有向完全图中，所含的边数为（ ）。 A. n B. n(n-1) C. n(n-1)/2 D. n(n+1)/2 答案: B

6. 在一个无权图中，若两顶点之间的路径长度为k，则该路径上的顶点数为（ ）。 A. k B. k+1 C. k+2 D. 2k 答案: B

7. 对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为（ ）。 A. 0 B. 1 C. n D. n-1 答案: B

8. 若要把n个顶点连接为一个连通图，则至少需要（ ）条边。 A. n B. n+1 C. n-1 D. 2n 答案: C

9. 若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用（ ）次深度优先搜索遍历的算法。

A. 1 B. k-1 C. k D. k+1 答案: C

10. 在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（ ）。 A. n B. e C. n*e D. 2e 答案: D

11. 在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素的个数为（ ）。 A. n B. e C. n*e D. 2e 答案: B

12. 在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为（ ）。 A. n B. e C. n*e D. 2e 答案: D

13. 若一个图的边集为{（A，B），（A，C），（B，D），（C，F），（D，E），（D，F）}，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为（ ）。 A. A，B，C，F，D，E B. A，C，F，D，E，B C. A，B，D，C，F，E D. A，B，D，F，E，C

4

答案: B

14. 若一个图的边集为{（A，B），（A，C），（B，D），（C，F），（D，E），（D，F）}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为（ ）。 A. A，B，C，D，E，F B. A，B，D，E，F，C C. A，B，D，C，E，F D. A，C，B，F，D，E 答案: D

15. 由一个具有n个顶点的连通图生成的最小生成树中，具有（ ）条边。 A. n B. n-1 C. n+1 D. 2n 答案: B

16. 已知一个无向图的边集为{(0,1)3,(0,2)5,(0,3)6,(1,4)10,(2,3)2,(2,4)9,(3,4)8}，则该图的最小生成树的边集为（ ）。

A. {(0,1)3,(0,2)5,(0,3)6,(3,4)8} B. {(0,1)3,(0,2)5,(0,3)6,(2,3)2} C. {(2,3)2,(0,2)5,(3,4)8,(0,3)6} D. {(2,3)2,(0,2)5,(3,4)8,(0,1)3} 答案: D

17. 已知一个无向图的边集为{(0,1)3,(0,2)4,(0,3)8,(1,4)10,(2,3)2,(2,4)12,(3,4)8}，则利用普里姆算法从顶点0出发求其最小生成树的过程中，得到的第３条边是（ ）。 A. (0,1)3 B. (0,2)4 C. (2,3)2 D. (3,4)5 答案: C

18. 已知一个无向图的边集为{(0,1)3,(0,2)4,(0,3)8,(1,4)10,(2,3)2,(2,4)12,(3,4)5}，则利用克鲁斯卡尔算法求其最小生成树的过程中，得到的第３条边是（ ）。 A. (0,1)3 B. (0,2)4 C. (2,3)2 D. (3,4)5 答案: B

二、填空题（共有题目13题,共计46.0分）

1. 在一个图中，所有顶点的度数之和等于所有边数的________倍。 答案: 2;

2. 在一个具有n个顶点的无向完全图中，包含有________条边。 答案: n(n-1)/2;

3. 在一个具有n个顶点的有向完全图中，包含有________条边。 答案: n(n-1);

4. 已知一个连通图的边集为{(1,2)3,(1,3)6,(1,4)8,(2,3)4,(2,5)10,(3,5)12,(4,5)2}，则度为3的顶点个数有________个。 答案: 4;

5. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要________条边。 答案: n-1;

6. 一个连通图中存在着________个连通分量。 答案: 1;

7. 若一个图的顶点集为{a,b,c,d,e,f}，边集为{(a,b),(a,c),(b,c),(d,e)}，则该图含有________个连通分量。 答案: 3;

8. 一个图的边集为{(a,c),(a,e),(b,e),(c,d),(d,e)},从顶点a出发进行深度优先搜索遍历得到的顶点序列为________，从顶点a出发进行广度优先搜索遍历得到的顶点序列为________。 答案: a,c,d,e,b;a,e,b,d,c;a,e,d,c,b;a，c，d，e，b a,c,e,d,b;a,e,c,b,d;a,e,c,d,b;

9. 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为________和________。 答案: n;N n-1;N-1;

5

三、程序填空题（共有题目1题）

1. 下面函数的功能是返回二叉树BT中值为X的结点所在的层号，请完成相应的程序。 int NodeLevel(BTreeNode *BT, ElemType X) {

if(BT==NULL) return 0;

else if(BT->data==X) return 1; else {

int c1=NodeLevel(BT->left,x) if (c1>=1) ________; int c2=________; if________; return 0; } }

答案：return c1+1 NodeLevel(BT->right,X) (c2>=1) return c2+1;

一、单选题（共有题目5题,共计50.0分） 1. 下面程序段的时间复杂度是（ ）。 for( int i=0;i

A. O(m 2) B. O(n 2) C. O(m*n) D. O(m+n) 答案: C

2. 执行下面程序段时，执行S语句的次数为（ ）。 for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) S;

A. n 2 B. n 2/2 C. n(n+1) D. n(n+1)/2 答案: D

3. 下面算法的时间复杂度为（ ）。 int f(unsigned int n) {

if(n==0||n==1) return 1; else

return n*f(n-1); }

A. O(n) B. O(1) C. O(n 2) D. O(n!) 答案: A

4. 从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为（ A. O(1) B. O(n) C. O(n 2) D. O(n!) 答案: B

5. 输出一个二维数组b[m][n]中所有元素值的时间复杂度为（ ）。A. O(m+n) B. O(m*n) C. O(m 2) D. O(n 2) 答案: B

二、填空题（共有题目10题,共计30.0分）

。 11

） 1. ________是一个数据整体中相对独立的单位。 答案: 数据元素;元素;

2. ________是数据处理领域组织数据的基本单位。 答案: 记录;数据记录;

3. 数据的逻辑结构被分为________、________、________、________4种。 答案: 集合结构 线性结构 树形结构

图形结构;网状结构;图;

4. 数据的物理结构又名________，它主要有________、________、________和________4种方式。 答案: 存储结构 顺序;顺序存储 链接;链接存储 索引 散列;

5. 在线性结构中，前驱结点和后继结点之间存在着________的联系。 答案: 1对1;1：1;

6. 在树形结构中，前驱和后继结点之间存在着________联系。 答案: 1对多;1：m;

7. 在图形结构中，前驱和后继结点之间存在着________的联系。 答案: 多对多;m：n;

8. 算法应具备________、确定性、________、输入和输出五个特性。 答案: 有穷性 可行性;

9. 对算法评价一般从正确性、________、可读性、简单性、________、________六个方面进行的。 答案: 健壮性 时间复杂度 空间复杂度;

10. 在下面程序段中，s=s+p语句的执行次数是________，p*=j语句的执行次数是________，该程序段的时间复杂度为________。 int i=0,s=0; while(++i<=n) {

int p=1;

for( int j=1;j<=i;j++) p*=j; s=s+p; }

答案: n n(n+1)/2

O(n 2);平方阶;

三、问答题（共有题目5题,共计20.0分）

1. 下面程序段的功能是什么？求出其时间复杂度。 int Prime(int n) {

int i=2;

int x=(int)sqrt(n); while(i<=x)

12

{

if(n%i==0) break; i++; }

if(i>x) return 1; else return 0; }

答案:

判断n是否是一个素数，若是则返回数值1，否则返回0。 该算法的时间复杂度为O( )。

2. 分析下面程序段的功能，并求出其时间复杂度。 int sum1(int n) {

int p=1,s=0;

for(int i=1;i<=n;i++) {

p*=i; s+=p; }

return s; }

答案: 计算 的值。时间复杂度是O(n)。

3. 分析下面程序段的功能，并求出其时间复杂度。 int sum2(int n) {

int s=0;

for(int i=1;i<=n;i++) {

int p=1;

for(int j=1;j<=i;j++) p*=j; s+=p; }

return s; }

答案: 计算 的值，其时间复杂度为O(n 2)。

4. 分析下面程序段的功能，并求出其时间复杂度。 int fun(int n) {

int i=1,s=1; while(s

求出满足不等式1+2+3+......+i n的最小i值。其时间复杂度为O( )。5. 分析下面程序段的功能，并求出其时间复杂度。

13

void reverse(char *p) {

int n=strlen(p);

for(int i=0;i

char ch; ch=p[i];

p[i]=p[n-i-1]; p[n-i-1]=ch; } }

答案: 其功能是将一个字符串中的所有字符按相反的次序重新放置。时间复杂度是O(n)。

三、问答题（共有题目1题,共计10.0分） 1. 简要说明算法与程序的区别？

答案: 算法通常用高级语言来描述，但和高级语言有一定的区别；

算法着重于思想的描述，可能会省略很多细节，因而算法需要进行适当的修改才能变成程序在机器上实现，算法必须满足5个特征，但程序未必能满足有穷性。

一、单选题（共有题目7题,共计70.0分） 1.

对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找任一元素的平均查找长度为（ ）。 A. 5.5 B. 5 C. 39/8 D. 19/4

2. 对长度为3的顺序表进行查找，若查找第1个元素的概率为1/2，查找第2个元素的概率为1/3，查找第3个元素的概率为1/6，则查找任一元素的平均查找长度为（ ）。

A. 5/3 B. 2 C. 7/3 D. 4/3

3. 对于长度为n的顺序存储的有序表，若采用二分查找，则对所有元素的最长查找长度为（ ）的值的向上取整。

A. log2 (n+1) B. log 2 n C. n/2 D. (n+1)/2

4. 对于长度为n的顺序存储的有序表，若采用二分查找，则对所有元素的最长查找长度为（ ）的值的向下取整加1。

A. log 2 (n+1) B. log 2 n C. n/2 D. (n+1)/2 5. 对于长度为9的顺序存储的有序表，若采用二分查找，在等概率情况下的平均查找长度为（ ）的值除以9。 A. 20 B. 18 C. 25 D. 22

6. 对于长度为18的顺序存储的有序表，若采用二分查找，则查找第15个元素的查找长度为（ ）。

A. 3 B. 4 C. 5 D. 6

7. 对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用二分查找，则查找元素26的查找长度为（ ）。 A. 2 B. 3 C. 4 D. 5

二、填空题（共有题目3题,共计30.0分）

1. 以顺序查找方法从长度为n的顺序表中查找一个元素时，平均查找长度为 ，时间复杂度为 。 2. 以二分查找方法从长度为12的有序表中查找一个元素时，平均查找长度为 。 3. 对于二分查找所对应的判定树，它既是一棵 ，又是一棵 。

一、单选题（共有题目3题,共计60.0分）

14

1.

若对n个元素进行直接插入排序，在进行第 i 趟（1in-1）排序时，为寻找插入位置最多需要进行（ ）次元素的比较。

A. i+1 B. i-1 C. i D. 1

2. 若对n个元素进行直接插入排序，在进行任一趟排序的过程中，为寻找插入位置而需要的时间复杂度为（ ）。 A. O(1) B. O(n) C. O(n 2) D. O(log 2 n)

3. 在对n个元素进行直接选择排序的过程中，需要进行（ ）趟选择和交换。 A. n+1 B. n C. n-1 D. n/2

二、填空题（共有题目2题,共计40.0分）

1. 每次从无序表中取一个元素，把它插入到有序表中的适当位置，此种排序方法叫做 排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做 排序。

2. 在直接选择排序中，记录比较次数的时间复杂度为 ，记录移动次数的时间复杂度为 。O(n 2)

作业标题：第3章 复习题2得分：100.0（总分：100.0）

一、单选题（共有题目3题,共计30.0分） 1.

设一个具有t个非零元素的m*n大小的稀疏矩阵采用顺序存储，求其转置矩阵的普通转置算法的时间复杂度为（ ）。

A. O(m) B. O(n) C. O(n+t) D. O(n*t)标准答案: D

2. 广义表( )的表头是( )。

A. ( ) B. 没有表头 C. (( )) D. 0标准答案: B

3. 广义表( )的表尾是( )。

A. 没有表尾 B. ( ) C. ( ( ) ) D. 0标准答案: A

二、填空题（共有题目7题,共计70.0分） 1.

在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为________域和________域。

你的答案: 值 指针

标准答案: 值;子表指针;指针 子表指针;指针;值; 2.

广义表（( )）的表头是________。

你的答案: 空表

标准答案: ();空表; 3.

广义表( ( ) )的表尾是________。 你的答案: 空表

15

标准答案: ();空表;

4. (( ),(e),(a,(b,c,d)))的表头是________。 你的答案: ()

标准答案: ();空表;

5. (( ),(e),(a,(b,c,d)))的表尾是________。 你的答案: ((e),(a,(b,c,d))) 标准答案: ((e),(a,(b,c,d)));

6. 广义表((e),(a,(b,c,d)))的长度是________。 标准答案: 2;

7. 广义表((e),(a,(b,c,d)))的深度是________。 标准答案: 3;

一、单选题（共有题目7题,共计70.0分） 1.

对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找任一元素的平均查找长度为（ ）。 A. 5.5 B. 5 C. 39/8 D. 19/4

2. 对长度为3的顺序表进行查找，若查找第1个元素的概率为1/2，查找第2个元素的概率为1/3，查找第3个元素的概率为1/6，则查找任一元素的平均查找长度为（ ）。

A. 5/3 B. 2 C. 7/3 D. 4/3

3. 对于长度为n的顺序存储的有序表，若采用二分查找，则对所有元素的最长查找长度为（ ）的值的向上取整。

A. log2 (n+1) B. log 2 n C. n/2 D. (n+1)/2

4. 对于长度为n的顺序存储的有序表，若采用二分查找，则对所有元素的最长查找长度为（ ）的值的向下取整加1。

A. log 2 (n+1) B. log 2 n C. n/2 D. (n+1)/2 5. 对于长度为9的顺序存储的有序表，若采用二分查找，在等概率情况下的平均查找长度为（ ）的值除以9。 A. 20 B. 18 C. 25 D. 22

6. 对于长度为18的顺序存储的有序表，若采用二分查找，则查找第15个元素的查找长度为（ ）。

A. 3 B. 4 C. 5 D. 6

7. 对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用二分查找，则查找元素26的查找长度为（ ）。 A. 2 B. 3 C. 4 D. 5

二、填空题（共有题目3题,共计30.0分）

1. 以顺序查找方法从长度为n的顺序表中查找一个元素时，平均查找长度为 ，时间复杂度为 。 2. 以二分查找方法从长度为12的有序表中查找一个元素时，平均查找长度为 。 3. 对于二分查找所对应的判定树，它既是一棵 ，又是一棵 。

一、单选题（共有题目3题,共计60.0分） 1.

若对n个元素进行直接插入排序，在进行第 i 趟（1in-1）排序时，为寻找插入位置最多需要进行（ ）次元素的比较。

A. i+1 B. i-1 C. i D. 1

2. 若对n个元素进行直接插入排序，在进行任一趟排序的过程中，为寻找插入位置而需要的时间复杂度为（ ）。 A. O(1) B. O(n) C. O(n 2) D. O(log 2 n)

3. 在对n个元素进行直接选择排序的过程中，需要进行（ ）趟选择和交换。 A. n+1 B. n C. n-1 D. n/2

16

二、填空题（共有题目2题,共计40.0分）

1. 每次从无序表中取一个元素，把它插入到有序表中的适当位置，此种排序方法叫做 排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做 排序。

2. 在直接选择排序中，记录比较次数的时间复杂度为 ，记录移动次数的时间复杂度为 。O(n 2)

一、单选题（共有题目9题,共计54.0分） 1.

栈的插入和删除操作在（ ）进行。 A. 栈顶 B. 栈底 C.

任意位置 D.

指定位置 你的答案: A 标准答案: A 该题分数:6.0 你的得分:6.0 解答过程： 2.

一个链栈的栈顶指针用top表示，当p所指向的结点进栈时，执行的操作为（ A.

p->next =top; top=top->next; B.

top=p; p->next=top; C.

p->next=top->next;top->next=p; D.

p->next=top;top=p; 你的答案: D 标准答案: D 该题分数:6.0 你的得分:6.0 解答过程： 3.

一个链栈的栈顶指针用top表示，当进行退栈时所进行的指针操作为（ ）。 A.

。 17

）top->next=top; B.

top=top->data; C.

top=top->next; D.

top->next=top->next->next; 你的答案: C 标准答案: C 该题分数:6.0 你的得分:6.0 解答过程： 4.

若让元素1、2、3依次进栈，则出栈次序不可能出现（ ）情况。 A.

3，2，1 B.

2，1，3 C.

3，1，2 D.

1，3，2

你的答案: C 标准答案: C 该题分数:6.0 你的得分:6.0 解答过程： 5.

在一个顺序队列中，队首指针指向队首元素的（ ）位置。 A. 前一个 B. 后一个 C. 当前 D. 后面

18

你的答案: A 标准答案: A 该题分数:6.0 你的得分:6.0 解答过程： 6.

当利用大小为N的数组顺序存储一个队列时，若没设有队列长度的变量，则该队列的最大长度为（ ）。 A. N－2 B. N－1 C. N D. N＋1

你的答案: B 标准答案: B 该题分数:6.0 你的得分:6.0 解答过程： 7.

从一个顺序队列删除元素时，首先需要（ ）。 A.

队首指针循环加1 B.

队首指针循环减1 C.

取出队首指针所指位置上的元素 D.

取出队尾指针所指位置上的元素 你的答案: A 标准答案: A 该题分数:6.0 你的得分:6.0 解答过程： 8.

假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件为( A.

front==rear

)。 19

B.

front!=NULL C.

rear!=NULL D.

front==NULL 你的答案: D 标准答案: D 该题分数:6.0 你的得分:6.0 解答过程： 9.

假定利用数组a[N]循环顺序存储一个队列，用f和r分别表示队首和队尾指针，并已知队未空，当进行出队并返回队首元素时所执行的操作为( )。 A.

return a[++r%N]; B.

return a[--r%N]; C.

return a[++f%N]; D.

return a[f++%N]; 你的答案: C 标准答案: C 该题分数:6.0 你的得分:6.0 解答过程：

二、填空题（共有题目7题,共计46.0分） 1.

队列的插入操作在________进行，删除操作在________进行。 你的答案: 队尾 队首

标准答案: 队尾 队首;

该题分数:6.57 你的得分:6.57 解答过程： 2.

栈又称为________表，队列又称为________表。 标准答案: 后进先出 先进先出;

20

本文来源：https://www.bwwdw.com/article/ytn8.html