第二部分线性表
一、选择题
1．关于顺序存储的叙述中,哪一条是不正确的( B )
A.存储密度大
B.逻辑上相邻的结点物理上不必邻接
C.可以通过计算直接确定第i个结点的位置
D.插入、删除操作不方便
2．长度为n的单链表连接在长度为m的单链表后的算法的时间复杂度为( C )
A O(n)
B O(1)
C O(m)
D O(m+n)
3．在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是：( A )
A 访问第i个结点（1<=i<=n）和求第i个结点的直接前趋（2<=i<=n）
B 在第i个结点（1<=i<=n）后插入一个新结点
C 删除第i个结点（1<=i<=n）
D 将n个结点从小到大排序
4．一个向量第一个元素的存储地址是100 ，每个元素的长度为2 ，则第5 个元素的地址是：( B )
（A ）110 （ B ）108 （C ）100 （D ）120
5．已知一个顺序存储的线性表，设每个结点需要占m个存储单元，若第一个结点的地址为da，则第i个结点的地址为：( A )
A）da+(i-1)*m B) da+i*m C) da-i*m D) da+(i+1)*m
6．在具有n个结点的单链表中，实现（A ）的操作，其算法的时间复杂度为O(n)。
A）遍历链表和求链表的第i个结点B）在地址为p的结点之后插入一个结点
C）删除开始结点D）删除地址为p的结点的后继结点
7．链表是一种采用（B ）存储结构存储的线性表。
（A ）顺序（B ）链式（ C ）星式（D ）网状
8．线性表若采用链式存储结构时，要求内存中可用存储单元的地址：（D ）（A ）必须是连续的（ B ）部分地址必须是连续的
（C ）一定是不连续的（ D ）连续或不连续都可以
9．线性表Ｌ在（B ）情况下适用于使用链式结构实现。
（Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入
（Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂
10．在长度为n 的顺序表的第i (1≤i≤n+1) 个位置上插入一个元素，元素的移动次数为( A )
A.n-i+1
B.n-i
C.i
D.i-1
11．线性表是（A）。
a、一个有限系列，可以为空
b、一个有限系列，不能为空
c、一个无限系列，可以为空
d、一个无限系列，不能为空
12. （A）线性表。
A.(孔子,诸葛亮,曹雪芹)
B.{A,B,C,D}
C.{10,11,12,13,14}
D.(1,2,3,...)
13. （）是表示线性数据结构的。
A.循环链表
B.邻接多重表
C.孩子链表
D.单链表
14. 将线性表的数据元素以（B）结构存放, 查找一个数据元素所需时间不依赖于表长。
A.循环双链表
B.哈希(Hash)表
C.一维数组
D.单链表
15. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（B）。（A）s->link=p;p->link=s;
（B）s->link=p->link;p->link=s;
（C）s->link=p->link;p=s;
（D）p->link=s;s->link=p;
16. 在循环链表中first为指向链表表头的指针，current为链表当前指针，在循环链表中检测
current是否达到链表表尾的语句是( D )。
（A）current->link=NULL (B)first->link=current
（C）first=current (D)current->link=first
17. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比
较( D )个结点。
A. n
B. n/2
C.（n-1）/2
D. (n+1)/2
18. 在一个具有n个结点的有序单链表中，插入一新结点并仍然有序的时间复杂度为( B )。
A. O(1)
B. O(n)
C. O(n2)
D. O(nlog2n)
19. 用链表表示线性表的优点是( C )。
A. 便于随机存取
B. 花费的存储空间比顺序表少
C. 便于插入与删除
D. 数据元素的物理顺序与逻辑顺序相同
20. 当需要随机查找线性表的元素时,宜采用( C )作存储结构。
A. 双向链表
B. 循环链表
C. 顺序表
D. 单链表
21. 线性表的链接实现有利于（ A ）运算。
A、插入b、读表元c、查找d、定位
22. 线性表采用链式存储时，其地址（D ）。
A 必须是连续的
B 部分地址是连续的
C 一定是不连续的
D 连续与否均可以
23. 设单链表中指针p指着结点a，若要删除a之后的结点（若存在），则需要修改指针的操作为（A）。
A、p->next=p->next->next b、p=p->next
C、p= p->next->next d、p->next=p
24. 向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动（B ）个元素。
A、8
B、63.5
C、63
D、7
25. 向一个有127 个元素的顺序表中删除一个元素，平均要移动（C ）个元素
（A）8 （B）63.5 （C）63（D）7
26. 用链表表示线性表的优点是（A ）
A 便于插入和删除操作
B 数据元素的物理顺序与逻辑顺序相同
C 花费的存储空间较顺序存储少
D 便于随即存取
27. 以下数据结构中不属于线性数据结构的是（C ）
A 队列
B 线性表
C 二叉树
D 栈
28．对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为（B ）。
A．N+1 B．N C．(N+1)/2 D．N/2
29．下列叙述中正确的是( A )。
A. 线性表是线性结构
B. 栈与队列是非线性结构
C. 线性链表是非线性结构
D. 二叉树是线性结构
30．在单链表中，增加头结点的目的是( A )。
A. 方便运算的实现
B. 使单链表至少有一个结点
C. 标识表结点中首结点的位置
D. 说明单链表是线性表的链式存储实现
31．线性表的顺序存储结构和线性表的链式存储结构分别是（B ）。
A.顺序存取的存储结构、顺序存取的存储结构
B.随机存取的存储结构、顺序存取的存储结构
C.随机存取的存储结构、随机存取的存储结构
D.任意存取的存储结构、任意存取的存储结构
33．线性表中正确的说法是( D )。
A. 每个元素都有一个直接前驱和一个直接后继
B. 线性表至少要求一个元素
C. 表中的元素必须按由小到大或由大到小排序
D. 除了第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继34．线性表是具有n个（C ）的有限序列。
A. 表元素
B. 字符
C. 数据元素
D. 数据项
35．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（C ）。（1≤i≤n+1）
A. O(0)
B. O(1)
C. O(n)
D. O(n2)
36．在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度（B）。
A. O(1)
B. O(n)
C. O(nlogn)
D. O(n2)
37．某线性表最常用的运算是插入和删除，插入运算是指在表尾插入一个新元素，删除运算是指删除表头第一个元素，那么采用（A ）存储方式最节省运算时间。
A. 仅有尾指针的单向循环链表
B. 仅有头指针的单向循环链表
C. 单向链表
D. 双向链表
二、填空题
1．在单项链表中删除一个指定结点的后继的时间复杂度为[ O(1) ]
2．线性表中______数据元素的个数______________________ 称为表的长度。
3. 在n 个结点的单链表中，在P 指向的结点之后插入一个结点的时间复杂度为_O（n）。4．设长度为n的线性表顺序存贮,若在它的第i-1和第i个元素之间插入一个元素, 共需移动__n-i+1_______ 个元素(1 5．在顺序表中访问任意结点的时间复杂度为O（1），因此顺序表也称为随机存储的数据结构。 6．在单链表中要在已知结点*p之前插入一新结点，需找到插入点，其时间复杂度为O（n），而在双链表中，完成同样操作的时间复杂度为O（1）。 7．循环链表的主要优点是从任何一个结点出发可以遍历所有结点。 8．在一个单链表中删除p所指结点的下一个结点时，应执行以下操作： q=p->link; p->link=__ p->link ->link __ __ Delete q 9．将适当的语句添入单链表搜索函数find中。 template { current=first->link； while(current!=NULL) if(current->data=value) break else current=current->link; return __ current ___ __ } 10．顺序存储方法是把逻辑上相邻的结点存储在物理位置__也相邻______ 的存储单元中。 11．顺序存储结构使线性表中逻辑上相邻的数据元素在物理上也相邻。因此，这种表便于__随机__访问，是一种__随机访问存储结构__。 12．在一个不带头结点的单链表中，在表头插入或删除与其在其他位置插入或删除操作的过程___不相同________。 13．已知L是无头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点，添加合适的语句。 1) P结点之后插入结点S：S->next=P->next; P->next=S; 2) P结点之前插入结点S： pre=L; while(pre->next!=P) pre=pre->next; S->next=P; pre->next=S; 3) 在表首插入结点S：S->next=L; L=S; 4) 在表尾插入结点S： while(P->next) P=P->next; P->next=S; S->next=NULL; 14．已知P结点是某双向链表的中间结点，添加合适的语句。 1)P结点之后插入结点S： S->next=P->next; S->prior=P; P->next->Prior=S; P->next=S; 2)P结点之前插入结点S： S->next=P; S->prior=P->prior; P->prior->next=S; P->prior=S; 3)删除P结点的直接后继结点： Q=P->next; P->next=Q->next; Q->next->prior=P; free(Q); 4)删除P结点的直接前驱结点： Q=P->prior; P->prior=Q->prior; Q->prior->next=P; free(Q); 5)删除P结点： P->prior->next=P->next; P->next->prior=P->prior; free(P); 15．在链表的结点中，数据元素所占存储量和整个结点所占的存储量之比称作存储密度。 三、判断题 1．线性链表中各个链结点之间的地址不一定要连续。( R ) 2．若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适。( W ) 3．若线性表采用顺序存储结构，每个数据元素占用4个存储单元，第12个数据元素的存储地址为144，则第1个数据元素的存储地址是101。( W ) 4．若长度为n的线性表采用顺序存储结构，删除表的第i个元素之前需要移动表中n-i+1个元素。( W ) 5．在顺序表中取出第i 个元素所花费的时间与i 成正比。（W ） 四、写出下列算法完成的功能 1）ListNode *Demo1(LinkList L, ListNode *p) /*L是带有头结点的单链表*/ { ListNode *q = L->next; while(q && q->next !=p) q = q->next; if(q) return q; else error(“*p is not in L!”); } 寻找结点P的前驱结点，若存在则返回前驱结点的地址，若不存在则给出错误信息 2) void Demo2(ListNode *p, ListNode *q) { DataType temp; temp = p->data; p->data = q->data; q->data = temp; } 交换结点p和q数据域的内容 3) LinkList Demo3(LinkList L) /*L是无头结点的单链表*/ { ListNode *p, *q; if(L && L->next) { q=L; L=L->next; p=L; While(p->next) p=p->next; p->next = q; q->next = NULL; } return L; } 将链表L第一个结点变为最后一个结点 4) LinkList *Connect(LinkList *L1, LinkList *L2) /* L1,L2是带有头结点的单链表*/ { LinkList *p; p=L1; while(p->next!=NULL) p=p->next; p->next = L2->next; return(L1); } 将L2连接到L1后面 数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C ） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ） A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放 该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。 10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与（ A ）的表示等价。 A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为（ C ） for (int i=0;i 数据结构练习题1 指导老师：常璐璐 姓名：邢莉彬 学校：滨州学院 院系：信息工程学院软件技术 填空题 1. 对于一个n个结点的单链表，在表头插入元素的时间复杂度为_____O(1)_____，在表尾插入元素的时间复杂度为_____O(n)_____。 2. 删除非空线性链表中由q所指的链结点（其直接前驱结点由r指出）的动作时执行语句___r->link=q->link_______和______free(q)____。 结点结构为 typedef struct Node{ int value; node * link; }node; 3. 非空线性链表中，若要在由p所指的链结点后面插入新结点q，则应执行语句____ q->link=p->link;______和_____ p->link=q;_____。 结点结构为 typedef struct Node{ int value; node* link; }node; 4. 线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____(n-1)/2_____。 5. 在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动_____ n-i+1_____ 个元素。 6.在具有n个链结点的链表中查找一个链结点的时间复杂度为O(_______n___)。 7. 线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为_____O（n）_____；而在链式存储方式下，插入和删除操作的时间复杂度都是____O(1)______ 。 8. 若某线性表采用顺序存储结构，每个元素占4个存储单元，首地址为100，则第10个元素的存储地址为____136______。 选择题 1. 对于一个带头结点的单链表，头指针为head，判定该表为空的条件是________B__。 A. head==NULL B. head->next==NULL C. head->next==head D. head!=NULL 2. 将长度为m的线性链表链接在长度为n的线性链表之后的过程的时间复杂度若采用大O形式表示，则应该是______B____。 A．O(m) B．O(n) C．O(m+n) D．O(m-n) 3.在包含1000个数据元素的线性表中，实现如下4个操作所需要的执行时间最长的是______A____ 。 习题二 一、选择题 1．在一个长度为n的顺序表中删除第i个元素（0＜i 序号 数据结构实验报告 班级姓名同组者/ 成绩 日期 3.9指导教师 实验名称实验一线性表及其应用 一、实验目的 1、深刻理解线性表的逻辑特性及其顺序、链式存储方式的特点。 2、熟练掌握线性表的常用操作（建立、插入、删除、遍历等）在顺序、链式存储上的实现。 3、加深对C/C++等编程语言的相关知识点的理解（如结构体、指针、函数、引用参数等）。 二、实验内容 1、根据给定的整型数组，以尾插法建立一个单链表，并实现以下操作： ①查找：输入一个欲查找的整数，找到则显示第一个相匹配的整数在单链表中所处的位置，若不存在，则显示提示信息。 ②删除：输入一个欲删除的整数e ，若存在则在单链表中删除第一个值为 e 的元素。 ③插入：输入一个欲插入位置i 和欲插入元素e，将e 插入到第i 个整数之前（注意i 的合法性）。 A、算法思想 ①创建 head 为头结点指针，初始时head->next 为NULL ；tail 始终指向当前链表的最后一个元素，其初始时指向头结点；p 始终指向每次申请的新结点，修改p->data 为当前读入的整数；修改tail->next 为p ，修改tail 为p ；最后修改tail->next 为NULL ，。 ②插入 找到插入点的前驱（即第i-1 个结点）的指针p ；s 指向新申请的结点；修改s->data 为参数e，修改s->next 为p->next ，修改p->next 为s 。 ③查找 ……利用p进行遍历，直到节点的数据和所给的数据相同，输出节点的位置 ④删除 ……利用p进行遍历，并总是将p的前一节点的指针赋给pre，一旦找到，则删除节点并 退出循环，没有到话，反馈相关信息 B、算法源码 /* *线性表及其应用 */ #include 填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/ 实验1 线性表的基本操作 一、需求分析 目的： 掌握线性表运算与存储概念，并对线性表进行基本操作。 1.初始化线性表； 2.向链表中特定位置插入数据； 3.删除链表中特定的数据； 4.查找链表中的容； 5.销毁单链表释放空间； 二、概要设计 ●基础题 主要函数： 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 实验步骤： 1，初始化顺序表 2，调用插入函数 3，在顺序表中查找指定的元素 4，在顺序表中删除指定的元素 5，在顺序表中删除指定位置的元素 6，遍历并输出顺序表 ●提高题 要求以较高的效率实现删除线性表中元素值在x到y（x和y自定义）之间的所有元素 方法： 按顺序取出元素并与x、y比较，若小于x且大于y，则存进新表中。 编程实现将两个有序的线性表进行合并，要求同样的数据元素只出现一次。 方法： 分别按顺序取出L1，L2的元素并进行比较，若相等则将L1元素放进L中，否则将L 1，L2元素按顺序放进L。 本程序主要包含7个函数 主函数main() 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 提高题的程序 void Combine(List* L1,List* L2,List* L) void DeleteList3(List* L,int x,int y) 二、详细设计 初始化线性表InitList（List* L，int ms） void InitList(List* L,int ms) { L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); L->size=0; L->MAXSIZE=LIST_INIT_SIZE; 一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价,不包括如下（B ）方面的内容。 Ａ.健壮性和可读性Ｂ．并行性C。正确性Ｄ．时空复杂度 2.2．在带有头结点的单链表ＨL中,要向表头插入一个由指针p指向 的结点，则执行（A ). Ａ. p－〉ｎｅxt=HL->nexｔ; ＨL-〉nexｔ=p; B． p-〉next=HL；ＨL=p； Ｃ。p-＞ｎext=HＬ； p＝HL；Ｄ. HL=p; ｐ－〉next＝ＨL； 3.3．对线性表,在下列哪种情况下应当采用链表表示？( B ） Ａ.经常需要随机地存取元素 B。经常需要进行插入和删除操作 C。表中元素需要占据一片连续的存储空间D．表中元素的个数不变 4. 4.一个栈的输入序列为１ 2 3，则下列序列中不可能是栈的输出序 列的是( C ） A. 2 3 1 ??? B. ３ 2 1 C。 3 １ 2 ??? D. 1 ２３ 5. 5.AＯV网是一种（D ）。 A．有向图Ｂ．无向图Ｃ．无向无环图D．有向无环图 6.6。采用开放定址法处理散列表的冲突时,其平均查找长度（Ｂ)。 A．低于链接法处理冲突B．高于链接法处理冲突Ｃ.与链接法处理冲突相同 D。高于二分查找 7.7。若需要利用形参直接访问实参时，应将形参变量说明为（D ) 参数. Ａ。值Ｂ。函数 C.指针 D。引用 8.８．在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结 点都具有相同的（ A )。 A。行号 B.列号 C．元素值 D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为( D )。 A。O（loｇ 2n) B．Ｏ（nlog 2 n） C。０（n) D.0 （n2） 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C ). Ａ．O(n） B. Ｏ(1） C。 O（log 2 n） D. O(n2)二、运算题（每题 6 分，共２４分） 第一章概论 一、选择题 1、研究数据结构就是研究（D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作（研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作） 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。（线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素，有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继）（链表、栈、队列、数组、串） A. 图 B. 树 C. 广义表（线性表的推广） D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i 6、算法是（D ）。为了解决某一问题而规定的一个有限长的操作序列 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log3n) D. O(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（B ）和运算等的学科。（关系和操作） A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（ A ）。 i=s=0; while(s 北京邮电大学电信工程学院 数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 带头结点的单链表 2.2 关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中b、代码实现： Linklist::Linklist(int a[],int n)//头插法 {front=new Node; front->next=NULL; for(int i=n-1;i>=0;i--) {Node*s=new Node; s->data=a[i]; s->next=front->next; front->next=s; } } 2、尾插法 a、伪代码实现：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)//尾插法 {front=new Node; Node*r=front; for(int i=0;i 第一章线性表 2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。 解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。 2.2 填空题。 解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。 (2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。 (3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。 (4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。 2.3 在什么情况下用顺序表比链表好？ 解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。 2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。 解： 2.5 画出执行下列各行语句后各指针及链表的示意图。 L=(LinkList)malloc(sizeof(LNode)); P=L; for(i=1;i<=4;i++){ P->next=(LinkList)malloc(sizeof(LNode)); P=P->next; P->data=i*2-1; } P->next=NULL; for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2); for(i=1;i<=3;i++) Del_LinkList(L,i); 解： 2.6 已知L是无表头结点的单链表，且P结点既不是 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 实验一线性表及其应用 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、实现提示 1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。 在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024 typedef int elemtype; /* 线性表中存放整型元素*/ typedef struct { elemtype vec[MAXSIZE]; int len; /* 顺序表的长度*/ }sequenlist; 将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。 2. 注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。 3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下： typedef int elemtype; typedef struct node 《数据结构》 第二章线性表习题 一、单项选择题 1. 线性表是________。 A．一个有限序列，可以为空B．一个有限序列，不可以为空 C．一个无限序列，可以为空D．一个无限序列，不可以为空 2. 在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动个元素。 A．n-i B．n-i+l C．n-i-1 D．i 3. 线性表采用链式存储时，其地址________。 A．必须是连续的B．一定是不连续的 C．部分地址必须是连续的D．连续与否均可以 4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。 A．n/2 B．n C．（n+1）/2 D．（n-1）/2 5. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是____。 A． p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; B． s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; C． p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; D． s->prior=p; s->next=p->next; p->next->prior=s; p->next=s; 6. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为________。A．p->next=p->next->next; B．p=p->next; C．p=p->next->next; D．p->next=p; 7. 在一个长度为n的顺序表中向第i个元素(0< i 实验报告 课程名称____数据结构上机实验__________ 实验项目______线性表的应用____________实验仪器________PC机___________________ 系别_____电子信息与通信学院___ 专业________ ___ 班级/学号______ __ 学生姓名______ ___________ 实验日期_______________________ 成绩_______________________ 指导教师_______________________ 实验一.线性表的应用 1.实验目的：掌握线性链表的存储、运算及应用。利用链 表实现一元多项式计算。 2.实验内容： 1)编写函数，实现用链表结构建立多项式； 2)编写函数，实现多项式的加法运算； 3)编写函数，实现多项式的显示； 4)测试：编写主函数，它定义并建立两个多项式，显示 两个多项式，然后将它们相加并显示结果。变换测试用的多项式，检查程序的执行结果。 选做内容：修改程序，选择实现以下功能： 5)多项式求值：编写一个函数，根据给定的x值计算并 返回多项式f(x)的值。测试该函数（从终端输入一个x的值，调用该函数并显示返回结果）。 6)多项式相减：编写一个函数，求两个多项式相减的多 项式。 7)多项式相乘：编写一个函数，求两个多项式的乘积多 项式。 3.算法说明： 1)多项式的建立、显示和相加算法见讲义。可修改显示 函数，使输出的多项式更符合表达规范。 2)多项式减法：同次项的系数相减（缺项的系数是0）。 例如a(x)=-5x2+2x+3，b(x)= -4x3+3x，则a(x)-b(x) =4x3-5x2-x+3。提示：a(x)-b(x) = a(x)+(-b(x))。 3)多项式乘法：两个多项式的相乘是“系数相乘，指数 相加”。算法思想是用一个多项式中的各项分别与另 一个多项式相乘，形成多个多项式，再将它们累加在 一起。例如，a(x)=-5x2+2x+3，b(x)=-4x3+3x，则 a(x)*b(x) = (-4x3)*(-5x2+2x+3)+(3x)*(-5x2+2x+3) = (20x5-8x4-12x3) + (-15x3+6x2+9x) = 20x5-8x4-27x3+6x2+9x。 4.实验步骤： 根据实验报告的要求，我对文件夹里的C文件进行了丰 富和修改，步骤如下： 链表结构建立多项式： typedef struct polynode { float coef; //系数 int exp; //指数 struct polynode *next; //下一结点指针 } PNode; 编写函数，实现多项式的加法运算； PNode * PolyAdd (PNode *f1, PNode *f2) //实现加法功能。 第一章绪论 一、选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系 C.可读性和文档性 D.数据复杂性和程序复杂性k 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。A.正确B.不正确 二、填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.算法的五个重要特性是、、、、。 4.下面程序段的时间复杂度是。 for( i = 0; i < n; i++) for( j = 0; j < m; j++) A[i][j] = 0; 5.下面程序段的时间复杂度是。 i = s = 0; while ( s < n) { i ++; /* i = i +1*/ s += i; /* s = s + i*/ } 6.下面程序段的时间复杂度是。 s = 0; for( i = 0; i < n; i++) for( j = 0; j < n; j++) s += B[i][j]; sum = s; 7.下面程序段的时间复杂度是。 i = 1; while ( i <= n ) i = i * 3; 线性表 一、选择题 1.线性表是（ A ） A．一个有限序列，可以为空B．一个有限序列，不可以为空 C．一个无限序列，可以为空D．一个无限序列，不可以为空 2.一维数组与线性表的特征是（ C ）。 A．前者长度固定，后者长度可变B．两者长度均固定 C．后者长度固定，前者长度可变D．两者长度均可变 3.用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是( B ). A．当前结点所在地址域B．指针域 C．空指针域D．空闲域 4.用链表表示线性表的优点是（ B ）。 A．便于随机存取 B．便于进行插入和删除操作 C．占用的存储空间较顺序表少 D．元素的物理顺序与逻辑顺序相同 5.在具有 n 个结点的单链表中，实现__A _的操作，其算法的时间复杂度都是O（n）。 A．遍历链表和求链表的第i个结点 B．在地址为P的结点之后插入一个结点 C．删除开始结点 D．删除地址为P的结点的后继结点 6.下面关于线性表的叙述中，错误的是（ B ）。 A．线性表采用顺序存储必须占用一片连续的存储单元 B．线性表采用顺序存储便于进行插入和删除操作 C．线性表采用链式存储不必占用一片连续的存储单元 D．线性表采用链式存储便于进行插入和删除操作 7.已知单链表的每个结点包括一个指针域next，它指向该结点的后继结点。现要将指针 q 指向的新结点插入到指针 p 指 向的结点之后，下面的操作序列中正确的是（ C ）。 A . q = p->next; p->next = q->next ; B . p->next = q->next; q = p->next ; C . q->next = p->next; p->next = q ; D . p->next = q; q->next = p->next ; 数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 存储结构 带头结点的单链表 关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中 b、代码实现： Linklist::Linklist(int a[],int n) 堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)取链表长度函数 a、伪代码实现：判断该链表是否为空链表，如果是，输出长度0 如果不是空链表，新建立一个temp指针，初始化整形数n为0 将temp指针指向头结点 判断temp指针指向的结点的next域是否为空，如果不是，n加一，否 则return n 使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next 域为0，返回n b 、代码实现 void Linklist::Getlength()Linklist(); cout<数据结构试题及答案
数据结构线性表习题1
数据结构线性表2答案
数据结构线性表实验报告
数据结构课后习题及答案
数据结构_实验1_线性表的基本操作
数据结构试题及答案10套
数据结构试题答案
数据结构实验一题目一线性表实验报告
数据结构线性表答案
数据结构习题与答案
《数据结构》实验一 线性表及其应用
数据结构 第二章 线性表习题
数据结构线性表的应用实验报告
数据结构作业及答案
数据结构-线性表-习题
数据结构实验一题目一线性表实验报告
相关主题
文本预览