铜仁学院数据结构期末考试题汇总（王军）

45空串是___零个字符的串______ 46空串长度等于____零______ 。

47空白串是_____由一个或多个空格字符组成的串

空白串长度等于______包含的空格个数 ____________

模式串t=‘abaabcac”的next函数值序列为__01122312

模式串t=‘abaabcac”的nextval函数值序列为____-1，0，-1，1，0，2，A.1/2 B.1 C.2 D.4

关键路径是事件结点网络中 _______A__________ 。 A. 从源点到汇点的最长路径 B.最长的回路

C.从源点到汇点的最短路径 D.最短的回路 -1，1 __

由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法 错误。

某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是 D

A.空或只有一个结点 B. 完全二叉树 C.二叉排序树

D.高度等于其节点数

深度为5的二叉树至多有 C个结点 A.16 B.32 C.31 D.10

根据使用频率为5个字符设计的哈夫曼编码不可能是 c A.111，110，10，01，00 B.000，001，010，011，1 C.100，11，10，1，0 D.001，000，01，11，10

树和二叉树的主要差别1是 树中结点的最大度数没有限制，而二叉树结点的最大度数为2

树和二叉树的主要差别2是

树的结点无左、右之分，而二叉树的结点有左、右之分

深度为k的完全二叉树至少有 _ 2的K-1次方_____ 个结点

深度为k的完全二叉树至多有 ：（2的k次方）-1 个结点，

深度为k的完全二叉树若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是______（2的k-1次方）___。

一棵二叉树的第i(i>=1)层最多有 2的i-1次方______个结点

一棵有n（n>0）个结点的满二叉树共有___ 2的logn次方__________ 个叶子结点

一棵有n（n>0）个结点的满二叉树共有____（n-1）/2_________ 个非叶子结点。 9

一个n个顶点的无向图最多有_______C__________条边。 A.n B.n(n-1) C.n(n-1)/2 D. 2n

在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 ___B_______ 倍。

下面不正确的说法是 _______B__________ 。

A、 关键活动不按期完成就会影响整个工程的完成时间 B、任何一个关键活动提前完成，将使整个工程提前完成 C、所有关键活动都提前，则整个工程提前完成

D、某些关键活动若提前完成，将使整个工程提前完成。

一个图的___邻接矩阵___________ 表示法是惟一的 一个图的____邻接表___________表示法是不惟一的

在有n个顶点的有向图中，每个顶点的度最大可达_2(n-1) ___

十二章

采用顺序查找法查找长度为n的线性表时，每个元素的平均查找长度为_____C______ A.n B.n/2 C.(n+1)/2 D.(n-1)/2

在一个长度为12的有序表，按折半查找法对改表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为______B__________

A.35/12 B.37/12 C.39/12 D.43/12

查找效率最高的二叉排序树是 _________C____

A. 所有结点的左子树都为空的二叉排序树 B.所有结点的右子树都为空的二叉排序树 C.平衡二叉树

D.没有左子树的二叉排序树

以下说法错误的是______B__________ 。

A、 散列法存储的基本思想是由关键码值决定数据的存储地址 B、散列表的结点中只包含数据元素自身的信息，不包含任何指针 C、装填因子是散列法的一个重要参数，它反映了散列表的装填程度 D、散列表的查找效率主要取决于散列表造表时选取的散列函数何处理冲突的方法

散列表的平均查找长度_________A____________ 。 A与处理冲突方法有关与表长无关

B、与处理冲突方法无关与表的长度有关 C、与处理冲突方法有关且与表的长度有关 D、与处理冲突方法无关且与表的长度无关

设线性表（a1，a2，?，a500）元素的值由小到大排列，对一个给定的k值用折半法查找线性表，在查找不成功的情况下至多需比较__________9______ 次。

一个无序序列可以通过构造一棵___二叉排序__________树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程

在散列存储中，装填因子a的值越大，则存取元素时___发生冲突的可能性就越大_

在散列存储中，装填因子a的值越小，则存取元素时___发生冲突的可能性就越小__

十五章

排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为__C_________ A. 希尔排序 B.冒泡排序 C.插入排序 D.选择排序

在文件“局部有序”或文件长度较小的情况下，最佳内排序方法是______C________ A. 直接插入排序 B.冒泡排序 C.直接选择排序 D.归并排序

对给出的一组关键字{14，5，19，20，11，19}。若按关键字非递减排序，第一趟排序结果为{14，5，19，20，11，19}，问采用的排序算法是____C_______

A. 简单选择排序 B.快速排序 C.希尔排序

D.二路归并排序

在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是_______ D____

A. 希尔排序 B.冒泡排序 C.插入排序 D.选择排序

在对一组记录{54，38，96，23，15，72，60，45，83}进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 _______ 5 ______ 次。

每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做______交换___________ 排序；

每次使两个相邻的有序表合并成一个有序表的排序方法叫做 __二路归并_________ 排序

____快速____________ 排序方法采用的是二分法的思想

