数据结构模拟考试测试题库

栈

设有三个元素XXZ顺序进栈(进的过程中允许出栈)，下列得不到的出栈排列是()。

•4XYZ

•8、YZX

•C>ZXY

•D、ZYX

正确答案：C我的答案：C得分：14.2分

2

向一个栈顶指针为hs的链栈中插入一个s结点时，应执行()。

•Nhs・>next=s;

•8、s->next=hs;hs=n;

•C>—ext=hs->next;hs->next=s;

•D、s->next=hs;hs二hs->next;

正确答案：B我的答案：B得分：14.2分

3

栈在()中应用。

.4递归调用

•B,子程序调用

•C,表达式求值

•。、ABC

正确答案：A我的答案：D得分：0.0分

4

栈的操作原则是()。

•A、先进先出

•8>后进先出

•C,先进后出

•0、不分顺序

正确答案：B我的答案：B得分：14.2分

一个栈的输入序列为123...n,若输出序列的第一个元素是n,输出第i(l<=i<=n)个元素是()。

•A.一不确定

•B,n-i+1

・C.i

•D,n-i

正确答案：B我的答案：B得分：14.2分

6

链栈与顺序栈相比，有一个比较明显的优点，即0

•人插入操作方便

•B,通常不会出现栈满的情况

•C、不会出现栈空的情况

•D、删除操作更方便

正确答案：B我的答案：D得分：0.0分

二.简答题（共1题,14.8分）

1

假定有四个元素A,B,C,D依次进栈,进栈过程中允许出栈，试写出所有可能的出栈序列。

正确答案：

共有14中可能的出栈序歹U分别为：ABCD","ABDC","ACBD","

ACDB";"BACD","ADCB","BADC","BCAD","BCDA","BDCA","CBAD","CBDA","CDBA","DCBAo

我的答案：

DCBA

CDBA

BCDA

ABCD

BACD

ACDB

ADCB

BDCA

批语

队列

若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3,当从队列中

删除一个元素，再加入两个元素后,rear和front的值分别为多少?()

•4.1和5

・8、2和4

•C,4和2

•D、5和1

正确答案：B我的答案：B得分：6.2分

2

用链表方式存储的队列，在进行删除运算时()。

•4.仅修改头指针

•8、仅修改尾指针

•C、头、尾指针都要修改

•0、头、尾指针可能都要修改

正确答案：D我的答案：D得分：6.2分

3

队列的操作原则是()。

•先进先出

•8、后进先出

•C、先进后出

•D.不分顺序

正确答案：A我的答案：A得分：6.2分

4

循环队列的出队操作为()。

•A.sq.front=(sq.front+l)%maxsize

•8、sq.front=sq.front+1

•C>sq.rear=(sq.rear+l)%maxsize

•D、sq.rear=sq.rear+工

正确答案：A我的答案：A得分：6.2分

栈和队列都是()。

•A、顺序存储的线性结构

•8,链式存储的非线性结构

•C,限制存取点的线性结构

•D、限制存取点的非线性结构

正确答案：C我的答案：C得分：6.2分

循环队列的队空条件为()。

•A.(sq.rear+l)%maxsize==(sq.front+l)%maxsize

•8>(sa.rear+l)%maxsize==sq.front+l

•C、sq.(rear+l)%maxsize==sq.front

•D,sq.rear==sa.front

正确答案：D我的答案：D得分：6.2分

循环队列的队满条件为()。

•A.(sq.rear+l)%maxsize==(sq.front+l)%maxcize

•B、(sq.rear+l)%maxsize==sq.front+：l

•Cysq.(rear+l)%maxsize二二sq.front

•D、sq・rea「==sq.front

正确答案：c我的答案：C得分：6.2分

二.判断题(共8题,49.6分)

队列和栈都是运算受限的线性表，只允许在表的两端进行运算。()

我的答案：x得分：6.2分正确答案：x

通常使用队列来处理函数或过程的调用。()

我的答案：x得分：6.2分正确答案：x

循环队列通常用指针来实现队列的头尾相接。()

我的答案：x得分：6.2分正确答案：x

队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。()

我的答案：X得分：6.2分正确答案：X

5

栈与队列是一种特殊操作的线性表。()

我的答案：K得分：6.2分正确答案：7

6

栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。()

我的答案：x得分：6.2分正确答案：x

7

栈和队列都是线性表，只是在插入和删除时受到了一些限制。()

我的答案：X得分：6.2分正确答案：X

8

循环队列也存在空间溢出问题。()

我的答案：K得分：6.2分正确答案：V

三.简答题(共1题,7.0分)

1

什么是队列的上溢现象?一般有几种解决方法，试简述之。

