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

常熟理工学院《数据结构》考试试卷试题总分： 70 分 考试时限:50分钟题号一二三四五总分阅卷人核分人得分一、单项选择题（每题2分，共40分）B1、数据结构是一门研究非数值计算的程序设计问题

系班级学号（9位）姓名 阅————卷————密————封————装————订————线 ————————————————————— 常熟理工学院 《数据结构》考试试卷 试题总分：分考试时限分钟 70:50 核分人 题号 一 二 三 四 五 总分 阅卷人 得分 每题分，共分 240 一、单项选择题（） 、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。 B1 结构关系运算算法 A.B.C.D. 、在以下叙述中，正确的是（）。 B2 线性表的线性存储结构优于链表的存储结构二维数组是其数据元素为线性表的线性表 A.B. 栈的操作方式是先进先出队列的操作方式是先进后出 C.D. 、下面程序段的时间复杂度是（）。 A3 i=s=0; while(s<n){ i++;s+=i; } 2 A.O(n)B.O(n)C.O(logn)D.O(√n) 2 、判断一个循环队列（空间大小为）为空的条件是（）。 A4QM A.Q->front==Q->rearB.Q->rear-Q->front-1==M C.Q->front+1=Q->rearD.Q->rear+1=Q->front 、不带头结点的单链表为空的判定条件是（）。 A5head A.head==NULLB.head->next==NULL C.head->next==headD.head!=NULL 、在一个单链表中，若删除所指结点的后继结点，则执行：（）。 A6p 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; 、设矩阵是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组中，对下三角部分中任一元素 D7AB[1,n(n-1)/2] ，在一维数组的下标位置的值是（）。 ai,j(i>=j)Bk A.i(i-1)/2+j-1B.i(i-1)/2+jC.i(i+1)/2+j-1D.i(i+1)/2+j 、广义表，的表头是（）。 B8A=((ab),a) A.aB.(a,b)C.bD.((a)) 、求整数n（n>=0）的阶乘的算法如下，其时间复杂度是（）。 D9 intfact(intn) { if(n<=1)return1; returnn*fact(n-1); } 2 A.o(logn)B.O(n)C.O(nlogn)D.O(n) 22 、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。 B10 A．单链表B．仅有头指针的单循环链表 C．双链表D．仅有尾指针的单循环链表 、设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队顺序 C11 是bdcfeag，则栈S的容量至少是（）。 A.1B.2C.3D.4 、一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。 B12 A.不确定B.n-i+1C.iD.n-i 、假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]= D13 （）。 A.808B.818C.1010D.1020 、稀疏矩阵一般的压缩存储方法有两种，即（）。 C14 二维数组和三维数组三元组和散列三元组和十字链表散列和十字链表 A.B.C.D. 、设计一个判别表达式中左右括号是否配对出现的算法，采用（）数据结构最佳。 C15 线性表的顺序存储结构队列栈线性表的链式存储结构 A.B.C.D. N 、当用大小为的数组存储顺序循环队列时，该队列的最大长度为（）。 C16 A.NB.N+1C.N-1D.N-2 、队列的删除操作是在（）。 A17 1/2 第页共页