_____堆______ 排序方法其数据的组织采用完全二叉树结构。 A

若某线性表的常用操作是取第i个元素及其前趋元素，则采用______存储方式最节省时间。

A.顺序表 B.单链表 C.双链表 D.单向循环 B

串是任意有限个______。

A.符号构成的序列 B.字符构成的序列 C.符号构成的集合 D.字符构成的集合 D

如果以链表作为栈的存储结构,则退栈操作时_______。 A.必须判别栈是否满干 B.对栈不作任何判别 C.判别栈元素的类型 D.必须判别栈是否空 A

设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为_______。

A.front=(front+1)%(m+1) B.front=(front+1)% m C.rear=(rear+1)% m D.front=front+1 B

深度为6(根的层次为1)的二叉树至多有_______结点 A.64 B.63 C.31 D.32 C

将含100个结点的完全二叉树从根这一层开始，每层从左至右依次对结点编号，根结点的编号为1。编号为47的结点X的双亲的编号为_______。

A.24 B.25 C.23 D.2无法确定 D

设有一个无向图G=(V,E)和G'=(V',E')，如果G'为G的生成树，则下面不正确的说法是_______。

A.G'为G的子图 B.G'为G的一个无环子图 C.G'为G的极小连通子图且V'=V D.G'为G的连通分量 D

用线性探测法查找闭散列上，可能要探测多个散列地址，这些位置上的键值_______。

A.一定都是同义词 B.一定都不是同义词 C.都相同 D.不一定都是同义词 C

二分查找要求被查找的表是_______。

A.键值有序的链接表 B.链接表但键值不一定有序表 C.键值有序的顺序表 D.顺序表但键值不一定有序表 B

当初始序列（共n个元素）已经按键值有序，用直接插入法对其进行排序，需要比较的次数为_______。

A. n2 B. n-1 C. log2n D. nlog2n C

算法分析的目的是_______。

A.找出数据结构的合理性 B.研究算法中的输入/输出关系 C.分析算法的效率以求改进 D.分析算法的易读性 B

需要经常查找结点的前驱与后继的场合中，使用_______比较合适。 A.单链表 B.双向链表 C.链表 D.循环链表

D

下面关于线性表的叙述中，错误的是_______。 A.顺序表使用一维数组实现的线性表 B.顺序表必须占用一片连续的存储单元

C.顺序表的空间利用率高于链表 D.在链表中，每个结点只有一个链域 B

带头结点的单链表head为空的判断条件是_______。

A. head==NULL B. head->next==NULL C. head->next==head D. head!=NULL A

队列通常采用两种存储结构是( )

A.顺序存储结构和链表存储结构 B.散列方式和索引方式

C.链表存储结构和数组 D.线性存储结构和非线性存储结构 C

深度为5的二叉树至多有( )个结点。

A.16 B.32 C.31 D.10 A

对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组的大小为 ( )

A.n B.n+1 C.n-1 D.n+边数 C

在一个具有n个顶点的无向图中，要连通全部顶点至少需要( )条边。

A.n B.n+1 C.n-1 D.n/2 B

静态查找表与动态查找表二者的根本差别在于( ) A.它们的逻辑结构不一样 B.施加在其上的操作不同

C.所包含的数据元素的类型不一样 D.存储实现不一样 A

散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。因为散列函数不是一对一的关系，所以选择好的( )方法是散列文件的关键。

A.散列函数 B.除余法中的质数

C.冲突处理 D.散列函数和冲突处理 C

对于大文件的排序要研究在外设上的排序技术，即( ) A.快速排序法 B.内排序法 C.外排序法 D.交叉排序法 C

设有5000个无序的元素，希望用最快的速度挑选出其中前50个最大的元素，最好选用( )法。

A.冒泡排序 B.快速排序 C.堆排序 D.基数排序 D

算法指的是（ ）

A.计算机程序 B.解决问题的计算方法 C.排序算法 D.解决问题的有限运算序列 B

线性表采用链式存储时，结点的存储地址（ ）

A.必须是不连续的 B.连续与否均可 C.必须是连续的 D.和头结点的存储地址相连续 C

将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ）

A．O（1） B．O（n） C．O（m） D．O（m+n） D

设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ）

A．front=front+1 B．front=(front+1)%(m-1) C．front=(front-1)%m D．front=(front+1)%m A

如下陈述中正确的是（ ）

A．串是一种特殊的线性表 B．串的长度必须大于零 C．串中元素只能是字母 D．空串就是空白串 C

若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（ ）

A．O（ ） B．O（n） C．O（n2） D．O（n3） C

在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( )

A．4 B．5 C．6 D．7 D

在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( ) A．e B．2e C．n2－e D．n2－2e C

假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是( )

A．O(n) B．O(e) C．O(n+e) D．O(n*e)

1、在数据结构的讨论中把数据结构从逻辑上分为 （C ）

A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。

2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ） A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续

3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。 A n B n/2 C (n-1)/2 D (n+1)/2

4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。 A s→link = p→link; p→link = s; B p→link = s; s→link = q;

