《数据结构期中考试试卷答案资格考试教师资格考试_资格考试-教师资格考试.pdf》由会员分享，可在线阅读，更多相关《数据结构期中考试试卷答案资格考试教师资格考试_资格考试-教师资格考试.pdf（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、学习必备 欢迎下载 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-next=p Dp-next=s;s-n
2、ext=q 5.在一个具有 n 个单元的顺序栈中，假定以地址低端（即 0 单元）作为栈底，以 top 作为栈顶指针，当做出栈处理时，top 变化为_。C Atop 不变 Btop=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.两串的长度相等，并且两串包含的字符相同 C.两串包含的字符相同 D.两串的长度相等
3、，并且对应位置上的字符相同 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.16 C.17 D.47 二、填空题（每空 1分，共 20分）1.数据的逻辑结构有四种基本形
4、态，分别是_、_、_和_。2.集合，线性，树，图 2.一个算法的效率可分为_效率和_效率。4.时间，空间 3.当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_存储结构为宜。7顺学习必备 欢迎下载 序，链接 4.对于一个具有 n 个结点的单链表，在已知的结点 p 后插入一个新结点的时间复杂度为_，在给定值为 x 的结点后插入一个新结点的时间复杂度为_。12O(1)，O(n)5.可以在线性表的_位置插入和删除元素；对于栈只能在_位置删除元素；对于队列只能在_位置插入元素。9 任何，栈顶，队尾 6.设字符串 S1=“AB
5、CDEF”，S2=“PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2），SUB（S1，LEN（S2），2）后的串值为_。3.“BCDEDE”7.一维数组的逻辑结构是_，存储结构是_；对于二维或多维数组，分为_和_两种不同的存储方式。1.线性结构，顺序结构，以行为主序，以列为主序 8.三维数组 Rc1d1,c2d2,c3d3 共含有_个元素。（其中：c1d1,c2d2,c3d3）9.（d1-c1+1）（d2-c2+1）（d3-c3+1）9.数组 A110，-26，28 以行优先的顺序存储，设第一个元素的首地址是 100，每个元素占 3 个存储长度的存储空间，则元素 A5，0，7
6、 的存储地址为_。10.913 三、简答题（每题 6分，共 18分）1.已知 L是无表头结点的单链表，且 P结点既不是首元结点也不是尾元结点，试写出合适的语句序列。(1)在 P结点后插入 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(pne
7、xt)p=p next；S2：p next=q；qnext=NULL；return L；请回答下列问题：（1）说明语句 S1 的功能；（2）说明语句组 S2 的功能；（3）设链表表示的线性表为（a1,a2,an）,写出算法执行后的返回值所表示的线性表。该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。四、算法设计题（每题 14分，共 42分）1.假设有一个循环链表的长度大于 1，且表中既无头结点也无头指针，已知 p 为指向链表中某结点的指针，设计在链表中删除 p 所指结点的前趋结点的算法。解：可引入一个指针 q，当 q-n
8、ext=p时，说明此时 q 所指的结点为 p 所指结点的前趋结点，从而可得算法如下：void delete(LinkList*p)/在链表中删除 p 所指结点的前趋结点 LinkList*q,*t;q=p;while(q-next-next!=p)/q-next不是 p 的前趋结点 数据数据元素数据项数据库设语句的时间是单位时间则以下语句的时间复杂度为在一个长度为的顺序表中删除第个元素时需向前移动个元素在一个单链表中已知结点是结点的前趋结点若在和之间插入结点则须执行在一个具有个单元的循环队列中假定和分别为队头指针和队尾指针则判断队满的条件为两个字符串相等的条件是两串的长度相等两串的长度相等并且
9、两串含的字符相同两串含的字符相同两串的长度相等并且对应位置上的字符相同数组中每个元素的长义表其长度为深度为无穷大假设在一棵二叉树中双分支结点数为单分支结点数为个则叶子结点数为个二填空题每空分共分数据的逻辑结构有四种基本形态分别是和集合线性树图一个算法的效率可分为效率和效率时间空间当对一个线学习必备 欢迎下载 q=q-next;t=q-next;/t 指向要删除结点 q-next=p;/删除 t 结点 free(t);2.已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于 max 但大于 min 的元素的算法。2算法描述如下：delete(LinkList*h
10、ead,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.假设表达式有单字母变量和双目四则运算符构成。试写一个算法，对一个通常书写形式且书写正确的表达式求值。数据数据元素数据项数据库设语句的时间是单位时间则以下语句的时间复杂度为在一个长度为的顺序表中删除第个元素时需向前移动个元素在一个单链表中已知结点是结点的前趋结点若在和之间插入结点则须执行在一个具有个单元的循环队列中假定和分别为队头指针和队尾指针则判断队满的条件为两个字符串相等的条件是两串的长度相等两串的长度相等并且两串含的字符相同两串含的字符相同两串的长度相等并且对应位置上的字符相同数组中每个元素的长义表其长度为深度为无穷大假设在一棵二叉树中双分支结点数为单分支结点数为个则叶子结点数为个二填空题每空分共分数据的逻辑结构有四种基本形态分别是和集合线性树图一个算法的效率可分为效率和效率时间空间当对一个线