数据结构模拟(共五卷)

数据结构模拟（一）

一、单项选择题（100题）

1、二维数组A行下标i的范围从1到12,列下标j的范围从3到10,采用行序

为主序存储，每个数据元素占用4个存储单元，该数组的首地址（即A[l][3]的

地址）为1200,则A[6][5]的地址为（）。

A、1400

B、1404

C、1372

D、1368

2、一个长度为n的顺序表中,删除下标为i（OWiWnT）的元素时，需要向前移

动（）个元素。（3.0分）

A、n-i

B、n-i+1

C、n-i-1

D、i

3、“二叉树为空”意味着二叉树（）。（3.0分）

A、由一些没有赋值的空结点构成

B、根结点没有子树

C、不存在

D、没有结点

4、在二叉排序树中，每个结点的关键字值（）o（5.0分）

A、比左子树所有结点的关键字值大，比右子树所有结点的关键字值小

B、比左子树所有结点的关键字值小，比右子树所有结点的关键字值大

C、比左右子树的所有结点的关键字值都大

D、与左.右子树所有结点的关键字值无必然的大小关系

5、假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入哈希表

中，至少要进行（）次探测。

A、k-1

B、k

C、k+1

D、k（k+l）/2

6、（3分）线性表适合于顺序查找的存储结构是（C）o

A、索引存储

B、压缩存储

C、顺序存储

D、散列存储

7、在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该

是()

A、i>0

B、iWn

C,lWiWn

D、lWiWn+1

8、在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链接的表头

指针向量大小至少为()

A、n

B、2n

C、e

D、2e

9、对于一个具有n个顶点和e条边的无向图，若采用邻接表示，则顶点表向

量的大小和所有邻接表中的结点总数分别是()。

A、都是n

B、都是n+e

C、n和n+e

D、n和2e

10、*给定排序码值序列为{F,B,J,C,E,A,I,D,C,H},对其按字母的字

典序列的次序进行排列，希尔(Shell)排序的第一趟(dl=5)结果应为()。

A、｛B,F,C,J,A,E,D,I,C,H)

B、｛C,B,D,A,E,F,I,C,J,H)

C、｛B,F,C,E,A,I,D,C,H,J)

D、｛A,B,D,C,E,F,I,J,C,H)

11、设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一

维数组B[l,n(n-l)/2]中，对下三角部分中任一元素ai,j(i>=j),在一维数组B

的下标位置k的值是()

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

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

C、i(i+l)/2+j-l

D、i(i+l)/2+j

12、任何一个无向连通网的最小生成树

A、有一棵或多棵

B、只有1棵

C、一定有多棵

D、可能不存在

13、以下说法正确的是()0

A、在单链表中,任何两个元素的存储位置之间都有固定的联系，因此可以从

头结点开始,查找任何一个元素

B、在单链表中,要取得某个元素，只要知道该元素的指针即可，因此,单链表

是随机存取的存储结构

C、顺序存储方式只能用于存储线性结构

D、顺序存储方式的优点是存储密度大，且插入、删除运算效率高

14、(3分)假设散列表长m=ll,散列函数H(key)=key先H表中己有4个结点：H

(39):。6,H(41):8.H(53):9,H(76):10,占了4个位置，其余位置为

空。现采用线性探查法处理冲突,存储关键字85时需要探查的次数是(C)o

A、2

B、3

C、4

D、5

15、在一个链队中，假设和分别为队首和队尾指针,则删除一个结点的运算时

(C)o

A、r=f->next;

B、r=r->next：

C、f=f->next;

D、f=r->next;

16、(4分)顺序表中有10个数据元素，若第-一个元素的存储地址是1000,则

最后-一个元素地址是1036,第5个元素的地址是(B)。

A、1010

B、1016

C、1018

D、1019

17、下列叙述中错误的是(C)。

A、图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次

B、图的遍历可以采用深度优先遍历和广度优先遍历

C、图的广度优先遍历只适用于无向图

D、图的深度优先遍历是一个递归过程

18、对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时

间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度分别为

A、0(1),0(n)

B、0(n),0(n)

C、0(1),0(1)

D、0(n),0(l)

19、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序

遍历的结果为(A)。

A、CBEFDA

B、FEDCBA

C、CBEDFA

D、不定

20、对n个顶点和e条边的有向图，以邻接矩阵存储，则求图中某顶点入度的

时间复杂度为()o

A、O(n)

B、0(e)

C、0(n+e)

D、0(n2)

21、从没有排序序列中挑选元素,并将其一次插入已排序序列末端的方法，称

()

A、归并排序

B、冒泡排序

C、插入排序

D、选择排序

22、下列各种排序算法中平均时间复杂度为0(n2)是()。

A、快速排序

B、堆排序

C、归并排序

D、冒泡排序

23、表示一个有100个顶点，1000条边的无向图的邻接矩阵有()个非零矩

阵元素。

A、100

B、1000

C、9000

D、1000X2

24、判断顺序栈(最多结点数为m)为栈满的条件是

A、top==0

B、top!=m

C、top!=0

D>top==m

25、下列排序方法中，()所需的辅助空间最大。(2.0分)

A、选择排序

B、希尔排序

C、快速排序

D、归并排序

26、下列数据结构中，不属于二叉树的是。

A、B树

B、AVL树

C、二叉排序树

