数据机构选择题

（1）在数据结构中，从逻辑上可以把数据结构分成（ C ）。

A ．动态结构和静态结构 B ．紧凑结构和非紧凑结构

C ．线性结构和非线性结构 D ．内部结构和外部结构

（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ C ）。

A ．存储结构 B ．存储实现

C ．逻辑结构 D ．运算实现

（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ B ）。

A ．数据具有同一特点

B ．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致

C ．每个数据元素都一样

D ．数据元素所包含的数据项的个数要相等

（4）以下说法正确的是（ D ）。

A ．数据元素是数据的最小单位

B ．数据项是数据的基本单位

C ．数据结构是带有结构的各数据项的集合

D ．一些表面上很不相同的数据可以有相同的逻辑结构

（5）以下与数据的存储结构无关的术语是（ C ）。

A ．顺序队列 B. 链表 C. 有序表 D. 链栈

（6）以下数据结构中，（ A ）是非线性数据结构

A ．树 B ．字符串 C ．队 D ．栈

（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地

址是（ B ）。

A ．110 B ．108 C ．100 D ．120

（2）在n 个结点的顺序表中，算法的时间复杂度是O(1)的操作是（ A ）。

A ．访问第i 个结点（1≤i ≤n ）和求第i 个结点的直接前驱（2≤i ≤n ）

B ．在第i 个结点后插入一个新结点（1≤i ≤n ）

C ．删除第i 个结点（1≤i ≤n ）

D ．将n 个结点从小到大排序

（3） 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移

动 的元素个数为（ B ）。

A ．8 B ．63.5 C ．63 D ．7

（4）链接存储的存储结构所占存储空间（ A ）。

A ．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

B ．只有一部分，存放结点值

C ．只有一部分，存储表示结点间关系的指针

D ．分两部分，一部分存放结点值，另一部分存放结点所占单元数

（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。

A ．必须是连续的 B ．部分地址必须是连续的

C ．一定是不连续的 D ．连续或不连续都可以

（6）线性表Ｌ在（ B ）情况下适用于使用链式结构实现。

A ．需经常修改Ｌ中的结点值 Ｂ．需不断对Ｌ进行删除插入

C ．Ｌ中含有大量的结点 Ｄ．Ｌ中结点结构复杂

（7）单链表的存储密度（ C ）。

A ．大于1 B ．等于1 C ．小于1 D ．不能确定

（8）将两个各有n 个元素的有序表归并成一个有序表，其最少的比较次数是（ A ）。

A ．n B ．2n-1 C ．2n D ．n-1

（9）在一个长度为n 的顺序表中，在第i 个元素（1≤i ≤n+1）之前插入一个新元素时

须向后移动（ B ）个元素。

A ．n-i B ．n-i+1 C ．n-i-1 D ．i

(10) 线性表L=(a1，a 2, „„a n ) ，下列说法正确的是（ D ）。

A ．每个元素都有一个直接前驱和一个直接后继

B ．线性表中至少有一个元素

C ．表中诸元素的排列必须是由小到大或由大到小

D ．除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接

后继。

(11) 若指定有n 个元素的向量，则建立一个有序单链表的时间复杂性的量级是（ C ）。 2A ．O(1) B ．O(n) C ．O(n) D ．O(nlog2n)

(12) 以下说法错误的是（ D ）。

A ．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结

构时实现的效率低

B ．顺序存储的线性表可以随机存取

C ．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活

D ．线性表的链式存储结构优于顺序存储结构

(13) 在单链表中，要将s 所指结点插入到p 所指结点之后，其语句应为（ D ）。

A ．s->next=p+1; p->next=s;

B ．(*p).next=s; (*s).next=(*p).next;

C ．s->next=p->next; p->next=s->next;

D ．s->next=p->next; p->next=s;

(14) 在双向链表存储结构中，删除p 所指的结点时须修改指针（ A ）。

A ．p->next->prior=p->prior; p->prior->next=p->next;

B ．p->next=p->next->next; p->next->prior=p;

C ．p->prior->next=p; p->prior=p->prior->prior;

D ．p->prior=p->next->next; p->next=p->prior->prior;

