数据结构三套试卷详细分析.docx

数据结构试卷（一）

一、单选题（每题2分，共20分）

栈和队列的共同特点是( A )。A.只允许在端点处插入和删除元素B.都是先进后出

C.都是先进先出

D.没有共同点

Ps:栈：先进后出；队列：先进先出

用链接方式存储的队列，在进行插入运算时(D ).

A.仅修改头指针 B.头、尾指针都要修改

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

ps:新结点的插入和栈顶结点的删除都在链表的表头，即栈顶进行。如果队列为空，即第一个结点为null，那么插入时改变了头指针。

以下数据结构中哪一个是非线性结构？(D )

A.队列 B.栈 C.线性表 D.二叉树

Ps：数据结构=逻辑结构+存储结构。二叉树属于层次关系——树结构。

设有一个二维数组 A[m][n]，假设A[0][0]存放位置在644

(10)

，A[2][2]存放位置在

676

，每个元素占一个空间，问A[3][3]

存放在什么位置？脚注

表示用10进制

(10)

表示。C

(10)

(10)

A．688 B．678 C．692 D．696

Ps：此题画个图即知。可知A[0][2]的存放位置是646，A[2][1]的存放位置是661，因为A[2][2]的存放位置在 676，可知两层之差为 15，然后即可知道 A[3][3]的存放位置在676+15+1=692.

树最适合用来表示( C )。

A.有序数据元素 B.无序数据元素

C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据Ps：树属于层次关系，所以可表示元素之间具有分支层次关系的数据。

二叉树的第k层的结点数最多为(D).

A．2k-1 B.2K+1 C.2K-1 D.2k-1

Ps:二叉树的性质一：在二叉树的第k（k=1）层最多有2k-1 个结点。

若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( D )

A.1，2，3 B.9，5，2，3

Ps：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。本题分析思路：首先18个元素是在有序表中的，即将它放入一维数组中的时候是有顺序的。则，第一个比较应该是（1+18）/2=9；第二次比较应该是(1+9)/2=4

Ps：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。本题分析思路：首先18个元素是在有序表中的，即将它放入一维数组中的时候是有顺序的。则，第一个比较应该是（1+18）/2=9；第二次比较应该是(1+9)/2=4；第三次比

较应该是(1+4)/2=2，接下来就是3了。

对n个记录的文件进行快速排序，所需要的辅助存储空间大致为C

A.O（1） B.O（n） C.O（1ogn） D.O（n2）

2

Ps:快速排序是需要一个辅助空间的，该空间的大小最好为c选项，最差情况为B选项，本

题选C

9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）

=K%9作为散列函数，则散列地址为1的元素有（ D）个，

A．1 B．2 C．3 D．4Ps：散列函数即为将要进行散列存储的数进行一系列的运算，然后将它们确定在散列表中，本题只需将线性表中的数都用H(K)进行计算，然后结果为1的数有几个即为答案。%是取余。

10.设有6个结点的无向图，该图至少应有( A )条边才能确保是一个连通图。

A.5 B.6 C.7 D.8

Ps：连通图是每两个结点都有一条边相连，没有任何孤立结点。所以6个结点的无

向图至少应该有5条边。