D、哈夫曼树

27、在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印机

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

取出数据打印。该缓冲区应该是一个()结构

A、栈

B、队列

C、树

D,线性表

28、在下列排序方法中不需要对排序码值进行比较就能进行排序的是()。

A、基数排序

B、快速排序

C、直接插入排序

D、堆排序

29、栈在()中应用。

A、递归调用

B、子程序调用

C、表达式求值

D、A,B,C

30、队列的特点是O。

A、先进先出

B、后进先出

C、先进后出

D、不进不出

31、若栈采用顺序存储方式存储，现两栈共享空间V[m],top[i]代表第i个

栈(i=1,2)栈顶，栈1的底在v[0],栈2的底在则栈满的条件是

()

A、top[2]-top[l]=0

B、top[l]+l=top[2]

C、top[l]+top[2]=m

D、top[l]=top[2]

32、若长度为n的线性表采用链式存储结构，访问其第i个元素的算法时间

复杂度为()

A、0(n)

B、0(n'2)

C、0(n-3)

D、0(log2"n)

33、设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂

度为()0

A、0(n)

B,0(n2)

C、0(nlog2n)

D、0(log2n)

34、下面叙述正确的是

A、二叉树是特殊的树

B、二叉树等价于度为2的树

C、完全二叉树必为满二叉树

D、二叉树的左右子树有次序之分

35、设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为

()o

A、top=top+l

B、top=top-l

C、top->next=top

D、top=top->next

36、一个递归算法必须包括()。

A、递归调用

B、子程序调用

C、表达式求值

D、A,B,C

37、设无向图G中顶点数为n,则图G至多有()条边。

A、0

B、n

C、n(n-1)/2

D、n(n-l)

38、分别以下列序列构造二叉排序树，与其他三个序列构造结果不同的是()0

⑸0分)

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)

39、若一棵二叉树具有10个度为2的结点,5个度为1的结点，则度为0的结

点个数是(B)

A、9

B、11

C、15

D、不确定

40、链表适用于()o(5.0分)

A、顺序查找

B、二分查找

C、插值查找

D、随机

41、经过下列栈的运算后EmptyStaCk(s)的值是()。

InitStaCk(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,x);

A、A、

B、B、

C、1

D、0

42、在数据结构中，从存储结构上可以将之分为

A、动态结构和静态结构

B、顺序存储和非顺序存储

C、紧凑结构和非紧凑结构

D、线性结构和非线性结构

43、在任何情况下，时间复杂度均为0(nlgn)的不稳定的排序方法是()。

⑵0分)

A、直接插入

B、快速排序

C、堆排序

D,归并排序

44、判定一个顺序栈ST(最多元素为m0)为栈满的条件是

A、top!=0

B、top==0

C、top!=m0

D>top==m0-l

45、某内排序方法的稳定性是指(D)。

A、该排序算法不允许有相同的关键字记录

B、该排序算法允许有相同的关键字记录

C、平均时间为0(nlogn)的排序方法

D、以上都不对

46、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为

A、n

B、n/2

C、(n+l)/2

D、(n-l)/2

47、设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字

映射到HASH表中需要做()次线性探测。

A、n2

B、n(n+l)

C、n(n+1)/2

D、n(n-l)/2

48、设有一个递归算法如下：Intfun(intn){if(n<=0)return0;

elsen+fun(n-l)；}则计算fun(n)(n>0)需要调用该函数的次数为()。

A、n+1

B、n-1

C、n

D、n+2

49、对于一个具有N个顶点的无向凰若采用邻接矩阵表示,则该矩阵大小是

()

A、N

