××科技大学成都学院二零零八至二零零九学年第一学期一．填空题（每空2分，共40分）；1.数据结构算法中，通常用时间复杂度和__空间复杂度___两种方法衡量其效率。

2.下面程序段的时间复杂度为___O(n2)______。

(n>1)for(i = 1; i <= n; i++)for(j = 1; j <= i; j++)x = x + 1;3.静态链表中指针表示的是______下一结点的地址______。

4.线型表、栈和队列都是____线型_______结构，可以在线型表的____任意___位置插入和删除元素；对于栈只能在____栈顶_____插入和删除元素；对于队列只能在____队尾___插入元素和_____队头_____删除元素。

5.在具有n个单元的循环队列中，队满时共有_____n-1____个元素。

6.在一个长度为n 的顺序表中第i 个元素（1<=i<=n）之前插入一个元素时，需向后移动__n-i+1__个元素。

7.在n个结点的单链表中要删除已知结点*p，需找到它的_____前驱________。

8.带有一个头结点的单链表head为空的条件是_________head->next==NULL__________。

9.在栈顶指针为hs的链栈中，判断栈空的条件是_________hs= =NULL__________。

10.在hq的链队列中，判定只有一个结点的条件是__hq.front->next==hq.rear________。

11.非空的循环单链表head的尾结点（由p指向），满足条件____p->next==head。

12.两个串相等的充分必要条件是______串长相等且对应字符相等_______。

13.空串是_______长度为0的串______，其长度等于___0________。

14.空格串是______由空格字符组成的串______，其长度等于_____空格的个数_________ 。

1.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表2.设a1、a2、a3为3个结点，则如下的链式存储结构称为：AA．循环链表 B．单链表 C．双向循环链表 D．双向链表3.有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（B ）A. 5 4 3 6 1 2B. 3 4 6 5 2 1C. 4 5 3 1 2 6D. 2 3 4 1 564.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i 个栈( i =1,2)栈顶，栈1 的底在v[1]，栈2 的底在V[m]，则栈满的条件是（B ）。

A. top[2]-top[1]|=0B. top[1]+1=top[2]C. top[1]+top[2]=mD. top[1]=top[2]5.数组Ｑ［ｎ］用来表示一个循环队列，front为当前队列头元素的前一位置，rear为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为(D)A. rear－frontB.（n＋front－rear）% nC. n＋rear－frontD.（n＋rear－front）% n6.设栈S 和队列Q 的初始状态为空，元素e1，e2，e3，e4,e5 和e6 依次通过栈S，一个元素出栈后即进队列Q，若6 个元素出队的序列是e2，e4,e6,e5，e3,e1 则栈S 的容量至少应该是( B)。

A． 6 B. 4 C. 3 D. 27.在数据结构中，从逻辑上可以把数据结构分成（C）。

8. A．动态结构和静态结构 B．紧凑结构和非紧凑结构9. C．线性结构和非线性结构 D．内部结构和外部结构10.判定一个顺序栈ST（最多元素为N）为空的条件是（B ）。

A．ST．top ！= ST.base B．ST．top==ST.baseC．ST．top！=N D．ST．top==N11.一个队列的入列序列是1，2，3，4，则队列的输出序列是 B 。

A．4,3,2,1 B．1,2,3,4 C．1,4,3,2 D．3,2,4,112.判定一个循环队列QU(最多元素为N)为空的条件是 C 。

A．QU.front== （QU.rear+1）%N B．QU.front！= （QU.rear+1）%NC．QU.front== QU.rear D．QU.front！= QU.rear13.判定一个循环队列QU（最多元素为m0）为满队列的条件是 A 。

A．QU.front== （QU.rear+1）%N B．QU.front！= （QU.rear+1）%NC．QU.front== QU.rear D．QU.front！= QU.rear+114.不带头结点的单链表head为空的判定条件是 AA．head=NULL B．head - >next=NULL C．head- >next=headD．head!=NULL15.15.在双向链表指针p 的结点前插入一个指针q 的结点操作是（C ）。

A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;16.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较___D___个结点。

