2022年数据结构期中考试试卷答案 .pdf

《2022年数据结构期中考试试卷答案 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构期中考试试卷答案 .pdf（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、（第 1 页，共 3 页）20142015 学年度第一学期数据结构期中考试试卷一、选择题（每题2 分，共 20 分）1. 计算机内部数据处理的基本单位是（ B ） 。A.数据 B.数据元素C.数据项D.数据库2. 设语句 x+的时间是单位时间，则以下语句的时间复杂度为（B） 。for(i=1; i=n; i+) for(j=i; j=n; j+) x+; A.O(1) B.O(2n) C.O(n) D.O(3n) 3. 在一个长度为n 的顺序表中删除第i 个元素 (0=inext=p-next; p-next=s Bq-next=s; s-next=p Cp-next=s-next; s-ne

2、xt=p Dp-next=s; s-next=q 5. 在一个具有n 个单元的顺序栈中，假定以地址低端（即0 单元）作为栈底，以top 作为栈顶指针，当做出栈处理时，top 变化为 _。C Atop 不变B top=0 Ctop- Dtop+ 6. 在具有 n 个单元的顺序存储的循环队列中，假定 front和 rear 分别为队头指针和队尾指针，则判断队满的条件为_。D Arear n= = front B （front+l） n= = rear Crear n -1= = front D(rear+l)n= = front 7. 两个字符串相等的条件是（D ） 。A.两串的长度相等 B.两串

3、的长度相等，并且两串包含的字符相同C.两串包含的字符相同 D.两串的长度相等，并且对应位置上的字符相同8. 数组 A中，每个元素的长度为3 个字节，行下标i 从 1 到 8，列下标 j 从 1 到 10，从首地址 SA开始连续存放在存储器内，该数组按行存放时，元素A85的起始地址为（ C ） 。A.SA+141 B.SA+144 C.SA+222 D.SA+225 9. 设有广义表D=(a,b,D) ，其长度为（ B ） ，深度为（ A ） 。A.无穷大B.3 C.2 D.5 10. 假设在一棵二叉树中， 双分支结点数为15， 单分支结点数为30 个，则叶子结点数为 （B ）个。A. 15 B

4、. 16 C. 17 D. 47 二、填空题（每空1 分，共 20 分）1. 数据的逻辑结构有四种基本形态，分别是_、_、_和_。2. 集合，线性，树，图2. 一个算法的效率可分为_效率和 _效率。 4. 时间，空间3. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用 _存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_存储结构为宜。7顺名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - （第 2 页，

5、共 3 页）序，链接4. 对于一个具有n 个结点的单链表，在已知的结点p 后插入一个新结点的时间复杂度为_，在给定值为x 的结点后插入一个新结点的时间复杂度为_。12O(1) ，O(n) 5. 可以在线性表的_位置插入和删除元素；对于栈只能在_位置删除元素；对于队列只能在 _位置插入元素。9 任何，栈顶，队尾6. 设字符串S1= “ABCDEF”，S2= “PQRS ”，则运算S=CONCAT（SUB （S1，2，LEN （S2） ） ，SUB （S1，LEN （S2） ，2） ）后的串值为 _。3. “BCDEDE”7. 一维数组的逻辑结构是_，存储结构是 _；对于二维或多维数组，分为 _和

6、_两种不同的存储方式。1. 线性结构，顺序结构，以行为主序，以列为主序8. 三维数组Rc1,d1,c2,d2,c3,d3 共含有 _个元素。 （其中：c1d1,c2d2,c3d3）9. （d1-c1+1）（ d2-c2+1）（ d3-c3+1）9. 数组 A1,10，-2 , 6，2,8 以行优先的顺序存储，设第一个元素的首地址是100，每个元素占 3 个存储长度的存储空间，则元素 A5 ，0，7 的存储地址为 _。10. 913 三、简答题（每题6 分，共 18 分）1. 已知 L 是无表头结点的单链表，且 P结点既不是首元结点也不是尾元结点，试写出合适的语句序列。 (1) 在 P结点后插入

7、S结点。 (2) 在表首插入S结点。 (3) 在表尾插入S结点。2 已知 L 是带表头结点的非空单链表，且P结点既不是首元结点也不是尾元结点，试写出合适的语句序列。(1) 删除 P结点的直接后继结点。(2) 删除 P结点。（3）删除尾元结点。3 LinkList mynote(LinkList L) /L是不带头结点的单链表的头指针 if(L&L-next) q=L；L=Lnext ；p=L； S1： while(pnext) p=pnext ； S2： p next=q ； qnext=NULL； return L； 请回答下列问题： （1）说明语句S1的功能；（2）说明语句组S2的功能；（

8、3）设链表表示的线性表为（ a1,a2, ,an）, 写出算法执行后的返回值所表示的线性表。该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。四、算法设计题（每题14 分，共 42 分）1. 假设有一个循环链表的长度大于1，且表中既无头结点也无头指针，已知 p 为指向链表中某结点的指针，设计在链表中删除p 所指结点的前趋结点的算法。解： 可引入一个指针q，当 q-next=p 时，说明此时q 所指的结点为p 所指结点的前趋结点，从而可得算法如下：void delete (LinkList *p) /在链表中删除p 所指结点

9、的前趋结点LinkList *q,*t; q=p; while(q-next-next!=p) /q-next 不是 p 的前趋结点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - （第 3 页，共 3 页）q=q-next; t=q-next; /t 指向要删除结点q-next=p; /删除 t 结点free(t); 2. 已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于max 但大于 mi

10、n 的元素的算法。2算法描述如下：delete(LinkList *head, int max, int min) LinkList *p,*q; q=head; p=head-next; while (p!=NULL) if(p-datadata=max) q=p; p=p-next; else q-next=p-next; free(p); p=q-next; 3. 假设表达式有单字母变量和双目四则运算符构成。试写一个算法，对一个通常书写形式且书写正确的表达式求值。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -