数据结构期中复习题完整版
- 格式：doc
- 大小：86.00 KB
- 文档页数：21
下载文档原格式
合集下载
数据结构期中考试试卷
数据结构期中考试试卷一、选择题（每题2分，共20分）1. 在数据结构中，线性结构的特点是什么？A. 元素之间存在一对一关系B. 元素之间存在一对多关系C. 元素之间存在多对多关系D. 元素之间存在一对一或多对多关系2. 以下哪个算法不是排序算法？A. 快速排序B. 归并排序C. 深度优先搜索D. 堆排序3. 在二叉树中，度为2的节点最多有多少个子节点？A. 1B. 2C. 3D. 44. 哈希表解决冲突的方法不包括以下哪一项？A. 分离链接法B. 开放寻址法C. 链地址法D. 树形结构法5. 以下哪个不是图的遍历算法？A. 深度优先搜索B. 广度优先搜索C. 动态规划D. 克鲁斯卡尔算法6. 栈的特点是？A. 后进先出B. 先进后出C. 先进先出D. 后进后出7. 以下哪个不是二叉搜索树的性质？A. 左子树上所有节点的值小于它的根节点的值B. 右子树上所有节点的值大于它的根节点的值C. 左子树和右子树都是二叉搜索树D. 所有节点的值都相等8. 在数据库中，索引的作用是什么？A. 增加数据存储空间B. 提高数据检索效率C. 降低数据插入速度D. 减少数据存储量9. 以下哪个不是图的存储结构？A. 邻接矩阵B. 邻接表C. 树形结构D. 边列表10. 递归算法的基本思想是什么？A. 将问题分解为更小的子问题B. 重复执行相同的操作C. 将问题转化为非递归形式D. 避免使用循环结构二、填空题（每题2分，共20分）1. 在数据结构中，______是一种特殊的线性表，只允许在一端进行插入和删除操作。
2. 排序算法中，______排序的时间复杂度为O(n^2)，适用于小规模数据的排序。
3. 在图的表示中，______矩阵可以有效地表示稠密图。
4. 哈希表中，______是指两个关键字通过哈希函数得到同一个哈希地址。
5. 栈和队列的主要区别在于，栈是______，而队列是先进先出。
6. 二叉树的遍历方式包括前序遍历、中序遍历和______遍历。
数据结构试卷(期中考试)
第页/共 页 《数据结构》期中考试试卷一、选择题（每题2分，共40分）1．组成数据的基本单位是【 】。
A ．数据项B ．数据类型C ．数据元素D ．数据变量 2．线性表采用链式存储时，结点的存储地址【 】。
A ．必须是不连续的 B ．连续与否均可C ．必须是连续的D ．和头结点的存储地址相连续3. 有一个含头结点的单链表，头指针为head ，判断其是否为空的条件为【 】。
A ．head==NULL B ． head->next==NULL C ．head->next==head D ．head!=NULL 4．算法分析的目的是【 】。
A ．辨别数据结构的合理性B ．评价算法的效率C ．研究算法中输入与输出的关系D ．鉴别算法的可读性5．已知指针p 所指结点不是尾结点，若在*p 之后插入结点*s ，则应执行下列哪一个操作？【 】。
A. s->next = p ； p-> next = s ；B. s-> next = p-> next ； p-> next = s ；C. s-> next = p-> next ； p = s ；D. p-> next = s ； s-> next = p ； 6．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可 能出现的出栈序列为【 】。
A ．3，2，6，1，4，5B ．5，6，4，2，3，1C ．1，2，5，3，4，6D ．3，4，2，1，6，5 7．一个元素进入队列的时间复杂度是【 】。
A O(1)B O(n)C O(n 2)D O(log 2n) 8．数组A[1..5,1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为【 】。
A 1140 B 1145 C 1120 D 1125 9．链表不具有的特点是【 】。
数据结构复习题及答案5篇
数据结构复习题及答案5篇第一篇：数据结构复习题及答案、数据结构复习题及答案中南大学现代远程教育课程考试（专科）复习题及参考答案数据结构一、判断题：1．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。
（）2．链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。
（）3．在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。
（）4．折半搜索只适用于有序表，包括有序的顺序表和有序的链表。
（）5．如果两个串含有相同的字符，则这两个串相等。
（）6．数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。
（）7．在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
（）8．通常递归的算法简单、易懂、容易编写，而且执行的效率也高。
（）9．一个广义表的表尾总是一个广义表。
（）10．当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。
（）11．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）。
（）12．存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。
（）13．直接选择排序是一种稳定的排序方法。
（）14．闭散列法通常比开散列法时间效率更高。
（）15．有n个结点的不同的二叉树有n!棵。
（）16．直接选择排序是一种不稳定的排序方法。
（）17．在2048个互不相同的关键码中选择最小的5个关键码，用堆排序比用锦标赛排序更快。
（）18．当3阶B_树中有255个关键码时,其最大高度(包括失败结点层)不超过8。
（）19．一棵3阶B_树是平衡的3路搜索树,反之,一棵平衡的3路搜索树是3阶非B_树。
（）20．在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。
数据结构期中考试题
一、单项选择题（每小题3分，共30分）1、线性结构是数据元素之间存在的一种_______。
A、一对多关系B、多对多关系C、多对一关系D、一对一关系2、以下数据结构中，哪一个不是线性结构（）A．生成树 B. 顺序栈 C. 单链表 D. 循环队列3、设n是偶数，则运行下列程序段的时间复杂度为（）。
x=100;for(p=2;p<=n;p++)for(q=2*i;q<=n;q++)x=(x+1)*3;A．O(1) B.O(n) C.O(n2) D.O(lbn)4、若频繁地对线性表进行插入和删除操作，该线性表应该采用——存储结构。
A、散列B、顺序C、链式D、索引5、在非空双向循环链表中由q所指的链结点后面插入一个由p所指的链结点的动作依次为：p->llink=Q；p->rlink=q->rlink;q->rlink=p；_______.(空白处为一条赋值语句) A、q->llink=p B、q->rlink->llink=pC、p->rlink->llink=pD、p->llink->llink=p6、设循环队列的结构是：const int Maxsize=100;typedef int Data Type;typedef struct {Data Type data[Maxsize];Int front, rear;} Queue;若有一个Queue类型的队列Q，试问判断队列满的条件应是下列哪一个语句（）A 、Q.front= = Q.rear; B、 Q.front - Q.rear= = Maxsize;C、Q.front + Q.rear= = Maxsize;D、 Q.front= = (Q.rear+1)% Maxsize;7、已知L是一个不带表头的单链表, 在表首插入结点*p的操作是（）。
A. p = L; p->next = L;B. p->next = L; p = L;C. p->next = L; L = p;D. L = p; p->next= L;8、下面关于串的叙述中，哪一个是不正确的？( )A．串是字符的有限序列 B.空串是由空格构成的串C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储9、若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为( )。
数据结构期中考试试题及答案
一、单项选择题(本题总分 20分，每题 2分)在每小题列出的四个选项中只有 一个选项是符合题目要求的，请将正确选项前的字母。
1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( D ) 。
A.顺序表 B.链表 C.索引表 D.散列表采用排除法，顺序表存储位置表示数据元素的顺序关系，跟关键字无法；链表的地址是动态分配的；索引表是 按数据元素的关键字排序所得，它的数据元素是没有规律的2.在长度为 n 的顺序表的第 i(1≤i ≤n+1)个位置上插入一个元素，元素的移动次数为( A ) 。
A.n -i+1B.n -iC.iD.i -1代入计算法，我们知道在 i=n+1 时不需要移动元素3.若一棵二叉树的先序遍历序列为 a,b,c ，则由 abc 三个结点构成的二叉树个数为( B ) 。
A.4B.5C.6D.74.三维数组 A[4][5][6]按行优先存储方法存储在内存中，若每个元素占 2 个存储单元，且数组中第一个元素的存 储地址为 130，则元素 A[3][4][5]的存储地址为(B A.370B .368C .366) 。
D.372Loc(3,4,5)=loc(0,0,0)+(3*5*6+4*6+5)*2=130+119*2=368;5.高度为 h 的二叉树（仅含根结点的二叉树高度为 1）的结点最少是多少( D) 。
A. h+1B. 2hC. 2h －1D. h二叉树性质 26. 将两个各有 n 个元素的有序表归并成一个有序表，其最多的比较次数是( A. nB.n+1 C. 2n-1D. n-17. 已知一算术表达式的中缀形式为 A ＋B *C -D/E ，后缀形式为 ABC *+DE/-，其前缀形式为( C) 。
A )。
A. -+A*BC/DE C. -+*ABC/DEB. –A+B*CD/E D. –A+B*C/DE根据中缀和后缀表达式可画出表达树如下：- + /A* D EBC故前缀表达式为：-+A*BC/DE数据结构期中考试8．下面图示的顺序存储结构表示的二叉树是（ A ）。
数据结构期中考试试题及答案
2014-2015学年第二学期《数据结构与算法》期中考试学号：姓名：一、写语句1.设单链表结点指针域为next，试写出删除链表中指针p所指结点的直接后继的C语言语句。
2.设单链表中某指针p所指结点（即p结点）的数据域为data，链指针域为next，请写出在p结点之前插入s结点的操作3. 设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre和next,试写出在指针p 所指结点之前插入s结点的C语言描述语句。
4. 一线性表存储在带头结点的双向循环链表中，L为头指针。
如下算法：（1）说明该算法的功能。
（2）在空缺处填写相应的语句。
void unknown (BNODETP *L){ …p=L->next; q=p->next; r=q->next；while (q!=L){ while (p!=L) && (p->data>q->data) p=p->prior；q->prior->next=r；(1) ______；q->next=p->next；q->prior=p；(2) ______；(3) ______；q=r；p=q->prior；(4) ______；} }二、写算法1．设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法：（要求用最少的时间和最小的空间）(1)确定在序列中比正整数x大的数有几个（相同的数只计算一次，如序列{20,20,17,16,15,15,11,10,8,7,7,5,4}中比10大的数有5个）；(2) 在单链表将比正整数x小的数按递减次序排列；(3) 将正整数（比）x大的偶数从单链表中删除。
2. 设键盘输入n个英语单词，输入格式为n, w1, w2, …,wn,其中n表示随后输入英语单词个数，试编一程序，建立一个单向链表，实现：（1）如果单词重复出现，则只在链表上保留一个。
数据结构期中测试题答案
《数据结构》期中测试班级：姓名：学号：一、填空题：1、在数据结构中，从逻辑上可以把数据结构分为集合、线性结构、树形结构和图状结构，其中树形结构和图状结构合称为非线性结构。
数据结构被形式地定义为二元组（D，S），其中D是数据元素的有限集合，S是D上关系的有限集合。
2、算法的五个重要特性是有穷性、确定性、可行性、输入和输出。
3、一个顺序表第一个元素的存储地址是100，每个元素的长度为3，则第6个元素的地址是115。
在顺序表中插入或删除一个元素，需要平均移动（n+1）/2个元素，具体移动的元素个数与插入或删除元素的位置有关。
顺序表中逻辑上相邻的元素的物理位置相邻。
单链表中逻辑上相邻的元素的物理位置不一定相邻。
单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的指针域指示。
在单链表中设置头结点的作用是使第一个结点与其他结点的操作统一。
4、从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（n+1）/2个结点。
在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是O（n）。
给定有n个元素的线性表，建立一个有序单链表的时间复杂度是O（n2）。
5、已知L是无表头结点的非空单链表，且指针p所指结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
在p所指结点后插入s所指结点：4、1。
在p所指结点前插入s所指结点：7、11、8、4、1。
在表首插入s所指结点：5、12。
在表尾插入s所指结点：11、9、1、6。
1)p->next=s;2)p->next=p->next->next;3)p->next=s->next;4)s->next=p->next;5)s->next=L;6)s->next=NULL;7)q=p;8)while(p->next!=q) p=p->next;9)while(p->next!=NULL) p=p->next;10)p=q;11)p=L;12)L=s;13)L=p;6、已知指针p所指结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。
级数据结构期中试卷(打印)
得分一、选择题（每小题2分，共30分）1．下面程序段的时间复杂度是（ ）。
for(i=0;i<2*n;i++) for(j=1;j<3*n;j++) A[i][j]=0;A ．O(n)； B. O(5n)； C ．O(6n 2)； D. O(n 2).2．在存储数据时，通常不仅要存储各数据元素的值，而且要有存储（ ）。
A ．数据的处理方法； B. 数据元素的类型； C ．数据元素之间的关系； D. 数据的存储方式.3. 若某线性表最常用的操作是存取任意指定序号的元素和在最后进行插入和删除操作，则利用哪种存储方式最节省时间（ ）。
A ．顺序表； B. 双链表； C ．带头结点的双循环链表； D. 单循环链表. 4. 设单链表的长度为n ，则删除第i （1≤i ≤n ）个结点的算法的时间复杂度为（ ）。
A ．O(1)； B. O(i)； C ．O(n)； D. O(n+i).5. 有n 个结点的线性表采用顺序表作为存储结构，要在第i （1≤i ≤n+1）个位置插入一个新结点时，需要移动的结点个数为（ ）。
A ．i ； B. n-i ； C ．i-n ； D. n-i+1.6. 对于一个头指针为head 的带头结点的单链表，判断该表为空的条件是（ ）。
A ．head==NULL ； B. head －>next==NULL ； C ．head －>next==head ； D. head!=NULL.7. 在头指针为head 且表长大于1的单循环链表中，指针p 指向表中某个结点，若p->next->next=head ，则（ ）。
A ．p 指向头结点； B. p 指向尾结点；C ．*p 的直接后继是头结点； D. *p 的直接后继是尾结点. 8. 执行如下语句后，*(xp+2)的值为 int x[ ]={2,5,6,8},*xp; xp=x;A ．2 ； B. 5 ； C ．6 ； D. 8.9. 删除双链表中间某个结点，需要修改（ ）个指针域。
《数据结构》期中试题(有答案)
福建师范大学数学与计算机科学学院
2009--2010学年度上学期08电信
《数据结构》期中试题
试卷类别：闭卷考试时间：90分钟
倚窗远眺，目光目光尽处必有一座山，那影影绰绰的黛绿色的影，是春天的颜色。
周遭流岚升腾，没露出那真实的面孔。
面对那流转的薄雾，我会幻想，那里有一个世外桃源。
在天阶夜色凉如水的夏夜，我会静静地，静静地，等待一场流星雨的来临…
许下一个愿望，不乞求去实现，至少，曾经，有那么一刻，我那还未枯萎的，青春的，诗意的心，在我最美的年华里，同星空做了一次灵魂的交流…
秋日里，阳光并不刺眼，天空是一碧如洗的蓝，点缀着飘逸的流云。
偶尔，一片飞舞的落叶，会飘到我的窗前。
斑驳的印迹里，携刻着深秋的颜色。
在一个落雪的晨，这纷纷扬扬的雪，飘落着一如千年前的洁白。
窗外，是未被污染的银白色世界。
我会去迎接，这人间的圣洁。
在这流转的岁月里，有着流转的四季，还有一颗流转的心，亘古不变的心。
数据结构期中试卷及答案
一、选择题（每小题2分，共30分）1. 数据结构是（ D ）。
A．一种数据类型 B．数据的存储结构C．一组性质相同的数据元素的集合D．相互之间存在一种或多种特定关系的数据元素的集合2．以下与数据的存储结构无关的术语是（ D ）。
A．链队列 B. 链表 C. 顺序表 D. 栈3．以下数据结构中，（ A ）是非线性数据结构A．树 B．字符串 C．队 D．栈4．一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（B）。
A．98 B．100 C．102 D．1065．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D ）。
A．插入 B．删除 C．排序 D．查找6．线性表采用链式存储时，其地址(D )。
A．必须是连续的 B．一定是不连续的C．部分地址必须连续 D．连续与否均可以7．线性表是(A )。
A．一个有限序列，可以为空 B．一个有限序列，不可以为空C．一个无限序列，可以为空 D．一个无限序列，不可以为空8．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ B ）。
A．3，2，6，1，4，5 B．3，4，2，1，6，5C．1，2，5，3，4，6 D．5，6，4，2，3，19. 若一个栈的输人序列是1，2，3，…，n，输出序列的第一个元素是n，则第k个输出元素是（C ）。
A．k B．n-k-1 C．n-k+1 D．不确定10.对于队列操作数据的原则是（ A ）。
A. 先进先出B. 后进先出C. 先进后出D. 不分顺序11. 栈和队列的共同点是（ C ）。
A. 都是先进先出B. 都是先进后出C. 只允许在端点处插入和删除元素D. 没有共同点12．在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（ A ）。
A．front=front->next B．rear=rear->nextC．rear->next=front D．front->next＝rear13. 空串与空格串（ B ）。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
7.编写一个算法来交换单链表中指针p所指结点与其后继结点，head是该链表的头指针，p指向该链表中某一结点。
8.假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值非递增次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
9.编写一个算法，设有两个无头结点的单链表，头指针分别为ha、hb,两个链表的数据都按递增序存放。要求将hb归并到ha表中,且归并后ha仍递增序，在归并中对于ha表中已有的数据若hb中的这部分也有，则hb中的这部分数据不归并到ha中，hb的链表在算法中不允许破坏。
A．p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;
B．p->next=s; p->next->prior=s;s->prior=p; s->next=p->next;
C．s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;
2.【答案】D
本题程序中每次循环将y的值增加1，然后比较n与y+1的平方大小，所以总共要进行根号n次比较。
3.【答案】D
在线性表的第1至第n个位置插入一个数据元素显然是允许的，紧挨在线性表最后那个数据元素后面插入一个数据元素也是允许的，因此，i的合法值应该是1≦i≦n+1。
4.【答案】C
只有删除非空线性表的第1至第n个数据元素才是可能的，因此，i的合法值应1≦i≦n。
5.【答案】A
删除线性表中的第i个数据元素，需要将线性表的第i+1个数据元素至第n个数据元素依次前移1个位置，一共需要移动n-i个数据元素。
6.【答案】C
在线性表的第i个位置插入一个新的数据元素之前，需要先将线性表的第i个数据元素至第n个数据元素依次后移1个位置，一共需要移动n-i+1个数据元素。
7.【答案】D
A 1，3，2，4 B. 2，3，4，1C.4，3，1，2D. 3, 4 , 2, 1
3．设栈的初始状态为空，当字符序列n1_作为栈的输入时，输出长度为3的且可用作C语言标识符的序列有（）个。
A.3 B.4 C.5 D.6
4.若某栈的输入序列是1，2，3，…，n，输出序列的第一个元素为n，则第i个输出元素为（）。
y++;
}
A.O(n)B.O(n2)C.O(1)D.O(√n)
3.若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值应该是（）
A．i>0 B.i≤n C.1≤i≤nD.1≤i≤n+1
4.若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，i的合法值应该是（）。
D.线性表采用链接存储，便于插入和删除操作
17.以下关于链式存储结构的叙述中，（）是不正确的。
A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构
B.逻辑上相邻的结点物理上不必相邻
C.可以通过计算直接确定第i个结点的存储地址
D.插入、删除运算操作方便，不必移动结点
18.如某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
（1）描述算法的基本设计思想；
（2）描述算法的详细实现步骤；
（3）根据设计思想和实现步骤，采用程序设计语言描述算法，关键之处请给出简要注
4.假设一个单循环链表，其结点含有三个域（pre，data，next）。其中data为数据域；pre为指针域，它的值为空指针；next为指针域，它指向后继结点。请设计算法，将此表改成双向链表。
C.便于插入和删除D.便于利用零散的存储空间
22.下面说法正确的是( )
A.集合与线性表的区别在于是否按关键排序
B.对于任何数据结构，链式存储结构一定优于顺序存储结构
C.链表中的头结点仅起到标识作用
D.在单链表中设置头结点的作用主要是使插入和删除等操作统一，在第一个元素之前插
元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。
二、综合应用题
1.线性表(a1,a2,a3,…,a4)采用顺序存储，每个元素都是整数，试设计算法用最少时间把所有值为负数的元素移到全部正数值元素前边的算法。例:(x,-x,-x,x,x,-x…x)变为(-x,-x,-x…x,x,x)。
2.线性表(a1,a2,a3,…,an)中元素递增有序按顺序存储，要求设计算法完成下述功能:
本题主要考查线性表的顺序存储结构的特点。
8.【答案】D
若线性表采用链式存储结构，各链结点之间的地址连续可以，不连续也可以（但每一个链
第二章 栈、列队和数组
一、单项选择题
1.栈和列队的相同之处是（）。
A．元素的进出满足先进后出B．元素的进出满足先进先出
C．只允许在端点进行插入和删除操作D.无共同点
2.某栈的输入序列为1，2，3，4，下面的四个序列中（）不可能是它的输出序列。
A.带表头结点的单链表，一个链表指针指向表头结点
B.带表头结点的单循环链表，一个链表指针指向表头结点
C.不带表头结点的单链表，一个链表指针指向表的第一个结点
D.不带表头结点的单循环链表，一个链表指针指向表的第一个结点
21.线性表的静态链表存储结构与顺序存储结构相比优点是( )。
A.所有的操作算法实现简单B.便于随机存储
A.p=p->next; B.p->next=p; C.p->next=p->next->next; D.p=p->next->next;
14.设双向链表中结点的结构为（prior，data，next），在双向链表中删除指针p所指的结点时需要修改指针（）
A.p->prior->next=p->next; p->next->prior=p->prior;
D．s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;
16.下面关于线性表的叙述中，错误的是哪一个（）。
A.线性表采用顺序存储，必须占用一片连续的存储单元
B.线性表采用顺序存储，便于进行插入和删除操作
C.线性表采用链接存储，不必占用一片连续的存储单元
A.i B.n-iC.n-i+1D.以上都不对
5.设栈的输入序列为1，2，3，…，n，输出序列为a1 ,a2, a3,…，an，若存在1≤k≤n时ak=n，则当k≤i≤n 时ai为（ ）。
A.n-i+1 B.n-i+k C.n-i-1 D.不确定
6.若进栈序列为a，b，c，则通过出栈操作可能得到的a，b，c的不同排列个数为（）。
9.给定n个数据元素，逐个输入这些元素，建立一个有序单链表的时间复杂度是（）。
A.O(1) B.O(n) C.O(n2) D.O(nlogn)
10.线性表（a1,a2,…,an）以链接方式存储时，访问第i个位置元素的时间复杂度为（）
A.O(i) B.O(1) C.O(n) D.O(i-1)
11.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）。
12.已知线性表第一个链接点指针为list,请写一算法，将该链表分解为两个有头结点的循环链表，并将两个循环链表的长度分别存放在各自头结点的数据域中。其中，线性表中序号为奇数的元素分解到第一个循环链表中，序号为偶数的元素分解到第二个循环链表中。（要求用最少的时间和最少的空间）
13.设键盘输入n个英语单词，输入格式为n,w1,w2,…wn,其中n表示随后输入英语单词个数，试编一程序，建立一个单链表，实现：
10.已知L1、L2分别为两个单循环链表的头结点指针，m、n分别为L1、L2表中数据结点个数。要求设计一个算法，用最快速度将两表合并成一个带头结点的单循环链表。
11.已知不带头结点的线性表list，链表中结点构造为(data,next)，其中data为数据域，next为指针域。请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链接点空间。
第一章
一、单项选择题
1.对于数据结构下列结论不正确的是（）
A.相同的逻辑结构，对应的存储结构也必相同
B.数据结构由逻辑结构、存储结构和基本操作3个方面组成
C.数据存储结构就是数据逻辑结构的机内的实现
D.对数据基本操作的实现与存储结构有关
2.下面算法的时间复杂度是（）
int y=0;
while(n>=(y+1)*(y+1)){
（1）用最少时间在表中查找数值为x的元素；
（2）若找到将其与后继元素位置相交换；
（3）若找不到将其插入表中并使表中元素仍递增有序
3.已知一个带有头结点的单链表，假设该链表只给出了头指针L，在不改变链表的前提下，
请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k为正整数)，若查找成功，算法输出该结点的data域的.6
7.设计一个递归问题的非递归算法通常需要设置（）结构。
A.线性表 B.数组C.栈D.队列
8.当执行函数时其局部变量的存储一般采用（）进行存储。
A.树 B.静态链表 C.栈 D.队列
9.向一个栈顶指针为top的链栈中插入一个x节点，则执行（）。
A.top->next=x B.x->next=top->next; top->next=x;
（1）如果单词重复出现，则只在链表上保留一个；
（2）除满足（1）的要求外，链表结点还应有一个频度域，记录该单词重复出现的次数，然后输出出现次数最多的前k（k<=n）个单词。
8.假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值非递增次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
9.编写一个算法，设有两个无头结点的单链表，头指针分别为ha、hb,两个链表的数据都按递增序存放。要求将hb归并到ha表中,且归并后ha仍递增序，在归并中对于ha表中已有的数据若hb中的这部分也有，则hb中的这部分数据不归并到ha中，hb的链表在算法中不允许破坏。
A．p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;
B．p->next=s; p->next->prior=s;s->prior=p; s->next=p->next;
C．s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;
2.【答案】D
本题程序中每次循环将y的值增加1，然后比较n与y+1的平方大小，所以总共要进行根号n次比较。
3.【答案】D
在线性表的第1至第n个位置插入一个数据元素显然是允许的，紧挨在线性表最后那个数据元素后面插入一个数据元素也是允许的，因此，i的合法值应该是1≦i≦n+1。
4.【答案】C
只有删除非空线性表的第1至第n个数据元素才是可能的，因此，i的合法值应1≦i≦n。
5.【答案】A
删除线性表中的第i个数据元素，需要将线性表的第i+1个数据元素至第n个数据元素依次前移1个位置，一共需要移动n-i个数据元素。
6.【答案】C
在线性表的第i个位置插入一个新的数据元素之前，需要先将线性表的第i个数据元素至第n个数据元素依次后移1个位置，一共需要移动n-i+1个数据元素。
7.【答案】D
A 1，3，2，4 B. 2，3，4，1C.4，3，1，2D. 3, 4 , 2, 1
3．设栈的初始状态为空，当字符序列n1_作为栈的输入时，输出长度为3的且可用作C语言标识符的序列有（）个。
A.3 B.4 C.5 D.6
4.若某栈的输入序列是1，2，3，…，n，输出序列的第一个元素为n，则第i个输出元素为（）。
y++;
}
A.O(n)B.O(n2)C.O(1)D.O(√n)
3.若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值应该是（）
A．i>0 B.i≤n C.1≤i≤nD.1≤i≤n+1
4.若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，i的合法值应该是（）。
D.线性表采用链接存储，便于插入和删除操作
17.以下关于链式存储结构的叙述中，（）是不正确的。
A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构
B.逻辑上相邻的结点物理上不必相邻
C.可以通过计算直接确定第i个结点的存储地址
D.插入、删除运算操作方便，不必移动结点
18.如某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
（1）描述算法的基本设计思想；
（2）描述算法的详细实现步骤；
（3）根据设计思想和实现步骤，采用程序设计语言描述算法，关键之处请给出简要注
4.假设一个单循环链表，其结点含有三个域（pre，data，next）。其中data为数据域；pre为指针域，它的值为空指针；next为指针域，它指向后继结点。请设计算法，将此表改成双向链表。
C.便于插入和删除D.便于利用零散的存储空间
22.下面说法正确的是( )
A.集合与线性表的区别在于是否按关键排序
B.对于任何数据结构，链式存储结构一定优于顺序存储结构
C.链表中的头结点仅起到标识作用
D.在单链表中设置头结点的作用主要是使插入和删除等操作统一，在第一个元素之前插
元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。
二、综合应用题
1.线性表(a1,a2,a3,…,a4)采用顺序存储，每个元素都是整数，试设计算法用最少时间把所有值为负数的元素移到全部正数值元素前边的算法。例:(x,-x,-x,x,x,-x…x)变为(-x,-x,-x…x,x,x)。
2.线性表(a1,a2,a3,…,an)中元素递增有序按顺序存储，要求设计算法完成下述功能:
本题主要考查线性表的顺序存储结构的特点。
8.【答案】D
若线性表采用链式存储结构，各链结点之间的地址连续可以，不连续也可以（但每一个链
第二章 栈、列队和数组
一、单项选择题
1.栈和列队的相同之处是（）。
A．元素的进出满足先进后出B．元素的进出满足先进先出
C．只允许在端点进行插入和删除操作D.无共同点
2.某栈的输入序列为1，2，3，4，下面的四个序列中（）不可能是它的输出序列。
A.带表头结点的单链表，一个链表指针指向表头结点
B.带表头结点的单循环链表，一个链表指针指向表头结点
C.不带表头结点的单链表，一个链表指针指向表的第一个结点
D.不带表头结点的单循环链表，一个链表指针指向表的第一个结点
21.线性表的静态链表存储结构与顺序存储结构相比优点是( )。
A.所有的操作算法实现简单B.便于随机存储
A.p=p->next; B.p->next=p; C.p->next=p->next->next; D.p=p->next->next;
14.设双向链表中结点的结构为（prior，data，next），在双向链表中删除指针p所指的结点时需要修改指针（）
A.p->prior->next=p->next; p->next->prior=p->prior;
D．s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;
16.下面关于线性表的叙述中，错误的是哪一个（）。
A.线性表采用顺序存储，必须占用一片连续的存储单元
B.线性表采用顺序存储，便于进行插入和删除操作
C.线性表采用链接存储，不必占用一片连续的存储单元
A.i B.n-iC.n-i+1D.以上都不对
5.设栈的输入序列为1，2，3，…，n，输出序列为a1 ,a2, a3,…，an，若存在1≤k≤n时ak=n，则当k≤i≤n 时ai为（ ）。
A.n-i+1 B.n-i+k C.n-i-1 D.不确定
6.若进栈序列为a，b，c，则通过出栈操作可能得到的a，b，c的不同排列个数为（）。
9.给定n个数据元素，逐个输入这些元素，建立一个有序单链表的时间复杂度是（）。
A.O(1) B.O(n) C.O(n2) D.O(nlogn)
10.线性表（a1,a2,…,an）以链接方式存储时，访问第i个位置元素的时间复杂度为（）
A.O(i) B.O(1) C.O(n) D.O(i-1)
11.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）。
12.已知线性表第一个链接点指针为list,请写一算法，将该链表分解为两个有头结点的循环链表，并将两个循环链表的长度分别存放在各自头结点的数据域中。其中，线性表中序号为奇数的元素分解到第一个循环链表中，序号为偶数的元素分解到第二个循环链表中。（要求用最少的时间和最少的空间）
13.设键盘输入n个英语单词，输入格式为n,w1,w2,…wn,其中n表示随后输入英语单词个数，试编一程序，建立一个单链表，实现：
10.已知L1、L2分别为两个单循环链表的头结点指针，m、n分别为L1、L2表中数据结点个数。要求设计一个算法，用最快速度将两表合并成一个带头结点的单循环链表。
11.已知不带头结点的线性表list，链表中结点构造为(data,next)，其中data为数据域，next为指针域。请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链接点空间。
第一章
一、单项选择题
1.对于数据结构下列结论不正确的是（）
A.相同的逻辑结构，对应的存储结构也必相同
B.数据结构由逻辑结构、存储结构和基本操作3个方面组成
C.数据存储结构就是数据逻辑结构的机内的实现
D.对数据基本操作的实现与存储结构有关
2.下面算法的时间复杂度是（）
int y=0;
while(n>=(y+1)*(y+1)){
（1）用最少时间在表中查找数值为x的元素；
（2）若找到将其与后继元素位置相交换；
（3）若找不到将其插入表中并使表中元素仍递增有序
3.已知一个带有头结点的单链表，假设该链表只给出了头指针L，在不改变链表的前提下，
请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k为正整数)，若查找成功，算法输出该结点的data域的.6
7.设计一个递归问题的非递归算法通常需要设置（）结构。
A.线性表 B.数组C.栈D.队列
8.当执行函数时其局部变量的存储一般采用（）进行存储。
A.树 B.静态链表 C.栈 D.队列
9.向一个栈顶指针为top的链栈中插入一个x节点，则执行（）。
A.top->next=x B.x->next=top->next; top->next=x;
（1）如果单词重复出现，则只在链表上保留一个；
（2）除满足（1）的要求外，链表结点还应有一个频度域，记录该单词重复出现的次数，然后输出出现次数最多的前k（k<=n）个单词。