C p→link = s→link; s→link = p; D q→link = s; s→link = p;

5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。

A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序

6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。 A 求子串 B 模式匹配 C 串替换 D 串连接

7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1

C rear=rear->link->link; delete rear; 到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空

D s=rear->link->link; rear->link->link=s->link; delete s; 间中，则存放该数组至少需要的存储字数是（ C ）。

A 80 B 100 C 240 D 22、设单循环链表中结点的结构为（data,link）,且first为指向链表表头270 的指针，current为链表当前指针，在循环链表中检测current是否达到8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 链表表尾的语句是( D )。

A current->link =null B first->link=current A 栈 B 队列 C 循环队列

C first=current D current->link=first D 优先队列

9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。 23、一个栈的入栈序列为a，b，c，则出栈序列不可能的是( C )。

10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针

分别为front和rear，则当前队列中的元素个数是（ D ）。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与（ A ）的表示等价。 A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。 A 指针 B 引用 C 值 D

变量

13、下面程序段的时间复杂度为（ C ） for (int i=0;i

int f(unsigned int n) { if(n= =0 || n= =1) return 1; else return n*f(n-1); } A O(1) B O(n) C O(n2) D O(n !) 15、线性表若是采用链式存储结构时，要求内存中可用存储单元的地址

( D )。 A 必须是连续的

B 部分地址必须是连续的

C 一定是不连续的

D 连续或不连续都可以

16、数据结构的定义为(D，S)，其中D是( B )的集合。

A 算法 B数据元素 C 数据操作 D 逻辑

结构 17、算法分析的目的是( A )。 A 找出数据结构的合理性

B 研究算法中输入和输出的关系

C 分析算法的效率以求改进

D 分析算法的易懂性和文档性

18、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行( B )。

A s->link=p;p->link=s; B s->link=p->link;p->link=s; C s->link=p->link;p=s; D p->link=s;s->link=p; 19、设单链表中结点结构为(data,link).已知指针q所指结点是指针p所指结点的直接前驱，若在*q 与*p之间插入结点*s，则应执行下列哪一个操作（ B ） A s->link=p->link; p->link=s; B q->link=s; s->link=p C p->link=s->link; s->link=p; D p->link=s; s->link=q; 20、设单链表中结点结构为(data,link).若想摘除结点*p的直接后继，则

应执行下列哪一个操作（ A ）

A p->link=p->link->link; B p=p->link; p->link=p->link->link; C p->link=p->link; D p=p->link->link; 21、设单循环链表中结点的结构为（data,link）,且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作（ D ） A s=rear; rear=rear->link; delete s; B rear=rear->link; delete rear; A c,b,a B b,a,c C c,a,b D a,c,b 24、栈的数组表示中，top为栈顶指针，栈空的条件是( A )。 A top=0 B top=maxSize C top=maxSize D top=-1 25、栈和队列的共同特点是( C )。 A 都是先进后出 B 都是先进先出 C 只允许在端点处插入和删除 D 没有共同点 26、假定一个顺序存储的循环队列的队头和队尾指针分别为f和r ,则判断队空的条件为( D ).

A f+1= =r B r+1= =f C f= =0 D f= =r 27、当利用大小为n 的数组顺序存储一个队列时，该队列的最大长度为（ B ） A n-2 B n-1 C n D n+1 28、当利用大小为n 的数组顺序存储一个栈时，假定用top= =n 表示栈空，则向这个栈插入一个元素时，首先应执行（ ）语句修改top指针。

A top++; B top--; C top=0; D top; 29、设链式栈中结点的结构为（data, link）,且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列（ A ）操作。 A x=top->data; top=top->link; B top=top->link; x=top->data;

C x=top; top=top->link; D x=top->data; 30、设循环队列的结构是：

const int Maxsize=100; typedef int Data Type; typedef struct { Data Type data[Maxsize]; Int front, rear; } Queue; 若有一个Queue类型的队列Q，试问判断队列满的条件应是下列哪一个语句（ D ）

A Q.front= = Q.rear; B Q.front - Q.rear= = Maxsize; C Q.front + Q.rear= = Maxsize; D Q.front= = (Q.rear+1)% Maxsize; 31、设有一个递归算法如下：

int fact (int n ) { if (n<=0) return 1; else return n*fact(n-1); } 下面正确的叙述是（ B ） A 计算fact(n) 需要执行n次递归 B fact(7)=5040 C 此递归算法最多只能计算到fact(8) D 以上结论都不对 32、设有一个递归算法如下 int x (int n) { if (n<=3) return 1;

else return x(n-2)+x(n-4)+1; } 试问计算 x(x(8))时需要计算（ D ）次x函数。 A 8 次 B 9 次 C 16 次 D 18次 33、设有广义表D(a,b,D),其长度为（ B ），深度为（ A ） A ∞ B 3 C 2 D 5 34、广义表A(a),则表尾为（ C ） A a B (( ) ) C 空表 D （a） 35、下列广义表是线性表的有（ C ）