广工2015数据结构复习题目及答案

数据结构 -C 语言版》第一章 绪论单项选择题1．在数据结构中，数据的基本单位是 ________2．数据结构中数据元素之间的逻辑关系被称为__ ___ 。

A. 数据的存储结构B. 数据的基本操作C. 程序的算法3．在数据结构中，与所使用计算机无关的是数据的 ________ ___。

A. 存储结构B. 逻辑和物理结构C. 逻辑结构4．在链式存储结构中，数据之间的关系是通过 _______ ___ 体现的。

A. 数据在内存的相对位置B. 指示数据元素的指针C. 数据的存储地址D. 指针5．计算算法的时间复杂度是属于一种 ______ ___。

A. 事前统计的方法B. 事前分析估算的方法C. 事后统计的方法D. 事后分析估算的方法6．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是A. n 2B. nlognC. nD. logn7.设使用某算法对 n 个元素进行处理，所需的时间是T(n)=100nlog 2n+200n+2000，则该算A. 数据项B. 数据类型C. 数据元素D. 数据变量D. 数据的逻辑结构D. 物理结构法的渐近时间复杂度为_____ ___。

A. O(1)B. O(n)C. O(200n)D. O(nlog2n)CDCBBDD第二章线性表单项选择题1 •链表不具有的特点是 ___________ 。

A.可随机访问任一元素B.插入和删除时不需要移动元素C.不必事先估计存储空间D.所需空间与线性表的长度正比2.设顺序表的每个元素占 8个存储单元。

第1个单元的存储地址是 100，则第6个元素占用的最后一个存储单元的地址为 ______________ 。

3 •在线性链表存储结构下，插入操作算法 ________________ B. p_>next = p_>n ext;D. p = p->n ext; p->n ext = p->n ext- >n ext;5 .将长度为n 的单链表接在长度为 m 的单链表之后的算法时间复杂度为 __________________ A. 0( n)B. 0(1)C. 0(m)D. 0(m+n)6 •需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是 ________A.单链表B.静态链表C.线性链表D.顺序存储方式ACCABB 填空题1 •在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的 ____ 结点。

2 •在单链表中，指针 p 所指结点为最后一个结点的条件是 _____________ 。

3 •将两个各有n 个元素的有序表归并成一个有序表，其最少的比较次数是 __________________ 4•在一个长度为n 的顺序表中第i 个元素(1 < i < n )之前插入一个元素时，需向后移动元 素的个数是 ___________________ 。

5.在长度为n 的顺序表中插入一个元素的时间复杂度为 _______________A. 139B. 140C. 147D. 148A.需要判断是否表满 C.不需要判断表满 4 •在一个单链表中，若删除B.需要判断是否表空D.需要判断是否表空和表满p 所指结点的后继结点，则执行A. p->n ext = p->n ext- >n ext;C. p = p->n ext- >n ext;1前驱2 _p-> next==NULL3.14. n-i+15.0( n)例题解析【例2-1】编写一个算法将一个单链表逆转，要求在原表上进行，不允许重新建链表。

解：该算法可以在遍历原表的时候将各结点的指针逆转，从原表的第一个结点开始，头结点的指针在最后修改成指向原表的最后一个结点，即新表的第一个结点。

实现本题功能的函数如下：void inverse(Lnode *h){s=h->next;if(s==NULL) return;q=NULL;p=s;while(p!=NULL){ p=p->next;s->next=q; /* 逆转指针*/q=s; /*指针前移*/s=p;}h->next=q; /*头指针h的后继是p*/}【例2-2】编写一算法将两个按元素值递增有序排列的单链表A和B归并成一个按元素值递增有序排列的单链表Co解：对于两个或两个以上的，结点按元素值有序排列的单链表进行操作时，应采用“指针平行移动，依次扫描完成”的方法。

从两表的第一个结点开始顺链表逐个将对应数据元素进行比较，复制小的并插入c表尾。

当两表中之一已到表尾，则复制另一个链表的剩余部分，插入到c表尾。

设pa、pb分别指向两表当前结点，p指向c表的当前表尾结点。

