线性结构练习题
概述练习题
单项选择题
1．从逻辑上可以把数据结构分为（）两大类
A．动态结构与静态结构B．顺序结构与链式结构
C．线性结构与非线性结构D．初等结构与构造型结构
2．在下面的程序段中，对x的赋值语句的频度为（）
fo r（k=1;k<=n;k+ +）
for(j=1;j<=n;j+ +)
x=x+1;
A．O(2n) B．O(n) C．O(n2) D. O(log2n)
3．采用链式存储结构表示数据时，相邻的数据元素的存储地址（）A．一定连续B．一定不连续
C．不一定连续D．部分连续，部分不连续
4．下面关于算法说法正确的是（）
A．算法的时间复杂度一般与算法的空间复杂度成正比
B．解决某问题的算法可能有多种，但肯定采用相同的数据结构
C．算法的可行性是指算法的指令不能有二义性
D．同一个算法，实现语言的级别越高，执行效率就越低
5．在发生非法操作时，算法能够作出适当处理的特性称为（）
A．正确性B．健壮性C．可读性D．可移植性
6．某算法的时间复杂度为O(n2)，表明该算法的（）
A．问题规模是n2B．执行时间等于n2
C．执行时间与n2成正比D．问题规模与n2成正比
7．算法的时间复杂度取决于（）
A．问题的规模B．待处理数据的初态
C．A与B都对D．算法的易读性
判断题
1．数据的逻辑结构是指数据的各数据项之间的逻辑关系。（）
2．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）
3．数据的逻辑结构说明数据元素之间的次序关系，它依赖于数据的存储结构。（）4．算法的优劣与描述算法的语言无关，但与所用计算机的性能有关。（）
5．算法必须有输出，但可以没有输入。（）
线性结构练习题
单项选择题
1．线性表是（）
A．一个有限序列，可以为空B．一个有限序列，不能为空
C．一个无限序列，可以为空D．一个无限序列，不能为空
2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概念的，插入一个元素时平均要移动表中的（）个元素
A．n/2 B．(n＋1)/2 C．(n－1)/2 D．n
3．线性表采用链式存储时，其地址（）
A．必须是连续的B．部分地址必须是连续的
C．一定是不连续的D．连续与否均可
4．用链表表示线性表的优点是（）
A．便于随机存取B．花费的存储空间较顺序存储少
C．便于插入和删除D．数据元素的物理顺序与逻辑顺序相同5．链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（）存储方式最节省运算时间
A．单链表B．双向链表C．单循环链表D．带头节点的双向循坏链表6．下面关于线性表的叙述错误的是（）
A．线性表采用顺序存储，必须占用一片地址连续的单元
B．线性表采用顺序存储，便于进行插入和删除操作
C．线性表采用链式存储，不必占用一片地址连续的单元
D．线性表采用链式存储，便于进行插入和删除操作
7．单链表中，增加一个头结点的目的是为了（）
A．使单链表至少有一个结点B．标识表结点中首结点的位置
C．方便运算的实现D．说明单链表是线性表的链式存储8．在单链表指针为P的结点之后插入指针为s的结点，正确的操作是（）A．p->next=s; s->next=p->next; B．s->next=p->next; p->next=s;
C．p->next=s; p->next=s->next; D．p->next=s->next; p->next=s;
9．在双向链表存储结构中，删除p所指的结点时须修改指针( )
A．(p->prior)->next=p->next; (p->next)->prior=p->prior;
B．p->prior=(p->prior)->prior; (p->prior)->next=p;
C．(p->next)->prior=p; p->prior=(p->next)->next;
D．p->next=(p->prior)->prior; p->prior=(p->next)->next;
10．完成在双向循环链表结点p之后插入s的操作是( )
A．p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;
B．p->next->prior=s; p->next=s; s->prior=p; s->next=p->next;
C．s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;
D．s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;
11．若某线性表中最常用的在操作是取第i个元素和找第i个元素的前驱元素，则采用（）存储方式最节省运算时间。
A．单链表B．顺序表C．双向链表D．单循环链表
12．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A．单链表B．仅有头指针的单循环链表
C．双向链表D．仅有尾指针的单循环链表
13．向一个栈顶指针为TOP的链栈中插入一个p所指结点时，其操作步骤为（）A．Top->next=p; B．p->next=top->next; top->next=p;
C．p->next=top; top=p; D．p->next=top; top=top->next; 14．对于栈操作数据的原则是（）
A．先进先出B．后进先出C．后进后出D．不分顺序15．若已知一个栈的入栈序列是P1，P2，P3，…，P n，其输出序列为P1，P2，P3，…，P n，若P n是n，则P i为（）
A．i B．n－i C．n－i＋1 D．不确定16．表达式a*(b－c)＋d的后缀表达式是（）
A．abcd*－＋B．abc－*d＋C．abc*－d＋D．＋－*abcd 17．采用顺序存储的两个栈的共享空间S[1…m]，top[i]代表第i个栈（i=1，2）的栈顶，栈1的底在S[1]，栈2的底在S[m]，则栈满的条件是（）
A．top[2]－top[1]=0 B．top[1]+1=top[2]
C．top[1]+top[2]=m D．top[1]=top[2]
18．一个栈的入栈序列是abcde，则栈的不可能的输出序列是（）
A．edcba B．decba C．dceab D．abcde
19．在一个链队列中，若f，r分别为队首、队尾指针，则插入s所指结点的操作为（）A．f->next=r; f=s; B．r->next=s; r=s;
C．s->next=r; r=s; D．s->next=f; f=s
20．用不带头结点的单链表存储队列时，在进行删除运算时（）
A．仅修改头指针B．仅修改尾指针
C．头、尾指针都要修改D．头、尾指针可能都要修改
21．递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构A．队列B．静态链表C．栈D．顺序表
22．栈和队都是( )
A．顺序存储的线性结构B．链式存储的非线性结构
C．限制存取点的线性结构D．限制存取点的非线性结构
23．若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为S1，S2，S3，…，S n，若S1=n，则S i为（）
A．i B．n－i C．n－i＋1 D．以上都不对判断题
1．线性表的逻辑顺序与存储顺序总是一致的。（）
2．顺序存储的线性表可以按序号随机存取。（）
3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（）
4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此
属于同一数据对象。（）
5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（）6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（）
7．线性表的链式存储结构优于顺序存储结构。（）
8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（）9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（）
11．静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（）
12．线性表的特点是每个元素都有一个前驱和一个后继。（）
13．栈和队列的存储，既可以采用顺序存储结构，又可以采用链式存储结构。（）
14．任何一个递归过程都可以转换成非递归过程。（）
15．若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列3，2，5，6，4，1。（）16．通常使用队列来处理函数的调用。（）
17．循环队列通常用指针来实现队列的头尾相接。（）
简答题
1．线性表、栈和队列都是什么结构，可以在线性表的什么位置插入和删除元素；栈是一种什么样的线性表，只能在什么位置插入和删除元素；而队列是一种什么样的线性表，只能在什么位置插入元素，在什么位置删除元素？
2．5 个元素，其入栈次序为A，B，C，D，E。在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个出栈且D第二个出栈）的次序有哪几种？
3．假设S和X分别表示进栈和出栈操作，由输入序列”ABC”得到的输出序列”BCA”的操作序列为”SSXSXX”。则由输入序列”ABCDE”得到输出序列”DECBA”的操作序列为？
4．广义表( a, (a, b), d, e, ((i, j), k )) 的长度是多少？深度是多少？已知广义表A= (( a, b ), ( c , ( d, e )))，则广义表运算Head(Tail(A))等于什么？
5．下面的算法是实现对不带头结点的单链表L进行就地逆置，并用L返回逆置后的链表的头指针，请在空缺处填入相应语句完成其算法的功能。（注意：一个空缺处只能填入一条语句）
void reverse (LinkList L)
{ LinkList p, q;
p=NULL;
q=L;
while (q!=NULL)
{①
q->next=p;
p=q;
②
}
③
}
6．下面是一算法的核心部分，试说明该算法的功能。其中L是一个带头结点的单链表。
pre=L->next;
if (pre!=NULL)
while (pre->next!=NULL)
{ p=pre->next;
if (p->data>=pre->data) pre=p;
else return(0);
}
return(1);
7．已知一顺序表L，其元素值非递减有序排列，编写一个算法删除顺序表中值相同的多余元素。
8．已知带头结点的单链表L中的结点是按整数值递增排列的，试写一算法，将值为x的结点插入到表L中，使得L仍然递增有序，并且分析算法的时间复杂度。
第2章线性表习题解析(答)
第二章线性表练习题 一、选择题 1.线性表是具有n个的有限序列。 A、表元素 B、字符 C、数据元素 D、数据项 E、信息项 2.线性表的静态链表存储结构与顺序存储结构相比优点是。 A、所有的操作算法实现简单 B、便于随机存储 C、便于插入和删除 D、便于利用零散的存储器空间 3.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为。 A、O(log2n) B、O(1) C、O(n) D、O(n2) 4.（1）静态链表既有顺序存储的特点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关； （2）静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加；（3）静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是。 A、（1）、（2） B、（1） C、（1）、（2）、（3） D、（2） 6.在双向链表存储结构中，删除p所指的结点时须修改指针。 A、p－＞next－＞prior=p－＞prior; p－＞prior－＞next=p－＞next; B、p－＞next=p－＞next－＞next;p－＞next－＞prior=p; C、p－＞prior－＞next=p;p－＞prior=p－＞prior－＞prior; D、p－＞prior=p－＞next－＞next;p－＞next=p－＞prior－＞prior;
7.在双向循环链表中，在P指针所指的结点后插入q所指向的新结点，其修改指针的操作是。 A、p－＞next=q; q－＞prior=p;p－＞next－＞prior=q;q－＞next=q; B、p－＞next=q;p－＞next－＞prior=q;q－＞prior=p;q－＞next=p－＞next; C、q－＞prior=p; q－＞next=p－＞next; p－＞next－＞prior=q; p－＞next=q; D、q－＞next=p－＞next;q－＞prior=p;p－＞next=q;p－＞next=q; 8.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。 A、 n b、2n－1 c、2n d、n－1 9.在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动个元素。 A、n－i B、n－i+1 C、n－i－1 D、i 10.线性表L=(a1，a2,……an)，下列说法正确的是。 A、每个元素有有一个直接前驱和一个直接后继 B、线性表中至少有一个元素 C、表中诸元素的排列必须是由小到大或由大到小。 D、除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。 11.对单链表表示法，以下说法错误的是。 A、数据域用于存储线性表的一个数据元素 B、指针域(或链域)用于存放一指向本结点所含数据元素的直接后继所在结点的指针 C、所有数据通过指针的链接而组织成单链表 D、NULL称为空指针，它不指向任何结点只起标志作用
第6章线性空间练习题.doc
第6章 线性空间练习题 一、填空题（3515''?=） 1. 已知三维向量空间的一组基是123(1,0,1),(1,1,0),(2,1,1)ααα==-=，则向量(3,2,1)β=在这组基下的坐标是 ． 2. 从 R 2的基 1211,01αα????== ? ?-????到基1211,12ββ???? == ? ????? 的过渡矩阵为 ． 3. 已知132326583945A ?? ? = ? ??? ，则0AX =解空间的维数是 ，解空间一组基 是 ． 4. 设2 R 中定义11(,)(,)(,),(,)(,)a b c d a c b d k k a b ka kb αβα⊕=⊕=++++?=?=，则 2(,,)R R ⊕?，不作成线性空间的理由可以为 ． 5. 设Q 是有理数域，{,}Q a a b Q =+∈，关于实数的加法和乘法作成线性空间 (,,)Q Q +?，该空间的维数是 ． 二、单项选择题（3515''?=） 1. 在下列集合中，对指定的运算不能构成实数域R 上的一个线性空间的是 ( )． (A) 所有m ×n 的实矩阵，对矩阵的加法及数与矩阵的乘法 (B) 所有n 阶实对称矩阵，对矩阵的加法及数与矩阵的乘法 (C) 所有n 阶实反对称矩阵，对矩阵的加法及数与矩阵的乘法 (D) 所有n 阶可逆矩阵，对矩阵的加法及数与矩阵的乘法 2. 设V ＝R 3，下列集合为V 的子空间的是 ( )． (A) {}(,,)0a b c a b c ++= (B) {} (,,)0a b c a ≥ (C) { } 222 (,,)1a b c a b c ++≤ (D) {} (,,),,a b c a b c Q ∈(Q 为有理数域) 3. 下列线性空间中， ( )与其它三个空间不同构． (A) 2 (,,,)R R +? (B) (,,,)C R C +?是复数域 (C) 230{(,,)|}V x y z x y z =+-= (D) (,,,)C C C +?是复数域 4. 向量空间{}12123(,, ,)20n W x x x x x x =-+=，则W 的维数为( ) ． (A) 1 (B) 2 (C) n (D) n -1 5. 在n R 中，由基12,,,n ααα到基12,,,n βββ的过渡矩阵为C ，则C ＝ ( )． (A) 112 12()()n n αααβββ- (B) 11212()()n n αααβββ-
线性表练习题(答案)
第2章线性表 一选择题 下列程序段的时间复杂度为（ C ）。 for( int i=1;i<=n;i++) for( int j=1;j<= m; j++) A[i][j] = i*j ; A. O(m2) B. O(n2) C. O(m*n) D. (m+n) 下面关于线性表的叙述中，错误的是哪一个？（B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 线性表是具有n个（ C ）的有限序列（n>0）。 A．表元素B．字符C．数据元素D．数据项 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表B．仅有头指针的单循环链表 C．双链表D．仅有尾指针的单循环链表 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 A．单链表B．双链表C．单循环链表D．带头结点的双循环链表 链表不具有的特点是（ B ） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 下面的叙述不正确的是（B,C ） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C ）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ C ）A．O（i）B．O（1）C．O（n）D．O（i-1） 循环链表H的尾结点P的特点是（A ）。 A．P->next=H B．P->next= H->next C．P=H D．P=H->next 完成在双循环链表结点p之后插入s的操作是（D ）；
数据结构课后习题及答案
填空题（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; 求串长*/
线性空间试题.doc
向量空间 一 判断题 (1) 平面上全体向量对于通常的向量加法和数量乘法: ,,k k R αα=∈ 作成实数域R 上 的向量空间. ( ) . (2) 平面上全体向量对于通常的向量加法和数量乘法: 0,,k k R α=∈ 作成实数域R 上 的向量空间. ( ). (3) 一个过原点的平面上所有向量的集合是3V 的子空间. ( ). (4) 所有n 阶非可逆矩阵的集合为全矩阵空间()n M R 的子空间. ( ). (5) 121 {(,, ,)|1,}n n i i i x x x x x R ==∈∑为n R 的子空间. ( ). (6)所有n 阶实反对称矩阵的集合为全矩阵空间()n M R 的子空间. ( ). (7)11{(,0, ,0,)|,}n n x x x x R ∈为n R 的子空间. ( ). (8)若1234,,,αααα是数域F 上的4维向量空间V 的一组基, 那么122334,,,αααααα++ 是V 的一组基. ( ). (9)n 维向量空间V 的任意n 个线性无关的向量都可构成V 的一个基. ( ). (10)设12,, ,n ααα是向量空间V 中n 个向量, 且V 中每一个向量都可由12,, ,n ααα 线性表示, 则12,,,n ααα是V 的一组基. ( ). (11) 设12,,,n ααα是向量空间V 的一个基, 如果12,, ,n βββ与12,, ,n ααα等价, 则 12,,,n βββ也是V 的一个基. ( ). (12) 3x 关于基332,,1,1x x x x x +++的坐标为(1,1,0,0). ( ). (13)设12,,,s V V V 为n 维空间V 的子空间, 且12s V V V V =+++.若 12dim dim dim s V V V n ++ +=, 则12s V V V ++ +为直和. ( ). (14)设12,,,s V V V 为n 维空间V 的子空间, 且12s V V V V =++ +. 若 121230,()0,V V V V V =+=121,()0,S s V V V V -++ += 则12s V V V ++ +为直和.
数据结构实验报告 实验一 线性表链式存储运算的算法实现
昆明理工大学信息工程与自动化学院学生实验报告 （201 —201 学年第一学期） 课程名称：数据结构开课实验室：年月日年级、专业、班学号姓名成绩 实验项目名称线性表链式存储运算的算法实现指导教师 教 师 评语教师签名： 年月日 一.实验内容： 线性表链式存储运算的算法实现，实现链表的建立、链表的数据插入、链表的数据删除、链表的数据输出。 二.实验目的： 1.掌握线性表链式存储结构的C语言描述及运算算法的实现； 2.分析算法的空间复杂度和插入和删除的时间复杂度； 3.总结比较线性表顺序存储存储与链式存储的各自特点。 三.主要程序代码分析： LinkList creatListR1() //用尾插入法建立带头结点的单链表 { char *ch=new char(); LinkList head=(LinkList)malloc(sizeof(ListNode)); //生成头结点*head ListNode *s,*r,*pp; r=head; //尾指针初值指向头结点 r->next=NULL; scanf("%s",ch); //读入第一个结点的值 while(strcmp(ch,"#")!=0) { //输入#结束
pp=LocateNode(head,ch); if(pp==NULL) { s=(ListNode *)malloc(sizeof(ListNode)); //生成新的结点*s strcpy(s->data,ch); r->next=s; //新结点插入表尾 r=s; //尾指针r指向新的表尾 r->next=NULL; } scanf("%s",ch); //读入下一个结点的值 } return head; //返回表头指针 } int Insert(ListNode *head) //链表的插入 { ListNode *in,*p,*q; int wh; in=(ListNode *)malloc(sizeof(ListNode));in->next=NULL; //生成新结点p=(ListNode *)malloc(sizeof(ListNode));p->next=NULL; q=(ListNode *)malloc(sizeof(ListNode));q->next=NULL; scanf("%s",in->data); //输入插入的数据 scanf("%d",&wh); //输入插入数据的位置 for(p=head;wh>0;p=p->next,wh--); q=p->next; p->next=in; in->next=q; } void DeleteList(LinkList head,char *key) //链表的删除 { ListNode *p,*r,*q=head; p=LocateNode(head,key); //按key值查找结点的 if(p==NULL) exit(0); //若没有找到结点，退出 while(q->next!=p) //p为要删除的结点，q为p的前结点q=q->next; r=q->next; q->next=r->next; free(r); //释放结点*r } 四.程序运行结果：
线性表练习题答案
一、判断题 1．线性表的逻辑顺序与存储顺序总是一致的。(FALSE) 2．顺序存储的线性表可以按序号随机存取。(TRUE) 3．顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移动。（TRUE） 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。（TRUE） 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（FALSE） 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（TRUE）7．线性表的链式存储结构优于顺序存储结构。（FALSE） 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。（TRUE） 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（TRUE）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（FALSE） 二、单选题、(请从下列A，B，C，D选项中选择一项) 11．线性表是( ) 。 (A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。 答：A 12．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等 概率的。插入一个元素时平均要移动表中的（）个元素。 (A) n/2 (B) (n+1)/2 (C) (n –1)/2 (D) n 答：A 13．线性表采用链式存储时，其地址( D ) 。 (A) 必须是连续的；(B) 部分地址必须是连续的； (C) 一定是不连续的；(D) 连续与否均可以。 答：D 14．用链表表示线性表的优点是（）。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同 答：C 15. 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。 (A)单链表 (B)双链表 (C)单循环链表
数据结构线性结构习题
第一章 1．数据结构是一门研究非数值计算的程序设计问题中计算机 的 () 以及它们之间的 () 和运算等的学科。 2．数据的逻辑结构被形式的定义为B=（K，R），其中K是 () 的有限集合，R是K上的 的有限集合。 3．数据结构在计算机内存中的表示是指 () 。 4．在数据结构中，与所使用的计算机无关的是数据的 () 结构。 5．算法分析的目的是 () ，算法分析的两个主要方面是。 6．计算机算法指的是 () ，它必须具备输入，输出和 () 等5个特性。 7．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 () 。 8．以下说法正确的是：() A 数据元素是数据的最小单位。 B 数据项是数据的基本单位 C 数据结构是带结构的数据项的集合 D 一些表面上很不相同的数据可以有相同的逻辑结构 9．一个数据结构在计算机中的 () 称为存储结构。 10．数据结构，数据元素和数据项在计算机中的映射分别称为存储结构，节点和数据域。这 个断言正确否？ 11．有下列用二元组表示的数据结构，画出]它们分别对应的逻辑结构图形表示，并指出它 们分别属于何种结构。 （1）A=（K，R），其中：K={a,b,c,d,e,f,g,h}， R={
习题与复习题详解(线性空间)----高等代数
习题5. 1 1． 判断全体n 阶实对称矩阵按矩阵的加法与数乘是否构成实数域上的线性空间． 答 是． 因为是通常意义的矩阵加法与数乘, 所以只需检验集合对加法与数乘运算的封闭性. 由n 阶实对称矩阵的性质知，n 阶实对称矩阵加n 阶实对称矩阵仍然是n 阶实对称矩阵，数乘n 阶实对称矩阵仍然是n 阶实对称矩阵, 所以集合对矩阵加法与数乘运算封闭, 构成实数域上的线性空间. 2．全体正实数R +, 其加法与数乘定义为 ,,k a b ab k a a a b R k R +⊕==∈∈o 其中 判断R +按上面定义的加法与数乘是否构成实数域上的线性空间. 答 是. 设,R λμ∈. 因为,a b R a b ab R + + ?∈?⊕=∈, ,R a R a a R λλλ++?∈∈?=∈o , 所以R + 对定义的加法与数乘运算封闭. 下面一一验证八条线性运算规律 (1) a b ab ba b a ⊕===⊕; (2) ()()()()()a b c ab c ab c abc a bc a b c ⊕⊕=⊕====⊕⊕; (3) R +中存在零元素1, ?a R +∈, 有11a a a ⊕=?=; (4) 对R +中任一元素a ，存在负元素1n a R -∈, 使111a a aa --⊕==; (5)11a a a ==o ; (6)()()a a a a a λ μμλμλμλλμ??==== ??? o o o o ; (7) ()a a a a a a a a λμμμλλλμλμ++===⊕=⊕o o o ; 所以R +对定义的加法与数乘构成实数域上的线性空间. 3. 全体实n 阶矩阵，其加法定义为 按上述加法与通常矩阵的数乘是否构成实数域上的线性空间. 答 否. A B B A ∴⊕⊕与不一定相等. 故定义的加法不满足加法的交换律即运算规则（１）, 全体实n 阶矩阵按定义的加法与数乘不构成实数域上的线性空间. 4．在22P ?中，{}2222/0,,W A A A P W P ??==∈判断是否是的子空间.
数据结构_实验1_线性表的基本操作
实验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;
线性表练习题
一、火车出栈序列 （train.pas） 【题目描述】 输入n（n列火车),输出火车出栈的所有可能顺序。 【输入样例】 3 【输出样例】 3 2 1 2 3 1 2 1 3 1 3 2 1 2 3 【数据规模】 3<=n<=12 二、括号匹配 （LongestRegularBracketsSequence.pas） 【题目描述】 对一个由(，)，[，]括号组成的字符串，求出其中最长的括号匹配子串。具体来说，满足如下条件的字符串称为括号匹配的字符串：1．（），[]是括号匹配的字符串 2．若A是括号匹配的串,则(A),[A]是括号匹配的字符串 3．若A,B是括号匹配的字符串，则AB也是括号匹配的字符串。例如，(),[],([]),()()都是括号匹配的字符串，而][,[()],(]则不是。 字符串A的子串是指由A中连续若干个字符组成的字符串。 例如：A,B,C,ABC,CAB,ABCABC都是ABCABC的子串空串是任何字符串的子串。 【输入格式】 输入一行，为一个仅由()[]组成的非空字符串。 【输出格式】 输入也仅有一行，为最长的括号匹配子串。若有相同长度的子串，
输出位置靠前的子串。 【数据规模】 对20%的数据，字符串长度<=100； 对50%的数据，字符串长度<=10,000； 对100%的数据，字符串长度<=1,000,000； 三、马的最短步数 （horse.pas） 【题目描述】 求马在棋盘上从某个起点到某个终点的最少步数。 【输入格式】 第一行，n，m，表示棋盘有n行m列；(2 习题八查找 一、单项选择题 1．顺序查找法适合于存储结构为（）的线性表。 A．散列存储 B. 顺序存储或链式存储 C. 压缩存储 D. 索引存储 2.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 3．适用于折半查找的表的存储方式及元素排列要求为( ) A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 4．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( ) A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减5．当采用分块查找时，数据的组织方式为 ( ) A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 6．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（）。 A．正确 B. 错误 7. 二叉查找树的查找效率与二叉树的(（1） )有关, 在 (（2） )时其查找效率最低。 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 8．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。 A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性 9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。 A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110) 10．下图所示的4棵二叉树,( )是平衡二叉树。 （A）（B）（C）（D） 11．散列表的平均查找长度（）。 A．与处理冲突方法有关而与表的长度无关 B．与处理冲突方法无关而与表的长度有关 C．与处理冲突方法有关且与表的长度有关 D．与处理冲突方法无关且与表的长度无关 12. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（）个 空间向量与空间角试题 ————————————————————————————————作者：————————————————————————————————日期： 课时作业(二十) [学业水平层次] 一、选择题 1．若异面直线l 1的方向向量与l 2的方向向量的夹角为150°，则l 1与l 2所成的角为( ) A ．30° B ．150° C ．30°或150° D ．以上均不对 【解析】 l 1与l 2所成的角与其方向向量的夹角相等或互补，且异面直线所成角的范围为? ? ? ??0，π2.应选A. 【答案】 A 2．已知A (0,1,1)，B (2，－1,0)，C (3,5,7)，D (1,2,4)，则直线AB 与直线CD 所成角的余弦值为( ) A.522 66 B ．－52266 C.52222 D ．－52222 【解析】 AB →＝(2，－2，－1)，CD → ＝(－2，－3，－3)， ∴cos 〈AB →，CD →〉＝AB →·CD → |AB →||CD →|＝53×22＝522 66， ∴直线AB 、CD 所成角的余弦值为522 66. 【答案】 A 3．正方形ABCD 所在平面外一点P ，P A ⊥平面ABCD ，若P A ＝ AB ，则平面P AB 与平面PCD 的夹角为( ) A ．30° B ．45° C ．60° D ．90° 【解析】 如图所示，建立空间直角坐标系，设P A ＝AB ＝1.则A (0,0,0)，D (0,1,0)，P (0,0,1)．于是AD → ＝(0,1,0)． 取PD 中点为E ， 则E ? ? ???0，12，12， ∴AE →＝? ?? ??0，12，12， 易知AD →是平面P AB 的法向量，AE → 是平面PCD 的法向量，∴cos AD →，AE →＝22， ∴平面P AB 与平面PCD 的夹角为45°. 【答案】 B 4．(2014·陕西师大附中高二检测)如图3-2-29，在空间直角坐标系Dxyz 中，四棱柱ABCD —A 1B 1C 1D 1为长方体，AA 1＝AB ＝2AD ，点E 、F 分别为C 1D 1、A 1B 的中点，则二面角B 1-A 1B -E 的余弦值为( ) 一、判断题 1. 线性表的逻辑顺序与存储顺序总是一致的。(FALSE) 2. 顺序存储的线性表可以按序号随机存取。(TRUE) 3.顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移动。TRUE) 4.线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。(TRUE) 5，在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。(FALSE ) 6.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。(TRUE) 7.线性表的链式存储结构优于顺序存储结构。(FALSE ) 8. 在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。(TRUE) 9.线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。(TRUE) 10.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。(FALSE ) 二．选择题 11．线性表是()。 (A)一个有限序列，可以为空； (B)一个有限序列，不能为空； (C)一个无限序列，可以为空； (D)一个无序序列，不能为空。答：A 12．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（）个元素。 (A)n/2(B)(n+1)/2(C)(n–1)/2(D)n答：A 13．线性表采用链式存储时，其地址()。 (A)必须是连续的；(B)部分地址必须是连续的；(C)一定是不连续的；(D)连续与否均可以。答：D 14．用链表表示线性表的优点是（）。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同答：C 15.单链表中，增加一个头结点的目的是为了（）。 第六章 线性空间练习题参考答案 一、填空题 1.已知0000,,00V a b c a b c R c b ?????? ? =+∈?? ??? ?+???? 是33R ?的一个子空间，则维（V ） ＝ 3 ， V 的一组基是000000000100,100,010*********?????? ? ? ? ? ? ? ? ? ??????? . 2．在P 4中，若1234(1,2,0,1),(1,1,1,1),(1,,1,1),(0,1,,1)k k αααα===-=线性无关，则k 的取值范围是3k ≠（以1234,,,αααα为行或者列构成的行列式不为零）. 3．已知a 是数域P 中的一个固定的数，而1{(,,,),1,2,,}n i W a x x x P i n =∈=L L 是P n+1的一个子空间，则a ＝ 0 ，而维(W)＝n 4．维数公式为12dim dim V V +=1212dim()dim()V V V V ++I . 5．设123,,εεε是线性空间V 的一组基，112233x x x αεεε=++，则由基123 ,,εεε到基231,,εεε的过渡矩阵T ＝001100010?? ? ? ???，而α在基321,,εεε下的坐标是321(,,) x x x 由基123,,εεε到基233112,,εεεεεε+++的过渡矩阵为T ＝011101110?? ? ? ??? . 6．数域P 上n 级对称矩阵全体构成数域P 上 (1) 2 n n +维线性空间，数域P 上n 级反对称矩阵全体构成数域P 上 (1) 2 n n -维线性空间，数域P 上n 级上三角矩 姓名学号 ElemType data; //待插入元素 SqList L; //定义SqList类型变量 InitList_Sq(L); //初始化顺序表 printf("※1. 请输入所需建立的线性表的长度："); scanf_s("%d", &LIST_MAX); printf("※2. 请录入数据："); for (i = 0; i 第2章习题 (1) 第2章习题 2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last，在实现各基本运算时需要做那些修改？ 【解】 //用线性表最后一个元素的下标last代替listLen实现顺序表 #define MAXLEN 100 typedef int elementType; typedef struct sllLast { elementType data[MAXLEN]; int last; }seqList; //初始化 void initialList(seqList &S) { https://www.wendangku.net/doc/2e4930325.html,st=-1; } //求表长度 int listLength(seqList S) { return https://www.wendangku.net/doc/2e4930325.html,st+1; } //按序号取元素 bool getElement(seqList S,int i,elementType &x) { if(i<1 || i>https://www.wendangku.net/doc/2e4930325.html,st+1) //i为元素编号，有效范围在https://www.wendangku.net/doc/2e4930325.html,st+1之间 return false; else { x=S.data[i-1]; return true; } } //查找元素x，成功：返回元素编号；失败：返回0 int listLocate(seqList S,elementType x) { int i; for(i=0;i<=https://www.wendangku.net/doc/2e4930325.html,st;i++) { if(S.data[i]==x) return i+1; //找到，转换为元素编号输出} return 0; } //插入元素 int listInsert(seqList &S,elementType x, int i) { int k; if(https://www.wendangku.net/doc/2e4930325.html,st>MAXLEN-1) return 0; //表满，返回0 else if(i<1 || i>https://www.wendangku.net/doc/2e4930325.html,st+2) return 1; //插入位置查处范围，返回1 else { for(k=https://www.wendangku.net/doc/2e4930325.html,st;k>=i-1;k--) S.data[k+1]=S.data[k]; S.data[i-1]=x; https://www.wendangku.net/doc/2e4930325.html,st++; return 2; } } //删除元素 int listDelete(seqList &S,int i) { int k; if(https://www.wendangku.net/doc/2e4930325.html,st==-1) return 0; //空表，返回0 else if(i<1 || i>https://www.wendangku.net/doc/2e4930325.html,st+1) return 1; //删除元素编号超出范围，返回1 else数据结构习题及答案
空间向量与空间角试题
数据结构_线性表练习题
线性空间练习题参考答案
实验一线性表与应用(I)
第2章线性表习题解答