A．n B．n/2 C．(n—1)/2 D．(n+1)/2 17.设串s1=‘ABCDEFG’,s2='PQRST',函数con(x,y)返回x和y串的连接串，subs（s,i,j）返回串s的从序号i的字符开始的j个字符组成的字串， len(s)返回串s的长度，则con(subs(s1,2,len(s2)), subs(s1,len(s2),2))的结果串是 D A）BCDEF B）BCDEFG C）BCPQRST D）BCDEFEF三．综合题（每题6分，共30分）1.线性表具有两种存储方式，即顺序方式和链接方式。

现有一个具有五个元素的线性表L={23，17，47，05，31}，若它以单链表方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节,由大写字母表示）组成，如下所示：100其中指针p，q，r，s，t的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？(共6分)2.答：p= 108 q = 116 r = 112 s= 0 或NULLt= 100 首址= 104 末址= 112 。

3.如果想将输入的一个字符序列逆序输出，如输入“abcdef ”，输出“fedcba”，请分析用线性表、堆栈和队列等方式正确输出的可能性？(共6分)线性表是随机存储，可以实现，靠循环变量（j--）从表尾开始打印输出；堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；队列是先进先出，不易实现。

4.写出删除顺序表中第i个元素的算法：(共6分)Status ListDelete_sq(SqList &L, int i, ElemType &e) Status del_sqllist(SqList &L,int i, ElemType &e) {if (i < 1‖i > L.length) return ERROR;e= L.elem[i];for (j=i+1;j<= L.length;j++)L.elem[j-1]= L.elem[j];--L.length;return OK;}5.写出顺序栈的入栈算法(共6分)Status Push(SqStack &S, SelemType e)void Push ( Stack &S, ElemType e ){ //在栈顶之上插入元素e为新的栈顶元素p = new LNode ; // 建新的结点if(!p) exit(1) ; // 存储分配失败p -> data = e;p->next=S.top ;// 链接到原来的栈顶S.top = p; // 移动栈顶指针++S.length;// 栈的长度增1} // Push6.写出链队列的出队列算法(共6分)Status DeQueue(LinkQueue &Q, QelemType &e)Status DeQueue (LinkQueue &Q, QElemType &e) {// 若队列不空，则删除Q的队头元素，//用e 返回其值，并返回OK；否则返回ERRORif (Q.front == Q.rear) return ERROR; p = Q.front->next; e = p->data;Q.front->next = p->next;if (Q.rear == p) Q.rear = Q.front;free (p); return OK;}××科技大学成都学院2008~2009学年第一学期中期试题——数据结构答案一．填空题（每题2分，共40分）；二．单项选择题（每题2分，共30分）；三．综合题（共30分）7.p= 108 q = 116 r = 112 s= 0 或NULLt= 100 首址= 104 末址= 112 。

8.线性表是随机存储，可以实现，靠循环变量（j--）从表尾开始打印输出；堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；队列是先进先出，不易实现。

3．Status del_sqllist(SqList &L,int i, ElemType &e){if (i < 1‖i > L.length) return ERROR;e= L.elem[i];for (j=i+1;j<= L.length;j++)L.elem[j-1]= L.elem[j];--L.length;return OK;}4.void Push ( Stack &S, ElemType e ){ //在栈顶之上插入元素e为新的栈顶元素p = new LNode ; // 建新的结点if(!p) exit(1) ; // 存储分配失败p -> data = e;p->next=S.top ;// 链接到原来的栈顶S.top = p; // 移动栈顶指针++S.length;// 栈的长度增1} // Push5．Status DeQueue (LinkQueue &Q, QElemType &e) { // 若队列不空，则删除Q的队头元素，//用e 返回其值，并返回OK；否则返回ERRORif (Q.front == Q.rear) return ERROR;p = Q.front->next; e = p->data;Q.front->next = p->next;if (Q.rear == p) Q.rear = Q.front;free (p); return OK;}全真模拟试题（一）一、单项选择题（在每小题的4个备选答案中，选出正确的答案，并将其号码填在题干的括号内。