若设A中当前所指的元素为a, B中当前所指的元素为b,则当前应插入到C中的元素c为a a bcb a b例如：A=(3,5,8,11)B=(2,6,8,9,11,15,20)贝U C=(2,3,5,6,8,8,9,11,11,15,20)实现本题功能的函数如下：Lnode *hb(Lnode *pa,Lnode *pb) {Lnode * p,* q,*pc;pc=(Lnode*)malloc(sizeof(Lnode));{q=(Lnode*)malloc(sizeof(Lnode)); q->data=pa->data; pa=pa->next; p->next=q; p=q; }while(pb!=NULL)/*若表B 比A 长，将B 余下的结点链在 C 表尾*/{q=(Lnode*)malloc(sizeof(Lnode)); q->data=pb->data; pb=pb->next; p->next=q; p=q; }p->next=NULL; p=pc; /*p 指向表C 的头结点pc*/pc=p->next; /*改变指针状态，使 pc 指向p 的后继*/ free(p); /* 释放 p 空间 */return (pc); }此算法的时间复杂度为 0(m+n)，其中m ，n 分别是两个被合并表的表长。

/*建立表c 的头结点pc*/ P=pc ；/*p 指向C 表头结点*/while(pa!=NULL&&pb!=NULL)q=(Lnode*)malloc(sizeof(Lnode)); /*建立新结点q*/if(pb->data<pa->data)/*比较A 、B 表中当前结点的数据域值的大小*/{q->data=pb->data; /*B 中结点值小，将其值赋给q 的数据域*/pb=pb->next;/*B 中指针pb 后移*/else{q->data=pa->data; /*相反，将A 结点值赋给q 的数据域*/pa=pa->next;/*A 中指针pa 后移*/p->next=q; /*将q 接在p 的后面*/ p=q;/*p 始终指向C 表当前尾结点*/while(pa!=NULL)/*若表A 比B 长，将A 余下的结点链在 C 表尾*/第三章栈和队列单项选择题1. ______________________ 在初始为空的堆栈中依次插入元素 此时栈顶元素是 _________________________ 。

A. cB. dC. bD. e2•若某堆栈的输入序列是 1, 2, 3，…，n ,输出序列的第一个元素为n ,则第i 个输出元素为 ____________ 。

A. iB. n-iC. n-i+1D.哪个元素无所谓3. 向一个栈顶指针为h 的带头结点链栈中插入指针s 所指的结点时，应执行 _______________A. h->n ext = s;D. s->next = h->n ext; h->n ext=s;4. 一个栈的入栈序列是 ______________________________________ a , b ,c ,d ,e ,则栈的不可能的输出序列是 _______________________________________________A. edcbaB. decba5•栈和队列的共同点是 ______________A.都是先进后出C. 只允许在端点处插入和删除元素 6•对于循环队列 _______________ 。

A.无法判断队列是否为空 C. 队列不可能满7.若用一个大小为6的数组来实现循环队列， 且当前队尾指针rear 和队头指针front 的值分 别为0和3。

当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为 。

BCDCCDACA 填空题1•在求表达式值的算符优先算法中使用的主要数据结构是 ______________ 。

2. 设有一个空栈，现输入序列为 1, 2, 3, 4, 5。

经过 push , push , pop , push , pop , push, pop , push 后，输出序歹u 是 _________ 。

3. ___________________________________________________ 仅允许在同一端进行插入和删除的线性表称为 _____________________________________________ 。

7 .在顺序栈s 中，栈为空的条件是 ____________ ，栈为满的条件是 ______ 。

f ，e , d , c ，b ，a 以后，连续进行了三次删除操作, B. s->n ext = h;C. s->n ext = h; h = h->n ext; C. dceabD. abcdeB.都是先进先出D.没有共同点B.无法判断队列是否为满 D.以上说法都不是A. 1 和 5B. 2 和 48. 判定一个循环队列 QU (最多元素为A. QU->fro nt==QU->rearC. QU->fro nt==(QU->rear+1) % m0 9. 判定一个循环队列QU (最多元素为A. QU->fro nt==QU->rearC. 4 和 2D. 5 和 1m0)为满队列的条件是 ______________ B. QU->fro nt!=QU->rearD. QU->fro nt!=(QU->rear+1) % m0 m0)为空的条件是 ______________ 。

B. QU->fro nt!=QU->rear D. QU->fro nt!=(QU->rear+1) %m04. 用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S 、X 操作串为 ____________ 。