《数据结构基础练习(线性表)》由会员分享，可在线阅读，更多相关《数据结构基础练习(线性表)（5页珍藏版）》请在金锄头文库上搜索。
1、数据结构基础练习（线性表）学号姓名班级.一、选择题1. 算法的时间复杂度取决于A A. 问题的规模B.变量的多少 C.问题的难度D. A和E2. 算法能正确的实现预定功能的特性为算法的A oA. 正确性B.易读性C.健壮性D.高效性3. 数据的物理结构主要包含A这几种结构。A. 顺序结构和链表结构B.线性结构和非线性结构C.动态结构和静态结构D.集合、线性结构、树形结构、图形结构4. 数据在计篦机内存中的表示是指A 。A.数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系5. 数据结构被形式化定义为二元组（D, S）,其中D是_ B 的有限集合。A.算法B.数据元素C.数据操作
2、D.数据关系6. 算法效率的度量是D 。A.正确度和简明度B.数据复杂度和程序复杂度C.高的速度和正确度D.时间复杂度和空间复杂度7. 在卞列存储结构中，最适合实现在线性表中进行随机访问的是_A 。A.数组B.双向链表C.单向链表 D.循坏链表8. 与单链表相比，双链表的优点之一是_D 。A.可以由最后一个结点找到头结点B.可随机访问C.插入、删除操作更加简单D.访问前驱结点更加方便9. 如果对线性表的运算只有2种，即删除第一个元素，在最后一个元素的后面插入新元素, 则最好使用 D 。A.顺序表 B.单链表 C.双向链表 D.具有表尾指针的循环单链表10. 在表头指针为head且表长人于1的单
3、向循环链表中，指针p指向表中的某个结点， 若 p-next-next= = head,则 D 。A. p指向头结点B. p指向尾结点C.*p的直接后继是头结点D.*p的直接后继是尾结点11. 带表头附加结点的单链表head为空的判断条件是C A. head =NULLB. head-next= = NULLC. head-next= = headD. head!=NULL12. 对线性表，在下列情况下应当采用链表表示的是一B 。A. 经常需要随机地存取元素B. 经常需要进行插入和删除操作C. 表中元素需要占据一片连续的存储空间D. 表中的元素个数不变13. 如果最常用的操作是取第i个结点及前驱
4、，则采用 A存储方式最节省时间。A.顺序表B.双链表 C.单循坏链表D.单链表14. 可以用带表头附加结点的链表表示线性表，也可以用不带表头附加结点的链表表示线性表，前者最主要的好处是_B 。A.可以加快对表的遍历B.使空表和非空表的处理统一C.节省存储空间D.可以提高存取表元素的速度15. 一个顺序表所占存储空间的大小与D 无关。A.顺序表长度B.结点类型C.结点中个数据域的类型D.结点的存放次序16. 从一个具n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平 均比较 D 个结点。A. nB. n/2C. (n-l)/2D. (n+l)/217. 单链表中，q在前,p在后的
5、指向相邻的两个结点，要在q,p之间插入s所指的结点应 是一 D 。A. s-next=p-next; p-next=s; B. p-next=s-next; s-next=p;C. p-next=s; s-next=q;D. q-next=s; s-next=p;18. 不带表头附加结点的单链表head为空的判断条件是一B A. head-next=NULLB. head = = NULLC. head-next=headD. head! = NULL19. 一个循环单链表中，若要在指针q所指结点的后面插入一个由指针P所指向的结点， 则执行 D A. qnext=p； pnext=qnext：
6、B. pnext=qnext； q = p；C. qnext=pnext； pnext=q：D. pnext=qnext； qnext=p；20. 在循环双链表的指针p所指结点之前插入指针q所指结点的操作是一D A. p-left=q; q-ight=p; p-left-right=q; q-left=p-left;B. p-left=q; p-left-right=q; q-right=p; q-left=p-left;C. q-right=p; q-left=p-left; p-left=q; p-left-right=q;D. q-right=p; q-left =p-left; p-l
7、eft-right=q; p-left=q;二、算法设计题1. 设有一个顺序表L,其元素为整型数据，下列算法将L中所有小于0的整数放在前半部 分，人于0的整数放在后半部分。提示：从L的两端查找，前端找人于0的数据，后端找 小于0的数据，然后将两位置的数据交换。void MoveList(SeqList &L)int i=Oj=L.size-l;wlule(ij)while(L.listi0)j 一；temp=L.listi;Listi=L.listj;L.listj=temp;2. 编写一个函数，实现从单链表中查找出所有元素的最人值，该值由函数返回，若单链表 为空，则显示出错信息并停止运行。E
8、lemType FmdMax(LNode *H)LNode *p=H-next;if(p=NULL)cout线性表为空，操作无效！”endl;return 0:int max=p-data;while(p !=NULL)if(p-datamax)niax=p-data;p=p-next;return max;3. 设h为不带头结点的单链表，写出和下列递归过程等价的非递归程序。void func(LNode *h)if(h! = NULL) func(h-n ext); coutdata;算法的功能：逆序输出链表各结点的信息void func(LNode *&h)LNode *p=NULL, *
9、q=h, *r;wlule(q?=NULL)r=q-next;q-next=p;p=q；q=r;h=p；4. 编写一个在带头结点的单链表中删除一个最小值节点的算法(假设该链表中每个节点的 值不重复)。bool DeleteMm(LNode *&H)LNode *p=H,*q=H-next;LNode if(q=NULL)cen,线性表为空，操作无效！ ”endl;return false;int miii=q-data;while(q! =NULL) if(q-datadata;m=p;n=q; elsep=q； q=q-next;m-next=n-next; return tine;5. 假设有一个循环链表的长度大于1,且表中既无头结点也无头指针。已知s为指向链表 某个结点的指针，编写算法在链表中删除指针s所指结点的前驱结点。void Delete(LNode *&S)if(S=NULL)return;LNode *p=S,*q;while(p-next-next !=S) p=p-next;q=p-next; next=S;delete q;