B、(N-D2

C、(N-1)*N

D、N*N

50、对有n个记录的表进行直接插入排序,在最坏情况下需进行()次关键字比

较。

A、n-l

B、n+1

C、n/2

D、n(n-l)/2

参考答案及解析

一、单项选择题

1、D

2、C

3、D

4、A

5、D

6、C

7、C

8、A

9、D

10、D

11、B

12、A

13、A

14、C

15、C

16、B

17、C

18、A

19、A

20、D

21、D

22、D

23、D

24、D

25、D

26、A

27、B

28、A

29、A

30、A

31、B

32、B

33、D

34、D

35、D

36、B

37、C

38、C

39、B

40、A

41、C

42、B

43、C

44、D

45、D

46、C

47、D

48、A

49、D

50、D

数据结构模拟（二）

一、单项选择题（100题）

1、以下说法正确的是（）。

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

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

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

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

2、用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[l..n],

结点R[i]若有左孩子，其左孩子的编号为结点

A、R[2i+1]

B、R[2i]

C、R[i/2]

D、R[2i-1]

3、在n个结点的顺序表中，算法的时间复杂度是0（1）的操作是（）。

A、访问第i个结点（iWiWn）和求第i个结点的直接前驱（2WiWn）

B、在第i个结点后插入一个新结点（IWiWn）

C、删除第i个结点（iWiWn）

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

4、有n个十进制整数进行基数排序,其中最大的整数为5位,则基数排序过程中

临时建立的队数个数是（）。

A、10

B、n

C、5

D、2

5、一棵二叉树有100个结点，则至少有（）个叶结点。

A、1

B、2

C、3

D、4

6、算法是描述解决特定问题的思路.方法和步骤,是求解步骤（指令）的有限序

列。其特性除了包含输入和输出外,还包括（）。（5.0分）

A、有穷性.正确性.可行性

B、有穷性.正确性.确定性

C、有穷性.确定性.可行性

D、正确性.确定性.可行性

7、已知一如下10个记录的表，其关键字序列为

(2,15,19,25,30,34,44,55,58,80),用折半查找法查找关键字为55的记录，比较

次数是

A、1次

B、2次

C、3次

D、4次

8、若INDEX(S,T)表示求T在S中的位置，则对于

S="BeiJing&Nanjing"，T=“jing”,INDEX(S,T)=()o

A、2

B、3

C、4

D、5

9、设串长为n,模式串长为m,则KMP算法所需的附加空间为()。

A、0(m)

B、0(n)

C、0(m*n)

D、0(nlog2m)

10、双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p

指向链表中的一个结点，在P的结点前插入一个指针q指向的结点操作是

()o

A、p->llink=q;

B、p->llink=q;Q->rlink=p;p->llink->rlink=q;

C、q->rlink=p;

D、q->llink=p->llink;

q->llink=p->llink;q->rlink=q;P->llink->rlink=q;p->llink=q->rlink;P->1

1ink=q;p->llink=q;

11、下列四种排序方法中，不稳定的方法是()

A、直接插入排序

B、冒泡排序

C、归并排序

D、直接选择排序

12、假设以行序为主序存储二维数组A=array[l...100,1...100],设每个数组

元素占2个存储单元,基地址为10,则L0C[5,5]=

A、818

B、808

C、1010

D、1020

13、下述编码中哪一个不是前缀编码（）

A、{00,01,10,11）

B、{01,0,1,10）

C、{0,10,110,111）

D、[1,01,000,111）

14、由权值3,6,7,2,5的叶子结点生成的一颗哈夫曼树，它的带权长度为（）0

（3.0分）

A、51

B、23

C、53

D、74

15、一个队列的入队序列是1,2,3,4,5,6,7,则队列的出队序列可能是（）。

A、1,2,3,5,7,6,4

B、1,2,3,4,5,6,7

C、7,6,5,4,1,2,3

D、7,6,5,4,3,2,1

16、若SUBSTR⑸i,k）表示求S中从第i个字符开始的连续k个字符组成的子

串的操作,则对于S="Beijing&Nanjing"，SUBSTR（S,4,5）=（）。

A、“ijing”

B、“jing&”

C、“ingNa”

D、“ing&N”

17、链队列的在建立时，可以采用（）将几个元素链接起来建立单链表。

A、头插法

B、尾插法

C、随机插入法

D、需要指定插入位置的方法

18、（6分）数据的逻辑结构可以分为0。

A、动态结构和静态结构

B、顺序结构和链式结构

C、线性结构和非线性结构

D、简单结构和构造结构

19、下述几种排序方法中，要求辅助内存最大的是（）。

A、插入排序

B、快速排序

C、归并排序

D、选择排序

20、顺序栈包含两部分，数组data[10]和栈顶top,当top值为()表示栈

满。

A、0

B、9

C,10

D、-1

21、下列程序的空间复杂度是()。

For(i=l;i<=n;++i){for(j=l;j<=m;++j){c[i][j]=0;}}

A、0(m*n)

B、0(m+n)

C、0(m-n)

D、0(m/n)

22、数据结构这门学科的研究内容下面选项最准确的是

A、研究数据对象和数据之间的关系

B、研究数据对象

C、研究数据对象和数据的操作

D、研究数据对象、数据之间的关系和操作

23、某顺序栈sqStack,其成员包含两部分:data[10]和top,分别代表数据

和栈顶，则表示栈中第三个数据元素的是()

A、sqStack.data[2]

B、sqStack.data[3]

C、sqStack.data[4]

D、无法表示

24、在一个单链表中，删除p所指结点的直接后继的操作是

A、p->next=p->next->next;

B、p=p->next;p->next=p->next->next;

C、p->next=p->next;

D、p=p->next->next;

25、数据在计算机存储器内表示时，物理地址与逻辑地址不相同的,称为0

A、存储结构

B、逻辑结构

C、链式存储结构

D、顺序存储结构

26、算法的有穷性是指()。

A、算法程序的运行时间是有限的

B、算法程序所处理的数据量是有限的

C、算法程序的长度是有限的

D、算法只能被有限的用户使用

27、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小

是（）

A、n

B、（n-l）/2

C,n-1

D>n2

28、如果含有n个顶点的图形成一个环，则它有（）棵生成树

A、n

B、n-1

C、n+1

D、不确定

29、由三个结点构成的二叉树，共有（）种不同的形态

A、4

B、5

C、6

D、7

30、设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。

A、8

B、7

C、6

D、5

31、在二叉排序树中插入一个结点最坏情况下的时间复杂度为（）0

A、0（1）

B、0（n）

C、0（log2n）

D、0（n2）

32、（3分）下列关于散列函数的说法正确的是（D）。

A、散列函数越复杂越好

B、用除余法构造的散列函数是最好的

C、散列函数越简单越好

D、在冲突尽可能少的情况下,散列函数越简单越好

33、在进栈运算时，应先判别栈是否①，在出栈运算时.应先判别栈是否②，

①②处应该是（）

A、空，满

B、满，空

C、满，上溢

D、空，下溢

34、设二维数组A[L.m,1..n](即m行n列)按行存储在数组B[L.m*n]

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

A、(i-l)*n+j

B、(i-l)*n+j-l

C,i*(j-l)

D、j*m+i-l

35、在长度为n的顺序表的第i(lsisn+1)个位置上插入一个元素，元素的移

动次数为(A)。

A、n-i+1

B、n-i

C、i

D、i-1

36、(6分)已知二叉排序树G,要输出其结点的有序序列,则采用的遍历方法是

(Oo

A、按层遍历

B、前序遍历

C、中序遍历

D、后序遍历

37、设有100个元素的有序表,采用折半查找方法,成功时最大的比较次数是()

A、25

B、50

C、10

D、7

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

是

A、n在m右方

B、n在m左方

C、n是m的祖先

D、n是m的子孙

39、用链式存储的栈，在进栈操作时，将要进栈的结点放在链表的()

A、头部

B、尾部

C、中间

D、用户指定的位置

40、对包含n个元素的散列表进行查找，平均查找长度为

A、不直接依赖于n

B、O(n2)

C、O(log2n)

D、0（n）

41、栈通常采用的两种存储结构是（）

A、顺序存储结构和链式存储结构

B、散列方式和索引方式

C、链式存储结构和数组

D、线性存储结构和非线性存储结构

42、在一棵二叉树上第4层的结点数最多为

A、2

B、4

C、6

D、8

43、双向链表的每一个结点有（）个地址域（指针域/引用域）。（3.0分）

A、1

B、2

C、3

D、0

44、设有串sl=Mwelcometozdsoftcolleage!w和s2="so"，那么s2在si

中的索引位置是

A、12

B、14

C、13

D、10

45、假设以行序为主序存储二维数组A=array[1..100,1..100],设每个数据元

素占2个存储单元，基地址为10,则L0C[5,5]=（）。

A、808

B、818

C、1010

D、1020

46、设一个链表最常用的操作是在末尾插入结点，则选用（）最节省时间。

A、单链表

B、单循环链表

C、带尾指针的单循环链表

D、带头结点的双循环链表

47、从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的

一端的方法，称为（）o

A、归并排序

B、冒泡排序

C、插入排序

D、选择排序

48、有六个元素6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序

列？（C）

A、543612

B,453126

C,346521

D.234156

49、对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、

右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编

号，可采用（）遍历实现编号。

A、先序

B、中序

C、后序

D、从根开始按层次遍历

50、已知某二叉树的后序遍历序列是DabeC,中序遍历序列是DebaC,它的前序

遍历序列是（）

A、aCbeD

B、DeCaB

C、DeabC

D、CeDba

参考答案及解析

一、单项选择题

1、D

【解析】解释：数据元素是数据的基本单位，数据项是数据的最小单位，数据结构是带

有结构的各数据元素的集合。

2、B

3、A

【解析】解释：在顺序表中插入一个结点的时间复杂度都是0(n2),排序的时间复杂度为

0(n2)或0(nlog2n)。顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接

前驱都可以直接通过数组的下标直接定位，时间复杂度是0(1)O

4、A

5、A

6、C

7、B

8、C

9、A

10、C

11、C

12、A

13、B

14、A

15、B

16、B

17、B

18、C

19、C

20、B

21、A

22、D

23、A

24、A

25、C

26、A

27、D

28、A

29、B

30、B

31、B

32、D

33、B

34>A

【解析】解释：特殊值法。取i二户1,易知A[l,1]的的下标为1,四个选项中仅有A选项

能确定的值为1,故选A。

35、A

36、C

37、D

38、B

39、A

40、A

41、A

42、D

43、B

44、C

45、B

【解析】解释：以行序为主，则L0C[5,5]=[(5-1)*100+(5-1)]*2+10=818。

46、C

47、D

48、C

49、C

【解析】解释：根据题意可知按照先左孩子、再右孩子、最后双亲结点的顺序遍历二叉

树，即后序遍历二叉树。

50、D

数据结构模拟（三）

一、单项选择题（100题）

1、下面叙述正确的是（）。

A、算法的执行效率与数据的存储结构无关

B、算法的空间复杂度是指算法程序中指令（或语句）的条数

C、算法的有穷性是指算法必须能在执行有限个步骤之后终止

D、以上三种描述都不对

2、设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1则T中

的叶子数为（D）

A、5

B、6

C、7

D、8

3、在一棵平衡二叉树中，每个结点的平衡因子的取值范围是（）。

A、-ri

B、-2~2

C、「2

D、0~1

4、用链式存储的栈，在进行出栈和入栈运算时（）

A、仅修改头指针

B、仅修改尾指针

C、头、尾指针都要修改

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

5、下列叙述正确的是。

A、线性表是线性结构

B、栈和队列是非线性结构

C、线性链表是非线性结构

D、二叉树是线性结构

6、连续存储设计时，存储单元的地址（）。

A、一定连续

B、一定不连续

C、不一定连续

D、部分连续，部分不连续

7、一个子串在包含它的主串中的位置是指。。

A、子串中最后的那个字符在主串中的位置

B、子串的最后那个字符在主串中首次出现的位置

C、子串中第一个字符在主串中的位置

D、子串的第一个字符在主串中首次出现的位置

8、图中有关路径的定义是（A）o

A、由顶点和相邻顶点序偶构成的边所形成的序列

B、由不同顶点所形成的序列

C、由不同边所形成的序列

D、上述定义都不是

9、下列数据中，（C）是非线性数据结构。

A、栈

B、队列

C、完全二叉树

D、堆

10、在数据结构中，从逻辑上可以把数据结构分成

A、动态结构和静态结构

B、紧凑结构和非紧凑结构

C、线性结构和非线性结构

D、内部结构和外部结构

11、在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个

新结点，则需要相继修改（）个指针域的值。

A、2

B、3

C、4

D、6

12、某哈希查找表有n条记录，对应的哈希函数具有m个值，则（）

A、n<m

B、n>m

C、n<=m

D、n>=m

13、栈和队列都是（）。

A、顺序存储的线性结构

B、链式存储的非线性结构

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

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

14、下面关于线性表的叙述中，错误的是哪一个？（B）

A、线性表采用顺序存储,必须占用一片连续的存储单元。

B、线性表采用顺序存储,便于进行插入和删除操作。

C、线性表采用链接存储，不必占用一片连续的存储单元。

D、线性表采用链接存储，便于插入和删除操作。

15、具有4个顶点的无向完全图有一条边

A、6

B、12

C、16

D、20

16、下面程序段的时间复杂性的量级为()。Intfun(int

n){1=1,s=l;While(s<n)S+=++I;ReturnI;}

A、0(n/2)

B、O(logn)

C、0(n)

D、0(nl/2)

17、一趟排序结束后不一定能够选出一个元素放在其最终位置上的是()0

A、堆排序

B、冒泡排序

C、快速排序

D、归并排序

18、在存储结构上，如果用带头节点单链表实现队列(假定front和rear分别

为队首和队尾指针)，则删除一个结点的操作为

A、front.next=front.next,next

B、rear=rear.next

C、rear=front.next

D、front=front,next

19、通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着

()o

A、数据具有同一特点

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

一致

C、每个数据元素都一样

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

20、排序方法中，从未排序序列中依次取出元素与已排序序列(初始时为空)

中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为()

A、希尔排序

B、起泡排序

C、插入排序

D、选择排序

21、高度为n、结点数也为n的二叉树，共有()棵。

A、n

B、2n-l

C、n-1

D、2n-l

22、一个顺序栈S,其栈顶元素下标为top,则将元素e入栈的操作是(),,

(4.0分)

A、S[top]=e;top++;

B、top++;S[top]=e;

C、S[top]=e;

D>S[top]=e;

23、下列程序的时间复杂度是()。

For(i=l;i<=n;++i){for(j=l;j<=n;++j){c[i][j]=0;}}

A、0(n*n)

B、0(n)

C、0(2n)

D、0(2n*n)

24、无向图的邻接矩阵是-一个(B)。

A、对角矩阵

B、对称矩阵

C、上三角矩阵

D、零矩阵

25、(3分)下列选项中,其平均查找性能与基于二叉排序树的查找相当的是

(A)o

A、二分查找

B、顺序查找

C、分块查找

D、索顺序查找

26、在一个图中，所有顶点的度数之和等于所有边数的()倍

A、1212122020年1月2日

B、1

C、2

D、3

27、栈的插入与删除操作在()进行。(4.0分)

A、栈顶

B、栈底

C、任意位置

D、指定位置

28、设图G中顶点数为n,则图G至少有()条边。

A、0

B、n

C、n（n-l）/2

D>n（n-1）

29、（4分）判定一个队列QU（最多元素为m）为空的条件是（C）。

A、QU->rear-QU->front==m

B、QU->rear-QU->front-1==m

C、QU->front==QU->rear

D、Q（J->front==QU->rear+l

30、用链表方式存储的队列，在进行删除运算时（）。

A、仅修改头指针

B、仅修改尾指针

C、头、尾指针都要修改

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

31、算法的计算量的大小称为计算的（）<,

A、效率

B、复杂性

C、现实性

D、难度

32、图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。

A、前序，栈

B、层次，栈

C、前序，队列

D、层次，队列

33、顺序表中第一个元素的存储地址是100,每个元素的长度为2,则第五个元

素的地址是（）

A、110

B、108

C、100

D、120

34、在一个顺序循环队列中，队尾指向队尾元素的（）位置。

A、前一个

B、后一个

C、当前

D、最后

35、在一棵二叉排序树上按（）遍历得到的结点序列是一个有序序列

A、先序

B、中序

C、后序

D、头序

36、（4分）若栈采用链式存储结构,则下列说法中正确的是（B）。

A、需要判断栈满且需要判断栈空

B、不需要判断栈满但需要判断栈空

C、需要判断栈满但不需要判断栈空

D、不需要判断栈满也不需要判断栈空

37、对于顺序循环队列，以下说法正确的是（）

A、无法判断队列是否为空

B、无法判断队列是否为满

C、队列不可能满

D、以上说法都不对

38、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）

A、接层遍历

B、中序遍历

C、先序遍历

D、后序遍历

39、设一组初始记录关键字序列为（Q,H,C,Y,P,A,M,S,R,D,F,X）,

则按字母升序的第一趟冒泡排序结束后的结果是（）。

A,F,H,C,D,P,A,M,Q,R,S,Y,X

B、P,A,C,S,Q,D,F,X,R,H,M,Y

C、A,D,C,R,F,Q,M,S,Y,P,H,X

D、H,C,Q,P,A,M,S,R,D,F,X,Y

40、设广义表L=（（a,b,c））,则L的长度和深度分别为（）。

A、1和1

B、1和3

C、1和2

D、2和3

41、在二叉排序树的（）序列是一个递增有序序列。

A、先序遍历

B、中序遍历

C、后序遍历

D、层次遍历

42、具有4个顶点的无向完全图有（）条边

A、6

B、12

C、18

D、20

43、以下说法错误的是（）0

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

式存储结构时实现的效率低

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

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

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

44、根据线性表链式存储结构中每一个结点包含的指针数，将线性链表分成

()

A、单链表与循环链表

B、单链表与十字链表

C、单链表与双链表

D、循环链表与多链表

45、(4分)在一个单链表中,若删除p指向结点的后继结点,则执行的操作为

(A)o

A、q=p->next;p->next=p->next->next;free(q)

B、p=p->next;q=p->next;p=q->next;fe(e)

C、q=p->next->next;p=p->next;free(q)

D、p=p->next->next;q=p->next;feeq)

46、设一棵4叉树中有N1个度数为1的结点,N2个度数为2的结点,……,N4个

度数为4的结点,则该树中共有()个叶子结点。

A、N1+N2

B、N1+2*N2+3*N3

C、N2+N3+4*N4

D、N2+2*N3+3*N4+1

47、如果让元素1,2,3,4,5,6,7依次进栈，则出栈次序不可能出现()的情况

A、1,2,3,4,5,6,7

B、7,6,1,4,3,2,5

C、3,2,1,4,5,6,7

D、1,2,3,4,5,7,6

48、对n个不同的关键字进行递增冒泡排序,在下列哪种情况下比较的次数最多

()。

A、元素无序

B、元素递增有序

C、元素递减有序

D、都一样

49、时间复杂度不受数据初始状态影响而恒为0(nlog2n)的是()。

A、堆排序

B、冒泡排序

C、选择排序

D、快速排序

50、设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多

比较次数不超过()o

A、log2(n)+1

B、log2(n)-1

C、log2(n)

D、log2(n+1)

参考答案及解析

一、单项选择题

1、C

2、D

3、A

4、D

5、A

6、A

7、D

8、A

9、C

10、C

11、C

12、D

13、C

14、B

15、A

16、D

17、D

18、A

19、B

20、C

21、B

22、B

23、A

24、B

25、A

26、C

27、A

28、A

29、C

30、D

31、B

32、D

33、B

34、B

35、B

36、B

37、D

38、C

39、D

40、C

【解析】解释：广义表的深度是指广义表中展开后所含括号的层数，广义表的长度是指

广义表中所含元素的个数。根据定义易知L的长度为1,深度为2。

41、B

42、A

43、D

44、C

45、A

46、D

47、B

48、C

49、A

50、A

数据结构模拟(四)

一、单项选择题(100题)

1、采用邻接表存储的图的深度优先遍历算法类似于二叉树的。

A、按层遍历

B、前序遍历

C、中序遍历

D、后序遍历

2、设计一个判别表达式中左右括号是否配对出现的算法，采用()数据结构最

佳。

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

B、队列

C、栈

D、线性表的链式存储结构

3、计算机算法必须具备输入、输出、()等5个特性。

A、可行性、可移植性和可扩展性

B、可行性、确定性和有穷性

C、确定性、有穷性和稳定性

D、易读性、安全性和稳定性

4、串是()。

A、少于一个字母的序列

B、任意个字母的序列

C、不少于一个字符的序列

D、有限个字符的序列

5、设散列表中有m个存储单元，散列函数H(key)=key%p,则p最好选择

()o

A、小于等于m的最大奇数

B、小于等于m的最大素数

C、小于等于m的最大偶数

D、小于等于m的最大合数

6、用链表表示线性表的优点是()。

A、便于随机存取

B、占用的存储空间较顺序表少

C、便于进行插入和删除操作

D、元素的物理顺序与逻辑顺序相同

7、广义表A=((a),a)的表头是()。

A、a

B、(a)

C、b

D、((a))

8、树的后序遍历等价于该树对应二叉树的。

A、层次遍历

B、前序遍历

C、中序遍历

D、后序遍历

9、(3分)某索引顺序表共有元素395个，.平均分成5块。若先对引表采用顺序

查找,再对块中元素进行顺序查找,则在等概率情况下,分块查找成功的平均查找

长度是(A)。

A、43

B、79

C、198

D、200

10、给定一段文本中的4个字符(u,v,w.x)及其出现频率(fu,fv,fw,

fx),若对应的哈夫曼编码为u:00,v:010,w:011,x:l,则下列哪组频率可能对

应(fu,fv,fw.fx)?(B)o

A、15,23,16,45

B、30,12,20,33

C、41,12,20,32

D、55,22,18,46

11、对于长度为18的顺序存储的有序表，若采用二分查找，则查找第15个

元素的查找长度为()。(1分)

A、3

B、4

C、5

D、6

12、一棵二叉树的第7层上最多含有的结点数为。

A、4

B、64

C、127

D、128

13、(6分)若希望1000个无序元素中尽快求得前10个最大元素,应借用(A)o

A、堆排序

B、快速排序

C、冒泡排序

D、归并排序

14、下列程序段的时间复杂度为()。For(i=0;i<m;i++)for(j=0;

j<t;j++)c[i][j]=0;For(i=0;i<m;i++)for(j=0;j<t;

j++)for(k=0;k<n;k++)

c[i][j]=c[i][j]+a[i][k]*b[k][j];

A、0(m*n*t)

B、0(m+n+t)

C、0(m+n*t)

D、0(m*t+n)

15、最大容量为maxsize的循环队列，队尾指针是rear,队头是front,则

队满条件为()

A、(rear+1)maxsize==(front+1)maxsize

B、(front+1)maxsize==rear

C、(rear+1)maxsize==front

D、rear==front

16、一个有序表为｛1,3,9,12,32,41,45,62,75,77,82,95,100),

当用二分查找值为82的结点时，查找成功时的比较次数为()。(1分)

A、1

B、2

C、4

D、8

17、单链表不具备的特点是()0(3.0分)

A、插入.删除不需要移动元素

B、链表长度可动态增长

C、所需空间与线性长度成正比

D、可随机访问任一个元素

18、(6分)在下列排序方法中，记录关键字比较的次数与记录的初始排列次序无

关的方法是(D)。

A、直接插入排序

B、冒泡排序

C、希尔排序

D、直接选择排序

19、设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，all

为第一元素，其存储地址为1,每个元素占一个地址空间，则a85的地址为

()。

A、13

B、32

C、33

D、40

20、对于线性表(7,34,55,25,64,46,20,10)进行散列存储时，若选用

H(K)=K附作为散列函数，则散列地址为1的元素有()个.

A、1

B、2

C,3

D、4

21、若已知一个栈的入栈序列是1,2,3,..,n,其输出序列为pl,p2,p3,…,pn,

若pl=n,则pn为()o

A、1

B、n

C、n/2

D、n-1

22、(3分)若某二叉树的后序遍历序列为dabec,中序遍历序列是debac,则它的

前序遍历序列是(B)。

A、acbed

B、cedba

C、deabc

D、decab.

23、串的长度是指()。

A、串中所含不同字母的个数

B、串中所含字符的个数

C、串中所含不同字符的个数

D、串中所含非空格字符的个数

24、将序列(100,80,90,60,120,110,130,1,2,3)生成二叉排序树,则该树的高度

为

A、4

B、5

C、6

D、7

25、递归函数调用时，处理参数及返回地址，要用一种称为()的数据结构。

A、队列

B、多维数组

C、栈

D、线性表

26、串“ababaaababaa”的next数组为()。

A、012345678999

B、012121111212

C、011234223456

D、0123012322345

27、深度为h的满m叉树的第k层有（）个结点。（IWkWH）

A、mk-1

B、mk-1

C>mh-1

D、mh-l

28、表长为n的顺序存储的线性表，当在任意位置上插入或删除一个元素的概

率相等时，插入一个元素所需移动元素的平均个数为（D、），删除一个元素需

要移动元素的平均个数为（）

A、（n-l）/2

B、n

C、（n+l）/2

D、n/2

29、（3分）在一非空二叉树的中序遍历序列中,根结点的右边（A）o

A、只有右子树上的所有结点

B、只有右子树.上的部分结点

C、只有左子树上的部分结点

D、只有左子树上的所有结点

30、高度为5（不设计外部结点）的3阶B-树至少有（）个结点。

A、32

B、31

C、64

D、108

31、G是一个简单的非连通无向图，共有28条边，则该图至少有（）个顶

点。

A、6

B、7

C、8

D、9

32、序列⑵5,4,1,8,6,7,3｝是第一趟递增排序后的结果，则采用的排序方法可

能是（）。

A、快速排序

B、冒泡排序

C、堆排序

D、直接插入排序

33、在带权图的最短路径问题中，路径长度是指。

A、路径上的顶点数

B、路径上的边数

C、路径上的顶点数与边数之和

D、路径上各边的权值之和

34、数据的基本单位（）

A、数据结构

B、数据元素

C、数据项

D、文件

35、设一个顺序有序表A[l:14]中有14个元素，则采用二分法查找元素A[4]的

过程中比较元素的顺序为（）o

A、A[l],A[2],A[3],A[4]

B,A[l],A[14],A[7].,A[4]

C、A[7],A[3],A[5],A[4]

D、A[7],A[5],A[3],A[4]

36、向一个栈顶指针为HS的链栈中将一个S指针所指的结点入栈，执行（）。

A、HS->next=s

B、S->next=HS->next;HS->next=s

C、S->next=HS;HS=s

D、S->next=HS;HS=HS->next

37、（4分）从一个栈顶指针为HS的链栈中删除一个结点时,用x保存被删结点的

值,则执行⑻。

A、x=HS;HS=HS->next;

B、x=HS->data;

C、HS=HS->next;x=HS->data;

D>x=HS->data;HS=HS->next;

38、给定一个无序的单链表,要求的空间复杂度为0（1）,则建立一个长度为n的

有序单链表的时间复杂度为（）

A、0（n）

B、0（1）

C、0（n、2）

D、0（log2n）

39、非空的循环单链表head的尾结点（由p所指向）满足

A、p->next==NULL

B、p==NULL

C、p->next==head

D>p==head

40、下列关于算法输出的叙述中，正确的是（）。

A、算法一定没有输出

B、算法可以没有输出

C、算法至少有一个输出

D、算法必须有多个

41、链式栈结点为：（data,link）,top指向栈顶.若想摘除栈顶结点，并将删

除结点的值保存到x中，则应执行操作（）o

A、x=top->data;top=top->link；

B、top=top->link;x=top->link；

C、x=top;top=top->link；

D>x=top->link；

42、算法是（）。

A、计算机程序

B、解决问题的计算方法

C、排序算法

D、解决问题的有限运算序列

43、在一棵二叉树中,度为0的结点数为nO,度为2的结点数为n2,则n0=（）

A、n2-2

B、n2-l

C、n2+l

D、n2+2

44、在单链表结点p之后插入结点s,正确的操作是（）。（3.0分）

A、p.next=s;s.next=p.next;

B、s.next=p.next;p.next=s;

C、p.next=s;p.next=s.next;

D>p.next=s.next;p.next=s;

45、将数组称为随机存储结构是因为（）o

A、数组元素是随机的

B、随时可以对数组元素进行访问

C、对数组的任一元素的存取时间是相等的

D、数组的存储结构是不定的

46、设森林F中有三棵树，第一，第二，第三棵的结点个数分别为Ml,M2,M3。与

森林F对应的二叉树根节点的右子树的个数是（）。（3.0分）

A、Ml

B、M1+M2

C、M3

D、M2+M3

47、设有序表中的元素为（13,18,24,35,47,50,62）,则在其中利用二分

法查找值为24的元素需要经过（）次比较。

A、1

B、2

C、3

D、4

48、（4分）栈结构通常采用的两种存储结构是（A）。

A、顺序存储结构和链表存储结构

B、散链方式和索引方式

C、链表存储结构和数组

D、线性存储结构和非线性存储结构

49、（4分）下列关于队列的叙述中，错误的是（D）。

A、队列是一种先进先出的线性表

B、队列是-种后进后出的线性表

C、循环队列中进行出队操作时要判断队列是否为空

D、在链队列中进行入队操作时要判断队列是否为满

50、抽象数据类型的三个组成部分分别为（）。

A、数据对象、数据关系和基本操作

B、数据元素、逻辑结构和存储结构

C、数据项、数据元素和数据类型

D、数据元素、数据结构和数据类型

参考答案及解析

一、单项选择题

1、B

2、C

3、B

4、D

5、B

6、C

7、B

8、C

9、A

10、B

11、B

12、B

13、A

14、A

15、C

16、D

17、D

18、D

19、C

20、D

21、A

22、B

23、B

24、C

25、C

26、C

27、A

28、D

29、A

30、B

31、D

32、D

33、D

34、B

35、C

36、B

37、D

38、C

39、C

40、C

41、A

【解析】解释：x=top->data将结点的值保存到x中，top=top->link栈顶指针指向栈顶

下一结点，即摘除栈顶结点。

42、D

43、C

44、B

45、B

46、D

47、C

48、A

49、D

50、A

数据结构模拟（五）

一、单项选择题（100题）

1、假定利用数组A[N]顺序存储一个栈，top表示栈顶指针，已知栈未满，则X

入栈时所执行的操作是（）o

A、a[-top]=x;

B、a[top--]=x

C、a[++top]=x

DNa[top++]=x

2、若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素算

法的时间复杂度（）o

A、0（log2n）

B、0（1）

C、0（n）

D、0（rT2）

3、设T是赫夫曼树，具有5个叶结点，树T的高度最高可以是（）

A、2

B、3

C、4

D、5

4、循环队列S为满的条件是（）。

A、S->rear==S->front

B、S->rear+l）%maxsiae==s->front

C、S->rear==0

D、s->front==0

5、已知输入序列为abed经过队列后能得到的输出序列有（）

A、dacb

B、abed

C、deba

D>cadb

6、假设以数组A[60]存放循环队列的元素，其期指针是front=47.当前队列有

50个元素,则队列的尾指针值为（B）o

A、3

B、37

C,50

D、97

7、(3分)如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是

T2中结点的(B)。

A、前序

B、中序

C,后序

D、层序

8、顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为()。

A、0(n)

B、0(n2)

C、0(n/2)

D、0(log2n)

9、下面属于整数类I的实例的是()

A、229

B、0.229

C、229E-2

D、"229”

10、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为

()o

A、第i行非0元素的个数之和

B、第i列非0元素的个数之和

C、第i行0元素的个数之和

D、第i列0元素的个数之和

11、计算机内部数据处理的基本单位是()

A、数据

B、数据元素

C、数据项

D、数据库

12、(3分)下列关于哈夫曼树的叙述中，错误的是(A)。

A、用n个结点构造的哈夫曼树是唯一的

B、哈夫曼树中只有度为0或度为2的结点

C、树中两个权值最小的结点可能是兄弟结点

D、同-结点集构造的二叉树中，哈夫曼树的WPL最小

13、一个算法应该是()。

A、程序

B、问题求解步骤的描述

C、要满足五个基本特性

D、A和C.

14、从表中任一结点出发，都能扫描整个表的是()。

A、单链表

B、顺序表

C、循环链表

D、静态链表

15、