数据结构习题
第一章 ............................................................................................................................... 2 第二章 ............................................................................................................................... 3 第三章 ............................................................................................................................... 6 第四章 ............................................................................................................................... 7 第五章 ............................................................................................................................... 7 第六章 ............................................................................................................................... 9 第七章 ............................................................................................................................. 11 第九章 ............................................................................................................................. 13 第十章 ............................................................................................................................. 15 十二章 文件 .................................................................................................................... 16
1
第一章
一、 选择题
1.在数据结构中，与所使用的计算机无关的数据叫 结构。 A. 存储 B. 物理 C. 逻辑 D. 物理和存储 二、判断题
1．数据元素是数据的最小单位（ ）。 2．数据项是数据的基本单位（ ）。 三、基本概念
1.简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线 性结构、非线性结构。 2. 常用的存储表示方法有哪几种? 3.设三个函数f,g,h分别
为 f(n)=100n^3+n^2+1000 , g(n)=25n^3+5000n^2 , h(n)=n^1.5+5000nlgn 请判断下列关系是否成立： (1) f(n)=O(g(n)) (2) g(n)=O(f(n)) (3) h(n)=O(n^1.5)
(4) h(n)=O(nlgn)
◇ 这里我们复习一下渐近时间复杂度的表示法T(n)=O(f(n))，这里的\是数学符号，它的严格定义是\若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n0 ,使得当n≥n0时都满足0≤T(n)≤C·f(n)。\用容易理解的话说就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。这么一来，就好计算了吧。第(1)题中两个函数的最高次项都是n^3,因此当n→∞时，两个函数的比值是一个常数，所以这个关系式是成立的。
2
第二章
一、 选择题
１.在一个长度为n的顺序表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动 个元素。
A. n-1 B. n-i+1 C. n-i-1 D. I
2.线性表是 。 A. 一个有限序列，可以为空 B. 一个有限序列，不能为空 C. 一个无限序列，可以为空 D. 一个无限序列，不能为空
3.对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的，
删除一个元素时大约要移动表中的 个元素。 A. n+1 B. n-1 C. (n-1)/2 D. n 4.线性表采用链式存储时，其地址 。
A. 必须是连续的 B. 部分地址必须是连续的
C. 一定是不连续的 D. 连续与否均可以 5.设单链表中指针p指着结点(数据域为m)，指针f指着将要插入的新结点(数据域为x)，当x插在结点m之后时，只要先修改 后修改p->link=f即可。 A. f->link=p; B. f->link=p->link;
C. p->link=f->link; D. f=nil;
6.在双向链表存储结构中，删除p所指的结点时需修改指针 。 A. ((p->rlink) ->rlink) ->link=p; p->rlink=(p->rlink) ->rlink; B. (p->llink) ->rlink=p->rlink; (p->rlink) ->llink=p->llink; C. p->llink=(p->llink) ->llink; ((p->llink) ->llink) ->rlink=p;
D. ((p->llink) ->llink) ->rlink=p; p->llink=(p->llink) ->llink;
7.在双向链表存储结构中，删除p所指的结点的前趋结点（若存在）时需修改指
针 。
A. ((p->llink) ->llink) ->rlink=p; p->llink=(p->llink) ->llink; B. ((p->rlink) ->rlink) ->llink=p; p->rlink=(p->rlink) ->rlink; C. (p->llink) ->rlink=p->rlink; (p->rlink) ->llink=p->llink;
D. p->llink=(p->llink) ->llink; ((p->llink) ->llink) ->rlink=p;
8.根据线性表的链式存储结构，每个结点所含指针的个数，链表分为单链表和 。 A. 循环链表 B. 多重链表 C. 普通链表 D. 无头结点链表
9.从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需 平 均比较 个结点。 A. n B. n/2 C. (n-1)/2 D. (n+1)/2
10.在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入*s结点， 则执行 。
A. s->next=p->next; p->next=s; B. p->next=s->next; s->next=p; C. q->next=s; s->next=p; D. p->next=s; s->next=q;
二、填空
1. 在线性结构中第一结点 _______，其余每个结点有且只有 _______；最后一个结点
________，其余每个结点有且只有 [________。 2. 对于顺序存储的线性表，当随机插入或删除一个元素时，约需平均移动表长 ___ 的
3
元素。
3. 对于长度为n的顺序表，插入或删除元素的时间复杂性为 ____ ；对于顺序栈或队
列，插入或删除元素的时间复杂性为 _______ 。
4.从顺序表中删除第i个元素时，首先把第i个元素赋给 _______ 带回，接着从 _______ 开始向后的所有元素均 ______一个位置，最后使线性表的长度 __ 。
5.在线性表的顺序存储中，元素之间的逻辑关系是通过 _____ 决定的；在线性表的链接存储中，元素之间的逻辑关系是通过 _____ 决定的。 6.一个单链表中删除*p结点时，应执行如下操作: (1)q=p->next;
(2)p->data=p->next->data;
(3)p->next= [1] q->next或p->next->next ; (4)free(q);
7.若要在一个单链表中的*p结点之前插入一个*s结点时，可执行如下操作: (1)s->next= [1] p->next ; (2)p->next=s; (3)t=p->data;
(4)p->data= [2] s->data ; (5)s->data= [3] t ;
8.对于线性表的顺序存储，需要预先分配好存储空间，若分配太多则容易造成存储空
间的 ______ ，若分配太少又容易在算法中造成 ____ ，因此适应于数据量变化不大的情况；对于线性表的链接存储(假定采用动态结点)，不需要 ____分配
存储空间，存储器中的整个 _____ 都可供使用，分配和回收结点都非常方便，能够有效地利用存储空间，在算法中不必考虑 ___ 的发生，因此适应数据量变化较大的情况。
三、判断题
1．顺序存储的线性表可以随机存取（ ）。
2．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性
因此，是属于同一数据对象（ ）。
3．在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点查
找任何一个元素（ ）。
4．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构（ ）。
5．链表的每个结点中，都恰好包含一个指针（ ）。
四、综合题
1. 线性表有两种存储结构：一是顺序表，二是链表。试问： (1)两种存储表示各有哪些主要优缺点?
(2)如果有n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化，线性 表的总数也会自动地改变。在此情况下，应选用哪种存储结构?为什么? (3)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么，应采用哪种存储结构?为什么?
2. 用线性表的顺序结构来描述一个城市的设计和规划合适吗?为什么?
3. 在单链表和双向表中，能否从当前结点出发访问到任一结点? 4. 编写下列算法
(1)向类型有list的线性表L的第i个元素（0≤i≤L.len）之后插入一个新元素x。
4