正确答案：

在队列的顺序存储结构中"，"设队头指针为front","队尾指针为rear","队列的容量(即存储空间

的大小)为maxnum。当有元素要加入队列(即入队)时"，"若rear=maxnum","则会发生队列的上

溢现象","此时就不能将该元素加入队列。对于队列"，"还有一种"假溢出"现象:即队列中尚有

足够的空间"，"但元素却不能入队"，"一般是由于队列的存储结构或操作方式的选择不当所致

可以用循环队列解决。一般地","要解决队列的上溢现象"，"可以用以下几种方法：⑴可建

立一个足够大的存储空间以避免溢出"，"但这样做的缺点是:空间使用率低"，"浪费存储空间。

⑵要避免出现"假溢出"现象"，"可用以下方法解决：第一种:采用移动元素的方法。每当有一个

新元素入队，"就将队列中已有的元素向队头移动一个位置"，"假定空余空间足够。第二种:

每当删除一个队头元素"，"则可依次移动队列中的元素"，"总是使front智深指向队列中的第一

个位置。第三种:采用循环队列方式"，"将队头、队尾看作是一个首尾相接的循环队列","即用

循环数组实现","此时队首仍在队尾之前"，"作插入和删除运算时仍遵循"先进先出"原则。

我的答案：

在队列的顺序结构中，设队头指针为front,队尾指针为rear,队列的容量(即存储空

间大小)为maxnum。当有元素要加入队列时，若rear==maxnum则会发生队列的

上溢现象，此时就不能将该元素加入队列。对于队列，还有一种''假溢出''现象，队列

中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的

选择不当所致，可以用循环队列解决。

一般的，要解决队列的上溢现象有以下几种方法：

(1)可建立一个足够大的存储空间以避免假溢出，但这样做往往会造成空间使用率低,

浪费存储空间。

(2)要避免出现''假溢出''现象可以使用以下方法解决：

第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队

头移动一个位置，假定空余空间足够。

第二种：每当删除一个队头元素，则可依次移动队列中的元素总是使front指针指向

队列中的第一个位置。

批语

数组

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

址为10,则LOC[5,5]=()o

•4.808

・8<818

•C,1010

•。、1020

正确答案：B我的答案：B得分：6.2分

2

稀疏矩阵一般的压缩存储方法有两种，即()。

•A、二维数组和三维数组

•B、三元组和散列

•C、三元组和十字链表

•0、散列和卜字链表

正确答案：C我的答案：C得分：6.2分

3

已知二维数组AlOxlO中，元素a20的地址为560,每个元素占4个字节，则元素alO的地址为()。

•A,520

•8、522

•C,524

•D、518

正确答案：A我的答案：A得分：6.2分

4

对稀疏矩阵进行压缩存储的目的是()。

•4,便于进行矩阵运算

•8、便于输入和输出

•C、节省存储空间

•D.降低运算的时间复杂度

正确答案：C我的答案：C得分：6.2分

5

数组A中，每个元素的长度为3个字节，行下标i从1到8,列下标j从1到10,从首地址SA开

始连续存放在存储器内，该数组按行存放时，元素A⑻⑸的起始地址为()。

•A、SA+141

•B.SA+144

•C、SA+222

•0、SA+225

正确答案：C我的答案：C得分：6.2分

6

通常对数组进行的两种基本操作是0

•4建立与删除

•B、索引和修改

•C、查找与修改

•D,索引与查找

正确答案：C我的答案：C得分：6.2分

7

数组就是矩阵，矩阵就是数组，这种说法()。

•A、正确

・B、转送

•C,前句对，后句错

•D,后句对

正确答案：B我的答案：B得分：6.2分

8

设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列序优先的方式存储在一维数

组B[l...n(n+l)/2]中，对上述任一元素aij(l<i,j<n,K即在B中的位置为()。

•A、i(i-l)/2+i

•B、i(i-l)/2+i

•C,*l)/2+i-l

•D,i(i-l)/2+i-l

正确答案：B我的答案：B得分：6.2分

9

设二维数组A[l...m4...n](B|lm行n歹U)按行序优先存储在数组中，则二维数组元素

A[i,j]在一维数组B中的下标为()。

•A、(i-l)*n+i

•B,(i-l)*n+i-l

・C.

•0、i*m+i-l

正确答案：A我的答案：A得分：6.2分

二.判断题(共7题,44.2分)

数组可看成线性结构的一种推广，因此与线性表一样，可对它进行增删等操作。()

我的答案：X得分：6.2分正确答案：x

2

矩阵中的数据元素可以是不同的数据类型。()

我的答案：X得分：6.2分正确答案：X

3

对于不同的特殊矩阵应该采用不同的存储方式。()

