数据结构综合练习A卷

北京理工大学珠海学院

2010届毕业生《计算机科学技术专业综合》学士学位课

程考试试卷（A）

诚信考试承诺书 专业班级： 本人郑重承诺： 学号： 遵守考场纪律，不存在抄袭及其它违纪行为。 姓名： 承诺人签字： 年 月 日 试卷说明：闭卷，考试时间150分钟 题一 二 三 四 五 六 七 八 九 十 号 得 分

一 二 三 十十十总分 第二部分：共100分

五、单选题（每小题 1分，共20小题，共 20 分） 1、算法分析的目的是（ ）。

A、给出数据结构的合理性 B、研究算法中输入输出的关系 C、空间复杂性和时间复杂性 D、分析算法的效率以求改进 2、线性表是具有N个（ ）的有限序列。 A、表元素 B、字符 C、数据元素 D、数据项

3、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ ）。

1

得分 A、必须是连续的 B、大部分地址必须是连续的 C、连续或不连续都可以 D、一定是不连续的 4、对于顺序表，以下说法错误的是（ ）

A、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址

B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列

C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻

D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中 5、一棵有124个叶结点的完全二叉树，最多有（ ）个结点 A、247 B、248 C、249 D、250 6、向一个栈顶指针为HS的链栈中(有头结点)插入一个s结点，则执行（ ）

A、HS->next=s; B、s->next=HS;HS=s; C、s->next=HS->next;HS->next=s; D、s->next=HS;HS=HS->next; 7、一个栈的入栈序列为a，b，c，则出栈序列不可能的是( )。 A、c,b,a B、b,a,c C、c,a,b D、a,c,b 8、循环队列SQ采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front和rear，则判定此循环队列为满的条件是（ ） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 9、对线性表进行折半搜索时，要求线性表必须（ ）

A、以链接方式存储且结点按关键码有序排列 B、以数组方式存储

2

C、以数组方式存储且结点按关键码有序排列 D、以链接方式存储 10、下面结论正确的是（ ）。

A、一个广义表的表头肯定不是一个广义表 B、一个广义表的表尾肯定是一个广义表

C、广义表L=（（A，B））的表头为空表 D、广义表中原子个数即为广义表的长度

11、串是一种特殊的线性表，其特殊性体现在（ ）。

A、可以顺序存储 B、数据元素是一个字符 C、可以链接存储 D、数据元素可以是多个字符

12、数组SA中，每个元素的长度为3个字节，行下标I从0到7，列下标J从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（ ）。

A、80 B、100 C、240 D、270

13、若广义表A满足Head(A)=Tail(A)，则A为（ ）。 A、（） B、（（）） C、（（），（）） D、（（），（），（）） 14、对矩阵压缩存储是为了（ ）

A、方便运算 B、节省空间 C、方便存储 D、提高运算速度 15、按照二叉树的定义，具有3个结点的二叉树有（ ）种。

A、3 B、4 C、5 D、6

16、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（ ）。

A、acbed B、decab C、deabc D、cedba 17、哈夫曼树的带权路径长度是（ ）

A、所有结点权值之和 B、所有叶结点带权路径长度之和

3

C、带权结点的值 D、除根以外所有结点权值之和

18、设连通图G的顶点数为n，则G的生成树的边数为（ ）。 A、n-1 B、n C、2n D、2n-1 19、关键路径是事件结点网络中的（ ）。

A、从源点到汇点的最长路径 B、从源点到汇点的最短路径 C、最长的回路 D、最短的回路

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

A、插入排序 B、选择排序 C、快速排序 D、归并排序

六、填空题（每空 1.5 分，共30个空，共 45 分） 得分

1、对于给定的n个元素，可以构造出的逻辑结构有（ ）、（ ）、（ ）和（ ）四种

2、在线性结构中，第一个结点（ ）前趋结点，其余每个结点有且只有（ ）个前趋结点。

3、栈中存取数据的原则（ ），队列中存取数据的原则（ ）。

4、线性表、栈、队列都是（ ）结构，可以在线性表的（ ）位置

插入和删除元素；对于栈只能在（ ）插入和删除元素；对于队列只能在（ ）插入元素和在（ ）位置删除元素。 5、空串是（ ），其长度为（ ）。 6、两个串相等的充分必要条件是（ ）。

7、一个n*n的对称矩阵，如果以行为主序存入内存，则其容量为（ ）。 8、在树型结构中，树根结点没有（ ）结点，其余每个结点有且只有（ ）个前驱结点；叶子结点没有（ ）结点，其余每个结点的后继结点可以

4