1选择判断题

更新时间：2024-06-02 00:05:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

Test1

一、单项选择（每小题1分，共12分）

1.若某线性表的常用操作是取第i个元素及其前趋元素，则采用( D )存储方式最节省时间 A.单链表 B.双链表 C.单向循环 D.顺序表

顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表2.串是任意有限个( C )

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

3.设矩阵A(aij,1<=i,j<=10)的元素满足:aij<>0(i>=j,1<=i,j<=10),aij =0(i

素A[95]的首地址为( D )

A.2340 B.2336 C.2164 D.2160

Loc(aij)=Loc(a00)+(i*n+j)*d ,这是以行为主求物理地址的公式~a00是首地址，d为每个数组元素占据的地址单元，从二三行条件看出是下三角矩阵，所以a[9,5]之前有多少元素呢？这个应该知道

k=i(i-1)/2+j-1(因为i j从1开始的)，k=（8*9）/2+4=40,所以2000+40*4=2160

中的结点依次存放在计算机内存中一组地址连续的存储单元中。

4.如果以链表作为栈的存储结构,则退栈操作时( C )

A.必须判别栈是否满干 B.对栈不作任何判别 C.必须判别栈是否空 D.判别栈元素的类型

5.设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执

行出队操作的语句为( D )B

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

出队的操作是头指针增1。由于是循环队列，要对增1操作后的结果进行取模操作。data[m]中有m个元素，所以front+1后要%m。

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

根深度为一意思就是以根为第一层，总共就有六层，至多有1+2+2∧2+2∧3+2∧4+2∧5=63

2∧2=2的2次幂

7.将含100个结点的完全二叉树从根这一层开始，每层从左至右依次对结点编号，根结点的编

号为1。编号为49的结点X的双亲的编号为( A )49/2 A.24 B.25 C.23 D.2无法确定

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

A.G'为G的子图 B.G'为G的连通分量

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

9.用线性探测法查找闭散列上，可能要探测多个散列地址，这些位置上的键值( D )

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

10.二分查找要求被查找的表是( C )

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

11.当初始序列已经按键值有序，用直接插入法对其进行排序，需要比较的次数为( D )

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

12.堆是一个键值序列{k1,k2,...,ki,...,kn},对i=1,2,...,└ n/2 满足( C ) ┘， A.ki<=k2i<=k2i+1 B.ki

C.ki<=k2i 且 ki<=k2i+1 (2i+1<= n) D.ki<=k2i 或 ki<=k2i+1 (2i+1<= n)

二、判断题(正确的在括号内打\错的在括号内打\每小题1分，共10分) 1.双链表中至多只有一个结点的后继指针为空( V )

2.在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列

为满的条件是front=rear( X )

3.对链表进行插入和删除操作时，不必移动结点。( V )

4.栈可以作为实现程序设计语言过程调用时的一种数据结构。( V ) 5.在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧。( X )

6.对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则

该图一定是完全图。( X )

7.\顺序查找法\是指在顺序表上进行查找的方法。( X ) 8.向二叉排序树中插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。( V )

9.键值序列{A,C,D,E,F,E,F}是一个堆。( V )

10.在二路归并时，被归并的两个子序列中的关键字个数一定要相等。( X )

Test2

一、单项选择（每小题1分，共12分）

1.在以下排序算法中，最坏情况下时间复杂性最小的排序算法是( D ) A.插入排序 B.快速排序 C.直接选择排序 D.堆排序

2.分析排序算法的空间复杂性，主要是指( D )

A.数据集合所占的空间大小 B.记录比较时所需的空间大小 C.记录移动时所需的空间大小 D.算法中所需附加空间的大小

3.顺序查找时，数据的存储结构是( D )

A.链接存储 B.顺序存储 C.散列存储 D.既可以顺序存储，也可以链接存储

4.在二叉排序树上进行查找，在最理想的情况下查找一个元素的比较次数可以不超过( A )

A.└ log2n ┘+1 B.log2n C.n/2 D. n

5.n个顶点的连通无向图最小有( B )条边

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

6.在n个顶点的完全二叉树中，编号为i的结点为分支点的条件是( B )。 A.2*i>n B.2*i<=n C.i div 2>0 D.i div 2=1

7.先根序列和中根序列相同的非空二叉树是( C )

A.任一结点均无右子树的非空二叉树 B.根结点无右子树的非空二叉树 C.任一结点均无左子树的非空二叉树 D.根结点无左子树的非空二叉树

8.假设数组a[1..n,1..m]中每个元素占一个内存单元，从0地址开始存放，若数组以行为

主序存放时，a[i,j]的存储地址为( C )

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

9.如果以链表作为栈的存储结构，则进栈操作时( B ) A.必须判别是否栈满 B.对栈不必作任何判别 C.必须判别是否栈空 D.必须判别进栈元素类型

10.假设用一维数组sq[1..5]表示一个队列，则队列为空时，队头指针front和队尾指针

rear应分别满足( A )

A.front=0,rear=0 B.front=0,rear=1 C.front=1,rear=0 D.front=1,rear=1

11.对于顺序表的删除算法，若n为表长，删除各结点的概率相等，则删除算法的平均时间

复杂性为( B )

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

12.若p是用于扫描单链表l的各个结点的工作指针，则使p指向下一个结点须执行的语句为( A )

A.p=p^.next B.p=l.next C.p=p+1 D.p=l+1

二、判断题(正确的在括号内打\错的在括号内打\每小题1分，共10分) 13.对于给定的键值(83,40,63,13,35),快速排序的第一趟的结果是(13,35,40,63,83)。( X ) 14.若待排序的记录有n个，则使用冒泡排序算法进行排序共需n-1趟。( V ) 15.把在二叉排序树上删除的结点又插回去，其树形与原来的树形一定相同。( X )

16.二分查找的查找长度不超过└ log2n ┘+1。( V ) 17.在图G的拓朴序列中，Vi在Vj之前，则在G中必有一条弧。( X ) 18.已知二叉树的前序遍历序列和后序遍历序列不能唯一地确定这这棵树。( V )

19.二叉树是树的特殊情形。( X )

20.在循环队列中front和rear分别是队头和队尾指针，则入队操作是:rear=rear+1。( X )

21.链接存储方式既可以用于存储线性表，也可以用于存储各种非线性的数据结构。( V )

22.若顺序表从内存地址b开始存放，各结点都占用l(l>=1)个内存单元，则第i个结点的存储

地址为 b+i*l。( X )

Test3

一、单项选择（每小题1分，共12分）

1.一个具有n个顶点的无向完全图的边数为( B )

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

2.在索引顺序表中查找一个元素，可用的且最快的方法是( C )

A.用顺序查找法确定元素所在块，再用顺序查找法在相应的块中查找 B.用顺序查找法确定元素所在块，再用二分查找法在相应的块中查找 C.用二分查找法确定元素所在块，再用顺序查找法在相应的块中查找