常熟理工学院《数据结构》考试试卷

系班级学号（9位）姓名———————————阅————卷————密————封————装————订————线——————————第1页/共2页常熟理工学院《数据结构》考试试卷试题总分：70分考试时限:50分钟题号一二三四五总分阅卷人核分人得分一、单项选择题（每题2分，共40分）B1、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。A.结构B.关系C.运算D.算法B2、在以下叙述中，正确的是（）。A.线性表的线性存储结构优于链表的存储结构B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出A3、下面程序段的时间复杂度是（）。i=s=0;while(sn){i++;s+=i;}A.O(n)B.O(n2)C.O(log2n)D.O(√n)A4、判断一个循环队列Q（空间大小为M）为空的条件是（）。A.Q-front==Q-rearB.Q-rear-Q-front-1==MC.Q-front+1=Q-rearD.Q-rear+1=Q-frontA5、不带头结点的单链表head为空的判定条件是（）。A.head==NULLB.head-next==NULLC.head-next==headD.head!=NULLA6、在一个单链表中，若删除p所指结点的后继结点，则执行：（）。A.p-next=p-next-next;B.p=p-next;p-next=p-next-next;C.p-next=p-next;D.p=p-next-next;D7、设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素ai,j(i=j)，在一维数组B的下标位置k的值是（）。A.i(i-1)/2+j-1B.i(i-1)/2+jC.i(i+1)/2+j-1D.i(i+1)/2+jB8、广义表A=((a，b),a)的表头是（）。A.aB.(a,b)C.bD.((a))D9、求整数n（n=0）的阶乘的算法如下，其时间复杂度是（）。intfact(intn){if(n=1)return1;returnn*fact(n-1);}A.o(log2n)B.O(n)C.O(nlog2n)D.O(n2)B10、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表C11、设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队顺序是bdcfeag，则栈S的容量至少是（）。A.1B.2C.3D.4B12、一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（）。A.不确定B.n-i+1C.iD.n-iD13、假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。A.808B.818C.1010D.1020C14、稀疏矩阵一般的压缩存储方法有两种，即（）。A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表C15、设计一个判别表达式中左右括号是否配对出现的算法，采用（）数据结构最佳。A.线性表的顺序存储结构B.队列C.栈D.线性表的链式存储结构C16、当用大小为N的数组存储顺序循环队列时，该队列的最大长度为（）。A.NB.N+1C.N-1D.N-2A17、队列的删除操作是在（）。系班级学号（9位）姓名———————————阅————卷————密————封————装————订————线——————————第2页/共2页A.队头B.队尾C.队头元素后D.队列任意位置D18、设有两个串S1和S2，求串S2在S1中首次出现位置的运算称作（）。A.判子串B.连接C.求子串D.模式匹配C19、算法分析的两个主要方面（）。A.程序复杂性和数据复杂的性B.可读信和文档性C.空间复杂度和时间复杂度D.正确性和简单性B20、求广义表L=((),(a,b,(e,(c,d))),(k,j))的长度和深度分别为（）。A.6，3B.3，3C.6，4D.3，4二、填空题（每空2分，共10分）1、串”ababcebcabc”的next数组值为当j=0时-10012000012。2、设循环队列的容量是70，现经过一系列的入队和出队操作后，front为20，rear为11，则队列中元素的个数为03、队列的特点是先进先出。栈的特点是后进先出。4、二维数组可以按照顺序存储链序存储两种不同的存储方式。三、判断题（每题1分，共5分）（√）1、单链表不是一种随机存储结构。（√）2、栈和队列都是受限的线性结构。（√）3、KMP算法的最大特点是指示主串的指针不需回溯。（√）4、广义表是一种多层次的数据结构，其元素可以是单原子也可以是子表。（×）5、顺序存储只能用于存储线性结构。四、程序填空题(每题4分，共8分)1、有一个带头结的单链表，其结点的元素值以非递减有序排列，下面函数将删除该单链表中多余的元素值相同的结点，请在横线处将程序补充完整。Node*del(node*head){Node*q,*p=head-next;if(head-next!=NULL){while(p-next!=NULL)if(p-data!=p-next-data)P=p-next;else{q=p-next;p-next=q-next;free(q);}}returnhead;}2、写出算法的功能。intfunction(SqQueue*Q,ElemType*e){if(Q-front==Q-rear)returnERROR;*e=Q-base[Q-front];Q-front=(Q-front+1)%MAXSIZE;returnOK;}功能：队列出队五、综合题(7分）编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。typedefstructLNode{Elemtypedate;LNode*next;}LNode,*LinkList;intChangeList(LinkListhead){LNode*p=head;If(head)returnERROR;while(p){p=p-next;}p-next=head;returnOK;}