c语言数据结构

本文格式为Word版，下载可任意编辑——c语言数据结构一、单项选择题（共有题目5题,共计50.0分）

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

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

2.在一个长度为n的顺序存储的线性表中，删除第i个元素（1in）时，需要从前向后依次前移（）个元素。A.n-IB.n-i+1C.n-i-1D.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-1i+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->NEXTp->next->data;P->NEXT->DATA;

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

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

1

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

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

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

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

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

答案:HL->next==NULL;HL->next==nullHL->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.nB.n+1C.2nD.2n-1答案:D

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

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

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

1.从二叉探寻树中查找一个元素时，其时间繁杂度大致为()。A.O(n)B.O(1)C.O(Log2n)D.O(n2)答案: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(n2)D.O(nLog2n)答案:D

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

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

答案:最小值最大值;

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

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

2

答案:02i+12i+2;

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

答案:向上堆顶;

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

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

答案:堆尾堆顶向下;

8.若有两棵树T1和T2均为小根堆，当以它们作为一棵树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(structBTreeNode*BST,ElemTypex){

while(BST!=NULL){

if(________)returnelseif(xdata)________;elseBST=BST->right;}

________;}

3

答案:x==BST->dataBST=BST->leftreturnNULL;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

13.若一个图的边集为{（A，B），（A，C），（B，D），（C，F），（D，E），（D，F）}，则从顶点A开始对该图进行深度优先探寻，得到的顶点序列可能为（）。A.A，B，C，F，D，EB.A，C，F，D，E，BC.A，B，D，C，F，ED.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，FB.A，B，D，E，F，CC.A，B，D，C，E，FD.A，C，B，F，D，E答案:D

15.由一个具有n个顶点的连通图生成的最小生成树中，具有（）条边。A.nB.n-1C.n+1D.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)3B.(0,2)4C.(2,3)2D.(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)3B.(0,2)4C.(2,3)2D.(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，ba,c,e,d,b;a,e,c,b,d;a,e,c,d,b;

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

5

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

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

if(BT==NULL)return0;

elseif(BT->data==X)return1;else{

intc1=NodeLevel(BT->left,x)if(c1>=1)________;intc2=________;if________;return0;}}

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

一、单项选择题（共有题目5题,共计50.0分）1.下面程序段的时间繁杂度是（）。for(inti=0;ix)return1;elsereturn0;}

答案:

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

2.分析下面程序段的功能，并求出其时间繁杂度。intsum1(intn){

intp=1,s=0;

for(inti=1;i标准答案:();空表;

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.5B.5C.39/8D.19/4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16

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

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

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

一、单项选择题（共有题目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，1B.

2，1，3C.

3，1，2D.

1