(15) 在双向循环链表中，在p 指针所指的结点后插入q 所指向的新结点，其修改指针

的操作是（ C ）。

A ．p->next=q; q->prior=p; p->next->prior=q; q->next=q;

B ．p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;

C ．q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;

D ．q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;

（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（ C ）种情况。

A ．5，4，3，2，1 B ．2，1，5，4，3 C ．4，3，1，2，5 D ．2，3，5，4，

1

（2）若已知一个栈的入栈序列是1，2，3，„，n ，其输出序列为p1，p2，p3，„，

pn ，若p1=n，则pi 为（ C ）。

A．i B．n-i C．n-i+1 D．不确定

（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队

尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ D ）。

A ．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n

（4）链式栈结点为：(data,link)，top 指向栈顶. 若想摘除栈顶结点，并将删除结点的值

保存到x 中, 则应执行操作（ A ）。

A ．x=top->data;top=top->link； B ．top=top->link;x=top->link；

C ．x=top;top=top->link； D ．x=top->link；

（5）设有一个递归算法如下

int fact(int n) { //n大于等于0

if(n

else return n*fact(n-1); }

则计算fact(n)需要调用该函数的次数为（ A ）。

A ． n+1 B ． n-1 C ． n D ． n+2

（6）栈在 （ D ）中有所应用。

A ．递归调用 B ．函数调用 C ．表达式求值 D ．前三个选项都有

（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主

机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的

逻辑结构应该是（ A ）。

A ．队列 B．栈 C ． 线性表 D ．有序表

（8）设栈S 和队列Q 的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S ，

一个元素出栈后即进入Q ，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S 的

容量至少应该是（ B ）。

A ．2 B ．3 C ．4 D ． 6

（9）在一个具有n 个单元的顺序栈中，假设以地址高端作为栈底，以top 作为栈顶指

针，则当作进栈处理时，top 的变化为（ C ）。

A ．top 不变 B ．top=0 C ．top-- D ．top++

（10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结

构最佳。

A ．线性表的顺序存储结构 B．队列

C. 线性表的链式存储结构 D. 栈

（11）用链接方式存储的队列，在进行删除运算时（ D ）。

A. 仅修改头指针 B. 仅修改尾指针

C. 头、尾指针都要修改 D. 头、尾指针可能都要修改

（12）循环队列存储在数组A[0..m]中，则入队时的操作为（ D ）。

A. rear=rear+1 B. rear=(rear+1)%(m-1)

C. rear=(rear+1)%m D. rear=(rear+1)%(m+1)

（13）最大容量为n 的循环队列，队尾指针是rear ，队头是front ，则队空的条件是

（ D ）。

A. (rear+1)%n==front B. rear==front

C ．rear+1==front D. (rear-l)%n==front

（14）栈和队列的共同点是（ C ）。

A. 都是先进先出 B. 都是先进后出

C. 只允许在端点处插入和删除元素 D. 没有共同点

（15）一个递归算法必须包括（ B ）。

A. 递归部分 B. 终止条件和递归部分

C. 迭代部分 D. 终止条件和迭代部分

（1）串是一种特殊的线性表，其特殊性体现在（ B ）。

A ．可以顺序存储 B ．数据元素是一个字符

C ．可以链式存储 D ．数据元素可以是多个字符若

（2）串下面关于串的的叙述中，（ B ）是不正确的？

A ．串是字符的有限序列 B ．空串是由空格构成的串

C ．模式匹配是串的一种重要运算 D ．串既可以采用顺序存储，也可以采用链式存

储

（3）串“ababaaababaa ”的next 数组为（ C ）。

A ．[1**********]9 B ．[1**********]2 C ．[1**********]6 D ．[1**********]45

（4）串“ababaabab ”的nextval 为（ A ）。

A ．010104101 B ．010102101 C ．010100011 D ．010101011

（5）串的长度是指（ B ）。

A ．串中所含不同字母的个数 B ．串中所含字符的个数

C ．串中所含不同字符的个数 D ．串中所含非空格字符的个数

（6）假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存

储单元，基地址为10，则LOC[5,5]=（ B ）。

A ．808 B ．818 C ．1010 D ．1020

（7）设有数组A[i,j]，数组的每个元素长度为3字节，i 的值为1到8，j 的值为1到10，

数组从内存首地址BA 开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为

（ B ）。 A ．BA+141 B ．BA+180 C ．BA+222 D ．BA+225

（8）设有一个10阶的对称矩阵A ，采用压缩存储方式，以行序为主存储，a 11为第一

元素，其存储地址为1，每个元素占一个地址空间，则a 85的地址为（ B ）。

A ．13 B ．33 C ．18 D ．40

（9）若对n 阶对称矩阵A 以行序为主序方式将其下三角形的元素(包括主对角线上所有元素) 依次存放于一维数组B[1..(n(n+1))/2]中，则在B 中确定a （的位置k 的关系为（B ）。 ij i

A ．i*(i-1)/2+j B ．j*(j-1)/2+i C ．i*(i+1)/2+j D ．j*(j+1)/2+i

（10）A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N(N+1)/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k 是（B ）。

A ．i(i-1)/2+j B ．j(j-1)/2+i C ．i(j-i)/2+1 D ．j(i-1)/2+1

（11）设二维数组A[1.. m，1.. n]（即m 行n 列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i,j]在一维数组B 中的下标为（ A ）。

