《数据结构》期中试卷-2014-2015学年第二学期

《《数据结构》期中试卷-2014-2015学年第二学期》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、此…处…不…能…书写…北京理工大学珠海学院………此…2014～2015学年第二学期《数据结构》期中试卷处…不能…诚信声明专业：书…写…考场是严肃的，作弊是可耻的，对作弊人的处分是严厉的。…班级：我承诺遵守考场纪律，不存在抄袭及其它违纪行为。……考生（承诺人）签字：学号：…此处装适用年级专业：14级软件工程试卷说明：闭卷，考试时间90分钟不…能…题号一二三四总分书…写…得分………一、单项选择题（每小题2分，共30分）【得分：】…此…1、设计一个判别表达式中左、右括号是否配对出现的算法，采用()数据处…不结构最佳。能

2、…书…A.线性表的顺序存储结构B.栈写订C.队列D.线性表的链式存储结构……2.下面两段程序的时间复杂性是（）。……（1）i=1;此…处while(i<=n)…不…i=i*2;能书…（2）for(i=2;i<=n;++i)写……for(j=2;j<=i-1;++j)线{++x;……a[i][j]=x;此…处…}不…22能…A.O(log2n)，O(n)B.O(n),O(n)书…2C.O(n),O(n)D.O(log2n),O(n)写……3、带头结点的单链表为空的判定条件是（）。…A.head==NULLB.hea

3、d->next==NULL……C.head->next==headD.head!=NULL此…处…4.在一个具有n个单元的顺序栈中，假设栈底是存储地址的低端，现以top作不…能…第1页共7页书…写…………为栈顶指针（指向栈顶元素的下一个位置），当进行出栈操作时，假定栈非空，top的变化是()。A.top=top+1B.top=top-1C.top不变D.top不确定5.一个栈的入栈序列为a，b，c，d则出栈序列不可能的是()。A.a，b，c，dB、c，b，a，dC.d，c，b，aD、d，b，c，a6、二维数组SA

4、中，每个元素的长度为3个字节，行下标I从0到7，列下标J从0到9，从首地址SA开始连续存放在存储器内，该数组按行优先存放时，元素A[6][8]的起始地址为（）。A.SA+210B.SA+171C.SA+204D.以上都不对7.在数据结构中，从逻辑上可以把数据结构分成（）。A.动态和静态结构B.紧凑接和非紧凑结构C.线性与非线性结构D.内部结构和外部结构8.链表不具有的特点是（）。A.可随机访问任一元素B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表长度成正比9.在一个单链表中，已知q是p的前

5、趋结点，若q和p之间插入结点s，则执行（）。Ａ.s->next=p->next;p->next=s;Ｂ.p->next=s->next;s->next=p;Ｃ.q->next=s;s->next=p;Ｄ.p->next=s;s->next=q;10.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。A.顺序表B.单链表C.双向链表D.循环链表11、下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．

6、串既可以采用顺序存储，也可以采用链式存储12.循环链表主要优点是（）。A.不再需要头指针了B.已知某个结点的位置后，能够容易找到它的直接前趋C.在进行插入、删除运算时，能更好地保证链表不断开D.从表中任一结点出发都能扫描到整个链表13.删除双链表中间某个节点时，需要修改（）个指针域。A.1B.2C.3D.414.循环队列SQ采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front和rear，则判定此循环队列为空和为满的条件分别是（）第2页共7页此…处…不…能书…A.Q.front!=Q

7、.rear,Q.front==Q.rear写…B.Q.front==Q.rear,Q.front!=Q.rear……C.Q.front==Q.rear,Q.front==(Q.rear+1)%n…D.Q.front==Q.rear,Q.front!=(Q.rear+1)%n此…处15.利用栈求表达式的值时，设立操作数栈OPND，假设OPND只有两个存储单…不…元，在下列表达式中，不发生溢出的是（）。能书…A.A-B*(C-D)B.(A-B)*C-DC.(A-B*C)-DD.(A-B)*(C-D)写…………二、填空

8、题（每空2分，共20分）【得分：】…此1.若一个算法中的语句频度之和为T（n）=3n+n*log2n+4，则算法的时间复杂处装不…度为______。能…2.假设为循环队列分配的向量空间为Q[20]（下标从0开始），若队列的长度书…写…和队头指针值分别为13和17，则当前队尾指针的值为。……3.表长为N的顺序表，当在任何位置上插入或删除一个元素的概率相等时，…插入一个元素所