我的答案：V得分：6.2分正确答案：V

4

稀疏矩阵压缩存储后，必会失去随机存取功能。()

我的答案：K得分：6.2分正确答案：V

5

数组可看作基本线性表的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。()

我的答案：X得分：6.2分正确答案：X

6

矩阵中的行列数往往是不相等的。()

我的答案：x得分：6.2分正确答案：x

7

数组是同类型数值的集合。()

我的答案：X得分：7.0分正确答案：X

树和二叉树

1

任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（）。

A、不发生改变

B、发生改变

不能确定

以上都不对

正确答案：A我的答案：A得分：3.0分

2

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

A、逻辑

逻辑和存储

C物理

线性

正确答案：C我的答案：C得分：3.0分

3

在完全二叉树中，当i为奇数且不等于1时,结点i的左兄弟是结点o,否则没有左兄弟。

2i-1

i+1

2i+1

i-1

正确答案：D我的答案：D得分：3.0分

4

线索二叉树中,结点P没有左子树的充要条件是（）

p->Ic=NULL

p->Itag=1

p->!tag=1且p->!c=NULL

以上都不对

正确答案：B我的答案：B得分：3.0分

5

如果F是由有序树T转换而来的二叉树,那么T中结点的前序就是F中结点的()。

A、史序

前序

后序

层次序

正确答案：B我的答案：B得分：3.0分

6

已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为()。

1

2

3

4

正.答案：B我的答案：B得分：3.0分

7

设n,m为一棵二叉树上的两个结点,在中序遍历序列中n在m前的条件是()。

n在m右方

n在m左方

n是m的祖先

n是m的子孙

正确答案：B我的答案：B得分：3.0分

8

在一棵二叉树上第4层的结点数最多为()。

A、2

4

6

8

正碓I答案：D我的答案：D得分：3.0分

9

假设在一个二叉树中，双分支结点数为15,单分支结点数为32,则叶子结点数为()个。

15

16

17

47

正确答案：B我的答案：B得分：3.0分

10

某二叉树T有n个结点,设按某种遍历顺序对T中的每个结点进行编号,编号值为1,2,…,n,

且有如下性质：T中任一结点V,其编号等于左子树上的最小编号减1,而V的右子树的结点中,

其最小编号等于V左子树上结点的最大编号加1,这时按()编号。

中序遍历序列

前序遍历序列

后序遍历序列

层次遍历序列

正确答案：B我的答案：B得分：3.0分

根据先序序列ABDC和中序序列DBAC确定对应的二叉树,该二叉树()。

A、是完全二叉树

不是完全二叉树

C、是满二叉树

不是满二叉树

正确答案：A我的答案：A得分：3.0分

12

在树中除根结点外,其余结点分成m(m20)个()的集合T1,T2,T3-Tm,每个集合又都是树，此

时结点T称为Ti的父结点,Ti称为T的子结点(1WiWm)。

互不相交

可以相交

叶节点可以相交

树枝结点可以相交

正确答案：A我的答案：A得分：3.0分

13

如果结点A有三个兄弟,而且B是A的双亲，则B的出度是()。

3

4

C、5

1

正碓I答案：B我的答案：B得分：3.0分

14

欲在不使用栈的前提下实现任意二叉树的后序遍历的非递归算法,最佳方案是二叉树采用（）

存储结构。

三叉链表

广义表

二叉链表

顺序

正确答案：A我的答案：A得分：3.0分

二.判断题（共16题.48.0分）

1

若有一个结点是某二叉树子树中序遍历序列中的最后一个结点，则它必是该子树前序遍历序

列中的最后一个结点。（）

我的答案：V得分：3.0分正确答案：V

2

树的子树是无序的。（）

我的答案：X得分：3.0分正确答案：X

3

后序遍历和中序遍历与该树对应的二叉树,其结果不同。（）

我的答案：V得分：3.0分正确答案：V

4

二叉树的前序遍历中，任意结点均处在其子女结点之前。（）

我的答案：V得分：3.0分正确答案：V

5

树的后序遍历与其对应的二叉树的后序遍历序列相同。（）

我的答案：V得分：3.0分正确答案：V

6

线索二叉树是一种逻辑结构。（）

我的答案：X得分：3.0分正确答案：X

7

霍夫曼树的总结点个数（多于1时）不能为偶数。（）

我的答案：V得分：3.0分正确答案：V

8

霍夫曼树一定是完全二叉树。（）

我的答案：X得分：3.0分正确答案：X

9

满二叉树也是完全二叉树。（）

我的答案：V得分：3.0分正确答案：V

10

根据任意一种遍历序列即可唯一确定对应的二叉树。