A ．(i-1)*n+j B ．(i-1)*n+j-1 C ．i*(j-1) D ．j*m+i-1

（12）数组A[0..4,-1..-3,5..7]中含有元素的个数（ B ）。

A ．55 B ．45 C ．36 D ．16

（13）广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（ D ）。

A ．(g) B ．(d) C ．c D ．d

（14）广义表((a,b,c,d))的表头是（ C ），表尾是（ ）。

A ．a B ．( ) C ．(a,b,c,d) D ．(b,c,d)

（15）设广义表L=((a,b,c))，则L 的长度和深度分别为（ C ）。

A ．1和1 B ．1和3 C ．1和2 D ．2和3

（1）把一棵树转换为二叉树后，这棵二叉树的形态是（ A ）。

A ．唯一的 Ｂ．有多种

C ．有多种，但根结点都没有左孩子 Ｄ．有多种，但根结点都没有右孩子

（2）由3 个结点可以构造出多少种不同的二叉树？（ D ）

A ．2 B．3 C．4 D．5

（3）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ D ）。

A ．250 B． 500 C．254 D．501

（4）一个具有1025个结点的二叉树的高h 为（ C ）。

A ．11 B．10 C．11至1025之间 D．10至1024之间

（5）深度为h 的满m 叉树的第k 层有（ A ）个结点。(1=

k-1 k h-1h A ．m B．m -1 C．m D．m -1

（6）利用二叉链表存储树，则根结点的右指针是（ C ）。

A ．指向最左孩子 B．指向最右孩子 C．空 D．非空

（7）对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ C ）遍历实现编号。

A ．先序 B. 中序 C. 后序 D. 从根开始按层次遍历

（8）若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ C ）遍历方法最合适。

A ．前序 B．中序 C．后序 D．按层次

（9）在下列存储形式中，（ D ）不是树的存储形式？

A ．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法

（10）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ B ）。

A ．所有的结点均无左孩子 B．所有的结点均无右孩子

C ．只有一个叶子结点 D．是任意一棵二叉树

（11）某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ C ）的二叉树。

A ．空或只有一个结点 B．任一结点无左子树

C ．高度等于其结点数 D．任一结点无右子树

（12）若X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则X 的前驱为（ C ）。

A ．X 的双亲 B．X 的右子树中最左的结点

C ．X 的左子树中最右结点 D．X 的左子树中最右叶结点

（13）引入二叉线索树的目的是（ A ）。

A ．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除

C ．为了能方便的找到双亲 D．使二叉树的遍历结果唯一

（14）线索二叉树是一种（ C ）结构。

A ．逻辑 B． 逻辑和存储 C．物理 D．线性

（15）设F 是一个森林，B 是由F 变换得的二叉树。若F 中有n 个非终端结点，则B 中右指针域为空的结点有（ C ）个。

A ． n-1 B．n C． n+1 D． n+2

（1）在一个图中，所有顶点的度数之和等于图的边数的（ C ）倍。

A ．1/2 B ．1 C ．2 D ．4

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

A ．1/2 B ．1 C ．2 D ．4

（3）具有n 个顶点的有向图最多有（ B ）条边。

A ．n B ．n(n-1) C ．n(n+1) D ．n 2

（4）n 个顶点的连通图用邻接距阵表示时，该距阵至少有（ B ）个非零元素。

A ．n B ．2(n-1) C ．n/2 D ．n 2

（5）G 是一个非连通无向图，共有28条边，则该图至少有（ C ）个顶点。

A ．7 B ．8 C ．9 D ．10

（6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ B ）图。

A ．非连通 B ．连通 C ．强连通 D ．有向

（7）下面（B ）算法适合构造一个稠密图G 的最小生成树。

A ． Prim 算法 B ．Kruskal 算法 C ．Floyd 算法 D ．Dijkstra 算法

（8）用邻接表表示图进行广度优先遍历时，通常借助（ B ）来实现算法。

A ．栈 B. 队列 C. 树 D ．图

（9）用邻接表表示图进行深度优先遍历时，通常借助（ A ）来实现算法。

A ．栈 B. 队列 C. 树 D ．图

（10）深度优先遍历类似于二叉树的（ A ）。

A ．先序遍历 B ．中序遍历 C ．后序遍历 D ．层次遍历

（11）广度优先遍历类似于二叉树的（ D ）。

A ．先序遍历 B ．中序遍历 C ．后序遍历 D ．层次遍历

（12）图的BFS 生成树的树高比DFS 生成树的树高（ C ）。

A ．小 B ．相等 C ．小或相等 D ．大或相等

（13）已知图的邻接矩阵如图6.25所示，则从顶点0出发按深度优先遍历的结果是（ C ）。

⎡0⎢1⎢⎢1⎢⎢1

⎢1⎢⎢0

⎢⎣[***********][1**********]01⎤01⎥⎥00⎥⎥10⎥10⎥⎥01⎥10⎥⎦A ．0 2 4 3 1 5 6 B ．0 1 3 6 5 4 2 C ．0 1 3 4 2 5 6 D ．0 3 6 1 5 4 2

图6.25 邻接矩阵

（14）已知图的邻接表如图6.26所示，则从顶点0出发按广度优先遍历的结果是（ D ），按深度优先遍历的结果是（ ）。

A ．0 1 3 2 B ．0 2 3 1

C ．0 3 2 1 D ．0 1 2 3

图6.26 邻接表

（15）下面（ B ）方法可以判断出一个有向图是否有环。

A ．深度优先遍历 B ．拓扑排序 C ．求最短路径 D ．求关键路径

（1）对n 个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ C ）。 A ．(n-1)/2 B ． n/2 C ．(n+1)/2 D ．n

（2）适用于折半查找的表的存储方式及元素排列要求为（ D ）。

A ．链接方式存储，元素无序 B ．链接方式存储，元素有序

C ．顺序方式存储，元素无序 D ．顺序方式存储，元素有序

（3）当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ C ）。

A ．必定快 B ．不一定

C ．在大部分情况下要快 D ．取决于表递增还是递减

（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（ A ）比较大小，查找结果是失败。

A ．20，70，30，50 B ．30，88，70，50

C ．20，50 D ．30，88，50

（5）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（ B ）次关键字。 A ．3 B ．4 C ．5 D ．6

（6）折半搜索与二叉排序树的时间性能（ C ）。

A ．相同 B ．完全不同

C ．有时不相同 D ．数量级都是O(log2n)

（7）分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（ C ）。

A ．（100，80， 90， 60， 120，110，130）

B ．（100，120，110，130，80， 60， 90）

C ．（100，60， 80， 90， 120，110，130）

D ．(100，80， 60， 90， 120，130，110)

（8）在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A ，并已知A 的左孩子的平衡因子为0右孩子的平衡因子为1，则应作（ C ）型调整以使其平衡。

A ．LL B ．LR C ．RL D ．RR

（9）下列关于m 阶B-树的说法错误的是（ D ）。

A ．根结点至多有m 棵子树

B ．所有叶子都在同一层次上

C ．非叶结点至少有m/2 (m为偶数) 或m/2+1（m 为奇数）棵子树

D ．根结点中的数据是有序的

（10）下面关于B-和B+树的叙述中，不正确的是（ C ）。

A ．B-树和B+树都是平衡的多叉树 B ．B-树和B+树都可用于文件的索引结构

C ．B-树和B+树都能有效地支持顺序检索 D ．B-树和B+树都能有效地支持随机检索

（11）m 阶B-树是一棵（ B ）。

A ．m 叉排序树 B ．m 叉平衡排序树

C ．m-1叉平衡排序树 D ．m+1叉平衡排序树

（12）下面关于哈希查找的说法，正确的是（ C ）。

A ．哈希函数构造的越复杂越好，因为这样随机性好，冲突小

B ．除留余数法是所有哈希函数中最好的

C ．不存在特别好与坏的哈希函数，要视情况而定

D ．哈希表的平均查找长度有时也和记录总数有关

（13）下面关于哈希查找的说法，不正确的是（ A ）。

A ．采用链地址法处理冲突时，查找一个元素的时间是相同的

B ．采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是

相同的

C ．用链地址法处理冲突，不会引起二次聚集现象

D ．用链地址法处理冲突，适合表长不确定的情况

（14）设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位

置是（ D ）。

A ．8 B ．3 C ．5 D ．9

（15）采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字 ( A ) 。

A ．不一定都是同义词 B ．一定都是同义词

C ．一定都不是同义词 D ．都相同

（1）从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（ C ）。

A ．归并排序 B ．冒泡排序 C ．插入排序 D ．选择排序

（2）从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ D ）。

A ．归并排序 B ．冒泡排序 C ．插入排序 D ．选择排序

（3）对n 个不同的关键字由小到大进行冒泡排序，在下列（ B ）情况下比较的次数最多。

A ．从小到大排列好的 B ．从大到小排列好的

C ．元素无序 D ．元素基本有序

（4）对n 个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（ D ）。

A ．n+1 B ．n C ．n-1 D ．n(n-1)/2

（5）快速排序在下列（ C ）情况下最易发挥其长处。

A ．被排序的数据中含有多个相同排序码

B ．被排序的数据已基本有序

C ．被排序的数据完全无序

D ．被排序的数据中的最大值和最小值相差悬殊

（6）对n 个关键字作快速排序，在最坏情况下，算法的时间复杂度是（ B ）。

23A ．O(n) B ．O(n) C ．O(nlog2n) D ．O(n)

（7）若一组记录的排序码为（46, 79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。

A ．38，40，46，56，79，84 B ．40，38，46，79，56，84

C ．40，38，46，56，79，84 D ．40，38，46，84，56，79

（8）下列关键字序列中，（ D ）是堆。

A ．16，72，31，23，94，53 B ．94，23，31，72，16，53

C ．16，53，23，94，31，72 D ．16，23，53，31，94，72

（9）堆是一种（ B ）排序。

A ．插入 B ．选择 C ．交换 D ．归并

（10）堆的形状是一棵（ C ）。

A ．二叉排序树 B ．满二叉树 C ．完全二叉树 D ．平衡二叉树

（11）若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（ B ）。

A ．79，46，56，38，40，84 B ．84，79，56，38，40，46

C ．84，79，56，46，40，38 D ．84，56，79，40，46，38

（12）下述几种排序方法中，要求内存最大的是（ C ）。

A ．希尔排序 B ．快速排序 C ．归并排序 D ．堆排序

（13）下述几种排序方法中，（ C ）是稳定的排序方法。

A ．希尔排序 B ．快速排序 C ．归并排序 D ．堆排序

（14）数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( C ) 算法最节省时间。

A ．冒泡排序 B ．快速排序 C ．简单选择排序 D ．堆排序

（15）下列排序算法中，（ A ）不能保证每趟排序至少能将一个元素放到其最终的位置上。

A ．希尔排序 B ．快速排序 C ．冒泡排序 D ．堆排序