数据结构模拟2--带答案.doc

数据结构 模拟题2
一、判断题。判断下列各题是否正确，若正确，在答题卡中涂“A”，否则涂“B”。
1．线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。Χ
2．线性表的链式存储结构优于顺序存储结构。Χ
3．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。Χ
4．顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。Χ
5．链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。Χ
6．两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。√
7．在循环队列中，元素的个数为rear-front。Χ
8．完全二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。√
9．邻接表存储结构只用于有向图的存储，邻接矩阵对有向图和无向图的存储都适用。Χ
10．连通分量是无向图中的极小连通子图。Χ
11．没有回路的图能进行拓扑排序。√
12．生成树指的是图的极大连通子图。Χ
13．采用折半查找法对有序表进行查找总比采用顺序查找法对其进行查找要快。Χ
14．采用线性探测法处理冲突时，当从哈希表中删除一个记录时，不应将这个记录的所在位置的数据置空，因为这样会影响以后的查找。√
15．对于给定的关键字集合，以不同的次序插入到初始为空的二叉排序树中，得到的二叉排序树是相同的。Χ
二、单选题。
1．数据结构可以分为三大类，它们是【 】、树和图。A
A、线性表 B、栈和队列 C、链表 D、顺序表
2．下列程序段的时间复杂度为【 】。A
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、 O(m*n*t) B、 O(m+n+t) C、 O(m+n*t) D、 O(m*t+n)
3．若线性表的最常用的操作是存取第i个元素及其前驱元素的值，则采用【 】存储方式最省时间。D
A、单链表 B、双链表 C、单循环链表 D、顺序表
4．线性表L在【 】情况下适用于使用链式结构实现。D
A、L中含有大量的结点 B、L中结点结构复杂
C、需经常修改L中的结点值 D、 需不断对L进行删除插入
5．顺序表的存储密度【 】。B
A、大于1 B、等于1 C、小于1 D、不能确定
6．设顺序表表长为n，并在任意位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中【 】个元素。A
A、 B、 C、 D、n
7．建立一个长度为n的有序单链表的时间复杂度为【 】。C
A、 O(n) B、 O(1) C、 O(n2) D、 O(log2n)
8．带头结点的单链表H为空的条件是【 】。A
A、H->next==NULL B、H->next=NULL C、H.next==NULL D、H.next=NULL
9．若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为【 】。C
A、i B、n=i C、n-i+1 D、不确定
10．设用链表作为栈的存储结构则退栈操作【 】。B
A、 必须判别栈是否为满 B、 必须判别栈是否为空
C、 判别栈元素的类型 D、 对栈不作任何判别
11．用链接方式存储的队列，在进行插入运算时【 】。D
A. 仅修改头指针 　 B. 头、尾指针都要修改
C. 仅修改尾指针 D.头、尾指针可能都要修改
12．一个数组第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是【 】。 C
A、110 B、108 C、100 D、120
13．假设有二维数组A6×8，行列下标均从0开始，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，若按行存储时，元素A14的第一个字节地址为 【 】。C
A、72 B、150 C、1072 D、1150
14．二叉树是非线性数据结构，所以【 】。C
A、它不能用顺序存储结构存储 B、它不能用链式存储结构存储
C、顺序存储结构和链式存储结构都能存储
D、顺序存储结构和链式存储结构都不能使用
15．具有n(n>0)个结点的完全二叉树的深度为【 】。C
A、élog2(n)ù B、ë log2(n)û C、ë log2(n) û+1 D、élog2(n)+1ù
16．后序遍历的顺序是【 】。C
A、根结点，左子树，右子树 B、左子树，根结点，右子树
C、左子树、右子树，根结点 D、根结点，右子树，左子树
17．一棵二叉树的后序遍历序列为DEBFCA，中序遍历的序列为DBEAFC，则先序遍历的序列是【 】。A
A、ABCDEF B、DECABF C、DEAFBC D、CFEDBA
18．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为31的结点的双亲结点的编号为 【 】。A
A、15 B、16 C、62 D、63
19．对二叉树从1开始连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用【 】次序的遍历实现编号。C
A、先序 B、中序 C、后序 D、逐层遍历
20．设某棵二叉树中有2000个结点，则该二叉树的最小高度为【 】。C
A、 9 B、 10 C、 11 D、 12
21． 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10，其构造哈夫曼编码时所对应的哈夫曼树为【 】。A

22．设F是一个森林：B是由F转换得到的二叉树，F中有n个非终端结点，B中右指针域为空的结点有【 】个。A
A、n-1 B、n C、n+1 D、n+2
23．如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是【 】。D
A、0 1 3 2 B、0 2 3 1
C、0 3 2 1 D、0 1 2 3

24．已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是【 】。 A

A、0 3 2 1 B、0 1 2 3 C、0 1 3 2 D、0 3 1 2
25．下图从源点V0到V4的最短路径长度为【 】。A
A、60 B、90 C、100
26．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为【 】。A
A、 O(n) B、 O(n2) C、 O(n1/2) D、 O(1og2n)
27．链表适用于【 】查找。A
A、顺序 B、二分法 C、顺序，也能二分法 D、随机
28．折半查找有序表（14，26，30，42，50，53，70，88，100）。若查找表中元素58，则它将依次与表中【 】比较大小，查找结果是失败。D
A、50，26，14 B、50，70，88，100
C、50，26，30，42 D、50，70，53
29．长度为10的有序表进行折半查找时，查找位置4上的元素需要依次和【 】位置上的比较。A
A、5,2,3,4 B、6,3,4 C、5,2,3,4 D、不一定
30．具有10个元素的有序表进行折半查找时，其判定树为【 】。A
A、 B、
C、 D、
31．关于哈希查找中说法正确的是【 】。D
A、哈希查找的平均查找长度为0
B、用开放定址法处理冲突的哈希表在对某元素做删除时，只要将元素置空即可
C、好的哈希函数可以避免任何冲突
D、装载因子越大冲突的可能性也越大
32．设哈希表长为14，哈希函数为H(k)＝k%11。当前表中已有4个结点：
addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7
如果使用二次探测再哈希法处理冲突，则关键字为49的结点的地址为【 】。D
A、8 B、3 C、5 D、9
33．设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为【 】。A
A、10，15，14，18，20，36，40，21 B、 10，15，14，18，20，40，36，21
C、 10，15，14，20，18，40，36，2l D、15，10，14，18，20，36，40，21
34．设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（ ）。D
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
35．初始序列已经按键值有序时，用冒泡算法进行排序，需要比较的次数最少为【 】。D
A、n2 B、nlog2n C、log2n D、n-1