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

《数据结构-C语言版》

第一章 绪论

单项选择题

1.在数据结构中,数据的基本单位是_____ ____。

A. 数据项 B. 数据类型 C. 数据元素 D. 数据变量 2.数据结构中数据元素之间的逻辑关系被称为__ ____。

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

A. 存储结构 B. 逻辑和物理结构 C. 逻辑结构 D. 物理结构 4.在链式存储结构中,数据之间的关系是通过____ ____体现的。 A. 数据在内存的相对位置 B. 指示数据元素的指针 C. 数据的存储地址 D. 指针 5.计算算法的时间复杂度是属于一种____ ___。

A. 事前统计的方法 B. 事前分析估算的方法 C. 事后统计的方法 D. 事后分析估算的方法

6.在对算法的时间复杂度进行估计的时候,下列最佳的时间复杂度是____ __。 A. n2 B. nlogn C. n D. logn

7.设使用某算法对n个元素进行处理,所需的时间是T(n)=100nlog2n+200n+2000,则该算法的渐近时间复杂度为____ ___。

A. O(1) B. O(n) C. O(200n) D. O(nlog2n)

1

CDCBBDD

第二章 线性表

单项选择题

1.链表不具有的特点是____ ____。

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

2.设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100,则第6个元素占用的最后一个存储单元的地址为 。

A. 139 B. 140 C. 147 D. 148 3.在线性链表存储结构下,插入操作算法 。 A. 需要判断是否表满 B. 需要判断是否表空 C. 不需要判断表满 D. 需要判断是否表空和表满

4.在一个单链表中,若删除p所指结点的后继结点,则执行 。 A. p->next = p->next->next; B. p->next = p->next;

C. p = p->next->next; D. p = p->next; p->next = p->next->next;

5.将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为 。 A. O(n) B. O(1) C. O(m) D. O(m+n)

6.需要预分较大空间,插入和删除不需要移动元素的线性表,其存储结构是 。 A. 单链表 B. 静态链表 C. 线性链表 D. 顺序存储方式 ACCABB 填空题

1.在带表头结点的单链表中,当删除某一指定结点时,必须找到该结点的_____结点。 2.在单链表中,指针p所指结点为最后一个结点的条件是 。

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

5.在长度为n的顺序表中插入一个元素的时间复杂度为 。 1前驱 2 p->next==NULL

2

3.1 4.n-i+1 5.O(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归并成一个按元素值递增有序排列的单链表C。

解:对于两个或两个以上的,结点按元素值有序排列的单链表进行操作时,应采用“指针平行移动,依次扫描完成”的方法。从两表的第一个结点开始顺链表逐个将对应数据元素进行比较,复制小的并插入c表尾。当两表中之一已到表尾,则复制另一个链表的剩余部分,插入到c表尾。设pa、pb分别指向两表当前结点,p指向c表的当前表尾结点。若设A中当前所指的元素为a,B中当前所指的元素为b,则当前应插入到 C中的元素c为

?ac???b 例如:A=(3,5,8,11) B=(2,6,8,9,11,15,20)

则 C=(2,3,5,6,8,8,9,11,11,15,20) 实现本题功能的函数如下: Lnode *hb(Lnode *pa,Lnode *pb) {Lnode *p,*q,*pc;

a?b a?b pc=(Lnode*)malloc(sizeof(Lnode)); /*建立表c 的头结点pc*/

3

p=pc; /*p指向C表头结点*/ while(pa!=NULL&&pb!=NULL) {

q=(Lnode*)malloc(sizeof(Lnode)); /*建立新结点q*/

if(pb->datadata) /*比较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表尾*/ {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); }

此算法的时间复杂度为O(m+n),其中m,n分别是两个被合并表的表长。

4

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4