《数据结构》复习题

《《数据结构》复习题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构》复习题一.选择题:1.数据结构是研究数据的（A.理想结构，物理结构C.物理结构，逻辑结构2.纟R成数据的基木单位是（）以及它们之间的相互关系B.理想结构，抽象结构D.抽彖结构，逻辑结构A.数据项B.数据类型C.数据元素D.数据变量3.如果某数据结构的数据元素的集合为S={A,BCD,E,F,G},元素二间的关系为R二{vA,D>,vA,G〉,,,,},则该数据结构是一种（）A.线性结构B.树结构4.线性表的链接实现有利于()运算A.插入B.读表元5.设一数列的输入顺序为1,2,3

2、,4,5,A.3,2,5,6,4,1C.2,4,3,5,1,66.设字符串Sl='ABCDEFG',S2='PQRST'Sub(Sl,Length(S2),2))后结果为(A.'BCQR'B.'BCDEF'C.图结构D.链表结构C.杳找D.定位6通过栈操作不可能排成的输出序列为()B.1,5,4,6,2,3D.4,5,3,6,2,1则运算S=Concat(Sub(Sl,2,Length(S2))>)C.'BCDEFG'D.'BCDEFEF'7.设单链表中指针P指向结点A,若要删除A之后的结点（若存在），则修改指针的操作为（）A

3、.p->next=pfnext—nextC・p=pfnext—next8.线性表采用链式存储时，其地址（A.必须是连续的C.—•定是不连续的9.在内部排序时，排序不稳定的有（B.p=pfnextD.pfnext=pB.部分地址必须是连续的D.连续与否均可以A•插入排序B.冒泡排序C•快速排序D•归并排序10.设有1000个元索，用折半法查找时，最小比较次数为（）A.OB.1C.10D.50011.将一个元素进入队列的时间复杂度是（）A.O(l)B.O(n)C.O(n2)D.O(log2n)12.在一个具有n个结点的单链表中查找

4、其值等x的结点,在查找成功的情况卜,需要比较（）个元素结点A.n/2B.nC.(n+1)/2D.(nJ)/213•从一个长度为n的顺序表中删除第i个元素（lWiWn）,需向前移动（）个元素A.n-iB.n-i+1C.n-i-114.总共3层的完全二叉树，其结点数至少有（）A.3B.4C.715.队列操作的原则是（）A.先进先出B.后进先出C.只能进行插入D.iD.8D.只能进行删除16.若线性表最常用的操作是存取第i个元素及其前驱元素的值，则采用（）存储方式最节省时间A.单链表B.双向链表17.栈和队列都是（）A.顺序存储的线

5、性结构C.链接存储的线性结构18.与线性表的链接存储相符的特性是（A.插入和删除操作灵活C.便于随机访问19.若进队序列为1,2,3,则出队序列是（A.3,2,1B.1,3,2C.音循环链表D.顺序表B•限制存取点的线性结构D.限制存取点的非线性结构）B.需要连续存储空间D.存储密度人）C.1,2,3D.3,2,120.在单向循环链表中，若头指针为h,那么p所指结点为尾结点的条件是（）A.p=NULLB.p->next=NULLC.p=hD.p->next=h二•填充题：1.循环链表的主要优点是O2.一个n切的对称矩阵，如果以

6、行列为主序存入内存，其容量为o3.在双向循环链表中，在指针P所指的结点Z后插入指针f所指的结点,其操作为O4.设有一个空栈，现输入序列为1,2,3,4,5经过push,push,pop,push,pop,push,pop,push输出序歹lJ为>5.一个算法，如果不论问题规模大小运行所需时间都一样，则算法的时间复朵度是o6.数据结构有线性结构，树结构和等几种逻辑结构。7•顺序存储的队列如果不彩用循环方式，则会出现问题。8.在一个长度为n的顺序表中插入一个元素，最少需要移动个元素、最多需耍移动个元素。9.一个数组长度为20,用于

7、存放一个循环队列，则队列最多只有个元素。10.设单链表屮指针p指向结点A,若要删除A之麻的结点（若存在），则需要修改指针的操作为o11.对于一个以顺序实现的循环队列Q[0……m-1],队首，队尾指针分别为f和r,队列判空的条件是。12.直接选择排序算法在最好情况下所做的交换元素的次数为o13.具有64个结点的完全二叉树的深度为o14.已知二叉树中叶子数为50,仅有一个孩子的结点数为30,则总结点数为o15.运算符动态分配一个对象。16.VC++中预定义的两种流对象是和o17.限定符用其所长來声明只读变量。1&类的对象,可作为类

8、的对象处理。19.三种成员访问说明符分别是、和°20.无论对于顺序存储还是链接存储的栈和队列来说，进行插入或删除运算的时间复朵度相同，均为。三.判断题：1.具有线性表关系的集合屮，若a,b是集合屮的任意两个元素，则必有avb的关系（）2.即使某排序算法是不稳定的，但该方法仍有