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

栈

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

•小XYZ

•B、YZX

•ZXY

•D、ZYX

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

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

•A>hs->next=s;

•B、fxl=hs;h、=s;

•C»s->next-hs->next;hs->next=s;

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

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

栈在()中应用。

•N递归调用

•8、子程序调用

•C.表达式求值

•D、A,B,C

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

栈的操作原则是()。

•A先进先出

•8、后进先出

•C、先进后出

•D、不分顺序

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

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

•A.不确定

•B、n-i+1

•C、i

•D、n-i

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

6

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

•小插入操作方便

•8、通常不会出现栈满的情况

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

•D、删除操作更方便

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

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

1

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

正确答案：

共有14中可能的出栈序歹lj分另I」为：ABCD'V'ABDCV'ACBD"；'

,",,,,,,

ACDR"Z"RACD","ADCR","RADC,"RCAD","RCDA/"RnCA"z"CRAD",CRDA","CDRA",DCRA.

我的答案：

DCBA

CDBA

BCDA

ABCD

BACD

ACDB

ADCB

BDCA

批语

队列

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

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

•4、1和5

•B、2和4

•C、4和2

•。、5和1

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

2

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

•N仅修改头指针

•8、仅修改尾指针

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

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

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

3

队列的操作原则是()。

•N先进先出

•8、后进先出

•C、先进后出

•D、不分顺序

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

4

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

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

•8、sq.front=sci.front+l

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

•D、sa.rear=sq.rear+1

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

5

栈和队列都是()。

•N顺序存储的线性结构

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

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

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

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

6

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

•A、(sQ.rear+l)%maxsizr==(sci.front+l)%maxsize

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

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

•D、sa.rear==sa.front

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

7

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

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

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

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

•D、sa.rear==sa.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

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

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

6

栈和队列的存储方式，既可以是顺序方式，乂可以是链式方式。（）

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

7

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

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

8

循环队列也存在空间溢出问题。（）

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

三.简答题（共1题,7.0分）

1

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

正确答案：

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

的大小）为maxnum。当有元素要加入队列（即入队）时“，"若rear=maxnum;则会发生队列的上

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

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

/可以用循环队列解决。一般地“，”要解决队列的上溢现象可以用以下几种方法：（1：可建

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

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

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

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

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

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

我的答案：

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

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

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

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

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

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

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

浪费存储空间。

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

第一利h采用移动元素的方法C每当有一个新元素入队.就将队列中已有的元素向队

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

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

队列中的第一个位置。

批语

数组

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

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

•A.803

•B、818

•C、1010

•D、1020

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

2

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

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

•8、三元组和散列

•C、三元组和I•字琏表

•D、散列和十字链表

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

3

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

•4520

•8、522

•C>524

•D、518

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

4

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

•N便于进行矩阵运算

•8、便于输入和输出

•C、节省存储空间

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

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

5

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

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

•4、SA+141

•B、SA+144

■C,SA+222

•D、SA+225

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

6

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

•A、建立与删除

•8、索引和修改

•C、查找与修改

•D、索引与杳找

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

7

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

•4、正确

•B、镇送

•C、前句对，后句错

•D、后句对

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

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

组B[l...n(n+l)/2]中，对上述任一元素aij(14ij",且区j)在B中的位置为()。

•4、i(i；)/2+i

•8、4l)/2+i

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

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

9

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

在一维数组B中的下标为()。

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

•8、

•C.

•D、

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

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

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

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

2

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

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

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

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

4

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

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

5

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

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

6

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

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

7

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

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

树和二叉树

1

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

■A、不发生改变

•B、发生改变

•C、不能确定

•D、以上都不对

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

2

线索二叉树是一种o结构，

•A、逻箱

•B、逻辑和存储

•C、9

•D、线性

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

3

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

•A、2M

•B、j+1

•C、2i+1

•D、iT

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

4

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

.Axp->lc=NULL

•B、p->ltag=1

•Cxp->ltag=1且p->lc=NULL

•D、以上都不对

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

5

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

A、

B、前序

后序

D、层次序

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

6

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

A、1

B、2

C、3

D、4

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

7

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

Axn在m右方

Bn在m左方

C、n是m的祖先

D、n是m的子孙

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

8

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

A、2

B、4

C、6

D、8

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

9

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

Ax15

16

C、17

•D、47

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

10

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

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

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

•A、中序遍历序列

•前序遍历序列

•C、后序遍历序列

•D、层次遍历序列

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

11

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

•A、是完全二叉树

•B、不是完全二叉树

•C、是满二叉树

•D、不是满二叉树

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

12

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

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

•A、互不相交

•B、可以相交

•C、叶节点可以相交

•D、树枝结点可以相交

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

13

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

•A、3

B、4

C、5

D、1

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

14

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

存储结构。

A、三叉链表

B、广义表

C、二叉链表

D、顺序

正确答案：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

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

我的答案：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

根据任意一种